聚类方法在数据挖掘和知识发现(DMKD)、数据库、机器学习、人工智能、模式识别等［9］领域是一个活跃的研究方向。在典型的聚类问题中,有以下三个最基本的问题:①对于特定的数据集,如何确定好的聚类方法;②在一个数据集中,如何确定聚类的数目;③如何评估聚类本身的性能［175］。本书重点研究的是第一个问题。对于聚类方法的评估,学者们已经提出了一些聚类度量准则。Yeung等［167］指出对于微阵列数据,Figure Of Merit(FOM)准则认为不同的簇代表了不同的生物群组,在相同簇中的个体则具有相似的向量模式。Roth等［176］提出了稳定性度量准则来评估聚类方法分区的有效性,并可以用来选择聚类的数目。Azuaje［177］定义Dunn＇s度量准则来衡量簇的紧密性和分离性。Chou等［164］提出一个CS准则,来衡量不同密度或不同大小的簇的相对性能。Zalik［178］基于紧凑性和重叠性,提出了一个CO度量准则来评估分区的质量。
反映和衡量聚类方法性能的指标一般被分成三种度量准则［155,165］,分别是外部度量准则、相对度量准则和内部度量准则。其中,外部度量准则往往选择已经有了类别标记的目标数据通过聚类来说明聚类方法的有效性［165－166］;相对度量准则是通过和其他簇类结构进行对比分析来评估簇类结构的好坏［167］;内部度量准则是基于数据本身属性来对评估聚类的好坏,如簇的紧凑度、分离度等,不需要考虑额外的数据信息［168］。Brun等［169］指出由于外部度量准则是选择已有类别标号的数据进行聚类,能够直观体现聚类质量的优劣,在验证聚类方法有效性的效果上比内部度量准则和相对度量准则都要好。因此,本书选取了9个常用的外部度量指标,分别是Purity［179］,Entropy［180］,FMeasure［181］,Rand Index［166］,Adjusted Rand Index［166］,Jaccard Coefficient［182］,Fowlkes and Mallows Index［183］,Micro－average precision［184］和Mirkin metric［185］。指标的详细内涵可以查看相关文献,这里简单介绍以下评估指标。
(1)纯净度(Purity):纯净度是度量聚类生成的簇中内部异质的样本数量。纯度越高,异质样本就越少,聚类效果也就越好。该指标越大越好。其计算公式为:
(2)信息熵(Entropy):信息熵来源于热力学的概念,是指聚类划分中簇类被正确表示的相对随机性概率。其计算公式为:
该指标越小越好,趋近于0说明簇的划分完全纯净。
(3)F－Measure值:F－Measure值最早用来评价信息检索的效果,度量的是分类器的查全率和查准率的调和平均数。对于类t和簇Ck的查准率(精确度)、查全率(召回率)以及相应的F－Measure分别是:
当b=1时,Prec(t,Ck)和Rec(t,Ck)的权重则是相等的,那么按下面的公式可计算整个划分的F值为:
其取值范围为［0,1］,该指标越大越好。
记C={C1,C2,…,Ck}是数据集X的一个聚类结构,并且G={G1,G2,…,GT}是数据集的一个定义类别划分。我们将使用以下形式来指代数据集中点对(xi,xj)的含义:
①a:两个点属于聚类结构C中同一簇类并且属于划分G中同一群体类别。
②b:两个点属于聚类结构C中同一簇类但属于划分G中不同群体类别。
③c:两个点属于聚类结构C中不同簇类并且属于划分G中不同群体类别。
④d:两个点属于聚类结构C中不同簇类但属于划分G中同一群体类别。
令M=a+b+c+d为数据集中所有点对的最大数目,其含义和计算公式是:M=N(N－1)/2,其中N是数据集中数据元组点的数目。现在我们能够定义以下指标来度量C和G之间的相似度了。
(4)Rand指标:Rand指标是一种基于统计的衡量两个聚类簇之间的相似性的评估指标。该指标越大越好。其计算公式为:
Rand指标的值为［0,1］,0代表两个数据簇间不存在任何匹配的点,1代表数据聚类簇精确相同。
(5)Jaccard Coefficient:Jaccard系数也被称为Jaccard相似性系数,可以衡量两个聚类簇之间的相似性和差异性。该指标越大越好。其计算公式为:
(6)Folkes and Mallows Index:是由Folkes和Mallows于1983年提出的,将聚类结果和数据内在结构进行对比而得出聚类的准确度。该指标越大越好。其计算公式为:
(7)Adjusted Rand Index:是度量聚类结果准确性的指标,其取值范围为［－1,1］,衡量簇之间的一致性水平。该指标越大越好。其计算公式为:
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
