分層聚類算法在文本挖掘中的應用

劉卓 徐斌

蘇州科技學院電子與信息工程學院 江蘇 215011

0 引言

自20世紀80年代以來，隨著Internet技術的高速發展，信息化的浪潮席卷全球，社會的每個角落都有了數字化信息的身影。其中尤其以Web頁數量最為龐大，并且大約以每4至 6 個月翻一倍的速度增加。巨量的 Web頁在為我們提供了海量的信息同時，又給我們提出了新的挑戰，即如何從這些浩瀚的Web頁信息中快捷準確地得到我們想要的信息。自然我們不能夠采用人工的方式完成這項任務，借助于計算機采用數據挖掘的方法是目前廣泛使用的技術。

1 Web文本挖掘概述

數據挖掘(data mining)習慣上又稱為數據庫中知識發現(Knowledge Discovery in Database, KDD)，簡單的說就是利用計算機，從浩瀚如海的信息資源中找出真正具有價值的信息。數據挖掘可以按以下不同角度分類：從挖掘的數據源分類，一般可以分為關系數據庫、事務數據庫、空間數據庫、時間數據庫、面向對象數據庫、文本數據庫、多媒體數據庫、主動數據庫、Internet信息庫挖掘等。從挖掘出的知識分類，一般情況下，數據挖掘可以分為關聯規則、特征規則、分類規則、聚類規則、序列模式、數據綜合和概括、總結規則 、趨勢分析、偏差分析、模式分析、孤立點分析挖掘等。按照挖掘所采用的技術分類，數據挖掘一般可以分為統計分析方法，遺傳算法、粗糙集方法、決策樹、人工神經網絡、模糊邏輯、規則歸納、聚類分析、模式識別、最鄰接技術、可視化技術挖掘等。Web挖掘就是數據挖掘方法中的一種，它是指從大量Web文檔的集合C中發現隱含的模式p。如果將C 看作輸入，將p看作輸出，那么Web挖掘的過程就是從輸入到輸出的一個映射N: C→p。按照挖掘對象的不同，Web挖掘又可以分為兩類：內容挖掘和結構挖掘。內容挖掘指的是從Web文檔的內容信息中抽取知識，結構挖掘指的是從 Web文檔的結構信息中推導知識。Web內容挖掘又分為對文本文檔(包括 text，HTML 等格式)和多媒體文檔(包括image，audio，video 等媒體類型)的挖掘。Web 文本挖掘可以對Web上大量文檔集合的內容進行總結、分類、聚類、關聯分析，以及利用 Web 文檔進行趨勢預測等。本文所探討的對象為針對于Web文本文檔的挖掘。

2 Web文本挖掘中的聚類算法

聚類是根據個體所滿足的屬性對個體域進行剖分，把屬性相同或相近的個體劃歸為同一個“概念類”的過程，它是機器學習領域中的一個重要研究方向。文檔聚類的目標即使將文檔聚集成類，使得類與類之間的相似度盡量的小，而類內的相似度盡量的大。處理聚類問題，主要有以下幾種方法：統計方法、機器學習方法、神經網絡方法和面向數據庫的方法等。

聚類算法一般分為分割聚類法和分層聚類法。分割聚類算法通過一個評價函數把數據集分割為K個部分，需要K作為輸入參數。典型的分割聚類算法有 K-means 算法、K-medoids 算法、CLARANS 算法；分層聚類是由不同層次的分割聚類組成，層次之間的分割具有嵌套的關系，不需要K作為輸入參數。典型的分層聚類算法是 BIRCH算法、DBSCAN算法和CURE算法。目前，使用聚類方法自動建立文檔的類別過程通常如下所示：

（1）輸入多篇無類別標識的文本。

（2）借助詞典對這些文本進行分詞處理。

（3）提取每一個文本的特征向量。

（4）利用文本的特征向量，使用聚類算法進行類別組合計算。

（5）人工為每個得到的文本類別建立類別標識。

3 分層聚類法算法實現

本文采用分層聚類法并結合了改進的特征詞權重計算等方法，進行了無類別文檔集合的劃分處理。具體算法如下：輸入：無文本類別標識的文本集輸出：標識了類別的訓練文本集（1）文本分詞處理。

（2）統計詞頻，完成非完整詞串取舍，提取出文本文檔中的關鍵詞。

（3）公式(1)計算詞的特征值。

（4）按照詞的特征值使用插入排序算法遞增排序，并從排好序的詞集中提取前M個詞作為當前文檔的特征詞，從而得到每一個文檔的特征向量di(i=1,2,3,……,n)。

（5）di看作是一個具有單個成員的類Ci={di}，從而構成了該文檔集合的一個聚類C(n)={c1,c2,……,cn}。

（6）用公式(2)計算C中每對類(ci,cj)之間的相似度。

（7）選取具有最大相似度的類對，并將其合并為一個新的類，從而構成該文檔集合的一個新的聚類 C(n-1)={c1,c2,……,cn-1}。

（8）如果n!=1，轉到步驟3。

（9）對各個類文檔進行人工建立標號。算法說明：

其中：P為位置加權系數，Q為受限語義加權系數，L為Wi的長度，Ti為在文檔中出現的頻率，S為總文檔數，SD為在其中出現至少一次的文檔的數目。

其中：n為文檔 dx與 dy共同所有的特征詞個數，|dx|文檔dx中特征詞總數，|dy|文檔dy中特征詞總數，txk為向量dx第k維值。

4 結束語

本文對文本挖掘中所使用的層次聚類分析方法進行了探討，通過以上聚類算法的分析處理，我們可以在一定范圍內完成對各類訓練文本庫的建立。但是針對于公式中參數的選取還需要進一步的研究，以便在更大范圍內完成訓練語料庫的建立。

[1] 鄒臘梅,肖基毅,龔向堅.Web 文本挖掘技術研究.情報雜志.2007.

[2] 王繼成,潘金貴,張福炎.Web 文本挖掘技術研究.計算機研究與發展.1999.

[3] J.Han,Micheline,Kamber,Data,Mining:Concepts and Tchniques.San Mateo,CA:Morgan Kaufmann.2000.

[4] 張紅云,石陽,馬垣.數據挖掘中聚類算法比較研究.鞍山鋼鐵學院學報.2001.

[5] 于琨,糜仲春,蔡慶生.可應用與互聯網的自學習中文關鍵詞抽取算法.中國科學技術大學報.2002.

[6] 顧立帆,王永成.聯想樹分析方法及其在無詞庫中文自動標引中的應用.情報學報.1992.

[7] 何新貴,彭甫陽.中文文本的關鍵詞自動抽取和模糊分類.中文信息學報.1998.

[8] 羅三定,陸文彥,王浩,賈維嘉.基于概念的文本類別特征提起與文本模糊匹配.計算機工程與應用.2002.

[9] 孫麗華,張積東,李靜梅.一種改進的 KNN 方法及其在文本分類中的應用.應用技術. 2002.