13
$\begingroup$

Currently, I am trying to analyze a text document dataset that has no ground truth. I was told that you can use k-fold cross validation to compare different clustering methods. However, the examples I have seen in the past uses a ground truth. Is there a way to use k-fold means on this dataset to verify my results?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
14
$\begingroup$

The only application of cross-validation to clustering I know of is this one:

  1. Divide the sample into a 4 parts training set & 1 part testing set.

  2. Apply your clustering method to the training set.

  3. Apply it also to the test set.

  4. Use the results from Step 2 to assign each observation in the testing set to a training set cluster (e.g. the nearest centroid for k-means).

  5. In the testing set, count for each cluster from Step 3 the number of pairs of observations in that cluster where each pair is also in the same cluster according to Step 4 (thus avoiding the cluster-identification problem pointed out by @cbeleites). Divide by the number of pairs in each cluster to give a proportion. The lowest proportion over all clusters is the measure of how good the method is at predicting cluster membership for new samples.

  6. Repeat from Step 1 with different parts in training & testing sets to make it 5-fold.

Tibshirani & Walther (2005), "Cluster Validation by Prediction Strength", Journal of Computational and Graphical Statistics, 14, 3.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ can you further explain what a pair of observation is (and why are we using pair of observations in the first place) ? Furthermore, how can we define what is a "same cluster" in the training set compared to the test set? I had a look to the article, but did not get the idea. $\endgroup$
    – Tanguy
    Commented Mar 21, 2018 at 14:45
  • 1
    $\begingroup$ @Tanguy: You consider all pairs - if the observations are A, B, & C the pairs are {A,B}, {A,C}, & {B,C} - , & you don't try to define "the same cluster" across train & test sets, which contain different observations. Rather you compare the two clustering solutions applied to the test set (one generated from the training set & one from the test set itself) by looking how often they agree in uniting or separating members of each pair. $\endgroup$
    – Scortchi - Reinstate Monica ♦
    Commented Mar 21, 2018 at 16:40
  • $\begingroup$ ok, then the two matrices of pair of observations, one on the train set, one on the test set, are compared with a similarity measure? $\endgroup$
    – Tanguy
    Commented Mar 22, 2018 at 21:54
  • $\begingroup$ @Tanguy: No, you only consider pairs of observations in the test set. $\endgroup$
    – Scortchi - Reinstate Monica ♦
    Commented Mar 24, 2018 at 11:27
  • $\begingroup$ sorry I was not clear enough. One should take all pair of observations of the test set, from which a matrix filled with 0 and 1 can be built (0 if pair of observation do not lie in the same cluster, 1 if they do). Two matrices are calculated since we look at pair of observations for the clusters obtained from the training set and from the test set. The similarity of those two matrices is then measured with some metric. Am I correct? $\endgroup$
    – Tanguy
    Commented Mar 24, 2018 at 15:11
7
$\begingroup$

I'm trying to understand how would you apply cross validation to clustering method such as the k-means since the new coming data will change the centroid and even the clustering distributions on your existing one.

Regarding the unsupervised validation on clustering, you may need to quantify the stability of your algorithms with different cluster number on the re-sampled data.

The basic idea of clustering stability can be shown in the figure below:

enter image description here

You can observe that with the clustering number of 2 or 5, there are at least two different clustering results (see the splitting dash lines in the figures), yet with the clustering number of 4, the result is relatively stable.

Clustering stability: an overview by Ulrike von Luxburg might be helpful.

Improve this answer
$\endgroup$
7
$\begingroup$

Resampling such as done during (iterated) $k$-fold cross validation generates "new" data sets that vary from the original data set by removing a few cases.

For ease of explanation and clarity I'd bootstrap the clustering.

In general, you can use such resampled clusterings to measure the stability of your solution: does it hardly change at all or does it completely change?

Even though you have no ground truth, you can of course compare the clustering that results from different runs of the same method (resampling) or the results of different clustering algorithms e.g. by tabulating:

km1 <- kmeans (iris [, 1:4], 3)
km2 <- kmeans (iris [, 1:4], 3)
table (km1$cluster, km2$cluster)

#      1  2  3
#   1 96  0  0
#   2  0  0 33
#   3  0 21  0

as the clusters are nominal, their order can change arbitrarily. But that means that you are allowed to change the order so that the clusters correspond. Then the diagonal* elements count cases that are assigned to the same cluster and off-diagonal elements show in what way assignments changed:

table (km1$cluster, km2$cluster)[c (1, 3, 2), ]

#      1  2  3
#   1 96  0  0
#   3  0 21  0
#   2  0  0 33

I'd say the resampling is good in order to establish how stable your clustering is within each method. Without that it doesn't make too much sense to compare the results to other methods.

* works also with non-square matrices if different numbers of clusters result. I'd then align so that elements $i,i$ have the meaning of the former diagonal. The extra rows/columns then show from which clusters the new cluster got its cases.

You're not mixing k-fold cross validation and k-means clustering, are you?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.