王偉迪，陳 珂，胡天磊，陳 剛，壽黎但

浙江大學 計算機科學與技術學院，杭州 310027

1 引言

在文檔檢索、文檔聚類、文檔分類等任務中，一個關鍵的問題是如何準確地表達兩篇文檔之間的相似性。單詞移動距離（word mover’s distance，WMD）[1]是最近提出的一種有效的文檔相似性度量方式。結合歸一化的詞袋模型和Word2Vec模型[2]詞向量，文檔可以被表示成標簽（signature）的形式，文檔距離可以被形式化為推土機距離（earth mover's distance，EMD）。一個明顯的缺陷是，TF-IDF（term frequency-inverse document frequency）相對于詞袋模型更能體現(xiàn)單詞的重要性。文檔檢索、文檔分類等任務在采用WMD時會涉及到WMD度量下的近鄰查詢處理問題。由于單詞移動距離是基于EMD實現(xiàn)的，EMD度量下的查詢效率往往較低，并且WMD度量下的預取剪枝方法（prefetch prune）實質上為線性查詢。因此，查詢性能瓶頸也是在采用WMD度量文檔相似性時完成文檔檢索、文檔分類等任務必須要解決的問題。

首先，本文針對單詞移動距離的缺陷對它進行微調，將單詞權重調整為TF-IDF，從而得到基于TFIDF的單詞移動距離（TI-WMD）。接著，為了提高TIWMD度量下的文檔k近鄰（k-NN）查詢效率，一種直觀的想法是依據(jù)其他度量空間下的索引技術來控制TI-WMD度量下的候選文檔集規(guī)模。由于TI-WMD存在兩個下界，單詞質心距離TI-WCD（TF-IDF-word centroid distance）和松弛的單詞移動距離（relaxed TIWMD）以及一個與TI-WCD相關的上界，TI-WCD度量下獲取文檔的數(shù)量達到一定程度后，會包含TIWMD度量下的目標文檔。

基于此，針對TI-WCD為歐式距離，本文結合局部敏感哈希和EMD度量下的過濾-細化框架提出了一種層次化的查詢方法（hierarchical query）來提高TI-WMD度量下的文檔k-NN查詢效率。最后，通過文檔分類實驗與查詢實驗，本文對TI-WMD的有效性和層次化查詢方法的性能進行了全面的驗證。

本文的組織結構如下：第2章回顧了一些相關的研究工作；第3章介紹了基于TF-IDF的單詞移動距離（TI-WMD）；第4章詳細闡述了TI-WMD度量下的層次化查詢方法；第5章給出了實驗結果以及分析；第6章對全文進行了總結。

2 相關工作

本文的相關工作主要涉及文檔相似性度量方式、高維向量空間下的近鄰查詢、EMD度量下的查詢方法這三方面。

2.1 文檔相似性度量方式

很多方法已經(jīng)被提出用于衡量兩篇文檔之間的相似性。潛在語義分析算法（latent semantic analysis，LSA）[3]通過矩陣分解的方法來抽取低維的語義信息。主題模型（topic model）是對文字中隱含主題進行建模的方法，它包含概率潛語義分析（probabilistic latent semantic analysis，pLSA）[4]與隱含狄利克雷分布（latent dirichlet allocation，LDA）[5]兩種數(shù)學模型。隨著深度學習的發(fā)展，Word2Vec與Doc2Vec[6]模型相繼被提出，用以在大規(guī)模語料庫上學習單詞向量與文檔向量的表示方式。

2.2 高維向量空間下的近鄰查詢

高維向量空間下的近鄰查詢目前集中在近似方法的研究上，這些方法主要是基于降維（dimension reduction，DR）、局部敏感哈希（locality sensitive Hashing，LSH）、空間填充曲線等思想。其中，基于局部敏感哈希的方法由于它們的效率和準確性在數(shù)據(jù)庫領域受到了廣泛關注。基本的LSH方法由Datar等人[7]首次提出。為了減少對空間的消耗，Entropybased LSH和Multi-Probe LSH[8]方法被提出。LSB（locality sensitive B-tree）[9]是第一個設計用于磁盤數(shù)據(jù)的LSH方法。為了提高效率與準確性并減少空間需求，C2LSH方法被提出。為了減少I/O，sorting keys-LSH[10]方法被提出。

2.3 EMD度量下的查詢方法

推土機距離（EMD）[11]是兩個概率分布之間距離的一個度量。它要求兩個分布具有相同的完整性，比如歸一化的直方圖或者概率密度函數(shù)，其中每一個分布都可以被表示成簽名（signature）的形式。EMD作為一種相似性度量方式，已經(jīng)吸引了很多領域的研究人員的關注，包括信息檢索[11]、數(shù)據(jù)庫[12]等。然而，EMD較高的計算代價將它的應用限制在小規(guī)模數(shù)據(jù)集上。

為了提高EMD度量下的查詢效率，很多基于過濾-細化框架（filter-refinement framework）[13]的方法被提出。對于一個查詢，通過線性查找并依據(jù)EMD的下界可以將一些無效的對象過濾掉。這些下界包括正態(tài)分布[14]、質心與投影[15]、降維[16]、原始對偶空間[17]。

3 基于TF-IDF的單詞移動距離

本章主要介紹基于TF-IDF的單詞移動距離（TIWMD）的定義。

3.1 歸一化TF-IDF表示

文檔頻率（document frequency，DF）表示包含某個單詞的文檔的數(shù)目。由于文檔頻率往往較大，通過逆文檔頻率能將其映射到一個較小的取值范圍中。逆文檔頻率（inverse document frequency，IDF）經(jīng)過平滑處理后可以定義為式（1）所示：

其中，dft表示文檔頻率，N表示文檔的數(shù)目，t表示詞項。那么，對于每篇文檔中的詞項t，TF-IDF權重機制對文檔d中的詞項t賦予權重如式（2）所示：

在進行文檔距離計算的時候，將文檔表示成歸一化的評分向量，即d∈Rn。如果詞項i的TF-IDF評分為tf_idfi，歸一化的TF-IDF評分可以被表示為式（3）所示：

那么d可以被看成是單詞分布的n-1維單純形中的一個點；然而，d中卻不包含單詞的語義信息。

3.2 單詞移動代價

單詞移動代價（word travel cost），可以用單詞之間的距離來衡量。當單詞被表示成Word2Vec詞向量空間中的一個點時，單詞i與單詞j之間的距離可以被表示成式（4）所示：

其中，xi與xj為詞向量。本文將c(i,j)稱為單位權重下從單詞i處移動到單詞j處所需的代價。

3.3 文檔距離定義

假設d1和d2是兩篇文檔在n-1維單純形中的TF-IDF評分歸一化的向量表示，TI-WMD與WMD[1]類似地可以被形式化為式（5）所示的線性優(yōu)化問題。

這個優(yōu)化是EMD的一個特殊情況。其中，Tij表示權重流矩陣T的元素值。EMD的計算可以歸結為二分網(wǎng)絡的最小費用流并采用連續(xù)最短路徑算法（successive shortest path，SSP）進行解決。文檔被表示成標簽的格式后，計算TI-WMD的時間復雜度為Ο(p3lbp)，p表示文檔中不同單詞的數(shù)量。

4 TI-WMD度量下的層次化查詢

本章詳細介紹與層次化查詢相關的TI-WMD的下界、上界以及查詢的理論與實現(xiàn)。

4.1 TI-WMD下界

本節(jié)給出了TI-WMD的兩個下界，松弛的TI-WMD與基于TF-IDF的單詞質心距離。

4.1.1 松弛的TI-WMD

松弛的TI-WMD(RTI-WMD)可以被形式化為式（6）所示的線性優(yōu)化問題。

它刪除了式（5）中的第一個限制條件，二分網(wǎng)絡接收端只接收來自具有最小單詞移動代價的邊上的流。這個問題的最優(yōu)矩陣可以直接計算如式（7）所示。

最優(yōu)矩陣對應的代價為RTI-WMD。對稱地，刪除式（5）中的第二個限制條件可以得到另一個RTIWMD。

4.1.2 基于TF-IDF的單詞質心距離(TI-WCD)

圖1給出了TI-WCD的幾何示意圖。經(jīng)過文檔格式處理后，每篇文檔被表示成文檔標簽，它包含若干詞向量及對應的TF-IDF；單詞質心向量為詞向量對TF-IDF的加權均值，即Xd1與Xd2。那么，||Xd1-Xd2||被稱為基于TF-IDF的單詞質心距離。計算TIWCD的時間復雜度為O(np)，其中n是詞向量的維度。

Fig.1 Diagram of TI-WCD圖1 TI-WCD的幾何示意圖

可以與文獻[1]類似地證明TI-WCD與RTIWMD是TI-WMD的下界。

4.2 TI-WMD上界

圖2給出了TI-WMD的一個上界（ETI-WCD）。由于單位權重下的單詞移動代價由Word2Vec詞向量空間中的歐式距離來表示，根據(jù)三角不等式可知不同文檔間單詞的直接流動應該具有最小的移動代價，因此網(wǎng)絡流經(jīng)過單詞質心這一中間節(jié)點會引入更多的移動代價。那么，網(wǎng)絡流由文檔的每個單詞流往單詞質心，然后在單詞質心間流動，并流入另一篇文檔中的各個單詞，其移動代價必然為TI-WMD的上界。這個上界包含TI-WCD，本文將其稱為增強的TI-WCD(ETI-WCD)。它可以用式（8）來表示。

Fig.2 Diagram of ETI-WCD圖2 ETI-WCD的幾何示意圖

4.3 近似k最近鄰查詢

給定一個文檔查詢dq，TI-WMD度量下的k-NN查詢的目標是返回與查詢dq的TI-WMD最小的k篇文檔，d1,d2,…,dk。這k篇文檔滿足式（9）。其中，由式（8）可知，θk和θq是分別與特定文檔dk和dq相關的常數(shù)，它們是文檔中詞向量到文檔單詞質心的基于TF-IDF評分的歸一化距離。

對于任意一次查詢dq，假設TI-WCD度量下的k*近鄰為（按TI-WCD升序排列），TIWMD度量下的k近鄰為（按TI-WMD升序排列），其中k*≥k，依據(jù)式（9），只要滿足，那么必然有對于一次具體的文檔查詢都是存在確定的，只要k*足夠大，必然可以滿足上述臨界條件。

對于每一次查詢，臨界條件難以控制，無法確定k*與k具體的關系。本文與PrefetchPrune[1]類似地用參數(shù)m來控制候選文檔集的大小使得k*=mk(m>1)。m較小時，{d1,d2,…,dk}為TI-WMD度量下的近似k近鄰；m較大時，{d1,d2,…,dk}為TI-WMD度量下的精確k近鄰。

為了提高文檔查詢的效率，結合TI-WCD是歐式距離，TI-WMD是EMD，本文從原始文檔集中獲取時采用多探尋局部敏感哈希查詢[8]，從中獲取 {d1,d2,…,dk}采用過濾-細化框架[13]，進而可以得到一種層次化的查詢方法。由于多探尋局部敏感哈希得到的是TI-WCD度量下的近似k*近鄰，因此該層次化查詢必然也是得到TI-WMD度量下的近似k近鄰。

4.4 層次化查詢的實現(xiàn)

圖3給出了文檔層次化查詢的具體實現(xiàn)，它包含索引與查詢兩個部分。

4.4.1 索引策略

Fig.3 Procedure of hierarchical query圖3 層次化查詢的具體流程

本文針對文檔的單詞質心向量格式采用文獻[7]所述的如式（10）表達的LSH函數(shù)簇H，在內存中為原始文檔集構建L張哈希表。對于一個整數(shù)M，定義一個函數(shù)簇G={g:S→UM}使得任意的g∈G滿足g(v)=(h1(v),h2(v),…,hM(v))，這里hj∈H，1≤j≤M，g為M個LSH函數(shù)的復合函數(shù)。那么，哈希表可以通過下面3個操作進行構建和維護：

（1）init(L,M,W)構建L張哈希表，每一張哈希表i對應一個復合LSH函數(shù)gi，其包含的每個LSH函數(shù)的系數(shù)a與b都是隨機選取的。

（2）insert(v)對L張哈希表中的每一張表i，計算對應的哈希值gi(v)，并將文檔v放入gi(v)指向的哈希桶中。

（3）delete(v)對L張哈希表中的每一張表i，計算對應的哈希值gi(v)，并將文檔v從gi(v)指向的哈希桶中刪除。

4.4.2 查詢策略

文檔查詢的目標是獲取TI-WMD度量下的k近鄰文檔。它包括兩個查詢過程，獲取候選文檔集Dm與在候選文檔集Dm中進行k-NN查詢。這兩個過程分別涉及文檔的單詞質心向量格式與標簽格式。

在獲取候選文檔集Dm時，本文采用的是多探尋的局部敏感哈希方法來獲取m×k篇文檔。這個過程主要包括3個步驟：生成探測序列、挑選最相似的哈希桶以及在哈希桶中對文檔進行驗證。

在候選文檔集Dm中進行k-NN查詢時，本文采用的是過濾-細化框架。它依據(jù)TI-WMD的兩個下界TI-WCD與RTI-WMD對候選文檔進行剪枝。對于每一篇候選文檔，在過濾階段計算它與查詢文檔之間的TI-WCD和RTI-WMD，從而確定是否能夠剪枝；倘若無法通過TI-WCD和RTI-WMD剪枝掉候選文檔，在細化階段計算查詢文檔與候選文檔的TI-WMD。這樣可以避免一部分文檔參與TI-WMD復雜的計算流程。

4.4.3 復雜性分析

層次化查詢的時間復雜度由兩部分構成：（1）獲取候選文檔集Dm；（2）在候選文檔集Dm中進行k-NN查詢。第（1）部分的代價為O(DML+TM+(mk)lb(mk))，其中D為詞向量維度，M為復合LSH函數(shù)的維度，L為哈希表的個數(shù)，T為探尋次數(shù)，mk為候選文檔集Dm的大小。第（2）部分的代價為O(mkp3lbp)。值得注意的是，第（2）部分的代價比第（1）部分的代價高一個數(shù)量級，對此本文在實驗部分進行了驗證。

5 實驗與結果分析

本章通過在Reuters-21578與20-Newsgroups數(shù)據(jù)集上的k近鄰文檔分類實驗、近似k近鄰文檔分類實驗、查詢檢索實驗對TI-WMD度量的有效性與層次化查詢的性能進行了研究。

5.1 實驗設置

5.1.1 實驗環(huán)境

實驗運行環(huán)境如表1所示。

Table 1 Environment of experiment表1 實驗運行環(huán)境

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

Reuters-21578(Reuters)是Newswire新聞文檔集的一個分支。本文使用的數(shù)據(jù)集除去了屬于多個分類的文檔，它包含65個主題、8 293篇文檔。其中5 946篇文檔劃分為訓練集，2 347篇文檔劃分為測試集。在這些文檔中，最長的包含1 040個單詞，最短的包含6個單詞，平均長度為110個單詞。

20-Newsgroups(20News)來源于Usenet新聞集合。本文選取了18 774篇文檔，它們均勻分布于20個新聞組中，即20個類別。其中11 269篇文檔劃分為訓練集，7 505篇文檔劃分為測試集。在這些文檔中，最長的包含39 831個單詞，最短的包含5個單詞，平均長度為302個單詞。

5.1.3 文檔數(shù)據(jù)格式處理

本文提出的算法包含兩種數(shù)據(jù)格式，文檔的單詞質心向量（word centroid vector）與文檔簽名（signa-ture）。其中，單詞質心向量可表示為文檔標簽中的詞向量對單詞權重的加權均值。

圖4展示了文檔數(shù)據(jù)格式的處理流程。在文檔預處理階段，需要對文檔進行分詞、去非字符、去停用詞、統(tǒng)計詞頻并去高低頻詞。接下來，依據(jù)文檔集合D可計算每個單詞的逆文檔頻率IDF。然后，對于每一篇文檔，計算其包含的每個單詞所對應的TFIDF評分并獲得每個單詞對應的Word2Vec模型詞向量。進一步，TF-IDF評分歸一化后，可以得到相應的文檔標簽和單詞質心向量。其中，本文的詞向量采用的是可自由獲取的Google新聞Word2Vec模型。

Fig.4 Procedure of document formatting圖4 文檔數(shù)據(jù)格式化流程

5.1.4 實驗設置

對于TI-WMD，本文將其應用于k近鄰文檔分類算法，與WMD等其他文檔相似性度量方式進行了對比；對于層次化查詢，本文將其與TI-WMD同時應用于k近鄰文檔分類算法并與PrefetchPrune進行了對比，它們都是近似的文檔分類方法。

在k近鄰文檔分類實驗中，本文將訓練集按照80/20的比例劃分成訓練/驗證集合，用于優(yōu)化kNN分類算法中的參數(shù)k，其中k∈{1,2,…,20}；在近似k近鄰文檔分類實驗中，本文不再優(yōu)化kNN算法中的參數(shù)，而是采用已經(jīng)優(yōu)化過的參數(shù)k。

最后，本文關注查詢參數(shù)對查詢效果與查詢效率的影響。在查詢檢索實驗中，本文通過改變參數(shù)來觀察層次化查詢的效果和效率變化情況以及與PrefetchPrune的效率對比情況。

5.2 k近鄰文檔分類實驗

本實驗的目的是驗證基于TF-IDF的單詞移動距離度量方式能夠有效地衡量文檔之間的相似性。

5.2.1 效果度量

本文采用文檔分類錯誤率來對k近鄰文檔分類的效果進行評估。文檔分類錯誤率越低，文檔分類的效果越好，對應的度量方式越能表達文檔間的相似性。

分類錯誤率：測試集中分類結果與標簽不同的文檔所占的百分比即為分類錯誤率。

5.2.2 TI-WMD與其他度量方式的比較

圖5展示了在不同的相似性度量方式下，k近鄰文檔分類在兩個文檔數(shù)據(jù)集上的實驗結果。其中WMD表示文獻[1]中提出的單詞移動距離，TI-WMD表示本文改進的基于TF-IDF的單詞移動距離，TIWCD表示基于TF-IDF的單詞質心距離，RTI-WMD表示松弛的TI-WMD。

Fig.5 Error rate of kNN document classification圖5 kNN文檔分類錯誤率

實驗結果表明，與其他度量方式相比，TI-WMD具有最低的文檔分類錯誤率，這是因為TI-WMD不僅與WMD類似地通過EMD融合了Word2Vec模型表達的語義信息，而且采用了TF-IDF評分作為單詞重要性評估。其次，WMD相對于TI-WCD、RTIWMD的優(yōu)勢是融合EMD進行了單詞流動的優(yōu)化。這里，RTI-WMD與文獻[1]中提出的RWMD類似，為對稱的RTI-WMD1與RTI-WMD2的最大值，它具有相對較低的文檔分類錯誤率。TI-WCD是TI-WMD的一個比較松弛的下界，其錯誤率比TI-WMD、WMD、RTI-WMD都要高，這是因為它完全沒有考慮單詞流動，而是直接計算文檔的單詞質心間的距離。

另外，在文獻[1]中，與LSI、LDA、TF-IDF等經(jīng)典的文檔相似性度量方式相比，WMD度量應用于k近鄰文檔分類時，在8個數(shù)據(jù)集上具有最低的平均分類錯誤率。因此，TI-WMD度量也能夠較為有效地衡量文檔之間的相似性。

5.3 近似的k近鄰文檔分類實驗

本實驗的目的是驗證k近鄰文檔分類在使用層次化查詢方法時依然具有很好的效果。

5.3.1 效果度量

本文依然采用文檔分類錯誤率來對近似k近鄰文檔分類的效果進行評估。文檔分類錯誤率越低，近似k近鄰文檔分類與近似k近鄰查找算法的效果越好。

5.3.2 HQ-NN與PrefetchPrune-NN的比較

Fig.6 Error rate of approximate k-NN on Reuters圖6 在Reuters上的近似k-NN文檔分類錯誤率

Fig.7 Error rate of approximate k-NN on 20News圖7 在20News上的近似k-NN文檔分類錯誤率

圖6和圖7展示了HQ-NN與PrefetchPrune-NN算法在兩個數(shù)據(jù)集上進行近似k近鄰文檔分類對比實驗的結果。HQ-NN采用層次化查詢獲取k近鄰，PrefetchPrune-NN采用PrefetchPrune方法獲取k近鄰。

實驗結果表明，文檔分類的錯誤率隨著參數(shù)m在范圍1～20內逐漸減小并趨向穩(wěn)定（如4.4.2小節(jié)查詢策略中所述，參數(shù)m用來控制候選文檔集的大?。?。這是因為參數(shù)m越大，候選文檔集合越大，獲取準確的k近鄰的數(shù)量就會增加。需注意的是，與Prefetch-Prune-NN算法相比，HQ-NN算法的文檔分類錯誤率更低。這是因為HQ-NN算法采用多探尋局部敏感哈希查詢方法探測候選哈希桶以及附近的哈希桶來獲取候選文檔集合，它導致查詢盡管沒有獲取到TIWCD度量下準確的候選文檔集，卻使得候選文檔集合包含TI-WMD度量下準確的k近鄰的可能性更大。

因此，近似k近鄰文檔分類實驗結果反映了，參數(shù)m在范圍1～20內變化時，層次化查詢相對Prefetch-Prune在一定程度上更容易獲得TI-WMD度量下準確的k近鄰。

5.4 查詢實驗

本實驗的目的是驗證TI-WMD度量下的層次化查詢方法所具有的優(yōu)勢。

5.4.1 查詢文檔集合

本文在測試集中隨機挑選200篇文檔作為查詢文檔集。

5.4.2 效果與效率度量

本文采用3個不同度量指標來對層次化查詢方法進行評估。

（1）準確率（Precision）。給定一個文檔查詢q，使為TI-WMD度量下的k近鄰，層次化查詢方法返回其近似k近鄰O={o1,o2,…,ok}。那么層次化查詢方法的準確率用符號γ(q)表示，它可以被計算如式（11）所示。

在接下來的實驗中，本文使用準確率在查詢集合上的均值。

（2）平均響應時間（average response time，ART）。響應時間主要由兩部分組成，多探尋局部敏感哈希查詢和過濾-細化框架。為了使結論更一般化，本文采用平均響應時間來對算法的性能進行評估。其中，ti和nq分別用來描述第i個查詢的時間代價和查詢集合的容量。

（3）加速比（speedup ratio）。它為預取剪枝方法的平均響應時間與層次化查詢的平均響應時間的比率。如式（13）所示，符號α被用來表示加速比。

5.4.3 算法參數(shù)的影響

有很多不同的參數(shù)會對查詢結果的準確率和查詢的平均響應時間造成影響。這里主要考慮參數(shù)m對結果的影響。對于多探尋局部敏感哈希查詢中的參數(shù)W、L、T與M的設置要求是使其測試召回率不小于0.9。在實驗過程中，本文會調整參數(shù)m來對層次化查詢方法進行評估，其中候選文檔集的大小為mk。

圖8展示了層次化查詢在20Newsgroups和Reuters數(shù)據(jù)集上的準確率實驗結果。實驗結果表明，在參數(shù)m一定的情況下，準確率隨著k在范圍3～50內逐步增大，這是因為準確率評估指標是通過計算文檔比率來確定的，查詢文檔數(shù)目k越大，結果越具有一般性。其中，m是查詢參數(shù)，它決定了候選文檔集的大小。m越大，候選文檔集包含目標文檔的可能性越大，因此對于k-NN查詢，查詢準確率隨著參數(shù)m的增加而變大。然而，從實驗結果中可以發(fā)現(xiàn)，查詢準確率隨著參數(shù)m增大的程度卻趨向于平緩。這印證了前面的分析，m增大到一定程度后，候選文檔集會包含目標文檔集的所有文檔。

Fig.8 Precision of hierarchical query圖8 層次化查詢的準確率

圖9展示了層次化查詢在20Newsgroups和Reuters數(shù)據(jù)集上的平均響應時間。實驗結果表明，在參數(shù)m一定的情況下，平均響應時間隨著k在范圍1～20內接近線性增長。這是因為在參數(shù)m一定的情況下，候選文檔集的大小隨著k接近線性關系，那么采用過濾-細化框架從候選文檔集中獲取目標文檔的時間就與k接近線性關系，而采用局部敏感哈希方法獲取候選文檔集的響應時間相對這部分時間更小。從實驗結果可以發(fā)現(xiàn)，平均響應時間隨著參數(shù)m增大的程度卻并沒有趨向于平緩。

Fig.9 ART of hierarchical query圖9 層次化查詢的平均響應時間

結合這兩部分的分析可以知道，層次化查詢的準確性和平均響應時間在參數(shù)m的選擇上存在一定的矛盾。m越大，查詢準確率越高，而查詢的平均響應時間也越大，即效果越好，效率越差。因此，選取合適的參數(shù)m對層次化查詢的效果和效率進行折衷就十分必要。

5.4.4 與預取剪枝方法的性能比較

圖10和圖11展示了層次化查詢與PrefetchPrune在Reuters和20Newsgroup兩個數(shù)據(jù)集上的性能對比實驗結果。實驗結果表明，在參數(shù)m一定的情況下，層次化查詢和預取剪枝方法的平均響應時間隨著k在范圍1～20內逐漸增加，但是加速比卻隨著k在范圍1～20內快速下降。

Fig.10 Effect ofmon speedup ratio圖10 參數(shù)m對加速比的影響

Fig.11 Performance comparison of HQ and PrefetchPrune(m=3)圖11 HQ與PrefetchPrune的性能對比(m=3)

與預取剪枝方法相比，層次化查詢是通過局部敏感哈希索引的方式獲取候選文檔集，而不是線性查詢，這使得它可以不受數(shù)據(jù)集規(guī)模的限制。從候選文檔集中獲取目標文檔，層次化查詢和預取剪枝方法都涉及到單詞移動距離的計算。然而，Reuters和20Newsgroup數(shù)據(jù)集經(jīng)過預處理后在內存中所占的空間只有7.1 MB和13.5 MB。數(shù)據(jù)規(guī)模較小使得層次化查詢相對于預取剪枝方法在獲取候選文檔集時所減少的響應時間沒有發(fā)生明顯變化。并且，從候選文檔集中獲取目標文檔的響應時間卻會隨著k逐漸增加。這兩方面的原因導致了加速比隨著k在范圍1～20內快速下降。

另一方面，加速比也會隨著參數(shù)m的增加而變小，這是因為參數(shù)m的增加使得候選文檔集的大小增加，進而會有更多的單詞移動距離計算開銷。

6 總結

本文對單詞移動距離進行了改進，考慮到單詞對于文檔的重要性而采用TF-IDF評分作為單詞權重，從而使得改進后的單詞移動距離（TI-WMD）在衡量文檔相似性時更有效。然后，為了解決單詞移動距離度量下的文檔查詢性能瓶頸問題，本文提出了一種近似的層次化查詢方法。它采用局部敏感哈希方法在內存中為原始文檔集合構建哈希索引，使得查詢時可以有效地將目標文檔集限制在一個較小的候選文檔集中，并采用過濾-細化框架對候選文檔集進行剪枝，從而提高查詢的效率。在兩個公開文檔數(shù)據(jù)集上的實驗結果表明，TI-WMD在衡量文檔相似性上相對于WMD更有效，層次化查詢方法相對于PrefetchPrune方法具有更好的效果和效率，并且參數(shù)的選擇對層次化查詢的效果和效率也有著重要的影響。