基于K—means算法的文本分類技術研究

王健

摘 要 文本分類技術是網絡信息挖掘中內容挖掘的重要手段之一，通過文本的分類技術可以將網絡中紛繁復雜的信息分門別類的組織在一起，從更深的層次來尋找文檔之間的聯系本文，闡述了基于K-means算法的文本分類的關鍵技術，從網頁的解析、文本的表示、降維技術到分類算法進行詳細的論述，并對兩個K-means算法做了改進。

關鍵詞 文本分類 降維技術 文本表示 分類算法

中圖分類號：TP393 文獻標識碼：A

文本分類是指在給定分類體系下，根據文本內容自動確定文本類別的過程，將大量的文本歸到一個或多個類別中。從數學角度來看，文本分類是一個映射的過程，將未標明類別的文本映射到己有的類別中來，數學表示如下：f：A->B 其中A為待分類的文本集合，B為分類體系下的類別集合。

文本分類技術是網絡信息挖掘中內容挖掘的重要手段之一，通過文本的分類技術可以將網絡中紛繁復雜的信息分門別類的組織在一起，從更深的層次來尋找文檔之間的聯系，不只停留在字面的匹配上。文本分類技術應用于信息檢索中有利于提高檢索的正確率和準確率。

1網頁的解析

按照W3C組織所制定的標準，每一個HTML頁的結構都可以對應地描述成DOM樹的形式。DOM定義了HTML文檔的邏輯結構，提供了一種對網頁中的數據及內容進行管理和操作的途徑。DOM將整個文檔的內容分別抽象為不同的對象，用結點的形式予以表示，如標簽結點、文檔類型結點、文本結點、注釋結點、屬性結點等。再用類似于父子的關系將各結點按照不同層次有順序地組織起來，形成樹型結構。

2文本表示

向量空間模型（Vector Space Model，簡記為VSM）是一種較著名的用于文檔表示的統計模型，該模型以特征項做為文檔表示的基本單位，特征項可以由字詞或短語組成。每一個文檔可以看成是由特征項組成的n維特征向量空間的一個向量：D=（T1，W1；T2，W2；T3，W3……；Tn，wn），其中Wi為第i個向量Ti在文檔中的權重，一般選詞做特征項比選字做為特征項要好一些。一般使用TF-IDF公式計算特征項權重，其中TF（Term Frequency）表示詞頻，IDF（Inverse Document Frequency）表示逆文檔頻率，反映文檔集合中出現該特征項的文檔數目的頻率，TF-IDF權重公式如公式（1）所示：

3降維技術

3.1信息增益

信息增益在機器學習中經常被用做特征詞評判的標準，它是一個基于熵的評估方法，定義為某特征項在文檔中出現前后的信息熵之差。根據訓練數據計算出各特征詞的信息增益。刪除信息增益很小的詞，其余的按信息增益從大到小排列。如果以信息增益最大者為要根結點，建立一個決策樹就可以進行決策樹的分類挖掘。如公式（2）所示。

其中i=1，2…M。p（ci）表示類文本在語料中出現的概率，p（ci|w）表示文本包含特征項W時屬于ci類的條件概率，p（w）表示語料中不包含特征項W的文本的概率，p（ci|w）表示文本不包含特征項W時屬于ci類的條件概率，M為類別數。

3.2互信息（MI）

應用在相關詞統計建模中，在統計學中用于表示兩個變量間的關系，其計算如下公式（3）所示：

顯然當特征項W獨立于ci時它同該類的相關度為0 ，p（w）越小而同時p（w|ci）越大時特征項W提供類別ci的信息量越大，則這個特征項越能代表這一類，反之，p（w）越大的同時p（w|ci）越小，則可能得到負的互信息值，這種情況下，該特征項對分類的意義同樣很大。

3.3交叉熵（expected cross entropy）

與信息增益類似也是一種基于概率的方法，但只計算出現在文本中的特征項，其計算如公式（4）所示：

4分類算法

K-means算法是應用最廣泛的聚類算法之一，是一種已知聚類類別的聚類算法。指定類別數k，對樣本集合進行聚類，聚類的結果由k個聚類中心來表達。相似度的計算根據一個簇中樣本的平均值（被看作簇的中心）來進行。

首先，隨機選擇k個對象，每個對象初始的代表了一個簇的平均值或中心。對剩余的每個對象，根據其與各個簇中心的距離，將它賦給最近的簇。然后重新計算每個簇的平均值。這個過程不斷重復，直到準則函數收斂。通常，采用平方誤差準則，其定義如下：

這里的E是數據庫中所有對象的平方誤差的總和，p是空間中的點，表示給定的數據對象，mi是簇Ci的平均值（p和mi都是多維的）。這個準則試圖使生成的結果簇盡可能的緊湊和獨立。下面是K-means過程的概述。

輸入：聚類的數目k和包含n個對象的數據庫。

輸出：k個聚類簇，使平方誤差準則最小。

（1）任意選擇k個對象作為初始的聚類簇中心；

（2）重復；

（3）根據聚類簇中對象的平均值，將每個對象（重新）賦給最相似的聚類簇；

（4）更新聚類簇的平均值，即計算每個簇中對象的平均值；

（5）直到不再發生變化。

這個算法嘗試找出使平方誤差函數至最小的k個劃分。當結果簇是密集的，而簇與簇之間區別明顯時，它的效果較好。對處理大數據集，該算法是相對可伸縮的和高效率的，因為它的復雜度是O（nkt），其中，n是所有樣本的數目，k是聚類簇的數目，t是迭代的次數。通常的k<

但是，K-means只有在簇的平均值被定義的情況下才能使用。這使得它不適用某些應用，例如涉及到分類屬性的數據。要求用戶必須事先給出k，可以算是該方法的另一個缺點。同時K-means不適合發現非凸面形狀的簇，或者大小差別很大的簇。而且，它對于“噪聲”和孤立點數據是敏感的，少量的該類數據能夠對平均值產生極大的影響。

參考文獻

[1] 高潔，吉根林.文本分類技術研究[J].計算機應用研究，2004（3）：23-25.

[2] 高倬賢.中國圖書館圖書分類法與日本十進分類法比較研究[J].圖書館學研究，1999（6）：23-31.