Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
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?
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:
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.
To get the brainstorm-ball rolling, I'll start with a naive proposal.
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.
