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

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

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

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

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

5、，簡(jiǎn)稱LSH）的基本思想是5：對(duì)目標(biāo)項(xiàng)進(jìn)行多次哈希，使得相似項(xiàng)會(huì)比不相似項(xiàng)更可能哈希到同一個(gè)桶中，至少有一次哈希到同一個(gè)桶中的即為候選對(duì)。定義函數(shù)族F，若F中每個(gè)函數(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是一個(gè)隨機(jī)變量，a是桶寬，b是一個(gè)

6、在0，a之間均勻分布的隨機(jī)變量。所以vr是v在向量r上的投影，該函數(shù)族是（a/2，2a，1/2，1/3）-敏感的。即函數(shù)族F將每個(gè)數(shù)據(jù)哈希到的目標(biāo)桶是隨機(jī)直線上長(zhǎng)度為a的線段，在同一線段內(nèi)的數(shù)據(jù)相似性大。 定義一組哈希函數(shù)，設(shè)置不同的桶寬a，可以快速地將相似數(shù)據(jù)哈希到同一個(gè)桶中。 2.2 基于局部敏感哈希的近鄰傳播算法。（1）初始化桶寬a，最大迭代次數(shù)Max，聚類劃分連續(xù)不變次數(shù)Convits，阻尼系數(shù)，a（i，k）=0，r（i，k）=0。（2）定義哈希函數(shù)族F，對(duì)所有相似數(shù)據(jù)哈希到相同桶中，F(xiàn)（v）=|vr+b|÷a。（3）對(duì)每個(gè)桶mj中的數(shù)據(jù)，計(jì)算相似度矩陣Sj（i，k），及對(duì)角

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）對(duì)每個(gè)桶內(nèi)數(shù)據(jù)重復(fù)執(zhí)行4、5步，直到迭代次數(shù)超過max或聚類連續(xù)Convits不變即停止。（7）輸出每個(gè)桶的聚類結(jié)果。

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

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