基于中心向量KNN算法的改進(jìn)

王兆龍

(安徽文達(dá)信息工程學(xué)院)

基于中心向量KNN算法的改進(jìn)

王兆龍

(安徽文達(dá)信息工程學(xué)院)

針對(duì)KNN算法在中文文本分類時(shí)計(jì)算開銷大的問題，在已有改進(jìn)算法的基礎(chǔ)上進(jìn)行了更深入的研究，提出改進(jìn)的基于中心向量KNN算法.算法首先引入基于密度的思想對(duì)訓(xùn)練樣本進(jìn)行調(diào)整，同時(shí)計(jì)算各類別的類中心向量.在保證類中心向量準(zhǔn)確性的前提條件下，使分類階段的復(fù)雜計(jì)算提前到分類器的訓(xùn)練過程中.實(shí)驗(yàn)結(jié)果表明，該算法在不損失精確度的情況下，提高了分類實(shí)時(shí)性.

文本分類;多級(jí)分類器;類中心向量

0 引言

隨著信息技術(shù)和社交媒體的快速發(fā)展，各類文本信息之間邊界模糊、類域交叉,判斷信息屬性的難度日益增加，因此人們渴望有效的工具對(duì)所擁有的文本信息快速準(zhǔn)確分類.文本分類作為一種處理海量信息的關(guān)鍵技術(shù)，是在既定的訓(xùn)練模型下，根據(jù)內(nèi)容自動(dòng)地將新得到的、未知類別屬性的目標(biāo)文本劃歸到所屬的一個(gè)或多個(gè)類別中[1]，由此提取的知識(shí)在提高企業(yè)合作興趣和突顯商業(yè)優(yōu)勢(shì)方面有重要的意義.

目前國(guó)內(nèi)外關(guān)于文本分類算法的研究已取得一定成果，國(guó)內(nèi)學(xué)者也相繼提出了許多實(shí)用的文本分類改進(jìn)算法，并通過實(shí)驗(yàn)驗(yàn)證了其有效性.文獻(xiàn)[2]通過增加逼近向量的個(gè)數(shù)建立了基于SVM的級(jí)聯(lián)結(jié)構(gòu)分類器進(jìn)行人臉的檢測(cè)；文獻(xiàn)[3]為了提高處理大規(guī)模數(shù)據(jù)的速度，提出了聚簇消減大規(guī)模數(shù)據(jù)的支持向量分類算法；文獻(xiàn)[4]利用Z-order曲線和多重Hilbert曲線，將d維點(diǎn)集映射到一維空間，然后沿著曲線進(jìn)行一定范圍內(nèi)的比較查詢來找到最近鄰的K個(gè)鄰居；文獻(xiàn)[5]針對(duì)KNN算法在處理大數(shù)據(jù)時(shí)的不足提出了多層差分分類算法.該文在學(xué)習(xí)相關(guān)算法的基礎(chǔ)上，提出改進(jìn)的基于中心向量KNN算法[6]，并通過仿真實(shí)驗(yàn)證明該文提出的算法.

1 KNN算法和基于密度的訓(xùn)練集調(diào)整方法

1.1 KNN算法原理

KNN分類算法是一種思想簡(jiǎn)單、容易操作且應(yīng)用比較成熟的方法.其基本過程描述如下：將訓(xùn)練樣本映射于向量空間中的點(diǎn)，在給定訓(xùn)練樣本集D和遇到待分類文本x的情況下，通過相似度計(jì)算并排序，從訓(xùn)練集D中找到與x距離最近的K個(gè)文本，最后根據(jù)這K個(gè)文本所屬的類別來判定x的類別歸屬.

雖然KNN分類算法是經(jīng)典的文本分類算法，具有諸多優(yōu)點(diǎn)，但是KNN算法也存在不足之處：①若訓(xùn)練樣本分布不均勻，包括樣本數(shù)目不等或樣本影響范圍不同，都會(huì)造成分類準(zhǔn)確率的下降[7].在實(shí)際應(yīng)用中，大類別樣本在密度上的優(yōu)勢(shì)容易影響分類的準(zhǔn)確率[8].②因?yàn)镵NN算法具有很強(qiáng)的“懶惰性”特征[9]，如果遇到訓(xùn)練樣本規(guī)模較大的情況，那么在分類階段就會(huì)造成很高的計(jì)算開銷和系統(tǒng)負(fù)荷，嚴(yán)重影響分類器的整體性能.

1.2基于密度的KNN訓(xùn)練集調(diào)整方法

在經(jīng)過了類內(nèi)樣本密度的相關(guān)計(jì)算后，根據(jù)樣本的分布密度及數(shù)目，對(duì)訓(xùn)練樣本進(jìn)行調(diào)整時(shí)，分別對(duì)處于類邊界區(qū)域和類內(nèi)區(qū)域的樣本進(jìn)行處理.由于裁減訓(xùn)練集規(guī)模是以減少分類計(jì)算復(fù)雜度為主要目標(biāo)，因此對(duì)樣本調(diào)整時(shí)主要對(duì)高密度區(qū)域的樣本進(jìn)行裁減.具體方法如下：

①類邊界區(qū)域：對(duì)任意一個(gè)處于類邊界區(qū)域的樣本X，通過計(jì)算分析判斷X所處的密度區(qū)域，如果X處于高密度區(qū)域，就裁減掉從樣本X是高密度可達(dá)的樣本，使其降為均勻密度區(qū)域；若是處于均勻密度或低密度區(qū)域則保留不變.

②類內(nèi)區(qū)域：對(duì)任意一個(gè)處于類內(nèi)區(qū)域的樣本X，若樣本密度高于類內(nèi)期望密度，需裁減掉從樣本X是高密度可達(dá)的樣本，直到|Nε(x)|=LowPts；否則，樣本X所處區(qū)域已符合標(biāo)準(zhǔn)，故不作處理.

類邊界區(qū)域的劃分是分類中的關(guān)鍵性問題，在此討論該區(qū)域的劃分方法：

(1)該文用整個(gè)訓(xùn)練集的平均密度來確定給定的平均樣本數(shù)AvgPts，即對(duì)于樣本集D和給定的領(lǐng)域半徑ε，即:

(1)

(2)設(shè)DK(X)表示樣本X的第K個(gè)近鄰到X的距離，把D在平均樣本數(shù)為AvgPts下的平均領(lǐng)域半徑定義為ε，即：

(2)

一般情況下取AvgPts的值為6%～8%的AvgPtsε(0)時(shí)效果較好，由于樣本向量的產(chǎn)生過程不同，因此ε值的差異較大.結(jié)合訓(xùn)練集的規(guī)模和特點(diǎn)，最終確定合適大小的類邊界區(qū)域和類內(nèi)區(qū)域.但是如果處于類內(nèi)區(qū)域且處于高密度區(qū)域的樣本太少，這樣也會(huì)丟失待分類文本類別判定的部分信息，因此，在對(duì)類內(nèi)區(qū)域樣本裁減時(shí)，使用了一個(gè)小于AvgPts的樣本數(shù)LowPts來作為類內(nèi)區(qū)域的樣本期望密度，從而使裁減后的類內(nèi)區(qū)域密度低于類邊界區(qū)域密度，最終在不影響分類精度的情況下，減少了分類的計(jì)算量.

2 改進(jìn)中心向量KNN算法

類中心向量法[10-11]基本思想描述：在訓(xùn)練分類器時(shí)，首先計(jì)算訓(xùn)練集中所有類別的中心向量.在測(cè)試文本分類時(shí)，直接計(jì)算待分類文本向量與每個(gè)類中心向量的相似度，然后將其歸入與之相似度最大的那個(gè)類中.計(jì)算公式為：

(3)

其中，Nk表示第k類中文本的數(shù)目，wij為特征詞tj在文本dj中的TFIDF權(quán)重[12-13].

在此，對(duì)類中心向量法進(jìn)行更深入的計(jì)算研究，把類別判定向前推進(jìn)一步，在得到待分類文本向量與每個(gè)類中心向量的相似度值后，對(duì)其按從大到小進(jìn)行排序，選取前m(參數(shù)m由實(shí)驗(yàn)確定)個(gè)類別中的樣本組成新的小規(guī)模訓(xùn)練樣本集，然后使用K近鄰算法對(duì)待分類文本進(jìn)行二次類別判定，以確保最終分類結(jié)果的準(zhǔn)確性.算法具體步驟為：

(1)計(jì)算訓(xùn)練集中各類的中心向量,保存計(jì)算結(jié)果并建立初級(jí)分類器.如圖1所示中的訓(xùn)練集共有5個(gè)類，且把各類的中心向量分別記為C1、C2、C3、C4、C5.

圖1 類中心向量

(2)計(jì)算待分類文本X與步驟(1)所得結(jié)果的各個(gè)類中心向量的相似度，并將這些值按從大到小進(jìn)行排序.然后進(jìn)一步選擇前m(1

圖2 取類C1和類C2中的文本作為新訓(xùn)練集

(3)在上述所得的結(jié)果集上，使用傳統(tǒng)KNN算法對(duì)待分類文本X進(jìn)行最終類別的判定.假設(shè)K=4，則X屬于類C1，如圖3所示.

圖3 在新訓(xùn)練集上使用KNN算法

上述算法是以單個(gè)待分類文本為例對(duì)算法思想進(jìn)行描述，在實(shí)際進(jìn)行中文文本分類時(shí)，待分類文本數(shù)量很多，其算法思想與上文描述一致，不過具體的分類計(jì)算過程會(huì)復(fù)雜很多.

3 實(shí)驗(yàn)結(jié)果與分析

采用2013年李教授發(fā)布的中文語料庫(kù)[14]作為實(shí)驗(yàn)數(shù)據(jù).共20個(gè)類別，answer.rar為測(cè)試語料，9833篇文本；train.rar為訓(xùn)練語料，9804篇文本.采用中科院研發(fā)的漢語分詞系統(tǒng)ICTCLAS 3.0對(duì)實(shí)驗(yàn)文本數(shù)據(jù)進(jìn)行處理，還用到Weka工具的部分功能.具體仿真實(shí)驗(yàn)結(jié)果及分析如下.

3.1訓(xùn)練集調(diào)整前后裁減比例及分類性能

(1)訓(xùn)練集調(diào)整

為了驗(yàn)證不同分布密度的類別樣本的調(diào)整效果，該文選取了兩個(gè)分別取自train.rar和answer.rar的訓(xùn)練集A和B，共9個(gè)類別2160篇文本.為了能夠很好的驗(yàn)證訓(xùn)練集的調(diào)整效果并形成明顯的對(duì)比，此處采用控制變量的方法來選擇另一個(gè)訓(xùn)練集B，訓(xùn)練集B與A有相同的類別總數(shù)和文本總數(shù)，但是訓(xùn)練集B的每個(gè)類別都有240篇文本，因此訓(xùn)練集B的分布很均勻，而訓(xùn)練集A中樣本在各個(gè)類的分布差別較大.訓(xùn)練集A見表1.

表1 A訓(xùn)練集信息

使用上述的訓(xùn)練集調(diào)整算法進(jìn)行實(shí)驗(yàn).取AvgPts=10，分別取LowPts的值為 1～10，調(diào)整訓(xùn)練集實(shí)驗(yàn)以裁減訓(xùn)練集中的高密度區(qū)域從而降低分類計(jì)算復(fù)雜度為主.使得樣本分布不均勻的訓(xùn)練集A的裁減比例大于樣本分布均勻的訓(xùn)練集B，但是訓(xùn)練集B也有較低比例的裁減.

(2)訓(xùn)練集調(diào)整前后分類性能

為了評(píng)估整體的分類效果，該文仿真實(shí)驗(yàn)采用宏平均準(zhǔn)確率和召回率，對(duì)訓(xùn)練集調(diào)整前后的分類性能進(jìn)行了測(cè)試，隨機(jī)選取answer.rar測(cè)試語料中的1360篇文本，通過多次實(shí)驗(yàn)，K=23、LowPts=7、8時(shí)分類效果最好.實(shí)驗(yàn)數(shù)據(jù)見表2.

表2 訓(xùn)練集調(diào)整前后分類準(zhǔn)確率和召回率對(duì)比

實(shí)驗(yàn)數(shù)據(jù)表明，在使用調(diào)整后的訓(xùn)練集進(jìn)行分類時(shí)，確實(shí)降低了分類的計(jì)算復(fù)雜度而且沒有犧牲分類的準(zhǔn)確率，如果LowPts取合適的值，還能小幅度的提高分類的準(zhǔn)確率.這就保證了下一步計(jì)算類中心向量的準(zhǔn)確性，進(jìn)而能夠保證在初級(jí)分類后保留下來的訓(xùn)練集是基本準(zhǔn)確的，才能保證進(jìn)一步使用KNN分類算法的正確性，減少分類階段的時(shí)間開銷.

3.2算法實(shí)時(shí)性

為了討論在最好改進(jìn)效果條件下，改進(jìn)分類算法在時(shí)間開銷上的節(jié)省情況.在以下實(shí)驗(yàn)中，改進(jìn)的分類算法分別與傳統(tǒng)的KNN算法和文獻(xiàn)[5]中提出的差分多層KNN算法(DM-KNN)進(jìn)行了比較，為了保證比較的準(zhǔn)確性，選擇在相同的數(shù)據(jù)集上進(jìn)行分類并記錄其分類用的時(shí)間.其中取m=4，K=16，得到以下實(shí)驗(yàn)數(shù)據(jù),見表3.

表3 三種分類模型的分類時(shí)間比較

由表3中的數(shù)據(jù)可得，多級(jí)分類KNN算法比傳統(tǒng)KNN算法在時(shí)間開銷上節(jié)省了89635ms，即節(jié)省了52.86%.如果訓(xùn)練集中有n個(gè)樣本點(diǎn)，經(jīng)數(shù)據(jù)清洗后取s個(gè)特征項(xiàng)，假如有t個(gè)文本要被分類，則KNN算法的時(shí)間復(fù)雜度為O(nst).本實(shí)驗(yàn)中訓(xùn)練集的類別數(shù)N=9，當(dāng)m=4時(shí)，舍去的類別數(shù)為5N/9，平均裁減掉的文本總數(shù)為5N/9，時(shí)間復(fù)雜度降為O(4nst/9)，時(shí)間節(jié)省應(yīng)該為55.6%，而實(shí)際的實(shí)驗(yàn)結(jié)果為52.86%.深入分析誤差原因，算法在訓(xùn)練階段增加了訓(xùn)練集的調(diào)整和類中心向量的計(jì)算過程；這些過程所花費(fèi)的時(shí)間致使實(shí)際節(jié)省的時(shí)間低于理論值.另一方面，多級(jí)分類KNN算法比DM-KNN算法多用了220ms，相差不大，分析原因也如上所述，這也間接的體現(xiàn)了多級(jí)分類算法的先進(jìn)性和前沿性.

4 結(jié)束語

KNN分類算法的時(shí)間復(fù)雜度由訓(xùn)練集規(guī)模決定.該文由于建立了類中心向量初始分類器，因此隨著調(diào)整后的訓(xùn)練集規(guī)模的減小，時(shí)間復(fù)雜度也會(huì)隨之減小，分類速度就會(huì)得到提高.在計(jì)算訓(xùn)練集的類中心向量之前，引入了基于密度的思想對(duì)訓(xùn)練集進(jìn)行了有效的均勻性調(diào)整，保證了類中心向量的基本準(zhǔn)確性，進(jìn)而使KNN改進(jìn)算法能夠?qū)崿F(xiàn)二級(jí)分類的目標(biāo)，在不損失分類精度的同時(shí)，顯著提高了分類器的分類速度.因此，該文在保證KNN算法分類性能的基礎(chǔ)上，不僅使分類的計(jì)算復(fù)雜度有一定程度的縮減，說明了對(duì)KNN算法的改進(jìn)是有實(shí)際意義的.

[1] Fabrizio S.Machine learning in automated text categorization[J].ACM Computing Surveys,2002,34(1):1-47.

[2] Romdhani S,Torr P,Scholkopf B,et al.Efficient face detection by a cascaded support-vector machine expansion[J].Pattern Recognition,2004,3175:62-70.

[3] 陳光喜,徐建,成彥.一種聚簇消減大規(guī)模數(shù)據(jù)的支持向量分類算法[J].計(jì)算機(jī)科學(xué),2009,36( 3) :184-188.

[4] Hanan Samet.Depth-first k-nearest neighbor finding using the maxnearestdist estimator[C]//Proceedings of the 12th International Conference on Image Analysis and Proceeding,2003:486-491.

[5] 耿麗娟,李星毅.用于大數(shù)據(jù)分類的KNN算法研究[J].計(jì)算機(jī)應(yīng)用研究,2014,31(5):1342-1344.

[6] Chakrabarti S,Joshi M,Tawde V.Enhanced topic distillation using text markup tags and hyperlinks[C]//ACM SIGIR,2001.

[7] García V,Alejo R,Sánchez J S,et al.Combined effects of class imbalance and class overlap on instance-based classification [A] // Intelligent Data Engineering and Automated Learning-IDEAL 2006 [M].Berlin,Heidelberg:Springer,2006:371-378.

[8] Xia Zhan-guo,Xia Shi-xiong,Cai Shi-yu,et al.Semi-Supervised gaussian process classification algorithm addressing the class imbalance [J].Journal on Communications,2013,34(5):42-51.

[9] 曹勇.中文Web文本分類技術(shù)研究[D].廈門:廈門大學(xué),2007.

[10] 郭茂.基于類中心向量的文本分類模型研究與實(shí)現(xiàn)[D].大連：大連理工大學(xué),2010.

[11] Ling Jie,Zou Li-na.An improved KNN algorithm for text classification based on clustering center vector[C].IEEE International conference on Cyber Technology in Automation,Control,and Intelligent Systems(CYBER),2012.

[12] 李媛媛,馬永強(qiáng).基于潛在語義索引的文本特征詞權(quán)重計(jì)算方法[J].計(jì)算機(jī)應(yīng)用,2008,28(6):1461-1466.

[13] Zhu Shan-zong,Liu Yuan-chao,Liu Ming.Research on feature extraction from chinese text for opinion mining[C].International Conference on Asian Languages Processing,2009.

[14] Li Rong-lu.Computer information and technology department of fudan university center for international database natural language processing group.[EB/OL].[2013-5-23],[2015-6-10].(in Chinese)

Abstract:In order to solve the problem of high computational cost in Chinese text classification,a deep research on the improved algorithm based on KNN algorithm is made,and an improved algorithm is proposed based on KNN algorithm.Firstly,the density of the training samples is adjusted,and the class center vectors are calculated.Under the premise of ensuring the accuracy of the center vector,the complex computation in the classification stage is advanced to the training process of the classifier.The experimental results show that the proposed algorithm improves the classification performance without losing the accuracy.

Keywords:Text classification; Multi-stage classifier; Class center vector

(責(zé)任編輯：李家云)

TheImprovementofKNNAlgorithmBasedonCenterVector

Wang Zhaolong

(Anhui Wenda Information Engineering College)

TP391

A

1000-5617(2017)02-0018-04

2017-01-01