# Models for describing cluster change over time

Suppose I have a set of observations encoded as a matrix $$X$$ whose entries $$X_{it} \in \mathcal{C}$$ correspond to cluster labels of experimental unit $$i$$ with repeated measures at time $$t$$, where $$\mathcal{C}$$ denotes a finite set of nominal cluster indicators. For clarity, here nominal is meant to emphasize that particular values of $$x_{it}$$ have no inherent value, and are only meaningful given other $$x_{it}$$s values.

What models are suitable for describing the change in clusters over time?

• Usually, one talks about "clustering", if the measurements have certain attributes which allow to talk about some kind of distance between them. If you don't have those attributes, what is the basis of your clustering? Feb 25, 2022 at 7:02
• @frank right, I agree that's usually the case. For an illustrative example, what if I observe clustering of friends, but can't observe their individual characteristics? I know person 1,3,5 were together and 2, 4, 6 were together on day one, but know nothing else about these people. The next day, I learn person 1, 2, 3, 4, 5 are together and person 6 is alone, and again I know nothing else about these people.
– user
Feb 25, 2022 at 7:07
• OK, so you have a time-dependent set partition of your data. And you want to find a notion of similarity between your set partitions. So you can predict future partitions? What are your constraints? E.g. is the number of subsets in each partition constant? Is there an upper limit of how different two consecutive set partitons can be? Feb 25, 2022 at 7:23
• @frank prediction would be a dream but it is not necessarily the ultimate goal. I don't have a hypothesis; I am merely interested in ways such a process might be described/modelled mathematically. As for constraints, there are none except maybe the number of subsets is variable across time but less than some constant $K$.
– user
Feb 25, 2022 at 7:35
• $K\ll N$ where $N$ is the number of experimental units.
– user
Feb 25, 2022 at 7:45

Let's denote by $$S$$ the basic set which contains the elements that are grouped in clusters. So the clusters $$C_i$$ are subsets of $$S$$. Now, IIUC, we want the following properties to hold:

1. Any two different clusters $$C_i$$ and $$C_j$$ are disjoint ($$C_i\cap C_J = \emptyset, i\ne j$$).
2. All clusters together cover the whole set $$S$$ ($$\bigcup_{i=1}^K C_i = S$$)

In other words, the clustering is a set partition. So the goal is to better describe the space of set partitions; lets call it $$\cal P$$.

I think the first step would be to find a metric (or some weaker version of a metric) for $$\cal P$$. Once you have a metric, you can do all kinds of things, e.g. talk about groupings (that would then be "clusters of clusterings").

Since $$\cal P$$ is discrete and finite, we could maybe then think of this space as a graph, with the metric giving us a similarity value on each edge. We could cut all the edges below a certain similarity, so the graph would not have to be complete.

As far as the notion of a metric is concerned, the author of the question already mentioned the rand index; another possibility is e.g. based on the Fowlkes-Mallows index. You could also use mutual information.

For a similar question, see here.

Then, your time series of clusterings becomes a walk in the graph. You could define transition probabilities derived from the similarity values on the edges and could thus obtain some graph random walk. This would help do predictions.

• Oo I like the idea of modelling the partitions as random walks! From a practical perspective, how should I implement this approach to compute the transition probabilities? Presumably this would involve a summation with a number of terms in the order of the size of the set of all partitions, which is intractable for any realistic sample size $N$?
– user
Feb 25, 2022 at 14:35
• You could think about only considering neighboring partitions, those that need only a small number of atomic changes to get converted into each other. Or you find a metric with easy to compute upper bound and then only compute the proper metric with those that have an upper bound above a certain threshold. The problem of high complexity is however probably baked-in when considering the space of clusterings... Feb 25, 2022 at 14:51
• I searched "distance between set partitions" on google scholar, and found e.g. this one: citeseerx.ist.psu.edu/viewdoc/… Feb 25, 2022 at 14:59

A challenge in modelling cluster change over time is the inherently nominal values of cluster indicators. One way to work around this roadblock is to define random variables whose values correspond to the discrepancy between contiguous measures of partitions. In other words, define new random variables $$Y_t=D(X_{\cdot t}, X_{\cdot t-1})$$ for some sensible map $$D$$ measuring the discrepancy or similarity of two partitions. Then the problem simplifies to modelling a set of univariate time series data. For example, $$D$$ could be the rand index.
More generally, the idea is to define some sensible test function that maps partitions to real numbers, e.g., one could imagine computing the discrepancy of each partition versus some constant partition instead of computing the discrepancy between contiguous partitions. For this particular example, the interpretation can become fuzzy, as the range of values is limited, i.e., $$D$$ is not injective. The challenge now becomes finding a sensible test function, which likely depends on the data at hand.