基于KNN+層次SVM的文本自動分類技術

王金華　喻　輝　產　文　周向東　施伯樂

1(中國電子科技集團公司第三十二研究所　上海 200233)

2(成都軍區通信網絡技術管理中心　四川 成都 610000)

3(復旦大學計算機學院　上海 200433)

?

基于KNN+層次SVM的文本自動分類技術

王金華1喻輝2產文3周向東3施伯樂3

1(中國電子科技集團公司第三十二研究所上海 200233)

2(成都軍區通信網絡技術管理中心四川 成都 610000)

3(復旦大學計算機學院上海 200433)

摘要針對大規模文本的自動層次分類問題，K近鄰(KNN)算法分類效率較高，但是對于處于類別邊界的樣本分類準確度不是很高。而支持向量機(SVM)分類算法準確度比較高，但以前的多類SVM算法很多基于多個獨立二值分類器組成，訓練過程比較緩慢并且不適合層次類別結構等。提出一種融合KNN與層次SVM的自動分類方法。首先對KNN算法進行改進以迅速得到K個最近鄰的類別標簽，以此對文檔的候選類別進行有效篩選。然后使用一個統一學習的多類稀疏層次SVM分類器對其進行自上而下的類別劃分，從而實現對文檔的高效準確的分類過程。實驗結果表明，該方法在單層和多層的分類數據集上的分類準確度比單獨使用其中任何一種要好，同時分類時間上也比較接近其中最快的單個分類器。

關鍵詞自動文本分類KNN層次SVM

INTEGRATING KNN AND HIERARCHICAL SVM FOR AUTOMATIC TEXT CLASSIFICATION

Wang Jinhua1Yu Hui2Chan Wen3Zhou Xiangdong3Shi Bole3

1(The 32nd Institution of China Electronics Technology Group Corporation,Shanghai 200233,China)2(Network Management Center of Chengdu Military Area Command,Chengdu 610000,Sichuan,China)

3(School of Computer Science,Fudan University,Shanghai 200433,China)

AbstractFor automatic hierarchical classification of large-scale text, k-nearest neighbours (KNN) algorithm has higher classification efficiency but is not effective for classifying the samples on the borders of categories. The support vector machine (SVM) classification algorithms have higher accuracy, however a number of previous multi-class SVM algorithms are composed of a number of independent binary classifiers, thus they become slower in training process and are not suitable for hierarchical category structures. This paper presents a new method which integrates both KNN and hierarchical SVM algorithm for automatic text classification. First we modify the KNN algorithm to quickly obtain K class labels of the nearest neighbours, and effectively sift out candidate categories of the documents with them. Then we use a multi-class sparse hierarchical SVM classifier with uniform learning to make top-down categories partition on the sample, so that implement the efficient and accurate classification process on the documents. Experimental results demonstrate that the classification accuracy of this method on classification dataset with single-layer and multi-layer is better than just using either of the methods, meanwhile it is also close to the fastest single classifier in classification time.

KeywordsAutomatic text classificationK-nearest neighbourHierarchical support vector machine

0引言

Web技術和新媒體的發展帶來了文本大數據的快速增長，隨著人們在互聯網上便利地交流，各類電子化的文本文件、資料、檔案等已逐步取代了紙質文檔。對文檔進行語義上的分類管理是傳統的文檔管理中普遍采用的有效方法，例如圖書館的書別目錄檢索。然而，面對海量的文本信息資源，傳統的人工分類在人力耗費、時間響應等方面已經無法滿足實際工作的需要， 因此亟待開發以自動文本分類技術為基礎的自動文本管理系統。

當前流行的自動文本分類算法主要有神經網絡NN(Neural Net)算法[1]、樸素貝葉斯NB(Na?ve Bayes)方法[2]、K近鄰KNN(K Nearest Neighbor)算法[3]和支持向量機SVM(Support Vector Machines)算法[4]等。Yang等[5]在數據集Reuters-2l578 上的實驗表明，相比于其他方法，KNN和SVM方法無論在召回率還是準確率上都有一定程度的提高。KNN算法原理簡單，分類效率較高，但其是一種基于實例的統計學習方法，對于處于類別邊界的樣本分類準確度不是很高。而SVM分類算法目標在于最大化分類邊界之間的距離，因此分類準確度比較高，但訓練分類器過程比較緩慢。總之，單獨使用這兩種方法中的任何一種都很難達到理想的分類效率和效果。

因此，研究者通過對KNN和SVM兩種算法進行有機結合，一方面提升分類的準確度，一方面提高分類效率，從使海量文檔自動分類達到較好的效果。文獻[6]提出一種將KNN與SVM相結合的文本分類算法。首先使用KNN算法找出與文本最接近的K個鄰居的類標簽，然后在鄰居類標簽集上使用多個二值SVM分類器對樣本進行精分，在減少有效候選類數目的同時，有效提高了分類的準確度。然而，由于這些二值分類器分別由不同的訓練樣本單獨訓練得到，可能無法保證學習得到的分類面在分類輸出上保持良好的可比性。另一方面，其假設的單層文本類別結構在實際中往往是較少數的。文獻[7]則首先使用所有類的SVM分類器對樣本進行劃分，然后對各類別的輸出概率進行比較。只有當最大輸出值(預測正確類)與次大輸出值(其它最具混淆性的錯誤類)之間的差大于某個閾值時，才將該結果作為分類器的最終輸出結果。如果其差值小于該閾值，則進一步使用KNN分類器來得到最終結果。這樣提高了分類輸出結果的置信度，然而，在最壞情況下，該方法的分類過程是SVM和KNN方法的線性疊加，分類的效率有所下降。

當文檔的類別結構形成一個層次目錄時，層次分類算法不但能顯著地帶來分類效率的提升，甚至能提高分類的準確性[8]。而大多數情況下，由于海量的文檔集包含的語義種類豐富，也很難使用扁平的一層類別目錄去包含它。在本文中，我們提出一種結合KNN和層次SVM分類的自動文本分類技術。在訓練階段，我們使用多類SVM算法統一對樣本的層次目錄進行學習，而不是獨立地學習多個二值分類器，這樣可以更有效地在各個層次分類面的輸出上進行比較。在分類階段，使用KNN對待分類樣本的標簽進行篩選之后，在分類候選集標簽上使用學習到的SVM分類器進行自上而下的劃分，有效減少了候選的SVM分類面的數目，加快了分類過程。同時排除了部分不相關的類別分類面的干擾，提高了自動分類的準確性。

1KNN與SVM算法

1.1KNN分類算法

K近鄰KNN分類算法是基于實例學習的統計方法。其主要思想是在輸入特征空間中計算訓練樣本里與待測試樣例最近的K個鄰居，通過這些最近的鄰居類別標簽來“投票”得出新樣本的最終類別標簽。

(1)

這樣后驗概率Pn(wi|x)的估計為：

(2)

也就是說，點x屬于類別wi的后驗概率就是體積V中標記為wi的樣本點的個數與體積中全部樣本點個數的比值。這樣，為了達到最小的誤差率，我們就選擇使這個比值最大的那個類別作為最后的分類判別結果。

然而， KNN算法通常需要計算待測樣本到所有訓練樣本的距離并排序，從而選出其最近的K個鄰居。假設每個樣本的特征維度為d,則上述步驟的時間復雜度為n×d+nlogn。在對海量文本進行分類時，n的值往往很大，特征維度也比較高。因此，為了加快KNN算法的執行效率，一般從兩個方面改進算法的分類效率:1) 降低樣本的維度，選擇最精簡的特征來表示文本向量，這種做法往往較為直觀，但是當維度過少時分類效果會顯著降低；2) 將訓練集中的相似文本適當歸并，將其作為一個文檔來處理，這樣將明顯減少需要比較的文檔數目。這里我們采用文獻[6]中的方法，在每個自然類別中再對其進行類別內部文檔的聚類，將其聚成j個子類。然后計算每個子類的中心向量，最后將待分類樣本與這些子類的中心向量計算距離，從而快速找出最近的K個鄰居中心。由于聚類后每個類別包含的文本數量急劇減少，因此KNN分類的算法效率有了明顯的提高。

1.2層次SVM分類算法

支持向量機SVM方法具有較為完備的理論基礎。在各種不同的實際應用中也表現出了較為優越的分類性能，并具有較高的計算效率，能夠高效處理大規模數據。支持向量機利用訓練數據來建模最大間隔超平面，然后使用超平面作為決策邊界，對未歸類的數據進行分類。所謂最大間隔，即訓練集樣本點到該超平面的最小幾何間隔最大，而間隔越大則泛化錯誤越小，對于新數據的分類判別能力就越強。最終分類超平面的建模實際上只需要用到離超平面最近的少數訓練樣本，這些樣本也就是“支持向量”，其他不是支持向量的訓練樣本點對分類超平面沒有任何影響，因此支持向量機方法具有較高的穩定性。圖1給出了支持向量機的示意。

圖1　最大化間隔超平面和支持向量示意圖

在實際應用中，文檔的類別結構通常具有明顯的層次分布而非單層扁平的結構。當多類別形成一顆層次樹時，研究者發現層次分類模型比其對應的單層分類模型更加快速甚至有時更加準確[8]。因此，我們的分類模型基于層次分類框架。在本文中，我們將統一學習出一個多類的層次SVM分類器，各分類面的目標函數在同一個優化函數中實現，而不是分別訓練多個二值分類器[6]。

首先，給出如下標記：令A(i)、C(i)、D(i) 和S(i) 分別表示層次類別中節點i的祖先、孩子、后裔和兄弟節點，且令A+(i) = A(i)∪i。X ? Rd表示含d-維訓練文本特征向量組成的集合，Y = {1,2,…,m } 為層次類別目錄上的節點類別對應的編號(根節點除外)。層次SVM分類的訓練過程如下：給定一組訓練文本集D={(x1,y1),…, (xN,yN)}，xk∈ X，yk∈ Y，k ∈ {1,…,N}，學習m個SVM分類面w = {wi}?Rd,i=1,…,m，每個對應層次目錄上的一個節點i。我們需要解如下的優化目標：

(3)

subject to

?i∈A+(yk)?k∈{1,…,N}

ξk≥0?k∈{1,…,N}

其中，前兩項是混合L1稀疏正則化和L2正則化項，第三項是hinge損失函數。C1、C2和C3是控制正則化項和損失函數平衡的參數。對于某個訓練文本k對應的層次類別樹上從正確的葉子節點yk到根節點路徑上的所有節點，該損失函數將懲罰那些當前層次上的正確標簽的分類輸出與其他各容易混淆的兄弟節點的分類輸出的差距小于1的情況。如果該差距越小，則對應的損失項越大，從而有效增加各層次上相似類別的判別能力。在多類別層次分類的時候，支持向量機中的支持向量往往變得比較稠密[10]。從減少存儲開銷以及分類時間的角度考慮，我們選擇學習一個節儉的模型，其中每個分類面僅僅由若干個稀疏特征的權重組合而成。因此在層次學習框架中我們引入L1稀疏正則化項來對分類面的參數進行懲罰[11]。盡管L1正則化項包含絕對值操作，但不難證明該多類層次SVM分類目標函數對參數w來說仍然是一個凸優化問題。因此，我們可以很容易地使用一些有效的優化方法去解上述優化問題。我們將在下一節中介紹該模型的訓練過程。

2KNN+層次SVM分類框架

2.1訓練層次SVM分類模型

為了訓練層次SVM模型，我們將1.2節的目標函數改寫為：

minimizeJ(w)=Ω(w)+H(w)+r(w)

(4)

其中：

由于前兩個等式右邊可導，我們可以通過計算Ω(w) 和H(w)的子梯度去解決。我們使用一個兩階段的算法[11]來解決不可導項r(w)，即正則化項中的稀疏問題。那就是，在每輪迭代t中，我們首先忽略r(w)且使用正則化對偶平均方法RDA(regularized dualaveraging)[12]來更新Ω(w)和H(w)中的參數wt并且得到臨時中間變量wt+1/2。然后使用FOBOS更新來解r(w)中的L1正則化項，即，第t+1輪迭代中的新參數如下方式得到：

(5)

2.2KNN+層次SVM算法流程

在算法的訓練階段，兩部分單獨進行。KNN訓練過程主要是對各個類中的子類進行聚類并找到最優的K值；層次SVM分類器的訓練如2.1節所示，主要得到層次類別樹上各分類面的參數。而在實際分類階段，算法首先利用KNN分類算法計算其最近的K個鄰居中心，然后統計其K個最近鄰居中的所有類別，對于每個類別分別調用相應的層次SVM分類器進行分類。“KNN+層次SVM”算法流程如下所示：

算法KNN+層次SVM分類算法

輸入樣本集和待測樣本x的特征向量

輸出待測樣本x的層次分類標簽

步驟：

1) 通過距離函數選擇與待測樣本x距離最近的k個訓練樣本中心(子類中心向量)；其中k為KNN訓練得到的最優參數。

2) 對于這k個樣本中心對應的每個類別wi，我們保留其對應的層次路徑作為候選集，將待測樣本x的特征向量輸入該候選集對應的各層次的SVM分類器，計算樣本x與路徑上各類的相似度。

3) 若與葉子節點wi類的相似度值最大，則將類別wi對應的層次路徑類別標簽作為樣本x的分類結果，算法結束。

“KNN+層次SVM”分類算法結合了KNN算法的時效性和SVM算法的準確性。通過SVM分類器對KNN分類器得到的鄰居標簽作為候選標簽集進一步分類，達到的準確度比較高。該方法尤其對于類別標簽比較多時更有效，可以使用KNN過濾掉一些明顯不需要調用的類別對應的SVM分類器。

2.3文本預處理和特征選擇

從原始的中文文本得到標準長度的文本向量需要一個文本預處理的過程。該過程主要由分詞、去停用詞和統計詞頻信息三部分組成。本文采用中科院計算所的開源分詞工具ICTCLAS[13]來實現。我們對每篇文檔中出現的詞統計其詞頻和出現的文檔數量(文檔頻率)，以計算文檔特征權重詞頻-反文檔頻率(TF-IDF)向量。在獲得以上統計信息后，計算特征詞典中每個特征詞對于每個類別的區分度。這里使用交叉熵和互信息計算特征區分度的方法，將其加權平均來選擇有效的特征。

3實驗設置和實驗結果

為了使文檔自動分類系統具備良好的穩定性、擴展性和可用性，更加具備分類的準確行，本系統主要依托成熟的數據庫系統來存儲、管理分類信息、文本數據及各類算法參數等。由于分類信息的圖結構特點，本系統采用Neo4J圖數據庫對網絡數據進行存儲。同時對海量文本數據采用Oracle關系數據庫進行存儲。

3.1實驗數據集

? 訓練文檔數1614，有5個類別，測試文檔數806，測試文檔中包含與訓練文檔中相同的5個類別；

? 5個類別分別為：工作計劃、軍事訓練、拉練、突擊、武器裝備；

? 每篇文檔平均大小為1.32 KB；

? 文檔特征維度為1000。

3.2實驗結果與分析

? KNN與SVM相結合分類準確率與單獨使用KNN或SVM的對比如表1所示；

? KNN與SVM相結合分類所需時間與單獨使用KNN或SVM的對比如表2所示；

? 在文檔維度為1000的條件下，SVM分類器的準確率為90.82% ；

? 在文檔維度為10 000的條件下，K-SVM分類器的準確率達到最高，為92.18%。

表1　KNN與SVM結合分類效果

表2　KNN與SVM相結合后所需時間

通過表1，我們觀察到：

1) 當K值在5~15之間時，KNN與SVM結合后的準確率隨K值的增大而增大；

2) 當K值在15~25之間時，改進后的準確率隨K值的增大而減小，并最后等于僅有SVM分類器的準確率。

通過表1、表2可見，當K值較大時，KNN和SVM的結合分類器逐漸退化為SVM分類器；當K值合適時，不僅可以提高分類速度，還可以提高分類準確率。

4結語

本文提出了一種混合使用KNN與層次SVM來對文本進行自動分類的方法。使用加速KNN對文檔的候選類別集有效篩選后，在較少量的統一學習的稀疏SVM分類器上進行最后的類別劃分，實現了對文檔的高效、準確的分類機制。在單層和多層的分類數據集上的實驗結果表明，該方法的分類準確度比單獨使用其中任何一種要好，同時分類時間上也比較接近其中最快的單個分類器。對于實際工程中的海量文本層次分類，該方法是解決大規模文本分類問題的值得參考的一種方法。

參考文獻

[1] Ng H T,Goh W B,Low K L.Feature selection,perceptron learning,and a usability case study for text categorization[C]//20th Ann Int ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’97),1997:67-73.

[2] Lewis D D,Ringuette M.Comparison of two learning algorithms for text categorization[C]//Proceedings of the Third Annual Symposium on Document Analysis and Information Retrieval (SDAIR’94),1994:81-93.

[3] Masand B,Lino G,Waltz D.Classifying news stories using memory based reasoning[C]//15th Ann Int ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’92),1992:59-64.

[4] Vapnic V.The Nature of Statistical Learning Theory.Springer[M].New York,1995.

[5] Yang Y,Liu X.A re-examination of text categorization methods[C]//Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval.ACM,1999:42-49.

[6] 王強,王曉龍,關毅,等.K-NN與SVM相融合的文本分類技術研究[J].高技術通訊,2005,5(15):19-24.

[7] 匡春臨,夏清強.基于SVM-KNN的文本分類算法及其分析[J].計算機時代,2010(8):29-31.

[8] Koller D,Sahami M.Hierarchically classifying documents using very few words[C]//Proceedings of the 14th ICML,1997:170-178.

[9] 張玉芳,萬斌候,熊忠陽.文本分類中的特征降維方法研究[J].計算機應用研究,2012,29(7):2541-2543.

[10] Lee Y J,Mangasarian O L.Rsvm: Reduced support vector machines[J].Data Mining Institate Computer Sciences Department University of Wisconsin,2001,2(11):00-07.

[11] Wen Chan,Weidong Yang,Jinhui Tang,et al.Community Question Topic Categorization via Hierarchical Kernelized Classification[C]//Proceedings of CIKM’13,2013:959-968.

[12] Lafferty J D,McCallum A,Pereira F C N.Conditional random fields:Probabilistic models for segmenting and labeling sequence data[C]//Proceedings of the 18th International Conference on Machine Learning,2001:282-289.

[13] ICTCLAS漢語分詞系統[J/OL].http://www.ictclas.org/ictclas_files.html.

中圖分類號TP302.1

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.02.009

收稿日期：2014-09-01。王金華，高工，主研領域：數據工程與信息系統。喻輝，工程師。產文，博士。周向東，教授。施伯樂，教授。