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?
The only application of cross-validation to clustering I know of is this one:
Divide the sample into a 4 parts training set & 1 part testing set.
Apply your clustering method to the training set.
Apply it also to the test set.
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).
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.
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.
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:
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.
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?
There's a recent publication out on a bi-cross validation method for determining the number of clusters here.
and someone is trying to implement with sci-kit learn here.
Though their success is somewhat limited. As the publications indicates, this method doesn't work well when the clusters centers are highly correlated which can happen for large cluster sizes in low dimensional systems. (e.g. $7$ clusters in $2D$ doesn't work well.)