属性分布相似度吸引子传播聚类算法研究

王依章， 王丽敏＊， 韩旭明

（1.吉林财经大学管理科学与信息工程学院，吉林长春 130117；2.长春工业大学软件学院，吉林长春 130012）

0 引 言

吸引子传播聚类算法是美国学者Frey2007年在《Science》杂志上提出的一种新聚类算法。目前，该算法已成功应用于图像分割［1－2］、图像检索［3］、基因识别［4］、文本聚类［5］、最优航空路线确定［6］等诸多领域。近年来，国内外学者提出多种改进方法。例如国外学者Bruzzone L［7］等提出吸引子传播算法应用于多光谱图像领域，Qasim I［8］等把该算法应用在文本概念图自动生成领域，取得了显著的应用效果。国内学者于吉红［9］等提出用空间向量模型计算特征相似度，并应用于舰船三维模型进行视点空间均匀投影。张震［10］等提出将吸引子传播算法与数据流聚类相结合，改良了数据流聚类模型。文中根据属性间分布相似度提出改进算法，提高对高维稀疏数据的聚类性能，并应用于超市销售数据聚类。

1 吸引子传播聚类算法

吸引子传播聚类算法利用数据点之间的相似度构造相似度关系矩阵S［11］。相似度是两点间距离的相反数［12］。

相似度矩阵对角线的中值就是偏向参数P［13］。该算法初始假设每个样本点成为类代表的可能性相同，同时引入归属度矩阵和吸引度矩阵共同决定每一个样本的类代表点，计算方法如下：

吸引子传播聚类算法利用 下式计算归属度a（i，k）和吸引度r（i，k）之和，获取每个样本的类代表点［14］：

利用以下公式增强算法迭代的稳定性［15］：

2 基于属性分布相似度的吸引子传播聚类算法

文中提出基于属性分布相似度的吸引子传播聚类算法，构造新相似度矩阵。在高维二元数据中，假设X是数据对象集合，X＝｛Xi｜i＝1，2…，D｝，A是属性集合，A＝｛Ai｜i＝1，2…，D｝，Y＝｛Yij｜i＝1，2…，D｝表示对象在各属性分布上的取值分布情况，是i个对象的属性分布特征向量。如果Yij＝1，表明第i个对象在第j个属性上有值，否则稀疏。数据对象间相似度：

高维稀疏情形下，每个对象在属性取值上存在大量零值，有取值的属性数占总属性数的比例很小。改进方法如下式：

将式（8）计算的相似度矩阵引入吸引子传播算法，取代欧式距离矩阵。在实际应用中可以给相似度加上权重系数，当维度较高时，权重系数越接近1，可以发现更多有意义的相似对象，如下式：

3 仿真模拟实验与分析

仿真模拟实验环境是Pentium G645 2.9GHz CPU，4GB内存。实验采用UCI二元数据集，真实类数为2类，参数λ＝0.5，调整偏向参数P值，结果见表1和表2。

表1 AP聚类算法实验记录

表2 PDS-AP聚类算法实验记录

表1和表2表明，AP聚类算法在λ值不变的情况下，聚类类数逐渐减少，精度增高，最终稳定的聚类类数是3类，P值增大至某一点时发散，得不到数据集的真实类数。PDS-AP聚类算法在不同偏向参数下聚类性能均优于传统算法，并能够获取真实类数。

4 超市销售数据聚类应用

PDS-AP聚类算法应用在真实超市销售数据，数据来源于科研数据共享平台，数据总量共有741×41个数据点，超市销售数据见表3。

表3 超市销售数据

运行PDS-AP聚类算法，类数16，将对应的对象和其所属样本点放在一起，将增加客户的购买度和购物享受。如果有顾客特征资料，可以分析不同客户群的需求。

5 结 语

传统吸引子传播聚类算法的相似度矩阵基于欧式距离，对数据的类型具有选择性。为了克服此弊端，文中提出的基于属性分布相似度的PDSAP聚类算法，经UCI标准数据集和真实数据的验证，与传统的AP聚类算法相比，聚类精度更高，收敛速度更快，更适合高维稀疏数据的聚类。PDS-AP聚类算法的实际应用也取得了满意结果，而面对聚类结构复杂的数据，还需结合群优化算法进一步研究。

［1］ 许晓丽，卢志茂，张格森，等.改进近邻传播聚类的彩色图像分割［J］.计算机辅助设计与图形学学报，2012，24（4）：514-519.

［2］ 齐美彬，朱俊俊，纪平，等.大规模图像集中的代表性图像选取［J］.自动化学报，2014，40（4）：706-712.

［3］ 杨传慧，吉根林，章志刚.基于分块加权颜色直方图的图像聚类算法研究［J］.南京师范大学学报：工程技术版，2013，13（1）：42-43.

［4］ 汤健，管云雁，刘文广，等.马氏珠母贝家系遗传结构的微卫星分析［J］.Marine Sciences，2013，37（8）：35.

［5］ 文翰，肖南峰.基于强类别特征近邻传播的半监督文本聚类［J］.模式识别与人工智能，2013（5）：391.

［6］ 郑志敏，徐青.基于吸引子传播算法的城市航空便利性分析［J］.硅谷，2013（9）：72-73.

［7］ Yang C，Bruzzone L，Guan R C，et al.Incremental and decremental affinity propagation for semisupervised clustering in multispectral mages［J］.IEEE Transactions on Geoscience and Remote Sensing，2013，51（3）：1666-1679.

［8］ Qasim I，Jeong J W，Heu J U，et al.Concept map construction from text documents using affinity propagation［J］.Journal of Information Science，2013，39（1）：7-14.

［9］ 于吉红，白晓明，吕俊伟.改进相似度的吸引子传播聚类算法［J］.小型微型计算机系统，2013，34（3）：603-604.

［10］ 张震，汪斌强，李向涛，等.基于近邻传播学习的半监督流量分类方法［J］.自动化学报，2013，39（7）：1100-1109.

［11］ Sakellariou A，Sanoudou D，Spyrou G.Combining multiple hypothesis testing and affinity propagation clustering leadsto accurate，robust and sample size independent classification on gene expression data［J］.BMC bioinformatics，2012，13（1）：270.

［12］ 张震，汪斌强，伊鹏，等.一种分层组合的半监督近邻传播聚类算法［J］.电子与信息学报，2013，35（3）：645-651.

［13］ Torrent-Fontbona F，Muoz V，Lopez B.Solving large immobile location-allocation by affinity propagation and simulated annealing application to select which sporting event to watch［J］.Expert Systems with Applications，2013，40（11）：4593-4599.

［14］ Sattar F，Driessen P F.Non-stationary signals separation using STFT and affinity propagation clustering algorithm［C］／／Communications，Computers and Signal Processing（PACRIM），2013 IEEE Pacific Rim Conference on.IEEE，2013：389-394.

［15］ Foster B，Bagci U，Luna B，et al.Robust segmentation and accurate target definition for positron emission tomography images using Affinity Propagation［C］／／Biomedical Imaging（ISBI），2013IEEE 10th International Symposium on. IEEE，2013：1461-1464.