文檔聚類算法改進及效果測試文檔聚類研究

摘 要：本文提出一種利用文本間相似度進行主題的語義合并，對文本進行語義抽象聚類的算法。該模型充分利用現狀網上一些開源工具，并對已有的聚類算法進行改進，最后給出了該算法與其他算法的測試比較效果。

關鍵詞：文檔聚類；算法改進；測試

中圖分類號：TP391.1 文獻標識碼：A 文章編號：1674-7712 （2013） 14-0000-02

一、研究背景

在日常生產和生活中，人們面對非常復雜的事物，往往希望能夠把相似的東西歸為一類，有明顯區別的事物分屬在不同的類別中，這樣處理起來就大為簡便。隨著人類對自然和社會的認識不斷深入，要處理的數據量規模越來越大，相互關系也越來越復雜，分類越來越細，對分類的要求也越來越高，這時僅僅依靠定性分析就不能滿足要求。

聚類分析是一種數學工具引入后，形成的基于數值分類學的一種多元統計方法，也是文獻計量研究中經常用到的數據結構挖掘技術。

聚類是對無標簽的數據進行分類，優勢是無標簽，就是不需要在訓練前對訓練集集中的數據點進行人為的事先分類，缺點是聚類得到的模型不一定反映數據的真實模型。

聚類相當于將一大群人按照他們的距離（這里的距離可能是他們的相似程度或者其他，越相似距離越短）進行分類，聚類分析可以獲得數據的分類，但是這個分類不一定反映數據的真實模型。適用于目標分類。聚類是對數據樣例進行劃分，形成若干個簇。

隨著科技文獻檢索能力的加強，人們能夠直接從網上和眾多英文數據庫中獲取的科技文獻越來越多。如何從海量的英文資料中發現更多隱含的信息，這也是國內外眾多學者研究的一個熱點問題之一。例如，做文獻綜述時需要從檢索到的科技文獻中分析本課題的主要研究方向，在以前文獻量較少的情況下可以人工提煉和總結，但面對大量的文獻時則已超過了人的閱讀和分析能力，往往耗費大量的時間和精力也不能找到學科的主要研究領域。

二、聚類模型

收集文檔資料，對這些文檔中的文本信息進行分詞和統計詞頻，為下一步進行主題詞提取做準備。

單個網頁文本信息抽取與統計的詳細步驟如下：

將經過 Crunch 過濾后的網頁解析成 DOM Tree，然后根據該 DOM Tree，取得文本；

利用Charniak's parser對網頁的文本進行分詞；

利用Lucene的snowball組件對分詞后的各個單詞取詞根；

統計詞根的詞頻；

對所有的keyword進行基于語義相似度的聚類，當聚類結果中的keywords之間的語義相似度大于某個閾值的時候，對這些keywords進行語義層次的合并，詞頻數相加；

按詞頻從大到小排序，每個頁面取前N個詞根；

將處理以后的N個詞作為輸入，參與下一小節的主題詞提取的運算。經過過濾后網頁中的文本內容需要進行分詞與詞頻統計，我們這里采用的是共指消解系統所采用的預處理系統：Charniak's parser（英語語法分析器）。作為一種應用系統的數據預處理工具，它的功能有：（1）劃分出一個句子以及一個詞的起始位置與結束位置；（2）區分出詞或者短語的詞性；（3）檢測出名詞短語，如人名；（4）檢測出專有名詞，如the Summer Palace這樣的短語。這個工具改進了我們原本采用的簡單利用Lucene組件的進行分詞的技術，使得許多名詞短語和專有名詞的分詞更加的準確。另外，經過Charniak's parser處理以后的文本的詞性也已經知道，因此，我們直接忽略了介詞以及副詞等無關主題的詞過濾掉，對實驗結果的效率也改進不少。

在使用Charniak's parser分完詞之后，如果直接進行詞頻統計，同一名個詞可能會因為單復數形式的不同，或者是同一個動詞因為時態的不同，被統計成為兩個不同的詞。因此，需要再對得到詞或者詞組進行取詞根的操作。這里本文使用的是Snowball算法。Snowball是Lucene SandBox里的一個組件，它是信息檢索中用于處理字符串的處理的一個算法，可以將一個句子進行分詞運算，并取其詞根的操作。

我們對根據分詞，取詞根，利用共指消解工具后得到的指代關系處理以及原始的詞頻統計這系列的步驟處理之后，得到的詞或詞組的統計信息，接下來再進行語義相似度的計算：如果兩個經過分詞處理得到的文本都是是單個詞，并且在WordNet中可以查詢到它們的語義信息，我們就應用WordNet進行語義相似度計算；否則，則利用Wiki進行相應的語義相似度計算。

當兩個概念之間的語義相似度大于某個域值的時候，對兩個概念進行合并，詞頻數相加。這樣，我們就在主題抽取的步驟中引入了語義。對于單個網頁內 的keyword進行語義合并的算法，本文采用了層次聚類的方法。兩個聚類之間的 距離，我們用了兩個類中任意兩個元素的距離的平均。每一個聚類Ci為一個 keyword的集合，即Ci={ki，1 ki，2 ki，3 ...ki，n }， 兩個聚類Ci Cj的距離記為davg（Ci， Cj），

1.每一個keyword作為一個初始類，設定一個類之間的距離閾值d0；

2.計算任意兩個類之間的距離；

3.將所有兩兩之間的距離大于閾值d0的類合并；

4.重復2，3步，直到第 3步不再有類合并為止，算法結束。通過語義相似的文本的聚類處理以后，我們得到了一些Keyword的聚類。接下來進行語義合并的處理。通過檢索WordNet，判斷聚類里的Keyword，如果ki kj是同義詞的話，用ki kj里詞頻大的Keyword作為代表，詞頻數為兩者之和；如果ki kj有共同的上位詞（深度小于 4），則用它們的上位詞作為代表，詞頻數為兩者之和。

由于通過鏈接分析得到的網頁集，它們只是因為互相有著緊密的鏈接相互指向，而被挖掘出來，分到同一個網頁集當中，其結果可能并不只是一個社區，因此我們需要再進行一次網頁集的聚類。

通過無關內容塊的過濾之后，抽取出文本信息的網頁集，與平常的文檔集有著比較多的相似之處，因此，在網頁集的聚類方面，本文借鑒了文檔集的聚類方法。文本聚類在本質上是一種通過對對象集合按照某種規則進行劃分或覆蓋從而發現隱含的潛在有用的信息的一種知識發現的方法。聚類算法通常有以下幾類：（1）通過構建類別層次或者構造一棵類別樹進行聚類的層次聚類算法；（2）將數據集進行劃分的分割聚類算法；（3）按其連接分量的密度定義類別的基于密度的聚類方法；（4）通過對屬性空間進行單元劃分，然后對單元進行聚類的網絡聚類算法；（5）其他聚類算法還有基于“核”的聚類算法以及利用進化算法，梯度下降法等的聚類算法。各種不同的應用對聚類質量、效率以及結果可視化程度等方面往往都有特定的要求，因此要根據應用場合和目的選用適合的聚類算法。

由于一個網頁集中主題的個數是不確定的，因此本文選用層次聚類作為網頁集聚類的算法。因為層次聚類算法首先假設所有文檔自成一類，然后將最相似的兩類合并，并繼續這一過程，直到最后將所有文檔合并為一類，因而可以形成一棵聚類樹。層次聚類的優點在于可以適用于任意形狀的類別并且適用于任意形式的相似度或距離形式。另外，聚類粒度比較靈活性，聚類質量比較高，在信息檢索的應用背景下，層次聚合聚類在檢索相關文檔方面要比基于劃分的算法要好。

從網頁集中獲取主題詞，許多方法是將單個網頁頁面主題詞提取技術用于網頁集主題詞的提取。目前，網頁集主題詞的提取常見的方法有：

1.先建立特定領域的模板，再從文檔中提取信息填充模板，通過比較模板的內容，獲取共同部分生成主題詞；

2.建立文檔中的實體名對，通過分析實體名的出現頻率確定網頁集中各網頁的相關程度；

3.先建立詞的活動網絡，再從中提取文本的中心內容。另外，當前網頁集主題詞提取研究的主要方向是基于統計的機械式文摘方法。但是，越來越多的現象表明，統計并不能完全取代語義分析。不考慮句子的含義和句子間的關系機械抽取，必然導致主題詞的準確率低，連貫性差，產生一系列問題。因此，理想的網頁集主題詞提取模型應當將兩種方法相結合。

三、試驗設計與結果分析

為了測試我們的算法，我們選擇了兩組不同的數據。

第一組數據是體育方面的文章，是通過spider從fm365網站上搜集的，包含485篇文章。經過切詞處理，去掉停用詞（stop words）后保留了2719個特征詞。通過人類專家手工分類，將文檔分為六類，如下：

第二組數據是文藝類的文章，也是通過spider從互聯網上獲取的，包含了1199篇文章。在去掉停用詞后保留了15171個特征詞。通過預處理，將在文章中出現頻率少于0.1%或多于90%的詞過濾后（見第四章），保留了7542個特征詞。通過人類專家手工分類，這1199篇文章被分到六個不同的類別中：

值得注意的是，文藝類數據中各個類別的區分不像體育類中那么明顯，特別是某些類別涵蓋面非常廣泛，比如時尚、笑話、其他的范圍非常大，因而在幾百篇文章中并不能使其統計規律得到充分的體現，由此會帶來較大的誤差。如果沒有對語義的理解，可以想象即使是人類專家要對他進行合理的分類也有相當的困難。

對這兩組數據，我們用K-means，Ward’s method，HBC，以及本文提出的聚類算法分別作了測試（K-means，Ward’s method使用SPSSv10.0 進行的測試）。

使用K-means算法聚類，對于文藝類數據，聚類目標為6個類別時，最大的類別包括了974篇文章，并且準確率只有54.13%。對于體育類數據，當聚類目標為6時，最大的類別包括了446篇文章，準確率為53.28%。使用Ward’s method進行聚類，進行聚類，對文藝類數據達到的最高的準確率為62.41%，對體育類的準確率為61.41%。

這兩種算法的準確率均遠低于HBC算法和本文介紹的其他算法，因而下面的討論中不再考慮它們，而只與HBC算法進行對比。

對于文藝類數據：

三種算法在恰好分為六個類別時每個類別的文章數量，如下表所示：

總體來看三個算法產生的結果都沒有明顯的失衡，MED與HBC算法的分類都非常均勻，這兩個算法的第一個類別出現了較大的偏差，經對比，此類別中的文檔主要來自“其他”類。各種聚類方法的準確率如下：

從總體結果來看，MED算法取得了最佳的效果，相對MEI有了一定的改進。與HBC算法相比準確率也有明顯的提高。

四、結論

本文所采用的分詞技術，并不是簡單的按照空格，標點來進行英文單詞的分詞，而是采用了Brown大學的Charniak's parser。這個工具可以將輸入的文本的句子結構解析出來，同時可以把句中的名詞短語，動詞，以及介詞，副詞劃分出來，標上詞性。因此，這樣很多名詞短語，如人名、專有名詞都可以很好的解釋出來，對比普通的分詞工具，對主題的抽取的準確性有了很大的改進。并且我們引入了共指消解，利用了著名的共指消解系統GuiTAR進行了文本的共指消解的處理，使得我們可以知道文本中的代詞所指代的名詞，因此在詞頻統計時，將代詞所指代的名詞的詞頻加上相應的代詞出現的次數。這樣就既解決了主題抽取的結果中會出現無謂的高詞頻的代詞的現象，同時還增加了主題抽取的準確性。另外，本文在進行網頁集的主題抽取之前，利用單個網頁本身的主題詞進行了基于語義相似度的網頁的聚類，使得擁有不同主題的網頁聚集到不同的類中，從而減少了不同主題的網頁產生的噪聲。而且，利用主題詞之間的語義相似度，而不是單純的計算關鍵字的內積，使得網頁之間的語義信息得以保留，也提高了主題抽取的準確性。

參考文獻：

[1]Georgios Paliouras. Discovery ofWeb user communities and their role in personalization[J].Springer Science+Business Media B.V.10 March 2012.

[2]唐煥玲.文本分類系統SECTSCS中若干技術問題的探討[J].計算機工程與應用，2003（11）.

[3]陳克利.基于大規模真實文本的平衡語料分析與文本分類方法[C].Advances in Computation of Oriental Languages.北京：清華大學出版社，2003.

[4]Nazir，A.，Raza，S，Chuah， C.N.： Unveiling facebook：ameasurement study of social network based applications.In： Papagiannaki，K.，Zhang，Z.L.（eds.）Proceedings of the Eighth ACM SIGCOMM Conference on Internet Measurement， Vouliagmeni，43-56（2008）.

[5]Chris Fraley and Adrian E.Raftery， Model-Based Clustering， Discriminate Analysis， and Density Estimation，Technical Report NO.380，Department of Statistics， University of Washington，October 2000

[作者簡介]朱一（1964-），女，河南開封人，碩士，高級講師，研究方向：研究方向為數據庫等。