Model-based evaluation of clustering validation measures
Model-based evaluation of clustering validation measures
复制标题
DOI：
10.1016/j.patcog.2006.06.026
复制
发表时间：
2007-03-01
影响因子：
8
通讯作者：
Dougherty, Edward R.
中科院分区：
文献类型：
--
作者：
Brun, Marcel;Sima, Chao;Dougherty, Edward R.
聚类运算符获取一组数据点并将这些点划分为聚类（子集）。与任何科学模型一样，聚类算子的科学内容在于其预测结果的能力。这种能力是通过其相对于簇形成的错误率来衡量的。为了估计聚类算子的误差，生成点集样本，将算法应用于每个点集，并根据分布相对于已知分区评估聚类，然后在构成样本的点集上对误差进行平均。已经提出了许多有效性度量来评估基于随机点集过程的单一实现的聚类结果。在本文中，我们考虑了一些提出的有效性度量，并检查了它们与多种聚类算法和随机点集模型的错误率的相关性。有效性度量大致分为三类：内部验证基于计算结果集群的属性；相对验证基于相同算法生成的分区与不同参数或不同数据子集的比较；外部验证将聚类算法生成的分区与给定的数据分区进行比较。为了量化验证指标和聚类误差之间的相似程度，我们使用它们值之间的肯德尔等级相关性。我们的结果表明，总体而言，有效性指数的表现变化很大。对于复杂模型或当聚类算法产生复杂聚类时，内部索引和相对索引都无法预测算法的误差。一些外部指数似乎表现良好，而另一些则不然。我们得出的结论是，除非有证据（无论是在模型估计的足够数据还是先验模型知识方面）证明有效性度量与聚类算法的错误率密切相关，否则不应对有效性分数抱有太大信心。 (c) 2006 年模式识别协会。由爱思唯尔有限公司出版。保留所有权利。
A cluster operator takes a set of data points and partitions the points into clusters (subsets). As with any scientific model, the scientific content of a cluster operator lies in its ability to predict results. This ability is measured by its error rate relative to cluster formation. To estimate the error of a cluster operator, a sample of point sets is generated, the algorithm is applied to each point set and the clusters evaluated relative to the known partition according to the distributions, and then the errors are averaged over the point sets composing the sample. Many validity measures have been proposed for evaluating clustering results based on a single realization of the random-point-set process. In this paper we consider a number of proposed validity measures and we examine how well they correlate with error rates across a number of clustering algorithms and random-point-set models. Validity measures fall broadly into three classes: internal validation is based on calculating properties of the resulting clusters; relative validation is based on comparisons of partitions generated by the same algorithm with different parameters or different subsets of the data; and external validation compares the partition generated by the clustering algorithm and a given partition of the data. To quantify the degree of similarity between the validation indices and the clustering errors, we use Kendall's rank correlation between their values. Our results indicate that, overall, the performance of validity indices is highly variable. For complex models or when a clustering algorithm yields complex clusters, both the internal and relative indices fail to predict the error of the algorithm. Some external indices appear to perform well, whereas others do not. We conclude that one should not put much faith in a validity score unless there is evidence, either in terms of sufficient data for model estimation or prior model knowledge, that a validity measure is well-correlated to the error rate of the clustering algorithm. (c) 2006 Pattern Recognition Society. Published by Elsevier Ltd. All rights reserved.