基于維度分組降維的高維數據近似k近鄰查詢

李 松 胡晏銘 郝曉紅 張麗平 郝忠孝

(哈爾濱理工大學計算機科學與技術學院 哈爾濱 150080)

(lisongbeifen@163.com)

隨著計算機技術以及傳感器技術的不斷發展，基于位置的服務得到了廣泛的應用，其中最近鄰查詢作為基于位置服務中重要的支持性技術之一,在許多領域都有廣泛的應用.目前國內外學者針對最近鄰查詢問題進行了廣泛研究，為了更好地解決現實問題，學者們提出了一系列的變形，例如概率最近鄰查詢[1]、反向最近鄰查詢[2]、連續最近鄰查詢[3]、組最近鄰查詢[4]、強鄰近對查詢[5]、k近鄰(knearest neighbor，kNN)查詢[6-7]、反向k近鄰查詢[8]等，其中k近鄰查詢問題一直吸引學者們的目光.

kNN查詢問題作為最近鄰查詢問題的擴展形式，在現實生活中具有廣泛的應用.例如送餐員在接單時會選擇距離他最近的k個訂單；外出旅行時游客通過手機地圖查找最近的k個酒店；新聞網站通過分析與某用戶最相似的k個用戶的瀏覽歷史為該客戶進行新聞推薦等.kNN查詢技術除了被應用在現實生活中，也被廣泛應用到了科研等領域，然而與多數現實生活中處理的低維數據相反，科研領域要處理的數據多為高維數據.例如天文學中，在宇宙環境中查找與地球最相似的k個星球，不僅要考慮大小、溫度，還需要考慮自轉速度、大氣組成成分等眾多維度數據；在計算機的模式識別領域對圖像進行基于kNN分類時，需要處理的圖像數據的維度可高達成千上萬維.由于數據維度的增長，低維空間中的kNN查詢算法的效率隨之下降，甚至不如線性掃描，因此學者們提出了近似k近鄰(approximateknearest neighbor， AkNN)查詢，通過損失一定的精度來提升查詢效率，并給出一系列算法.

雖然現有的方法能夠解決AkNN查詢問題，但是在進行查詢的過程中大多不考慮數據維度間的關聯關系，對數據的所有維度進行統一的分析計算，影響了查詢的準確率和效率.以基于局部敏感哈希(locality sensitive hashing, LSH)的算法為例，應用m個Hash函數對大小為n的d維數據集進行索引時，計算數據集的索引值的時間復雜度為O(dnm)，可以看出其時間復雜度與維度成正相關.因此，為了提高查詢的效率，本文提出了一種基于維度間的關聯關系進行維度分組并降維的AkNN查詢的算法.

本文主要貢獻有3個方面：

1) 針對已有的高維數據近似k近鄰查詢算法不考慮數據維度值分布情況，面對0值維度個數遠大于非0值維度個數的數據空間、查詢效率降低、運算性能浪費等問題，提出了一種基于維度間關聯規則進行分組降維的思想，并設計了基于LSH的維度分組降維算法，降低了維度值分布對查詢的影響，提高了運算性能.

2) 針對基于維度間關聯規則的維度分組降維過程中維度間關聯規則挖掘效率低、挖掘關聯的頻繁維度耗時高的問題，本文基于單向頻繁模式樹提出了一個新的頻繁項集挖掘算法，通過該算法能快速挖掘出頻繁維度，實現維度間的關聯規則高效挖掘，為高維數據的維度分組降維提供支持.

3) 針對傳統的LSH編碼方式查詢高維數據近似k近鄰存在漢明距離準確率低、Hash函數內存消耗大等問題，本文提出了基于信息熵對編碼函數進行篩選和動態權重賦值，并通過加權漢明距離返回結果集的高維數據近似k近鄰查詢算法，提高了查詢性能和效率.

1 相關工作

在低維空間下，針對kNN查詢問題，研究者們提出一系列的查詢方法.文獻[9]針對大數據下查找k近鄰效率低的問題，提出了一種基于最優三角不等式檢測策略的精確k近鄰快速搜索方法.在低維障礙空間中，文獻[10]基于Voronoi圖提出了解決障礙空間組反k近鄰查詢算法OGRkNN，利用Voronoi圖的特性，過濾掉大量的非候選數據，有效地解決了靜態障礙物環境和動態障礙物環境下的組反k近鄰問題.針對障礙空間下連續反向k近鄰查詢問題，文獻[11]根據數據點到查詢區間的最大距離和數據點到障礙物的最小外包矩形的最小距離的關系對障礙物進行剪枝，同時應用R-tree對保留的障礙物進行索引，最后進行精煉和數據更新，得到最終結果.在低維路網環境中，文獻[12]提出了一個平衡的搜索樹索引結構G-tree，基于該索引結構解決了路網環境下的k近鄰查詢問題.文獻[13]對時變路網環境下的k近鄰查詢問題進行了研究，提出了基于Voronoi圖的二級索引樹結構——V-tree，該文獻根據時間找出了邊界點作為Voronoi圖的邊，然后結合G-tree對Voronoi區進行索引，通過遍歷樹結構得到最終結果.

以上研究主要是處理低維空間環境下的k近鄰查詢問題及其變種，但隨著維度的增長，算法查詢效率隨之下降.以R-tree索引結構為例，當數據維度大于20時，查詢效率不如線性掃描，因此如何高效高質量地解決高維空間近似k近鄰查詢問題是目前研究的重點.

文獻[14]為每個維度分配1個素數作為底數，每個維度上的值作為指數進行計算，并通過取對數的方式避免維度增長導致計算結果過大的缺陷，最終通過將計算結果求和的方式將高維數據降維到1維.針對高維大數據環境下絕大多數索引結構規模較大、內存不足以存儲的問題，文獻[15]基于Hilbert空間填充曲線和B+-tree設計了新的數據結構RDB-tree(reference distance B+-tree)，同時基于RDB-tree提出了HD-index(high dimensional-index)，基于該索引能夠以較高的時空效率和準確率進行AkNN查詢，但是存在空間填充曲線的并行通信的控制較為復雜、實現難度大的問題.文獻[16]提出了基于RP-forests(random projection forests)進行k近鄰查詢的算法，該算法不僅適用于低維空間，還適用于高維空間，但是RP-tree(random projection-tree)的分裂次數和劃分左右節點的閾值難以選擇，多個RP-tree也會占用大量的空間.針對動態的大規模的二進制數據集，文獻[17]提出了HWT(Hanmming weight trees)索引結構，該索引利用二進制碼及其子串的漢明權值來劃分二進制字符串的特征空間，進而基于HWT進行AkNN查詢.針對算法參數固定導致查詢的高延遲問題，文獻[18]通過建立和訓練梯度增強決策樹模型來學習和預測何時停止查詢，使算法在保持高精確度的前提下降低延遲，但是針對不同的數據集需要重復學習.文獻[19]提出了基于HNSW(hierarchical navigable small world)索引結構的AkNN查詢算法，該算法完全基于圖，從而避免了近鄰圖的粗搜索階段所需的額外的搜索結構，同時使用啟發式來選擇近鄰圖的鄰居以使提高查詢性能.

針對以上算法實現難度大和結構復雜的問題，Piotr Indyk提出的LSH被廣泛應用于高維空間下近似k近鄰查詢問題.針對原始LSH根據數據集直接劃分Hash桶導致查詢準確率低的問題，文獻[20]采用基于查詢點的Hash值為基準進行桶的劃分的方法，減小了與查詢點相鄰的數據點被劃分到相鄰桶的概率，提高了查詢結果的準確率.文獻[21]結合了基于漢明距離檢索方法速度快的優勢和基于查找表檢索方法的結果準確的優勢，提出了KMH(kmeans hashing)算法，該算法不僅提高了查詢的準確率，同時也提高了查詢速度.針對現有的通過機器學習的方式獲得Hash函數的算法的相似指標過于粗糙的問題，文獻[22]提出了一種新的細粒度相似度指標量化距離，提供了項之間相似度的更多信息，并提出基于該量化距離的查詢算法，查詢性能得到明顯提升.文獻[23]提出了沖突計數算法結構，應用歐氏空間中常用的基于2-范數的局部敏感Hash函數進行索引，算法能夠很好地處理大數據環境下的高維空間近似k近鄰查詢.針對IO性能瓶頸的問題，文獻[24]提出的O2LSH(optimal order LSH)算法將空間填充曲線作為復合Hash鍵值并建立線序排序，使鄰近候選點更多地分布在相同或相鄰的磁盤，進而提高IO性能和準確率，但是也面臨著填充曲線難以實現的問題.文獻[25]在索引階段將數據對象映射到多個2維投影空間，并在每個2維空間構造一組B+-tree進行索引，有效地降低了IO開銷.針對LSH無法為候選點提供準確的距離估計，導致在檢查不必要的點時產生額外的計算開銷從而降低了查詢處理性能的問題，文獻[26]提出的PMLSH(pivotiny M-tree LSH)查詢框架通過建立可調的置信區間實現精確的距離估計，實現對候選集的縮減，降低了額外的計算開銷.

目前現有的高維數據近似最近鄰查詢算法都是預先將原始數據集進行處理，然后建立索引結構，根據索引進行AkNN查詢.對原始高維數據的預處理過程中，大多不考慮維度間的關聯關系對查詢效率和準確率的影響.因此，本文提出了基于維度間的關聯規則進行維度分組的高維數據降維方法，應用該方法對高維數據進行預處理后，采用二進制編碼的方式進行查詢，同時基于信息熵篩選編碼函數、權重的動態設定等方式優化查詢方法.

2 主要定義

定義1.頻繁序列.設temp1

在頻繁項集挖掘的過程中,通過UFP-tree[27]找出所有的頻繁序列就可得到所有的頻繁項集，本文中如不特殊聲明，頻繁項集和頻繁序列等價.

定義2.近似k近鄰.設d維數據集X={x1,x2,…,xm}，其中xi∈Rd，X經過降維和編碼后得到數據集X′，對于給定查詢點q∈Rd，經過相同的降維方式和編碼后為q′，近似k近鄰查詢AkNN(q)返回1個數據集合P={p1,p2,…,pk}，其中pi∈X′，數據集合P中的數據滿足的條件為

定義3.局部敏感Hash函數[28].給定距離r和近似比率c，若一個Hash函數族H={h:Rd→Rd′}對給定的任意2個數據q，p滿足2個條件：

1) 若dist(q,p)≤r，則Pr[h(q)=h(p)]≥P1；

2) 若dist(q,p)≥cr，則Pr[h(q)=h(p)]≤P2；

則稱H是(r,cr,P1,P2)-敏感的，其中c>1，P1>P2，P1和P2是概率.

定義4.信息熵[29].信息熵是一種用于度量系統不確定性的度量方法，其香農計算公式為

(1)

其中,E(x)表示的是隨機變量x的熵，x∈{a1,a2,…,an}，p(ai)表示取值為ai的概率.

3 高維數據近似k近鄰查詢

在高維數據中，由于維度的激增，對查詢時效影響越來越大.本文通過算法1和算法2首先對數據維度之間的關聯規則進行挖掘，并通過算法3對前件具有交集的強正相關的維度集進行分組；進一步根據每組的維度分配Hash函數，算法4將數據維度按組進行Hash降維；最后將降維后得到的數據應用候選的局部敏感Hash函數進行編碼，算法5根據編碼后的各Hash函數的熵值篩選得到編碼函數和數據的編碼結果.進行查詢時，將查詢點按相同的方式進行維度分組降維，并用相同的編碼函數進行編碼，然后根據編碼后的漢明距離返回候選集，計算候選集中各編碼位的熵值并根據熵值進行動態加權，最終算法6返回加權漢明距離最小的k個數據作為結果.整個過程可以分為基于維度分組的Hash降維、基于Hash編碼的動態加權近似k近鄰查詢2個部分.

3.1 基于維度分組的Hash降維

3.1.1 基于維度間關聯規則的維度分組

本節基于UFP-tree提出了新的頻繁項集挖掘算法MFIA_UFP_tree和維度分組算法Group_PAR.算法MFIA_UFP_tree通過邏輯“與”運算高效地挖掘出所有的頻繁項集.算法Group_PAR基于相關系數對得到的頻繁項集進行正相關關聯規則(positive association rule, PAR)挖掘，進一步根據不同關聯規則的前件是否有交集進行維度的分組.為了支持算法MFIA_UFP_tree和提高頻繁項集挖掘效率，本節給出結構體Struct_info定義.

定義5.結構體Struct_info.

Struct_info{

seq;*項轉換后的序號*

count;*頻繁度計數*

r_code;*包含序號seq的路徑編碼*

}，

其中路徑編碼根據起始節點的位置來定，本文采用從0開始，從左到右依次加1的方式進行編碼.

在進行基于支持度和置信度[30]的頻繁項集挖掘時，首先對給定d維數據集Q={q|q∈Rd}進行二值化，對應維度有值的用“1”標記，沒有值的用“0”標記，得到二值化后的數據集Q′；然后掃描二值化后的數據集Q′，去除支持度小于給定閥值的維度，對剩余維度建立序號-項集轉換表，并構建UFP-tree.針對頻繁項集挖掘過程中統計支持度和項集剪枝的資源消耗問題，本文根據結構體的定義，進一步給出結構體數組的定義.

定義6.結構體數組S[].給定一個UFP-tree，設結構體數組S[]，當且僅當其滿足的條件為：

1) 對于任意以序號i為起點、根節點為終點的路徑，其序號集為Seq={seq1,seq2,…,seql},其中l為數組S[]的長度；

2)S[j].count的值為S[j].seq對應的節點在從i到根節點的路徑上的頻繁度計數和；

3)S[j].r_code的編碼位數為從i到根節點所有路徑的個數；

4)S[j].r_code的每位編碼上的值為S[j].seq對應節點在該路徑上的頻繁度計數；

稱S[]為序號i對應的結構體數組.

為保證所有的頻繁序列都能根據序號對應的結構體數組挖掘得到，本文根據結構數組和UFP-tree給出定理1.

定理1.給定UFP-tree，設序列FSeq={seq1,seq2,…,seqi}，若FSeq是頻繁序列，則序列FSeq一定屬于序號seqi對應的結構體數組S[].

證明. 定理1可以通過反證法進行證明.假設以序號seqi為結尾的頻繁序列FSeq不屬于seqi對應的結構體數組S[]，由UFP-tree的結構可知，任意以seqi為結尾的頻繁序列一定屬于以序號seqi對應的節點為起點、根節點為終點的1條或多條路徑，根據結構體數組的定義可知，任意1條從序號seqi對應的節點到根節點的路徑都是序號seqi對應的結構體數組的子集，所以序列FSeq也屬于序號seqi對應的結構體數組，與假設矛盾.

證畢.

在進行基于UFP-tree頻繁項集挖掘時，根據結構體數組S[]來進行以序號i為終止端點的頻繁序列挖掘，進而得到對應的頻繁項集.因此根據結構數組S[]，進一步給出定理2～4.

定理2.在序號i對應的結構體數組S[]中，若S[t].count小于最小支持度計數countmin，則以序號i為終止端點的所有頻繁序列一定不包含序號S[t].seq.

證明. 以反證法進行證明.假設S[t].count

證畢.

推論1.若有序序列{temp1,temp2,…,tempj}不是頻繁序列，則該序列的超集也不是頻繁序列.

定理3.在UFP-tree上，從序號i對應的樹節點到樹根的路徑頻繁度計數等于該路徑上序號i的頻繁度計數.

證明. 根據UFP-tree構建的過程和定義，顯然每條子樹的葉節點的頻繁度計數小于等于其父節點的頻繁度計數，從序號i對應的樹節點到樹根的路徑可以看成以序號i對應的樹節點為葉節點的子樹，在這棵子樹中，顯然序號i的頻繁度計數最小，所以該子樹的頻繁度計數為序號i的頻繁度計數，所以定理3得證.

證畢.

應用定理3可快速得到每條路徑的頻繁度計數.

定理4.設序列{temp1,temp2,…,tempj}是以序號tempj為終止序號的序列，當且僅當序列對應數組節點中的編碼進行“與”運算的結果C中各位的和不小于最小支持度計數時，該序列為頻繁序列.

C=S[t1].r_code&…&S[tj].r_code，

(2)

其中，ti為序號tempi在數組S[]中對應的下標.

證明. 根據結構體Struct_info的定義可知，路徑編碼r_code為序號seq在各路徑上頻繁度計數的分配情況，當序列中的某些序號出現在同一條路徑下時，這些序號在該路徑對應的編碼位的數值相同，未在同一條路徑的其余序號在該路路徑對應的編碼位的數值為0.即結構體數組中任意2個元素的路徑編碼進行“&”運算的結果可根據式(3)獲得：

(3)

其中，r_codeit表示結構體數組中下標為i元素對應的路徑編碼第t位的值，ct表示C的第t位數值.由于各序號對應的編碼位進行“與”運算得到的結果為序列中各序號共同出現在各路徑下的情況，結果各位數值進行求和計算，結果為序列的頻繁度計數.

證畢.

進一步給出頻繁項集挖掘算法MFIA_UFP_tree，如算法1所示,首先倒序遍歷序號，得到每個序號對應的結構體數組，然后調用算法2(MiningFS)進行頻繁項集的挖掘.

算法1.MFIA_UFP_tree(UFP_tree,countmin).

輸入：UFP_tree為UFP-tree、最小支持度計數countmin；

輸出：所有頻繁項集FP.

①S[]←?,FP←?；*初始化結構體數組S[]和頻繁項集FP*

② fori=max_ordertoldo

③ 將i的指針賦值給臨時變量Tp和tp;

④ while (Tp≠NULL)

⑤j←0;

⑥ if (!S.contain(tp)) then

⑦j←j+1;

⑧ 將tp指向的序號的結構體添加到結構體數組S[]；

⑨ else then

⑩S[tmp].count←S[tmp].count+tp.count;*tmp為序號tp在結構體數組S[]內的下標*

算法1倒序遍歷序號，求得以每個序號為起點、根節點為終點的所有路徑的結構體數組(行②～)，首先遍歷每條路徑上的節點(行③，行～)，進一步判斷數組中是否含有該節點，當不含時，將節點添加到S[]中，并將S[]的長度j加1(行⑦～⑨)，否則找到該節點在S[]中的位置，更新結構體信息(行～)，獲得對應的結構體數組S[]后,調用算法2對每條路徑進行頻繁項集的挖掘(行).算法2如下：

算法2.MiningFS(S[],j).

輸入：結構體數組S[]、數組長度j；

輸出：頻繁項集FP.

①Length←j;

②FP←FP∪{S[0].seq};

③NFP[]←?;*記錄所有長度為2的非頻繁序列的第2個序號*

④ fori=0 tojdo

⑤ if(S[i].count

⑥ 刪除S[i];

⑦Length←Length-1;

⑧ end if

⑨ end for

⑩ forF_len=2 toLength+1 then

算法2根據結構體數組S[]進行頻繁序列挖掘，首先記錄所有長度為2的非頻繁序列(行③)，應用定理2進行剪枝(行④～⑨)，進一步根據剪枝后的頻繁序列候選集的長度進行頻繁序列的挖掘(行⑩～).

挖掘出所有的頻繁序列后，對頻繁序列進行關聯規則挖掘.本文基于相關系數挖掘正相關無冗余關聯規則，其中相關系數計算：

(4)

其中,supp()為支持度，A和B分別是要挖掘的關聯規則的前件和后件.

根據關聯規則的定義可知，當關聯規則A→B是強關聯時，說明前件A的出現對后件B的出現起到了促進作用，即有很大的可能當A出現時B也出現，因此給出定理5作為維度分組依據.

定理5.正相關關聯規則A→B，若conf(A→B)=1，則前件A出現時后件B必然出現.(conf(A→B)表示關聯規則A→B的置信度)

證明. 當conf(A→B)=1時，則count(A∪B)=count(A)，即前件A和后件B共同出現的次數等于前件A出現的次數，即前件A出現后件B必然出現.

證畢.

通過算法1獲得頻繁項集后，基于相關系數進行關聯規則的挖掘，并依據定理5將相關聯的維度合并到1個分組，當不同關聯規則的前件有交集時，相關的維度分組進行合并.進一步給出分組算法Group_PAR，如算法3所示：

算法3.Group_PAR(FP,ρmin).

輸入：維度頻繁項集FP、最小相關系數ρmin；

輸出：維度分組情況Group.

①PAR←?,Group←?,j=0;

Group記錄分組情況*

② forX∈FPdo

③ 根據式(4)計算所有由頻繁序列X生成規則的相關系數ρAB，其中A∪B=X,A∩B=?；

④ if (ρAB≥ρmin) then

⑤ if (conf(A→B)≥1) then

⑥PAR←PAR∪{A→B};

⑦ end if

⑧ end if

⑨ end for

⑩ forY∈PARdo*Y的格式為A→B*

算法3先遍歷頻繁項集，對每個項集進行關聯規則的挖掘，生成關聯規則(行②～⑨)，然后刪除冗余規則(行⑩～)，對生成的正相關無冗余規則應用定理5進行分組，最終得到分組情況Group(行～).

3.1.2 基于維度分組的Hash降維

本節對維度分組后的數據集進行Hash降維，同時提出符號位的概念并給出定義.當組內維度個數大于1時，通過LSH函數進行降維，同時在新生成的維度上保持著原維度上的相對位置關系.本文采用的Hash函數是2-穩定分布LSH函數[31],其碰撞概率為

(5)

由于數據被Hash函數映射后數據位置關系發生偏移，本文對Hash降維后的數據設置了符號位，并給出符號位的定義.

(6)

根據符號位的定義和2-穩定分布LSH函數的性質，進一步得出性質1，并根據性質1來篩選候選集，提高查詢的準確率.

性質1.2個距離相近的數據經過相同的LSH函數映射后，落入相鄰的Hash桶中的數據對應符號位相同.

設Δ=|a·q+b|%w，t=ha(q)，當Δ<0.5w時，由圖1可知，ha(q)的概率分布向左偏移，點q經過Hash函數映射后有較大概率落入t-1桶的右半部分，即t-1桶中符號位為|t-1|+0.5的數據中存在點q的映射結果.同理Δ≥0.5w時，t+1桶中符號位為|t+1|-0.5的數據中存在點q的映射結果.

Fig. 1 Schematic diagram of sign bit identical probability圖1 符號位相同概率示意圖

通過算法3得到維度分組情況后，算法4首先根據分組結果中每個組中包含的項數來初始化Hash函數，隨后對數據進行Hash降維，根據每個組中包含的維度個數分配Hash函數，并將每組中的維度看成1個向量并進行計算，進一步根據式(6)計算符號位數值，最終返回降維后的數據集.因此，給出維度分組后進行降維的算法Reduce_dim，如算法4所示：

算法4.Reduce_dim(w,Group,X).

輸入：桶寬w、數據維度分組情況Group={g1,g2,…,gm}、原始數據集X={x1,x2,…,xn}；

輸出：降維后的數據集X′.

①X′←?；

② fori=0 tomdo

④ 為每個維度組初始化Num_func個Hash函數；

⑤ end for

⑥ fori=0 tondo

⑦ 對xi進行Hash降維;

⑩ end for

3.2 基于動態加權的近似k近鄰查詢

數據經過維度分組和Hash降維后，為了提高計算速度，本文將降維后的數據進行編碼，即x∈{0,1}l.根據編碼后的數據，應用熵理論對Hash編碼函數進行篩選.本文應用2-穩定分布LSH進行編碼，方法為

(7)

其中，a是服從2穩定分布的隨機函數產生的一個D-|Z|維向量，D為降維后的數據維度，Z為符號位，|Z|是符號位的長度.根據信息熵和Hash編碼的特性，進一步給出定理6.

定理6.若Hash函數將數據對象映射成0和1的概率越相近，那么該Hash函數的散列效果就越好.

證明. 根據式(7)對數據進行0，1編碼，其中Hash函數相當于二元信源，0和1為二元信源符號，二元信源熵的計算公式為

entropy(Y)=E(Y)=-ωlgω-? lg ?，

(8)

其中，E(Y)是ω的函數，ω為信源符號概率.

根據式(8)可知，當信源符號出現的概率越接近，信息熵越大，即Hash函數編碼結果越不確定，散列效果越好.因此得證.

證畢.

由于二進制編碼的長度對查詢準確率有著顯著的影響，為提高編碼質量，本文基于定理6篩選出熵值大的函數作為映射函數進行編碼.數據經過算法4進行維度分組降維預處理后，應用算法5對其進行編碼.

算法5.Hash_code(X′，l).

輸出：編碼后的數據集X_c.

①X_c←?；

② 初始化2l個Hash編碼函數;*隨機變量維度為D-|Z|維*

③ fori=0 tondo

⑤ end for

⑥ fori=0 to 2ldo

⑦ 根據式(8)計算每個編碼Hash函數的熵；

⑧ end for

⑨ 選擇出熵為前l大的函數作為編碼函數；

⑩ fori=0 tondo

算法5先隨機生成2l個Hash函數，進一步根據式(7)進行Hash(行①～⑤)，編碼后對編碼函數進行篩選，計算每個編碼函數對應的熵值，選擇出熵值為前l的函數作為編碼函數(行⑥～⑨)，最終將多余的編碼刪除得到最終編碼數據集(行⑩～)，因此時間復雜度為O(ln).

當進行查詢時，將查詢點q進行相同處理，通過與編碼后的數據集X_c中的數據進行比較，返回漢明距離在小于給定閾值dismin的數據作為候選集CS，進一步根據性質1篩選候選集，基于候選集中的每位編碼與查詢點對應位的編碼相同的概率，對編碼位進行權重賦值，然后計算查詢點q與候選集CS中數據的加權漢明距離，根據加權距離進行排序

并返回前k個數據.由二元信源熵函數可知，相同編碼位的編碼相同的概率越大，對應編碼位的可信度就越高，權重越大.根據熵權法對第i位設定權重：

(9)

其中，ei為第i位的信息熵值.

當對數據集進行編碼后，輸入查詢點進行相同的維度分組降維以及編碼后，基于加權漢明距離進行查詢，同時查詢過程中動態調整權值.查詢算法如算法6所示：

算法6.DWAkNN(X_c,q,dismin).

輸出：q的近似k近鄰.

①CS←?；*CS為候選集*

②q′←Reduce_dim(w,Group,q);

③q″←Hash_code(q′,l);

④ fori=0 tondo

⑦ end if

⑧ end for

⑨ 根據式(8)計算候選集CS中每位編碼的熵;*概率為與查詢點q對應編碼位相同的概率*

⑩ 根據式(9)計算候選集CS中每位編碼的權重；

算法6先將查詢對象q進行降維并進行編碼(行②③)，然后遍歷編碼后的數據集X_c，返回漢明距離小于dismin的數據并添加到候選集CS(行④～⑧)，計算候選集中數據的每位編碼位的熵值，進一步根據熵值計算編碼位的權重(行⑨⑩)，最后計算加權漢明距離并進行升序排序，當加權漢明距離相同時，根據符號位相同的個數進行排序，最終返回前k個數據作為查詢結果(行～).

4 實驗分析

為了評估算法性能，分別測試了自身參數對算法性能的影響以及與對比算法的性能.

4.1 參數分析

本節實驗分析關聯規則最小支持度min_s、頻繁項集最小支持度min_s_r和l對算法準確率的影響以及數據維度對算法查詢時間的影響.準確率Ratio其值為近似k近鄰距離與真實k近鄰距離之比的平均數，其值越接近1說明算法查詢質量越高，準確率Ratio計算方式為

(10)

本節實驗使用的數據集為真實數據集和人工數據集.分別是由IBM Almaden Quest研究小組的生成器生成的數據集T40I10D100K和由Roberto Bayardo從PUMSB中提供的pumsb數據集和由Claudio Lucchese等人通過爬蟲得到的網絡文檔數據集webdocs_samping.數據集是從FIMI信息庫下載得到(1)http:fimi.uantwerpen.bedata.3個數據集被廣泛應用于頻繁項集挖掘試驗.由于數據集webdocs過大，從原始數據集中隨機選取10萬條數據作為數據集進行實驗，并對數據信息進行了適當調整和優化.該數據集記為webdocs_samping.數據集屬性如表1所示：

Table 1 Attribute Sheet of Experimental Data Set forParameter Analysis

在實驗中，分別從各數據集隨機抽取5 000條事務作為查詢點進行查詢，最后計算平均時間和準確率作為比較.

實驗1.首先分析參數min_s和min_s_r對本文所提算法的準確性的影響.其中k=50，編碼長度l=32 b，Hash函數的桶寬w=4.由于數據集T40I10D100K是一個稀疏數據集，因此分析了參數min_s從0.5%～4%變化過程中對算法準確率的影響；數據集pumsb和webdocs_sampling相對稠密，因此分析了參數min_s從60%～95%的變化過程對算法正確率的影響，同時參數min_s_r的取值為60%，70%，80%，90%.參數影響分別如圖2～4所示.

Fig. 2 Experimental result on dataset T40I10D100K圖2 在數據集T40I10D100K上實驗結果

Fig. 3 Experimental result on dataset pumsb圖3 在數據集pumsb上實驗結果

Fig. 4 Experimental result on dataset webdocs_sampling圖4 在數據集webdocs_sampling上實驗結果

通過圖2～4可知，在3個數據集上當min_s_r固定時，Ratio隨著min_s的增大呈現上升的趨勢，由Ratio的計算公式可知，當Ratio偏離1越遠，算法的查詢結果的準確性越低，因此當min_s_r的值固定時，算法在3個數據集上的查詢準確性隨min_s的增大而降低.這是由于當min_s_r固定時，隨著頻繁項集最小支持度min_s的增大，導致在進行分組降維的過程中忽略的項增多，致使降維后的誤差大.同時在3個數據集上當min_s固定時，Ratio總體上隨min_s_r的增大而更趨近于1，即算法的準確性隨min_s_r的增大而增大，這是由于在分組降維過程中，關聯規則的質量影響著維度的分組，min_s_r越大說明關聯規則的前后件關系越緊密，組內的非零值維度越多，減少了Hash函數中隨機變量的維度和Hash函數的個數，降低了降維后的誤差.

實驗2.分析參數l對查詢準確率的影響.在本實驗中，設在數據集T40I10D100K中min_s=2%，另外2個數據集中為75%，設min_s_r在3個數據集中都為90%，k和w分別為50和4，分析l的值為8,16,32,48,64對查詢準確率的影響，結果如圖5所示:

Fig. 5 Effect of l on Ratio圖5 l對Ratio的影響

由圖5可知，在3個數據集上Ratio都隨著編碼長度l的增大而更趨近于1，即算法的查詢準確性隨著l的增大而增大，當編碼位數大于32 b時，編碼位數對查詢結果的提升幅度變小，這是由于算法在將數據從歐氏空間映射到漢明空間時本身信息缺失導致的.

通過實驗1和實驗2可以看出，本算法能以較高的正確率返回k近鄰，在稀疏和稠密數據集上表現都比較優異.

4.2 算法對比

本節通過與對比算法比較不同k下查詢結果的準確率和查詢時間進一步評估本文算法性能.

1) 數據集.本節應用真實數據進行對比實驗，所用的數據集分別是Mnist，Sun，Trevi，Nus，Deep，BlackFriday.其中前5個數據集通過GitHub網站獲取(2)https:github.comDBWangGroupUNSWnns_benchmark，被廣泛應用于現有的AkNN查詢實驗.原始BlackFriday數據集是從Kaggle平臺(全球數據科學競賽在線平臺)獲取(3)https:www.kaggle.comsdolezelblack-friday，由于原始數據集包含不相關的屬性，因此對其進行了數據清洗，只保留了每個用戶的購物信息.數據集屬性如表2所示.在查詢時，我們從每個數據集中隨機選取500個數據點作為查詢點，每個查詢點重復查詢50次，k分別取值為10,30,50,70,90，默認k=50，取查詢時間和查詢準確率的平均值作為算法的性能指標.

2) 對比算法.我們選擇HD-Index查詢算法[15]、HWT查詢算法[17]和QALSH(query-aware LSH)查詢算法[20]與本文所提出的DWAkNN查詢算法進行對比.所選算法分別基于Hilbert空間填充曲線、漢明加權樹和LSH實現.

Table 2 Comparison the Experimental Data Sets表2 對比實驗數據集

3) 參數設置.本文算法的參數min_s，min_s_r，w分別設置為0.04，0.9，4，編碼長度l=32 b.根據文獻[15]的實驗結果，將算法HD-Index的參數m，τHD-Index，α，βHD-Index分別設置為10，16(在數據集Trevi和BlackFriday上值分別設為64和60)、4 096和4 096，其中m為參考點個數，τHD-Index為RDB-tree的個數，α為經過RDB-tree剪枝獲得候選集個數，βHD-Index為經過三角不等式進行進一步過濾的候選集個數.根據文獻[17]的實驗過程，算法HWT的參數τHWT設為1 000，同樣應用LSH將數據集的實值向量映射到二進制碼，在本文中設置二進制長度為32 b.

Fig. 6 Influence of k on query time圖6 k值對查詢時間的影響

首先測試k值對查詢時間的影響.實驗結果如圖6所示.由圖6可以看出4個測試算法在6個數據集上的查詢時間都是隨著k的增大呈上升趨勢，本文算法效率優于算法QALSH和HD-Index，當k=50時，查詢效率分別提高了25.0%～72.8%和20.0%～63.0%.但是查詢時間略高于算法HWT.這是由于本文算法在進行查詢時會動態設置編碼位的權重，然后進行加權排序，導致查詢時間略高于算法HWT.根據圖6(b)(d)可以看出，隨著數據規模的增大(Sun數據集和Nus數據集維度相差不大，規模相差1個數量級)，4個算法的查詢時間也都增大.

Fig. 7 Influence of k on Ratio圖7 k值對Ratio的影響

其次測試k值對查詢準確率的影響.實驗結果如圖7所示.由圖7可以看出除了在數據集Black-Friday，算法QALSH的Ratio接近1，查詢質量最高，算法DWAkNN次之，算法HD-Index和算法HWT相差不大，略高于算法DWAkNN，在數據集BlackFriday上，算法DWAkNN最優.這是由于算法DWAkNN通過對維度間的關聯規則進行分組降維后再進行編碼，減少了數據信息的丟失，然而除購物信息數據集BlackFriday外，其他數據集都是圖像類型，數據維度間的關聯性不穩定，維度分組降維對算法的查詢準確率提升小于在BlackFriday數據集上的提升，因此在表2的前5個數據集上的查詢質量略低于QALSH算法，但是與同樣應用LSH對數據進行編碼的HWT算法相比，算法DWAkNN的查詢質量更優.同時結合圖6的查詢時間結果圖可以看出，在相同數據集上，本文所提算法DWAkNN能夠以較低的查詢時間返回更接近真實k近鄰的近似結果，算法的綜合性能更優.

最后測試本文算法與線性掃描(LineScan)查詢算法在高維數據集下的性能對比(高維空間線性掃描算法效率高于低維查詢算法).實驗結果如表3所示，可以看出本文算法的效率遠高于LineScan算法.

Table 3 High-Dimensional Data Set Query Time and Efficiency Improvement Table

通過實驗可得，本文所提算法DWAkNN能夠以較低查詢時間返回較高質量的AkNN查詢結果，與目前先進AkNN查詢算法相比，綜合性能更為優越，尤其提高了維度間關聯關系明顯的數據集下AkNN查詢的準確率，同時與傳統的低維空間下的查詢算法相比較，算法DWAkNN在高維空間下的查詢效率得到大幅度的提升.

5 總 結

本文對高維空間下近似k近鄰查詢問題進行了研究，針對高維數據降維過程不考慮維度間的關聯關系的問題，提出基于關聯規則的維度分組降維算法Reduce_dim，進一步提出了Hash_code算法，該算法基于LSH對降維后的數據進行編碼，并應用信息熵理論篩選編碼函數，最終提出了動態加權漢明距離近似k近鄰查詢算法DWAkNN，算法應用符號位對候選集進行篩選，提高了查詢準確率.實驗結果表明，本文提出的算法具有較好的性能.未來研究重點主要集中在基于神經網絡的高維空間近似k近鄰查詢問題等方面.