<p>There is another way to <strong>evaluate the clustering quality by computing a stability metric</strong> on subfolds, a bit like cross validation for supervised models:</p>

<ul>
<li><p>Split the dataset in 3 folds A, B and C. Compute two clustering with you algorithm on A+B and A+C. Compute the Adjusted Rand Index or Adjusted Mutual Information of the 2 labelings on their intersection A and consider this value as an estimate of the stability score of the algorithm.</p></li>
<li><p>Rinse-repeat by shuffling the data and splitting it into 3 other folds A', B' and C' and recompute a stability score.</p></li>
<li><p>Average the stability scores over 5 or 10 runs to have a rough estimate of the standard error of the stability score.</p></li>
</ul>

<p>As you can guess this is very computer intensive evaluation method.</p>

<p>It is still an open research area to know whether or not this Stability-based evaluation of clustering algorithms is really useful in practice and to identify when it can fail to produce a valid criterion for model selection. Please refer to <a href="http://arxiv.org/abs/1007.1075" rel="nofollow">Clustering Stability: An Overview</a> by Ulrike von Luxburg and references therein for an overview of the state of the art on those matters.</p>

<p>Note: it is important to use Adjusted for Chance metrics such as ARI or AMI if you want to use this strategy to select the best value of k in k-means for instance. Non adjusted metrics such as NMI and V-measure will tend to favor models with higher k arbitrarily.</p>
Validating Output From a Clustering Algorithm
<p><strong>Is there an objective way to validate the output of a clustering algorithm?</strong></p>

<p>I'm using scikit-learn's affinity propagation clustering against a dataset composed of objects with many attributes. The difference matrix supplied to the clustering algorithm is composed of the weighted difference of these attributes. I'm looking for a way to objectively validate tweaks in the distance weightings as reflected in the resulting clusters. The dataset is large and has enough attributes that manual examination of small examples is not a reasonable way to verify the produced clusters.</p>