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

李志堅(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ù)挖掘的文本分類算法。首先對(duì)網(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ù)集對(duì)模型性能進(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ù)形式增長(zhǎng)，其中非結(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]。

針對(duì)文本分類問(wèn)題，國(guó)內(nèi)外學(xué)者和專家投入了大量的時(shí)間和精力，進(jìn)行了廣泛深入的研究。文本分類算法可以劃分兩個(gè)階段：人工分類階段和自動(dòng)分類階段[3]。人工分類方法主要通過(guò)專家或?qū)I(yè)人士對(duì)文本類別進(jìn)行劃分，費(fèi)時(shí)費(fèi)力，而且分類結(jié)果不科學(xué)，不能滿足當(dāng)前海量的文本數(shù)據(jù)挖掘需求[4]。自動(dòng)分類方法主要通過(guò)計(jì)算機(jī)采用一定的算法進(jìn)行文本分類，分類復(fù)雜性大幅度降低，分類效率得以提高[5]。文本自動(dòng)分類是模式識(shí)別中的一種多分類問(wèn)題，主要包括文本特征提取、選擇以及文本分類器的構(gòu)建等[6]，本文主要針對(duì)文本分類器進(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ò)在分類過(guò)程中，經(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)化問(wèn)題。

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

1 CEPSO-SVM的文本分類模型

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

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

2 文本表示

2.1 文本向量化表示

設(shè)文本T={P1,P2,…,Pn}，其中n表示文本T中段落的數(shù)目，Pi(1≤i≤n)表示文本T中第i個(gè)段落，Pi=(ti1,ti2,…,timi)，其中mi表示段落Pi中關(guān)鍵詞數(shù)目，timk(1≤mk≤mi)表示段落Pi中第k個(gè)關(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í)理論的模式識(shí)別方法，其結(jié)構(gòu)如圖2所示。

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

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

w·x+b=0.

(3)

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

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

(4)

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

(5)

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

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

(6)

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

(7)

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

(8)

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

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

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

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

在粒子群算法中，在目標(biāo)搜索空間中有m個(gè)代表潛在問(wèn)題解的粒子，每個(gè)粒子都作為待優(yōu)化問(wèn)題的一個(gè)可行解，通過(guò)粒子之間的協(xié)作與競(jìng)爭(zhēng)尋求其最優(yōu)解。在第k次迭代中，第i個(gè)粒子的當(dāng)前位置和速度分別為xi(K)和vi(K)，粒子個(gè)體最優(yōu)歷史位置為：pBesti稱為個(gè)體最優(yōu)，種群的全局最優(yōu)粒子位置為gBesti，粒子種群在尋優(yōu)過(guò)程通過(guò)群體中個(gè)體之間的協(xié)作和信息共享來(lái)尋找最優(yōu)解，每個(gè)粒子根據(jù)下式對(duì)速度和位置進(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)化方式，兩個(gè)種群并行搜索，每一個(gè)種群采用不同的慣性權(quán)值ω，增強(qiáng)了種群的多樣性，較好個(gè)體可以在不同種群之間遷移，通過(guò)共享信息完成協(xié)作進(jìn)化，提高搜索效率，兩個(gè)種群慣性權(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ù)，主要包括兩個(gè)子群的規(guī)模，最大迭代次數(shù)tmax，參數(shù)c1，c2等。

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

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

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

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

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

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

4.1 數(shù)據(jù)來(lái)源

采用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)確地評(píng)價(jià)CEPSO-SVM的優(yōu)越性，選擇遺傳算法優(yōu)化支持向量機(jī)(GA-SVM)、粒子群算法優(yōu)化支持向量機(jī)(PSO-SVM)進(jìn)行對(duì)比實(shí)驗(yàn)，所有模型運(yùn)行10次，性能評(píng)價(jià)指標(biāo)為分類的正確率(precision)、召回率(recall)作為模型評(píng)價(jià)標(biāo)準(zhǔn)，它們定義如下：

(13)

(14)

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

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

4.2 結(jié)果與分析

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

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

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

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

4.2.2 分類速度對(duì)比

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

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

5 結(jié)語(yǔ)

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

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

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

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

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

[5]裴頌文,吳百鋒.動(dòng)態(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]趙輝,劉懷亮,范云杰,等.一種基于語(yǔ)義的中文文本分類算法[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]鄭誠(chéng),李鴻.基于主題模型的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ù)研究。