基于維度分組降維的高維數(shù)據(jù)近似k近鄰查詢

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

(哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150080)

(lisongbeifen@163.com)

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

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

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

本文主要貢獻(xiàn)有3個(gè)方面：

1) 針對(duì)已有的高維數(shù)據(jù)近似k近鄰查詢算法不考慮數(shù)據(jù)維度值分布情況，面對(duì)0值維度個(gè)數(shù)遠(yuǎn)大于非0值維度個(gè)數(shù)的數(shù)據(jù)空間、查詢效率降低、運(yùn)算性能浪費(fèi)等問題，提出了一種基于維度間關(guān)聯(lián)規(guī)則進(jìn)行分組降維的思想，并設(shè)計(jì)了基于LSH的維度分組降維算法，降低了維度值分布對(duì)查詢的影響，提高了運(yùn)算性能.

2) 針對(duì)基于維度間關(guān)聯(lián)規(guī)則的維度分組降維過程中維度間關(guān)聯(lián)規(guī)則挖掘效率低、挖掘關(guān)聯(lián)的頻繁維度耗時(shí)高的問題，本文基于單向頻繁模式樹提出了一個(gè)新的頻繁項(xiàng)集挖掘算法，通過該算法能快速挖掘出頻繁維度，實(shí)現(xiàn)維度間的關(guān)聯(lián)規(guī)則高效挖掘，為高維數(shù)據(jù)的維度分組降維提供支持.

3) 針對(duì)傳統(tǒng)的LSH編碼方式查詢高維數(shù)據(jù)近似k近鄰存在漢明距離準(zhǔn)確率低、Hash函數(shù)內(nèi)存消耗大等問題，本文提出了基于信息熵對(duì)編碼函數(shù)進(jìn)行篩選和動(dòng)態(tài)權(quán)重賦值，并通過加權(quán)漢明距離返回結(jié)果集的高維數(shù)據(jù)近似k近鄰查詢算法，提高了查詢性能和效率.

1 相關(guān)工作

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

以上研究主要是處理低維空間環(huán)境下的k近鄰查詢問題及其變種，但隨著維度的增長(zhǎng)，算法查詢效率隨之下降.以R-tree索引結(jié)構(gòu)為例，當(dāng)數(shù)據(jù)維度大于20時(shí)，查詢效率不如線性掃描，因此如何高效高質(zhì)量地解決高維空間近似k近鄰查詢問題是目前研究的重點(diǎn).

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

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

目前現(xiàn)有的高維數(shù)據(jù)近似最近鄰查詢算法都是預(yù)先將原始數(shù)據(jù)集進(jìn)行處理，然后建立索引結(jié)構(gòu)，根據(jù)索引進(jìn)行AkNN查詢.對(duì)原始高維數(shù)據(jù)的預(yù)處理過程中，大多不考慮維度間的關(guān)聯(lián)關(guān)系對(duì)查詢效率和準(zhǔn)確率的影響.因此，本文提出了基于維度間的關(guān)聯(lián)規(guī)則進(jìn)行維度分組的高維數(shù)據(jù)降維方法，應(yīng)用該方法對(duì)高維數(shù)據(jù)進(jìn)行預(yù)處理后，采用二進(jìn)制編碼的方式進(jìn)行查詢，同時(shí)基于信息熵篩選編碼函數(shù)、權(quán)重的動(dòng)態(tài)設(shè)定等方式優(yōu)化查詢方法.

2 主要定義

定義1.頻繁序列.設(shè)temp1

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

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

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

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].信息熵是一種用于度量系統(tǒng)不確定性的度量方法，其香農(nóng)計(jì)算公式為

(1)

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

3 高維數(shù)據(jù)近似k近鄰查詢

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

3.1 基于維度分組的Hash降維

3.1.1 基于維度間關(guān)聯(lián)規(guī)則的維度分組

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

定義5.結(jié)構(gòu)體Struct_info.

Struct_info{

seq;*項(xiàng)轉(zhuǎn)換后的序號(hào)*

count;*頻繁度計(jì)數(shù)*

r_code;*包含序號(hào)seq的路徑編碼*

}，

其中路徑編碼根據(jù)起始節(jié)點(diǎn)的位置來定，本文采用從0開始，從左到右依次加1的方式進(jìn)行編碼.

在進(jìn)行基于支持度和置信度[30]的頻繁項(xiàng)集挖掘時(shí)，首先對(duì)給定d維數(shù)據(jù)集Q={q|q∈Rd}進(jìn)行二值化，對(duì)應(yīng)維度有值的用“1”標(biāo)記，沒有值的用“0”標(biāo)記，得到二值化后的數(shù)據(jù)集Q′；然后掃描二值化后的數(shù)據(jù)集Q′，去除支持度小于給定閥值的維度，對(duì)剩余維度建立序號(hào)-項(xiàng)集轉(zhuǎn)換表，并構(gòu)建UFP-tree.針對(duì)頻繁項(xiàng)集挖掘過程中統(tǒng)計(jì)支持度和項(xiàng)集剪枝的資源消耗問題，本文根據(jù)結(jié)構(gòu)體的定義，進(jìn)一步給出結(jié)構(gòu)體數(shù)組的定義.

定義6.結(jié)構(gòu)體數(shù)組S[].給定一個(gè)UFP-tree，設(shè)結(jié)構(gòu)體數(shù)組S[]，當(dāng)且僅當(dāng)其滿足的條件為：

1) 對(duì)于任意以序號(hào)i為起點(diǎn)、根節(jié)點(diǎn)為終點(diǎn)的路徑，其序號(hào)集為Seq={seq1,seq2,…,seql},其中l(wèi)為數(shù)組S[]的長(zhǎng)度；

2)S[j].count的值為S[j].seq對(duì)應(yīng)的節(jié)點(diǎn)在從i到根節(jié)點(diǎn)的路徑上的頻繁度計(jì)數(shù)和；

3)S[j].r_code的編碼位數(shù)為從i到根節(jié)點(diǎn)所有路徑的個(gè)數(shù)；

4)S[j].r_code的每位編碼上的值為S[j].seq對(duì)應(yīng)節(jié)點(diǎn)在該路徑上的頻繁度計(jì)數(shù)；

稱S[]為序號(hào)i對(duì)應(yīng)的結(jié)構(gòu)體數(shù)組.

為保證所有的頻繁序列都能根據(jù)序號(hào)對(duì)應(yīng)的結(jié)構(gòu)體數(shù)組挖掘得到，本文根據(jù)結(jié)構(gòu)數(shù)組和UFP-tree給出定理1.

定理1.給定UFP-tree，設(shè)序列FSeq={seq1,seq2,…,seqi}，若FSeq是頻繁序列，則序列FSeq一定屬于序號(hào)seqi對(duì)應(yīng)的結(jié)構(gòu)體數(shù)組S[].

證明. 定理1可以通過反證法進(jìn)行證明.假設(shè)以序號(hào)seqi為結(jié)尾的頻繁序列FSeq不屬于seqi對(duì)應(yīng)的結(jié)構(gòu)體數(shù)組S[]，由UFP-tree的結(jié)構(gòu)可知，任意以seqi為結(jié)尾的頻繁序列一定屬于以序號(hào)seqi對(duì)應(yīng)的節(jié)點(diǎn)為起點(diǎn)、根節(jié)點(diǎn)為終點(diǎn)的1條或多條路徑，根據(jù)結(jié)構(gòu)體數(shù)組的定義可知，任意1條從序號(hào)seqi對(duì)應(yīng)的節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑都是序號(hào)seqi對(duì)應(yīng)的結(jié)構(gòu)體數(shù)組的子集，所以序列FSeq也屬于序號(hào)seqi對(duì)應(yīng)的結(jié)構(gòu)體數(shù)組，與假設(shè)矛盾.

證畢.

在進(jìn)行基于UFP-tree頻繁項(xiàng)集挖掘時(shí)，根據(jù)結(jié)構(gòu)體數(shù)組S[]來進(jìn)行以序號(hào)i為終止端點(diǎn)的頻繁序列挖掘，進(jìn)而得到對(duì)應(yīng)的頻繁項(xiàng)集.因此根據(jù)結(jié)構(gòu)數(shù)組S[]，進(jìn)一步給出定理2～4.

定理2.在序號(hào)i對(duì)應(yīng)的結(jié)構(gòu)體數(shù)組S[]中，若S[t].count小于最小支持度計(jì)數(shù)countmin，則以序號(hào)i為終止端點(diǎn)的所有頻繁序列一定不包含序號(hào)S[t].seq.

證明. 以反證法進(jìn)行證明.假設(shè)S[t].count

證畢.

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

定理3.在UFP-tree上，從序號(hào)i對(duì)應(yīng)的樹節(jié)點(diǎn)到樹根的路徑頻繁度計(jì)數(shù)等于該路徑上序號(hào)i的頻繁度計(jì)數(shù).

證明. 根據(jù)UFP-tree構(gòu)建的過程和定義，顯然每條子樹的葉節(jié)點(diǎn)的頻繁度計(jì)數(shù)小于等于其父節(jié)點(diǎn)的頻繁度計(jì)數(shù)，從序號(hào)i對(duì)應(yīng)的樹節(jié)點(diǎn)到樹根的路徑可以看成以序號(hào)i對(duì)應(yīng)的樹節(jié)點(diǎn)為葉節(jié)點(diǎn)的子樹，在這棵子樹中，顯然序號(hào)i的頻繁度計(jì)數(shù)最小，所以該子樹的頻繁度計(jì)數(shù)為序號(hào)i的頻繁度計(jì)數(shù)，所以定理3得證.

證畢.

應(yīng)用定理3可快速得到每條路徑的頻繁度計(jì)數(shù).

定理4.設(shè)序列{temp1,temp2,…,tempj}是以序號(hào)tempj為終止序號(hào)的序列，當(dāng)且僅當(dāng)序列對(duì)應(yīng)數(shù)組節(jié)點(diǎn)中的編碼進(jìn)行“與”運(yùn)算的結(jié)果C中各位的和不小于最小支持度計(jì)數(shù)時(shí)，該序列為頻繁序列.

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

(2)

其中，ti為序號(hào)tempi在數(shù)組S[]中對(duì)應(yīng)的下標(biāo).

證明. 根據(jù)結(jié)構(gòu)體Struct_info的定義可知，路徑編碼r_code為序號(hào)seq在各路徑上頻繁度計(jì)數(shù)的分配情況，當(dāng)序列中的某些序號(hào)出現(xiàn)在同一條路徑下時(shí)，這些序號(hào)在該路徑對(duì)應(yīng)的編碼位的數(shù)值相同，未在同一條路徑的其余序號(hào)在該路路徑對(duì)應(yīng)的編碼位的數(shù)值為0.即結(jié)構(gòu)體數(shù)組中任意2個(gè)元素的路徑編碼進(jìn)行“&”運(yùn)算的結(jié)果可根據(jù)式(3)獲得：

(3)

其中，r_codeit表示結(jié)構(gòu)體數(shù)組中下標(biāo)為i元素對(duì)應(yīng)的路徑編碼第t位的值，ct表示C的第t位數(shù)值.由于各序號(hào)對(duì)應(yīng)的編碼位進(jìn)行“與”運(yùn)算得到的結(jié)果為序列中各序號(hào)共同出現(xiàn)在各路徑下的情況，結(jié)果各位數(shù)值進(jìn)行求和計(jì)算，結(jié)果為序列的頻繁度計(jì)數(shù).

證畢.

進(jìn)一步給出頻繁項(xiàng)集挖掘算法MFIA_UFP_tree，如算法1所示,首先倒序遍歷序號(hào)，得到每個(gè)序號(hào)對(duì)應(yīng)的結(jié)構(gòu)體數(shù)組，然后調(diào)用算法2(MiningFS)進(jìn)行頻繁項(xiàng)集的挖掘.

算法1.MFIA_UFP_tree(UFP_tree,countmin).

輸入：UFP_tree為UFP-tree、最小支持度計(jì)數(shù)countmin；

輸出：所有頻繁項(xiàng)集FP.

①S[]←?,FP←?；*初始化結(jié)構(gòu)體數(shù)組S[]和頻繁項(xiàng)集FP*

② fori=max_ordertoldo

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

④ while (Tp≠NULL)

⑤j←0;

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

⑦j←j+1;

⑧ 將tp指向的序號(hào)的結(jié)構(gòu)體添加到結(jié)構(gòu)體數(shù)組S[]；

⑨ else then

⑩S[tmp].count←S[tmp].count+tp.count;*tmp為序號(hào)tp在結(jié)構(gòu)體數(shù)組S[]內(nèi)的下標(biāo)*

算法1倒序遍歷序號(hào)，求得以每個(gè)序號(hào)為起點(diǎn)、根節(jié)點(diǎn)為終點(diǎn)的所有路徑的結(jié)構(gòu)體數(shù)組(行②～)，首先遍歷每條路徑上的節(jié)點(diǎn)(行③，行～)，進(jìn)一步判斷數(shù)組中是否含有該節(jié)點(diǎn)，當(dāng)不含時(shí)，將節(jié)點(diǎn)添加到S[]中，并將S[]的長(zhǎng)度j加1(行⑦～⑨)，否則找到該節(jié)點(diǎn)在S[]中的位置，更新結(jié)構(gòu)體信息(行～)，獲得對(duì)應(yīng)的結(jié)構(gòu)體數(shù)組S[]后,調(diào)用算法2對(duì)每條路徑進(jìn)行頻繁項(xiàng)集的挖掘(行).算法2如下：

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

輸入：結(jié)構(gòu)體數(shù)組S[]、數(shù)組長(zhǎng)度j；

輸出：頻繁項(xiàng)集FP.

①Length←j;

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

③NFP[]←?;*記錄所有長(zhǎng)度為2的非頻繁序列的第2個(gè)序號(hào)*

④ fori=0 tojdo

⑤ if(S[i].count

⑥ 刪除S[i];

⑦Length←Length-1;

⑧ end if

⑨ end for

⑩ forF_len=2 toLength+1 then

算法2根據(jù)結(jié)構(gòu)體數(shù)組S[]進(jìn)行頻繁序列挖掘，首先記錄所有長(zhǎng)度為2的非頻繁序列(行③)，應(yīng)用定理2進(jìn)行剪枝(行④～⑨)，進(jìn)一步根據(jù)剪枝后的頻繁序列候選集的長(zhǎng)度進(jìn)行頻繁序列的挖掘(行⑩～).

挖掘出所有的頻繁序列后，對(duì)頻繁序列進(jìn)行關(guān)聯(lián)規(guī)則挖掘.本文基于相關(guān)系數(shù)挖掘正相關(guān)無冗余關(guān)聯(lián)規(guī)則，其中相關(guān)系數(shù)計(jì)算：

(4)

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

根據(jù)關(guān)聯(lián)規(guī)則的定義可知，當(dāng)關(guān)聯(lián)規(guī)則A→B是強(qiáng)關(guān)聯(lián)時(shí)，說明前件A的出現(xiàn)對(duì)后件B的出現(xiàn)起到了促進(jìn)作用，即有很大的可能當(dāng)A出現(xiàn)時(shí)B也出現(xiàn)，因此給出定理5作為維度分組依據(jù).

定理5.正相關(guān)關(guān)聯(lián)規(guī)則A→B，若conf(A→B)=1，則前件A出現(xiàn)時(shí)后件B必然出現(xiàn).(conf(A→B)表示關(guān)聯(lián)規(guī)則A→B的置信度)

證明. 當(dāng)conf(A→B)=1時(shí)，則count(A∪B)=count(A)，即前件A和后件B共同出現(xiàn)的次數(shù)等于前件A出現(xiàn)的次數(shù)，即前件A出現(xiàn)后件B必然出現(xiàn).

證畢.

通過算法1獲得頻繁項(xiàng)集后，基于相關(guān)系數(shù)進(jìn)行關(guān)聯(lián)規(guī)則的挖掘，并依據(jù)定理5將相關(guān)聯(lián)的維度合并到1個(gè)分組，當(dāng)不同關(guān)聯(lián)規(guī)則的前件有交集時(shí)，相關(guān)的維度分組進(jìn)行合并.進(jìn)一步給出分組算法Group_PAR，如算法3所示：

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

輸入：維度頻繁項(xiàng)集FP、最小相關(guān)系數(shù)ρmin；

輸出：維度分組情況Group.

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

Group記錄分組情況*

② forX∈FPdo

③ 根據(jù)式(4)計(jì)算所有由頻繁序列X生成規(guī)則的相關(guān)系數(shù)ρ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先遍歷頻繁項(xiàng)集，對(duì)每個(gè)項(xiàng)集進(jìn)行關(guān)聯(lián)規(guī)則的挖掘，生成關(guān)聯(lián)規(guī)則(行②～⑨)，然后刪除冗余規(guī)則(行⑩～)，對(duì)生成的正相關(guān)無冗余規(guī)則應(yīng)用定理5進(jìn)行分組，最終得到分組情況Group(行～).

3.1.2 基于維度分組的Hash降維

本節(jié)對(duì)維度分組后的數(shù)據(jù)集進(jìn)行Hash降維，同時(shí)提出符號(hào)位的概念并給出定義.當(dāng)組內(nèi)維度個(gè)數(shù)大于1時(shí)，通過LSH函數(shù)進(jìn)行降維，同時(shí)在新生成的維度上保持著原維度上的相對(duì)位置關(guān)系.本文采用的Hash函數(shù)是2-穩(wěn)定分布LSH函數(shù)[31],其碰撞概率為

(5)

由于數(shù)據(jù)被Hash函數(shù)映射后數(shù)據(jù)位置關(guān)系發(fā)生偏移，本文對(duì)Hash降維后的數(shù)據(jù)設(shè)置了符號(hào)位，并給出符號(hào)位的定義.

(6)

根據(jù)符號(hào)位的定義和2-穩(wěn)定分布LSH函數(shù)的性質(zhì)，進(jìn)一步得出性質(zhì)1，并根據(jù)性質(zhì)1來篩選候選集，提高查詢的準(zhǔn)確率.

性質(zhì)1.2個(gè)距離相近的數(shù)據(jù)經(jīng)過相同的LSH函數(shù)映射后，落入相鄰的Hash桶中的數(shù)據(jù)對(duì)應(yīng)符號(hào)位相同.

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

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

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

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

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

輸出：降維后的數(shù)據(jù)集X′.

①X′←?；

② fori=0 tomdo

④ 為每個(gè)維度組初始化Num_func個(gè)Hash函數(shù)；

⑤ end for

⑥ fori=0 tondo

⑦ 對(duì)xi進(jìn)行Hash降維;

⑩ end for

3.2 基于動(dòng)態(tài)加權(quán)的近似k近鄰查詢

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

(7)

其中，a是服從2穩(wěn)定分布的隨機(jī)函數(shù)產(chǎn)生的一個(gè)D-|Z|維向量，D為降維后的數(shù)據(jù)維度，Z為符號(hào)位，|Z|是符號(hào)位的長(zhǎng)度.根據(jù)信息熵和Hash編碼的特性，進(jìn)一步給出定理6.

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

證明. 根據(jù)式(7)對(duì)數(shù)據(jù)進(jìn)行0，1編碼，其中Hash函數(shù)相當(dāng)于二元信源，0和1為二元信源符號(hào)，二元信源熵的計(jì)算公式為

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

(8)

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

根據(jù)式(8)可知，當(dāng)信源符號(hào)出現(xiàn)的概率越接近，信息熵越大，即Hash函數(shù)編碼結(jié)果越不確定，散列效果越好.因此得證.

證畢.

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

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

輸出：編碼后的數(shù)據(jù)集X_c.

①X_c←?；

② 初始化2l個(gè)Hash編碼函數(shù);*隨機(jī)變量維度為D-|Z|維*

③ fori=0 tondo

⑤ end for

⑥ fori=0 to 2ldo

⑦ 根據(jù)式(8)計(jì)算每個(gè)編碼Hash函數(shù)的熵；

⑧ end for

⑨ 選擇出熵為前l(fā)大的函數(shù)作為編碼函數(shù)；

⑩ fori=0 tondo

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

當(dāng)進(jìn)行查詢時(shí)，將查詢點(diǎn)q進(jìn)行相同處理，通過與編碼后的數(shù)據(jù)集X_c中的數(shù)據(jù)進(jìn)行比較，返回漢明距離在小于給定閾值dismin的數(shù)據(jù)作為候選集CS，進(jìn)一步根據(jù)性質(zhì)1篩選候選集，基于候選集中的每位編碼與查詢點(diǎn)對(duì)應(yīng)位的編碼相同的概率，對(duì)編碼位進(jìn)行權(quán)重賦值，然后計(jì)算查詢點(diǎn)q與候選集CS中數(shù)據(jù)的加權(quán)漢明距離，根據(jù)加權(quán)距離進(jìn)行排序

并返回前k個(gè)數(shù)據(jù).由二元信源熵函數(shù)可知，相同編碼位的編碼相同的概率越大，對(duì)應(yīng)編碼位的可信度就越高，權(quán)重越大.根據(jù)熵權(quán)法對(duì)第i位設(shè)定權(quán)重：

(9)

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

當(dāng)對(duì)數(shù)據(jù)集進(jìn)行編碼后，輸入查詢點(diǎn)進(jìn)行相同的維度分組降維以及編碼后，基于加權(quán)漢明距離進(jìn)行查詢，同時(shí)查詢過程中動(dòng)態(tài)調(diào)整權(quán)值.查詢算法如算法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

⑨ 根據(jù)式(8)計(jì)算候選集CS中每位編碼的熵;*概率為與查詢點(diǎn)q對(duì)應(yīng)編碼位相同的概率*

⑩ 根據(jù)式(9)計(jì)算候選集CS中每位編碼的權(quán)重；

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

4 實(shí)驗(yàn)分析

為了評(píng)估算法性能，分別測(cè)試了自身參數(shù)對(duì)算法性能的影響以及與對(duì)比算法的性能.

4.1 參數(shù)分析

本節(jié)實(shí)驗(yàn)分析關(guān)聯(lián)規(guī)則最小支持度min_s、頻繁項(xiàng)集最小支持度min_s_r和l對(duì)算法準(zhǔn)確率的影響以及數(shù)據(jù)維度對(duì)算法查詢時(shí)間的影響.準(zhǔn)確率Ratio其值為近似k近鄰距離與真實(shí)k近鄰距離之比的平均數(shù)，其值越接近1說明算法查詢質(zhì)量越高，準(zhǔn)確率Ratio計(jì)算方式為

(10)

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

Table 1 Attribute Sheet of Experimental Data Set forParameter Analysis

在實(shí)驗(yàn)中，分別從各數(shù)據(jù)集隨機(jī)抽取5 000條事務(wù)作為查詢點(diǎn)進(jìn)行查詢，最后計(jì)算平均時(shí)間和準(zhǔn)確率作為比較.

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

Fig. 2 Experimental result on dataset T40I10D100K圖2 在數(shù)據(jù)集T40I10D100K上實(shí)驗(yàn)結(jié)果

Fig. 3 Experimental result on dataset pumsb圖3 在數(shù)據(jù)集pumsb上實(shí)驗(yàn)結(jié)果

Fig. 4 Experimental result on dataset webdocs_sampling圖4 在數(shù)據(jù)集webdocs_sampling上實(shí)驗(yàn)結(jié)果

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

實(shí)驗(yàn)2.分析參數(shù)l對(duì)查詢準(zhǔn)確率的影響.在本實(shí)驗(yàn)中，設(shè)在數(shù)據(jù)集T40I10D100K中min_s=2%，另外2個(gè)數(shù)據(jù)集中為75%，設(shè)min_s_r在3個(gè)數(shù)據(jù)集中都為90%，k和w分別為50和4，分析l的值為8,16,32,48,64對(duì)查詢準(zhǔn)確率的影響，結(jié)果如圖5所示:

Fig. 5 Effect of l on Ratio圖5 l對(duì)Ratio的影響

由圖5可知，在3個(gè)數(shù)據(jù)集上Ratio都隨著編碼長(zhǎng)度l的增大而更趨近于1，即算法的查詢準(zhǔn)確性隨著l的增大而增大，當(dāng)編碼位數(shù)大于32 b時(shí)，編碼位數(shù)對(duì)查詢結(jié)果的提升幅度變小，這是由于算法在將數(shù)據(jù)從歐氏空間映射到漢明空間時(shí)本身信息缺失導(dǎo)致的.

通過實(shí)驗(yàn)1和實(shí)驗(yàn)2可以看出，本算法能以較高的正確率返回k近鄰，在稀疏和稠密數(shù)據(jù)集上表現(xiàn)都比較優(yōu)異.

4.2 算法對(duì)比

本節(jié)通過與對(duì)比算法比較不同k下查詢結(jié)果的準(zhǔn)確率和查詢時(shí)間進(jìn)一步評(píng)估本文算法性能.

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

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

Table 2 Comparison the Experimental Data Sets表2 對(duì)比實(shí)驗(yàn)數(shù)據(jù)集

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

Fig. 6 Influence of k on query time圖6 k值對(duì)查詢時(shí)間的影響

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

Fig. 7 Influence of k on Ratio圖7 k值對(duì)Ratio的影響

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

最后測(cè)試本文算法與線性掃描(LineScan)查詢算法在高維數(shù)據(jù)集下的性能對(duì)比(高維空間線性掃描算法效率高于低維查詢算法).實(shí)驗(yàn)結(jié)果如表3所示，可以看出本文算法的效率遠(yuǎn)高于LineScan算法.

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

通過實(shí)驗(yàn)可得，本文所提算法DWAkNN能夠以較低查詢時(shí)間返回較高質(zhì)量的AkNN查詢結(jié)果，與目前先進(jìn)AkNN查詢算法相比，綜合性能更為優(yōu)越，尤其提高了維度間關(guān)聯(lián)關(guān)系明顯的數(shù)據(jù)集下AkNN查詢的準(zhǔn)確率，同時(shí)與傳統(tǒng)的低維空間下的查詢算法相比較，算法DWAkNN在高維空間下的查詢效率得到大幅度的提升.

5 總 結(jié)

本文對(duì)高維空間下近似k近鄰查詢問題進(jìn)行了研究，針對(duì)高維數(shù)據(jù)降維過程不考慮維度間的關(guān)聯(lián)關(guān)系的問題，提出基于關(guān)聯(lián)規(guī)則的維度分組降維算法Reduce_dim，進(jìn)一步提出了Hash_code算法，該算法基于LSH對(duì)降維后的數(shù)據(jù)進(jìn)行編碼，并應(yīng)用信息熵理論篩選編碼函數(shù)，最終提出了動(dòng)態(tài)加權(quán)漢明距離近似k近鄰查詢算法DWAkNN，算法應(yīng)用符號(hào)位對(duì)候選集進(jìn)行篩選，提高了查詢準(zhǔn)確率.實(shí)驗(yàn)結(jié)果表明，本文提出的算法具有較好的性能.未來研究重點(diǎn)主要集中在基于神經(jīng)網(wǎng)絡(luò)的高維空間近似k近鄰查詢問題等方面.