焦莉娟,宗春梅

(忻州師范學院 計算機系,山西 忻州 034000)

基于類別覆蓋集的改進蟻群算法研究

焦莉娟,宗春梅

(忻州師范學院 計算機系,山西 忻州 034000)

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

蟻群算法；文本分類；類別覆蓋集；詞義相似度

0 引言

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

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

1 蟻群算法

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

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

(1)一類螞蟻可對應(yīng)一個目標類別,該類別名稱由分類機制決定。此時應(yīng)使螞蟻有針對性地攜帶某種類別信息。

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

(1)

(3)信息素對應(yīng)為結(jié)點詞條的類別權(quán)重。

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

2 構(gòu)造分類器

2.1 分類算法

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

算法實現(xiàn)過程中需要解決如下問題：

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

(2)

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

(3)

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

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

(4)

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

2.2 分類過程

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

測試過程引入基于類別覆蓋集的分類算法將測試語料進行分類，分類過程如圖1所示。

3 實驗

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

圖1 分類過程模型

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

財經(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

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

圖2 引入類別覆蓋集前后分類精度對比

4 結(jié)語

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

[1] 鳳麗洲.文本分類關(guān)鍵技術(shù)及應(yīng)用研究[D].長春：吉林大學,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] 邸鵬,段利國.一種新型樸素貝葉斯文本分類算法[J].數(shù)據(jù)采集與處理,2014,29(1):11-15.

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

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

(責任編輯：孫 娟)

焦莉娟(1978-),女,山西忻州人,碩士,忻州師范學院計算機系副教授,研究方向為自然語言處理、數(shù)字圖像處理；宗春梅(1977-),女,山西忻州人,碩士,忻州師范學院計算機系講師,研究方向為數(shù)據(jù)挖掘。

10.11907/rjdk.162540

TP312

A

1672-7800(2017)003-0054-02