Web文檔聚類研究及系統實現

摘要:在對文檔聚類技術進行系統研究的基礎上，實現了Web文檔聚類系統，包括文檔預處理模塊、文檔聚類模塊、結果評估模塊以及用戶接口模塊。實現了包括統計頻數、反轉頻數并計算相應的頻率以及權值等功能。分析研究了數據預處理、聚類算法以及算法效果評估，重點分析了k-means算法，并提出了實現方案，詳細說明了各個模塊的設計原理及實現方法。

關鍵詞:文檔聚類;頻數;K-means;預處理

中圖分類號:TP311文獻標識碼:A文章編號:1009-3044(2010)21-6066-02

Research of Web Document Clustering and Implementation

DONG Chun-zhao， CHEN Wei， LIU Bin

(Southwest Jiaotong University， Chengdu 610031， China)

Abstract: On the foundation of web clustering analysis， our group developed the web document clustering system， including data preprocessing module， document clustering module， algorithm evaluation module and user interface module. The system achieved computing the statistics frequency， reversal frequency， the frequency of corresponding word and the weight of corresponding word. We analyzed the data preprocessing， clustering algorithm and evaluation of the algorithm， especially analyzed the k-means clustering algorithm. We proposed the implementation ways， in addition， explain the design principles and way of implementation of each module in detail.

Key words: document clustering; frequency; k-means algorithm; preprocessing

1 研究背景及意義

隨著信息技術的發展，數據挖掘技術已經得到了人們越來越多的關注和研究。在其中，聚類分析，作為數據挖掘的一個分支，在商務化、智能化中起的作用尤為重要。生活中到處都有聚類的影子，它離我們并不遙遠，面對數以萬記的信息資源，沒有一個代替人類進行聚類的軟件是行不通的。

所謂聚類，就是把一組雜亂無章的對象按照相似性歸成若干類別，使得屬于同一類別對象之間的距離盡可能小，而不同類別對象間的距離盡可能的大。Web文檔聚類就是把網絡中的文檔按相似性歸成若干類別，這樣便可以實現對Web文檔的有效篩選和管理。

2 系統的總體架構及各模塊介紹

系統的總體框架圖如圖1所示，由下到上依次為文檔來源層，聚類實施層，用戶接口層。文檔來源層主要是提供Web文檔資源，聚類實施層是聚類系統的核心，完成Web文檔聚類和結果評估，用戶接口層是將聚類實施層的結果反饋給用戶，以直觀的圖形化展現聚類的結果。

2.1 Web文檔的獲取

使用RSS閱讀器Google Reader下載大量的新聞，并使用網頁提取助手提取新聞正文，完成Web文檔的獲取工作，為后續模塊提供數據來源。

提取正文的過程包括:

1) 去掉網頁中的導航信息

2) 去掉HTML網頁中的tag標記

3) 去掉不合適的文檔或文檔內垃圾數據

2.2 文檔預處理模塊

通常來說，Web文檔數據只有一定的結構，甚至很多都沒有結構，并且文本文檔的內容是由英語等自然語言描述的，計算機還不能夠智能的識別和理解這些語言。所以需要對如今網絡上大量的Web文本進行相應的處理，提取文本的特征。

首先需要對文本文檔進行預處理，包括排除出現頻率很高但是對文章的理解并不會造成很大影響的含義虛泛的詞語，例如 a，an，is，the等;排除在文本中出現頻率很小的詞;去除噪詞提取詞干，英文詞要轉換成他的詞根，很多不同時態的實詞要將其回歸成原形。

① 去掉虛高頻詞

高頻詞，是在實際應用中，出現次數多、使用較頻繁的詞，虛高頻詞是沒有多大實際意義的高頻詞，例如，在英語文章中常常見到的the，a，an，on，in，about，but，by，for，to，are，is，am，were，this，was等。

② 去掉低頻詞

低頻詞，是在實際應用中，出現次數少、使用較少的詞。比如一些生僻的詞。

③ 去除噪詞提取詞干

噪詞指的是一個實詞有多種不同的時態表示方式，實詞不同的時態表示的意思往往差別不大，如動詞有不同的時態，名詞有單復數的形式等。為了便于對這些詞進行統計，需要先將其還原成原形，這個過程稱之為提取詞干。這樣能排除詞的不同形態造成的干擾，使聚類算法的準確性得以提高。

2.3 文檔聚類模塊

此模塊實現了統計頻數、反轉頻數并計算相應的頻率以及權值的功能。

2.3.1 統計頻數計算權值

頻數(即在某篇文章中，某個詞出現的次數)，頻率(即頻數除以該篇文章的總詞數)，某篇文章中的某個詞頻數和頻率較容易計算。

然后就可以用選定的權值計算方法計算文檔中各個詞的權值。筆者選定ITC函數作為特征權值計算函數，它應用廣泛，效果較好，從筆者所在小組實現情況來看，它形式較簡單，并且較好地代表了文檔的特性。

ITC權值計算公式如下:

(1)

其中aik表示詞 在k中的權值;fik表示單詞k在文檔i中出現的頻率;N是全部文檔數。

2.3.2 提取特征詞

特征詞的選擇有以下三個原則:

1) 選取那些包含語義信息較多，對文本表示能力較強的語言單位作為特征性;

2) 這種選取的過程本身應當比較容易實現，其時間和空間開銷都不應過大;

3) 文本在這些特征項上的分布應當有比較明顯的統計規律性;

為了有效的表示文檔的特征，通常，按照權值從高到低的順序選取一定數量的權值較大的詞作為該文檔的特征詞(特征項)。這些特征詞能夠有效地表示文本內容，并能將目標文本與其他文本區分開來。本系統中選取特征詞的個數為30個。

2.3.3實施k-means聚類算法

使用K-means方法對文檔進行聚類，K-means方法 是屬于劃分方法的一種聚類算法，是一種應用廣泛的聚類算法。該算法劃分思路是以k為參數，把n個對象分為k個簇，以使每一簇的內部具有較高的相似度，而簇與簇之間具有較低的相似度。相似度根據簇中對象的平均值(簇的重心)來計算。k個聚類具有以下特點:各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。

K-means算法的流程圖如圖2所示。

然而K-means也有自己的不足之處即是必須事先給出要生成的聚類數目k。采用不同的測度函數將會產生不同的聚類結果。筆者采用應用最普遍的均方差作為標準測度函數，公式如下:

(2)

J表示文本集中所有對象與相應聚類中心的均方差之和，oi表示第i個文本對象，Zj表示第j個聚類中的文本數，d(oi，cj)表示oi與cj之間的距離。

2.4 結果評估模塊

本系統采用熵值、純度對聚類結果進行評估。這兩種評估方法均屬于監督評估方法，其中熵代表了一個體系的混亂程度，即代表了聚類結果的混亂程度，因此，熵值越小結果越好;純度代表了一個體系的純凈度，即代表了聚類結果的純凈程度，因此，純度值越大結果越好。

熵的計算公式為:

(3)

其中pij為類簇i的成員屬于類j的概率;

純度的計算公式為:

(4)

其中Purityi表示Pij的最大值。

3 結束語

本系統基于ITC權值計算方法和K-means聚類算法，實現了讀入新聞正文、提取詞干、計算權值、聚類、聚類結果可視化的功能，以實現對Web文檔信息和數據的有效篩選和管理。未來的主要工作包括:橫向擴展已有的系統功能，包括采用多種不同的權值計算方法和多種不同的聚類算法，來檢驗權值計算方法對聚類的影響程度和不同聚類算法的聚類效果，最終使系統更好的完成聚類的功能。

參考文獻:

[1] 王麗坤，王宏，陸玉昌.文本挖掘及其關鍵技術與方法[J].計算機科學，2002，129(12):12-13.

[2] 安淑芝.數據倉庫與數據挖掘[M].北京:清華大學出版社，2005.

[3] Pang-Ning Tan， Michael Steinbach， and Vipin Kumar， Introduction to Data Mining， Pearson Education， Inc， 2005.

[4] 章成志，師慶輝，薛德軍.基于樣本加權的文本聚類算法研究[J].情報學報，2008(1).