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

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

?

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

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

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

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

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

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

1 基于特征庫投影算法

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

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

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

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

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

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

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

圖2 特征庫投影分類過程

1.2 特征庫

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

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

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

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

1.3 分類投影文件

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

(3)

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

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

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

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

(4)

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

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

(6)

為投影文件的數(shù)量；m為包含特征詞t的投影文件的數(shù)量。因為投影文本與分類一一對應，因此，m也可以是包含特征詞t的分類數(shù)量。當m越小，且時，越向靠近。

2 實驗過程及結(jié)果分析

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

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

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

實驗環(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 實驗步驟及結(jié)果

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

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

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

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

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

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

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

通過召回率和精準率來評價分類效果。

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

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

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

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

大樣本測試中，各分類的訓練樣本數(shù)量均在1 000個以上，最大為1 600個。FLP算法與KNN實驗結(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的計算時間基本與待檢測樣本的數(shù)量呈線性增長，但KNN的計算時間與訓練樣本數(shù)和待分類樣本數(shù)均有相關(guān)性，分類計算時間呈指數(shù)增大。

2.3 結(jié)果分析

2.3.1 分類效果對比分析

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

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

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

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

圖3 FLP和KNN分類指標項對比(小樣本)

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

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

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

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

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

2.3.2 分類效率對比分析

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

圖4 FLP和KNN分類指標項對比(大樣本)

表9 FLP與KNN分類效率對比

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

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

1—FLP分類耗時；2—KNN分類耗時。

3 結(jié)論

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

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

對于特征庫的構(gòu)建、投影實例的生成以及投影實例與待分類樣本之間相似度的計算還有待進一步 優(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]. 計算機應用, 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] 鐘將, 劉榮輝. 一種改進的KNN文本分類[J]. 計算機工程與應用, 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]. 科學技術(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ù)改進的 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] 吳春穎, 王士同. 一種改進的KNN Web文本分類方法[J]. 計算機應用研究, 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è)大學學報(自然科學版), 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 模型的增量學習算法[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]. 小型微型計算機系統(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] 錢強, 龐林斌, 高尚. 一種基于改進型KNN算法的文本分類方法[J]. 江蘇科技大學學報(自然科學版), 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]. 中文信息學報, 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]. 江西師范大學學報(自然科學版), 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

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

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