聚类分析模型算法研究及其有效性评价

李德新

摘要：该文分析了聚类分析算法的基本思想、原理、数学模型及实现过程，详细地分析了几种经典的聚类分析算法的优缺点，最后介绍了常用的聚类分析算法的有效性分析方法。

关键词：聚类分析算法;模型;有效性;评价

中图分类号：TP391        文献标识码：A

文章编号：1009-3044（2021）30-0026-02

開放科学（资源服务）标识码（OSID）：

1聚类分析的概念

在数据挖掘领域中，常常会遇到这样的一些的问题，从未加工的数据里面对有用的信息进行转换。转换过程中可以利用的技术有很多，而其中的分类是最为常用的一种转换技术。分类问题需要一个参考问题的样本数据，并且这些样本数据的属性值都是已知的。分类得到的一个非常有价值的分类规则，并可以利用这些规则进行未知类别的对象进行分类，是先验学习的经典案例。与分类相似的聚类[1]是将一个大数据集划分为许多子集的过程。在这个问题中，与分类所遇到的已知信息相比要少得多。在聚类过程中，待聚类的数据有关信息是不知道的，只能利用某种标准将数据进行划分到各个簇中。由此看来，聚类是一种发现数据对象内在联系的无监督的学习算法，它主要是建立在集合知识之上的一种方法。聚类分析[2]是知识发现和数据挖掘的重要方法之一。聚类的过程是对知识的发现的过程，因此由聚类得出的结果可以反映数据分布的本质特征。

2数据对象的相似性测量工具

聚类，顾名思义就是要将待处理的数据对象进行划分成类。聚类质量的标准取决于相同类中的数据对象的相似性或者不相同类的数据对象的相异性。由此可见，对两个数据对象之间的相似性度量对聚类具有重要意义。目前常用的相似性度量工具有距离和相似性系数两种。

2.1距离

用于聚类分析相似性测量的最常用的方法是距离。通常我们自然会想到用点与点之间的距离来测量数据对象的相似程度。因为距离具有一些众所周知的性质，假设用[d（x，y）]来表示两个点x、y之间的距离，则它具有如下性质成立：

（1）非负性。对于所有的x和y，[d（x，y）]≥0，仅当x = y时，[d（x，y）]=0.

（2）对称性。对于所有的x和y，[d（x，y）]=[d（y，x）].

（3）三角不等式。对于所有的x，y和z，[d（x，z）]≤[d（x，y）]+[d（y，z）]。

数据对象之间的相似性通常可用欧几里得距离及其变种来进行测量，对于两个数据对象x和y的距离的计算可采用以下3种常用的方法。

（1）欧几里得距离（Euclidean distance）

[d（x，y）]=[k=1n（xk-yk）2]

在上式中，n表示数据对象的维数，其中的xk和yk分别用来表示x、y的第k个属性值。

（2）闵可夫斯基距离（Minkowski distance）

[d（x，y）]=[k=1nxk-ykr1r]

这是最广泛的闵可夫斯基的距离形式。其中，r是参数。

（3）Mahalanobis距离

Mahalanobis距离也是用得比较多的一种用于测量两个数据对象之间的相似性的距离。通常可以用下面的公式计算：

[mahalanobis（x，y）=（x-y）T-1（x-y）]

其中[Σ]为样本协方差阵。该距离是为了克服其他两种距离定义容易受到量纲和多重相关性的影响的缺点而提出来的一种新颖的距离测量方法。该距离的不足之处在于计算量大，对大规模的数据量性能较差。

2.2相似性系数度量方法

相似性系数可定义为两个二元属性数据对象的相似性程度，它的值可以在[0，1]之间取值，当值为0时，表明两个数据对象不相似，当值为1时，可以得出两个数据对象非常相似的结论。有大量的理由可以表明在特定情形下，一种系数为何要比另一种好。

假设存在两个含有n个二元属性数据对象x，y。那么通常对数据对象x和y进行的比较就有如下四种情况：

（1）f00表示为当x取0、y取0时的属性数目;

（2）f01表示为x当取0、y取1时的属性数目;

（3）f10表示为x当取1、y取0时的属性数目;

（4）f11表示为x当取1、y取1时的属性数目。

SMC系数（Simple Matching Coefficient）SMC系数是目前应用得最为广泛的相似性系数之一。用SMC来表示，那么SMC就可以利用下面的计算公式来计算。

SMC = [值匹配的属性个数属性个数] =[][f11+f00f01+f10+f11+f00]

该系数对存在和不存在进行同等计数。

Jaccard系数（Jaccard Coefficient）

当数据对象包含非对称的二元属性时，利用SMC来进行判定时会出现无法区分的现象，为了克服SMC的缺点提出了Jaccard 系数，该系数可用符号J表示，计算公式为：

J = [匹配的个数不涉及0-0匹配的属性个数] =[][f11f01+f10+f11]

Tanimoto系数

用于对文档数据的相似性度量的Tanimoto系数可用EJ表示，计算公式如下：

EJ（x，y） = [x?yx2+y2-x?y]

皮尔森相关（Pearsons correlation）系数

皮尔森相关系数是对两个具有二元变量或连接变量的数据相关性进行测定的系数，可以用如下公式进行计算：

corr（x，y） =[covariance（x，y）standard_deviation（x）×standard_deviation（y）]=[sxysxsy]

3典型的聚类算法的有效性分析准则

为了验证算法的有效性，经常采用对聚类分析算法有效性评价方法有外部准则、内部准则以及相对准则，而这些评价准则都是依靠统计假设检验来实现的。

外部准则的精髓在于把聚类分析所得到的聚类结果和事先定义好的数据集的分类结构进行对比研究，并最终得出算法有效性的评价方法。外部准则方法可以采纳的统计标准包括Jaccard系数、Rand统计、Mallows指数、Fowlkes和Hubert的[Γ]统计和F- measure等。

外部准则在使用的时候，通常必须让它满足两个重要的条件：（1）聚类算法得到的结果C与预先已知的X划分的结果可以进行比较;（2）要能够对事先已经定义的划分结果X与它的近邻矩阵之间的相似程度进行测定。

在上述外部准则中所列举的方法中，使用的最广泛、优势最明显的方法是F-measure，该方法的优势主要来源于对信息检索领域中的查准率（precision）及查全率（recall）的结合[2]，在对分类i的F-measure进行计算时可用公式进行计算：

F（i） = 2PR/（P+R）

通过计算就能够得出各个聚类的F-measure值，按值的大小进行排序，就能够得出聚类质量的高低。而公式中的P和R分别表示的是查准率和查全率，可用下面的公式计算得出。

P = precision（i，j） = [Nij]/[Ni];

R = recall（i，j） = [Nij]/[Nj]，

在上面的两个公式中，[Nij]表示聚类j中分类数i的多少;而[Nj]表示的是聚类j中所有数据对象的数量;[Ni]是分类i中所有对象的个数。于是与聚类结果[λ]相对应的F-measure值可用下面的公式进行计算：

[Fλ=ii×F（i）ii]

在式中，[i]的取值为分类i数据对象的总个数。

内部准则是将聚类结果简单的与数据集合本身所具有的一些特征进行比较的评价方法。内部准则的方法也是对聚类算法评价的有效方法，较为常用的方法有统计指标有[Γ]统计、同现相关系数（CPCC）等[3]。

（1）不受簇的形状的限制

现实中的数据对象形成的簇，其形状可以是任意形状的。因此，一个好的聚类算法，应该能够发现任意形状的簇。

（2）可伸缩性

在实际的数据处理时，面临的数据对象的规模有大有小，可伸缩性指的是聚类算法既要具有处理大规模海量数据的能力又要能处理小规模数据的性能。因此，一个聚类算法需要具备良好的可伸缩性。

（3）同一时刻能够处理不同类型属性的能力

聚类算法需要具有处理不同类型的属性的能力，例如数值属性、组合类型属性或类属性。

参考文献：

[1] 范明，孟小峰，译.数据挖掘概念与技术[M].北京：机械工业出版社，2005.

[2] 胡建军，唐常杰，李川，等.基于最近邻优先的高效聚类算法[J].四川大学学报（工程科学版），2004，36（6）：93-99.

[3] Han Jiawei， Kamber Micheline. Data Ming Concepts and Techniques[M].2nd edition.San Francisco，USA：Morgan Kaufmann Publisher，2020.

【通聯编辑：代影】