王健

摘 要 本文闡述了基于WEB的文本分類的關鍵技術，從網頁的解析、文本的表示、降維技術到分類算法進行詳細的論述，并對兩個K-means算法和Baygers算法做了改進。

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

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

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

1網頁的解析

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

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）表示逆文檔頻率，反映文檔集合中出現該特征項的文檔數目。

3降維技術

3.1信息增益

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

3.2互信息：（MI）

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

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

4分類算法

4.1 K-means算法

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

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

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

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

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

4.2樸素貝葉斯算法

利用對研究對象的已有認識-先驗概率作為基礎，進行判斷。它具有最小的出錯率，在誤差率要求較高的應用上，它具有很大的優(yōu)勢。但貝葉斯算法需要已知條件的概率，而且其決策面往往是超曲面，形狀復雜，難以計算和構造。樸素貝葉斯是貝葉斯算法的改進，假設一個屬性對一個給定類的影響獨立于其它屬性的值。這一假定成為類條件獨立。它簡化了原來貝葉斯算法的計算，提高了算法效率，可以用于大型數據庫，并且已表現出高準確率和高速度。

樸素貝葉斯算法的本質是用詞和類別的聯合概率估計給定文檔屬于各個類別的概率。它假設，一個詞在給定類別的條件概率獨立于該類的其它詞的條件概率。這樣，就以降低分類精度的代價換來了較高的執(zhí)行效率。

參考文獻

[1] 姚天順.自然語言理解[M].北京：清華大學出版社，1995.

[2] 吳立德.大規(guī)模中文文本處理[M].上海：復旦大學出版社，1997.

[3] 王永成，許慧敏.OA中文文獻自動摘要系統(tǒng)[J].情報學報，1997，16（02）：128-132.