Validate Cluster Analysis by doing it on two subsamples

Question

I am working on validating a cluster analysis. I have read somewhere the approach to cross-validate the cluster analysis. The link of the article is http://jonathantemplin.com/files/clustering/psyc993_03.pdf -

1. Divide data into two subsets: A and B.
2. Apply clustering algorithm to A – get c classes.
3. Each object in B is assigned to “closest” class in A.
4. Apply clustering algorithm to B – get c classes.
5. Compare partitions of B (based on #3 and #4).
– If agreement is high, have high confidence in result

Regarding the 5th point, do "partitions" refers to cluster members? How can we calculate agreement between both the partitions? Is it a valid technique to cross-validate the cluster analysis?

Answer 1

Yes, you can do it. This sort of cross-validation or staibility check aims against overfitting always catching one with a single sample. It is just one among possible strategies. (I'm not in agreement with @Anony-Mousse statement that to use the approach you have to use only clustering based on centroids. But what is true is that A and B subsamples must be about the same size and formed randomly. And the size be large enough, for all the "true" clusters, if any, show up in both halves.)

I have some points to stress.

1. Assignment to closest cluster (pt 3) must be methodologically isomorphic to the clustering method used (e.g. if the method of clustering was hierarchical farthest neighbour so farthest neighbour (only not hierarchical) should be the assignment)$^1$.
2. Actually, you don't have to produce just the same number of clusters c in both clusterings. Due to possible outliers/noise points, it might be that (say) a 6-cluster solution on A be most similar to 7 cluster solution on B. So, try a small range of solutions on A, on B, and compare between them all (after the assignment of the points of B an A solution).
3. The comparison may be as follows. To compare a clustering solution (partition) produced on B with a one produced on (A + assignment of B-points to the A-clusters) construct 2 binary square matrices between all the B-points, wherein 0 = the two points are in different clusters; 1 = in the same cluster. One matrix is for the assignment results, the other matrix is for the clustering-of-B results. Compare the two matrices by, say, computation of cosine similarity (= Ochiai measure) between them (you can just unwrap the triangular parts of the symmetric matrices into two vectors and compute the measure for the vectors).

---

$^1$ _{I have written a function doing simultaneous or progressive assignments of new objects to clusters obtained after hierarchical clustering, 10+ methods of linkage. It is for SPSS, and found on my personal web-page.}

Answer 2

This is a stability test, but it is unclear to me when you can use this well. There are two hidden assumptions here:

1. running the algorithm again (on the other half) is likely to produce a similar result (questionable for k-means type algorithms that are sensitive to initialization)
2. centroid-type models (k-means type) where assigning objects to their nearest center is meaningful.

IMHO the A/B split would make more sense for DBSCAN (which does not involve randomness), but 1. assigning to the nearest cluster does not work well there (what about noise?), and 2. the parameters of DBSCAN will likely not apply to the full data set. The approach you outlined is approaching the problem too much from a classification point of view, but clustering is a rather different objective.

Last but not least, most clustering algorithm are based on some kind of aggregation. For example, k-means uses means. But of course these are not substantially affected by sampling. The mean of a (random, substantial) sample and the full data set should not systematically differ. So you may not learn much with this approach.