I'm doing shopping cart analyses my dataset is set of transaction vectors, with the items the products being bought.
When applying k-means on the transactions, I will always get some result. A random matrix would probably also show some clusters.
Is there a way to test whether the clustering I find is a significant one, or that is can be very well be a coincidence? If yes, how can I do it?
Regarding shopping cart analysis, I think that the main objective is to individuate the most frequent combinations of products bought by the customers. The association rules represent the most natural methodology here (indeed they were actually developed for this purpose). Analysing the combinations of products bought by the customers, and the number of times these combinations are repeated, leads to a rule of the type ‘if condition, then result’ with a corresponding interestingness measurement. You may also consider Log-linear models in order to investigate the associations between the considered variables.
Now as for clustering, here are some information that may come in handy:
At first consider Variable clustering. Variable clustering is used for assessing collinearity, redundancy, and for separating variables into clusters that can be scored as a single variable, thus resulting in data reduction. Look for the varclus function (package Hmisc in R).
Assessment of the clusterwise stability: function clusterboot {R package fpc}
Distance based statistics for cluster validation: function cluster.stats {R package fpc}
As mbq have mentioned, use the silhouette widths for assessing the best number of clusters. Watch this$^\dagger$. Regarding silhouette widths, see also the optsil function.
Estimate the number of clusters in a data set via the gap statistic.
For calculating Dissimilarity Indices and Distance Measures see dsvdis and vegdist.
EM clustering algorithm can decide how many clusters to create by cross validation, (if you can't specify a priori how many clusters to generate). Although the EM algorithm is guaranteed to converge to a maximum, this is a local maximum and may not necessarily be the same as the global maximum. For a better chance of obtaining the global maximum, the whole procedure should be repeated several times, with different initial guesses for the parameter values. The overall log-likelihood figure can be used to compare the different final configurations obtained: just choose the largest of the local maxima. You can find an implementation of the EM clusterer in the open-source project WEKA.
This is also an interesting link.
Also search here for Finding the Right Number of Clusters in k-Means and EM Clustering: v-Fold Cross-Validation
Finally, you may explore clustering results using clusterfly.
$^\dagger$ Not working.
This is a method using Monte Carlo to show whether a result is correct.
Our Null Hypothesis H_0 is that our dataset does not have an interesting clustering. Our alternative hypothesis H_1 is that our dataset contains an interesting clustering.
Hereby we think of interesting as, more interesting than the clustering structure of a random dataset with the same row and column margins. Of course other constraints could be chosen, but to loose constraints will make our result too general, and to narrow constraints will fix the clustering to much, therefore making our result insignificant automatically. The margins, as we will see, are a good choice because of the methods existing for randomizing with it.
Let's define as our test statistic the clustering error (squared in-cluster distance), T from Π_0. The value for our original dataset is t.
We don't know anything about this distribution, except that we can draw samples from it. Which makes it a good candidate for Monte Carlo.
Now we draw n (i.i.d) random samples from Π_0 and calculate the empirical p-value with the formula p_emp = 1 / (n+1) * (Σ_i=1-n I(t_i >= t) + 1)
The random sampling can be done by swap randomization. In simple words, a square is searched with on two opposite corners an 1 and on the other two corners a 0. Then the corners are flipped. This is keeping the column and row margins. The procedure is repeated enough times until the dataset is randomized enough (this will take some experiments). More info about this can be found in Assessing Data Mining Results via Swap Randomization by Gionis et. al.
One method to do this is defining the distribution of your data and taking the clustering error as test-statistic t.
For example, if we consider all data sets with the same row and column margins as being our data distribution, than we can take n random matrices Xi from this distribution and calculate the clustering error for them. Then we can calculate the emperical p-value by the formula
There is something like silhouette, which to some extent defines statistic that determines the cluster quality (for instance it is used in optimizing k). Now a possible Monte Carlo would go as follows: you generate a lot of random dataset similar to your original (for instance by shuffling values between rows in each column), cluster and obtain a distribution of mean silhouette that then may be used to test significance of silhouette in real data. Still I admin that I have never tried this idea.
The average silhouette index is not enough for validating our clustering. A clustering with less average silhouette index may have better quality then a greater one; imaging a case which all member of first cluster have high SIL index but the other clusters have negative SIL value and the average SIL index is still positive and high. So what is the benefit of having a high and rare SIL index in clustering? What is the benefit of having high p-value?
