摘 要：本文針對(duì)近鄰傳播聚類中存在的復(fù)雜度高問題，提出了局部敏感哈希的近鄰傳播聚類算法，根據(jù)局部敏感哈希先將相似數(shù)據(jù)哈希到同一桶中，在對(duì)每個(gè)桶中的數(shù)據(jù)進(jìn)行聚類。實(shí)驗(yàn)結(jié)果表明，該算法降低了復(fù)雜度，提高了準(zhǔn)確率。

關(guān)鍵詞：近鄰傳播聚類；局部敏感哈希；相似性

中圖分類號(hào)：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)處理量小、面對(duì)大量的數(shù)據(jù)時(shí)處理時(shí)間較長、難以達(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)之間的相似度進(jìn)行聚類，這些相似度可以是對(duì)稱的，也可以是不對(duì)稱的。這些相似度組成N×N的相似度矩陣S。任意兩個(gè)數(shù)據(jù)點(diǎn)xi和xj之間的相似度S（i，j）=-‖xi-xj‖2被存儲(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ā)送到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，簡(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

在近鄰傳播聚類中相似度矩陣采用歐式距離，則D維空間中面向歐式空間的LSH函數(shù)族為：F（v）=|vr+b|÷a。其中r是一個(gè)隨機(jī)變量，a是桶寬，b是一個(gè)在[0，a]之間均勻分布的隨機(jī)變量。所以vr是v在向量r上的投影，該函數(shù)族是（a/2，2a，1/2，1/3）-敏感的。即函數(shù)族F將每個(gè)數(shù)據(jù)哈希到的目標(biāo)桶是隨機(jī)直線上長度為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ì)角線元素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）消除聚類結(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é)果。

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ù)維度大小

Iris34150

Wine313178

Glass69214

ISTANBUL STOCK EXCHANGE 128536

針對(duì)不同的數(shù)據(jù)集，采用不同的桶寬，定義阻尼系數(shù)為0.5，相似度用歐氏距離的相反數(shù)表示，表2為兩種算法在數(shù)據(jù)集上的比較結(jié)果：

表2 實(shí)驗(yàn)結(jié)果

名稱類數(shù)原算法類數(shù)新算法類數(shù)原算法迭代次數(shù)新算法迭代次數(shù)原算法準(zhǔn)確度新算法準(zhǔn)確度

Iris33389800.950.95

Wine333104960.860.87

Glass6661261020.760.79

ISTANBUL STOCK EXCHANGE 1212132131780.670.65

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

[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].電子與信息學(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