基于內容的文本分類算法綜述

律佳

【摘要】隨著信息技術的發展，人們已經從信息缺乏的時代過渡到信息極為豐富的數字化時代，可以獲得越來越多的數字化信息，而這些信息大都是半結構化或非結構化數據，為了從中快速有效地獲得自己需要的信息，我們需要研究基于內容的文本信息分類技術。

【關鍵詞】k-元最近鄰居算法；貝葉斯算法；決策樹算法；支持向量機算法

1.引言

目前很多分類算法被研究者從不同角度提出，判斷不同分類算法的好壞可以由準確率、速度、健壯性、可伸縮性、可解釋性等幾個標準來衡量。經典的分類算法在不同的領域取得成功，比如貝葉斯算法、決策樹分類算法、KNN算法和支持向量機算法等。

2.文本分類算法

2.1貝葉斯（Na?ve Bayesian）算法

貝葉斯是一種概率方法，設每個數據樣本用一個 維特征向量來描述n個屬性的值，即：，假定有m個類，分別用表示。給定一個未知的數據樣本x（即沒有類標號），若樸素貝葉斯分類法將未知的樣本x分配給類，則一定是

根據貝葉斯定理，由于對于所有類為常數，最大化后驗概率可轉化為最大化先驗概率。如果訓練數據集有許多屬性和元組，計算的開銷可能非常大，為此，通常假設各屬性的取值互相獨立，這樣先驗概式（2）可以從訓練數據集求得。

根據此方法，對一個未知類別的樣本x，可以先分別計算出X屬于每一個類別的概率，然后選擇其中概率最大的類別作為其類別。

貝葉斯定理給出了最小化誤差的最優解決方法，可用于分類和預測。其特點是：

①貝葉斯分類并不把一個對象絕對地指派給某一類，而是通過計算得出屬于某一類的概率，具有最大概率的類便是該對象所屬的類。

②一般情況下在貝葉斯分類中所有的屬性都參與分類。

③貝葉斯分類對象的屬性可以是離散的、連續的，也可以是混合的。

2.2決策樹（Decision Tree）算法

在決策樹的內部結點進行屬性值的比較，并根據不同的屬性值從該結點向下分支，葉結點是要學習劃分的類。從根到葉結點的一條路徑就對應著一條合取規則，整個決策樹就對應著一組析取表達式規則。

2.2.1 ID3算法

70年代末。由J Ross Quinlan提出了ID3算法，ID3的具體方法是：檢測所有的屬性，選擇信息增益最大的屬性產生決策樹結點，由該屬性的不同取值建立分支，再對各分支的子集遞歸調用該方法建立決策樹結點的分支，直到所有子集僅包含同一類別的數據為止。最后得到一棵決策樹，它可以用來對新的樣本進行分類。

ID3算法的特點：算法的理論清晰，方法簡單，學習能力較強。但是ID3算法只對比較小的數據集有效，且對噪聲比較敏感，當訓練數據集加大時，決策樹可能會隨之改變。

2.2.2 C4.5算法

C4.5算法繼承了ID3算法的優點，并在以下幾方面對ID3算法進行了改進：

①用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足。

②在樹構造過程中進行剪枝。

③能夠完成對連續屬性的離散化處理。

④能夠對不完整數據進行處理。

C4.5算法的特點：產生的分類規則易于理解，準確率較高。但在構造樹的過程中，C4.5算法需要對數據集進行多次的順序掃描和排序，因而導致算法的低效；C4.5算法只適合于能夠駐留于內存的數據集，當訓練集大得無法在內存容納時程序無法運行。

2.3 k-元最近鄰居（K-Nearest Neighbor，KNN）算法

k-元最近鄰居算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。KNN算法具有以下特點：

①KNN算方法不依賴對基礎數據的嚴格規定，并能適應任何情況。②KNN算法由于判定邊界的任何特定子部分都依賴于少數輸入點和它們的特定位置，因而是擺動和不穩定的，即它具有高方差和低偏倚。③當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數。

2.4支持向量機（SVM-Support Vector Machine）算法

支持向量機算法是Vapnik等人根據統計學習理論提出的一種新的機器學習方法，其思想是以機構風險最小化原則為理論基礎，通過適當選擇函數子集及該子集中的判定函數使學習機的實際風險達到最小，保證了通過有限訓練樣本得到的小誤差分類器對獨立測試集的測試誤差仍然小。從算法本身及凸優化知識角度，可以得出該算法的下列特點：

①分類器有支持向量唯一決定。②多數情況下，支持向量的數目遠遠小于訓練集中的總樣本數量，從某種意義上說，壓縮了數據，保留了類別信息。③算法復雜度主要由訓練集樣本數量決定，而與訓練本身的維數關系不大。

3.分類算法的評價標準

分類算法可以根據下列標準進行評價和比較。

①預測的準確率。它包括模型正確地預測新的或先前未見過的樣本的類標號的能力。②計算速度。分類的時間包括構造模型和使用模型進行分類的時間。③強壯性。指正確預測含有噪聲和空缺值的數據集的能力。④可伸縮性。指對海量數據集有效地構造模型的能力。⑤模型描述的簡潔性和可解釋性。模型描述愈簡潔、愈容易理解，則愈受歡迎。

4.結束語

基于內容的文本分類技術的出現逐漸受到重視，是源于網絡用戶對信息獲取在數量得到滿足后的更高的一種要求。本文對目前比較優秀的各種分類算法進行了介紹、分析。綜合提出了評價分類算法好壞的5條標準。實際上，上述這些算法的準確度差別不大，在當今數據量急劇增長的時代，算法的執行速度、可伸縮性以及輸出結果的可理解性等特性更為重要。此外，由于分類的效果一般和數據的特點有關，目前還不存在能適合各種不同數據的優良分類方法，一種各方面特性都很好的分類算法仍有待進一步研究。

參考文獻

[1]明均仁，張帆.網絡文本信息過濾的意義及其模型初探.圖書與情報[J].2007，37-4

[2]孫建軍，成穎.信息檢索技術[M].科學出版社，2004：81～683