王明文，洪 歡，江愛文，左家莉

(江西師范大學(xué) 計算機信息工程學(xué)院，江西 南昌 330022)

基于詞重要性的信息檢索圖模型

王明文，洪 歡，江愛文，左家莉

(江西師范大學(xué) 計算機信息工程學(xué)院，江西 南昌 330022)

在信息檢索建模中，確定索引詞項在文檔中的重要性是一項重要內(nèi)容。以詞袋(bag-of-word)的形式表示文檔來建立檢索模型的方法中大多是基于詞項獨立性假設(shè)，用TF和IDF的函數(shù)來計算詞項的重要性，并未考慮詞項之間的關(guān)系。該文采用基于詞項圖(graph-of-word)的文檔表示形式來捕獲詞項間的依賴關(guān)系，提出了一種新的基于詞重要性的信息檢索圖模型TI-IDF。根據(jù)詞項圖得到文檔中詞項的共現(xiàn)矩陣和詞項間的概率轉(zhuǎn)移矩陣，通過馬爾科夫鏈計算方法來確定詞項在文檔中的重要性(Term Importance, TI)，并以此替代索引過程中傳統(tǒng)的詞項頻率TF。該模型具有更好的魯棒性，我們在國際公開數(shù)據(jù)集上與傳統(tǒng)的檢索模型進行了比較。實驗結(jié)果表明，該文提出的模型都要優(yōu)于BM25，且在大多數(shù)情況下優(yōu)于BM25的擴展模型、TW-IDF等模型。

詞項重要性；詞項圖；檢索模型；TI-IDF

1 引言

隨著互聯(lián)網(wǎng)的迅速發(fā)展，用戶越來越依賴Google、百度、搜狗等搜索引擎來獲取他們?nèi)粘Ｉ钪兴枰男畔?。對于用戶而言，都希望能找到與他們給定的需求(查詢)最相關(guān)的信息。這就涉及到在信息檢索過程中，如何定義一個針對給定查詢計算文檔排名的得分函數(shù)?，F(xiàn)有的檢索模型大多是以詞袋(bag-of-word)的形式，即詞項頻率TF信息，來表示一篇文檔。這些模型包括向量空間模型[1](TF-IDF)，概率模型[2](BM25)和使用Dirichlet先驗的語言模型[3]等，且詞項重要性的計算均建立在詞項的獨立性假設(shè)上，并未考慮詞項之間的相關(guān)性。Rijsbergen[4]已經(jīng)驗證了詞項間的依賴關(guān)系在信息檢索等文本處理中能起到重要的作用。但這種依賴關(guān)系目前并沒有得到足夠的重視，主要原因在于計算代價比較大，缺乏有效的表達形式。

本文基于詞項圖(graph-of-word)的形式提出一種新的、有效的文檔表示方法。對每篇文檔建立一個關(guān)于詞項的無向有權(quán)圖，圖中的節(jié)點對應(yīng)了文檔中的索引詞項，邊代表兩個詞項節(jié)點的共現(xiàn)關(guān)系，邊上的權(quán)重表示兩個詞項在文檔中共現(xiàn)的句子數(shù)。根據(jù)詞項圖，可以得到文檔中詞項的共現(xiàn)矩陣，進而得到詞項的概率轉(zhuǎn)移矩陣。最后，通過馬爾科夫鏈計算方法確定詞項在文檔中的重要性(Term Importance，TI)，結(jié)合Zhai等[5-6]提出的啟發(fā)式約束條件，得到檢索模型TI-IDF。詞項圖充分地考慮到詞項之間的依賴關(guān)系，比簡單的文檔向量保留了更多有用的信息，且構(gòu)建過程不需要太多額外的時間開銷，因此不影響檢索過程的時效性。通過對比實驗發(fā)現(xiàn)，本文的檢索模型取得的檢索結(jié)果都要優(yōu)于BM25，并在大多數(shù)情況下優(yōu)于BM25的擴展模型、TW-IDF等模型。

本文接下來第二部分將介紹相關(guān)工作；第三部分重點介紹詞項圖的構(gòu)建以及詞項重要性TI的計算；第四部分將主要介紹本文提出的檢索模型TI-IDF；與已有檢索模型的對比實驗和結(jié)果分析將在第五部分給出；最后，進行總結(jié)以及給出下一步工作。

2 相關(guān)工作

基于圖的算法已經(jīng)被成功運用于檢索中，典型的代表是L Page等[7]提出的PageRank。該算法使用圖形表示W(wǎng)eb結(jié)構(gòu)，根據(jù)圖結(jié)構(gòu)計算出網(wǎng)頁的重要性。相應(yīng)地，如何構(gòu)建檢索中文檔的詞項圖結(jié)構(gòu)，也就是考慮詞項之間的依賴關(guān)系，以及如何根據(jù)詞項圖確定詞項在文本中的重要性，成為信息檢索模型的一個重要課題。Blanco和Lioma根據(jù)詞項之間的共現(xiàn)關(guān)系，構(gòu)造出文檔內(nèi)詞項的無向無權(quán)圖，并采用類似PageRank的隨機游走方法計算詞項在文檔中的權(quán)重[8-9]。Rousseau等[10]依據(jù)詞項之間的共現(xiàn)關(guān)系以及詞項間的順序關(guān)系，構(gòu)造出文檔詞項的一個有向無權(quán)圖，并根據(jù)該圖中節(jié)點(詞項)的入度數(shù)確定詞項的權(quán)重。上述工作均以固定滑動窗口的形式統(tǒng)計詞項間的共現(xiàn)關(guān)系，特別地，Blanco和Lioma還依據(jù)調(diào)整窗口的大小計算詞項在文檔中的權(quán)重。本文與前述工作的主要區(qū)別是： (1)以句子為計算窗口統(tǒng)計詞項共現(xiàn)次數(shù)，其優(yōu)點在于句子是一個相對完整的語義單元，因此不需要進行窗口大小的調(diào)整以及考慮詞項間的順序關(guān)系；(2)本文構(gòu)造的是文檔內(nèi)詞項的無向有權(quán)圖，邊上的權(quán)重由兩個詞項共現(xiàn)的句子數(shù)確定；(3)本文采用馬爾科夫鏈計算方法來確定詞項在文檔中的重要性。另外，洪歡和甘麗新等[11-12]通過構(gòu)建整個文檔集中詞項間的Markov網(wǎng)絡(luò)圖形結(jié)構(gòu)，提取出相應(yīng)的詞項團用于檢索中(即將與查詢詞語義緊湊的詞項用于修正該詞項在文檔中的重要性)，從而取得較好的檢索效果，這也體現(xiàn)了圖模型很好地運用在查詢擴展中。

Zhai等[5-6]提出信息檢索模型需要滿足的一些啟發(fā)式約束條件，并對一些具有代表性的模型的得分函數(shù)進行驗證，發(fā)現(xiàn)當?shù)梅趾瘮?shù)滿足越多的約束條件，取得的檢索效果就越好。Rousseau等[10]則從這些檢索模型的得分函數(shù)中歸納出三類詞項頻率歸一化方法，包括： 1)凹面函數(shù)方法(TFk或者TFl)，該方法主要是用于解決詞項在文檔內(nèi)出現(xiàn)的次數(shù)線性增長時，查詢檢索到該文檔的概率(文檔得分)也線性增長，而應(yīng)該是服從一個衰減函數(shù)的問題。舉例來說，文檔中出現(xiàn)查詢詞項為兩次的文檔得分減去為一次的得分要大于出現(xiàn)101次和100次的得分差；2)主軸文檔長度歸一化方法[13](TFp)，該方法是用來防止查詢傾向于長度長的文檔，也就是對文檔的長度進行歸一化；3)低邊界規(guī)則化方法(TFδ)，該方法一般是結(jié)合TFp來使用，用于防止對長文檔過度懲罰而增加一個補償因子，因為Zhai等[14-15]提出當文檔長度非常長的時候，采用TFp歸一化方法的BM25檢索模型不能取得很好的檢索結(jié)果，而加入了TFδ方法后可以改善檢索結(jié)果。具體的歸一化方法如式(1)～(4)所示。

(1)

(2)

(3)

(4)

其中，tf(t,d)表示詞項t在文檔內(nèi)出現(xiàn)的次數(shù)，k1是經(jīng)驗參數(shù)，b是文檔長度傾斜參數(shù)，用于文檔長度的歸一化，在不同的模型中會有不同的取值，avdl表示數(shù)據(jù)集中文檔的平均長度， |d|表示當前檢索文檔的長度，參數(shù)δ是補償因子。

Rousseau等[10]將已有的一些形式為TF×IDF檢索模型的得分函數(shù)歸納成由以上三類TF歸一化方法的不同組合，不同的檢索模型采用不同的組合方式。例如，BM25模型的得分函數(shù)可以認為是TFk、TFp與IDF的組合形式，記作TFkοp×IDF，Singhal等[1]提出的Piv模型得分函數(shù)是TFl、TFp與IDF的組合形式，記作TFpοl×IDF。也可以用單獨一類的歸一化方法與IDF組合成一些得分函數(shù)形式，例如，TFl×IDF和TFk×IDF等。

3 詞項重要性度量

受日常生活中全國飛機航線圖的啟發(fā)，如果把文檔中的詞項看作航線圖中的機場，詞項之間的共現(xiàn)關(guān)系看作是航線圖中的航線，由所有的航線構(gòu)成了整個完整的航線圖，相應(yīng)地，所有詞項之間的共現(xiàn)關(guān)系組成了文檔的詞項圖。觀察飛機航線圖可以發(fā)現(xiàn)，一些重要的城市存在多條飛達該城市的航線，這些城市一般都是中心城市。相應(yīng)地在詞項圖中，如果一個詞項能夠很好地概括文檔的內(nèi)容，那么該詞項的度數(shù)會比較高，相應(yīng)地，該詞項在文檔中權(quán)重應(yīng)該比較高。以下我們將具體介紹詞項重要性的計算方法。

3.1 詞項圖(Graph-of-word)

我們將每篇文檔用詞項的無向有權(quán)圖(即詞項圖)來表示。在詞項圖中，節(jié)點表示文檔中出現(xiàn)的索引詞項，詞項之間存在的無向邊表示兩個詞項在文檔中的某一個句子中共現(xiàn)，無向邊上的權(quán)重則代表兩個詞項在文檔中共現(xiàn)的句子個數(shù)。選擇以句子為計算窗口來統(tǒng)計詞項之間的共現(xiàn)次數(shù)，是因為一個句子所表達的語義會更為完整，句子中詞項之間的關(guān)系也較為緊湊。已有的工作[8-10]均以滑動窗口的形式來統(tǒng)計詞項間的關(guān)系，這需要額外地調(diào)整滑動窗口的大小，增加計算開銷，并且許多跨句的詞項之間的關(guān)系并沒有同一句子中共現(xiàn)的詞項關(guān)系密切。舉一個簡單的示例，我們?nèi)REC-1目錄下的WSJ數(shù)據(jù)集中第一篇文檔分句后的三個句子，它們經(jīng)詞干化和去停用詞后得到： “rosenfieldcbexecutindustrisourc.industrisourcputpropoacquisitmillion.rosenfieldofficejohnblairreachcomment.”，由這部分文本內(nèi)容構(gòu)建出詞項圖如圖1所示。

圖1 詞項圖示例

在圖1中，節(jié)點表示文檔內(nèi)的詞項，邊表示在某一個句子中詞項間有共現(xiàn)關(guān)系，黑色以及加粗的邊分別代表兩個詞項共現(xiàn)的句子數(shù)為1和2。我們會發(fā)現(xiàn)，文檔內(nèi)每一個句子中的詞項關(guān)系都構(gòu)成一個完全多邊形，而文檔的詞項圖則由這n個(n代表文檔的句子數(shù))完全多邊形組合而成。

3.2 詞項圖構(gòu)建過程

詞項圖的構(gòu)建主要包括三個步驟。

1) 從給定的數(shù)據(jù)集中提取出每篇文檔的文本內(nèi)容，并采用LingPipe*http://alias-i.com/lingpipe/index.html程序?qū)λ形臋n進行分句。

2) 去停用詞及詞干化： 對每篇文檔的文本內(nèi)容采用Terrier*http://terrier.org/download停用詞表去除停用詞并采用Porter的詞干化程序進行詞干化。這一過程能夠幫助縮小詞項圖的規(guī)模，并更好地捕獲詞項之間的依賴關(guān)系。

3) 對每篇文檔依次構(gòu)建詞項圖： 統(tǒng)計每篇文檔內(nèi)所有詞項之間的共現(xiàn)關(guān)系(以句子為計算窗口)，并構(gòu)建出該文檔內(nèi)詞項的無向有權(quán)圖。采用無向有權(quán)圖的理由有兩個：a)無向圖的構(gòu)建過程更簡單，不用考慮詞項之間的順序關(guān)系；b)邊權(quán)重可以提高那些在文檔中經(jīng)常出現(xiàn)的詞項的權(quán)重，因為這些詞項可能是文檔的中心詞(類似保留詞項的頻率TF信息)。最后，通過詞項圖可以得到每篇文檔內(nèi)詞項的共現(xiàn)矩陣，有利于后續(xù)詞項重要性的計算。

3.3 詞項重要性度量

本文采用馬爾科夫鏈計算方法來確定詞項在文檔內(nèi)的重要性。馬爾科夫鏈計算方法是一種關(guān)于事件發(fā)生的概率計算方法，它利用目前的初始狀態(tài)概率向量與狀態(tài)轉(zhuǎn)移概率矩陣，確定事物未來的狀態(tài)。馬爾科夫鏈計算過程包括三部分。

1) 確定初始狀態(tài)概率向量 B0： 相應(yīng)地，在本文中就是確定文檔內(nèi)每個詞項的初始概率如式(5)所示。

(5)

其中，M表示文檔內(nèi)所有不同的詞項數(shù)。

2) 計算狀態(tài)轉(zhuǎn)移概率矩陣： 根據(jù)構(gòu)建出的詞項圖得到文檔內(nèi)詞項的共現(xiàn)矩陣，再通過共現(xiàn)矩陣得到詞項間的概率轉(zhuǎn)移矩陣 PN×N,Pij(i,j=0,1,…,M-1)的計算方法如式(6)所示。

(6)

其中，ni,j表示兩個詞項在文檔內(nèi)共現(xiàn)的句子數(shù)。式(6)中計算轉(zhuǎn)移概率 Pij時只考慮了詞項在同一句中(局部)的共現(xiàn)關(guān)系，考慮到詞項在一篇文檔內(nèi)的全局共現(xiàn)關(guān)系，采用類似PageRank中加入阻尼因子的方法，將公式(6)修改為式(7)。

(7)

其中，d表示阻尼因子，取默認值0.15(實驗中未進行調(diào)整，文獻[12]驗證了該參數(shù)的最優(yōu)值為0.15)，其他符號和之前公式的意義一致。

3) 計算轉(zhuǎn)移的結(jié)果： 馬爾科夫鏈計算方法有一個重要的性質(zhì)[17]，當概率轉(zhuǎn)移矩陣 P經(jīng)過m步概率轉(zhuǎn)移變成正規(guī)概率矩陣 U，代入馬爾科夫鏈計算模型 Bk=B0*Uk中，再經(jīng)過若干步(k步)會發(fā)現(xiàn) Bk將收斂，即 B=B*U。這里我們給出正規(guī)概率矩陣的定義：

定義1 一概率矩陣 P，若它的某次方 Pm的所有元素均為正數(shù)，則稱其為正規(guī)概率矩陣[17]。

通過式(7)我們發(fā)現(xiàn)，本文使用的概率轉(zhuǎn)移矩陣 P已經(jīng)是正規(guī)概率矩陣。因此，實驗中直接將轉(zhuǎn)移矩陣 P代入馬爾科夫鏈計算模型中，經(jīng)過若干步(k=8-12)迭代 B將會收斂。

4) 確定詞項的TI： 收斂得到的狀態(tài)概率向量 B中的概率將用于計算詞項在文檔內(nèi)的重要性TI，具體的計算如式(8)所示。

(8)

其中，i表示文檔d中詞項對應(yīng)的下標，Bi表示收斂后的向量 B中第i個元素(詞項)對應(yīng)的概率。

4 檢索模型構(gòu)建

類似已有的檢索模型TF-IDF以及BM25的得分函數(shù)，我們定義了一個新的檢索模型TI-IDF。同樣地，我們將關(guān)于詞項頻率(TF)歸一化方法運用在TI上，這些歸一化方法已經(jīng)被驗證可以很好地滿足信息檢索中的啟發(fā)式約束條件[5-6]。

4.1 TF-IDF和BM25

在本文中，我們將對本文提出的TI-IDF模型與TF-IDF、BM25以及它們的一些變形作對比實驗。對于TF-IDF檢索模型，我們主要參照Singhal等[1]使用主軸文檔長度歸一化后的模型TFpοl×IDF，記作Piv[6]，該模型的得分函數(shù)如式(9)所示。

(9)

其中，b是經(jīng)驗參數(shù)，一般取默認值為0.2(實驗中將調(diào)整該參數(shù))，df(t)表示詞項t的出現(xiàn)的文檔數(shù)，N表示整個數(shù)據(jù)集中包含的文檔數(shù)。

對于BM25模型，我們參照的是Robertson等[2]給出的模型的得分函數(shù)，也稱OkapiBM25(實驗中簡稱Okapi)。Okapi中的IDF部分在df(t)>N/2出現(xiàn)負數(shù)時，會導(dǎo)致檢索效果下降(實驗部分將給出驗證)。為了讓Okapi模型更好地滿足Zhai[5-6]提出的啟發(fā)式約束條件，我們將Okapi的IDF部分進行修正，修正后的模型稱為mod-Okapi[5]。各模型對應(yīng)的得分函數(shù)如式(10)和式(11)所示。

(10)

(11)

其中，K=k1×(1-b+b×|d|/avdl),b是經(jīng)驗參數(shù)，一般取值0.75(實驗中將調(diào)整該參數(shù))，k1取默認經(jīng)驗值1.2[2]。

在本文的實驗中，我們還將和Zhai等[6]提出的TF-IDF和BM25的擴展模型作對比實驗，這些擴展模型本質(zhì)上是把TFδ歸一化方法也組合進來，具體模型的得分函數(shù)被記作Piv+和BM25+[6]，在本文中分別對應(yīng)TFδοpοl×IDF和TFδοkοp×IDF，實驗中δ參照文獻[6]取默認值1.0。

4.2TI-IDF

類似已有TF×IDF形式的檢索模型得分函數(shù)，并結(jié)合凹面函數(shù)和主軸文檔長度歸一化兩種方法，我們定義出本文模型的新的得分函數(shù):TIpol×IDF和TIkοp×IDF，參照公式(9)和(11)給出具體的形式。

(12)

(13)

其中，ti(t,d)表示詞項在文檔中的權(quán)重(即上文所說的TI)，式中的其他符號和之前公式的意義一致。經(jīng)過實驗發(fā)現(xiàn)b取值0.06，且不需要調(diào)整。由于參數(shù)b非常小，盡管文檔長度 |d|遠比avdl大，但乘以參數(shù)b后，b×|d|/avdl依然比較小，不會造成對長文檔的過度懲罰。因此，對于本文的TI-IDF模型不需要使用類似TF的低邊界歸一化方法TFδ。

公式(12)和(13)中我們采用ti(t,d)*10的形式，乘以10是因為計算得到的詞項重要性TI一般要比詞項頻率TF小一個數(shù)量級，為了適應(yīng)TF歸一化方法，所以將TI的值乘以10。

5 實驗設(shè)計與分析

5.1 數(shù)據(jù)集與評價指標

本文采用的數(shù)據(jù)集是TREC-1 (AdhocTestCollections)中的四個子數(shù)據(jù)集，分別是：AP(美聯(lián)社新聞專線故事文章)、DOE(美國能源部技術(shù)文章摘要)、WSJ(華爾街日報文章)和ZIFF(Ziff-Davis出版公司文章)。TREC-1是用于TREC中的adhoc檢索任務(wù)的數(shù)據(jù)集，可以很好地判斷檢索模型的效果，數(shù)據(jù)集文檔保存在disks1&2中。查詢選用TREC-1adhoctopics.51-100， 在這些查詢文件

中只有title域的內(nèi)容作為查詢用，相關(guān)判斷集合選取查詢對應(yīng)的qrels.51-100文件。數(shù)據(jù)集(經(jīng)過分詞以及詞干化處理)的具體情況如表1所示。

表1 TREC1中的數(shù)據(jù)集

我們采用的評價指標是3-avg和11-avg，分別代表一組測試查詢在三個召回率點(0.2, 0.5, 0.8)和11個召回率點(0, 0.1, 0.2, ……, 1.0)上精確率的平均值。這種平均精度-召回率數(shù)值已成為信息檢索系統(tǒng)的標準評價指標，在信息檢索文獻中被廣泛采用。

5.2 實驗結(jié)果與分析

5.2.1 已有檢索模型實驗結(jié)果

本文首先對比了檢索模型BM25和TF-IDF使用不同歸一化方法組合后的實驗結(jié)果。也就是使用在第四節(jié)介紹的各種得分函數(shù)的檢索結(jié)果，實驗中所有得分函數(shù)中的參數(shù)k1和δ的取值取參照文獻中[6]確定的經(jīng)驗參數(shù)值k1=1.2,δ=1.0；對于參數(shù)b，實驗結(jié)果分為固定b和調(diào)整b兩種，具體的結(jié)果分別如表2和表3所示。

表2 固定參數(shù)b時，已有檢索模型的實驗結(jié)果

注： 加粗數(shù)字表示最好結(jié)果

表3 調(diào)整參數(shù)b時，已有檢索模型的實驗結(jié)果

續(xù)表

通過表2和表3我們發(fā)現(xiàn)，改進BM25模型得分函數(shù)中IDF部分后的mod-Okapi模型的檢索結(jié)果確實都要優(yōu)于初始的Okapi模型。實驗中，一開始我們將模型TI-IDF的得分函數(shù)中參數(shù)取值和TF-IDF模型一致，發(fā)現(xiàn)所得的檢索效果不是很理想。究其原因，主要是詞項重要性TI的取值不會像TF一樣受到文檔長度很大的影響，也就是在采用主軸文檔長度歸一化方法TFp時，參數(shù)b的取值應(yīng)該比較小，在接下來的實驗中我們將驗證這一觀點。

5.2.2 主軸文檔長度歸一化方法中參數(shù)b對TI-IDF模型的影響

在實驗中，TI-IDF檢索模型我們使用的得分函數(shù)是：TIpol×IDF，主要是它的檢索結(jié)果都要優(yōu)于得分函數(shù)TIkop×IDF。為了驗證TI受文檔長度的影響不會很明顯，我們分析得分函數(shù)中的TIp歸一化方法內(nèi)文檔傾斜參數(shù)b對TI-IDF模型檢索結(jié)果的影響，具體如圖2所示。

圖2 參數(shù)b對結(jié)果的影響

從圖2中我們發(fā)現(xiàn)，隨著參數(shù)b的增長，TI-IDF模型的檢索效果開始有小規(guī)模提高，當b=0.06時相對地穩(wěn)健，之后逐漸下降。特別地，當參數(shù)b=0時，也就是不采用主軸文檔長度歸一化方法，檢索結(jié)果也較好；而在b=0.2時，檢索結(jié)果已經(jīng)變得很差，這也驗證了5.2.1節(jié)中給出的觀點。因此，實驗中我們將TI-IDF模型中參數(shù)b的取值設(shè)為達到穩(wěn)健時的0.06，它的取值比Piv(b=0.2)和BM25(b=0.75)中的經(jīng)驗取值要小一個數(shù)量級，究其原因是，雖然文檔的長度變長，所包含的句子數(shù)以及詞項數(shù)也隨之增加，但文檔總的概率1沒有變化，TI增長的幅度較TF小得多，且在同一句話中多次出現(xiàn)的詞項與其他詞項之間只算一次共現(xiàn)。

5.2.3TI-IDF對比實驗結(jié)果

首先，為了驗證本文中采用基于詞項圖的文檔表示形式的檢索模型要優(yōu)于傳統(tǒng)的以詞袋形式來表示文檔的檢索模型，實驗中我們分別對比在不使用歸一化方法情況下，TF與TI、TF-IDF與TI-IDF的實驗結(jié)果，具體結(jié)果如表4所示。

表4 不使用歸一化方法的對比實驗結(jié)果

從表4我們發(fā)現(xiàn)，在四個數(shù)據(jù)集上TI都要優(yōu)于TF，且TI-IDF都要優(yōu)于TF-IDF，說明本文提出的基于詞項圖來表示文檔比傳統(tǒng)基于詞袋形式保留了更多有用的信息。

最后，我們將TI-IDF模型取得最好的檢索結(jié)果時的得分函數(shù)TIpοl×IDF與已有檢索模型中取得最好的檢索結(jié)果，包括固定參數(shù)b和調(diào)整參數(shù)b(分別記作Best和T_Best)以及初始的BM25模型(Okapi)作比較。另外，我們將Rousseau等[10]提出的檢索模型TW-IDF也用于對比實驗(實驗中參照原文取計算窗口大小為4來構(gòu)建文檔的有向無權(quán)圖，得分函數(shù)使用TWpοl×IDF，通過實驗取得到最好檢索結(jié)果的參數(shù)b,b=0.04)。具體對比實驗的結(jié)果如表5所示。

表5 使用歸一化方法的對比實驗結(jié)果

表5顯示本文的TI-IDF模型可以取得和Best、T_Best以及TW-IDF相當?shù)臋z索結(jié)果，且都要優(yōu)于初始的BM25 (Okapi)模型。在DOE和ZIFF數(shù)據(jù)集上TI-IDF的檢索結(jié)果最優(yōu)。另外，本文的TI-IDF模型和TW-IDF模型一樣無需參數(shù)調(diào)整，具有更好的魯棒性，對過長的文檔不會造成過度懲罰，因此都不需要低邊界歸一化方法TFδ。對于構(gòu)建每篇文檔的詞項圖造成的額外時間開銷，可以通過并行平臺來解決，因為詞項圖的構(gòu)建以及TI的計算過程中文檔集中所有文檔相互之間不存在依賴關(guān)系，且都可以離線計算。在AP和WSJ兩個數(shù)據(jù)集上檢索效果不是最優(yōu)的原因包括： 1)由于AP和WSJ中的文檔是新聞報道文章，存在許多口語化的單詞和長度較短的句子，另外，文章中的許多單詞縮寫、人名、地名等影響分句，也會造成出現(xiàn)一些詞項數(shù)很少的短句，使得文檔內(nèi)詞項與詞項之間的依賴關(guān)系少，這樣不利于捕獲詞項間的依賴關(guān)系，造成構(gòu)建的詞項圖不精確。而TI的取值非常依賴于構(gòu)建的詞項圖，最終導(dǎo)致TI的值不精確。2)本文在對TI進行歸一化的時候，直接使用已有的TF歸一化方法。從表4我們發(fā)現(xiàn)TI-IDF模型的檢索結(jié)果在所有數(shù)據(jù)集上都要優(yōu)于TF-IDF模型，因此，我們相信找到更適合TI的歸一化方法將會取得更好的檢索結(jié)果，在下一步的工作中我們將嘗試找出這些方法。

6 總結(jié)與展望

本文提出一種新的文檔表示形式——詞項圖(graph-of-word)和檢索圖模型TI-IDF，通過詞項圖捕獲詞項之間的依賴關(guān)系，得到詞項的共現(xiàn)矩陣以及概率轉(zhuǎn)移矩陣，然后采用馬爾科夫鏈計算方法確定詞項在文檔中的重要性TI，最后結(jié)合已有的TF歸一化方法，定義一個新的有效的得分函數(shù)TIpοl×IDF用于文檔檢索。實驗證明，本文提出的基于詞重要性的檢索圖模型，在公開測試數(shù)據(jù)集TREC-1上性能都要優(yōu)于BM25，并在大多數(shù)情況下優(yōu)于BM25的擴展模型、Piv及其擴展模型以及TW-IDF。此外，TI-IDF模型無需參數(shù)調(diào)整，較傳統(tǒng)TF-IDF無需增加過多計算開銷，具備良好的檢索性能，且具有更好的魯棒性不會對長文檔造成過度懲罰。為了得到更好的檢索效果，下一步的工作我們將從尋找更適合詞項重要性TI的歸一化方法著手，改進TI-IDF模型的得分函數(shù)。

[1]SinghalA,ChoiJ,HindleD,etal.At&tatTREC-7[J].NISTSPECIALPUBLICATIONSP, 1999: 239-252.

[2]RobertsonSE,WalkerS,JonesS,etal.OkapiatTREC-3[J].NISTSPECIALPUBLICATIONSP, 1995: 109-109.

[3]ZhaiC,LaffertyJ.Astudyofsmoothingmethodsforlanguagemodelsappliedtoadhocinformationretrieval[C]//Proceedingsofthe24thAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.ACM, 2001: 334-342.

[4]VanRijsbergenCJ.Atheoreticalbasisfortheuseofco-occurrencedataininformationretrieval[J].JournalofDocumentation, 1977, 33(2): 106-119.

[5]FangH,TaoT,ZhaiCX.Aformalstudyofinformationretrievalheuristics[C]//Proceedingsofthe27thAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.ACM, 2004: 49-56.

[6]LvY,ZhaiCX.Lower-boundingtermfrequencynormalization[C]//Proceedingsofthe20thACMInternationalConferenceonInformationandKnowledgeManagement.ACM, 2011: 7-16.

[7]PageL,BrinS,MotwaniR,etal.ThePageRankcitationranking:Bringingordertotheweb[J].StanfordInforlab,1999:1-14.

[8]BlancoR,LiomaC.Randomwalktermweightingforinformationretrieval[C]//Proceedingsofthe30thAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.ACM, 2007: 829-830.

[9]BlancoR,LiomaC.Graph-basedtermweightingforinformationretrieval[J].InformationRetrieval, 2012, 15(1): 54-92.

[10]RousseauF,VazirgiannisM.Graph-of-wordandTW-IDF:newapproachtoadhocIR[C]//Proceedingsofthe22ndACMInternationalConferenceonConferenceonInformation&KnowledgeManagement.ACM, 2013: 59-68.

[11] 甘麗新, 涂偉, 王明文, 等. 基于混合相關(guān)的Markov網(wǎng)絡(luò)信息檢索擴展模型[J]. 中文信息學(xué)報, 2013, 27(4): 83-88.

[12] 洪歡, 王明文, 萬劍怡, 等. 基于迭代方法的多層Markov網(wǎng)絡(luò)信息檢索模型[J]. 中文信息學(xué)報, 2013, 27(5): 122-128.

[13]SinghalA,BuckleyC,MitraM.Pivoteddocumentlengthnormalization[C]//Proceedingsofthe19thAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.ACM, 1996: 21-29.

[14]LvY,ZhaiCX.Whendocumentsareverylong,BM25fails![C]//Proceedingsofthe34thInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.ACM, 2011: 1103-1104.

[15]LvY,ZhaiCX.Adaptivetermfrequencynormalizationforbm25[C]//Proceedingsofthe20thACMInternationalConferenceonInformationandKnowledgeManagement.ACM, 2011: 1985-1988.

[16]RousseauF,VazirgiannisM.CompositionofTFnormalizations:newinsightsonscoringfunctionsforadhocIR[C]//Proceedingsofthe36thInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.ACM, 2013: 917-920.

[17]RhoadesBE.TheconvergenceofmatrixtransformsforcertainMarkovchains[J].StochasticProcessesandtheirApplications, 1979, 9(1): 85-93.

An Information Retrieval Graph Model Based on Term Importance

WANG Mingwen, HONG Huan, JIANG Aiwen, ZUO Jiali

(School of Computer Information Engineering, Jiangxi Normal University, Nanchang， Jiangxi 330022, China)

In information retrieval modeling, to determine the importance of index terms of the documents is an important content. Those retrieval models which use a bag-of-word document representation are mostly based on the term independence assumption, and calculate the terms’ importance by the functions of TF and IDF, without considering about the relationship between terms. In this paper, we used a document representation based on graph-of-word to capture the dependencies between terms, and proposed a novel information graph retrieval model TI-IDF. According to the graph, we obtained the co-occurrence matrix and the probability transfer matrix of terms, then we determined the terms’ importance (TI) by using the Markov chain computing method, and used TI to replace traditional term frequency at indexing time. This model possesses a better robustness, we compared our model with traditional retrieval models on the international public datasets. Experimental results show that, the proposed model is consistently superior to BM25 and better than its extension models, TW-IDF and other models in most cases.

term importance; graph-of-word; retrieval model; TI-IDF

王明文(1964—),博士,教授,博士生導(dǎo)師,主要研究領(lǐng)域為信息檢索、數(shù)據(jù)挖掘、機器學(xué)習(xí)。E-mail:mwwang@jxnu.edu.cn洪歡(1991—),碩士,主要研究領(lǐng)域為信息檢索、數(shù)據(jù)挖掘、自然語言處理。E-mail:honghuan252008@126.com江愛文(1984—),博士,副教授,主要研究領(lǐng)域為多媒體檢索、視覺與語言。E-mail:jiangaiwen@jxnu.edu.cn

1003-0077(2016)04-0134-08

2014-08-14 定稿日期： 2015-03-21

國家自然科學(xué)基金(61272212，61462043，61462045)；江西省自然科學(xué)基金(20122BAB211032，2015BAB217014)

TP391

A