文本分類的關(guān)鍵技術(shù)

王健

摘 要 本文闡述了基于WEB的文本分類的關(guān)鍵技術(shù)，從網(wǎng)頁的解析、文本的表示、降維技術(shù)到分類算法進(jìn)行詳細(xì)的論述，并對兩個K-means算法和Baygers算法做了改進(jìn)。

關(guān)鍵詞 文本分類 降維技術(shù) 文本表示 分類算法

中圖分類號：TP311文獻(xiàn)標(biāo)識碼：A

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

1網(wǎng)頁的解析

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

2文本表示

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

3降維技術(shù)

3.1信息增益

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

3.2互信息：（MI）

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

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

4分類算法

4.1 K-means算法

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

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

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

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

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

4.2樸素貝葉斯算法

利用對研究對象的已有認(rèn)識-先驗(yàn)概率作為基礎(chǔ)，進(jìn)行判斷。它具有最小的出錯率，在誤差率要求較高的應(yīng)用上，它具有很大的優(yōu)勢。但貝葉斯算法需要已知條件的概率，而且其決策面往往是超曲面，形狀復(fù)雜，難以計(jì)算和構(gòu)造。樸素貝葉斯是貝葉斯算法的改進(jìn)，假設(shè)一個屬性對一個給定類的影響?yīng)毩⒂谄渌鼘傩缘闹怠＿@一假定成為類條件獨(dú)立。它簡化了原來貝葉斯算法的計(jì)算，提高了算法效率，可以用于大型數(shù)據(jù)庫，并且已表現(xiàn)出高準(zhǔn)確率和高速度。

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

參考文獻(xiàn)

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

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

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