于 晓， 李 晨， 王亚茹

(天津大学 电气与自动化工程学院，天津 300072)

基于数据约减的聚类有效性分析*

于 晓， 李 晨， 王亚茹

(天津大学 电气与自动化工程学院，天津 300072)

聚类分析中利用有效性指标判断数据集的正确类数极易受到噪声数据、类之间分离性以及聚类算法的影响，所确定类数的正确性难以得到保证。为克服这个问题，以文献[1]中的数据约减方法为基础，对原数据集和约减后的数据集利用有效性指标进行正确类数判别。实验表明：该方法能增大类之间的分离性，有效判断数据集的最优类数。

数据约减； 方向角； 聚类分析； 最优类数

0 引 言

目前随着数据挖掘和人工智能技术的不断进步，各行的数据量不断涌现，如文本数据、基因数据、图像数据等，由于聚类方法的无监督性，使得聚类分析在处理海量信息中得到了广泛的应用[1]。近年来，随着聚类理论的不断发展，聚类分析在众多领域也获得了令人满意的效果。但是，作为数据挖掘的重要工具，聚类在发展中还存在许多问题，如聚类中相似性的度量、数据的预处理、聚类有效性等[2]。其中，聚类有效性问题中如何确定数据集的最佳类数一直以来都是聚类分析问题中的一大难题，也是众多学者研究的热点问题。因为现有的聚类算法绝大多数都要预先给出数据集的类数，才能对数据集进行有效的聚类分析。为此，众多聚类有效性指标被提出，以此确定数据集的最佳类数。但是由于数据结构的多样性和复杂性，研究表明[3]，没有哪一种聚类有效性指标可以在任何的情况下对任何的数据集都能取得良好的效果。

本文将基于张开角测度的数据约减方法应用于聚类分析中最佳类数的判别问题。通过优化原有的约简方法，对数据集进行数据约减，去掉数据集中的噪声数据，然后对约减前后的数据应用聚类方法和有效性指标进行最佳类数判别。实验证明，与原数据集相比，约减后的数据集能够得到较好的最优类数。

1 相关的工作

本节介绍了一个基于张开角的数据约简方法以及两个常用的聚类有效性指标，DBI指标[4]和Gap统计指标[5]，具体说明如下。

1.1 张开角测度的数据约减方法

设X={x1,x2,...,xi}是d维空间中包含n个数据向量的集合,xi={xi1,xi2,…,xid}是数据集中任意的第i个数据向量，设顺时针排列的距离xi最近的2d个数据向量为xi={xi1,xi2,…,xid}，则从xi出发与这些向量相连构成的(2d-1)个向量的张开角依次表示为(xi,xi1),(xi1,xi2),…,(xi(2d-1),xi2d)，则xi的平均张开角定义为

(1)

式中 Angle()为一对从xi出发的一对连接向量之间的夹角;|xsxi|为向量xs与xi之间的连接线的距离。

该方法根据数据集分布的一般特征，能够区分数据集中核心对象和边界对象分布的本质区别，实现以核心目标为中心的数据约减。然而，该方法中计算方向角的向量数为2d是经验确定的，并没有经过优化。本文将对此进行优化设计。

1.2 聚类有效性指标

作为数据挖掘领域的重要分支，聚类是一个无监督的学习过程，然而如何确定最佳类数一直以来都是一项困难的工作[6,7]。解决这类问题的一个有效方法就是构造聚类有效性指标，目前研究者已经提出了许多聚类有效性指标，如DBI指标、Gap指标、PC方法等[8]。目前在工程中广泛认可并最为常用的为DBI指标和Gap指标。

1)Davies-Bouldin指标

Davies-Bouldinindex(DBI)首先计算类内距离Si为

(2)

式中 xj为第i类中第j个数据点；Ai为第i类的类中心；Ni为第i类中的数据点总数；一般取q=2; 类间距离Mij定义为

(3)

式中 aik为第i类中心点的第k个属性值，Mij为第i类与第j类中心的距离，一般情况,取p=2;DBI指标定义为

(4)

从Rij中选出最大值Ri=max(Rij)，即第i类与其他类的相似度中最大的相似度的值，取平均得到

(5)

DBI指数越小，表明其对应的聚类效果则越好。在过去的20年中，DBI指标已经在工程中有记录的应用次数超过2 000次。

2)Gap统计指标

设xi表示数据集中的数据点，i=1,2,…,n,则xi可以表示为xi={xi1,xi2,…,xid}，d为数据集的维数，令dii＇表示数据点i与i＇之间的距离。

设C1，C2，…,Ck表示数据集被分成K个类，Cr表示数据点属于第r类，Nr=|Cr|为第r类中数据点的总数。第r类中任意两点之间的距离之和定义为

(6)

总的类内距离用符号Wk表示，Wk的计算表达式子为

(7)

则Gapn(k)指标定义为

(8)

2 本文提出的方法

使用聚类有效性指标确定类数的正确性严重受到以下因素影响：数据集中存在的大量噪声数据、类与类之间的不可分性以及聚类算法的不稳定性等等[9]，本文的研究表明,通过数据约简能够有效地降低上述因素的影响。

2.1 基本动机

图1显示了人工数据集Set1和Set2在二维坐标下的分布情况。通过基于张开角的数据约简方法进行约简。 图2、图3分别显示了约减30 %和90 %数据点后的结果，其中星号为保留下来的数据点，黑点的为约减掉的数据点。从约减结果可以看出，约减后的数据点逐渐趋向中心，数据集中类别分离性更加明显。

图1 原数据集Set1和Set2

图2 30 %的数据点约简

图3 90 %的数据点约简

因此，将数据集中非关键的数据去除，使数据集中类别的分离性更加明显，容易得到更加准确的类数判断[10]。

2.2 确定计算方向角的最优方式

上述基于张开角测度的数据约减方法根据数据集中各个数据点张开角的不同对数据集进行约减。为了得到最优的约减效果，确定以下优化目标：使数据集中所有点计算出的测度最大化。该优化目标基于两点：首先，数据点之间的测度值差别越大，约简结果越稳定[11]；其次，方向角测度较大的点对应各个类的核心点而较小的点对应边界点；因此，数据点之间测度值差别的最大化将增大这两类点之间的差别，从而随着约简过程的进行，边界点以及噪声点逐渐被去除，类之间的可分性越来越强。据此定义以下目标函数

(9)

3 实 验

实验中,使用UCI中具有不同结构和特征的15个数据集,这些数据集的特征说明如表1所示，且这些数据集的正确类数是已知的。

表1 15个UCI中真实数据集

实验中,首先使用张开角的数据约减方法对数据集进行不同比例的约减，对约减前后的数据集运用k-means进行聚类，然后对聚类结果分别应用DBI、Gap两个指标进行最优类数的判别，实验结果如表2、表3以及图4、图5所示。从实验结果中可以得出以下结论：

1)从表2、表3可得，与约减前的最优类数相比较，约减后的最优类数更加准确或更加接近数据集的真实类数，说明约减后数据集中类别之间的分离性更加凸显，因此，该方法对于聚类中最佳类数的判别具有一定的有效性。然而对类数未能正确判断的数据集，实际上，数据集中类的形状是任意的，无法用k-means聚类，因而无法得到正确的类数判别。

表2 DBI指标聚类数

表3 Gap指标聚类数

图4 Glass数据集约减前后DBI指标

图5 Iris数据集约减前后Gap指标

2)利用有效性指标得到的结果并非与真实类数完全一致，从结果可以看出，DBI指标类数判别的准确性要高于Gap指标的准确性。 因为不同的指标适用的条件不同，聚类有效性评价一直是聚类分析中一个重要的研究方向，目前还没有一种有效性指标可以完全适用于所有聚类算法。

3)如图4、图5中Glass，Iris数据集指标曲线图所示，约减后数据集的指标曲线图中最优点位置更加突出，其他数据集与之类似。

4 结 论

通过对数据结构的分析，文中将基于张开角测度的数据约减方法优化后针对一般数据集能够进行有效约减，并将该方法应用于聚类分析中最佳类数的判别问题。通过对具有不同数据结构和密度的数据集进行测试，可以发现约减后得到的最优类数与数据集的真实类数更加接近，这表明约减后数据集中类别的分离性更加明显，因此，该方法对聚类分析中最佳类数的判别具有一定的有效性和有用性。

该方法还有一定的不足之处，因为得到比较好的最优类数是以时间为代价的，约减的过程是一个逐层循环的过程，每次循环都要计算每个点周围的邻域点，因此，进一步提高该算法的效率有待进一步研究。

[1] 李 晨,王亚茹,岳士弘.基于张开角测度的数据约简[J].传感器与微系统,2016,35(4):25-28.

[2] 周世兵.聚类分析中的最佳聚类确定方法研究及应用[D].无锡：江南大学,2011.

[3] Sergios T,Konstantinos K.模式识别[M].4版.北京:电子工业出版社,2010.

[4] Arbelaitz O,Gurrutxaga I,Muguerza J,et al.An extensive comparative study of cluster validity indices[J].Pattern Recognition,2013,46(1):243-256.

[5] Guerra L,Bobles V,Bielza C,et al.A comparison of clustering quality indices using outliers and noise[J].Intelligent Data Analysis,2012,16(4):703-715.

[6] 白素琴,吴小俊.基于模糊聚类算法的有效性指标[J].江南大学学报,2007,6(6):878-882.

[7] 杨 燕,靳 蕃,KAME Lmohamed.聚类有效性评价综述[J].计算机应用研究,2008,25(6):1630-1632.

[8] 孙吉贵,刘 杰,赵连宇.聚类算法研究[J].软件学报,2008,19(1):48-61.

[9] 周开乐,杨善林,丁 帅,等.聚类有效性研究综述[J].系统工程理论与实践,2014,34(9):2417-2431.

[10] Jain A K.Data clustering:50 years beyond K-means[J].Pattern Recognition Letters,2010,31(8):651-666.

[11] 曹付元,武鹏鹏.一种基于稀疏度和距离的初始类中心选择算法[J].山西大学学报:自然科学版,2015,38(1):73-78．

Cluster validity analysis based on data reduction*

YU Xiao， LI Chen， WANG Ya-ru

(School of Electrical Engineering and Automation,Tianjin University,Tianjin 300072,China)

Estimating the correct number of clusters by cluster validity index in cluster analysis is highly susceptible to noise data,separation among clusters and clustering algorithm,so the correctness of the estimated number of clusters is difficult to be guaranteed.In order to overcome this problem,validity index is used to estimated number of clusters in original dataset and reduced dataset based on the data reducing method proposed in reference[1],the result demonstrate the method can enhance separation among clusters and effectively determine the optimal number of clusters.

data reduction; direction angle; cluster analysis; the optimal number of clusters

10.13873/J.1000—9787(2017)03—0055—03

2016—04—26

国家自然科学基金资助项目(61573251)

TP 391.4

A

1000—9787(2017)03—0055—03

于 晓(1991-)，女，硕士研究生，主要研究方向为模式识别。