基于整體相似度的文檔主題匹配研究

◆魏小銳

?

基于整體相似度的文檔主題匹配研究

◆魏小銳

(東莞理工學院計算機與網絡安全學院廣東 523808)

基于內容的網絡信息過濾需要動態地比較網頁與用戶模板。傳統文檔主題匹配算法主要以兩兩文檔間的相似度為基礎來計算，這在高維的文檔向量空間并不總是合適。超團模式是一種附加了整體相似度約束的頻繁項集，其內部文檔更有可能屬于同一類別。利用超團模式這種特性，提出了基于整體相似度的文檔主題匹配方法，只利用同一個超團內部的文檔來預測類別。該方法通過在現實世界數據集上與K-最近鄰算法進行比較，實驗結果證實了超團算法應用于文檔主題匹配的優越性。

文本挖掘；文檔匹配；整體相似度；超團模式

0 引言

隨著因特網迅速發展，互聯網已成為一個巨大的信息空間，為用戶提供了極具價值的信息資源。但是由于互聯網的開放性，人們發布、傳播和接收信息幾乎不受任何的控制, 人們對網絡資源的非正當使用也逐漸成為社會正常生產與生活的威脅。因此，信息過濾技術越來越多地應用在網絡上。比如，通過信息過濾技術，家長可以防止自己不在家時孩子訪問不健康的網頁，教師可以防止學生在實驗課上瀏覽與課堂內容不相關的網頁，公司可以防止員工上班時間瀏覽與工作不相關的內容。

由于網絡的動態性，基于內容過濾是當前網絡信息過濾系統主要采用的一種方法[1,2]。針對禁止用戶訪問的主題，選取一些代表性的種子文檔作為用戶模板。把用戶瀏覽的文檔作為測試文檔，我們需要從測試文檔中找出有可能與種子文檔屬于同一主題的文檔。這種檢索要求結果同時具有理想的召回率與準確率。較低的召回率意味著漏掉許多本該禁止訪問的文檔，而準確率過低則意味著許多正常的文檔也被禁止了?？梢?，基于內容過濾的關鍵在于從測試文檔集中找出與種子文檔主題匹配的文檔。

本文在傳統的信息檢索基礎上提出將超團模式應用于文檔主題匹配，研究如何用關聯模式來評估文檔間的相似度。通過在給定的文本集中挖掘最大文檔超團并計算相關文檔的整體相似度，從而找出那些與用戶模板里的種子文檔最相關的測試文檔，并以此為依據對用戶所瀏覽的網絡信息進行有效的監控和過濾。

本文接下來組織如下：第1節介紹文檔模型與文檔檢索的相關技術，第2節介紹超團模式以及相應的文檔主題匹配算法，第3節報告實驗結果，第4節是小結。

1 相關技術

1.1文檔向量模型

文檔向量空間模型是一個常應用于信息過濾、擷取、索引以及評估相關性的代數模型[3,4]。在該模型中，用D（Document）表示文本，其中文本是泛指各種機器可讀的記錄。

特征項（Term，用t表示）是指出現在文檔D中且能夠代表該文檔內容的基本語言單位，文本可以用特征項集表示為D(T1，T2，…，Tk, …,Tn)，其中Tk是特征項，1<=k<=n。對含有n個特征項的文本而言，通常會給每個特征項賦予一定的權重表示其重要程度。即D＝D(T1，W1；T2，W2；…，Tn，Wn)，簡記為D＝D (W1，W2，…，Wn)，我們把它叫做文本D的向量表示，其中Wk是Tk的權重（1≤ k ≤n ）。

1.2文檔相似度計算

兩個對象之間的相似度是這兩個對象相似程度的數值度量。當文檔用向量來表示時，那么向量的每個屬性代表一個特定詞條在文檔中出現的頻率。通常一個文檔集中擁有數以萬計的詞條。但是，具體到某一篇文檔時，由于它具有相對較少的單詞，所以其向量都很稀疏。這就要求文檔的相似性度量必須能夠處理稀疏向量[5,6]。

計算文檔相似度的方法有很多，其中比較有代表性的是余弦計算法（cosine measure）[7]。在向量空間模型中，兩個文本D1和D2之間的內容相關度Sim(D1，D2)可以用向量之間夾角的余弦值表示，公式為：

其中，W1k、W2k分別表示文本D1和D2第k個特征項的權值（1≤ k ≤n ） 。

1.3 基于K-最近鄰的k文檔匹配

K-最近鄰（KNN, K nearest neighbors）分類算法常用于文檔類別匹配[8,9]。該算法的主要思想是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)樣本中的大多數屬于某一個類別，則該樣本也屬于這個類別。

該方法在定類決策上只依據最鄰近幾個樣本與待分樣本之間的兩兩相似度來預測類別。其前提是：

（1）兩個樣本之間相似度越大，它們越有可能屬于同一類別；

（2）所選擇的近鄰都是已經提前正確分類的對象。

對于文檔這種高維數據，該算法計算量非常大，而且前面的前提（1）經常并不成立[10]。當樣本所屬類別不平衡時，如一個類的樣本容量很大，而其他類樣本容量比較小時，有可能導致當輸入一個新樣本時，該樣本的k個鄰居中大容量類的樣本永遠占多數。

2 基于整體相似度的文檔匹配

2.1超團模式

本算法提出了基于超團的整體相似度概念，在大量的測試文檔集中，利用整體相似度檢索出最接近于種子文檔集主題的文檔。接下來介紹“超團”(hyperclique)。

超團是在頻繁項集(frequent item set)的基礎上提出的一個較新的概念，是一種特殊的頻繁項集[11]。下面是H置信度的相關定義：

定義1 關聯規則的H置信度

對于頻繁項集X＝{i1,i2,i3,…,ik}，h置信度（h-confidence）的公式如下：

其中，s({ik})表示項集{ik}的支持度。

給定一個用戶自定義的支持度和h置信度閾值HC，我們把大于等于這些閥值的項集稱作超團。超團模式是一種強關聯模式，它的特點是當超團內的某個項目在事務中出現時，該超團的其他全部項在這個事務出現的概率不低于h置信度。如果用0-1矩陣表示事務集數據，用0-1列向量來表示每個項，那么超團內部任意兩項的余弦相似度可以由以下公式計算：

由以上兩個公式可知超團內部任意兩項的cosine相似度不低于超團的h置信度閥值HC。

2.2整體相似度

傳統文檔主題類別匹配主要根據所有文檔間的兩兩相似度來計算。本文提出利用超團模式強關聯的性質來計算多文檔之間的整體相似度，用于文檔類別匹配。具體地，相似度的計算只局限于文檔超團內部的文檔。將超團內的文檔分為種子文檔子集和測試文檔子集，然后為測試文檔子集中的每個文檔計算其與種子文檔子集所有文檔的相似度并取最大值，所得值即為該測試文檔與整個種子集的整體相似度值。

下面舉例說明整體相似度與兩兩相似度的區別。假設種子文檔集O={O1，O2，O3，O4}，測試文檔集D={D1，D2，D3，D4}，其中測試文檔集中只有D4與種子集不屬同一類別，兩個文檔集合之間文檔的兩兩相似度如表1所示。

表1 文檔兩兩相似度矩陣

根據相似度從高到低排列，測試集中的文檔排列為D2、D3、D4和D1。若采用K-最近鄰算法，當選取出相似度最高的3個測試文檔時，D4被視為與種子集屬于同一類別，但實際上它與種子集不屬同一類別。

當運用超團模式，通過設置一定的參數閥值挖掘得出的文檔超團為{ D1，D4，O1，O3}和{ D2，D3，O2，O4}，那么文檔之間所需計算的相似度如表2所示。

表2 文檔超團相似度矩陣

如表2所示，D1只需計算跟O1和O3的相似度，并取他們的最大值0.51作為測試文檔D1與種子集的整體相似度。根據相似度從高到低排列原則，測試集中的文檔排列為D3、D2、D1和D4。當選取出相似度最高的3個測試文檔時，所得文檔均與種子集同屬一個類別。在表2中，盡管D1與種子集的相似度為0.51，該值小于表1中D4與種子集的相似度0.73，但D1卻與種子集同屬一個類別。這就說明了在某些情況下通過計算多個文檔間的整體相似度對于文檔類別預測，要優于計算文檔兩兩間的相似度。

2.3算法描述

圖1是將超團運用到文檔類別匹配中的一個高層描述。輸入包括：測試文檔集D、用戶模板存儲的種子集O、超團的參數最小支持度閥值、最小H置信度閥值，以及用戶期待的輸出文檔數量K。輸出為從測試文檔集D選出的最有可能與種子集O屬于同一類別的K篇測試文檔。

圖1 基于超團的文檔類別匹配算法描述

在該算法中，步驟1-2首先將測試集與種子集兩兩文檔之間的相似度初始化為零；接著根據測試集、種子集以及用戶輸入條件（包括最小支持度閥值、最小H置信度閥值）挖掘出最大超團集。步驟3-11對最大超團集中的所有集合進行遍歷，把每個集合劃分為測試集和種子集，若其中一個子集為空則對下一個最大超團進行劃分，否則計算出劃分后測試集中所有文檔與劃分后種子集的相似度。在遍歷完最大超團集中所有最大超團后，步驟12根據文檔相似度從大到小的原則排列測試集中所有文檔，根據用戶選擇輸出的文檔數量輸出前K篇文檔，而這K篇文檔就被視為最有可能與種子集O屬于同一類別。

3 實驗評估

3.1實驗設計

為了比較基于超團的算法和K-最近鄰算法對于文檔類別匹配的效果，在實驗過程中我們采用了各種主題的文檔集。文檔集來源于中文文本分類語料庫 。語料庫包括財經、電腦、房產、教育、科技、汽車、人才、體育、衛生和娛樂十個主題的文檔集。按照類別大小比例，把語料庫隨機地劃分為種子集與測試集。每次在種子集選取一個主題的文檔作為當前種子集（用戶模板），計算測試集中文檔與它匹配的情況。

具體地，令D表示測試文檔中屬于當前主題的文檔集，P表示結果文檔集（總共K 篇），可以分別計算輸出結果的召回率(rec)、準確率(pre)和F1值如下：

3.2實驗結果

限于篇幅，下面只給出部分結果。當在種子集中選取“衛生”主題進行文檔類別匹配，超團算法中支持度及H-置信度值分別取0.001及0.002時實驗的比較結果如圖2所示：

當在種子集中選取“人才”主題進行文檔類別匹配，超團算法中支持度及H-置信度值分別取0.001及0.002時實驗的比較結果如圖3所示：

在圖2和圖3中我們可以看到兩種算法隨著K的取值的不斷變化，召回率、準確率和F1值都有所變化，但總體的趨勢是運用超團的算法的各個評測指標比KNN算法的要高。

在實驗過程中，我們分別選取種子集中的十個主題的文檔集進行檢測，發現在絕大多數情況下，采用超團算法的檢測結果的各項評價指標整體上都優于采用KNN算法的檢測結果。這也在一定程度上證實了將超團應用于文檔類別匹配總體性能上要優于采用K-最近鄰算法。

4 總結

本文重點研究了如何用關聯模式評估文檔間的相似度，匹配文檔主題?；诔瑘F模式的概念，提出利用整體相似度來找出那些與用戶模板主題最相關的測試文檔。大量的實驗結果也證實了基于超團的文檔主題匹配在準確性上要優于傳統基于兩兩相似度的KNN算法。雖然初步達到了預期的目標，但在超團模式參數選取等方面有待進一步完善。另外，如何自動學習具有代表性的種子集，以及如何解釋并展示檢測出的結果文檔，這些都是值得進一步研究的方向。

[1]劉宗仁.網上內容過濾技術的現狀及面臨的問題[J].現代情報，2005.

[2]白寧.基于特征選擇融合的垃圾郵件過濾方法[J].計算機應用與軟件，2014.

[3]Baeza-Yates, R, Ribeiro-Neto, B. Modern Information Retrieval. Addison-Wesley, 1999.

[4]潘俊輝，王輝.一種基于模糊VSM和神經網絡的文本分類方法[J].科學技術與工程，2011.

[5]張翔，周明全，董麗麗，閆清波.結合粗糙集與集成學習的中文文本分類方法研究[J].計算機應用與軟件，2011.

[6]郭頌，馬飛.文本分類中信息增益特征選擇算法的改進[J].計算機應用與軟件，2013.

[7]France, S. L., Carroll, J. D., Xiong, H.. Distance metrics for high dimensional nearest neighborhood recovery: Compression and normalization[J]. Information Sciences，2012.

[8]楊夢雄, 楊貫中.基于K-最近鄰算法的話務智能預測技術[J].科學技術與工程, 2007.

[9]羅辛, 歐陽元新，熊璋等.通過相似度支持度優化基于K 近鄰的協同過濾算法[J].計算機學報，2010.

[10]Vadapalli, S, Valluri, S. R., Karlapalem, K. A simple yet effective data clustering algorithm[J]. Proceedings of the 6th IEEE International Conference on Data Mining，2006.

[11]Xiong, H., Tan, P.-N., Kumar, V. Hyperclique pattern discovery[J]. Data Mining and Knowledge Discovery，2006.

本文受廣東省東莞市科技計劃項目（批準號：東科[2015]16-2014106101003）資助。