李志堅(jiān)

(阿壩師范學(xué)院，四川汶川 623002)

基于數(shù)據(jù)挖掘的文本分類算法

李志堅(jiān)

(阿壩師范學(xué)院，四川汶川 623002)

文本分類是網(wǎng)絡(luò)數(shù)據(jù)管理研究中的難點(diǎn)，本文運(yùn)用支持向量機(jī)非線性分類能力和協(xié)同進(jìn)化粒子群算法全局搜索能力，提出一種基于數(shù)據(jù)挖掘的文本分類算法。首先對網(wǎng)絡(luò)文本樣本進(jìn)行相關(guān)預(yù)處理，提取文本的特征向量，然后將訓(xùn)練樣本輸入到支持量機(jī)進(jìn)行訓(xùn)練，采用協(xié)同進(jìn)化粒子群優(yōu)化算法優(yōu)化分類器參數(shù)，最后采用Reuters21578數(shù)據(jù)集對模型性能進(jìn)行分析。研究結(jié)果表明，運(yùn)用協(xié)同進(jìn)化粒子群算法可以快速找到支持向量機(jī)的最優(yōu)參數(shù)，提高文本分類的正確率，分類速度可以滿足文本分類在線應(yīng)用要求。

文本分類；協(xié)同進(jìn)化粒子群算法；特征向量；支持向量機(jī)

隨著互聯(lián)網(wǎng)的高速發(fā)展，網(wǎng)絡(luò)上的信息量呈指數(shù)形式增長，其中非結(jié)構(gòu)化文本數(shù)據(jù)所占比率最大，如何從紛繁的文本數(shù)據(jù)中挖掘出用戶感興趣的信息變得日益重要[1]。文本分類是網(wǎng)絡(luò)文本數(shù)據(jù)挖掘的基礎(chǔ)，分類結(jié)果的好壞直接影響文本數(shù)據(jù)挖掘效果，因此如何構(gòu)建正確率高的文本分類算法成為網(wǎng)絡(luò)信息數(shù)據(jù)挖掘研究中的重點(diǎn)[2]。

針對文本分類問題，國內(nèi)外學(xué)者和專家投入了大量的時間和精力，進(jìn)行了廣泛深入的研究。文本分類算法可以劃分兩個階段：人工分類階段和自動分類階段[3]。人工分類方法主要通過專家或?qū)I(yè)人士對文本類別進(jìn)行劃分，費(fèi)時費(fèi)力，而且分類結(jié)果不科學(xué)，不能滿足當(dāng)前海量的文本數(shù)據(jù)挖掘需求[4]。自動分類方法主要通過計(jì)算機(jī)采用一定的算法進(jìn)行文本分類，分類復(fù)雜性大幅度降低，分類效率得以提高[5]。文本自動分類是模式識別中的一種多分類問題，主要包括文本特征提取、選擇以及文本分類器的構(gòu)建等[6]，本文主要針對文本分類器進(jìn)行研究。當(dāng)前，本文分類器主要基于支持向量機(jī)和神經(jīng)網(wǎng)絡(luò)等數(shù)據(jù)挖掘技術(shù)進(jìn)行構(gòu)建。神經(jīng)網(wǎng)絡(luò)是一種基于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則的數(shù)據(jù)挖掘技術(shù)，其可以描述文本類別與文本特征之間的非線性關(guān)系，在文本分類中到廣泛的應(yīng)用[7-9]，然而網(wǎng)絡(luò)文本是一種特殊文本數(shù)據(jù)，其特征向量的維數(shù)相當(dāng)高，導(dǎo)致神經(jīng)網(wǎng)絡(luò)在分類過程中，經(jīng)常出現(xiàn)“維數(shù)災(zāi)”等難題，而且神經(jīng)網(wǎng)絡(luò)自身存在網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜等不足，限制了其在文本分類的應(yīng)用范圍[10]。支持向量機(jī)是一種基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則的數(shù)據(jù)挖掘技術(shù)，較好地解決了“維數(shù)災(zāi)”等難題，泛化能力優(yōu)異，成為文本分類中的主要研究方向[10-12]。支持向量機(jī)的文本分類性能與核函數(shù)及參數(shù)密切相關(guān)，因此要獲得分類正確率高的文本分類結(jié)果，首先要解決支持向量機(jī)參數(shù)優(yōu)化問題。

針對支持向量機(jī)在文本分類中的參數(shù)優(yōu)化難題，本文以提高文本分類為目的，提出了一種基于數(shù)據(jù)挖掘技術(shù)的文本分類算法(CEPSO-SVM)，采用協(xié)同進(jìn)化粒子群優(yōu)化(co-evolution based on particle swarm optimization，CEPSO)算法選擇支持向量機(jī)的參數(shù)，并通過Reuters21578數(shù)據(jù)集對其性能進(jìn)行分析。

1 CEPSO-SVM的文本分類模型

基于CEPSO-SVM的文本分類步驟：首先收集相關(guān)文本樣本，并進(jìn)行相關(guān)預(yù)處理，提取特征向量和計(jì)算特征向量的權(quán)值，然后根據(jù)特征向量和特征向量的權(quán)值對訓(xùn)練樣本和測試樣本進(jìn)行處理，并將測試樣本輸入到支持量機(jī)進(jìn)行訓(xùn)練，通過協(xié)同進(jìn)化粒子群優(yōu)化算法選擇支持向量機(jī)的參數(shù)，最后建立文本分類模型，并采用測試樣本對模型性能進(jìn)行分析，其工作原理具體如圖1所示。

圖1 CEPSO-SVM的文本分類原理

2 文本表示

2.1 文本向量化表示

設(shè)文本T={P1,P2,…,Pn}，其中n表示文本T中段落的數(shù)目，Pi(1≤i≤n)表示文本T中第i個段落，Pi=(ti1,ti2,…,timi)，其中mi表示段落Pi中關(guān)鍵詞數(shù)目，timk(1≤mk≤mi)表示段落Pi中第k個關(guān)鍵詞，則文本T可以表示為[13]：

(1)

2.2 計(jì)算文本特征項(xiàng)權(quán)值

特征項(xiàng)，即關(guān)鍵詞，作為文本表示的基本單位，本文選擇TF*IDF算法計(jì)算特征項(xiàng)權(quán)值，具體如下：

(2)

3 支持向量機(jī)構(gòu)建本文分類器

3.1 支持向量機(jī)分類原理

支持向量機(jī)是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的模式識別方法，其結(jié)構(gòu)如圖2所示。

圖2 支持向量機(jī)的結(jié)構(gòu)

對于已知的樣本(xi,yi),yi=±1,i∈N+，通過支持向量機(jī)得出一個最優(yōu)分類平面，滿足以下表達(dá)式：

w·x+b=0.

(3)

同時，訓(xùn)練集樣本中應(yīng)該滿足：

yi(w·x+b)-1≥0.

(4)

將線性分類轉(zhuǎn)化為一個二次回歸問題：

(5)

其中，C為懲罰因子[14]。

最后，推導(dǎo)出支持向量的線性判別函數(shù)：

(6)

對于非線性分類問題，引入核函數(shù)k(xi,xi)性判別函數(shù)，可以得到：

(7)

本文選用RBF核函數(shù)，其公式如下：

(8)

文本分類是一種多分類問題，采用如圖3所示的方式構(gòu)建文本分類器。

圖3 多分類的文本分類器構(gòu)建

支持向量機(jī)在構(gòu)建文本分類器過程中，需要優(yōu)化核函數(shù)參數(shù)σ和C，為此本文協(xié)同進(jìn)化粒子群算法進(jìn)行優(yōu)化，以提高本文分類的正確率。

3.2 協(xié)同進(jìn)化粒子群算法

在粒子群算法中，在目標(biāo)搜索空間中有m個代表潛在問題解的粒子，每個粒子都作為待優(yōu)化問題的一個可行解，通過粒子之間的協(xié)作與競爭尋求其最優(yōu)解。在第k次迭代中，第i個粒子的當(dāng)前位置和速度分別為xi(K)和vi(K)，粒子個體最優(yōu)歷史位置為：pBesti稱為個體最優(yōu)，種群的全局最優(yōu)粒子位置為gBesti，粒子種群在尋優(yōu)過程通過群體中個體之間的協(xié)作和信息共享來尋找最優(yōu)解，每個粒子根據(jù)下式對速度和位置進(jìn)行更新：

vid(k+1)=wvid(k)+c1r1(pBestid(k)-xid(k))+c2r2(gBestid(k)-xid(k)).

(9)

xid(k+1)=xid(k)+vid(k+1).

(10)

其中，k為當(dāng)代的迭代次數(shù)，vid(k)和vid(k+1)分別為第i，i+1代粒子速度，vid(k)和vid(k+1)分別為第i，i+1代粒子位置；c1和c2為加速因子；r1和r2為隨機(jī)數(shù)；ω稱為慣性因子。

為了加快粒子種群搜索速度，本文引入雙種群協(xié)同進(jìn)化方式，兩個種群并行搜索，每一個種群采用不同的慣性權(quán)值ω，增強(qiáng)了種群的多樣性，較好個體可以在不同種群之間遷移，通過共享信息完成協(xié)作進(jìn)化，提高搜索效率，兩個種群慣性權(quán)值ω的更新方式分別如下：

ω1=ω1max-k×(ω1max-ω1min)/kmax.

(11)

ω2=(ω2max-ω2min)×(kmax-k)/kmax+ω2min.

(12)

3.3 協(xié)同進(jìn)化粒子群算法優(yōu)化支持向量機(jī)參數(shù)

步驟一：設(shè)置協(xié)同進(jìn)化粒子群算法的相關(guān)參數(shù)，主要包括兩個子群的規(guī)模，最大迭代次數(shù)tmax，參數(shù)c1，c2等。

步驟二：初始化粒子群S1和S2的位置和速度，并根據(jù)適應(yīng)度值確定pBest和gBest。

步驟三：根據(jù)每一種粒子對應(yīng)的參數(shù)(C,σ)得到文本分類正確率作為每個粒子的適應(yīng)度值。

步驟四：粒子群S1和S2分別根據(jù)(9)和(10)同步更新每個粒子的位置和速度，并對S1和S2的pBest和gBest進(jìn)行更新。

步驟五：比較粒子群S1和S2的pBest和gBest，共享兩種群中的pBest和gBest。

步驟六：如果t>tmax，最優(yōu)個體對應(yīng)的參數(shù)值為最優(yōu)參數(shù)(C,σ)，否則返回步驟三。

4 CEPSO-SVM在文本分類中的應(yīng)用

4.1 數(shù)據(jù)來源

采用Pentium(R)Dual-Core CPU E5800 @ 3.20GHzI，8 GB RAM，Windows 7操作系統(tǒng)，編程軟件為VC++，采用Reuters21578 Top10數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)。為了全面、準(zhǔn)確地評價(jià)CEPSO-SVM的優(yōu)越性，選擇遺傳算法優(yōu)化支持向量機(jī)(GA-SVM)、粒子群算法優(yōu)化支持向量機(jī)(PSO-SVM)進(jìn)行對比實(shí)驗(yàn)，所有模型運(yùn)行10次，性能評價(jià)指標(biāo)為分類的正確率(precision)、召回率(recall)作為模型評價(jià)標(biāo)準(zhǔn)，它們定義如下：

(13)

(14)

Reuters21578數(shù)據(jù)集是共有21578個文檔，共分為topics、organizations、exchanges、places和people五個大類，135個子類別，最常用的10個子類別稱為Reuters21578 Top10，具體如表1所示[15]。

表1 Reuters21578 Top10數(shù)據(jù)集

4.2 結(jié)果與分析

4.2.1 分類正確率和召回率比較

在表1的每個類別中選取一定量的文檔(70%)作為訓(xùn)練文本，其余文檔(30%)作為測試文本，CEPSO-SVM、GA-SVM以及PSO-SVM的文本分類的準(zhǔn)確率和召回率分別圖3和圖4所示。GA-SVM的文本分類正確率保持在82%左右，PSO-SVM文本分類正確率保持在92%左右，而CEPSO-SVM的文本分類正確率保持在97%左右，相對于對比模型，CEPSO-SVM分別大約提高了10%和5%，同時文本類的召回率也得到相應(yīng)的提高，這主要是由于相對于遺傳算法和標(biāo)準(zhǔn)粒子群優(yōu)化算法，協(xié)同進(jìn)化粒子群優(yōu)化的搜索能力更強(qiáng)，找到了更優(yōu)的支持向量機(jī)參數(shù)，因此獲得了更加理想的文本分類結(jié)果。

圖4 CEPSO-SVM與其它模型的分類正確率對比

圖5 CEPSO-SVM與其它模型的召回率對比

4.2.2 分類速度對比

對于海量文本數(shù)據(jù)進(jìn)行挖掘，分類速度是文本評分算法一個重要指標(biāo)，采用平均分類時間作為每一種算法的分類速度，如表2所示。相對于對比模型，CEPSO-SVM的分類時間最少，主要由于采用協(xié)同進(jìn)化粒子群算法對文本分類進(jìn)行尋優(yōu)，加快了算法的收斂速度，可以更好地滿足網(wǎng)絡(luò)文本在線分類需求。

表2 CEPSO-SVM與其它模型的分類速度對比

5 結(jié)語

本文針對支持向量機(jī)在文本分類過程的參數(shù)優(yōu)化問題，利用協(xié)同進(jìn)化粒子群算法控制參數(shù)少、尋優(yōu)能力強(qiáng)的優(yōu)勢，提出一種數(shù)據(jù)挖掘技術(shù)的文本分類算法，其通過協(xié)同進(jìn)化粒子群算法選擇支持向量機(jī)參數(shù)，并采用文本數(shù)據(jù)對其性能進(jìn)行仿真測試。實(shí)驗(yàn)結(jié)果表明，CEPSO-SVM不僅提高了文本分類的正確率，而且加快了文本分類的速度，是一種有效的文本數(shù)據(jù)挖掘方法。

[1]袁軍鵬,朱東華,李毅,等.文本挖掘技術(shù)研究進(jìn)展[J].計(jì)算機(jī)應(yīng)用研究,2006,23(2):1-4.

[2]龐觀松,蔣盛益.文本自動分類技術(shù)研究綜述[J].情報(bào)理論與實(shí)踐,2012,35(2):123-128.

[3]汪敏,肖詩斌,王弘蔚,等.一種改進(jìn)的基于《知網(wǎng)》的詞語相似度計(jì)算[J].中文信息學(xué)報(bào),2008,22(5):84-90.

[4]王振振,何明,杜永萍,等.基于LDA主題模型的文本相似度計(jì)算[J].計(jì)算機(jī)科學(xué),2013,40(12):229-232.

[5]裴頌文,吳百鋒.動態(tài)自適應(yīng)特征權(quán)重的多類文本分類算法研究[J].計(jì)算機(jī)應(yīng)用研究,2011,28(11):4092-4096.

[6]胡元,石冰.基于區(qū)域劃分的kNN文本快速分類算法研究[J].計(jì)算機(jī)科學(xué),2012,39(10):182-186.

[7]鐘將,孫啟干,李靜.基于歸一化向量的文本分類算法[J].計(jì)算機(jī)工程,2011,37(8):47-49.

[8]趙輝,劉懷亮,范云杰,等.一種基于語義的中文文本分類算法[J].情報(bào)理論與實(shí)踐,2012,35(3):115-118.

[9]Fernando F,Kseniya Z,Wolf-Gang M.Text categorization methods for automatic estimation of verbal intelligence[J].Expert Systems with Applications,2012,39(10):9807-9820.

[10]Sujeevan A,Younes B.Semi-structured document categorization with a semantic kernel[J].Pattern Recognition,2009,42(9):2067-2076.

[11]何維,王宇.基于句子的文本表示及中文文本分類研究[J].情報(bào)學(xué)報(bào),2009,28(6):839-843.

[12]Zakaria E,Abdelattif R,Mohamed A.Using word net for text categorization[J].The International Arab Journal of Information Technology,2008,5(1):16-24.

[13]Wei C P,Lin Y T Cross-lingual text categorization:conquering language boundaries in globalize environments[J].Information Processing & Management,2011,47(5):786-804.

[14]任劍鋒,梁雪,李淑紅.基于非線性流形學(xué)習(xí)和支持向量機(jī)的文本分類算法[J].計(jì)算機(jī)科學(xué),2012,39(1):261-263.

[15]鄭誠,李鴻.基于主題模型的K-均值文本聚類[J].計(jì)算機(jī)與現(xiàn)代化,2013,24(8):78-80,84.

TextClassificationAlgorithmOptimizingBasedonDataMining

LI Zhi-jian

(Aba Teachers University, Wenchuan Sichuan 623002, China)

Text classification is a key problem in network data management research, this paper puts forward a text classification algorithm based on data mining which uses nonlinear classification ability of support vector machine and search ability of collaborative global evolutionary particle swarm optimization algorithm. Firstly, the text samples are pre-processed to extract features, and then the features of training samples are input to support vector machines for training which co evolutionary particle swarm optimization algorithm is used to optimize the parameters of classifier, finally, the performance of the model is tested by Reuters21578 data. The results show that, co-evolution based on particle swarm optimization algorithm can quickly find the optimal parameters for support vector machine, improve the correct rate of text classification, classification speed can satisfy the application requirement of online classification.

text classification; co-evolution based on particle swarm optimization algorithm; feature vector; support vector machine

TP391

A

2095-7602(2017)12-0047-06

2016-12-30

李志堅(jiān)(1982- )，男，助理研究員，碩士研究生，從事計(jì)算機(jī)應(yīng)用技術(shù)研究。