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的網絡安全研究與應用 淺談數字證書在網絡安全中的應用 多媒體通信技術在如今社會信息高速公路中的應用 如何構建