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

1、基于局部敏感哈希的近邻传播聚类 本文档格式为WORD,感谢你的阅读。 摘 要：本文针对近邻传播聚类中存在的复杂度高问题，提出了局部敏感哈希的近邻传播聚类算法，根据局部敏感哈希先将相似数据哈希到同一桶中，在对每个桶中的数据进行聚类。实验结果表明，该算法降低了复杂度，提高了准确率。 关键词：近邻传播聚类；局部敏感哈希；相似性 TP311.13 在数据挖掘中，聚类分析是一种自动寻找类别的有效方法。聚类是对对象集进行考察并按照某种距离测度将其聚成多个簇的过程，聚类的目标是使得同一簇内的对象之间距离较短，不同簇内的对象距离较大1。聚类算法处理大数据集时要求高效性。通常的传统聚类算法存在着单位时间内处理量

2、小、面对大量的数据时处理时间较长、难以达到预期效果等缺陷1。 2007年，Frey等2人在Science杂志上的一篇论文首次提出了近邻传播（Affinity Propagation，简称AP）聚类，主要通过消息传播的方法来逐步确定高质量聚类中心并生成相应聚类。克服了K-means算法的缺点，能够在较短的时间内处理大数据集，得到较理想的结果。 针对近邻传播聚类计算复杂度高问题，有以下改进方法，如可变相似性度量的近邻传播聚类3，基于互近邻一致性的近邻传播聚类4等。本文提出一种基于局部敏感哈希的近邻传播聚类方法，降低了计算复杂度，提高了准确率。 1 近邻传播聚类 近邻传播算法根据N个数据点之间的相似

3、度进行聚类，这些相似度可以是对称的，也可以是不对称的。这些相似度组成N×N的相似度矩阵S。任意两个数据点xi和xj之间的相似度S（i，j）=-xi-xj2被存储在N×N。将所有数据点都作为潜在的聚类中心。以S矩阵的对角线上的数值S（k，k）作为k成为聚类中心的评判标准，该值越大，则其成为聚类中心的可能性也就越大，即参考度p（preference）。 在近邻传播聚类传递两种类型的消息，即吸引度（responsibility）和归属度（availability）。r（i，k）表示从点i发送到候选聚类中心k的数值消，判断k点是否是i点的聚类中心。a（i，k）则从候选聚类中心k发送

4、到i的数值消息，判断i点是否选择k作为其聚类中心。r（i，k）与a（i，k）越大，则k点作为聚类中心的可能性就越大，并且i点隶属于以k点为聚类中心的聚类的可能性也越大。在近邻传播聚类中，每次迭代都更新每个点的吸引度和归属度值，直到迭代结束，聚类中心确定，然后将其余点分配到相应的聚类中。 2 基于局部敏感哈希的近邻传播聚类 由于近邻传播聚类计算复杂度高，所以引进局部敏感哈希概念，先将相似近邻的数据哈希到相同桶中，然后对每个桶中的数据建立矩阵，进行迭代，判断每个桶中的聚类中心，降低了计算复杂度，提高了准确性。 2.1 局部敏感哈希。局部敏感哈希（locality-sensitive hashing

5、，简称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<d2。 在近邻传播聚类中相似度矩阵采用欧式距离，则D维空间中面向欧式空间的LSH函数族为：F（v）=|vr+b|÷a。其中r是一个随机变量，a是桶宽，b是一个

6、在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），及对角

7、线元素Sj（k，k）。（4）更新吸引度rj（i，k），归属度aj（i，k）。 rj（i，k）=Sj（i，k）-maxaj（i，k）+Sj（i，k） 其中kk aj（i，k）=min0，rj（k，k）+imax（0，rj（i，k） 其中ii，ik aj（i，k）=imax（0，rj（i，k） 其中ik （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）输出每个桶的聚类结果。

8、3 实验与结果分析 实验环境是在Matlab 2009b仿真平台上进行，CPU为2G，主存为1G。实验数据集采用uci数据集中的4组，如表1。本实验主要对比新算法与原近邻传播聚类算法的效率与准确性，准确性根据正确聚类数占所有数据比例进行计算。 表1 数据集 名称 类数 维度 大小 Iris 3 4 150 Wine 3 13 178 Glass 6 9 214 ISTANBUL STOCK EXCHANGE 12 8 536 针对不同的数据集，采用不同的桶宽，定义阻尼系数为0.5，相似度用欧氏距离的相反数表示，表2为两种算法在数据集上的比较结果： 表2 实验结果 名称 类数 原算法类数 新算法

9、类数 原算法迭代次数 新算法迭代次数 原算法准确度 新算法准确度 Iris 3 3 3 89 80 0.95 0.95 Wine 3 3 3 104 96 0.86 0.87 Glass 6 6 6 126 102 0.76 0.79 ISTANBUL STOCK EXCHANGE 12 12 13 213 178 0.67 0.65 在数据集Iris、Wine、Glass中，新算法表现了较高的准确度，能够正确聚类，且迭代次数少于原算法，降低了消耗，提高了效率。在数据集ISTANBUL STOCK EXCHANGE中，新算法聚类类数与原算法出现了差别，原因有可能是对于桶宽的设定不够合适，数据哈

10、希后的桶的数据多于类数，在今后的研究中应该分析如何降低桶中伪正例的概率及桶间数据相似性降低。 4 结束语 本文提出了局部敏感哈希的近邻传播聚类算法，根据局部敏感哈希先将相似数据哈希到同一桶中，在对每个桶中的数据进行聚类。实验结果表明，该算法一定程度上降低了复杂度，提高了准确率。今后应继续对桶宽的设置、降低桶中伪正例进行研究。 参考文献： 1L.Kaufman and P.Rousseeuw.Find Groups in Data：An Introduction to Cluster Analysis. Wiley Press，2005. 2Frey B.J.，Dueck D.Clusterin

11、g by Passing Messages between Data PointsJ.Science，2007（5814）：72-976. 3董俊，王锁萍，熊范纶.可变相似性度量的近邻传播聚类J.电子与信息学 报，2010（03）：509-514. 4邢艳，周勇.基于互近邻一致性的近邻传播算法J.计算机应用研究，2012（07）：2524-2526. 5王斌译.大数据互联网大规模数据挖掘与分布式处理M.北京：人民邮电出版社，2012. 作者简介：刘淑鑫（1988.12-），女，山东人，硕士研究生，研究方向：数据挖掘。 作者单位：东华大学 计算机科学与技术学院，上海 201620 文档资料：基于局部敏感哈希的近邻传播聚类 完整下载 完整阅读 全文下载 全文阅读 免费阅读及下载阅读相关文档:应用改进粒子群算法在云计算任务调度中的应用及其仿真研究 解析基于激光跟踪仪标定五轴数控加工中心主轴 单片机电路在防盗报警系统中的应用 蚁群遗传算法对于TSP问题的应用 计算机管理信息系统的发展方向探讨 企业计算机网络安全现状与控制探讨 局域网的安全攻防测试与分析 刍议计算机网络安全技术及其发展趋势 WOWAFAHP的网络安全研究与应用 浅谈数字证书在网络安全中的应用 多媒体通信技术在如今社会信息高速公路中的应用 如何构建