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

紀佳琪，鄭永基

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

0 引 言

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

1 背景知識

1.1 KNN連接定義

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

定義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 位置敏感哈希函數定義

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

定義4 設距離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稱為(r1,r2,P1,P2)-敏感的。

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

2 連接算法

本節我們提出了在Spark上實現，基于LSH的近似KNN連接算法，我們稱為LSHS KNN連接算法。該算法的主要過程如下：

(1)對原始高維數據(數據集S)標準化，形成由0和1組成的高維向量矩陣Sij。

(2)對標準化后的高維向量矩陣進行minHash簽名，形成簽名矩陣。

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

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

上述過程都是通過Spark RDD在分布式集群中完成。圖1描述了整個算法的流程，接下來將介紹一些關鍵步驟的具體算法和實現。

圖1 LSHS-KNN算法整體流程

2.1 minHash簽名

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

算法1：minHash簽名

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

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

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

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

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

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

(7) }

(8)}

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

2.2 簽名矩陣映射到桶

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

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

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

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

可見如果原數據高相似，經過哈希到桶的操作后，原相似數據有0.999 999 982的概率會被映射到同一個桶中。同理如果當C1和C2的相似度s=0.3的時候，經計算C1和C2一定存在某一個段相同的概率僅為0.0474，即原數據相似度低，則映射到同一個桶的概率也會極低。

圖2 簽名矩陣哈希到桶

2.3 KNN連接查詢

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

算法2：KNN連接查詢

(1)val R_RDD = textFile(RPath)

(2)R_RDD.map{

(3) 哈希得到桶號bucketNo

(4) 與bucketNo桶中所有數據計算距離

(5) 返回(rid,list)

(6)}

3 實 驗

為了驗證算法的正確性、性能以及不同參數對運算時間的影響，我們在集群上進行了相關測試。

3.1 軟硬件環境配置

在物理服務器上安裝了VMWare，并在VMWare中安裝7臺虛擬機，每臺虛擬機的配置都相同，其中1臺作為主結點(Master)，其它6臺作為從結點(Slaves)，其物理服務器和虛擬機的詳細配置見表1和表2。

每臺虛擬機安裝centos 7操作系統，Java1.8 64-bit，Hadoop 2.7.3和Spark 2.0。因為單臺虛擬機最大核數是4核，所以當使用n臺虛擬機時(本實驗n≤8),我們設置的最大分區數應該是4n，即使超過這個值，也不會增大加速比，甚至會因為調度問題反而性能下降。

表1 物理服務器配置

表2 虛擬機配置

3.2 數據集

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

部分測試，我們使用由Java程序生成的不同維度不同大小符合我們數據輸入標準的數據。與真實數據集比較，在測試算法的準確率時必須使用真實數據集，但是其它測試我們使用程序生成的數據集能夠更加方便地進行測試且不會影響測試結果。

3.3 測試與分析

(1)準確率分析

該實驗中我們不僅在3個真實數據集上測試LSHS-KNNJ準確率，而且還與單機精確實現KNN連接(本文簡稱Single-KNNJ)算法的準確率進行了比較(雖然精確實現KNN連接算法的效率最低，但是其準確率是最高的)。

LSHS-KNNJ中影響準確率的主要因素是桶的數量，從理論上分析，當桶的數量為1的時候，準確率最高，因為這等價于所有數據都映射到了同一個桶中，顯然此時計算量也最大，相當于和所有降維后的數據進行計算。除此以外k值也會影響準確率，但是對于不同數據，不同應用需要不斷調試來得到一個比較合理的k值，本實驗中把k值固定為5。我們隨機抽取數據集中10%的數據用作測試數據，其余用作訓練數據，用P代表準確率，T代表測試集標簽類型集合，Pr代表經KNN連接計算后的預測類型集合，則

圖3(a)顯示了在3個不同的真實數據集上的測試結果，結果表明無論哪個數據集都是當桶數為1的時候準確率最高，隨著桶數的增加準確率略有下降，但仍然保持著比較高的準確率。

圖3 準確率比較

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

(2)數據維度的影響

隨著數據維度的增高，顯然計算量會增大。但是因為本文算法最終的距離計算是和映射到某個桶中的數據進行的，因此很大程度地減少了數據維度對計算量的影響。該實驗中我們使用3個計算結點，k值為3，使用程序生成數據集S和R，S集的大小固定為105，R集的大小分別取105、2*105、和4*105，數據維度取值為{10,50,100,200,500,800,1000}。從圖4(a)中可以看出，當維度從10上升到1000增長了100倍時，計算時間分別僅增加了約2.627倍、2.825倍、2.699倍，可見維度對計算時間的影響非常小，因此本算法非常適用于高維數據的計算。

圖4 不同數據量和維度對算法時間影響

同時，我們還與另外3個有代表性的算法進行了比較：Single-KNNJ方法，本文引言介紹的H-BNLJ方法和LSHH-KNNJ方法；從圖4(b)中可以看出無論Single-KNNJ還是H-BNLJ，當維度增加時計算時間都急劇增長，無法適用于高維數據；LSHH-KNNJ雖然能夠比較好地適應維度的增長，但計算時間比本文提出的LSHS-KNNJ算法約慢2倍，這主要因為本文提出的算法充分利用了Spark的高性能內存計算能力。

(3)數據量和結點數影響

隨著數據量的增加，計算量因此增高，計算時間會增長；隨著結點數的增加，計算時間會減少。為了更清晰地分析數據量和結點數對計算時間產生的影響，我們進行了如下實驗。先保持其中一個數據集大小不變，另一個數據集大小從0.5*105到8*105變化，數據維度都為200，k=3，分別在2到8個結點上進行計算。從圖5(a)中我們可以看出：①隨著數據集R大小的倍數增長，計算時間增長的倍數約等于數據集R增長的倍數。顯然這是因為如果R增長了m倍，計算量也會增長m倍，因此計算時間也會增長m倍；②隨著結點數的增加，計算時間不斷減小。結點數增加為原來的2倍，計算時間的減小始終小于2倍，這主要因為計算結點的增加會增加一部分的通信和調度的開銷。從圖5(b)中可以看出隨著數據集S的倍數增長，計算時間增長的倍數遠小于數據集S增長的倍數，這主要是因為我們對數據集S建立了索引，增加的數據按照相似度被哈希到了不同的桶中，所以實際計算量的增幅很大程度上的減少了，這也是該算法能適應大數據的一個主要原因。

圖5 不同數據量不同結點數算法運行時間

4 結束語

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