紀佳琪，鄭永基

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

0 引 言

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

1 背景知識

1.1 KNN連接定義

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

定義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ù)以高概率映射到同一個桶(bucket)中，因此當有新數(shù)據(jù)進行近鄰查找時，只需使用相同的哈希函數(shù)把該數(shù)據(jù)映射到某一桶中，然后和該桶中的數(shù)據(jù)進行計算即可，這樣可以不用遍歷整個數(shù)據(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稱為(r1,r2,P1,P2)-敏感的。

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

2 連接算法

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

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

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

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

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

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

圖1 LSHS-KNN算法整體流程

2.1 minHash簽名

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

算法1：minHash簽名

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

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

(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對簽名矩陣的每一行i=1..n計算sig(i,c)=min(sig(i,c),h(r))

(7) }

(8)}

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

2.2 簽名矩陣映射到桶

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

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

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

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

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

圖2 簽名矩陣哈希到桶

2.3 KNN連接查詢

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

算法2：KNN連接查詢

(1)val R_RDD = textFile(RPath)

(2)R_RDD.map{

(3) 哈希得到桶號bucketNo

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

(5) 返回(rid,list)

(6)}

3 實 驗

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

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

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

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

表1 物理服務器配置

表2 虛擬機配置

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

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

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

3.3 測試與分析

(1)準確率分析

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

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

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

圖3 準確率比較

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

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

隨著數(shù)據(jù)維度的增高，顯然計算量會增大。但是因為本文算法最終的距離計算是和映射到某個桶中的數(shù)據(jù)進行的，因此很大程度地減少了數(shù)據(jù)維度對計算量的影響。該實驗中我們使用3個計算結(jié)點，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)中可以看出，當維度從10上升到1000增長了100倍時，計算時間分別僅增加了約2.627倍、2.825倍、2.699倍，可見維度對計算時間的影響非常小，因此本算法非常適用于高維數(shù)據(jù)的計算。

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

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

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

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

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

4 結(jié)束語

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