cs.LGFeb 24, 2026
SaveIntroducing Feature-Based Trajectory Clustering, a clustering algorithm for longitudinal data
Abstract
We present a new algorithm for clustering longitudinal data. Data of this type can be conceptualized as consisting of individuals and, for each such individual, observations of a time-dependent variable made at various times. Generically, the specific way in which this variable evolves with time is different from one individual to the next. However, there may also be commonalities; specific characteristic features of the time evolution shared by many individuals. The purpose of the method we put forward is to find clusters of individual whose underlying time-dependent variables share such characteristic features. This is done in two steps. The first step identifies each individual to a point in Euclidean space whose coordinates are determined by specific mathematical formulae meant to capture a variety of characteristic features. The second step finds the clusters by applying the Spectral Clustering algorithm to the resulting point cloud.
Figures & tables
Figure 1: A trajectory of lenght and its underlying function . The observations times are , , , , , , , .
Figure 2: In this example, the maximum of the the underlying function (in grey) is 10 so the value of the functional measure is 10. The underlying has been observed five times, resulting in a trajectory (black points) of lenght 5. The maximum value of the trajectory is 9.5 so the value of the trajectory meansure is 9.5.
Figure 3: On the left, the area under the curve (in grey) represents the value of the integral . On the right, this integral is approximated from a trajectory using the trapezoid rule of numerical integration. For any two consecutive points , , a rectangle is constructed with base equal to the distance between the observation times and heigh equal to the average of the coordinates, . The trapezoidal approximation to is the sum of the areas of the 7 rectangles constructed this way. In the present case, the true value of the integral is 75.2 and the trapezoidal approximation is 75.1.
Figure 4: The image on the left shows, for each point of the trajectory, a small segment of the line whose slope is given by the approximation to the derivative. A good approximation is one for which the red line is almost tangent to the graph. We see that the approximation is lacking especially at the fifth and sixth point, but at least every approximation carries the correct sign. The image on the right shows the graph of the derivative of the underlying function (pink) as well as its approximation at the observation times (red dots). We see that the approximation is farthest from the graph at the fifth and sixth point, in agreement with our previous observation.
Figure 5: The image on the left shows the graph of the derivative of the underlying function (pink) as well as its approximation at the observation times (red dots) and, in blue, a small segment of the line whose slope is approximated using . A good approximation is one for which the blue line is almost tangent to the graph. The approximation is worst than that of , which is to be expected since the approximation is itself built from an approximation. However, except for the first two points the signs are correct. The image on the right shows the graph of the true value of (light blue) against the approximations (blue dots).
Figure 6: The image on the left shows a function that has both regions of convexity (blue) and regions of concavity (red). The regions of convexity correspond exactly to the regions where the second derivative is positive while the regions of concavity are those where the second derivative is negative. The image of the right is the graph of the function and is an example of a globally concave function, meaning that it has only a region of concavity. This synthetic statement is equivalent to the fact that the second derivative, , is everywhere negative.
Figure 7: The possible values for the point . The black line suggests a constant underlying function. Region suggests a positive underlying function. Region suggests a negative underlying function. In region , the underlying function assumes both positive and negative values.
Figure 8: The mean of as the height of the rectangle whose area equals the area under the curve of . In the present case, .
Figure 9: Superimposed on the trajectory and underlying function from Figure 2 are the best affine approximation of the underlying function (pink) and its estimation using the trajectory (red).
Figure 10: Let denote the subspace of affine functions. The affine function closest to is the orthogonal projection of onto . Let denotes said orthogonal projection. Since the constant function belongs to , the functions and are orthogonal to each other. Therefor, we have the Pythagorean decomposition ( [ 2 ] Theorem 2.6).
Figure 11: The total variation of is the total lenght of the horizontal segments (in red). In this case, this number is approximately .
Figure 12: The area under the mean (pink) is the same as the area above the mean (light blue). However, the time spent above the mean (total lenghts of the blue segments) is less than the time spent below the mean (total lenghts of the red segments). This is symptomatic of an upward spike, and indeed, there it is at the end.
Figure 13: The function on the left has an upward spike and a downward spike of equal magnitude. The function on the right has no spikes at all. Yet, in both cases, an illustration of the fact that measures the ”net spikiness”.
Figure 14: If is below (resp. above) the mean at two subsequent observation times, we assume that the same holds at all intervening times. On the contrary, if passes from below the mean to above the mean (or vise versa), we assume that it crosses the mean precisely at the midpoint between the two observation times. In the above plot, this leads to approximating as the total lenght of the blue segments and to approximating as the total lenght of the red segments. If two consecutive points were to lie directly on the mean, the time interval between them would count towards neither nor .
Figure 15: The possible values for the point . The black line suggests an affine underlying function. Region (resp . ) suggests an increasing (resp. decreasing) underlying function. In region , the underlying function assumes both regions of growth and of decline.
Figure 16: The possible values for the point . The identity line (in black) suggests a quadratic underlying function. Region (resp . ) suggests a globally convex (resp. globally concave) underlying function. In region , the underlying function assumes both regions of convexity and of concavity.
| 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 | 100 | |
|---|---|---|---|---|---|---|---|---|---|
| 3 | 4 | 5 | 6 | 8 | 8 | 8 | 8 | 8 | 8 |
| 4 | 4 | 4 | 5 | 6 | 7 | 8 | 8 | 8 | 8 |
| 5 | 3 | 4 | 4 | 5 | 6 | 7 | 8 | 8 | 8 |
| 6 | 2 | 4 | 4 | 4 | 5 | 5 | 6 | 7 | 8 |
| 7 | 2 | 3 | 4 | 4 | 4 | 5 | 5 | 6 | 7 |
| 8 | 2 | 3 | 4 | 4 | 4 | 4 | 5 | 5 | 6 |
Table 1: Values of corresponding to various combinations of the sample size and the number of groups
Figure 17: Clusterings proposed by FBTC, klm and lcmm
Figure 18: A random sample of 10 trajectories from each of the 6 groups of the Symbols data set
| 204 | 171 | 168 | 163 | 163 | 126 | |
|---|---|---|---|---|---|---|
| 173 | 109 | 63 | ||||
| 157 | 95 | 62 | ||||
| 164 | 1 | 163 | ||||
| 178 | 168 | 9 | 1 | |||
| 159 | 3 | 156 | ||||
| 164 | 2 | 162 |
Table 2: The rows correspond to the true groupings whereas the columns correspond to the clustering proposed by FBTC
Figure 19: A random sample of up to 10 trajectories from each of the 4 groups comprising the Fungi data set
Figure 20: A random sample of 10 trajectories from each of the 6 groups comprising the ShapesAll data set
More in this topic
Time Series Clustering
Time series clustering groups sequences by shared temporal patterns, regimes, trajectories, or behaviors without requiring labeled examples.
See all 27 papers