基于數據挖掘的面向話題搜索引擎研究

陳 勇,張佳驥,吳立德,劉海娟

(1.中國電子科技集團公司第五十四研究所,河北石家莊050081;2.復旦大學,上海 200433)

0 引言

目前,無論是在互聯網上還是在機構內部,電子文本文檔的數量都在快速地增加著。通常這些文檔未經處理,雜亂地堆積在一起。這種原始狀態(tài)大大降低了文檔的可利用性,文檔的信息價值無法實現。文本搜索引擎的作用就是幫助人們快速準確地找到符合其檢索需求的相關文檔。因此,文本搜索引擎技術是開發(fā)和利用現有文本文檔的基礎,有著很好的應用前景。

1 問題分析

目前,大多數文檔檢索技術都是以單個詞為處理對象的[1,2]。這種技術有以下缺點。首先,從用戶角度來講,有時讓用戶僅僅使用幾個關鍵詞就把檢索要求描述清楚是一件很困難的事情。檢索需求的模糊不清必然會導致檢索結果的混亂;其次,從關鍵詞檢索技術本身來講,只要一個文檔中出現了檢索關鍵詞,就認為此文檔滿足檢索要求,這樣的簡單匹配方法常常會檢索出很多非相關文檔。

在文檔表示技術方面,目前許多文檔表示方法主要是基于向量空間模型(Vector Space Model)理論的[3,4]。向量空間模型理論也是以單個獨立詞為處理對象,并且假定詞與詞之間是相互獨立的。首先從詞匯表中選擇若干詞作為特征詞,由這些特征詞構成向量空間,然后把文檔集合中的每一個文檔表示為向量空間中的一個向量。基于向量表示就能夠計算兩兩文檔之間的相似度。向量空間模型理論是以詞與詞之間互不關聯和相互獨立為前提的。這一假設與實際情況并不相符,因為,在實際文本中詞與詞之間是相互關聯的。

通過對目前檢索和文檔表示技術的分析,可以發(fā)現檢索效果不佳主要有2個方面的原因。一方面,用戶無法僅僅利用若干關鍵詞就準確地描述出其檢索要求,檢索要求的不明確進而造成了檢索結果的混亂;另一方面,向量空間模型認為詞與詞之間是相互獨立的,因而只能基于單個詞抽取文檔特征,重要的上下文信息沒有得以利用為文檔表示服務。

2 解決方案

為了避免關鍵詞在描述用戶檢索要求方面的局限性,使用示例文檔作為用戶表達檢索要求的方式。一篇示例文檔包含了比若干關鍵詞豐富得多的信息,能夠更全面地代表用戶的檢索要求。這樣,就可以通過計算文檔集合中各個文檔與示例文檔的相似度來找出相關文檔,是否能夠對文檔進行準確表示直接影響著檢索結果的好壞。利用向量空間模型對文檔進行表示的缺點在于：在實際文本中,詞與詞通常是相互關聯而不是獨立的,正是詞與詞的各種搭配組合才使得語言能夠表達各種各樣的概念和豐富多彩的語義。另外,一個詞的具體含義是由上下文中的一些關聯詞決定的,將詞作為相互獨立的個體來看待就忽略了詞與詞之間重要的關聯關系,許多由詞組表達的重要特征就無法被發(fā)現。

在此項研究中,提出了同時抽取單個詞特征以及多詞特征對文檔進行表示的方法,這樣就能夠在多個層次上對文本進行分析,在多種精度上考察文檔間的相似度。之所以有這樣的考慮是因為,一方面,相對于獨立的單個詞而言,詞組包含了詞與詞之間的關聯信息,能夠表達更詳細、更具體的語義,這樣就可以克服基于單個詞方法的缺點;另一方面,與若干關鍵詞相比,示例文檔為抽取有意義的詞組提供了可能。示例文檔由句子組成,描述了一個完整的事件,因此能夠從中抽取有意義的詞組。

要想利用詞組進行文檔間的比較,就需要找出與文檔主題緊密相關的詞組。與文檔主題緊密相關的詞組在文檔中會被反復提及,因此,會以較高的頻率出現。

如何高效地找出這些頻繁出現的詞組是一個需要解決的技術難題。簡單的窮盡算法顯然無法解決這一問題。該項研究能夠成功地解決這一問題,其技術突破點在于首次把數據挖掘技術[5]引入到文檔搜索領域,借助挖掘算法大大提高了抽取文本特征的效率。為了利用數據挖掘算法,把一個文檔看作是一個數據集,把一個句子看作是一個交易記錄,把句子中的詞看作一個項,利用數據挖掘算法找出頻繁項目集,挖掘結果中的頻繁項目集就是頻繁詞組。

文檔相似度的計算是基于2個文檔間發(fā)生匹配的詞組進行的。從信息論的角度來講,2個對象間的相似程度反映的是二者間共享的特點的多寡。常用的基于單個詞計算2個文檔相似程度的公式如式(1)所示：

在研究中,根據基于詞組比較的特點設計了如式(2)所示的文檔相似度計算公式。式(2)考慮了以下3點因素：

①匹配詞組的長度。匹配詞組的長度越長,比較的精度就越細,2個文檔在高精度上的匹配要比在低精度上的匹配更有意義。因此,應被賦予更高的權值;

②相互匹配詞組的數量。2個文檔間相互匹配的詞組越多,那么其相似度越高;

③相互匹配詞組在2個文檔中發(fā)生的頻率。匹配詞組在2個文檔中發(fā)生的頻率越高,2個文檔越相似。

具體的文檔相似度計算公式如下：

d1和d2表示相互比較的2篇文檔;L代表最長的特征詞組長度;wk是長度為k的特征詞組的權重,通常特征精度越高,其權重越高;當匹配詞出現在文檔標題中或是人名、機構名和地名時,會給以額外權重;Pk為在長度為k特征詞組上發(fā)生的匹配數量;和分別表示匹配特征詞組在文檔1和文檔2中的頻率;式中分母是文檔1和文檔2中長度為 k的特征詞組頻率之和。

3 示例文檔檢索

圖1是一個示例文檔檢索系統(tǒng)流程圖。

圖1 示例文檔檢索系統(tǒng)

對于基于詞組的處理方式,需要使用數據挖掘算法抽取文本中的重要詞組特征。圖的左半部分表示一個非實時的建模過程,主要是抽取各個文檔的文本特征并進行聚類;圖的右半部分表示一個實時的檢索過程。圖1中各個模塊功能如下：

①分詞處理：研究使用中文文本進行實驗。中文不同于西方語言,詞與詞之間沒有明顯的間隔。因此,在對文本進行處理之前需要對中文文本進行分詞處理,并為每個詞添加詞性標注;

②過濾停用詞和非關鍵詞：根據分詞結果,把介詞、助詞以及一些非關鍵詞刪除。這些詞通常與文檔主題無關,刪除它們不會影響系統(tǒng)性能,還可以減少運算時間;

③利用數據挖掘算法抽取特征詞組：利用數據挖掘算法抽取各個文檔的特征;

④聚類：利用聚類算法對文檔進行聚類,將相似的文檔聚在一起,這樣可以提高檢索階段的執(zhí)行效率;

⑤計算向量與各類的類中心距離：計算示例文檔與各個類之間的距離,從而確定那些與示例文檔最相近的類(相似類)。同時,排除那些與示例文檔距離較遠的類(非相似類)。這樣在檢索階段就無需計算示例文檔與非相似類中各個文檔的距離,從而節(jié)省了時間;

⑥按相似度對相似類中的文檔排序：計算示例文檔與相似類中每一個文檔之間的距離,并根據距離排序。

4 實驗

實驗是基于一個含有21 734個文檔的文檔集合進行的。該文檔集合由基礎文檔和話題文檔兩部分組成：基礎文檔部分含有21 627個文檔,這些文檔來自網上數據庫—慧科新聞。話題文檔部分含有107個文檔,它們分別屬于24個話題,這些話題是從新聞網站的專題新聞獲取的。這2部分文檔都涉及了政治、社會和金融等方面的新聞。基礎文檔部分所含文檔都是2004年及以前的新聞報道;24個話題中包含的文檔都是2006年的新聞報道。每篇文檔平均包含1 000個漢字。利用搜集到的24個話題進行檢索實驗。從某一話題中任選一篇新聞報道作為示例文檔,看能否檢索出此話題中的其他新聞報導。準確率、召回率定義如下：

表1列出了取檢索結果前n(n=2,5,8,10)篇文檔時的準確率。

表1 檢索準確率及檢索時間

若n=話題所含新聞報道數,那么檢索準確率為79.02%。當n=10時的召回率為84.67%。檢索時間依需要與示例文檔進行相似度計算的文檔數量多少而變化,如表1所示。另外,發(fā)現文本中的命名實體在文本檢索過程中可以發(fā)揮重要的作用。命名實體指的是文本中出現的人名、機構名、地名和時間。命名實體反映了事件的發(fā)生地點、時間以及涉及的人物和機構,這些都是構成事件的要素。因此,2個文檔在這些詞上發(fā)生的匹配要比在其他詞上發(fā)生的匹配更能說明2個文檔間存在共性。在算法中,通過給發(fā)生在命名實體上的匹配更多的權重的方法來強調命名實體的重要性。

5 結束語

研究提出的利用數據挖掘算法抽取文本的多層次特征技術,能夠克服傳統(tǒng)特征抽取方法無法抽取多層次特征的不足。這種算法易于實現,且運算速度快,可以應用于面向話題的文本檢索。

[1]KENNETH L V,MOSES C M.Information retrieval in document spaces using clustering[M].Master's Thesis,Department ofInformaticsand Mathematical Modelling Technical University of Denmark,Auguest,2005.

[2]LIU Shuang,LIU Fang,YU Clement.An Effective Approach to Document Retrieval via Utilizing WordNet and Recognizing Phrases[C]//SIGIR'04,July 25 29,Sheffield,Yorkshire,UK,2004：266-272.

[3]ZAMIR O,ETZIONIO.Web DocumentClustering：A Feasibility Demonstration[C]∥Proceedings of the 19th International ACM SIGIR Conferenceon Research and Development in Information Retrieval(SIGIR98),1998：46-54.

[4]SALTON G,YANG C S,YU C T.A Theory of Term Importance in Automatic Text Analysis[J].JASIS,1975,26(1)：33-44.

[5]HAN Jia-wei,MICHELINE KAMBER.Data Mining：Concepts and Techniques[M].San Fransisco：Morgan Kaufmann Publishers,2002.