基于Spark的高維K近鄰連接算法

紀(jì)佳琪，鄭永基

(1.河北民族師范學(xué)院 信息中心，河北 承德 067000；2.圓光大學(xué) 計(jì)算機(jī)工學(xué)院，韓國(guó) 益山 54538)

0 引 言

K近鄰連接(k nearest neighbor join)，簡(jiǎn)稱(chēng)KNN連接，是一種簡(jiǎn)單有效的惰性數(shù)據(jù)挖掘算法[1]，可廣泛用于相似圖像匹配[2]、相似聲音匹配[3]、相似文本匹配[4]等領(lǐng)域。為了解決KNN連接計(jì)算量過(guò)大問(wèn)題，許多學(xué)者提出了近似KNN連接算法[5,6]。然而，隨著應(yīng)用數(shù)據(jù)量急劇增加、數(shù)據(jù)維度不斷增高，使用單機(jī)運(yùn)算無(wú)法在可以接受的時(shí)間內(nèi)計(jì)算出結(jié)果。為處理大規(guī)模高維度數(shù)據(jù)，使用Hadoop[7]分布式計(jì)算是一種有效的解決方案，因此很多新算法也相繼提出[8-10]。文獻(xiàn)[11]中提出了一種稱(chēng)為H-BNLJ的KNN連接精確算法，該算法的主要思想是首先把數(shù)據(jù)集R和S分別劃分成子集，如R={R1，R2}和S={S1，S2}，然后R中的每一個(gè)子集和S中的每一個(gè)子集結(jié)合形成新集合{R1S1,R1S2,R2S1,R2S2}，最后發(fā)送新集合中的元素至不同的計(jì)算結(jié)點(diǎn)進(jìn)行距離計(jì)算后再進(jìn)行結(jié)果的合并，但該方法會(huì)產(chǎn)生大量的網(wǎng)絡(luò)數(shù)據(jù)傳輸，當(dāng)數(shù)據(jù)量增加或數(shù)據(jù)維度增高時(shí)，性能下降明顯。文獻(xiàn)[12]中詳述了使用LSH基于Hadoop MapReduce實(shí)現(xiàn)的KNN連接近似算法(本文簡(jiǎn)稱(chēng)LSHH-KNNJ)，但是MapReduce是一種批量處理的編程模型，它會(huì)把計(jì)算的中間結(jié)果存儲(chǔ)到本地硬盤(pán)上，當(dāng)需要時(shí)再?gòu)挠脖P(pán)中讀取，這樣它的IO開(kāi)銷(xiāo)很高，因此不適合于對(duì)時(shí)間性能要求較高的應(yīng)用。本文提出了一種基于Spark的使用位置敏感哈希函數(shù)[13]對(duì)數(shù)據(jù)預(yù)先進(jìn)行索引的近似KNN連接算法(我們稱(chēng)為L(zhǎng)SHS-KNNJ算法)，并通過(guò)實(shí)驗(yàn)對(duì)相關(guān)討論進(jìn)行了驗(yàn)證。

1 背景知識(shí)

1.1 KNN連接定義

設(shè)R和S是n維空間上的兩個(gè)數(shù)據(jù)集，對(duì)于任意r∈R和s∈S都是由0和1組成的n維向量。用r[i]和s[i]分別表示數(shù)據(jù)集R和S中的第i個(gè)向量，ri和si分別表示向量r和s的第i維值。設(shè)d(r,s)為向量r和s的杰卡得距離(Jaccard distance)，knn(r,S)為向量r與數(shù)據(jù)集S中最近的k個(gè)向量的集合，knnJoin(R,S)表示對(duì)于每一個(gè)r∈R，返回r與數(shù)據(jù)集S中最近的k個(gè)向量的集合。具體數(shù)學(xué)定義如下：

定義2knn(r,S)={(r,s[i])k|?s[j]∈S,d(r,s[i])

定義3knnJoin(R,S)={(r,s)|?r∈R,?s∈knn(r,S)}。

1.2 位置敏感哈希函數(shù)定義

位置敏感哈希函數(shù)(locality-sensitive hashing，LSH)[14]是為了解決高維空間近似近鄰查找的一種算法，它可以把相似的高維數(shù)據(jù)以高概率映射到同一個(gè)桶(bucket)中，因此當(dāng)有新數(shù)據(jù)進(jìn)行近鄰查找時(shí)，只需使用相同的哈希函數(shù)把該數(shù)據(jù)映射到某一桶中，然后和該桶中的數(shù)據(jù)進(jìn)行計(jì)算即可，這樣可以不用遍歷整個(gè)數(shù)據(jù)集進(jìn)行計(jì)算。LSH定義如下：

定義4 設(shè)距離r2>r1>0,且1>P1>P2>0,Ifd(q,v)≤r1thenPH(h(q)=h(v))≥P1,Ifd(q,v)>r2thenPH(h(q)=h(v))≤P2，向量q,v稱(chēng)為(r1,r2,P1,P2)-敏感的。

其中，q和v是高維空間M中的任意兩個(gè)由0和1組成的高維向量；由定義1知d(q,v)表示q和v的杰卡德距離。H代表若干由某一向量映射到另一向量的哈希函數(shù)，H={h:s→u}；P代表碰撞概率，即映射到同一個(gè)桶的概率。

2 連接算法

本節(jié)我們提出了在Spark上實(shí)現(xiàn)，基于LSH的近似KNN連接算法，我們稱(chēng)為L(zhǎng)SHS KNN連接算法。該算法的主要過(guò)程如下：

(1)對(duì)原始高維數(shù)據(jù)(數(shù)據(jù)集S)標(biāo)準(zhǔn)化，形成由0和1組成的高維向量矩陣Sij。

(2)對(duì)標(biāo)準(zhǔn)化后的高維向量矩陣進(jìn)行minHash簽名，形成簽名矩陣。

(3)對(duì)簽名矩陣再進(jìn)行Hash映射，使相似的向量能夠以高概率映射到同一個(gè)桶中。

(4)對(duì)于數(shù)據(jù)集R中的每一個(gè)向量r，使用相同的Hash函數(shù)映射到某個(gè)桶中，r與該桶中所有向量進(jìn)行距離計(jì)算，并取出距離最近的k個(gè)向量返回。

上述過(guò)程都是通過(guò)Spark RDD在分布式集群中完成。圖1描述了整個(gè)算法的流程，接下來(lái)將介紹一些關(guān)鍵步驟的具體算法和實(shí)現(xiàn)。

圖1 LSHS-KNN算法整體流程

2.1 minHash簽名

由于標(biāo)準(zhǔn)化后的向量仍為高維向量，在進(jìn)行近鄰計(jì)算時(shí)代價(jià)依然很高。為了解決高維向量計(jì)算開(kāi)銷(xiāo)過(guò)大的問(wèn)題，需要找到一種方法，可以在降低其維度的同時(shí)使原有數(shù)據(jù)的特征盡可能地保留下來(lái)，這種方法就是minHash簽名方法，它可以保證原始數(shù)據(jù)的相似度很高經(jīng)過(guò)簽名后的數(shù)據(jù)相似度依然很高，原始數(shù)據(jù)的相似度很低經(jīng)過(guò)簽名后數(shù)據(jù)的相似度也很低。具體算法是先對(duì)矩陣Sij進(jìn)行隨機(jī)行排列，則這次minHash值就是每列第一次出現(xiàn)1的行索引值組成的集合，重復(fù)該過(guò)程n次，即可以得到n個(gè)minHash值，即原數(shù)據(jù)的維度也變?yōu)閚維。由于在具體實(shí)現(xiàn)的時(shí)候?qū)ij進(jìn)行隨機(jī)行排列也是一個(gè)非常耗時(shí)的過(guò)程，所以本文采用隨機(jī)函數(shù)來(lái)模擬Sij進(jìn)行隨機(jī)排列。我們選用的隨機(jī)函數(shù)為h(x)=(ax+b)/d，其中a，b是每次迭代時(shí)隨機(jī)生成的正整數(shù)，x是矩陣的行索引值，d是數(shù)據(jù)的維度。其偽代碼表示如下：

算法1：minHash簽名

(1)初始化簽名矩陣sign×d(n行，d列)，值都為無(wú)窮大。

(2)隨機(jī)生成a與b用于哈希函數(shù)h(x)=(ax+b)/d的計(jì)算

(3)for (r from 0 to矩陣S行數(shù)){

(4) for (c from 0 to矩陣S列數(shù)){

(5) if(S[r,c]==0) continue;

(6) else對(duì)簽名矩陣的每一行i=1..n計(jì)算sig(i,c)=min(sig(i,c),h(r))

(7) }

(8)}

(9)重復(fù)n次步驟(2)到步驟(9)

2.2 簽名矩陣映射到桶

雖然經(jīng)過(guò)簽名后的矩陣達(dá)到了降維目的，但是當(dāng)數(shù)據(jù)量很大的時(shí)候，遍歷所有數(shù)據(jù)查找近鄰依然極其耗時(shí)。為了解決這個(gè)問(wèn)題，我們需要把相似的數(shù)據(jù)映射到同一個(gè)桶中，這樣全部數(shù)據(jù)會(huì)根據(jù)相似度不同被映射到不同的桶中，當(dāng)進(jìn)行近鄰搜索時(shí)，只需和某一桶中的數(shù)據(jù)進(jìn)行計(jì)算機(jī)即可?？梢?jiàn)，如果桶的數(shù)量是n，在數(shù)據(jù)較平均分配到桶的情況下，計(jì)算量只有原來(lái)的1/n。具體算法是：

(1)把簽名矩陣的若干行(具體行數(shù)可以自定義)看成一段，這樣簽名矩陣被分成若干段，每段有若干行。

(2)選取任意一段，對(duì)段中的列進(jìn)行哈希映射(可以使用MD5或SHA等哈希算法)到桶，這樣段中相同的列就會(huì)被映射到同一個(gè)桶中，這時(shí)段所在的列我們就認(rèn)為是高概率相似的。

圖2展示了簽名矩陣哈希到桶的整個(gè)過(guò)程。接下來(lái)我們證明為什么經(jīng)過(guò)該哈希過(guò)程到同一桶中后的數(shù)據(jù)是高概率相似的。假設(shè)該簽名矩陣是n行m列的(由于1列代表一條數(shù)據(jù)，因此實(shí)際情況列數(shù)會(huì)很多，即列數(shù)等于數(shù)據(jù)條數(shù)；行數(shù)則是數(shù)據(jù)的維度，因此實(shí)際數(shù)值的量級(jí)在10到102)，每段的行數(shù)為r，顯然共有n/r段(在選取r數(shù)值時(shí)要保證n/r是整數(shù))。假設(shè)C1列和C2列的相似度是s，則C1和C2中存在某個(gè)段相同的概率是(s)r，C1和C2在所有段都不相同的概率為(1-sr)n/r，那么C1和C2一定存在某一個(gè)段相同的概率是1-(1-sr)n/r。假設(shè)此時(shí)r=5，n=100，C1和C2相似度為s=0.9的時(shí)候，經(jīng)上面的公式計(jì)算可得C1和C2一定存在某一個(gè)段相同的概率為0.999 999 982。

可見(jiàn)如果原數(shù)據(jù)高相似，經(jīng)過(guò)哈希到桶的操作后，原相似數(shù)據(jù)有0.999 999 982的概率會(huì)被映射到同一個(gè)桶中。同理如果當(dāng)C1和C2的相似度s=0.3的時(shí)候，經(jīng)計(jì)算C1和C2一定存在某一個(gè)段相同的概率僅為0.0474，即原數(shù)據(jù)相似度低，則映射到同一個(gè)桶的概率也會(huì)極低。

圖2 簽名矩陣哈希到桶

2.3 KNN連接查詢(xún)

經(jīng)過(guò)上面的步驟，相當(dāng)于已經(jīng)對(duì)數(shù)據(jù)集S進(jìn)行了索引(分桶)，這時(shí)只需讀取R到RDD，然后依次取出R中的元素并按上面的方法哈希后得到桶號(hào)，然后和該桶中的所有數(shù)據(jù)進(jìn)行距離計(jì)算取出距離最近的k個(gè)值返回即可。算法的偽代碼如下：

算法2：KNN連接查詢(xún)

(1)val R_RDD = textFile(RPath)

(2)R_RDD.map{

(3) 哈希得到桶號(hào)bucketNo

(4) 與bucketNo桶中所有數(shù)據(jù)計(jì)算距離

(5) 返回(rid,list)

(6)}

3 實(shí) 驗(yàn)

為了驗(yàn)證算法的正確性、性能以及不同參數(shù)對(duì)運(yùn)算時(shí)間的影響，我們?cè)诩荷线M(jìn)行了相關(guān)測(cè)試。

3.1 軟硬件環(huán)境配置

在物理服務(wù)器上安裝了VMWare，并在VMWare中安裝7臺(tái)虛擬機(jī)，每臺(tái)虛擬機(jī)的配置都相同，其中1臺(tái)作為主結(jié)點(diǎn)(Master)，其它6臺(tái)作為從結(jié)點(diǎn)(Slaves)，其物理服務(wù)器和虛擬機(jī)的詳細(xì)配置見(jiàn)表1和表2。

每臺(tái)虛擬機(jī)安裝centos 7操作系統(tǒng)，Java1.8 64-bit，Hadoop 2.7.3和Spark 2.0。因?yàn)閱闻_(tái)虛擬機(jī)最大核數(shù)是4核，所以當(dāng)使用n臺(tái)虛擬機(jī)時(shí)(本實(shí)驗(yàn)n≤8),我們?cè)O(shè)置的最大分區(qū)數(shù)應(yīng)該是4n，即使超過(guò)這個(gè)值，也不會(huì)增大加速比，甚至?xí)驗(yàn)檎{(diào)度問(wèn)題反而性能下降。

表1 物理服務(wù)器配置

表2 虛擬機(jī)配置

3.2 數(shù)據(jù)集

實(shí)驗(yàn)使用了3個(gè)真實(shí)的數(shù)據(jù)集：①CNAE-9 Data Set：這是一個(gè)用于文本處理的已經(jīng)經(jīng)過(guò)預(yù)處理的由0和1組成的數(shù)據(jù)集，有857個(gè)維度和1080條記錄；②Farm Ads Data Set：是一個(gè)從12個(gè)網(wǎng)址收集的有關(guān)農(nóng)場(chǎng)動(dòng)物文本，標(biāo)簽表示該文本是否為廣告，有54 877個(gè)維度和4143條記錄；③Semeion Handwritten Digit Data Set：由80個(gè)人手寫(xiě)0-9數(shù)字，經(jīng)過(guò)處理后生成16*16共256個(gè)值的矩陣(即維度是256)，共1593條記錄。

部分測(cè)試，我們使用由Java程序生成的不同維度不同大小符合我們數(shù)據(jù)輸入標(biāo)準(zhǔn)的數(shù)據(jù)。與真實(shí)數(shù)據(jù)集比較，在測(cè)試算法的準(zhǔn)確率時(shí)必須使用真實(shí)數(shù)據(jù)集，但是其它測(cè)試我們使用程序生成的數(shù)據(jù)集能夠更加方便地進(jìn)行測(cè)試且不會(huì)影響測(cè)試結(jié)果。

3.3 測(cè)試與分析

(1)準(zhǔn)確率分析

該實(shí)驗(yàn)中我們不僅在3個(gè)真實(shí)數(shù)據(jù)集上測(cè)試LSHS-KNNJ準(zhǔn)確率，而且還與單機(jī)精確實(shí)現(xiàn)KNN連接(本文簡(jiǎn)稱(chēng)Single-KNNJ)算法的準(zhǔn)確率進(jìn)行了比較(雖然精確實(shí)現(xiàn)KNN連接算法的效率最低，但是其準(zhǔn)確率是最高的)。

LSHS-KNNJ中影響準(zhǔn)確率的主要因素是桶的數(shù)量，從理論上分析，當(dāng)桶的數(shù)量為1的時(shí)候，準(zhǔn)確率最高，因?yàn)檫@等價(jià)于所有數(shù)據(jù)都映射到了同一個(gè)桶中，顯然此時(shí)計(jì)算量也最大，相當(dāng)于和所有降維后的數(shù)據(jù)進(jìn)行計(jì)算。除此以外k值也會(huì)影響準(zhǔn)確率，但是對(duì)于不同數(shù)據(jù)，不同應(yīng)用需要不斷調(diào)試來(lái)得到一個(gè)比較合理的k值，本實(shí)驗(yàn)中把k值固定為5。我們隨機(jī)抽取數(shù)據(jù)集中10%的數(shù)據(jù)用作測(cè)試數(shù)據(jù)，其余用作訓(xùn)練數(shù)據(jù)，用P代表準(zhǔn)確率，T代表測(cè)試集標(biāo)簽類(lèi)型集合，Pr代表經(jīng)KNN連接計(jì)算后的預(yù)測(cè)類(lèi)型集合，則

圖3(a)顯示了在3個(gè)不同的真實(shí)數(shù)據(jù)集上的測(cè)試結(jié)果，結(jié)果表明無(wú)論哪個(gè)數(shù)據(jù)集都是當(dāng)桶數(shù)為1的時(shí)候準(zhǔn)確率最高，隨著桶數(shù)的增加準(zhǔn)確率略有下降，但仍然保持著比較高的準(zhǔn)確率。

圖3 準(zhǔn)確率比較

圖3(b)顯示LSHS-KNNJ和Single-KNNJ在3個(gè)不同的真實(shí)數(shù)據(jù)集上準(zhǔn)確率平均值的比較。從圖中可以看出LSHS-KNNJ的準(zhǔn)確率比Single-KNNJ略低，但差距不大。

(2)數(shù)據(jù)維度的影響

隨著數(shù)據(jù)維度的增高，顯然計(jì)算量會(huì)增大。但是因?yàn)楸疚乃惴ㄗ罱K的距離計(jì)算是和映射到某個(gè)桶中的數(shù)據(jù)進(jìn)行的，因此很大程度地減少了數(shù)據(jù)維度對(duì)計(jì)算量的影響。該實(shí)驗(yàn)中我們使用3個(gè)計(jì)算結(jié)點(diǎn)，k值為3，使用程序生成數(shù)據(jù)集S和R，S集的大小固定為105，R集的大小分別取105、2*105、和4*105，數(shù)據(jù)維度取值為{10,50,100,200,500,800,1000}。從圖4(a)中可以看出，當(dāng)維度從10上升到1000增長(zhǎng)了100倍時(shí)，計(jì)算時(shí)間分別僅增加了約2.627倍、2.825倍、2.699倍，可見(jiàn)維度對(duì)計(jì)算時(shí)間的影響非常小，因此本算法非常適用于高維數(shù)據(jù)的計(jì)算。

圖4 不同數(shù)據(jù)量和維度對(duì)算法時(shí)間影響

同時(shí)，我們還與另外3個(gè)有代表性的算法進(jìn)行了比較：Single-KNNJ方法，本文引言介紹的H-BNLJ方法和LSHH-KNNJ方法；從圖4(b)中可以看出無(wú)論Single-KNNJ還是H-BNLJ，當(dāng)維度增加時(shí)計(jì)算時(shí)間都急劇增長(zhǎng)，無(wú)法適用于高維數(shù)據(jù)；LSHH-KNNJ雖然能夠比較好地適應(yīng)維度的增長(zhǎng)，但計(jì)算時(shí)間比本文提出的LSHS-KNNJ算法約慢2倍，這主要因?yàn)楸疚奶岢龅乃惴ǔ浞掷昧薙park的高性能內(nèi)存計(jì)算能力。

(3)數(shù)據(jù)量和結(jié)點(diǎn)數(shù)影響

隨著數(shù)據(jù)量的增加，計(jì)算量因此增高，計(jì)算時(shí)間會(huì)增長(zhǎng)；隨著結(jié)點(diǎn)數(shù)的增加，計(jì)算時(shí)間會(huì)減少。為了更清晰地分析數(shù)據(jù)量和結(jié)點(diǎn)數(shù)對(duì)計(jì)算時(shí)間產(chǎn)生的影響，我們進(jìn)行了如下實(shí)驗(yàn)。先保持其中一個(gè)數(shù)據(jù)集大小不變，另一個(gè)數(shù)據(jù)集大小從0.5*105到8*105變化，數(shù)據(jù)維度都為200，k=3，分別在2到8個(gè)結(jié)點(diǎn)上進(jìn)行計(jì)算。從圖5(a)中我們可以看出：①隨著數(shù)據(jù)集R大小的倍數(shù)增長(zhǎng)，計(jì)算時(shí)間增長(zhǎng)的倍數(shù)約等于數(shù)據(jù)集R增長(zhǎng)的倍數(shù)。顯然這是因?yàn)槿绻鸕增長(zhǎng)了m倍，計(jì)算量也會(huì)增長(zhǎng)m倍，因此計(jì)算時(shí)間也會(huì)增長(zhǎng)m倍；②隨著結(jié)點(diǎn)數(shù)的增加，計(jì)算時(shí)間不斷減小。結(jié)點(diǎn)數(shù)增加為原來(lái)的2倍，計(jì)算時(shí)間的減小始終小于2倍，這主要因?yàn)橛?jì)算結(jié)點(diǎn)的增加會(huì)增加一部分的通信和調(diào)度的開(kāi)銷(xiāo)。從圖5(b)中可以看出隨著數(shù)據(jù)集S的倍數(shù)增長(zhǎng)，計(jì)算時(shí)間增長(zhǎng)的倍數(shù)遠(yuǎn)小于數(shù)據(jù)集S增長(zhǎng)的倍數(shù)，這主要是因?yàn)槲覀儗?duì)數(shù)據(jù)集S建立了索引，增加的數(shù)據(jù)按照相似度被哈希到了不同的桶中，所以實(shí)際計(jì)算量的增幅很大程度上的減少了，這也是該算法能適應(yīng)大數(shù)據(jù)的一個(gè)主要原因。

圖5 不同數(shù)據(jù)量不同結(jié)點(diǎn)數(shù)算法運(yùn)行時(shí)間

4 結(jié)束語(yǔ)

本文詳細(xì)介紹了基于Spark的使用位置敏感哈希函數(shù)的近似KNN連接算法。無(wú)論從理論分析還是實(shí)驗(yàn)結(jié)果來(lái)看該算法對(duì)高維大數(shù)據(jù)的處理是準(zhǔn)確的、高效的,尤其是維度的變化對(duì)計(jì)算時(shí)間的影響較小使得該算法非常適用于超高維數(shù)據(jù)的場(chǎng)景。下一步我們將繼續(xù)研究基于Spark的使用KD-Tree的近似KNN連接算法，并比較兩者之間的性能差異。