Introduction
Topological data analysis claims it can find the shape of a data set: its clusters, its loops, its holes. The way it does this is easiest to see on a data set small enough to work by hand, where you already know the answer.
This reading takes eight points arranged around a circle and follows, threshold by threshold, how a loop appears, persists, and is finally filled in. It ends with the "barcode" that summarizes what was found.
The Starting Point
You have a point cloud: a set of data points together with a way of measuring the distance between any two of them. This one has eight points spaced evenly around a circle of radius 1, like the hours on a clock with only eight marks. Label them 1 to 8 going around. The distance between two points is the ordinary straight-line distance.
The procedure, which Gunnar Carlsson's survey describes in general form, has one rule and one setting (Carlsson 2009):
- The rule. Pick a distance, called the threshold. Join any two points whose distance is at most the threshold with a line. Then fill in any triangle whose three sides are all drawn.
- The setting. Don't fix the threshold. Sweep it from small to large and watch what changes.
The aim is to see which features last.
Walking Through the Threshold Sweep
Step 1: Compute the distances
Because the points are evenly spaced, there are only four different distances. Put point 1 at (1, 0). Its neighbor, point 2, is an eighth of the way around, at about (0.707, 0.707). By the Pythagorean theorem,
d = \sqrt{(1 - 0.707)^2 + (0.707)^2} = \sqrt{0.0858 + 0.5} \approx 0.77
The same method gives the other distances. Point 3 is at (0, 1), so points two steps apart are \sqrt{1 + 1} = \sqrt{2} \approx 1.41 apart. Points three steps apart are about 1.85 apart. Opposite points, four steps apart, are 2 apart, the diameter of the circle.
| Steps apart | Example pair | Distance |
|---|
| 1 (neighbors) | 1 and 2 | about 0.77 |
| 2 | 1 and 3 | about 1.41 |
| 3 | 1 and 4 | about 1.85 |
| 4 (opposite) | 1 and 5 | 2 |
Step 2: Connect points closer than 0.5
At a threshold of 0.5, no two points are close enough to join, since the smallest distance is about 0.77. You see eight separate dots. In topological terms there are eight clusters, groups of points connected to each other but not to the rest, and no other structure. This is what any data set looks like at a small enough threshold.
Step 3: Raise the threshold past 0.77
As soon as the threshold reaches about 0.77, every point joins its two neighbors. The eight dots become an octagon. Two things have happened at once. The eight clusters have merged into one. And a loop has appeared: a closed path of connections around an empty middle.
No triangles are filled in yet. A triangle needs all three of its sides drawn, and any three of these points include at least one pair more than 0.77 apart.
Step 4: Raise it further and watch the loop persist
At a threshold of about 1.41, points two steps apart join too. Now triangles appear: points 1, 2, and 3 are joined in pairs, so that triangle is filled in, and likewise for every run of three neighbors. These eight thin triangles form a band around the edge of the circle. The middle is still empty, so the loop is still there.
The loop survives until the threshold reaches about 1.85. At that value, points three steps apart join. Now there are triangles that reach across the middle. For example, points 1, 4, and 6 are joined in pairs: 1 to 4 is three steps, 4 to 6 is two steps, and 6 to 1 is three steps going the short way around. Triangles like this cover the empty center, and the loop is filled in. By a threshold of 2, every pair of points is joined and the cloud is one solid blob.
You can confirm that nothing crosses the center before 1.85. Below that threshold, every filled triangle uses three points within two steps of each other, so every triangle stays in the band near the edge.
Step 5: Read the barcode
Now record each feature as a bar, from the threshold where it appears to the threshold where it disappears. This set of bars is the barcode.
- Eight cluster bars start at 0. Seven end at about 0.77, when the dots join; one lasts forever, since everything stays connected from then on.
- One loop bar starts at about 0.77 and ends at about 1.85.
The loop bar is long: it lasts across more than a whole unit of threshold. Its persistence, the range of thresholds over which a feature in a data set survives, is about 1.85 - 0.77 = 1.08. In real data there would also be short bars, small loops that open and close almost at once because of random gaps between points. Carlsson's reading is that long bars correspond to large-scale features of the space the data came from, and short bars to noise or sparse sampling (Carlsson 2009). The long loop bar here says that the data lie around a circle, which is true.
Figure: The eight points on a circle shown at three thresholds, side by side: separate dots at 0.5; an octagon with an empty center at 1.0; and the octagon with filled triangles crossing the center at 1.9. Alt text: Three panels of eight points in a ring, first unconnected, then joined into an octagon, then filled in across the middle.
Key Considerations
The filling threshold depends on the construction. The rule used here fills a triangle once its three sides are drawn. Another common construction grows a disk around each point and fills in whatever region the disks cover, with the threshold measured as the disks' diameter. With that rule, the loop appears at the same threshold, about 0.77, when neighboring disks touch, but it isn't filled until the disks cover the center of the circle, at a threshold of 2. Both constructions find the same loop. They disagree about exactly where it ends, which is why the barcode is read for long versus short bars rather than for exact endpoints.
The common mistake: treating any loop at one threshold as real. If you look at a data set at a single threshold and see a loop, you don't yet know whether it reflects the data's shape or a chance gap between a few points. A chance loop usually closes as soon as the threshold rises a little. The point of the sweep is to see how long each feature lasts. A loop is believable when it persists over a wide range of thresholds, not when it appears once.
What the method doesn't tell you. The barcode reports that the data lie around a loop. It doesn't report the loop's size or position, and it doesn't explain why the data have that shape. Those questions need other tools.
Summary
Sweeping the threshold over eight points on a circle turns separate dots into an octagon with one loop, which persists from about 0.77 to about 1.85 before triangles fill it in.
| Threshold | What you see | Clusters | Loops |
|---|
| 0.5 | Eight separate dots | 8 | 0 |
| 1.0 | Octagon around an empty center | 1 | 1 |
| 1.6 | Octagon plus a band of thin triangles; center still empty | 1 | 1 |
| 1.9 | Triangles across the center; loop filled in | 1 | 0 |
| 2.1 | Every pair joined; one solid blob | 1 | 0 |
- The clusters merge into one at about 0.77, the distance between neighbors.
- The loop is born at about 0.77 and dies at about 1.85, a persistence of about 1.08.
- The long-lived loop is the shape of the data: the points lie on a circle.
References
- Carlsson, Gunnar. 2009. "Topology and Data." Bulletin of the American Mathematical Society 46: 255–308. doi:10.1090/S0273-0979-09-01249-X.