光俊叶，刘明霞,2，张道强+

1.南京航空航天大学 计算机科学与技术学院，南京 211106

2.泰山学院 信息科学技术学院，山东 泰安 271021

有效距离在聚类算法中的应用*

光俊叶1，刘明霞1,2，张道强1+

1.南京航空航天大学 计算机科学与技术学院，南京 211106

2.泰山学院 信息科学技术学院，山东 泰安 271021

聚类；距离度量；度量学习；有效距离

1 引言

在如今的大数据时代，人们需要利用成熟的数据挖掘技术处理海量的数据，希望从中找到有价值的信息或模型[1]。聚类分析是数据挖掘中不可或缺的常用技术[2]，在许多领域（例如，医学方面的疾病诊断[3-4]和电力系统方面的安全保障[5]等）有非常重要的利用价值。

聚类分析的研究历史比较长远，存在很多种类型的聚类算法。其中，K-means是经典的基于划分的聚类算法，但是该算法对初始聚类中心的选择非常敏感，易收敛到局部最优解，而且聚类簇K的数目还难以确定，不合适的K值往往会得到比较差的聚类结果[6]。于是研究人员不断提出改进算法，希望可以弥补算法存在的不足。例如，Huang提出了K-modes-Huang算法，将传统K-means拓展到可以处理包含多种不同数据类型的大数据集的方法[7]。Gupta等人提出的基于文档的K-means算法可以自动进行K选择以及聚类簇的细化[8]。考虑到K-means算法利用均值计算中心点时噪声点造成的不利影响，K-medoids算法选择有代表性的真实存在的样本点作为聚类簇的中心。K-means和K-medoids算法都要求一个样本属于且只属于一个聚类簇。1969年，Ruspini提出了FCM（fuzzy C-means）聚类算法，指出一个样本也可能属于多个聚类簇，只是隶属度不同而已[9]。2002年，Zhang等人引入核方法，不仅将FCM的适用范围从球形分布拓展到包括非球形的任意分布，而且可以自动评估聚类簇的数目[10]。2006年，李洁等人提出基于特征加权的模糊聚类算法（new feature weighted fuzzy clustering algorithm，NFWFCA），可以有选择性地区别对待不同的特征，更加有利于聚类[11]。2007年，Cai等人提出了FGFCM（fast generalized fuzzy C-means）算法，该方法融合了局部空间信息和灰度信息，可以更快更好地进行图像分割[12]。聚类算法在不断地更新改进，虽然在这些算法中距离度量方法都大同小异，但它确实是至关重要的一个步骤。

距离度量可以计算样本之间的距离或者相似性，它的优劣性在很大程度上影响甚至决定着聚类效果。常用的度量方法是欧氏距离。虽然欧氏距离是简单并且方便计算的，但是只考虑了数据之间的直接地理距离，忽略了其余有价值的信息（如拓扑几何关系等）。很多学者尝试用其他距离进行聚类分析。例如，Groenen等人提出的模糊聚类模型中使用明氏距离代替欧氏距离[13]。Xiang等人提出在已知must-link和cannot-link等约束信息的情况下学习样本之间的马氏距离然后进行聚类分析，这种度量方法在图形分割和脸部识别等应用中都取得了比较好的实验结果[14]。Rammal等人对红外线光谱聚类进行了研究，通过实验验证了使用L1或曼哈顿距离的实验结果优于欧氏距离以及切氏距离[15]。新型度量方法的提出可以说是层出不穷。Brockmann等人在探讨影响传染病传播情况的因素时，提出了一种不是传统意义上距离的有效距离度量方法。该距离基于两地之间由于航空运输导致的人口流动比率，发现各地与病菌发源地之间的有效距离与病菌到达相应地点的时间成固定比例，并且利用该有效距离度量方法模拟H1N1和SARS病毒传播情况与真实情况十分吻合[16]。综上所述，不同的距离度量方法有不同的优势，可以从不同的角度描述样本之间的距离，可能得到不同的聚类结果。

本文提出了一种充分考虑样本全局性结构信息的距离度量方法——有效距离度量（effective distance metric），其基本思想是首先通过稀疏重构的方法构造样本之间的连接网络，然后借鉴Dirk等人提出的基于比率的距离度量方法计算样本之间的有效距离。进一步地，本文将有效距离应用到K-means、K-medoids和FCM经典聚类算法中，并且在UCI标准数据集上进行实验。实验结果表明，基于有效距离度量的聚类方法有更高的聚类精确度，能够得到比传统聚类算法更好的聚类结果。

本文内容安排如下：第2章简单介绍了与本文相关的工作；第3章详细讨论了本文提出的新的基于有效距离的聚类方法；第4章通过多个实验验证了本文算法的性能；最后对本文的工作进行总结和展望。

2 相关工作

2.1 聚类分析算法

已有的研究中，按照各类标准人们提出了多种聚类算法[6]。其中，K-means、K-medoids、FCM是3种常用的聚类算法。

2.1.1 K-means算法

目前，K-means聚类算法在很多领域中已经成为进行数据分析的主要工具[1]。该聚类算法以对数据集进行硬划分使得聚类的类内误差平方和最小为基本依据。给定数据样本X=[x1,x2,…,xn]T∈Rn×d,需要聚成c个簇，用vk(k=1,2,…,c)表示每个聚类簇的聚类中心，uki=uXk(xi)表示第i个样本xi对第K个子集XK的隶属程度，且uki∈{0,1}。设划分矩阵U是一个c×n的矩阵，可以用U=[uki]c×n表示。定义K-means聚类算法的目标函数为：

该算法的目标是寻找最优对(U,V)，使得目标函数J1(U,V)取得最小值。

2.1.2 K-medoids算法

K-medoids聚类算法是在K-means聚类算法的基础上改进的。K-means算法利用均值计算中心点时容易受到噪声点或者离群点的影响，K-medoids算法具有较强的鲁棒性，它选择有代表性的真实存在的样本点，也就是到当前聚类簇中所有其他数据样本的距离之和最小的样本点，作为聚类簇的中心。

2.1.3 FCM算法

K-means和K-medoids两种聚类算法是基于“非此即彼”的思想，属于硬划分的方法。但是实际应用中，许多问题本身具有一定的模糊不可分性，使用模糊聚类方法处理更加合理。FCM是基于K-means推广形式的具有代表性的一种模糊聚类算法[17]。1974年，Dunn首次提出了利用模糊C进行划分，引入聚类分析的模糊化情形[18]，其提出的算法的核心思想是根据模糊划分求得划分矩阵U，并用隶属度的平方值对每个数据样本与每个聚类中心点之间的距离进行加权，从而得到一个新的目标函数：

1981年，Bezdek对此方法进行了完善，并将其推广到更为普遍的表示形式[19]，即将式（2）中的目标函数J2进行进一步的推广，定义了模糊C-均值聚类算法的目标函数为：

其中，m∈[1,∞)称作模糊加权指数（或平滑参数），数据样本的隶属度取值为[0,1]区间内的任何一个实数。FCM聚类算法的基本依据是“类内加权误差平方和最小化”准则。

2.2 距离度量

2.2.1 传统的距离度量方法

常用的距离度量有欧氏距离、绝对值距离、切氏距离、明氏距离、马氏距离和归一化距离等。这里简单介绍欧氏距离的具体度量方法。

设a=(a1,a2,…,ad)，b=(b1,b2,…,bd)为两个样本，则它们之间的欧氏距离定义为：

欧氏距离是使用最为广泛、最简单的距离度量，而且欧氏距离具有平移和旋转不变性。

2.2.2 有效距离

近几年，全球气候的反常变化导致了很多传染性病毒的肆意传播，比如2003年的SARS病毒和2009年的H1N1病毒。2013年，Brockmann等人在探讨影响传染病传播情况的因素时，提出了一种不是传统意义上距离的有效距离度量方法。该距离基于两地之间由于航空运输导致的人口流动比率，发现各地与病菌发源地之间的有效距离与病菌到达相应地点的时间成固定比例。而且利用该有效距离度量方法模拟H1N1和SARS病毒传播情况与真实情况十分吻合[16]。以真实病菌传播情况为例，该有效距离度量方法还可以成功地挖掘出传染病菌的传播源，并且预测传染病菌未来的传播状态。而简单的欧氏距离度量在这些案例中没有办法达到满意的效果。这些事实说明，现实世界中两个事物之间的距离实际上不仅仅取决于几何坐标中的欧氏距离或者地理距离。度量两个事物之间的距离时，除了考虑这两个事物之间的关系之外，还要考虑与这两个事物相关的其余事物对它们的影响，也就是要考虑数据的全局结构信息。

因此，本文提出了通过概率形式反映样本之间全局性结构信息的有效距离度量方法。具体的有效距离示意图如图1所示。假设有4个数据样本点A、B、C、D。图1（a）是4个样本点之间的有向关系图，图中各边所占的权重值相等。图1（b）中，通过计算概率值P(n|m)表示有向图中样本点之间各边所占的权重，而且图中边的宽度越宽，表示其权重越大。概率值P(n|m)表示从m点出发到达n点的直接路径数与所有从m点出发的直接路径数的比值。例如，概率值P(B|A)=1/4，表示从A点到B点的概率是1 4，其中4表示从A点出发的路径总共有4条，1表示其中有1条路径可以直接到达B点。另外，从图1（b）中容易看出，从B点出发到达D点的概率（如P(D|B)=1）明显大于从C点出发到达D点的概率（如P(D|C)=1/5）。根据Brockmann等人提出的有效距离思想[16]，概率值P(n|m)越小表示从m点到n点的有效距离就越大，反之亦然。跟常见的欧氏距离或者地理距离相比，有效距离因为考虑了数据样本间的全局性结构信息，所以更能体现出数据样本之间隐藏的模式结构信息。因此，用有效距离度量方法代替欧氏距离，能更全面地展示样本之间的关联信息，而完全不受样本分布、地理距离等因素的影响。

Fig.1 Graphical explanation of effective distance图1 有效距离示意图

3 基于有效距离的聚类算法

3.1 基于稀疏表示的有效距离的计算

近年来，稀疏表示在机器学习、模式识别[20]和计算机视觉[21]等领域得到越来越广泛的应用。稀疏表示可以构建高效的数据表示，作为从数据本身学习到的几个典型（原子）模式的一个组合（通常为线性的），很多基于稀疏表示的方法取得了令人鼓舞的成果[22]。如前所述，有效距离度量方法能够考虑数据样本之间的全局性信息。值得注意的是，稀疏表示方法能够有效表达数据的全局特性。基于稀疏表示的这一特性，本文提出了一种基于稀疏表示的有效距离计算方法。

假设需要处理2.1.1小节中描述的样本集。构建数据样本之间有效距离的具体步骤如下：

（1）根据数据样本之间在稀疏表示过程中所占的权重系数构建有向图。

式（5）中B=[x1,x2,…,xi-1,xi+1,…,xn]T表示样本xi从X中移除。

根据式（5）计算求得权重系数矩阵W=[w1,w2,…,wn]T，Wij表示样本xi在稀疏表示样本xj的过程中所占的权重值。λ是稀疏表示过程中的正则化参数λ∈(0,1]，λ越大则矩阵越稀疏。

（2）求数据样本间归一化后的权重系数。

根据式（6）得到归一化的权重系数矩阵P。Pij越大，说明xi在稀疏重建xj时，所占的权重越大，也就表示xi在xj的所有近邻中位置更靠前，xi与xj之间的相似度越大，有效距离越小。

（3）计算样本之间的有效距离。

根据式（7）得到有效距离矩阵ED。因为0≤Pij≤1，所以lnPij≤0，显然EDij≥1。

3.2 基于有效距离的聚类算法

本文通过将有效距离应用到K-means、K-medoids和FCM经典聚类算法中，开发了3种基于有效距离的聚类算法，即EK-means、EK-medoids和EFCM聚类算法。

3.2.1 基于有效距离的K-means聚类算法

传统的K-means聚类算法一般利用欧氏距离评估两个数据样本之间的相似性，考虑到有效距离的思想后，提出了基于有效距离的K-means——EK-means聚类算法。

EK-means聚类算法的目标函数为：

其中，Dij为数据样本xi距离聚类簇的中心vj的有效距离，并且

式（9）以及接下来的式（10）、（11）中m表示该聚类簇所包含的数据样本的个数；rjq表示属于该聚类簇的第q个数据样本在原始数据样本中的编号。

EK-means算法的具体流程如下。

算法1基于有效距离的K-means聚类算法

3.2.2 基于有效距离的K-medoids聚类算法

传统的K-medoids聚类算法一般利用欧氏距离评估数据样本之间的相似性，考虑到有效距离的思想后，提出了基于有效距离的K-medoids——EK-medoids聚类算法。

EK-medoids算法的具体流程与K-means的流程大致相同。不同之处在于，第二步要利用得到的有效距离矩阵ED构造相似性矩阵A∈Rn×n，矩阵中的元素定义如下：

另外需要注意的是簇中心样本更新方法的不同。传统的K-medoids聚类算法中，计算第i个聚类簇的新聚类中心的方法如下：

在EK-medoids算法中应该用下面公式来计算：

这样，第i个聚类簇的新聚类中心vi=xrij。其中j的取值范围均为0≤j≤m。

3.2.3 基于有效距离的FCM聚类算法

FCM是一种柔性的模糊划分。隶属度uki的迭代更新方法为：

其中，uki(1 ≤k≤c,1≤i≤n)表示第i个样本xi属于第k个聚类簇的隶属函数。dki表示数据样本xi与第k个聚类簇的聚类中心之间的距离。

EFCM聚类算法的具体流程如下。

算法2基于有效距离的FCM聚类算法

4 实验结果与分析

4.1 实验设置

本文实验中利用稀疏表示构建数据样本之间的有向图，其中正则化参数λ∈[0.10,0.95]，每次取值间隔0.5。FCM中的模糊加权指数取通用值2。实验最终将聚类后的结果与传统算法的结果进行对比，把聚类的正确精度作为实验结果，同时要求正确率与聚类效果是正相关的。另外，考虑到程序每次运行时聚类中心有不同的初始化，对每个算法重复运行了50次，然后将50次的平均值作为最终的聚类结果。其中，有关有效距离实验的最终结果是取不同λ对应的聚类精度中的最大值。

4.2 实验结果与分析

在10个UCI标准数据集上进行了基于传统欧氏距离的聚类算法和基于有效距离的聚类算法的对比实验。

表1首先描述了实验中所涉及到的10个UCI标准数据集，包括每个数据集中数据样本的维数、个数以及聚类簇数目等情况。然后展示了EK-means聚类算法与K-means聚类算法、EK-medoids聚类算法与K-medoids聚类算法、EFCM聚类算法与FCM聚类算法分别在这些数据集上的聚类结果。从表1的聚类结果可以看出，在UCI标准数据集下，基于有效距离的聚类算法结果绝大部分都要优于基于欧氏距离的聚类算法。

图2是各种算法对比的箱形图。该图非常直观地描述了K-means与EK-means、K-medoids与EK-medoids，FCM与EFCM聚类算法在10个UCI数据集上的聚类结果比较情况。图2中一个箱形对应的横线从下到上依次为：下边缘线、下四分位线、中位数线、上四分位线以及上边缘线。从图2可以明显看出，所有的基于有效距离的算法的各条线都比传统的聚类算法的对应线要高，体现了新算法明显优于传统算法。

Table 1 UCI datasets and comparision of algorithms表1 UCI数据集介绍以及算法结果比较

Fig.2 Clustering results图2 聚类算法结果对比

5 总结与展望

本文提出了一种充分考虑样本之间的全局结构信息的有效距离度量方法。进一步地，对提出的3种基于有效距离的聚类算法，包括EK-means、EK-medoids以及EFCM方法，在标准UCI Benchmark数据集上进行了聚类实验，并通过实验结果验证了所提方法的有效性。在未来的研究中，拟尝试寻找更有意义的距离度量，希望可以更好地完善聚类算法，提高聚类算法的性能。

[1]Xu Rui,Wunsch D.Survey of clustering algorithms[J]. IEEE Transactions on Neural Networks,2005,16(3):645-678.

[2]Shirkhorshidi A S,Aghabozorgi S,Wah T Y,et al.Big data clustering:a review[C]//LNCS 8583:Proceedings of the 14th International Conference on Computational Science and Its Applications,Guimarães,Portugal,Jun 30-Jul 3, 2014.Berlin,Heidelberg:Springer,2014:707-720.

[3]Shi Jinlong,Luo Zhigang.Nonlinear dimensionality reduction of gene expression data for visualization and clustering analysis of cancer tissue samples[J].Computers in Biology and Medicine,2010,40(8):723-732.

[4]Sebiskveradze D,Vrabie V,Gobinet C,et al.Automation of an algorithm based on fuzzy clustering for analyzing tumoral heterogeneity in human skin carcinoma tissue sections[J]. Laboratory Investigation,2011,91(5):799-811.

[5]Kalyani S,Swarup K S.Particle swarm optimization basedK-means clustering approach for security assessment in power systems[J].Expert Systems with Applications,2011, 38(9):10839-10846.

[6]Sun Jigui,Liu Jie,Zhao Liayu.Clustering algorithms research[J].Journal of Software,2008,19(1):48-61.

[7]Huang Zhexue.Extensions to theK-means algorithm for clustering large data sets with categorical values[J].Data Mining and Knowledge Discovery,1998,2(3):283-304.

[8]Gupta H,Srivastava R.K-means based document clustering with automatic“K”selection and cluster refinement[J].International Journal of Computer Science and Mobile Applications,2014,2(5):7-13.

[9]Ruspini E H.A new approach to clustering[J].Information and Control,1969,15(1):22-32.

[10]Zhang Daoqiang,Chen Songcan.Fuzzy clustering using kernel method[C]//Proceedings of the 8th IEEE Interna-tional Conference on Control and Automation,Xiamen, China,Jun 19,2002.Piscataway,USA:IEEE,2002:123-127.

[11]Li Jie,Gao Xinbo,Jiao Licheng.A new feature weighted fuzzy clustering algorithm[C]//LNCS 3641:Proceedings of the 10th International Conference on Rough Sets,Fuzzy Sets,Data Mining,and Granular Computing,Regina,Canada, Aug 31-Sep 3,2005.Berlin,Heidelberg:Springer,2005:412-420.

[12]Cai Weiling,Chen Songcan,Zhang Daoqiang.Fast and robust fuzzy C-means clustering algorithms incorporating local information for image segmentation[J].Pattern Recognition,2007,40(3):825-838.

[13]Groenen P J F,Jajuga K.Fuzzy clustering with squared Minkowski distances[J].Fuzzy Sets and Systems,2001,120 (2):227-237.

[14]Xiang Shiming,Nie Feiping,Zhang Changshui.Learning a Mahalanobis distance metric for data clustering and classification[J].Pattern Recognition,2008,41(12):3600-3612.

[15]Rammal A,Perrin E,Vrabie V,et al.Optimal preprocessing and FCM clustering of MIR,NIR and combined MIR-NIR spectra for classification of maize roots[C]//Proceedings of the 3rd International Conference on E-Technologies and Networks for Development,Apr 29-May 1,2014.Piscataway, USA:IEEE,2014:110-115.

[16]Brockmann D,Helbing D.The hidden geometry of complex,network-driven contagion phenomena[J].Science,2013, 342(6164):1337-1342.

[17]FahadA,Alshatri N,Tari Z,et al.Asurvey of clustering algorithms for big data:Taxonomy and empirical analysis[J]. IEEE Transactions on Emerging Topics in Computing,2014, 2(3):267-279.

[18]Dunn J C.Well-separated clusters and optimal fuzzy partitions[J].Journal of Cybernetics,1974,4(1):95-104.

[19]Bezdek J C.Pattern recognition with fuzzy objective function algorithms[M].Secaucus,USA:Springer-Verlag New York,Inc,1981.

[20]Wright J,Yang A Y,Ganesh A,et al.Robust face recognition via sparse representation[J].IEEE Transactions on PatternAnalysis and Machine Intelligence,2009,31(2):210-227.

[21]Yang Jianchao,Wright J,Huang T S,et al.Image superresolution via sparse representation[J].IEEE Transactions on Image Processing,2010,19(11):2861-2873.

[22]Xie Yuan,Zhang Wensheng,Qu Yangyun,et al.Discriminative subspace learning with sparse representation viewbased model for robust visual tracking[J].Pattern Recognition,2014,47(3):1383-1394.

GUANG Junye was born in 1991.She is an M.S.candidate at Nanjing University of Aeronautics and Astronautics. Her research interests include machine learning,data mining and pattern recognition,etc.

光俊叶（1991—），女，南京航空航天大学硕士研究生，主要研究领域为机器学习，数据挖掘，模式识别等。

LIU Mingxia was born in 1981.She received the Ph.D.degree from Nanjing University of Aeronautics and Astronautics in 2015.Her research interests include machine learning,data mining and medical image processing,etc.

刘明霞（1981—），女，2015年于南京航空航天大学获得博士学位，主要研究领域为机器学习，数据挖掘，医学图像处理等。

ZHANG Daoqiang was born in 1978.He is a professor and Ph.D.supervisor at Nanjing University of Aeronautics and Astronautics.His research interests include machine learning,pattern recognition,data mining and medical image processing,etc.

张道强（1978—），男，南京航空航天大学教授、博士生导师，主要研究领域为机器学习，模式识别，数据挖掘，医学图像处理等。

Application of Effective Distance in ClusteringAlgorithms*

GUANG Junye1,LIU Mingxia1,2,ZHANG Daoqiang1+
1.College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China
2.College of Information Science and Technology,Taishan University,Taian,Shandong 271021,China
+Corresponding author:E-mail:dqzhang@nuaa.edu.cn

Distance metric learning is a key step in clustering analysis,which is an important sub-domain of data mining. Euclidean distance metric is a quite commonly used local distance metric in clustering algorithms,which only focuses on the distance between two samples.This paper proposes a new global distance metric method,named as the effective distance metric.In the new method,the similarity between two samples is evaluated by using not only the distance between these two samples,but also distances between one specific sample and all the other related ones.Sparse reconstruction coefficients are employed to reflect such global relationship among samples.Then,this paper develops three effective distance-based clustering algorithms,including EK-means,EK-medoids and EFCM,by applying the effective distance to three classical clustering algorithms,i.e.,K-means,K-medoids and FCM(fuzzy C-means),respectively. The experimental results on UCI benchmark datasets demonstrate the efficacy of the proposed methods.

clustering;distance metric;metric learning;effective distance

10.3778/j.issn.1673-9418.1603046

A

：TP181

*The National Natural Science Foundation of China under Grant Nos.61422204,61473149(国家自然科学基金);the Open Foundation of Graduate Innovation Center in NUAAunder Grant No.kfjj20151605(南京航空航天大学研究生创新实验室开放基金).

Received 2016-02,Accepted 2016-04.

CNKI网络优先出版:2016-04-19,http://www.cnki.net/kcms/detail/11.5602.TP.20160419.1143.006.html

GUANG Junye,LIU Mingxia,ZHANG Daoqiang.Application of effective distance in clustering algorithms. Journal of Frontiers of Computer Science and Technology,2017,11(3)：406-413.

摘 要：聚类分析是数据挖掘领域的重要组成部分之一，而度量学习是聚类分析中的关键性步骤。传统聚类算法中通常使用欧氏距离进行距离度量，但是欧氏距离只关注两两样本之间的距离关系，并没有顾及数据的全局性分布结构。考虑到数据的全局性结构信息，提出了一种新的具有全局性的度量方法——有效距离度量（effective distance metric），其主要思想是通过稀疏重构的方法计算数据样本之间的有效距离。进一步地，将有效距离应用到K-means、K-medoids和FCM（fuzzy C-means）3种经典聚类算法中开发了3种基于有效距离的聚类算法，即EK-means，EK-medoids和EFCM聚类算法。通过与传统聚类算法在UCI标准数据集上的实验结果进行比较，验证了基于有效距离的聚类算法能显著提高聚类效果。