焦莉娟,宗春梅

(忻州師范學(xué)院 計(jì)算機(jī)系,山西 忻州 034000)

基于類(lèi)別覆蓋集的改進(jìn)蟻群算法研究

焦莉娟,宗春梅

(忻州師范學(xué)院 計(jì)算機(jī)系,山西 忻州 034000)

結(jié)合蟻群算法在解決分類(lèi)問(wèn)題方面的優(yōu)勢(shì),以及中文網(wǎng)頁(yè)內(nèi)容特征值的離散性特點(diǎn),提出一種改進(jìn)的基于蟻群算法的網(wǎng)頁(yè)分類(lèi)方法。該算法通過(guò)攜帶類(lèi)別信息的種群螞蟻的爬行,在迭代過(guò)程中尋找一條最佳路徑與之匹配，實(shí)現(xiàn)了Web頁(yè)面的分類(lèi)。最佳路徑通過(guò)計(jì)算測(cè)試文檔與每一類(lèi)別的覆蓋集合,進(jìn)而比較最優(yōu)覆蓋集合得到。其中類(lèi)別權(quán)重計(jì)算中引入了文字鏈接比和標(biāo)簽權(quán)值，進(jìn)一步提高了分類(lèi)精度。實(shí)驗(yàn)證明，引入類(lèi)別覆蓋集的蟻群分類(lèi)算法能夠取得更好的分類(lèi)效果。

蟻群算法；文本分類(lèi)；類(lèi)別覆蓋集；詞義相似度

0 引言

基于文本分類(lèi)的網(wǎng)絡(luò)頁(yè)面分類(lèi)是根據(jù)頁(yè)面文本內(nèi)容,由計(jì)算機(jī)依照某種分類(lèi)算法,把文本自動(dòng)映射到一個(gè)或多個(gè)預(yù)先定義好的類(lèi)別。網(wǎng)頁(yè)標(biāo)記與頁(yè)面鏈接是影響網(wǎng)絡(luò)頁(yè)面分類(lèi)的主要元素,采用文本與網(wǎng)頁(yè)特征有機(jī)結(jié)合的分類(lèi)方法是網(wǎng)頁(yè)分類(lèi)的研究趨勢(shì)[1]。目前常用的文本分類(lèi)方法有支持向量機(jī)[2]、樸素Bayes[3]、KNN[4]等。

蟻群算法ACA(Ant Colony Algorithm)是20世紀(jì)90年代意大利學(xué)者M(jìn) Dorigo,V Maniezzo,A Colorni等[5]通過(guò)模擬真實(shí)螞蟻尋找路徑的行為,而提出的一種成熟的模擬進(jìn)化算法。蟻群算法最初主要用于求解TSP問(wèn)題、分配問(wèn)題、Job-shop調(diào)度問(wèn)題等,目前已有學(xué)者將其應(yīng)用于文本分類(lèi)問(wèn)題,并取得顯著效果。本文利用蟻群算法在解決分類(lèi)問(wèn)題方面的優(yōu)勢(shì),將其引入Web頁(yè)面分類(lèi)領(lǐng)域,并提出類(lèi)別覆蓋集概念。

1 蟻群算法

研究發(fā)現(xiàn),螞蟻在尋找食物時(shí),會(huì)在走過(guò)的路上留下一種分泌物產(chǎn)生氣味,用來(lái)進(jìn)行信息交互,以此進(jìn)行相互合作共同完成任務(wù)。后來(lái)的螞蟻會(huì)選擇氣味最重的路徑行進(jìn)并釋放同樣的分泌物,如此循環(huán)往復(fù)。由于最短路徑上的螞蟻?zhàn)钕确祷叵佈?這樣單位時(shí)間內(nèi)的螞蟻流量最大,氣味揮發(fā)量最少,路上留下的氣味最重,因而有越來(lái)越多的螞蟻選這條路徑,直到所有螞蟻都趨向這條路徑。

用蟻群算法解決經(jīng)典問(wèn)題與網(wǎng)頁(yè)分類(lèi)問(wèn)題的關(guān)聯(lián)可描述如下：

(1)一類(lèi)螞蟻可對(duì)應(yīng)一個(gè)目標(biāo)類(lèi)別,該類(lèi)別名稱(chēng)由分類(lèi)機(jī)制決定。此時(shí)應(yīng)使螞蟻有針對(duì)性地?cái)y帶某種類(lèi)別信息。

(2)城市間的距離可對(duì)應(yīng)為特征結(jié)點(diǎn)之間存在的類(lèi)別關(guān)聯(lián)程度,即相似度,其計(jì)算公式為[5]：

(1)

(3)信息素對(duì)應(yīng)為結(jié)點(diǎn)詞條的類(lèi)別權(quán)重。

這樣,只要通過(guò)帶有類(lèi)別信息的種群螞蟻的爬行,便可找到每種類(lèi)別的最佳路徑,通過(guò)比較選擇一條信息素濃度最高的最佳路徑所對(duì)應(yīng)的類(lèi)別即為該文檔所屬類(lèi)別。

2 構(gòu)造分類(lèi)器

2.1 分類(lèi)算法

算法基本原理是,當(dāng)螞蟻類(lèi)別與文檔類(lèi)別一致時(shí)聚合效果好,生成的聚類(lèi)數(shù)量較少,因而信息素濃度高；相反其類(lèi)別一致性越差,聚合結(jié)果越雜亂,信息素濃度越低。算法中引入類(lèi)別覆蓋集來(lái)描述聚類(lèi)結(jié)果。首先使螞蟻?zhàn)陨韼в蓄?lèi)別信息并遍歷所有結(jié)點(diǎn),將測(cè)試文檔中的一個(gè)特征詞條作為一個(gè)結(jié)點(diǎn)。當(dāng)某一類(lèi)螞蟻k全部迭代完后,便生成一條類(lèi)別路徑Ik作為類(lèi)別k的覆蓋集合,即描述該類(lèi)別的最優(yōu)解。所有蟻群迭代結(jié)束后,可通過(guò)比較每一類(lèi)對(duì)應(yīng)各自類(lèi)別覆蓋集合上的信息素濃度b得出分類(lèi)結(jié)果,信息素濃度最大者的路徑Ik所描述的類(lèi)別k即為該文檔所屬類(lèi)別。

算法實(shí)現(xiàn)過(guò)程中需要解決如下問(wèn)題：

(1)確定路徑的下一節(jié)點(diǎn)。分別計(jì)算當(dāng)前節(jié)點(diǎn)與剩余節(jié)點(diǎn)的相似度概率積：X=S·Pij,其中S為兩點(diǎn)的余弦值,轉(zhuǎn)移概率計(jì)算公式為：

(2)

(2)更新結(jié)點(diǎn)j的信息素τj。在螞蟻已經(jīng)走過(guò)的路徑上信息量增加的同時(shí),各邊路徑上的原有信息量還會(huì)隨時(shí)間有一定的丟失。因此更新信息量的公式如下：

(3)

其中,ρ表示信息量τ隨時(shí)間的推移而衰減的程度。分類(lèi)問(wèn)題中期望螞蟻?zhàn)哌^(guò)的路徑能夠?qū)?yīng)一個(gè)文檔類(lèi)別的覆蓋集合,因此本文取△τ=wjk,為類(lèi)別k對(duì)于詞條j的權(quán)重值。

(3)確定最優(yōu)覆蓋集合。每一個(gè)類(lèi)別覆蓋集合記錄了此類(lèi)別對(duì)應(yīng)的一條最優(yōu)路徑的所有結(jié)點(diǎn),通過(guò)引入信息素濃度來(lái)比較各路徑與文本類(lèi)別的關(guān)聯(lián)程度,即單位距離內(nèi)信息素最多的路徑被認(rèn)為是與文本類(lèi)別關(guān)聯(lián)性最強(qiáng)的一條路徑,即最優(yōu)覆蓋集合。信息素濃度計(jì)算公式為：

(4)

算法描述：①按分類(lèi)機(jī)制取m只類(lèi)別螞蟻a1,a2,……,am,將測(cè)試文檔的特征詞條隨機(jī)散列；②初始化第k類(lèi)的類(lèi)別覆蓋集為空集φ；③隨機(jī)選擇首結(jié)點(diǎn)；④計(jì)算當(dāng)前詞條與其余所有詞條的相似度轉(zhuǎn)移概率積X；⑤選擇X值最大者作為下一詞條,并與當(dāng)前詞條連通,更新信息素濃度；⑥重復(fù)④、⑤,直到Max(X)小于標(biāo)準(zhǔn)值,轉(zhuǎn)下一步；⑦將通路聚合為一個(gè)新結(jié)點(diǎn),該結(jié)點(diǎn)信息素為原通路中所有結(jié)點(diǎn)信息素之和；⑧重復(fù)③～⑦,直到不再產(chǎn)生新聚類(lèi)為止；⑨重復(fù)②～⑧m次,得到m個(gè)類(lèi)別覆蓋集合；⑩求每一類(lèi)別覆蓋集的信息素濃度b,其最大值所對(duì)應(yīng)的類(lèi)別k=argMaxb(k)即為所求類(lèi)別。

2.2 分類(lèi)過(guò)程

訓(xùn)練過(guò)程中,若當(dāng)前訓(xùn)練文檔類(lèi)別為k,則利用TFID方法計(jì)算類(lèi)別k對(duì)于詞條i的權(quán)重wik。計(jì)算時(shí)引入“權(quán)重因子”可得到一個(gè)精度更高的詞條權(quán)重值。其中權(quán)重因子由網(wǎng)頁(yè)中標(biāo)簽權(quán)重和文字鏈接比的乘積計(jì)算得到。訓(xùn)練結(jié)果得到一個(gè)權(quán)重類(lèi)別詞庫(kù)。

測(cè)試過(guò)程引入基于類(lèi)別覆蓋集的分類(lèi)算法將測(cè)試語(yǔ)料進(jìn)行分類(lèi)，分類(lèi)過(guò)程如圖1所示。

3 實(shí)驗(yàn)

實(shí)驗(yàn)選取了200篇文檔,其中140篇作為訓(xùn)練語(yǔ)料,包括財(cái)經(jīng)類(lèi)40篇、體育類(lèi)40篇、文化類(lèi)30篇、軍事類(lèi)30篇、60篇作為測(cè)試語(yǔ)料。經(jīng)過(guò)特征提取可得到6 217個(gè)特征項(xiàng),訓(xùn)練過(guò)程就是計(jì)算這些特征項(xiàng)結(jié)點(diǎn)相對(duì)于每一類(lèi)別的權(quán)重值w。測(cè)試過(guò)程中,依照上述算法,對(duì)每一篇測(cè)試文檔進(jìn)行迭代、計(jì)算,并采用國(guó)際上通用的準(zhǔn)確率、召回率對(duì)分類(lèi)效果進(jìn)行評(píng)估。實(shí)驗(yàn)結(jié)果如表1所示。表1中參數(shù)A、B分別表示螞蟻種群平均數(shù)量和標(biāo)準(zhǔn)值。

圖1 分類(lèi)過(guò)程模型

表1 分類(lèi)結(jié)果比較

財(cái)經(jīng)體育文化軍事平均值P0．900．790．770．861000．58R0．880．830．800．800．84BPR0．890．810．790．83P0．920．930．960．91AB2000．70R0．900．910．950．920．93BPR0．910．920．960．91P0．920．930．810．915000．90R0．880．910．850．920．89BPR0．900．920．830．91

實(shí)驗(yàn)證明,對(duì)種群螞蟻規(guī)模、確定是否停止本次迭代的標(biāo)準(zhǔn)值的大小、權(quán)重因子等參數(shù)的取值都會(huì)直接影響分類(lèi)精度。圖2給出了A、B值分別取200和0.70時(shí),算法改進(jìn)前后分類(lèi)精度的對(duì)比。

圖2 引入類(lèi)別覆蓋集前后分類(lèi)精度對(duì)比

4 結(jié)語(yǔ)

本文主要研究了用蟻群算法進(jìn)行文本分類(lèi),并提出一種切實(shí)可行的分類(lèi)算法。實(shí)驗(yàn)證明,用基于類(lèi)別覆蓋集的改進(jìn)蟻群算法進(jìn)行文本分類(lèi)具有強(qiáng)魯棒性和優(yōu)良的分布式計(jì)算機(jī)制等優(yōu)勢(shì),是一個(gè)值得深入研究的課題。種群螞蟻規(guī)模確定以及如何選擇最佳相似度、標(biāo)準(zhǔn)值及詞性因子等參數(shù),以便達(dá)到最優(yōu)的分類(lèi)效果等,則是下一步需要解決的問(wèn)題。

[1] 鳳麗洲.文本分類(lèi)關(guān)鍵技術(shù)及應(yīng)用研究[D].長(zhǎng)春：吉林大學(xué),2015.

[2] WANG F,WANG Z,LI Z,et al.Concept-based short text classification and ranking[C].Proceeding of the 23rd ACM International Conference on Information and Knowledge Management.ACM,2014:1069-1078.

[3] 邸鵬,段利國(guó).一種新型樸素貝葉斯文本分類(lèi)算法[J].數(shù)據(jù)采集與處理,2014,29(1):11-15.

[4] 鐘將,劉榮輝.一種改進(jìn)的KNN文本分類(lèi)[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(2):142-144.

[5] 段海濱.蟻群算法原理及其應(yīng)用[M].北京:科學(xué)出版社,2005.

(責(zé)任編輯：孫 娟)

焦莉娟(1978-),女,山西忻州人,碩士,忻州師范學(xué)院計(jì)算機(jī)系副教授,研究方向?yàn)樽匀徽Z(yǔ)言處理、數(shù)字圖像處理；宗春梅(1977-),女,山西忻州人,碩士,忻州師范學(xué)院計(jì)算機(jī)系講師,研究方向?yàn)閿?shù)據(jù)挖掘。

10.11907/rjdk.162540

TP312

A

1672-7800(2017)003-0054-02