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

王健

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

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

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

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

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

1網(wǎng)頁的解析

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

2文本表示

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

3降維技術

3.1信息增益

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

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

3.2互信息（MI）

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

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

3.3交叉熵（expected cross entropy）

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

4分類算法

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

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

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

輸入：聚類的數(shù)目k和包含n個對象的數(shù)據(jù)庫。

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

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

（2）重復；

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

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

（5）直到不再發(fā)生變化。

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

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

參考文獻

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

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