Clustering methods like Mean Shift or k-Means are executed and if necessary, re-started with different parameters. This standard approach of providing input data, executing an algorithm, observing the outcome and re-running the method with different parameters completely neglects the insights which can be gained considering to look at the core of an clustering algorithm. In this work we provide an approach to analyze the trajectories of data points within a run of a clustering method. Thereby we also introduce the concept of data point entanglement, revealing if subsets of data points have common trajectories over the iterations of an clustering algorithm. Further we introduce the idea of data point resilience, whose intuition is to reflect if a subset of data points maintains its entanglement even at different hyperparameter settings.
Within the past decades a rich set of various clustering methods has been
developed, aimed at different tasks such as detecting convex clusters such as k-means
[
We take as an example to explain the concept of data point entanglement the two-moons data set consisting of fifty data points. The two-moons data set consists of two opposing moon-shaped two-dimensional figures as it can be seen in figure 1 top left figure. We execute the Mean Shift algorithm with a bandwidth of 0.3. In figure 1 it can be seen how the points are dragged into two modes over the ten iterations. Definition 1. Storing the position of each of the data points p ∈ D at all iterations i ∈ I yields a trajectory θ ∈ T for each data point. Two data points pi, pj are entangled if dDT W (θpi , θpj ) ≤ τ where the smaller the threshold τ is chosen, the more entangled are the two data points.
The core intuition behind definition 1 is that the more similar the trajectories of two data points are, the more entangled the two observed data points. As a measure of similarity of trajectories we have utilized dynamic time warp (DTW). In context of time series analysis DTW is widely used to determine how well given time series align. Due to the brevity of this paper, we remain using here DTW for the rest of this work, yet want to emphasize that further research regarding other distance measures is a vital topic. Having the DTW distance between two data point iteration trajectories, we define a distance matrix as follows: Definition 2. An entanglement matrix M is a distance matrix where each of its elements mij ∈ M is a pairwise distance dDT W (θpi , θpj ) between two data point trajectories θpi , θpj as stated in definition 1.
Such an entanglement matrix can be seen in figure 2 which is based on the two-moons data set mentioned before. Here we can see all pairwise data point trajectory similarities, where a dark color implies a high similarity between two data point trajectories and a bright color means the opposite. As the entanglement matrix is symmetric, we can omit either the lower or upper triangle. Further we can also exclude the diagonal from our observations as a data point trajectory is always maximum similar to itself.
Visualizing the trajectories of each data point results in a pattern as seen in figure 3 where the movement of the data points is directed towards two centers (modes).
Based on the data from the entanglement matrix from figure 2 we have selected three tuples of data points which have an very low DTW distance on their trajectories, namely p38 = (0.5, −0.366025404), p39 = (0.965925826, 0.258819045), p40 = (0.617316568, −0.423879533). We computed their scores at a bandwidth of 0.5, 0.4, 0.3, 0.2, 0.1 and 0.05 on the two-moons data set. In figure 4 it becomes immediately visible that the low DTW distance and thus the high entanglement between (p38, p40) remains mostly the same while on the other two data point pairs the DTW distance increase massively at lower bandwidths weakening their entanglement. This phenomenon of a stable level DTW distance we define as follows:
Definition 3. The entanglement between two data points pi, pj is coined with the term resilience ρ if the variance of the DTW distance of their respective trajectories at different hyperparameter settings λ ∈ Λ is small, meaning that the resulting value ρ is close to zero.
ρ(θpi ,θpj )Λ = var(dDT W (θpi , θpj )Λ) = Λ1 X(dDT Wλ (θpi , θpj ) − μΛ)2 | | λ∈Λ (1)
Based on the equation above the resilience of the entanglement between two data point trajectories can be computed. Intuitively spoken, it reflects the variance of the distance of two data point trajectories at different hyperparameters λ regarding the mean which is defined as the average of the distance of two data point trajectories over all chosen hyperparameters λ: μΛ := |Λ1| Pλ∈Λ dDT Wλ (θpi , θpj ). Having such a measure, the immediate question is what it can be used for. The entanglement resilience can serve as an indication for a subset of data points which have a strong relation to each other regardless the choice of different hyperparameters. Applying definition 3 to our example of the data points trajectory tuples (p38, p39), (p39, p40) and (p38, p40)leads to the following values: ρ(p38,p39) = 13.51, ρ(p39,p40) = 13.66 and ρ(p38,p40) = 0.23. This small value supports our observation from figure 4 that the trajectories of the data points 38 and 40 remain similar to each other at different hyperparameters. 4
In our work we have introduced two core concepts, namely the data points entanglement and the entanglement resilience. Both are primarily aimed to be used in context of interactive clustering tools such as PARADISO. They can be either used to automate steps within an algorithm or to provide additional information to the users, serving as a basis for their decisions in the interactive setting. Future work encompasses the extension and application on high-dimensional settings and a broader range of clustering algorithms at which this concept is applicable. Further the choice of the threshold τ as mentioned in definition 1 requires further investigations approaching questions such as: How τ should be chosen, and if this parameter can be learned or estimated. One of the major motivations of this work is to catalyst the development of methods which reveal patterns that take place ’under the hood’ of the clustering algorithms, leveraging the understanding of such methods.