基于改进相似性度量的邻近传播聚类算法

温爱红 徐草草

摘 要： 邻近传播（Affinity Propagation，AP）聚类将数据集中所有数据点均视为潜在的聚类中心，并采用欧氏距离法计算输入相似度矩阵，导致其性能对变形十分敏感。针对这一缺陷，提出了采用两种不同的相似性度量方法来计算数据集中两个数据点之间的相似度。分别将明可夫斯基（Minkowski）和切比雪夫（Chebychev）相似性度量引入到AP聚类中，替换原有的欧氏距离度量来构建相似性矩阵。在UCI机器学习数据集上，利用Jaccard指数和Fowlkes-Mlowers对提出方法进行了量化评估。实验结果表明，基于明可夫斯基距离和切比雪夫距离的AP聚类方法在总体精度上优于现有的欧氏距离。

关键词： 数据聚类; 邻近传播算法; 欧氏距离; 相似性度量; 聚类中心

中图分类号： TP 393      文献标志码： A

Abstract： Affinity propagation （AP） clustering treats all data points in the dataset as potential cluster centers， and uses the Euclidean distance method to calculate the input similarity matrix， which results in its performance being very sensitive to deformation. In view of this defect， two different similarity measurement methods are proposed to calculate the similarity between two data points in the data set. Minkowski and Chebychev similarity measures are introduced into the AP cluster， respectively， and the original Euclidean distance measure is replaced to construct the similarity matrix. On the UCI machine learning data set， the proposed method is quantitatively evaluated using Jaccard index and Fowlkes-Mlowers. The experimental results show that the AP clustering method based on Minkowski distance and Chebyshev distance has better overall accuracy than the existing Euclidean distance.

Key words： data clustering; proximity propagation algorithm; Euclidean distance; similarity measure; cluster center

0 引言

作為数据挖掘的常用技术方法之一，聚类分析技术出现的频度较高，聚类方法被广泛应用于计算机视觉、市场分析、生物信息学等不同领域[1-3]。聚类方法的目标是将一个数据集划分成不同的子簇，将具有相似特征的数据点划分到一个簇中。

作为一种新的无监督聚类技术，邻近传播（Affinity Propagation，AP）聚类是Frey和Dueck[4] 提出的一种基于消息传递的聚类算法，表现出比传统聚类方法更好的性能。不同于传统的聚类方法，AP聚类使用了相似性矩阵和偏向参数。前者用于实现相似性度量从而获得数据点之间相似性的真实值。由于AP聚类将所有数据集对象视为聚类中心，因此通过在数据点之间传递基于偏向参数的真实值消息来进行数据点分簇，直到获得一组中心和聚类结果。通过上述分析，可以得出偏向参数用于确定聚类的数量，通常以相似度的中间值作为偏好值。通过逐渐调整偏向参数，可以获得不同数量的聚类结果。

1 相关工作分析

近年来，AP聚类被广泛应用于医学图像分割、网络定位等领域[5-6]。例如，在医学图像分割方面，AP聚类被用来在功能磁共振成像（Functional magnetic resonance imaging，FMRI）中对大脑区域进行聚类。AP聚类也可以用于检测动态对比增强磁共振成像中的动脉输入功能。此外，AP聚类通过选择最佳阈值实现分割正电子发射断层扫描图像中的区域。

然而，大多数文献采用了欧几里德距离（欧氏距离）作为相似性度量，这影响了AP聚类的性能。这是因为欧几里德距离度量对变形具有很高的敏感度，具体来说就是欧几里德距离没有考虑数据点之间的空间关系。近期有研究人员开始尝试使用不同的相似性度量方法来取代传统的欧几里德距离，以便改善AP聚类性能。在文献[7]中，引入了一种模糊统计相似性度量（fuzzy statistical similarity measure，FSS）来评价像素矢量之间的相似性。而文献[8]通过引入非对称相似性度量，扩展了基于余弦指数的相似性度量。在文献[9]中，使用两个不同数据点之间的欧几里德距离的组合来寻找相似度矩阵。

借鉴上述研究的思路，本文对AP聚类算法进行了改进，提出了采用两种不同的相似性度量来计算数据集中数据点之间的相似度，以提高其聚类精度。

2 邻近传播聚类存在的问题

与其他聚类方法相比，AP聚类算法实现起来更加简单、快速，能够获得更低的聚类误差。虽然它有一定优势，但在两个方面仍具有局限性[6]：

1） 相似性度量;

2） 寻找最佳偏向参数。

3 提出的改进相似性度量的方法

在这一部分中，提出将明可夫斯基和切比雪夫相似性度量引入到AP聚类中，来构建不同的相似性矩阵，其目的是定义一个相似度函数（x，y），函数的值表示两点之间的“相似”程度。

3.1 基于明可夫斯基度量的相似矩阵

明可夫斯基距离被认为是包含其他特殊距离（如欧几里得距离）的广义距离。近年来，许多关于聚类的研究都将明可夫斯基距离纳入到他们的研究中。已有不少模糊聚类方法采用了明可夫斯基距离函数。文献[10]利用明可夫斯基距离函数对模糊c-均值算法的性能进行了改进研究。因此，明可夫斯基距离是一种简明的参数化距离，通过调整明可夫斯基参数p可以适应任何应用场景。

3.2 基于切比雪夫度量的相似矩阵

切比雪夫距离用于检查数据点对之间的绝对差值。切比雪夫距离定义如式（9）。DChebyshev（p，q）=maxpi-qi

（9）  为了正确分割图像，在文献[24]中将切比雪夫度量引入到轮廓模型中。切比雪夫距离是具有L范数的明可夫斯基距离的特例，其主要优点是确定数据集之间距离时所需时间较短，因此本文将其引入到AP聚类。本文提出了一种基于切比雪夫的方法来构造相似度矩阵。方程式中的契比雪夫。公式（9）中的切比雪夫将提供成对数据点之间的最大距离。然后，当应用于AP聚类时，切比雪夫将被转换为负值，如式（10）。s（i，k）=-maxxi-ki

（10）  使用切比雪夫相似性度量的AP聚类流程与图1一致。

4 实验结果

4.1 数据集

在从UCI机器学习库获得的IRIS数据集、Wine和Ionoshpere数据集[10]上对所提出的改进进行了评估，以验证所提出的算法。其中，IRIS数据集包含150个实例，具有4个特征，具有3个簇。Wine数据集包含178个实例，具有13个特征，并分为3个簇。Ionosphere数据集包含351个实例，具有34个特征，具有2个簇。这些数据集的详细信息、大小、维度和簇的数量，如表1所示。

4.3 聚类结果可视化

直观显示IRIS上采用明可夫斯基距离度量的AP聚类结果，如图2所示。

IRIS上采用切比雪夫距离度量的AP聚类结果，如图3所示。

从图2和图3可以看出，以萼片长度和宽度，花瓣长度为坐标轴的三维聚类可视化验证了两种方法的有效性。

4.4 性能对比

使用来自UCI的3个数据集进行了AP聚类测试，以评估所提出的方法的准确性。该方法是通过改变传统AP算法的距离度量来实现的。如表2—表4所示。

分别显示了使用欧氏距离、欧氏距离组合[9]、明可夫斯基和切比雪夫四种不同距离度量的AP聚类结果。表2给出了四种不同距离度量方法在Iris数据集上的聚类结果，表中粗体表示最佳聚类結果。

从表2可以看出，采用明可夫斯基的AP聚类准确率最高，Jaccard指数T为0.80，Fowlkes-Mlowers指数FM为0.89。采用切比雪夫的AP聚类准确率次之，分别为0.78和0.88。采用欧氏距离组合的AP聚类准确率稍差，分别为0.76和0.85。采用的AP聚类准确率最低。表3给出了四种不同距离度量方法在Ionoshpere数据集上的聚类结果，准确率结果排名第一的为切比雪夫距离，其次为明可夫斯基距离。

表4给出了4种不同距离度量方法在Wine数据集上的聚类结果。对于Iris和Ionoshpere数据集，使用明可夫斯基和切比雪夫距离度量确实适度提高了聚类质量和精度。然而，使用欧氏距离和欧氏距离组合的AP聚类在Wine数据集中的表现优于明可夫斯基和切比雪夫。之所以会出现这种情况，是因为Wine数据集的不同簇中有一些数据点聚集过于紧密。

对于不同的p值，基于明可夫斯基度量的AP聚类结果也有不同。当 p=2时，其结果与采用欧氏距离的AP聚类结果相同。当p=3时，其聚类性能更低。

结果表明，由于明可夫斯基距离的灵活性和通用性，在AP聚类中采用明可夫斯基距离更为可取。尽管切比雪夫距离确实产生了很好的结果，但它仍然只是明可夫斯基距离的一个特例。

5 总结

本文提出了基于明可夫斯基距离和切比雪夫距离的AP聚类方法，并在对UCI数据集上进行验证。实验结果表明，选择不同距离度量方法对聚类结果有很大的影响。与欧氏距离和欧氏距离组合相比，基于明可夫斯基距离和切比雪夫距离的AP聚类方法的总体精度更高。因此，在选择距离度量时应给予相当的重视。但是对于在紧密程度较高的数据集，使用欧几里德距离的AP聚类表现更好，后期将对该问题进行进一步研究。

参考文献

[1] 谢娟英， 屈亚楠. 密度峰值优化初始中心的K-medoids聚类算法[J]. 计算机科学与探索， 2016， 10（2）：230-247.

[2] 周润物， 李智勇， 陈少淼，等. 面向大数据处理的并行优化抽样聚类K-means算法[J]. 计算机应用， 2016， 36（2）：311-315.

[3] 罗恩韬， 王国军， 李超良. 大数据环境中多维数据去重的聚类算法研究[J]. 小型微型计算机系统， 2016， 37（3）：438-442.

[4] Chidean M I， Morgado E， Sanromán-Junquera M， et al. Energy Efficiency and Quality of Data Reconstruction Through Data-Coupled Clustering for Self-Organized Large-Scale WSNs[J]. IEEE Sensors Journal， 2016， 16（12）：5010-5020.

[5] 谷瑞军， 汪加才， 陈耿.面向大规模数据集的近邻传播聚类[J]. 计算机工程， 36（23）：22-24.

[6] 刘璐， 靳少辉， 焦李成. 采用流形近邻传播聚类的极化SAR图像分类[J]. 信号处理， 2016， 32（2）：135-141.

[7] Yang C， Bruzzone L， Sun F， et al. A Fuzzy-Statistics-Based Affinity Propagation Technique for Clustering in Multispectral Images[J]. IEEE Transactions on Geoscience & Remote Sensing， 2010， 48（6）：2647-2659.

[8] 董俊， 王锁萍， 熊范纶. 可变相似性度量的近邻传播聚类[J]. 电子与信息学报（3）：5-10.

[9] Zhirong Yang， Jukka Corander， Erkki Oja. Low-Rank Doubly Stochastic Matrix Decomposition for Cluster Analysis[J]. Journal of Machine Learning Research， 2016， 17（187）：1-25.

[10] Punit Rathore， James C. Bezdek， Sarah M. Erfani. Ensemble Fuzzy Clustering Using Cumulative Aggregation on Random Projections[J]. IEEE Transactions on Fuzzy Systems， 2018， 26（3）：1510-1524.

（收稿日期： 2020.04.01）