基于局部敏感哈希的近鄰傳播聚類

1、基于局部敏感哈希的近鄰傳播聚類 本文檔格式為WORD,感謝你的閱讀。 摘 要：本文針對近鄰傳播聚類中存在的復(fù)雜度高問題，提出了局部敏感哈希的近鄰傳播聚類算法，根據(jù)局部敏感哈希先將相似數(shù)據(jù)哈希到同一桶中，在對每個桶中的數(shù)據(jù)進行聚類。實驗結(jié)果表明，該算法降低了復(fù)雜度，提高了準(zhǔn)確率。 關(guān)鍵詞：近鄰傳播聚類；局部敏感哈希；相似性 TP311.13 在數(shù)據(jù)挖掘中，聚類分析是一種自動尋找類別的有效方法。聚類是對對象集進行考察并按照某種距離測度將其聚成多個簇的過程，聚類的目標(biāo)是使得同一簇內(nèi)的對象之間距離較短，不同簇內(nèi)的對象距離較大1。聚類算法處理大數(shù)據(jù)集時要求高效性。通常的傳統(tǒng)聚類算法存在著單位時間內(nèi)處理量

2、小、面對大量的數(shù)據(jù)時處理時間較長、難以達到預(yù)期效果等缺陷1。 2007年，F(xiàn)rey等2人在Science雜志上的一篇論文首次提出了近鄰傳播（Affinity Propagation，簡稱AP）聚類，主要通過消息傳播的方法來逐步確定高質(zhì)量聚類中心并生成相應(yīng)聚類?？朔薑-means算法的缺點，能夠在較短的時間內(nèi)處理大數(shù)據(jù)集，得到較理想的結(jié)果。 針對近鄰傳播聚類計算復(fù)雜度高問題，有以下改進方法，如可變相似性度量的近鄰傳播聚類3，基于互近鄰一致性的近鄰傳播聚類4等。本文提出一種基于局部敏感哈希的近鄰傳播聚類方法，降低了計算復(fù)雜度，提高了準(zhǔn)確率。 1 近鄰傳播聚類 近鄰傳播算法根據(jù)N個數(shù)據(jù)點之間的相似

3、度進行聚類，這些相似度可以是對稱的，也可以是不對稱的。這些相似度組成N×N的相似度矩陣S。任意兩個數(shù)據(jù)點xi和xj之間的相似度S（i，j）=-xi-xj2被存儲在N×N。將所有數(shù)據(jù)點都作為潛在的聚類中心。以S矩陣的對角線上的數(shù)值S（k，k）作為k成為聚類中心的評判標(biāo)準(zhǔn)，該值越大，則其成為聚類中心的可能性也就越大，即參考度p（preference）。 在近鄰傳播聚類傳遞兩種類型的消息，即吸引度（responsibility）和歸屬度（availability）。r（i，k）表示從點i發(fā)送到候選聚類中心k的數(shù)值消，判斷k點是否是i點的聚類中心。a（i，k）則從候選聚類中心k發(fā)送

4、到i的數(shù)值消息，判斷i點是否選擇k作為其聚類中心。r（i，k）與a（i，k）越大，則k點作為聚類中心的可能性就越大，并且i點隸屬于以k點為聚類中心的聚類的可能性也越大。在近鄰傳播聚類中，每次迭代都更新每個點的吸引度和歸屬度值，直到迭代結(jié)束，聚類中心確定，然后將其余點分配到相應(yīng)的聚類中。 2 基于局部敏感哈希的近鄰傳播聚類 由于近鄰傳播聚類計算復(fù)雜度高，所以引進局部敏感哈希概念，先將相似近鄰的數(shù)據(jù)哈希到相同桶中，然后對每個桶中的數(shù)據(jù)建立矩陣，進行迭代，判斷每個桶中的聚類中心，降低了計算復(fù)雜度，提高了準(zhǔn)確性。 2.1 局部敏感哈希。局部敏感哈希（locality-sensitive hashing

5、，簡稱LSH）的基本思想是5：對目標(biāo)項進行多次哈希，使得相似項會比不相似項更可能哈希到同一個桶中，至少有一次哈希到同一個桶中的即為候選對。定義函數(shù)族F，若F中每個函數(shù)f都滿足下列條件，則稱為（d1，d2，p1，p2）-敏感的函數(shù)族： （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函數(shù)族為：F（v）=|vr+b|÷a。其中r是一個隨機變量，a是桶寬，b是一個

6、在0，a之間均勻分布的隨機變量。所以vr是v在向量r上的投影，該函數(shù)族是（a/2，2a，1/2，1/3）-敏感的。即函數(shù)族F將每個數(shù)據(jù)哈希到的目標(biāo)桶是隨機直線上長度為a的線段，在同一線段內(nèi)的數(shù)據(jù)相似性大。 定義一組哈希函數(shù)，設(shè)置不同的桶寬a，可以快速地將相似數(shù)據(jù)哈希到同一個桶中。 2.2 基于局部敏感哈希的近鄰傳播算法。（1）初始化桶寬a，最大迭代次數(shù)Max，聚類劃分連續(xù)不變次數(shù)Convits，阻尼系數(shù)，a（i，k）=0，r（i，k）=0。（2）定義哈希函數(shù)族F，對所有相似數(shù)據(jù)哈希到相同桶中，F(xiàn)（v）=|vr+b|÷a。（3）對每個桶mj中的數(shù)據(jù)，計算相似度矩陣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）消除聚類結(jié)果震蕩：rjnew（i，k）=rjold（i，k）+（1-）rjnew（i，k）；ajnew（i，k）=ajold（i，k）+（1-）ajnew（i，k）。（6）對每個桶內(nèi)數(shù)據(jù)重復(fù)執(zhí)行4、5步，直到迭代次數(shù)超過max或聚類連續(xù)Convits不變即停止。（7）輸出每個桶的聚類結(jié)果。

8、3 實驗與結(jié)果分析 實驗環(huán)境是在Matlab 2009b仿真平臺上進行，CPU為2G，主存為1G。實驗數(shù)據(jù)集采用uci數(shù)據(jù)集中的4組，如表1。本實驗主要對比新算法與原近鄰傳播聚類算法的效率與準(zhǔn)確性，準(zhǔn)確性根據(jù)正確聚類數(shù)占所有數(shù)據(jù)比例進行計算。 表1 數(shù)據(jù)集 名稱 類數(shù) 維度 大小 Iris 3 4 150 Wine 3 13 178 Glass 6 9 214 ISTANBUL STOCK EXCHANGE 12 8 536 針對不同的數(shù)據(jù)集，采用不同的桶寬，定義阻尼系數(shù)為0.5，相似度用歐氏距離的相反數(shù)表示，表2為兩種算法在數(shù)據(jù)集上的比較結(jié)果： 表2 實驗結(jié)果 名稱 類數(shù) 原算法類數(shù) 新算法

9、類數(shù) 原算法迭代次數(shù) 新算法迭代次數(shù) 原算法準(zhǔn)確度 新算法準(zhǔn)確度 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 在數(shù)據(jù)集Iris、Wine、Glass中，新算法表現(xiàn)了較高的準(zhǔn)確度，能夠正確聚類，且迭代次數(shù)少于原算法，降低了消耗，提高了效率。在數(shù)據(jù)集ISTANBUL STOCK EXCHANGE中，新算法聚類類數(shù)與原算法出現(xiàn)了差別，原因有可能是對于桶寬的設(shè)定不夠合適，數(shù)據(jù)哈

10、希后的桶的數(shù)據(jù)多于類數(shù)，在今后的研究中應(yīng)該分析如何降低桶中偽正例的概率及桶間數(shù)據(jù)相似性降低。 4 結(jié)束語 本文提出了局部敏感哈希的近鄰傳播聚類算法，根據(jù)局部敏感哈希先將相似數(shù)據(jù)哈希到同一桶中，在對每個桶中的數(shù)據(jù)進行聚類。實驗結(jié)果表明，該算法一定程度上降低了復(fù)雜度，提高了準(zhǔn)確率。今后應(yīng)繼續(xù)對桶寬的設(shè)置、降低桶中偽正例進行研究。 參考文獻： 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.電子與信息學(xué) 報，2010（03）：509-514. 4邢艷，周勇.基于互近鄰一致性的近鄰傳播算法J.計算機應(yīng)用研究，2012（07）：2524-2526. 5王斌譯.大數(shù)據(jù)互聯(lián)網(wǎng)大規(guī)模數(shù)據(jù)挖掘與分布式處理M.北京：人民郵電出版社，2012. 作者簡介：劉淑鑫（1988.12-），女，山東人，碩士研究生，研究方向：數(shù)據(jù)挖掘。 作者單位：東華大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，上海 201620 文檔資料：基于局部敏感哈希的近鄰傳播聚類 完整下載 完整閱讀 全文下載 全文閱讀 免費閱讀及下載閱讀相關(guān)文檔:應(yīng)用改進粒子群算法在云計算任務(wù)調(diào)度中的應(yīng)用及其仿真研究 解析基于激光跟蹤儀標(biāo)定五軸數(shù)控加工中心主軸 單片機電路在防盜報警系統(tǒng)中的應(yīng)用 蟻群遺傳算法對于TSP問題的應(yīng)用 計算機管理信息系統(tǒng)的發(fā)展方向探討 企業(yè)計算機網(wǎng)絡(luò)安全現(xiàn)狀與控制探討 局域網(wǎng)的安全攻防測試與分析 芻議計算機網(wǎng)絡(luò)安全技術(shù)及其發(fā)展趨勢 WOWAFAHP的網(wǎng)絡(luò)安全研究與應(yīng)用 淺談數(shù)字證書在網(wǎng)絡(luò)安全中的應(yīng)用 多媒體通信技術(shù)在如今社會信息高速公路中的應(yīng)用 如何構(gòu)建