关于基于局部敏感哈希近邻传播聚类

论文导读：
摘 要：本文针对近邻传播聚类中存在的复杂度高理由，提出了局部敏感哈希的近邻传播聚类算法，根据局部敏感哈希先将相似数据哈希到同一桶中，在对每个桶中的数据进行聚类。实验结果表明，该算法降低了复杂度，提高了准确率。
关键词：近邻传播聚类；局部敏感哈希；相似性
中图分类号：TP311.13
在数据挖掘中，聚类分析是一种自动寻找类别的有效策略。聚类是对对象集进行考察并按照某种距离测度将其聚成多个簇的过程，聚类的目标是使得同一簇内的对象之间距离较短，不同簇内的对象距离较大[1]。聚类算法处理大数据集时要求高效性。通常的传统聚类算法存在着单位时间内处理量小、面对大量的数据时处理时间较长、难以达到预期效果等缺陷[1]。
2007年，Frey等[2]人在Science杂志上的一篇论文首次提出了近邻传播（Affinity Propagation，简称AP）聚类，主要通过消息传播的策略来逐步确定高质量聚类中心并生成相应聚类。克服了K-means算法的缺点，能够在较短的时间内处理大数据集，得到较理想的结果。
针对近邻传播聚类计算复杂度高理由，有以下改善策略，如可变相似性度量的近邻传播聚类[3]，基于互近邻一致性的近邻传播聚类[4]等。本文提出一种基于局部敏感哈希的近邻传播聚类策略，降低了计算复杂度，提高了准确率。
1 近邻传播聚类
近邻传播算法根据N个数据点之间的相似度进行聚类，这些相似度可以是对称的，也可以是不对称的。这些相似度组成N×N的相似度矩阵S。任意两个数据点xi和xj之间的相似度S（i，j）=-‖xi-xj‖2被存储在N×N。将所有数据点都作为潜在的聚类中心。以S矩阵的对角线上的数值S（k，k）作为k成为聚类中心的评判标准，该值越大，则其成为聚类中心的可能性也就越大，即参考度p（preference）。
在近邻传播聚类传递两种类型的消息，即吸引度（responsibility）和归属度（ailability）。r（i，k）表示从点i发送到候选聚类中心k的数值消，判断k点是否是i点的聚类中心。a（i，k）则从候选聚类中心k发送到i的数值消息，判断i点是否选择k作为其聚类中心。r（i，k）与a（i，k）越大，则k点作为聚类中心的可能性就越大，并且i点隶属于以k点为聚类中心的聚类的可能性也越大。在近邻传播聚类中，每次迭代都更新每个点的吸引度和归属度值，直到迭代结束，聚类中心确定，然后将其余点分配到相应的聚类中。
2 基于局部敏感哈希的近邻传播聚类
由于近邻传播聚类计算复杂度高，所以引进局部敏感哈希概念，先将相似近邻的数据哈希到相同桶中，然后对每个桶中的数据建立基于局部敏感哈希的近邻传播聚类论文资料由论文网www.7ctime.com提供,转载请保留地址.矩阵，进行迭代，判断每个桶中的聚类中心，降低了计算复杂度，提高了准确性。
2.1 局部敏感哈希。局部敏感哈希（locality-sensitive hashing，简称LSH）的基本思想是[5]：对目标项进行多次哈希，使得相似项会比不相似项更可能哈希到同一个桶中，至少有一次哈希到同一个桶中的即为候选对。定义函数族F，若F中每个函数f都满足下列条件，则称为（d1，d2，p1，p2）-敏感的函数族：
（1）若d（x，y）≤d1，则f（x）=f（y）的概率至少为p1。
（2）若d（x，y）≥d2，则f（x）=f（y）的概率至多为p2。
其中d（x，y）表示x和y之间距离，p1>p2，d1在近邻传播聚类中相似度矩阵采用欧式距离，则D维空间中面向欧式空间的LSH函数族为：F（v）=|vr+b|÷a。其中r是一个随机变量，a是桶宽，b是一个在[0，a]之间均匀分布的随机变量。所以vr是v在向量r上的投影，该函数族是（a/2，2a，1/2，1/3）-敏感的。即函数族F将每个数据哈希到的目标桶是随机直线上长度为a的线段，在同一线段内的数据相似性大。
定义一组哈希函数，设置不同的桶宽a，可以快速地将相似数据哈希到同一个桶中。
2.2 基于局部敏感哈希的近邻传播算法。（1）初始化桶宽a，最大迭代次数Max，聚类划分连续不变次数Convits，阻尼系数θ，a（i，k）=0，r（i，k）=0。（2）定义哈希函数族F，对所有相似数据哈希到相同桶中，F（v）=|vr+b|÷a。（3）对每个桶mj中的数据，计算相似度矩阵Sj（i，k），及对角线元素Sj（k，k）。（4）更新吸引度rj（i，k），归属度aj（i，k）。
rj（i，k）=Sj（i，k）-max{aj（i，k′）+Sj（i，k′）} 其中k≠k′
aj（i，k）=min{0，rj（k，k）+∑i′{max（0，rj（i′，k））}} 其中i≠i′，i′≠k
aj（i，k）=∑i′{max（0，rj（i′，k））} 其中i′≠k
（5）消除聚类结果震荡：rjnew（i，k）=θrjold（i，k）+（1-θ）rjnew（i，k）；ajnew（i，k）=θajold（i，k）+（1-θ）ajnew（i，k）。（6）对每个桶内数据重复执行4、5步，直到迭代次数超过max或聚类连续Convits不变即停止。（7）输出每个桶的聚类结果。
3 实验与结果分析
实验环境是在Matlab 2009b仿真平台上进行，CPU为2G，主存为1G。实验数据集采用uci数据集中的4组，如表1。本实验主要对比新算法与原近邻传播聚类算法的效率与准确性，准确性根据正确聚类数占所有数据比例进行计算。
表1 数据集
名称类数维度大小
Iris34150
Wine313178
Glass69214ISTANBUL STOCK EXCHANGE 128536
针对不同的数据集，采用不同的桶宽，定义阻尼系数为0.5，相似度用欧氏距离的相反数表示，表2为两种算法在数据集上的比较结果：
表2 实验结果
名称类数原算法类数新算法类数原算法迭代次数新算法迭代次数原算法准确度新算法准确基于局部敏感哈希的近邻传播聚类相关论文由www.7ctime.com收集,如需论文.度论文导读：-2526.王斌译.大数据互联网大规模数据挖掘与分布式处理.北京：人民邮电出版社，2012.作者简介：刘淑鑫（1988.12-），女，山东人，硕士研究生，研究方向：数据挖掘。作者单位：东华大学计算机科学与技术学院，上海201620上一页12

Iris33389800.950.95
Wine333104960.860.87
Glass6661261020.760.79
ISTANBUL STOCK EXCHANGE 1212132131780.670.65
在数据集Iris、Wine、Glass中，新算法表现了较高的准确度，能够正确聚类，且迭代次数少于原算法，降低了消耗，提高了效率。在数据集ISTANBUL STOCK EXCHANGE中，新算法聚类类数与原算法出现了差别，理由有可能是对于桶宽的设定不够合适，数据哈希后的桶的数据多于类数，在今后的研究中应该分析如何降低桶中伪正例的概率及桶间数据相似性降低。
4 结束语
本文提出了局部敏感哈希的近邻传播聚类算法，根据局部敏感哈希先将相似数据哈希到同一桶中，在对每个桶中的数据进行聚类。实验结果表明，该算法一定程度上降低了复杂度，提高了准确率。今后应继续对桶宽的设置、降低桶中伪正例进行研究。
参考文献：
[1]L.Kaufman and P.Rousseeuw.Find Groups in Data：An Introduction to Cluster Analysis. Wiley Press，2005.
[2]Frey B.J.，Dueck D.Clustering by Passing Messages between Data Points[J].Science，2007（5814）：72-976.
[3]董俊，王锁萍，熊范纶.可变相似性度量的近邻传播聚类[J].电子与信息学 报，2010（03）：509-514.
[4]邢艳，周勇.基于互近邻一致性的近邻传播算法[J].计算机应用研究，2012（07）：2524-2526.
[5]王斌译.大数据互联网大规模数据挖掘与分布式处理[M].北京：人民邮电出版社，2012.
作者简介：刘淑鑫（1988.12-），女，山东人，硕士研究生，研究方向：数据挖掘。
作者单位：东华大学 计算机科学与技术学院，上海 201620