朱命冬，徐立新，申德榮，寇 月，聶鐵錚

1.河南工學院 計算機科學與技術系，河南 新鄉(xiāng) 453003

2.東北大學 計算機科學與工程學院，沈陽 110819

1 引言

隨著基于位置的服務、傳感器網絡、人臉識別、人工智能、數據挖掘等技術的流行，不確定數據在現實生活中廣泛存在。例如，溫度傳感器測量出一個地區(qū)溫度70%的概率為26℃，30%的概率為30℃，即一個事件都以一定的概率發(fā)生。而對不確定數據的管理中一個不可或缺操作是查詢操作，如查詢一個區(qū)域范圍內平均溫度大于30℃的城市。因此不確定性的相似性查詢也被廣泛關注，如不確定性top-k，不確定性數據連接和不確定性最近鄰（nearest neighbor，NN）等[1-6]。隨著云計算技術的成熟和處理大數據需求的加劇，分布式計算和云平臺下算法的研究成為一種趨勢。

隨著數據類型多樣化和復雜化，互聯(lián)網中出現了大量的不確定性文本數據。例如對互聯(lián)網中的圖書進行分類時，從不同網站抽取到的同一本書的摘要信息可能是不同的。假設有一本書Book1,從4個網站抽取到的摘要為A11,從6個網站抽取到的摘要為A12,則這本書的摘要以不確定性的形式可以描述為{＜A11,0.4＞,＜A12,0.6＞}, 即Book1={＜A11,0.4＞,＜A12,0.6＞},可設第二本書的摘要信息為Book2={＜A21,0.5＞,＜A22,0.5＞}。那么在計算Book1和Book2這兩本書的類別時，不僅僅要計算兩本書的摘要內容，還要考慮兩本書的摘要權重。再如，對圖書網站的評價信息進行抽取時，每一個書評都有其支持度，如圖1是《史蒂夫?喬布斯傳》的一條書評，對應每個書評都有“有用”或“喜歡”點擊數，代表該書評的支持度。每本書都有許多書評，每個書評都有一個支持度，很明顯所有的書及其書評組成一個巨大的不確定性文本數據集。同樣的，在微博網站中,每條微博都有點贊數量和轉發(fā)數量，根據這些數量可以計算出某個微博的支持度。這些文本和對應的支持度組成了不確定性文本數據集。通過這個數據集可以查找潛在的朋友，這會比單純比較用戶屬性更全面。類似的應用還有通過影評找相似的電影，通過餐館的評價找相似的餐館等。并且面向不確定文本數據基于余弦相似度的相似性查詢在組合推薦、實體識別、數據集成等領域都具有廣泛應用。例如在讀書網站豆瓣網上，人們傾向于閱讀書評，從而獲得有共同愛好的朋友或者找到和自己讀過的書比較類似的書。當數據集比較大時，這些應用都需要一種高效的面向大規(guī)模不確定性文本數據集的相似性查詢方法。

Fig.1 Areview and support rate of“Steve Jobs”圖1《史蒂夫?喬布斯傳》的一條書評及其支持度

從信息檢索領域的理論和實踐可知，對文本進行分類（例如網頁分類，評論的情感分類）常用方法是先將文本轉化為TF-IDF向量，然后通過計算對應向量的余弦距離得出文本之間的相似性[7]。余弦相似度考慮了文本本身的詞頻和全局詞頻等信息，以及信息論對TF-IDF的理論支持[8]，將文本型的相似匹配轉化為數值型的矩陣計算，使其在計算長文本的相關性和相似性時具有更好的嚴密性和有效性[9-10]。

本文面向不確定文本數據，研究基于余弦相似度的分布式最近鄰查詢方法，目標是提出一種解決方案。一方面該方法需要提高查詢準確度和效率；另一方面該方法需要基于分布式環(huán)境處理大規(guī)模數據集。基于余弦距離計算不確定性文本的相似性主要優(yōu)勢有：

（1）余弦相似度的計算TF-IDF的理論支持[8]，將文本型的相似匹配轉化為數值型的矩陣計算，在整合計算不確定性數據的權重的過程中，純數據的計算比混合數據和文本的計算效率更高。

（2）目前大數據的應用需求普遍存在，通過對余弦相似距離構建索引，可以支持面向大規(guī)模數據的分布式環(huán)境下的k近鄰(k-nearest neighbor,kNN）、逆向k近鄰(reversek-nearest neighbor,RkNN）等復雜查詢。

本文提出基于余弦相似度的分布式環(huán)境下的不確定相似性查詢方法及最近鄰查詢算法，并給出面向度量空間的逆向最近鄰查詢算法。本文的主要貢獻可概括如下：

（1）通過分析不確定文本數據的余弦相似度計算的特征，提出了高效的相似度計算方法和改進的索引結構sMVP-tree（statistic multiple vantage point tree）。

（2）通過對余弦距離進行轉化，提出了一種基于sMVP-tree的相似性查詢方法UnCos（uncertain cosine similarity）。

（3）給出了基于sMVP-tree的查詢過濾方法，然后在UnCos的基礎上提出了分布式kNN查詢算法，以及面向度量空間的RkNN查詢過濾方法。

（4）通過大量實驗驗證了本文算法的有效性。

本文組織結構如下：第2章給出了相關工作；第3章介紹了預備知識和本文使用的數據模型；第4章詳細描述了本文提出的查詢方法UnCos；第5章提出了分布式查詢處理算法；第6章給出實驗結果與分析；第7章對全文進行總結，并指出進一步的工作方向。

2 相關研究

近年來，面向不確定數據的相似性查詢引起了廣泛的關注，根據研究對象大致可將現有研究分為兩類：針對數值型數據的方法[11-16]和針對文本型數據的方法[17-21]。

在針對數值型數據的方法中，文獻[11]針對不確定數值型數據進行研究，分別在歐式距離、歐式平方距離和直角距離的條件下提出了查詢期望最近鄰（expected nearest neighbor，ENN）的計算方法，這些方法只需要構建線性大小的索引就可以在綜合對數或次線性時間代價內計算出ENN。文獻[12]提出了查詢非零概率最近鄰數據對象的高效算法，提出了預估一個數據對象是查詢的最近鄰的概率的方法，分別給出了返回最大似然估計的最近鄰和返回大于一定概率的最近鄰的算法。文獻[13]提出了在歐式距離條件下面向不確定數據的相似性查詢方法，該方法可以返回用戶指定概率閾值內的kNN查詢。為了處理大規(guī)模高維數據，文獻[14]通過將空間和時間信息整合構建統(tǒng)一索引的基礎上提出了一種快速的kNN查詢算法。文獻[15]提出了一種概率逆向kNN(probabilistic RkNN,PRkNN)的查詢框架，然后基于已有的空間過濾法給出了有效的概率過濾準則，將空間過濾、概率過濾和概率確認方法整合起來提出了新的PRNN算法和PRkNN算法。文獻[16]對現有的基于歐式距離計算路網kNN查詢方法在內存中計算效果進行了詳細比較，提出了改進的增量歐式限制（incremental Euclidean restriction，IER）方法。但現有方法的RkNN查詢過濾方法多針對歐式空間，不適用于度量空間，本文提出的RkNN算法可以有效處理度量空間的數據。

在針對文本型數據的方法中，文獻[17]提出了面向無結構文本的相似性查詢方法，該方法通過有效的詞組劃分過濾不相關的數據對象。但該方法需要預先查詢閾值進行查詢過濾。文獻[18]提出了在編輯距離條件下面向不確定性字符串的相似連接方法。該方法引入了字符串級不確定性模型和字符級不確定性模型，并基于概率q-gram提出了上界過濾器和下界過濾器，從而提高相似字符串識別效率。文獻[19]提出了一種面向近似近鄰查詢的分布式哈希學習方法 SparkPQ（spark product quantization）。SparkPQ基于一種按行列劃分的分布式矩陣，采用分布式K-Means算法實現模型求解和碼本訓練，利用訓練出的碼本模型對分布式數據進行編碼和索引，最終通過Spark分布式框架實現近似近鄰查詢系統(tǒng)。Wang等人提出了可以適用于余弦相似度的不確定性文本類型的相似連接方法[20]。該方法通過字符串特征生成策略對候選查詢結果進行過濾，但該方法需要預先設置不確定性閾值，閾值大小很難準確地設定使其適合各種場景。現有的針對不確定性文本型數據的相似性查詢方法多是集中式方法，文獻[3,21]提出了基于MapReduce的不確定性相似性查詢方法。文獻[3]的方法主要是基于Jaccord距離對兩個集合進行相似性連接。與本文最相關的是文獻[21]提出的方法，文獻[21]利用Voronoi結構將相似的數據對象映射到同一個節(jié)點進行相似性查詢處理，本文在實驗部分和此方法進行了詳細的比較。

3 預備知識

本章介紹所使用的基本概念和數據結構。

字符串相似度函數主要用于衡量兩個字符串之間的相似度，可大致分為兩類：面向詞組的相似度方法和面向字符的相似度方法。面向詞組的方法有余弦相似度方法、Dice相似度方法和Jaccard相似度方法等；面向字符的方法有編輯距離方法、Q-gram方法和Smith-Waterman算法等。本文主要分析基于余弦相似度的計算方法。余弦相似度是通過測量兩個向量內積空間的夾角的余弦值來度量它們之間的相似性。如果兩個向量的方向是一樣的，則它們之間的余弦相似度是1，如果兩個向量的方向是垂直的，則它們之間的余弦相似度是0。

余弦相似度多用在高維正向量空間中。比如在信息檢索和數據挖掘領域，一般一個詞條被認為是一個維度，一篇文檔可以被看作一個多維的向量，向量值代表對應詞條在這篇文檔中的重要度。已知兩個字符串s1和s2的向量s1和s2，則s1和s2的余弦相似度是[22]：

TF-IDF是將字符串轉化為向量的常用方法，TF是指一個詞條t在一篇文檔s中出現的次數，記為tft,s。直觀地說，一個詞條的頻度越大，該詞條在文檔中的重要性就越高。但是有的詞條在別的文檔中也普遍存在，不具有區(qū)分度。比如一個汽車公司的文檔，幾乎每篇文檔中都有“汽車”這個詞。因此一種衡量一個詞條是否具有區(qū)分度的概率被提出來了。一個詞條t的IDF計算方法是：idft=lb(N/dft),其中dft是指包含詞條t的文檔數，N是總的文檔數量。整合兩個概念后，詞條t在文檔s中的TF-IDF為：tfidf(t,s)=tft,s×idft,通過TF-IDF可以計算出詞條在文檔中的權重。

定義1（度量空間距離函數）設D是一個數據對象域，任意x,y∈D,如果距離函數d(x,y)滿足以下條件，則d(x,y)是度量空間距離函數[23]：

面向度量空間的索引方法是通過數據對象之間的距離進行查詢過濾，對于索引方法，數據對象的內容及距離計算函數則是黑盒（black-box）。在面向度量空間的索引方法中，MVP-tree（multiple vantage point tree）是較好的常用方法之一[23]。

MVP-tree是一種基于VP-tree的改進索引方法。主要面向如下兩方面進行改進：（1）數據空間外部的樞紐點可以對數據空間進行劃分，而且在索引中的不同層可以共享樞紐點。這樣，一方面可以減少計算代價，另一方面可以對數據空間進行更好的劃分。（2）索引的構建過程中，葉子節(jié)點中的數據對象保存了從根節(jié)點到該葉子節(jié)點中樞紐的距離。在查詢處理過程中通過這些距離可以減少計算代價，從而提高查詢效率。

根據文獻[23]，可以得出關于MPV-tree的一個引理。

引理1構建MVP-tree的計算代價是O(nlogmn),其中m是索引節(jié)點的出度，n為數據對象的個數。基于MVP-tree進行等值查詢的計算復雜度是O(logmn)。

下面給出本文的數據模型。

數據模型：一個不確定數據對象p是由字符串集S={s1,s2,…,sl}和對應的一個集合W={w1,w2,…,wl}組成，其中wi是對應si的支持度，wi∈[0,1]且。用d表示兩個字符串的余弦距離函數，即對于任意兩個字符串s1和s2,d(s1,s2)=1-CS(s1,s2),其中s1和s2分別是字符串s1、s2的TF-IDF向量，CS是余弦相似度函數。給定余弦距離函數d,兩個不確定數據對象p1和p2的期望距離是：

其中，l1和l2分別是數據對象p和q中的字符串個數。

定義2（期望k最近鄰）設P={p1,p2,…,pn}是包含n個不確定性數據對象的數據集，對于一個不確定性對象q,q在數據集P中的期望最近鄰是ENN(q,P)=argminp∈PED(q,p),q的期望k最近鄰(expectedkNN,EkNN)是本文在不產生歧義的情況下EkNN被簡寫為kNN。

定義3（逆向期望k最近鄰）給定一個不確定性對象q,q的逆向期望k最近鄰(reverse EkNN,REkNN)是REkNN(q,P)={p∈P|q∈EkNN(p,P)}。本文在上下文清晰的情況下REkNN被簡寫為RkNN。

4 查詢方法UnCos

本章分析基于不確定性文本數據余弦相似度計算的特性，提出面向不確定性文本數據基于余弦相似度的查詢方法UnCos。UnCos的構建是基于MVP-tree的改進索引sMVP-tree，在給出UnCos方法之前，首先介紹改進的MVP-tree，稱為sMVP-tree。

sMVP-tree的構建過程與MVP-tree的構建過程基本類似，主要區(qū)別在于sMVP-tree的構建過程中每個索引節(jié)點的分支都保留對應孩子節(jié)點所屬數據對象的距離統(tǒng)計直方圖，直方圖表示為histogram(Ni),索引節(jié)點Ni是第i個索引節(jié)點。如圖2所示是索引節(jié)點N3中樞紐點p1對孩子節(jié)點N4中數據對象的距離直方圖histogram(N4)，其中x軸代表距離的劃分區(qū)間，y軸代表對應區(qū)間內數據對象個數。sMVP-tree的構建過程如算法1所示，首先構造一個索引節(jié)點（第1行），從數據集中隨機選擇一個數據對象，計算出該數據對象和其他數據對象距離的中位數，并根據該中位數將數據集分成兩部分DS1和DS2（第2～4行），用同樣的方法將數據集進一步劃分為四部分DS11、DS12、DS21、DS22（第5～9行）。在計算距離中位數的過程中將四部分的距離直方圖保存在索引節(jié)點中（第10行）。然后對這四部分遞歸調用構建sMVP-tree算法，直到不可再分，并返回結果（第11～12行）。

Fig.2 Space partition of sMVP-tree圖2 sMVP-tree結構示意圖

算法1sMVP-tree構建算法sMVP

輸入：數據集DS

輸出：sMVP-tree

1.創(chuàng)建根索引節(jié)點in

2.P1←從數據集DS中隨機選擇一個數據對象

3.M1←對于所有ds∈D計算距離d(P1,ds)并得出中位數

4.根據M1將DS劃分為兩個集合DS1和DS2

5.P2←從數據集DS2隨機選擇一個數據對象

6.M11←對于所有ds∈DS1計算距離d(P2,ds)并得出中位數

7.M12←對于所有ds∈DS2計算距離d(P2,ds)并得出中位數

8.DS1被M11劃分為DS11和DS12

9.DS2被M12劃分為DS21和DS22

10.將樞紐數據對象(P1,P2)存入索引節(jié)點in中，并且為集合(P1,P2,DS11),(P1,P2,DS12),(P1,P2,DS21),(P1,P2,DS22)構建距離直方圖并存入索引節(jié)點in中

11.遞歸調用sMVP(DS11),sMVP(DS12),sMVP(DS21),sMVP(DS22)生成索引節(jié)點in的子節(jié)點直到葉子節(jié)點

12.返回in

根據算法1，sMVP-tree的計算復雜度同MVP-tree一樣，多了存儲直方圖的空間復雜度，因此可以得出引理2。

引理2構建sMVP-tree的計算復雜度為O(nlogmn),m是索引節(jié)點的出度，空間復雜度為

根據樞紐點的直方圖可以計算出指定距離段的數據對象數量，定義該函數為NumHist(Ni,dist1,dist2),其中dist1和dist2是距離區(qū)間，Ni是索引節(jié)點i。如果Ni是根節(jié)點，則需要對整個索引樹的直方圖進行計算。

基于sMVP-tree索引結構，提出基于余弦相似度的查詢方法UnCos。UnCos主要分為兩部分：第一部分是索引構建部分，在不確定數據集上構建sMVP-tree。該部分通過分析不確定性余弦相似度計算的理論特征，給出了高效的相似度計算方法。第二部分是查詢處理，基于sMVP-tree進行相似性查詢。該部分給出了有查詢質量保證的查詢方法，并給出了計算復雜度理論分析。下面將對這兩部分分別進行詳細的介紹。

4.1 索引構建

設P={p1,p2,…,pn},pi={＜si1,wi1＞,＜si2,wi2＞,…,＜sil,wil＞},為了計算不確定字符串間的余弦相似度，將每個字符串視為一個文檔，然后計算該文檔的TF-IDF向量。令pi={＜si1,wi1＞,＜si2,wi2＞,…,＜sil,wil＞},其中s即對應字符串s的TF-IDF向量。根據式（1）即可計算出不確定字符串間的基于余弦相似度的期望距離。通過分析不確定性余弦相似度的特性，可以給出更快的計算方法，見定理1。

定理 1設，則對于任意pi,pj∈P,

證明根據式（1），又 因 為因此可以得出ED(pi,pj)=定理1得證。 □

通過定理1，不確定性的余弦相似度計算的復雜度可以從O(l2d)減少為O(ld),其中d為TF-IDF向量的維度。

sMVP-tree可以有效地適用于度量空間的最近鄰查詢，但余弦相似度的計算不屬于度量空間。為了有效使用sMVP-tree，首先需要將余弦相似度等價轉化為角度相似度。兩個字符串s1和s2的角度相似度轉化公式如下：

則s1和s2的角度距離可表示為AD(s1,s2)=1-AS(s1,s2)。下面引理3給出了將余弦相似度轉化為角度相似度的合理性。

引理3對于任意的不確定對象q∈P,q的角度相似度的最近鄰即為q的余弦相似度最近鄰。

證明使用反證法，已有一個數據對象q∈P,設p*是q的角度相似度的最近鄰，但不是q的余弦相似度最近鄰，則根據式（1），存在數據對象p,使得：

又因為對任意p∈P,ED(q,p*)≤ED(q,p),即：

因此至少有一對字符串使得：

令x=CS(q,p),則因為F(x)是單調增函數，所以對?x1＜x2,F(x1)＜F(x2)。根據式（3），F(CS(q.si,p?.sj))＜F(CS(q.si,p.sk)),這與式（4）沖突，從而引理3成立。 □

參照引理2，在不確定數據集上的一個sMVP-tree可以以O(ndlogmn+ndl)計算復雜度計算出來，其中d是TF-IDF向量的維度，O(ndl)是計算不確定性數據對象期望的計算復雜度。

4.2 查詢處理

構建好sMVP-tree后，當有不確定性最近鄰查詢q時，首先計算出q的平均點qˉ，然后在構建好的sMVP-tree中查詢qˉ的最近鄰，最后將qˉ的最近鄰返回作為q的查詢結果。具體算法見算法2。

算法2UnCos查詢算法

輸入：查詢q和sMVP-tree

輸出：q的最近鄰查詢結果

1.計算出q的平均點qˉ

2.根據索引節(jié)點中的樞紐數據對象，從根節(jié)點開始計算與qˉ距離最小的孩子索引節(jié)點qnode

3.如果qnode不是葉子節(jié)點，迭代查找與qˉ距離最小的孩子索引節(jié)點

4.如果qnode是葉子節(jié)點，則查找葉子節(jié)點中與qˉ距離最小的數據對象最近鄰

5.返回最近鄰

為了保證查詢結果的正確性，提出了引理4。

引理4q為一個不確定性查詢數據對象，在sMVP-tree中和qˉ的最近鄰即是數據對象q的ENN。

證明根據定理1和引理3，此引理易得證。 □

因此，可以通過O(ndlogmn+ndl)的計算復雜度計算出不確定數據對象集的sMVP-tree。當給定 一個不確定查詢數據對象q，以O(ld)計算出q的 平均點q，因為最近鄰查詢是由兩次范圍查詢組成且 以第二次計算復雜度高于第一次，所以可以以在sMVP-tree中找出qˉ的最近鄰點并返回結果。其中m為索引樹的出度，r為查詢的平均選擇度，h為sMVP-tree的高度。因此可以得出定理2。

定理2P為一個不確定性數據集，以O(ndlogmn+ndl)的計算復雜度在P上構建sMVP-tree，從而可以以的時間復雜度處理基于余弦相似度的不確定性最近鄰查詢。

5 分布式查詢處理算法

當數據集比較大時，如定理2所示算法的計算復雜度會比較高，因此為了有效處理大規(guī)模數據集，本章將算法擴展到分布式環(huán)境下，提出分布式kNN算法和分布式RkNN算法。

分布式算法是基于分而治之的思想，如圖3所示，P2P分布式系統(tǒng)中各個計算節(jié)點是相互獨立并自治的。設C是計算節(jié)點的數量，PV是數據集的樞紐點集，PV={pvi},其中1≤i≤pn,pn是樞紐點數量。PV作為全局信息存儲在各個計算節(jié)點上，每個計算節(jié)點負責一個或多個樞紐點，數據對象根據數據對象與樞紐點的距離被劃分到各個計算節(jié)點上，然后各個計算節(jié)點在本地構建sMVP-tree。

當有計算節(jié)點接收一個不確定性數據對象為q,查詢范圍為R的查詢后，該計算節(jié)點會充當協(xié)調者，并通過式（5）計算相關的樞紐點：

Fig.3 Data flow of distributed algorithm圖3 分布式算法的數據流圖

其中maxdi是pvi維護的數據對象中最大的距離。然后協(xié)調者會轉發(fā)查詢到相關的樞紐點所在的計算節(jié)點上，各個計算節(jié)點通過本地sMVP-tree計算出查詢結果并返回給協(xié)調者。最后協(xié)調者收集中間查詢結果并返回最終結果給用戶。很明顯樞紐點的選擇和查詢算法是系統(tǒng)性能的關鍵點，接下來具體討論這兩點。

5.1 數據劃分樞紐點的選擇

（1）樞紐點的選擇。樞紐點的主要作用是在查詢過程中過濾不相關的數據對象，因此選擇樞紐點的指標是盡可能增加查詢的過濾能力。在度量空間中一般選擇較遠的樞紐點[24]，基于這種啟發(fā)式方法，提出了與文獻[23]類似的樞紐點選擇方案：

①從樣本數據集中隨機選擇一個數據對象o；

②將樣本數據集中距離o最遠的數據對象放到樞紐點集PV中；

③將樣本數據集中和PV中樞紐點平均距離最大的數據對象加入到PV中；

④重復上一步工作直到|PV|=pn。

（2）查詢敏感的負載均衡。在分布式環(huán)境中用一致性哈希對樞紐點進行維護和管理，即樞紐點被劃分在[0,2max]域上，[0,2max]被劃分成多個區(qū)間（token），每個計算節(jié)點負責一個或多個區(qū)間，查詢在系統(tǒng)中通過分布式哈希表進行路由。使用較好的哈希方法如SHA1，樞紐點可以均勻地劃分在各個計算節(jié)點上。但是查詢往往不是均勻分布的，而且分布會發(fā)生動態(tài)變化，因此為了達到系統(tǒng)的負載均衡，需要一種查詢敏感的調整方法。首先為負載均衡設置閾值t，如果一個計算節(jié)點（NodeA）超過平均負載的t倍，即NodeA成了查詢熱點，則NodeA與其負責區(qū)域相鄰的計算節(jié)點（NodeB）進行通信，減少NodeA負責的區(qū)域并增加NodeB負責的區(qū)域，并將相應的樞紐點從NodeA移動到NodeB上。在這個過程中如果別的計算節(jié)點產生了負載失衡，則對該計算節(jié)點重復這個過程直到實現系統(tǒng)的負載均衡。注意為了避免發(fā)生抖動（thrash）現象，負載調整方法要以同一個方向進行。

（3）樞紐點的數量pn的選擇。查詢處理的計算時間可以分為兩部分：一部分是根據樞紐點計算相關計算節(jié)點的時間gt；另一部分是各個計算節(jié)點進行本地查詢的計算時間lt。因此查詢處理的計算時間ct=gt+lt。很明顯，相關計算節(jié)點的計算時間gt和樞紐點數量pn成正比，即gt=α×pn,α是系數比，α的取值和計算節(jié)點的處理性能有關；而本地查詢的計算時間lt和pn成反比，在平均情況下，其中r是查詢對索引樹孩子節(jié)點的平均選擇度，m是索引樹的出度，N是數據集的大小，β是系數比，β由計算節(jié)點的平均處理性能決定。因此可以得出ct的計算公式：

通過求導并計算極值可以得出，當式（7）滿足時：

ct取最小值。通過式（7）可以計算出合適的樞紐點數量。

5.2 分布式查詢算法

如本章開篇所述，在該分布式查詢模型中利用式（5）易于處理范圍查詢。下面討論兩種復雜查詢處理算法：最近鄰查詢算法和逆向最近鄰查詢算法。

5.2.1 kNN查詢

先考慮簡單情況，k=1時，即為1NN查詢，當一個計算節(jié)點接收到一個數據對象為q的1NN查詢后，該計算節(jié)點作為調度者首先以q為查詢對象，0為查詢半徑發(fā)起查詢，計算相關的樞紐點，即計算出樞紐點集PS={pni|ED(pni,q)≤maxdi},其中maxdi是樞紐節(jié)點pni與其維護最遠數據對象的距離。然后調度者將查詢轉發(fā)給負責PS集中數據對象的計算節(jié)點（表示為CS），各個計算節(jié)點計算數據對象q在本地的最近鄰并返回給調度者。調度者接收到所有候選最近鄰后，計算出與q距離最小的數據對象，設mind是最小距離。之后，調度者以q為查詢對象，mind為查詢范圍計算出相關的樞紐點，向負責這些樞紐點除了CS集的計算節(jié)點，轉發(fā)最近鄰查詢。最后，調度者收集候選數據對象計算出最近鄰，返回給用戶。

下面介紹kNN查詢算法，具體過程如算法3所示。首先根據統(tǒng)計直方圖預估出初始查詢距離initR,并計算出相關的計算節(jié)點（第1行），對于一個查詢對象為q的kNN查詢，q與各個樞紐點的距離是qdisti=ED(pni,q),令：

其中，NumHist是第5章定義的直方圖中數據對象計算函數。然后將查詢轉發(fā)給相關的計算節(jié)點集CS1,各個計算節(jié)點計算出本地的kNN數據對象作為候選集返回給調度者，調度者從所有的候選數據對象中計算出最小的kNN候選數據對象的距離mind,并計算出查詢范圍為mind時相關計算節(jié)點CS2（第2～6行），向計算節(jié)點集CS1-CS2轉發(fā)請求，并收集各個計算節(jié)點本地的kNN候選數據對象，計算出最終的kNN結果并返回（第7～11行）。

kNN查詢算法也是使用兩個范圍查詢實現的，但主要區(qū)別是在第一個范圍查詢時，kNN使用樞紐點中sMVP-tree匯總的直方圖信息可以預估出更好的查詢范圍initR。initR可以對k個最近鄰的數據對象有較好的估計，從而有效降低第二次范圍查詢的代價。

根據算法3的計算過程，kNN查詢算法的通信代價由三部分組成：第一部分是收集預估initR的信息，通信代價為O(pn),其中pn為樞紐點數量。第二部分是根據查詢半徑mind計算出的相關計算節(jié)點，通信代價為O(pn)。第三部分是各個計算節(jié)點返回的查詢結果，通信代價為O(k)。因此可得出kNN查詢算法的通信代價為O(2pn+k)。

算法3kNN查詢算法

輸入：查詢q和整數k

輸出：q的kNN查詢結果

1.根據式（8）計算出initR，進而計算出相關的計算節(jié)點CS1

2.將查詢q和查詢半徑initR轉發(fā)給CS1

3.candity←各個計算節(jié)點y∈CS1，計算出本地的k最近鄰

4.candit1←匯總所有candity信息，計算出候選的kNN

5.mind←計算出candit1中數據對象與q最遠的距離

6.CS2←根據式（5）計算出查詢半徑為mind時的相關計算節(jié)點

7.將查詢q轉發(fā)給計算節(jié)點集{CS2-CS1}

8.candity←各個計算節(jié)點y∈CS2,計算出本地的kNN

9.candit2←匯總所有candity,計算出候選的kNN

10.finalkNN←匯總candit1和candit2,計算出最終的kNN

11.ReturnfinalkNN

5.2.2 RkNN查詢

RkNN也是常用的相似性查詢之一，但需要消耗更多的計算代價。在歐式空間中，可以利用空間劃分的特性[25]對RkNN構建索引并進行有效的過濾。但在度量空間中，只能使用數據對象之間的距離過濾數據對象，而沒有方向性等輔助信息，這使得RkNN查詢代價非常高。一個容易想到的簡單方法（SimM）是：首先對數據集進行預處理，并計算出各個數據對象的kNN,對應于每個數據對象p存儲一個列 表 {＜1,d1＞,＜2,d2＞,…,＜i,di＞,＜2i,d2i＞,…,＜lbn,dlbn＞},其中di是數據對象p和iNN之間的距離，n是數據集的大小。假設有一個RkNN查詢q,對于數據對象p,如果滿足ED(o,p)≤d2i,其中i=argmini(i＜k≤2i),則p可能是q的查詢結果，否則p不是q的查詢結果。SimM需要的空間復雜度是O(nlbn),過濾過程的計算復雜度O(n)。很明顯這樣的計算復雜度過高，下面給出一種基于sMVP-tree直方圖的查詢過濾方法。設一個RkNN查詢對象q,一個樞紐點p及該樞紐點負責的數據對象集O。對于任意數據對象o∈O,如果滿足式（9），則o不可能是RkNN查詢結果。

NumHist(p,0,|ED(q,p)-ED(o,p)|-ED(o,p))＞k（9）

用式（9）可以從索引節(jié)點上過濾到大量不相關的數據對象，從而提高查詢效率。如圖4，是樞紐點p維護數據對象的直方圖，當有一個R3NN查詢q時，根據三角不等式，任意數據對象o和q的距離大于o的3NN的最遠距離，因此該數據對象集不包含R3NN的查詢結果，可以過濾掉。

基于該過濾方法，提出了RkNN算法，見算法4，根據式（9）計算出相關的樞紐點（第1行），將查詢轉發(fā)給相關的計算節(jié)點，各個計算節(jié)點在本地的sMVP-tree上使用式（9）計算出候選數據對象（第2～3行），利用kNN查詢算法過濾出真正的RkNN結果并返回（第4～8行）。

Fig.4 Query filtering ofRkNN圖4RkNN查詢過濾

算法4RkNN查詢算法

輸入：查詢q和整數k

輸出：q的RkNN查詢結果

1.根據式（9）計算相關的樞紐點和計算節(jié)點集CS

2.將查詢q轉發(fā)給計算節(jié)點集CS

3.candity←各個計算節(jié)點y∈CS,計算出候選的數據對象

4.For?oi∈candity

5.canditi←利用算法3計算出oi的kNN

6.Ifq∈canditi

7.將oi放入結果集RS中

8.Endif

9.Endfor

10.ReturnRS

從算法4可以看出，RkNN算法主要由|canditi|次kNN查詢算法組成，因此通信代價為O(|canditi|×(2pn+k))。

6 實驗測試與分析

6.1 實驗設置

實驗中使用了兩個真實數據集，第一個數據集抽取自著名的讀書網站豆瓣讀書（http://book.douban.com/），記為Douban，抽取了50萬本書籍信息，平均每本書記錄了30個評價，根據支持度每個評價被賦予一個概率值。第二個數據集抽取自微博網站（http://weibo.com/），記為Weibo，抽取了10萬人的微博信息，平均每個人搜集了45條微博，并且根據喜歡度給定每條微博一個概率值。去除掉TF-IDF值比較低的詞組并通過LDA（latent Dirichlet allocation）[26]算法將詞組合并，從而使詞組數小于500。

實驗基于Cassandra實現，分布式集群由20個計算節(jié)點組成，計算節(jié)點的配置為：Red Hat Linux System 6.1操作系統(tǒng)，IntelCore i3 2100 3.1 GHz CPU和8 GB內存。本文分布式算法的實現主要基于Cassandra系統(tǒng)中P2P的路由協(xié)議，并不依賴于其他優(yōu)化，因此為了客觀考察算法的性能，不使用緩存技術和內存數據庫系統(tǒng)。

目前沒有針對不確定性的基于余弦相似度的相似性查詢算法，本文實驗主要和兩個比較相關的算法進行比較：一個是簡單法（SimM），使用MVP-tree而不是sMVP-tree，對于kNN查詢使用簡單的兩次范圍查詢，對于RkNN查詢則使用文中所述的簡單策略。另一個較相關方法是DistV（distributed Voronoi）[21]，該方法是一個基于Voronoi圖的方法，通過Cassandra系統(tǒng)（http://wi了計算方法的近似度，將計算出的最近鄰和ki.apache.org/cassandra/HadoopSupport）的MapReduce擴展實現。本文提出的方法在實驗中簡稱為DistUC（distributed uncertain cosine similarity）。

實驗中參數默認值如表1所示。

如第5章所述，構建sMVP-tree的計算復雜度和構建MVP-tree的計算復雜度一樣，但空間復雜度要略高于MVP-tree。如表2所示，Weibo中sMVP-tree的空間代價比MVP-tree多28%，Douban數據集中sMVP-tree的空間代價比MVP-tree多30%。因為數據集大小不同，對于Douban數據集的索引空間代價要高于Weibo數據集的索引空間代價。而對于Douban數據集的索引空間代價在分布式環(huán)境中是可以接受的，即平均每個計算節(jié)點的空間代價約為38.9 MB。

Table 1 Experiment parameters表1 實驗參數

為了計算方法的近似度，將計算出的最近鄰和人工選出的結果進行比較。具體地說，對于kNN查詢，設是真實的結果，o1,o2,…,om是算法查詢結果，則近似度為，顯而易見近似度越接近1，性能越好。

Table 2 Space cost of sMVP-tree表2 sMVP-tree的空間代價 MB

6.2 定理1的效果

首先通過1NN查詢驗證定理1對算法性能的影響。在圖5和圖6中比較了使用定理1和不使用定理1時算法的運行時間和準確度。很明顯圖5顯示了使用定理1時算法的運行時間約是不用時的至圖6顯示了算法在Douban和Weibo數據集上的近似度，可以看出在Douban上的近似度要好于在Weibo上的近似度。這是因為Douban的評價長度要比Weibo的更長，包含的信息量更大。本文的算法更適合于Douban數據集。

Fig.5 Effect of Theorem 1圖5 定理1改進效果

為了驗證余弦相似度在處理不確定性文本數據時的優(yōu)勢，圖7和圖8比較了在Douban和Weibo數據集中分別使用余弦相似度計算和Jaccard相似度計算的運行時間和準確性。從圖7中可以看出，在運算時間方面，因為余弦相似度計算方法的計算過程全是數值型運算，效率比混合文本匹配和數值計算的Jaccard相似性計算方法高，進一步通過定理1的優(yōu)化方法，運行時間約是Jaccard相似性計算方法的至同時，從圖8中可以看出，在Douban和Weibo數據集上，余弦相似度計算方法的準確性要優(yōu)于Jaccard相似性計算方法。

Fig.7 Running time:Cosine similarity vs.Jaccard similarity圖7 余弦相似度和Jaccard相似性方法運行時間比較

Fig.8 Accuracy:Cosine similarity vs.Jaccard similarity圖8 余弦相似度和Jaccard相似性方法準確性比較

6.3 詞組數的影響

圖9和圖10是在Douban數據集上從100到400變化詞組數時進行1NN查詢時的實驗結果。在度量空間內，查詢通過數據對象之間的距離進行過濾，查詢效率和數據分布密切關系。因為通過樞紐點的劃分使得相近的數據對象在一個計算節(jié)點上，詞組數的增加沒有對性能產生很大的影響，如圖所示，查詢的計算代價和數據的詞組數呈線性關系。圖9顯示出隨著數據集的詞組數增加，各個算法的運行時間也在逐漸增加，可以看出在詞組數各種取值情況下，DistUC都要比其他兩種算法快。圖10顯示出，隨著數據詞組數的增加，近似度趨于更好。

Fig.9 Effect of tokens number:running time圖9 詞組數的影響：運行時間

Fig.10 Effect of tokens number:accuracy圖10 詞組數的影響：近似度

6.4 kNN查詢性能

通過變化參數k來驗證kNN查詢算法的性能。圖11和圖12顯示了在Douban和Weibo數據集上的kNN算法運行時間。本質上DistUC是由兩輪最近鄰查詢組成，且可以看出DistUC的執(zhí)行效率要明顯好于DistV。圖13顯示了kNN算法的準確度，在Douban和Weibo數據集上近似值都小于3，說明了算法的有效性。

6.5 RkNN查詢性能

最后通過變化參數k來驗證RkNN查詢算法的性能。圖14和圖15顯示了在Douban和Weibo數據集上的RkNN算法運行時間。從圖14和圖15中可以看出sMVP-tree的過濾方法明顯提高了查詢效率，DistUC方法要比SimM方法快一個數量級。圖16顯示了RkNN算法的準確度，本質上RkNN算法是由多個并行的最近鄰算法組成，保持了其較好的近似度。

6.6 負載均衡

Fig.11 Running time ofkNNalgorithm on Douban圖11 kNN算法在Douban上運行時間

Fig.12 Running time ofkNNalgorithm on Weibo圖12 kNN算法在Weibo上運行時間

Fig.13 Accuracy ofkNNalgorithm圖13 kNN算法近似度

Fig.14 Running time ofRkNNalgorithm on Douban圖14 RkNN算法在Douban上運行時間

最后通過包含不同比例的kNN查詢和RkNN查詢的混合查詢任務驗證系統(tǒng)的負載均衡情況，主要考察3種kNN查詢和RkNN查詢的比例，分別是（30%，70%）、（50%，50%）、（70%，30%）。實驗中通過計算系統(tǒng)中計算節(jié)點負載的相對標準差來衡量負載均衡，即，其中xˉ是各個計算節(jié)點負載的平均值，δ是各個計算節(jié)點負載的標準方差。圖17顯示了DistUC算法的負載均衡情況，得益于一致性哈希的均衡性和查詢敏感的動態(tài)平衡性，DistUC算法在不同的查詢負載下均表現出良好的負載均衡，相對標準差維持在0.4以下。

Fig.15 Running time ofRkNNalgorithm on Weibo圖15 RkNN算法在Weibo上運行時間

Fig.16 Accuracy ofRkNNalgorithm圖16 RkNN算法近似度

Fig.17 Load balance圖17 負載均衡

7 結束語

隨著大數據的應用急速增長，面向大規(guī)模數據的分布式查詢處理成為研究熱點。本文研究了分布式環(huán)境下基于余弦相似度的不確定最近鄰查詢的問題。首先分析了不確定性余弦相似度計算的特性，并給出了高效的計算方法，提出了基于sMVP-tree的查詢方法。然后將算法擴展到分布式環(huán)境中，介紹了分布式環(huán)境下的kNN查詢算法，并首次提出了面向度量空間的RkNN查詢和過濾方法。最后通過真實數據上的實驗驗證了算法的有效性。

[1]Zhang Peiwu,Cheng R,Mamoulis N,et al.Voronoi-based nearest neighbor search for multi-dimensional uncertain databases[C]//Proceedings of the 29th International Conference on Data Engineering,Brisbane,Apr 8-12,2013.Washington:IEEE Computer Society,2013:158-169.

[2]Peng Liping,Diao Yanlei,Liu Anna.Optimizing probabilistic query processing on continuous uncertain data[C]//Proceedings of the 37th International Conference on Very Large Data Bases,Seattle,Aug 29-Sep 3,2011.New York:ACM,2011:1169-1180.

[3]Ma Youzhong,Meng Xiaofeng.Set similarity join on massive probabilistic data using MapReduce[J].Distributed and Parallel Databases,2014,32(3):447-464.

[4]Ye Mao,Lee W C,Lee D L,et al.Distributed processing of probabilistictop-Kqueries in wireless sensor networks[J].IEEE Transactions on Knowledge&Data Engineering,2013,25(1):76-91.

[5]Yi Ke,Li Feifei,Kollios G,et al.Efficient processing oftop-Kqueries in uncertain databases with X-relations[J].IEEE Transactions on Knowledge&Data Engineering,2008,20(12):1669-1682.

[6]Dallachiesa M,Palpanas T,Ilyas I F.Top-knearest neighbor search in uncertain data series[J].Proceedings of the VLDB Endowment,2014,8(1):13-24.

[7]Huang Chenghui,Yin Jian,Hou Fang.A text similarity measurement combining word semantic information with TF-IDF method[J].Chinese Journal of Computers,2011,34(5):856-864.

[8]Robertson S.Understanding inverse document frequency:on theoretical arguments for IDF[J].Journal of Documentation,2004,60(5):503-520.

[9]Han Min,Tang Changjie,Duan Lei,et al.TF-IDF similarity based method for tag clustering[J].Journal of Frontiers of Computer Science and Technology,2010,4(3):240-246.

[10]Wu H C,Luk R W P,Wong K F,et al.Interpreting TF-IDF term weights as making relevance decisions[J].ACM Transactions on Information Systems,2008,26(3):55-59.

[11]Agarwal P K,Efrat A,Sankararaman S,et al.Nearest-neighbor searching under uncertainty[C]//Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems,Scottsdale,May 20-24,2012.New York:ACM,2012:225-236.

[12]Agarwal P K,Aronov B,Har-Peled S,et al.Nearest neighbor searching under uncertainty II[C]//Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems,New York,Jun 22-27,2013.New York:ACM,2013:115-126.

[13]Zheng Kai,Fung G P C,Zhou Xiaofang.K-nearestneighbor search for fuzzy objects[C]//Proceedings of the 2010 International Conference on Management of Data,Indianapolis,Jun 6-10,2010.New York:ACM,2010:699-710.

[14]Li Chen,Shen Derong,Zhu Mingdong,et al.kNNquery processing approach for content with location and time tags[J].Journal of Software,2016,27(9):2278-2289.

[15]Bernecker T,Emrich T,Kriegel H P,et al.Efficient probabilistic reverse nearest neighbor query processing on uncertain data[C]//Proceedings of the 37th International Conference on Very Large Data Bases,Seattle,Aug 29-Sep 3,2011.New York:ACM,2011:669-680.

[16]Abeywickrama T,Cheema M A,Taniar D.k-nearestneighbors on road networks:a journey in experimentation and inmemory implementation[J].Proceedings of the VLDB Endowment,2016,9(6):492-503.

[17]Wang Pei,Xiao Chuan,Qin Jianbin,et al.Local similarity search for unstructured text[C]//Proceedings of the 2016 International Conference on Management of Data,San Francisco,Jun 26-Jul1,2016.New York:ACM,2016:1991-2005.

[18]Jestes J,Li Feifei,Yan Zhepeng,et al.Probabilistic string similarity joins[C]//Proceedings of the 2010 International Conference on Management of Data,Indianapolis,Jun 6-10,2010.New York:ACM,2010:327-338.

[19]Wen Qingfu,Wang Jianmin,Zhu Han,et al.Distributed learning to hash for approximate nearest neighbor search[J].Chinese Journal of Computers,2017,40(1):192-206.

[20]Wang Jiannan,Li Guoliang,Feng Jianhua.Extending string similarity join to tolerant fuzzy token matching[J].ACM Transactions on Database Systems,2014,39(1):7.

[21]Akdogan A,Demiryurek U,Kashani F B,et al.Voronoibased geospatial query processing with MapReduce[C]//Proceedings of the 2nd International Conference on Cloud Computing,Indianapolis,Nov 30-Dec 3,2010.Washington:IEEE Computer Society,2010:9-16.

[22]Manning C D,Raghavan P,Schtze H.Introduction to information retrieval[M].New York:Cambridge University Press,2008:113-133.

[23]Bozkaya T,Ozsoyoglu M.Indexing large metric spaces for similarity search queries[J].ACM Transactions on Database Systems,1999,24(3):361-404.

[24]Bustos B,Navarro G,Chávez E.Pivot selection techniques for proximity searching in metric spaces[J].Pattern Recognition Letters,2003,24(14):2357-2366.

[25]Yang Shiyu,Cheema M A,Lin Xuemin,et al.Reverseknearest neighbors query processing:experiments and analysis[J].Proceedings of the VLDB Endowment,2015,8(5):605-616.

[26]Shu Liangcai,Long Bo,Meng Weiyi.A latent topic model for complete entity resolution[C]//Proceedings of the 25th International Conference on Data Engineering,Shanghai,Mar 29-Apr 2,2009.Washington:IEEE Computer Society,2009:880-891.

附中文參考文獻：

[7]黃承慧,印鑒,侯昉.一種結合詞項語義信息和TF-IDF方法的文本相似度量方法[J].計算機學報,2011,34(5):856-864.

[9]韓敏,唐常杰,段磊,等.基于TF-IDF相似度的標簽聚類方法[J].計算機科學與探索,2010,4(3):240-246.

[14]李晨,申德榮,朱命冬,等.一種對時空信息的kNN查詢處理方法[J].軟件學報,2016,27(9):2278-2289.

[19]文慶福,王建民,朱晗,等.面向近似近鄰查詢的分布式哈希學習方法[J].計算機學報,2017,40(1):192-206.