尹紹鋒，鄭蕙，徐少華，榮輝桂，張娜

?

一種基于特征庫投影的文本分類算法

尹紹鋒1，鄭蕙2，徐少華1，榮輝桂3，張娜3

(1. 湖南大學(xué)校園信息化建設(shè)與管理辦公室，湖南長沙，410082；2. 湖南商學(xué)院旅游管理學(xué)院，湖南長沙，410205；3. 湖南大學(xué)信息工程與科學(xué)學(xué)院，湖南長沙，410082)

基于KNN的主流文本分類策略適合樣本容量較大的自動分類，但存在時(shí)間復(fù)雜度偏高、特征降維和樣本剪裁易出現(xiàn)信息丟失等問題，本文提出一種基于特征庫投影(FLP)的分類算法。該算法首先將所有訓(xùn)練樣本的特征按照一定的權(quán)重策略構(gòu)筑特征庫，通過特征庫保留所有樣本特征信息；然后，通過投影函數(shù)，根據(jù)待分類樣本的特征集合將每個(gè)分類的特征庫映射為投影樣本，通過計(jì)算新樣本與各分類投影樣本的相似度來完成分類。采用復(fù)旦大學(xué)國際數(shù)據(jù)庫中心自然語言處理小組整理的語料庫對所提出的分類算法進(jìn)行驗(yàn)證，分小量訓(xùn)練文本和大量訓(xùn)練文本2個(gè)場景進(jìn)行測試，并與基于聚類的KNN算法進(jìn)行對比。實(shí)驗(yàn)結(jié)果表明：FLP分類算法不會丟失分類特征，分類精確度較高；分類效率與樣本規(guī)模的增長不直接關(guān)聯(lián)，時(shí)間復(fù)雜度低。

文本分類；KNN算法；特征庫投影

隨著文本信息處理技術(shù)的快速發(fā)展，文本分類算法日益成熟，成為當(dāng)前數(shù)據(jù)挖掘預(yù)處理過程中的重要方法。目前關(guān)于文本分類算法的研究很多, 主要可 分為3類：1) 基于統(tǒng)計(jì)的方法, 如樸素貝葉斯[1]、KNN[2]、支持向量機(jī)[3]、最大熵等方法；2) 基于規(guī)則的方法，如決策樹(DT)[4]；3) 基于連接的方法，如神經(jīng)網(wǎng)絡(luò)等[5]。其中，KNN算法是由COVER和HART于1976年提出[2]，YANG等[6]以準(zhǔn)確率、召回率、F-Score等作為評測指標(biāo)，通過假設(shè)檢驗(yàn)方法驗(yàn)證KNN和SVM在綜合性能上高于其他的文本分類方法。同時(shí)，KNN同時(shí)能解決文本分布出現(xiàn)多峰值的情況，因此，KNN分類性能較穩(wěn)定[6]。KNN作為一種惰性學(xué)習(xí)方法，只有在分類時(shí)才臨時(shí)建立分類器，需要與所有訓(xùn)練樣本逐個(gè)計(jì)算相似度，計(jì)算量非常大。而且因?yàn)橛?xùn)練樣本密度不均勻也會直接影響分類效果。針對這些問題，近年來出現(xiàn)了不少改進(jìn)算法，如VSM優(yōu)化進(jìn)行特征降維。這類優(yōu)化基于2個(gè)途徑進(jìn)行，包括特征選擇與特征抽取。特征選擇基于特征選擇函數(shù)，比較常見的有互信息(MI)[7]、文檔頻率(DF)、信息增益(IG)[8]等。鐘將等[9]使用潛在語義分析方法對文本特征空間進(jìn)行降維處理。此外，對訓(xùn)練樣本進(jìn)行優(yōu)化剪裁。導(dǎo)致KNN算法分類效率較低的主要原因是其具有惰性學(xué)習(xí)的特點(diǎn)，訓(xùn)練樣本數(shù)量越大，時(shí)間消耗越大。壓縮近鄰法[10]對樣本中心部位樣本進(jìn)行剪裁，僅保留邊界來進(jìn)行分類決策。WILSON等[11?12]則通過邊界剪裁訓(xùn)練集，在減少訓(xùn)練樣本數(shù)量的同時(shí)使邊界清晰。張永等[13]通過投影的方法縮減訓(xùn)練集的規(guī)模，同時(shí)在尋找近鄰過程中對文本進(jìn)行降維處理，從兩方面降低算法的計(jì)算時(shí)間。KNN的另外一種優(yōu)化是訓(xùn)練樣本聚合，使用更具代表性的樣本來縮小樣本空間。張孝飛等[14]通過簇代表進(jìn)行分類。吳春穎等[15]則結(jié)合相關(guān)反饋思想進(jìn)行排類，在不降低分類精度的基礎(chǔ)上提高分類速度。為改善搜索算法，提升樣本計(jì)算過程效率，王淵等[16]通過粗糙集算法將樣本空間分為核心與混合2個(gè)區(qū)域，采用差異化分類策略提高分類效率和精度。郭躬德等[17]提出基于KNN 模型的增量學(xué)習(xí)算法，而黃杰等[18]則進(jìn)一步為KNN模型增量學(xué)習(xí)算法提出了模型簇修剪算法。錢強(qiáng)等[19]采用逐步逼近的方法，通過建立所有訓(xùn)練樣本之間的距離排序，從而在分類過程中參考已有的距離信息，減少搜索空間。ZHANG等[20]提出超球體的思想也有效地提升了算法效率。然后，代六玲等[21?22]指出KNN的分類準(zhǔn)確率與樣本規(guī)模呈正相關(guān)性，因此，在保證KNN分類準(zhǔn)確率的前提下，不能單純通過剪裁樣本這種損失信息的方法進(jìn)行改進(jìn)。為此，本文作者采用聚類的思路，將大量的訓(xùn)練樣本通過聚合構(gòu)建出分類特征庫，在分類過程中針對待分類的樣本通過投影函數(shù)從分類特征庫提取特征項(xiàng)構(gòu)造投影樣本，在不損失樣本信息的前提下，大幅度降低計(jì)算復(fù)雜度，提高分類效率。

1 基于特征庫投影算法

萬韓永等[23]認(rèn)為不同的樣本對分類的貢獻(xiàn)是不同的。本文進(jìn)一步認(rèn)為不同的特征項(xiàng)對分類的貢獻(xiàn)不同。單個(gè)的文本的特征總會具有局限性，而且難免出現(xiàn)人為的標(biāo)注錯(cuò)誤，這些都會干擾分類效果。針對這種問題，本文認(rèn)為可以將不同類別訓(xùn)練文本聚合成一個(gè)特征庫，在聚合過程中，對分類具有較大共享的特征被增強(qiáng)，而干擾項(xiàng)被削弱。

1—d1；2—d2；3—d3；4—d4；5—C。

本文為每個(gè)分類構(gòu)造1個(gè)特征庫(FL, feature library)。對文本進(jìn)行分類時(shí)，從各FL提取與文本一致的特征項(xiàng)，構(gòu)成1個(gè)分類投影文本，設(shè)與的相似度為：

基于特征庫的分類函數(shù)為

分類函數(shù)()是一個(gè)關(guān)于文本間相似度的函數(shù)，為待分類的文本與各分類的投影文本之間的相似度集合。當(dāng)與之間的相似度最大時(shí)，取值為1，否則為0。

1.1 特征庫投影分類算法實(shí)現(xiàn)流程

基于特征庫的文本分類算法實(shí)現(xiàn)流程包括4個(gè)主要步驟：1) 根據(jù)訓(xùn)練文本集構(gòu)建分類特征庫；2) 建立待分類文本的向量空間模型()，根據(jù)()為各建立每個(gè)分類針對()的投影文件；3) 計(jì)算()與各分類投影文件向量的相似度；4) 根據(jù)相似度確定分類結(jié)果。特征庫投影分類過程見圖1。

圖2 特征庫投影分類過程

1.2 特征庫

特征庫是屬于同一個(gè)分類的一組特征項(xiàng)的集合，記為，1個(gè)特征項(xiàng)包含1個(gè)特征詞以及該特征詞出現(xiàn)的次數(shù)?？杀硎救缦拢?/p>

其中：t為集合中第個(gè)有效的特征詞；c為第個(gè)有效特征詞在特征庫中的權(quán)重。中特征詞為該分類中各文本特征詞集合的并集：

其中：()為中特征詞集合；為特征詞個(gè)數(shù)；(d)為該分類中已知的第個(gè)文本的特征詞集合；為該分類訓(xùn)練文本的數(shù)量。

c為特征詞在各文檔中出現(xiàn)詞頻的和，可表示為

1.3 分類投影文件

分類投影(projection)是針對1個(gè)待分類文本特征項(xiàng)的權(quán)重映射所形成的1個(gè)特征項(xiàng)集合。假設(shè)待分類的文本為，投影文件為，為從關(guān)于的投影轉(zhuǎn)換函數(shù)，則表示為

(3)

1.4 特征詞權(quán)重計(jì)算

1.4.1 待分類文件特征詞權(quán)重計(jì)算

待分類文件中特征詞的權(quán)重為特征詞的詞頻。對于待分類文本，通過向量空間模型表示為

其中：()為文本的向量；t為一組不重復(fù)的特征詞；w()為特征詞t的權(quán)重，這里為t的詞頻，即

(4)

1.4.2 投影文件特征詞權(quán)重計(jì)算

投影文件中特征詞的權(quán)重使用詞頻-?集中率算法(term frequency-?concentration ratio, TF-?CR)計(jì)算。針對1個(gè)待分類的文件，可以通過投影函數(shù)獲取一組投影文件：

(6)

為投影文件的數(shù)量；m為包含特征詞t的投影文件的數(shù)量。因?yàn)橥队拔谋九c分類一一對應(yīng)，因此，m也可以是包含特征詞t的分類數(shù)量。當(dāng)m越小，且時(shí)，越向靠近。

2 實(shí)驗(yàn)過程及結(jié)果分析

2.1 測試文本集和實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)語料庫采用復(fù)旦大學(xué)國際數(shù)據(jù)庫中心自然語言處理小組整理的訓(xùn)練文本集以及測試文本集，共有17個(gè)分類，其中訓(xùn)練文本7 981個(gè)，測試文本7 958個(gè)。語料集又進(jìn)一步分為小樣本和大樣本訓(xùn)練語料集。其中，小樣本語料庫選擇訓(xùn)練樣本數(shù)量小于100的分類，共計(jì)11個(gè)分類，如表1所示。

大樣本語料庫選擇訓(xùn)練樣本數(shù)量大于1 000的分類，共計(jì)6個(gè)分類，如表2所示。

實(shí)驗(yàn)環(huán)境采用如下設(shè)置：開發(fā)語言采用java1.6，Eclipse集成開發(fā)環(huán)境；操作系統(tǒng)為win10 professional 64bit；硬件為1.93 GHz，AMD A8-4500M CPU, 4 GB RAM。

表1 小樣本語料庫

表2 大樣本語料庫

2.2 實(shí)驗(yàn)步驟及結(jié)果

本次實(shí)驗(yàn)主要通過對比FLP算法與基于聚類的KNN算法的分類效果來驗(yàn)證FLP的有效性。采用KNN算法時(shí)，經(jīng)測定取值為9。

對抽取的測試文檔進(jìn)行分詞、去停用詞處理，建立測試文檔的向量空間模型，并使用式(4)確定每個(gè)測試文本中每個(gè)特征的權(quán)重。

根據(jù)測試文本的空間向量，通過式(3)為每個(gè)分類建立投影文件，然后根據(jù)式(1)計(jì)算測試文本與投影文件之間的相似度，最后根據(jù)式(2)確定測試文本所屬的分類。為了較全面地驗(yàn)證算法的有效性，實(shí)驗(yàn)先抽取訓(xùn)練樣本數(shù)據(jù)量少于100個(gè)文本的分類，共11個(gè)，其中最少的樣本數(shù)量為27個(gè)，最多的為76個(gè)；然后抽取訓(xùn)練樣本數(shù)量大于1 000個(gè)文本的分類，共6個(gè)，其中最少樣本數(shù)量為1 022個(gè)，最多1 601個(gè)。通過不同規(guī)模的訓(xùn)練樣本環(huán)境驗(yàn)證算法的分類效果和分類效率。

2.2.1 小樣本測試結(jié)果

小樣本測試中，各分類的訓(xùn)練樣本數(shù)量最小為27個(gè)，最大為76個(gè)；在基于該樣本的分類測試中，分析得到FLP算法與KNN算法結(jié)果。

表3所示為FLP算法針對小樣本語料庫的分類結(jié)果。其中表3中的行表示樣本的實(shí)際所屬分類，列表示樣本被識別的分類。

表3中，當(dāng)行列的分類一致時(shí)，說明該樣本被正確識別，否則分類失敗。如C15分類共33個(gè)測試樣本，其中有26個(gè)被正確識別，記為；有7個(gè)分類失敗，記為；4個(gè)被分為C23類，C29類、C36和C37分別1個(gè)；同時(shí)，有5個(gè)其他分類的樣本被劃分為C15分類，記為，其中，C35類2個(gè)，C16，C36及C37分別1個(gè)。

通過召回率和精準(zhǔn)率來評價(jià)分類效果。

召回率表示屬于某個(gè)分類的所有樣本被正確識別的個(gè)數(shù)，精準(zhǔn)率表示所有被識別為某一分類的樣本中正確樣本的數(shù)量。經(jīng)計(jì)算，C15的召回率為 0.787 878 79，精準(zhǔn)率為0.838 709 677。

隨后，將KNN算法應(yīng)用于小樣本集中進(jìn)行測試，得到其分類結(jié)果如表4所示。

從表4可知：FLP與KNN都較好地完成了分類，從分類結(jié)果的整體看，F(xiàn)LP略優(yōu)于KNN，但FLP的計(jì)算復(fù)雜度比KNN的低，分類效率明顯提高。

2.2.2 大樣本測試結(jié)果

大樣本測試中，各分類的訓(xùn)練樣本數(shù)量均在1 000個(gè)以上，最大為1 600個(gè)。FLP算法與KNN實(shí)驗(yàn)結(jié)果分別如表5和表6所示。

表3 FLP分類測試結(jié)果(小樣本)

表4 KNN分類測試結(jié)果(小樣本)

表5 FLP分類測試結(jié)果(大樣本)

表6 KNN分類測試結(jié)果(大樣本)

從表5和表6可以看出：FLP與KNN都完成了分類，從整體分類結(jié)果看，F(xiàn)LP略優(yōu)于KNN。對比小樣本測試，F(xiàn)LP的計(jì)算時(shí)間基本與待檢測樣本的數(shù)量呈線性增長，但KNN的計(jì)算時(shí)間與訓(xùn)練樣本數(shù)和待分類樣本數(shù)均有相關(guān)性，分類計(jì)算時(shí)間呈指數(shù)增大。

2.3 結(jié)果分析

2.3.1 分類效果對比分析

對上述實(shí)驗(yàn)結(jié)果，分別從召回率、精準(zhǔn)率以及-測量值這3個(gè)維度進(jìn)行對比評估。在分類過程中，增加召回率，則可能導(dǎo)致精準(zhǔn)率降低，反之亦然。因此，用綜合評估分類效果：

針對，和這3個(gè)指標(biāo)，F(xiàn)LP算法與KNN算法的分類結(jié)果見表7。

從表7可以看出：FLP算法平均值為0.810 000 0，平均值為0.840 000 0，平均值為0.820 000 0，均高于KNN相對應(yīng)評估指標(biāo)，尤其時(shí)間消耗明顯減少。其對應(yīng)指標(biāo)的分類結(jié)果如圖3所示。

表7 FLP和KNN小樣本分類結(jié)果對比

圖3 FLP和KNN分類指標(biāo)項(xiàng)對比(小樣本)

從圖3可以看出：FLP算法在小樣本訓(xùn)練的結(jié)果中，整體效果優(yōu)于KNN。

表8所示為FLP算法與KNN算法所得召回率、準(zhǔn)確率以及的對比。從表8可以看出：FLP算法各項(xiàng)評估指標(biāo)在0.840 000 0左右，比小樣本測試略有提升，KNN所得結(jié)果與小樣本測試結(jié)果相比也有明顯提升，說明樣本數(shù)量的增加對分類效果有利。而FLP算法時(shí)間消耗遠(yuǎn)比KNN算法的少。

表8 FLP和KNN大樣本分類結(jié)果對比

從圖4可以直觀看出FLP算法在大樣本訓(xùn)練的結(jié)果中，其分類效果依然優(yōu)于KNN。

同時(shí)對比FLP在2個(gè)不同分類場景的結(jié)果，當(dāng)訓(xùn)練樣本增加時(shí)，F(xiàn)LP的分類召回率、準(zhǔn)確率均有提高，說明訓(xùn)練樣本的數(shù)量對分類結(jié)果有直接影響。

2.3.2 分類效率對比分析

FLP算法相對于KNN算法最大的優(yōu)勢是時(shí)間復(fù)雜度的降低。FLP的時(shí)間復(fù)雜度是關(guān)于分類數(shù)量的函數(shù)，而KNN是關(guān)于訓(xùn)練樣本數(shù)量的函數(shù)，在正常情況下，F(xiàn)LP分類效率比KNN的高。表9所示為500個(gè)測試樣本在不同訓(xùn)練樣本規(guī)模時(shí)2種算法的耗時(shí)。

圖4 FLP和KNN分類指標(biāo)項(xiàng)對比(大樣本)

表9 FLP與KNN分類效率對比

由表9可以看出：FLP比KNN算法在分類效率上有明顯提升；隨著訓(xùn)練樣本增加，KNN用時(shí)呈線性增加，而FLP用時(shí)增加緩慢。

FLP算法在訓(xùn)練樣本超過一定范圍后，分類用時(shí)增加率減緩。出現(xiàn)這種現(xiàn)象的原因可能是特征庫文件的規(guī)模不再隨訓(xùn)練樣本的增加而增加，因此，構(gòu)建投影文件的耗時(shí)趨于穩(wěn)定，如圖5所示。

1—FLP分類耗時(shí)；2—KNN分類耗時(shí)。

3 結(jié)論

1) FLP算法在優(yōu)化過程中，一方面沒有丟失特征，同時(shí)在聚合過程中有效抑制了噪聲，而且KNN的分類效率也提高5%左右，提出的算法較KNN算法的分類精度高。

2) FLP算法分類耗時(shí)與訓(xùn)練樣本規(guī)模的增長沒有直接關(guān)聯(lián)，增加訓(xùn)練樣本數(shù)、提升分類精度對分類效率影響較?。欢鳮NN算法則受樣本規(guī)模約束較大，隨樣本規(guī)模增大，分類耗時(shí)迅速增大。可見FLP算法相比KNN算法的另一個(gè)優(yōu)勢是分類效率大幅度提高。

對于特征庫的構(gòu)建、投影實(shí)例的生成以及投影實(shí)例與待分類樣本之間相似度的計(jì)算還有待進(jìn)一步 優(yōu)化。

[1] LEWIS D D. Naive (Bayes) at forty: the independence assumption in information retrieval[C]// European Conference on Machine Leaning. Heidelberg, Berlin: Springer, 1998: 4?15.

[2] COVER T M, HART P E. Nearest neighbor pattern classification[J]. IEEE Transactions on Information Theory, 1967, 13(1): 21?27.

[3] CHANG C C, LIN C J. LIBSVM: a library for support vector machines[J]. ACM Transactions on Intelligent Systems and Technology, 2011, 2(3): 1?27.

[4] TSANG S, KAO B, YIP K Y, et al. Decision trees for uncertain data[J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(1): 64?78.

[5] GHIASSI M, OLSCHIMKE M, MOON B, et al. Automated text classification using a dynamic artificial neural network model[J]. Expert Systems with Applications, 2012, 39(12): 10967?10976.

[6] YANG Yiming, LIU Xia. A re-examination of text categorization methods[C]// Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York, USA: ACM, 1999: 42?49.

[7] 范雪莉, 馮海泓, 原猛. 基于互信息的主成分分析特征選擇算法[J]. 控制與決策, 2013, 28(6): 915?919. FAN Xueli, FENG Haihong, YUAN Meng. PCA based on mutual information for feature selection[J]. Control and Decision, 2013, 28(6): 915?919.

[8] 石慧, 賈代平, 苗培. 基于詞頻信息的改進(jìn)信息增益文本特征選擇算法[J]. 計(jì)算機(jī)應(yīng)用, 2014, 34(11): 3279?3282. SHI Hui, JIA Daiping, MIAO Pei. Improved information gain text feature selection algorithm based on word frequency information[J]. Journal of Computer Applications, 2014, 34(11): 3279?3282.

[9] 鐘將, 劉榮輝. 一種改進(jìn)的KNN文本分類[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48(2): 142?144. ZHONG Jiang, LIU Ronghui. Improved KNN text categorization[J]. Computer Engineering and Applications, 2012, 48(2): 142?144.

[10] ANGIULLI F. Fast condensed nearest neighbor rule[C]// Proceedings of the 22nd International Conference on Machine Learning. New York: ACM, 2005: 25?32.

[11] WILSON D L. Asymptotic properties of nearest neighbor rules using edited data[J]. IEEE Transactions on Systems, Man and Cybernetics, 1972, 2(3): 408?421.

[12] DEVIJVER P A, KITTLER J. Pattern recognition:a statistical approach[M]. London: Prentice-Hall, 1982: 1?50.

[13] 張永, 孟曉飛. 基于投影尋蹤的KNN文本分類算法的加速策略[J]. 科學(xué)技術(shù)與工程, 2014, 36(14): 92?96. ZHANG Yong, MENG Xiaofei. Accelerated k-nearest neighbors text classification algorithm based on projection pursuit[J]. Science Technology and Engineering, 2014, 36(14): 92?96.

[14] 張孝飛, 黃河燕. 一種采用聚類技術(shù)改進(jìn)的 KNN 文本分類方法[J]. 模式識別與人工智能, 2009, 22(6): 936?940. ZHANG Xiaofei, HUANG Heyan. An improved KNN text categorization algorithm by adopting cluster technology[J]. Pattern Recognition and Artificial Intelligence, 2009, 22(6): 936?940.

[15] 吳春穎, 王士同. 一種改進(jìn)的KNN Web文本分類方法[J]. 計(jì)算機(jī)應(yīng)用研究, 2008, 25(11): 3275?3277. WU Chunyin, WANG Shitong. Improved KNN web text classification method[J]. Application Research of Computers, 2008, 25(11): 3275?3277.

[16] 王淵, 劉業(yè)政, 姜元春. 基于粗糙KNN算法的文本分類方法[J]. 合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版), 2014, 37(12): 1513?1517. WANG Yuan, LIU Yezheng, JIANG Yuanchun. Method of text classification based on rough k-nearest neighbor algorithm[J]. Journal of Hefei University of Technology (Natural Science), 2014, 37(12): 1513?1517.

[17] 郭躬德, 黃杰, 陳黎飛. 基于KNN 模型的增量學(xué)習(xí)算法[J].模式識別與人工智能, 2010, 23(5): 701?707. GUO Gongde, HUANG Jie, CHEN Lifei. KNN model based incremental learning algorithm[J]. Pattern Recognition and Artificial Intelligence, 2010, 23(5): 701?707.

[18] 黃杰, 郭躬德, 陳黎飛. 增量KNN模型的修剪策略研究[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2011, 32(5): 845?849. HUANG Jie, GUO Gongde, CHEN Lifei. Research on pruning strategy of incremental KNN model[J]. Journal of Chinese Computer Systems, 2011, 32(5): 845?849.

[19] 錢強(qiáng), 龐林斌, 高尚. 一種基于改進(jìn)型KNN算法的文本分類方法[J]. 江蘇科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2013, 27(4): 381?385. QIAN Qiang, PANG Linbin, GAO Shang. A text classification method based on improved KNN algorithm[J]. Journal of Jiangsu University of Science and Technology, 2013, 27(4): 381?385.

[20] ZHANG Bin, SRIHARI S N. Fast k-nearest neighbor classification using cluster-based trees[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(4): 525?528.

[21] 代六玲, 黃河燕, 陳肇雄. 中文文本分類中特征抽取方法的比較研究[J]. 中文信息學(xué)報(bào), 2004, 18(1): 27?33. DAI Liuling, HUANG Heyan, CHEN Zhaoxiong. A comparative study on feature selection in Chinese text categorization[J]. Journal of Chinese Information Processing, 2004, 18(1): 26?32.

[22] RONG Huigui, ZHOU Xun, YANG Chang, et al. The rich and the poor: a Markov decision process approach to optimizing taxi driver revenue efficiency[C]// Proceedings of the 25th ACM International Conference on Information and Knowledge Management. Indianapolis , USA, 2016: 2329?2334.

[23] 萬韓永, 左家莉, 萬劍怡, 等. 基于樣本重要性原理的KNN文本分類算法[J]. 江西師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015, 39(3): 297?303. WAN Hanyong, ZUO Jiali, WAN Jianyi, et al. The KNN text classification based on sample importance principals[J]. Journal of Jiangxi Normal University (Natural Sciences Edition), 2015, 39(3): 297?303.

(編輯 陳燦華)

A text classification algorithm based on feature library projection

YIN Shaofeng1, ZHENG Hui2, XU Shaohua1, RONG Huigui3, ZHANG Na3

(1. Department of Campus Informatization and Management, Hunan University, Changsha 410082, China;2. School of Tourism Management, Hunan University of Commerce, Changsha 410205, China;3. School of Information Science and Engineering, Hunan University, Changsha 410082, China)

Considering that KNN algorithm has some disadvantages such as high time complexity, feature reduction, sample clipping and information loss, a feature library projection (FLP) classification algorithm was proposed. Firstly, the algorithm reserved all the features and characteristics of the training sample weight in the feature library. The data in this library were changed into new projection samples through the projection functions. By calculating the similarity of the new sample with the projection samples, data classification could be achieved. Based on the text classification, the effectiveness of the algorithm and texts, the data were validated under two conditions, i.e. small training texts and large training texts, and it was compared with KNN algorithm. The results show that the FLP algorithm does not lose the classification feature, and the classification accuracy is higher than that of other ones. The classification efficiency is not directly related to the sample size growth, and the time complexity is low.

text classification; KNN algorithm; feature library projection

10.11817/j.issn.1672-7207.2017.07.014

TP391

A

1672?7207(2017)07?1782?08

2016?09?20；

2016?11?12

國家自然科學(xué)基金資助項(xiàng)目(61672221，61304184，61672156) (Projects(61672221, 61304184, 61672156) supported by the National Natural Science Foundation of China)

鄭蕙，講師，從事旅游大數(shù)據(jù)挖掘與電子商務(wù)研究；E-mail: zhdilly@163.com