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

王金華　喻　輝　產(chǎn)　文　周向東　施伯樂

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

2(成都軍區(qū)通信網(wǎng)絡(luò)技術(shù)管理中心　四川 成都 610000)

3(復(fù)旦大學(xué)計算機學(xué)院　上海 200433)

?

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

王金華1喻輝2產(chǎn)文3周向東3施伯樂3

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

2(成都軍區(qū)通信網(wǎng)絡(luò)技術(shù)管理中心四川 成都 610000)

3(復(fù)旦大學(xué)計算機學(xué)院上海 200433)

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

關(guān)鍵詞自動文本分類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技術(shù)和新媒體的發(fā)展帶來了文本大數(shù)據(jù)的快速增長，隨著人們在互聯(lián)網(wǎng)上便利地交流，各類電子化的文本文件、資料、檔案等已逐步取代了紙質(zhì)文檔。對文檔進行語義上的分類管理是傳統(tǒng)的文檔管理中普遍采用的有效方法，例如圖書館的書別目錄檢索。然而，面對海量的文本信息資源，傳統(tǒng)的人工分類在人力耗費、時間響應(yīng)等方面已經(jīng)無法滿足實際工作的需要， 因此亟待開發(fā)以自動文本分類技術(shù)為基礎(chǔ)的自動文本管理系統(tǒng)。

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

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

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

1KNN與SVM算法

1.1KNN分類算法

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

(1)

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

(2)

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

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

1.2層次SVM分類算法

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

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

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

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

(3)

subject to

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

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

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

2KNN+層次SVM分類框架

2.1訓(xùn)練層次SVM分類模型

為了訓(xùn)練層次SVM模型，我們將1.2節(jié)的目標函數(shù)改寫為：

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

(4)

其中：

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

(5)

2.2KNN+層次SVM算法流程

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

算法KNN+層次SVM分類算法

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

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

步驟：

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

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

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

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

2.3文本預(yù)處理和特征選擇

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

3實驗設(shè)置和實驗結(jié)果

為了使文檔自動分類系統(tǒng)具備良好的穩(wěn)定性、擴展性和可用性，更加具備分類的準確行，本系統(tǒng)主要依托成熟的數(shù)據(jù)庫系統(tǒng)來存儲、管理分類信息、文本數(shù)據(jù)及各類算法參數(shù)等。由于分類信息的圖結(jié)構(gòu)特點，本系統(tǒng)采用Neo4J圖數(shù)據(jù)庫對網(wǎng)絡(luò)數(shù)據(jù)進行存儲。同時對海量文本數(shù)據(jù)采用Oracle關(guān)系數(shù)據(jù)庫進行存儲。

3.1實驗數(shù)據(jù)集

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

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

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

? 文檔特征維度為1000。

3.2實驗結(jié)果與分析

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

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

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

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

表1　KNN與SVM結(jié)合分類效果

表2　KNN與SVM相結(jié)合后所需時間

通過表1，我們觀察到：

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

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

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

4結(jié)語

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

參考文獻

[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] 王強,王曉龍,關(guān)毅,等.K-NN與SVM相融合的文本分類技術(shù)研究[J].高技術(shù)通訊,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].計算機應(yīng)用研究,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漢語分詞系統(tǒng)[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。王金華，高工，主研領(lǐng)域：數(shù)據(jù)工程與信息系統(tǒng)。喻輝，工程師。產(chǎn)文，博士。周向東，教授。施伯樂，教授。