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

◆魏小銳

?

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

◆魏小銳

(東莞理工學(xué)院計(jì)算機(jī)與網(wǎng)絡(luò)安全學(xué)院廣東 523808)

基于內(nèi)容的網(wǎng)絡(luò)信息過(guò)濾需要?jiǎng)討B(tài)地比較網(wǎng)頁(yè)與用戶模板。傳統(tǒng)文檔主題匹配算法主要以兩兩文檔間的相似度為基礎(chǔ)來(lái)計(jì)算，這在高維的文檔向量空間并不總是合適。超團(tuán)模式是一種附加了整體相似度約束的頻繁項(xiàng)集，其內(nèi)部文檔更有可能屬于同一類(lèi)別。利用超團(tuán)模式這種特性，提出了基于整體相似度的文檔主題匹配方法，只利用同一個(gè)超團(tuán)內(nèi)部的文檔來(lái)預(yù)測(cè)類(lèi)別。該方法通過(guò)在現(xiàn)實(shí)世界數(shù)據(jù)集上與K-最近鄰算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果證實(shí)了超團(tuán)算法應(yīng)用于文檔主題匹配的優(yōu)越性。

文本挖掘；文檔匹配；整體相似度；超團(tuán)模式

0 引言

隨著因特網(wǎng)迅速發(fā)展，互聯(lián)網(wǎng)已成為一個(gè)巨大的信息空間，為用戶提供了極具價(jià)值的信息資源。但是由于互聯(lián)網(wǎng)的開(kāi)放性，人們發(fā)布、傳播和接收信息幾乎不受任何的控制, 人們對(duì)網(wǎng)絡(luò)資源的非正當(dāng)使用也逐漸成為社會(huì)正常生產(chǎn)與生活的威脅。因此，信息過(guò)濾技術(shù)越來(lái)越多地應(yīng)用在網(wǎng)絡(luò)上。比如，通過(guò)信息過(guò)濾技術(shù)，家長(zhǎng)可以防止自己不在家時(shí)孩子訪問(wèn)不健康的網(wǎng)頁(yè)，教師可以防止學(xué)生在實(shí)驗(yàn)課上瀏覽與課堂內(nèi)容不相關(guān)的網(wǎng)頁(yè)，公司可以防止員工上班時(shí)間瀏覽與工作不相關(guān)的內(nèi)容。

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

本文在傳統(tǒng)的信息檢索基礎(chǔ)上提出將超團(tuán)模式應(yīng)用于文檔主題匹配，研究如何用關(guān)聯(lián)模式來(lái)評(píng)估文檔間的相似度。通過(guò)在給定的文本集中挖掘最大文檔超團(tuán)并計(jì)算相關(guān)文檔的整體相似度，從而找出那些與用戶模板里的種子文檔最相關(guān)的測(cè)試文檔，并以此為依據(jù)對(duì)用戶所瀏覽的網(wǎng)絡(luò)信息進(jìn)行有效的監(jiān)控和過(guò)濾。

本文接下來(lái)組織如下：第1節(jié)介紹文檔模型與文檔檢索的相關(guān)技術(shù)，第2節(jié)介紹超團(tuán)模式以及相應(yīng)的文檔主題匹配算法，第3節(jié)報(bào)告實(shí)驗(yàn)結(jié)果，第4節(jié)是小結(jié)。

1 相關(guān)技術(shù)

1.1文檔向量模型

文檔向量空間模型是一個(gè)常應(yīng)用于信息過(guò)濾、擷取、索引以及評(píng)估相關(guān)性的代數(shù)模型[3,4]。在該模型中，用D（Document）表示文本，其中文本是泛指各種機(jī)器可讀的記錄。

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

1.2文檔相似度計(jì)算

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

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

其中，W1k、W2k分別表示文本D1和D2第k個(gè)特征項(xiàng)的權(quán)值（1≤ k ≤n ） 。

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

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

該方法在定類(lèi)決策上只依據(jù)最鄰近幾個(gè)樣本與待分樣本之間的兩兩相似度來(lái)預(yù)測(cè)類(lèi)別。其前提是：

（1）兩個(gè)樣本之間相似度越大，它們?cè)接锌赡軐儆谕活?lèi)別；

（2）所選擇的近鄰都是已經(jīng)提前正確分類(lèi)的對(duì)象。

對(duì)于文檔這種高維數(shù)據(jù)，該算法計(jì)算量非常大，而且前面的前提（1）經(jīng)常并不成立[10]。當(dāng)樣本所屬類(lèi)別不平衡時(shí)，如一個(gè)類(lèi)的樣本容量很大，而其他類(lèi)樣本容量比較小時(shí)，有可能導(dǎo)致當(dāng)輸入一個(gè)新樣本時(shí)，該樣本的k個(gè)鄰居中大容量類(lèi)的樣本永遠(yuǎn)占多數(shù)。

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

2.1超團(tuán)模式

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

超團(tuán)是在頻繁項(xiàng)集(frequent item set)的基礎(chǔ)上提出的一個(gè)較新的概念，是一種特殊的頻繁項(xiàng)集[11]。下面是H置信度的相關(guān)定義：

定義1 關(guān)聯(lián)規(guī)則的H置信度

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

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

給定一個(gè)用戶自定義的支持度和h置信度閾值HC，我們把大于等于這些閥值的項(xiàng)集稱作超團(tuán)。超團(tuán)模式是一種強(qiáng)關(guān)聯(lián)模式，它的特點(diǎn)是當(dāng)超團(tuán)內(nèi)的某個(gè)項(xiàng)目在事務(wù)中出現(xiàn)時(shí)，該超團(tuán)的其他全部項(xiàng)在這個(gè)事務(wù)出現(xiàn)的概率不低于h置信度。如果用0-1矩陣表示事務(wù)集數(shù)據(jù)，用0-1列向量來(lái)表示每個(gè)項(xiàng)，那么超團(tuán)內(nèi)部任意兩項(xiàng)的余弦相似度可以由以下公式計(jì)算：

由以上兩個(gè)公式可知超團(tuán)內(nèi)部任意兩項(xiàng)的cosine相似度不低于超團(tuán)的h置信度閥值HC。

2.2整體相似度

傳統(tǒng)文檔主題類(lèi)別匹配主要根據(jù)所有文檔間的兩兩相似度來(lái)計(jì)算。本文提出利用超團(tuán)模式強(qiáng)關(guān)聯(lián)的性質(zhì)來(lái)計(jì)算多文檔之間的整體相似度，用于文檔類(lèi)別匹配。具體地，相似度的計(jì)算只局限于文檔超團(tuán)內(nèi)部的文檔。將超團(tuán)內(nèi)的文檔分為種子文檔子集和測(cè)試文檔子集，然后為測(cè)試文檔子集中的每個(gè)文檔計(jì)算其與種子文檔子集所有文檔的相似度并取最大值，所得值即為該測(cè)試文檔與整個(gè)種子集的整體相似度值。

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

表1 文檔兩兩相似度矩陣

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

當(dāng)運(yùn)用超團(tuán)模式，通過(guò)設(shè)置一定的參數(shù)閥值挖掘得出的文檔超團(tuán)為{ D1，D4，O1，O3}和{ D2，D3，O2，O4}，那么文檔之間所需計(jì)算的相似度如表2所示。

表2 文檔超團(tuán)相似度矩陣

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

2.3算法描述

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

圖1 基于超團(tuán)的文檔類(lèi)別匹配算法描述

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

3 實(shí)驗(yàn)評(píng)估

3.1實(shí)驗(yàn)設(shè)計(jì)

為了比較基于超團(tuán)的算法和K-最近鄰算法對(duì)于文檔類(lèi)別匹配的效果，在實(shí)驗(yàn)過(guò)程中我們采用了各種主題的文檔集。文檔集來(lái)源于中文文本分類(lèi)語(yǔ)料庫(kù) 。語(yǔ)料庫(kù)包括財(cái)經(jīng)、電腦、房產(chǎn)、教育、科技、汽車(chē)、人才、體育、衛(wèi)生和娛樂(lè)十個(gè)主題的文檔集。按照類(lèi)別大小比例，把語(yǔ)料庫(kù)隨機(jī)地劃分為種子集與測(cè)試集。每次在種子集選取一個(gè)主題的文檔作為當(dāng)前種子集（用戶模板），計(jì)算測(cè)試集中文檔與它匹配的情況。

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

3.2實(shí)驗(yàn)結(jié)果

限于篇幅，下面只給出部分結(jié)果。當(dāng)在種子集中選取“衛(wèi)生”主題進(jìn)行文檔類(lèi)別匹配，超團(tuán)算法中支持度及H-置信度值分別取0.001及0.002時(shí)實(shí)驗(yàn)的比較結(jié)果如圖2所示：

當(dāng)在種子集中選取“人才”主題進(jìn)行文檔類(lèi)別匹配，超團(tuán)算法中支持度及H-置信度值分別取0.001及0.002時(shí)實(shí)驗(yàn)的比較結(jié)果如圖3所示：

在圖2和圖3中我們可以看到兩種算法隨著K的取值的不斷變化，召回率、準(zhǔn)確率和F1值都有所變化，但總體的趨勢(shì)是運(yùn)用超團(tuán)的算法的各個(gè)評(píng)測(cè)指標(biāo)比KNN算法的要高。

在實(shí)驗(yàn)過(guò)程中，我們分別選取種子集中的十個(gè)主題的文檔集進(jìn)行檢測(cè)，發(fā)現(xiàn)在絕大多數(shù)情況下，采用超團(tuán)算法的檢測(cè)結(jié)果的各項(xiàng)評(píng)價(jià)指標(biāo)整體上都優(yōu)于采用KNN算法的檢測(cè)結(jié)果。這也在一定程度上證實(shí)了將超團(tuán)應(yīng)用于文檔類(lèi)別匹配總體性能上要優(yōu)于采用K-最近鄰算法。

4 總結(jié)

本文重點(diǎn)研究了如何用關(guān)聯(lián)模式評(píng)估文檔間的相似度，匹配文檔主題?；诔瑘F(tuán)模式的概念，提出利用整體相似度來(lái)找出那些與用戶模板主題最相關(guān)的測(cè)試文檔。大量的實(shí)驗(yàn)結(jié)果也證實(shí)了基于超團(tuán)的文檔主題匹配在準(zhǔn)確性上要優(yōu)于傳統(tǒng)基于兩兩相似度的KNN算法。雖然初步達(dá)到了預(yù)期的目標(biāo)，但在超團(tuán)模式參數(shù)選取等方面有待進(jìn)一步完善。另外，如何自動(dòng)學(xué)習(xí)具有代表性的種子集，以及如何解釋并展示檢測(cè)出的結(jié)果文檔，這些都是值得進(jìn)一步研究的方向。

[1]劉宗仁.網(wǎng)上內(nèi)容過(guò)濾技術(shù)的現(xiàn)狀及面臨的問(wèn)題[J].現(xiàn)代情報(bào)，2005.

[2]白寧.基于特征選擇融合的垃圾郵件過(guò)濾方法[J].計(jì)算機(jī)應(yīng)用與軟件，2014.

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

[4]潘俊輝，王輝.一種基于模糊VSM和神經(jīng)網(wǎng)絡(luò)的文本分類(lèi)方法[J].科學(xué)技術(shù)與工程，2011.

[5]張翔，周明全，董麗麗，閆清波.結(jié)合粗糙集與集成學(xué)習(xí)的中文文本分類(lèi)方法研究[J].計(jì)算機(jī)應(yīng)用與軟件，2011.

[6]郭頌，馬飛.文本分類(lèi)中信息增益特征選擇算法的改進(jìn)[J].計(jì)算機(jī)應(yīng)用與軟件，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]楊夢(mèng)雄, 楊貫中.基于K-最近鄰算法的話務(wù)智能預(yù)測(cè)技術(shù)[J].科學(xué)技術(shù)與工程, 2007.

[9]羅辛, 歐陽(yáng)元新，熊璋等.通過(guò)相似度支持度優(yōu)化基于K 近鄰的協(xié)同過(guò)濾算法[J].計(jì)算機(jī)學(xué)報(bào)，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.

本文受廣東省東莞市科技計(jì)劃項(xiàng)目（批準(zhǔn)號(hào)：東科[2015]16-2014106101003）資助。