|
1 文本聚類研究現(xiàn)狀 Internet 已經(jīng)發(fā)展為當(dāng)今世界上最大的信息庫和全球范圍內(nèi)傳播信息最主要的渠道。隨著 Internet 的大規(guī)模普及和企業(yè)信息化程度的提高，各種資源呈爆炸式增長,。在中國互聯(lián)網(wǎng)絡(luò)信息中心 (CNNIC)2007 年 1 月最新公布的中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計報告中顯示,， 70.2% 的網(wǎng)絡(luò)信息均以文本形式體現(xiàn)。對于這種半結(jié)構(gòu)或無結(jié)構(gòu)化數(shù)據(jù),，如何從中獲取特定內(nèi)容的信息和知識成為擺在人們面前的一道難題。近年來,，文本挖掘,、信息過濾和信息檢索等方面的研究出現(xiàn)了前所未有的高潮。 作為一種無監(jiān)督的機(jī)器學(xué)習(xí)方法,，聚類技術(shù)可以將大量文本信息組成少數(shù)有意義的簇,，并提供導(dǎo)航或瀏覽機(jī)制。 文本聚類的主要應(yīng)用點包括： (1) 文本聚類可以作為多文檔自動文摘等自然語言處理應(yīng)用的預(yù)處理步驟,。其中比較典型的例子是哥倫比亞大學(xué)開發(fā)的多文檔自動文摘系統(tǒng) Newsblaster[1] ,。該系統(tǒng)將新聞進(jìn)行 聚類處理，并對同主題文檔進(jìn)行冗余消除,、信息融合,、文本生成等處理，從而生成一篇簡明扼要的摘要文檔,。 (2) 對搜索引擎返回的結(jié)果進(jìn)行聚類,，使用戶迅速定位到所需要的信息。比較典型的系統(tǒng)有 Infonetware Real Term Search ,。 Infonetware 具有強(qiáng)大的對搜索結(jié)果進(jìn)行主題分類的功能,。另外，由 Carrot Search 開發(fā)的基于 Java 的開源 Carrot2 搜索結(jié)果聚合聚類引擎 2.0 版也是這方面的利用,， Carrot2 可以自動把自然的搜索結(jié)果歸類 ( 聚合聚類 ) 到相應(yīng)的語義類別中,，提供基于層級的、同義的以及標(biāo)簽過濾的功能,。 (3) 改善文本分類的結(jié)果,，如俄亥俄州立大學(xué)的 Y.C.Fang 等人的工作 [2] 。 (4) 文檔集合的自動整理,。如 Scatter/Gather[3] ,，它是一個基于聚類的文檔瀏覽系統(tǒng)。 2 文本聚類過程 文本聚類主要依據(jù)聚類假設(shè)：同類的文檔相似度較大,，非同類的文檔相似度較小,。作為一種無監(jiān)督的機(jī)器學(xué)習(xí)方法，聚類由于不需要訓(xùn)練過程,、以及不需要預(yù)先對文檔手工標(biāo)注類別,，因此具有較高的靈活性和自動化處理能力，成為對文本信息進(jìn)行有效組織、摘要和導(dǎo)航的重要手段,。文本聚類的具體過程如圖 1 所示,。 圖 1 文本聚類過程  2.1 文本信息的預(yù)處理 文本聚類的首要問題是如何將文本內(nèi)容表示成為數(shù)學(xué)上可分析處理的形式，即建立文本特征,，以一定的特征項 ( 如詞條或描述 ) 來代表目標(biāo)文本信息,。要建立文本信息的文本特征，常用的方法是：對文本信息進(jìn)行預(yù)處理 ( 詞性標(biāo)注,、語義標(biāo)注 ) ,，構(gòu)建統(tǒng)計詞典，對文本進(jìn)行詞條切分,，完成文本信息的分詞過程,。 2.2 文本信息特征的建立 文本信息的特征表示模型有多種，常用的有布爾邏輯型,、向量空間型,、概率型以及混合型等。其中,，向量空間模型 (Vector Space Model,VSM) 是近幾年來應(yīng)用較多且效果較好的方法之一 [4] ,。 1969 年， Gerard Salton 提出了向量空間模型 VSM ,，它是文檔表示的一個統(tǒng)計模型,。該模型的主要思想是：將每一文檔都映射為由一組規(guī)范化正交詞條矢量張成的向量空間中的一個點,。對于所有的文檔類和未知文檔,，都可以用此空間中的詞條向量（ T1 ,W 1 ,T 2 ,W2 ,…, Tn , Wn ）來表示 ( 其中,， Ti 為特征向量詞條,； Wi 為 Ti 的權(quán)重 )[5] ,。一般需要構(gòu)造一個評價函數(shù)來表示詞條權(quán)重,，其計算的唯一準(zhǔn)則就是要最大限度地區(qū)別不同文檔,。這種向量空間模型的表示方法最大的優(yōu)點在于將非結(jié)構(gòu)化和半結(jié)構(gòu)化的文本表示為向量形式，使得各種數(shù)學(xué)處理成為可能,。 2.3 文本信息特征集的縮減 VSM 將文本內(nèi)容表示成數(shù)學(xué)上可分析處理的形式,，但是存在的一個問題是文檔特征向量具有驚人的維數(shù)。因此,，在對文本進(jìn)行聚類處理之前,，應(yīng)對文本信息特征集進(jìn)行縮減。通常的方法是針對每個特征詞條的權(quán)重排序,，選取預(yù)定數(shù)目的最佳特征作為結(jié)果的特征子集,。選取的數(shù)目以及采用的評價函數(shù)都要針對具體問題來分析決定,。 降低文本特征向量維數(shù)的另一個方法是采用向量的稀疏表示方法。雖然文本信息特征集的向量維數(shù)非常大,，但是對于單個文檔,，絕大多數(shù)向量元素都為零，這一特征也決定了單個文檔的向量表示將是一個稀疏向量,。為了節(jié)省內(nèi)存占用空間,，同時加快聚類處理速度，可以采用向量的稀疏表示方法,。假設(shè)確定的特征向量詞條的個數(shù)為 n ，傳統(tǒng)的表示方法為而（ T1 ,W 1 ,T 2 ,W2 ,…, Tn , Wn ）稀疏表示方法為 (D 1 ,W1 ,D2 ,W2 ,Dp ,…,Wp , n)(Wi ≠ 0) ,。其中， Di 為權(quán)重不為零的特征向量詞條,； Wi 為其相應(yīng)權(quán)重,； n 為向量維度。這種表示方式大大減小了內(nèi)存占用,，提升了聚類效率,，但是由于每個文本特征向量維數(shù)不一致，一定程度上增加了數(shù)學(xué)處理的難度,。 2.4 文本聚類 在將文本內(nèi)容表示成數(shù)學(xué)上可分析處理的形式后,，接下來的工作就是在此數(shù)學(xué)形式的基礎(chǔ)上，對文本進(jìn)行聚類處理,。文本聚類主要有 2 種方法：基于概率 [6] 和基于距離 [7] ,。基于概率的方法以貝葉斯概率理論為基礎(chǔ),，用概率的分布方式描述聚類結(jié)果,。基于距離的方法,，就是以特征向量表示文檔,，將文檔看成向量空間中的一個點，通過計算點之間的距離進(jìn)行聚類,。 目前,，基于距離的文本聚類比較成熟的方法大致可以分為 2 種類型：層次凝聚法和平面劃分法。 對于給定的文件集合 D ={d1 , d 2 ,…,di ,…, dn } ,，層次凝聚法的具體過程如下： (1) 將 D 中的每個文件 di 看成一個具有單個成員的簇 ci ={di } ,，這些簇構(gòu)成了 D 的一個聚類 C={c1 ,c2 ,…,ci ,…,cn }; (2) 計算 C 中每對簇 (ci ,cj ) 之間的相似度 sim{ ci ,cj } ； (3) 選取具有最大相似度的簇對 (ci ,cj ) 將 ci 和 cj 合并為一個新的簇 ck =sim ci ∪ cj ,，從而構(gòu)成了 D 的一個新的聚類 C =(c1 , c 2 ,…,cn-1 ); (4) 重復(fù)上述步驟,，直至 C 中剩下一個簇為止。該過程構(gòu)造出一棵生成樹,，其中包含了簇的層次信息以及所有簇內(nèi)和簇間的相似度,。對于給定的文件集合 {} D ={d1 , d2 ,…,di ,…, dn } ,，平面劃分法的具體過程如下： (1) 確定要生成簇的數(shù)目 k ； (2) 按照某種原則生成 k 個聚類中心作為聚類的種子 S=(s1 ,s2 ,…,si ,…,sk ); (3) 對 D 中的每個文件 di ,，依次計算它與各個種子 sj 的相似度 sim (di ,sj );  (4) 選取具有最大相似度的種子 ，將 di 歸入以 sj 為聚類中心的簇 cj ,，從而得到 D 的一個聚類 C ={ci ,cj } (5) 重復(fù)此步驟若干次,，以得到較為穩(wěn)定的聚類結(jié)果,。這 2 種類型各有優(yōu)缺點。層次凝聚法能夠生成層次化的嵌套簇,，準(zhǔn)確度較高,。但在每次合并時,，需要全局地比較所有簇之間的相似度，并選出最佳的 2 個簇,，因此執(zhí)行速度較慢，不適合大量文件的集合,。而平面劃分法相對來說速度較快,，但是必須事先確定 k 的取值，且種子選取的好壞對群集結(jié)果有較大影響,。 綜合考慮這 2 種聚類類型的優(yōu)缺點,，本文提出了一種基于向量空間模型的文本聚類的改進(jìn)方法—— LP 算法,。具體過程如下： 對于給定的文件集合 D ={d1 , d 2 ,…,di ,…, dn }: (1) 將 D 中的每個文件 di 看作是一個具有單個成員的簇 ci ={di } ； (2) 任選其中一單個成員簇 ci 作為聚類的起點,； (3) 在其余未聚類的樣本中,，找到與 ci 距離滿足條件的 dj ( 可以是與 ci 距離最近的點,，即相似度 sim (c i ,dj ) 最大的 dj ，也可以是與 ci 距離不超過閾值 d 的點,，即相似度 sim (ci ,dj ) ≥ d 的任意 dj ) ,。將 dj 歸入 ci 形成一個新的簇 ck =sim ci ∪ dj ; (4) 重復(fù)步驟 (3) ，直至與 ci 距離最近的 dk 與 ci 之間的距離超過閾值 d ,，此時認(rèn)為已經(jīng)聚完了一類,； (5) 選擇一個未聚類的單個成員簇，重復(fù)步驟 (3) 和步驟 (4) ,，開始新的一輪聚類,，直至所有的單個成員簇 ci 都參與了聚類。 LP 算法不需要比較所有簇之間的相似度,，執(zhí)行速度較快,，適合大量文件的集合，實用性更高,。同時，在聚類過程中不需要事先確定 k 的取值,，降低了與領(lǐng)域知識的依賴性,，提高了靈活性,。 3 實驗設(shè)計 本文采用搜狐研發(fā)中心搜狗實驗室的互聯(lián)網(wǎng)語料鏈接關(guān)系庫 SOGOU-T 。該關(guān)系庫提供了一個大規(guī)?；ヂ?lián)網(wǎng)鏈接關(guān)系對應(yīng)表，用于驗證各種鏈接關(guān)系分析算法的有效性與可行性,。語料關(guān)系庫中的數(shù)據(jù)分為 10 大類 (C000007 汽車,， C000008 財經(jīng)， C000010 IT ,， C000013 健康,， C000014 體育， C000016 旅游,， C000020 教育,， C000022 招聘， C000023 文化,， C000024 軍事 ) ,。語料關(guān)系庫可供下載的共有 3 個版本： Mini 版，精簡版,，完整版。本文使用前 2 個版本進(jìn)行實驗,。語料庫的組織方式如下：為 10 個大類各建立 1 個文件夾,，在每個文件夾中，每 1 份語料自成 1 個 .txt 文件,。 實驗過程如下： (1) 將所有文件夾下的 .txt 文件隨機(jī)連結(jié)成一個大的完整文件，同時保留 .txt 文件的所屬類別 ( 本實驗保留了類別的最后 2 位： 07,08, … ) ,。 (2) 采用中國科學(xué)院計算技術(shù)研究所數(shù)字化室 & 軟件室發(fā)布的中文自然語言處理開放平臺漢語詞法分析系統(tǒng) ICTCLAS ,。利用 ICTCLAS_Win ，將 (1) 中的文件進(jìn)行一級標(biāo)注的詞語切分,。 (3) 統(tǒng)計標(biāo)注好的切分詞語的詞頻,。 (4) 按照權(quán)重 ( 詞頻 ) 的大小整理切分詞語，并保留權(quán)重超過一定限定值 ( 閾值 ) 的特征項,。 ( 本實驗保留了詞頻大于 100 的詞語作為特征項 ) 同時,，根據(jù)漢語的特點，在實驗中設(shè)計了 2 種情況,，以分析比較詞性對于聚類效果的影響： 1) 所有類型的詞語都參與聚類,； 2) 只保留被標(biāo)注為名詞的詞語。 (5) 根據(jù) (4) 中確定的切分詞語構(gòu)造空間向量的基向量,，同時確定空間向量的維數(shù)等參數(shù),。 (6) 將語料庫中的每一份語料文件 (.txt 文件 ) 都表示為一個空間向量。在實驗過程中,，采用了如下 2 種表示方法： 1) 傳統(tǒng)的空間向量表示方法： (T 1 ,W 1 ,T2 , W2 ,…, T n ,Wn ) ,； 2) 稀疏的空間向量表示方法： (D 1 ,W 1 ,D2 , W2 ,…,D p ,Wp ,n) 。 (7) 聚類：聚類過程是實驗的重點,，也是目標(biāo)所在,。 1) 在開始聚類前，首先對 (6) 中已經(jīng)表示好的文本空間向量做歸一化處理,。向量歸一化在模式識別中是很重要的一環(huán),，其目的是把事件的統(tǒng)計分布概率統(tǒng)一歸納在 0-1 灰色聚類的隸屬性上,，這樣，聚類過程對于每一個空間向量的敏感度都是一樣的,。  傳統(tǒng)空間向量： ,  其中 : ;  稀疏空間向量：  其中 http://edu./uploadfile/2009/0910/20090910100906272.jpg 2) 在實驗中,，采用歐幾里德距離來表示任意 2 個文本向量之間的距離。   稀疏空間向量：計算方法與傳統(tǒng)空間向量類似,，計算相同詞條之間距離平方和的算術(shù)平方根,。 3)LP 算法要求預(yù)先確定閾值。實驗中,，采取的閾值策略是：制定初始閾值 ( 即針對單個成員簇的閾值,，此閾值根據(jù)實驗效果多次調(diào)整 ) ，當(dāng) 2 個簇合并為 1 個簇時,，新簇的閾值由合并算法根據(jù)被合并簇的聚類特征求出,。 2 個簇進(jìn)行合并，其特征向量分別為 X=(T1 ,x1 ,T 2 ,x2 ,…,Tn ,Xn ),Y=(T1 ,y1 , T2 , y 2 ,…,Tn , yn ) ,，則組成的新簇的特征向量為  合并定理：假定對 2 個簇進(jìn)行合并,，合并后的簇的閾值表示為  其中， dist 指 2 個特征向量之間的距離,。 4 數(shù)據(jù)分析 實驗中對于本文提到的 3 種聚類方式都有涉及,，對于它們的優(yōu)劣在實驗層面上做了研究比對。 A ：所有類型的詞語都用于構(gòu)建空間向量,； B ：只采用名詞構(gòu)建空間向量,； C ：采用傳統(tǒng)的空間向量表示方法； D ：采用稀疏的空間向量表示方法,。 Mini 版 (SogouC.mini.20061102) ：共 100 篇文檔,，每個類別 10 篇,。 精簡版 (SogouC.reduced.20061102) ：共 10 020 篇文檔,，每個類別 1 002 篇。 表 1 是實驗結(jié)果,。其中,， t(time) 表示聚類消耗時間，單位為 ms ,； a(accuracy) 表示聚類準(zhǔn)確度,。聚類消耗的時間依賴于執(zhí)行的具體狀況，因而有一定的差異,。表中所取的數(shù)據(jù)是排除突變數(shù)據(jù) ( 即壞數(shù)據(jù) ) 之后,，多次實驗結(jié)果的平均值。 表 1 聚類實驗效果  對實驗結(jié)果進(jìn)行分析,，可以總結(jié)出以下 5 點： (1) 對于精簡版的聚類,， 3 種方法的效果都優(yōu)于 Mini 版,。這是因為，精簡版的基礎(chǔ)數(shù)據(jù)量較大,，個別的突變數(shù)據(jù)對于聚類效果的影響就相對較小,。 (2) 采用稀疏向量表示法之后，聚類的時間消耗減少了約 4/5 ,，表明對于高維向量采用其稀疏表示可以有效地節(jié)省內(nèi)存占用空間,，加快聚類處理速度。 (3) 相較于層次聚類,， LP 算法在時間消耗上下降了約 30% ,，因此，對于數(shù)據(jù)量較大,，實時性要求較高的場合,，由于有效地減少了消耗時間， LP 算法還是顯示出了它的優(yōu)勢,。 (4) 相較于平面劃分法,， LP 算法在聚類的準(zhǔn)確性上提高了 11%~13% ，達(dá)到了 77%~83% ,，從而保證了聚類的準(zhǔn)確度在可接受的范圍之內(nèi),。 (5) 本次實驗中， LP 算法在聚類準(zhǔn)確性上略遜于層次法,，筆者認(rèn)為這主要是因為：層次法的主要思想是全局最優(yōu),，每次聚為一個簇的 2 個成員之間的相似度都是最大的，而在 LP 算法中,，決定將 2 個成員歸為一類的唯一衡量就是閾值 d ,。閾值選取的好壞對于實驗效果的影響非常大。因此,，如何選取閾值的初始值以及在聚類過程中如何動態(tài)地調(diào)整閾值是下一步的主要工作,。 5 結(jié)束語 文本聚類在文本模式識別中占有重要的地位，這也是本文研究的價值所在,。本文分析了基于距離的文本聚類中比較成熟的 2 種方法：層次凝聚法和平面劃分法,，并提出了一種改進(jìn)方法 LP 。從實驗效果上看,， LP 算法速度更快,，靈活性也更高。在后續(xù)的工作中,，還將進(jìn)一步在實驗的基礎(chǔ)上對算法進(jìn)行反復(fù)修正和拓展,，以達(dá)到更好的聚類和實用效果。 |
|
|
