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

焦莉娟,宗春梅

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

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

焦莉娟,宗春梅

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

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

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

0 引言

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

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

1 蟻群算法

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

用蟻群算法解決經典問題與網頁分類問題的關聯可描述如下：

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

(2)城市間的距離可對應為特征結點之間存在的類別關聯程度,即相似度,其計算公式為[5]：

(1)

(3)信息素對應為結點詞條的類別權重。

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

2 構造分類器

2.1 分類算法

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

算法實現過程中需要解決如下問題：

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

(2)

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

(3)

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

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

(4)

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

2.2 分類過程

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

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

3 實驗

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

圖1 分類過程模型

表1 分類結果比較

財經體育文化軍事平均值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

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

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

4 結語

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

[1] 鳳麗洲.文本分類關鍵技術及應用研究[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].數據采集與處理,2014,29(1):11-15.

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

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

(責任編輯：孫 娟)

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

10.11907/rjdk.162540

TP312

A

1672-7800(2017)003-0054-02