基于改進蟻群算法和支持向量機的網(wǎng)頁分類研究

摘要:網(wǎng)頁分類技術(shù)是web數(shù)據(jù)挖掘的一個重要分支，是基于自然語言處理技術(shù)和機器學(xué)習(xí)學(xué)習(xí)算法的一個典型的具體應(yīng)用?；诮y(tǒng)計學(xué)習(xí)理論和蟻群算法理論，該文提出了一種基于支持向量機和改進蟻群算法相結(jié)合的構(gòu)造網(wǎng)頁分類器的高效分類方法，實驗結(jié)果證明了該方法的有效性和魯棒性，彌補了僅利用支持向量機對于大樣本訓(xùn)練集收斂慢的不足，具有較好的準(zhǔn)確率和召喚率。

關(guān)鍵詞:改進蟻群算法;網(wǎng)頁分類;支持向量機;貢獻函數(shù)

中圖分類號:TP391文獻標(biāo)識碼:A文章編號:1009-3044(2009)35-10069-03

Study of Categorization of Web-Page Based on Improved Ant Colony Algorithm and Support Vector Machine

SONG Jun-tao， DU Qing-ling

(Dept. of Information Science and Engineering， Henan University of Technology， Zhengzhou 450001， China)

Abstract: Web page categorization is an of web data mining， it is a typical application based on technology of natural language processing and machine learning. It is imperative to find a effective and efficient method for web page categorization. In this paper， a new method is proposed for web page categorization based on improved ant colony optimization algorithm (IACOA) and support vector machines (SVMs).The experimental results show that the method is effective and robust， only to make up for the use of support vector machines for large sample training set less than the slow convergence with better precision and recall.

Key words: improved ant colony algorithm (IACA); web page categorization; support vector machine (SVM); contribution function

隨著計算機網(wǎng)絡(luò)技術(shù)的快速發(fā)展和Web 2.0廣泛深入的應(yīng)用，同時互聯(lián)網(wǎng)上的信息呈指數(shù)級增長，人們可利用的網(wǎng)絡(luò)信息也越來越多，如何從這些海量的信息中高效的獲得所需信息已成為當(dāng)前必須解決的問題。bayes分類、關(guān)聯(lián)規(guī)則、決策樹分類、單純的支持向量機算法[7]等在文本分類中得到廣泛的應(yīng)用并取得了很大的進步，與文本分類最大的不同在于網(wǎng)頁屬于半結(jié)構(gòu)化數(shù)據(jù)且數(shù)量極大，先前的文本分類算法直接引用到網(wǎng)頁分類中，其分類精度和效率受到一定的影響，特別是大規(guī)模樣本適應(yīng)性不強，收斂速度慢。支持向量機分類最大的優(yōu)點在于構(gòu)造一個最優(yōu)超平面，且有強大的統(tǒng)計理論基礎(chǔ)，分類精度高，因此在分類中得到廣泛的應(yīng)用，但對于大規(guī)模樣本訓(xùn)練過程中，表現(xiàn)出適應(yīng)性不強，收斂速度比較慢的不足，為此本文提出了基于蟻群算法和支持向量機的網(wǎng)頁分類方法。

1 SVM基本原理和蟻群算法

1.1 SVM基本原理

支持矢量機(Support Vector Machine，SVM)[1]是Vapnik等人于20世紀(jì)90年代中期提出的一類新型機器學(xué)習(xí)方法， 其理論基礎(chǔ)是統(tǒng)計學(xué)習(xí)理論。與基于經(jīng)驗風(fēng)險最小化原理的傳統(tǒng)的統(tǒng)計學(xué)習(xí)方法不同，SVM基于的是結(jié)構(gòu)風(fēng)險最小化原理。SVM不僅結(jié)構(gòu)簡單，而且各種技術(shù)性能尤其是推廣能力比神經(jīng)網(wǎng)絡(luò)等方法有明顯提高。標(biāo)準(zhǔn)的SVM的實現(xiàn)涉及求解線性約束的二次規(guī)劃問題，該問題可以收斂到全局最優(yōu)解。但當(dāng)訓(xùn)練數(shù)據(jù)很多時——這是很多實際問題所碰到的情況，二次規(guī)劃問題的求解受到存儲器容量的限制，而且分類速度也得不到保證，從而限制了SVM在很多問題上的應(yīng)用。常用的做法是將問題分解為若干個子問題，然后再對這些子問題進行逐一優(yōu)化。這樣做的缺陷是:結(jié)果可能只是一個次優(yōu)解，并且分解的時候可能需要多次分解才能將問題的規(guī)模轉(zhuǎn)化為能解決的程度。

1.2 蟻群算法簡介

蟻群算法[2](Ant Algorithm)由意大利人M.Dorigo等人首先提出的，蟻群算法是一個新的啟發(fā)算法，蟻群算法固有的并發(fā)性和可擴充性，使它非常適合用于帶約束的二次優(yōu)化求解問題。在同一時間內(nèi)，所有影響資源狀態(tài)的因素都能由一個事情，即信息素描述。進而能夠非常簡單、快速地獲得預(yù)測結(jié)果。

該算法按照啟發(fā)式思想，通過信息傳媒Pheromone的誘導(dǎo)作用，逐步收斂到問題的全局最優(yōu)解，是求解適應(yīng)性計算問題的一種有效方法。由于帶約束的二次規(guī)劃求解問題是眾所周知的NP問題，而大量的實驗表明，蟻群算法是一種有效的求解NP類問題的新型算法，具有較強的魯棒性和內(nèi)在的分布并行性，且易于和其他方法相結(jié)合。蟻群算法還有一個很大的優(yōu)點就是具有可擴展性。所謂可擴展性指的是在原有一個規(guī)模n的問題上求出最優(yōu)解后，再增加m個節(jié)點，可在原有解的基礎(chǔ)上快速找到該問題的n+m規(guī)模的最優(yōu)解，本文將蟻群算法與支持向量機結(jié)合充分保證支持向量機分類精度同時彌補其針對大規(guī)模訓(xùn)練樣本收斂慢的不足。

2 ACA及SVM在網(wǎng)頁分類中的應(yīng)用

2.1 網(wǎng)頁文檔預(yù)處理

網(wǎng)頁中數(shù)據(jù)最大的特點是半結(jié)構(gòu)化，數(shù)據(jù)呈現(xiàn)形式多樣化，首先用向量空間模型(SVM)[4-5]表示W(wǎng)eb頁面數(shù)據(jù)信息，本文采用TFIDF[6]向量表示方法，并非所有特征對分類都有用，況且不同的特征所起的作用也不一樣，預(yù)處理階段最重要的是關(guān)鍵特征提取及降維，直接影響到后續(xù)分類的精度。

2.2 SVM訓(xùn)練及ACA優(yōu)化求解流程

首先將樣本集分為訓(xùn)練集(80%)和測試集(20%)兩部分，訓(xùn)練集專門用于SVM訓(xùn)練，而測試集專門用于評價測試SVM分類性能，其中影響SVM分類性能的兩個重要參數(shù)是折衷參數(shù)C和高斯核函數(shù)K(xi，xj)=Ф(xi)Ф(xj)，訓(xùn)練過程中，不斷地調(diào)整參數(shù)C，同時利用上述蟻群算法對高斯核函數(shù)進行優(yōu)化，最終選取合適的參數(shù)值，整個過程利用上述蟻群算法對SVM分類器函數(shù)優(yōu)化求解，輸出分類結(jié)果，整個分類過程如圖1。

2.3 SVM[8-10]訓(xùn)練算法描述

1) 假設(shè)待訓(xùn)練樣本集為T={(x1，y1)，(x2，y2)，…，(xi，yi)} 其中xi∈Rn，yi∈{1，2，…M} i=1，2， …，n

2) SVM算法的出發(fā)點是利用核技巧在高維空間里進行有效的計算，找出支持向量及其系數(shù)構(gòu)造最優(yōu)分類面。而此最優(yōu)分類面的構(gòu)造問題實質(zhì)上是在約束條件下求解一個二次優(yōu)化問題，以得到一個最優(yōu)的決策函數(shù)，最優(yōu)分類超平面為:

決策分類目標(biāo)函數(shù)為:

3) 最優(yōu)分類超平面問題描述為:

b是一個閾值。

4) 其對偶最優(yōu)化問題為:

αi為二次優(yōu)化問題的最優(yōu)解，其中，K(xi，xj)=Ф(xi)Ф(xj)稱為高斯核函數(shù)，n為訓(xùn)練樣本個數(shù)，C為懲罰因子，它控制的是訓(xùn)練錯誤率與模型復(fù)雜度間的折衷。容易證明，該優(yōu)化問題的解中只有一部分(通常是很少的部分)αi不為零，這些不為零αi的對應(yīng)的樣本就是支持向量，只有支持向量影響最終的劃分結(jié)果。

2.4 蟻群算法[3-9]求解步驟:

算法優(yōu)化求解開始時，訓(xùn)練集中的每一個樣本點對應(yīng)一個螞蟻智能體，從t=0時刻開始第一輪搜索，當(dāng)t=l時所有螞蟻遍歷所有樣本點，完成了第一輪搜索。此時更新路徑上的信息素，并將禁忌表清空。然后開始下一輪搜索，在達到用戶設(shè)定的最大搜索輪數(shù)NC時，算法終止，此時找到的最優(yōu)解作為問題的最優(yōu)解。

1) 初始化:設(shè)定t=0，循環(huán)輪次數(shù)NC=0，對每條路徑設(shè)置ζi(0)=C和Δζij=0，將m只螞蟻均勻放置n個訓(xùn)練集中。

2) 設(shè)置s=l(s是禁忌表的索引)，對k=l，…，m，將第k只螞蟻所在的樣本點的編號放入禁忌表中。

3) 在禁忌表索引s≤n時，重復(fù)如下操作:

① s=s+i;

② 對k=1，…，m，做如下工作:依照公式

計算螞蟻在樣本點i選擇第j個樣本點作為下一站的概率，并按概率選擇樣本點，將螞蟻移至該樣本點，將其編號放入禁忌表中。

4) 對k=l，…，m，做如下工作:計算第k只螞蟻走過的路

徑長度，記錄當(dāng)前找到的最優(yōu)解，按公式

計算每只螞蟻的信息素增量。

5) 對所有的點(i，j)根據(jù)公式

更新路徑上的信息素。

設(shè)置t=t+n;NC=NC+1;設(shè)置所有的Δζij=0，

6) 如果NC≤NCmax或者沒有出現(xiàn)收斂現(xiàn)象，設(shè)置它們的禁忌表為空;轉(zhuǎn)到第2)步;否則，輸出最優(yōu)解，算法結(jié)束。

2.5 改進蟻群算法

2.5.1 貢獻函數(shù)的引入及優(yōu)化信息素平滑機制

蟻群算法在螞蟻對路徑進行探索之前，會對每條路徑上的信息素含量進行初始化，即每條邊的信息素含量具有相同的賦值。螞蟻在進行路徑選擇的時候，主要是憑借路徑的長度和信息素的含量來計算選擇該條路徑的概率，而在算法的起始階段，各條邊上的信息素含量是沒有差異或者差異很小。這樣就導(dǎo)致了螞蟻在最初階段僅僅憑借路徑的長短來對路徑進行選擇，然后再在選擇的路徑上留下信息素，從而吸引后續(xù)的螞蟻繼續(xù)對這些路徑進行探索。這種機制會使螞蟻盡可能的選擇長度較短的邊來構(gòu)造整個路徑，它使得螞蟻在路徑選擇時只對局部的優(yōu)化進行考慮，而忽略了全局，形成“近視”現(xiàn)象，在開始階段，每條邊上的信息素含量是相同的，螞蟻僅根據(jù)路徑的長度來進行概率性選擇。一種被稱作信息素平滑的機制首次被提出，它使得算法在接近收斂時能夠減小各條邊之間的信息素含量的差異，從而保證螞蟻對解空間的探索行為不會集中在一個相對較窄的范圍之內(nèi)。為了更好的分析、改進這種機制，首先簡單介紹一下蟻群算法的收斂條件。

從前面的分析可以看出，隨著蟻群對路徑探索的深入，也就是循環(huán)次數(shù)的增加，信息素的更新和揮發(fā)使得邊之間的信息素含量的差異將會變得越來越大，最終導(dǎo)致以每個城市為起點的邊集合中只有一條邊上的信息素含量值保持在一個較高的水平上。由于信息素的揮發(fā)機制，其它的邊幾乎不對螞蟻的選擇過程產(chǎn)生影響。這種情況被稱作算法收斂[11]，具體的定義如下:

定義2.1 τ(i，j)以i為起點的所有邊的集合上的信息素含量值，τmax(i，j)=argmax{τ(i，j)}，τmin(i，j)=argmin{τ(i，j)}，使信息素含量最大、最小值之間的差ζr=τmax(i，j)- τmin(i，j)。令τ=λζr+τmin(i，j)，其中λ∈(0，1)，那么點i的λ-branching就定義為集合{τ(i，j)τ(i，j)>τ<τ}的個數(shù)。

由定義2.1可以看出當(dāng)信息素含量差異越大時，λ-branching的值越小。所有點的λ-branching的均值就表明了算法的收斂程度，均值越接近1，算法越接近收斂狀態(tài)，即當(dāng)meanλ-branching =l時，算法收斂，也就是說螞蟻不再對新的解空間進行探索，最終結(jié)果將被獲得。當(dāng)算法非常接近收斂的時候，信息素平滑機制允許每條邊上的信息素含量根據(jù)一定的比例進行增加，從而減小差異，保持螞蟻對新的解空間的搜索行為。平滑公式如下:

其中，τij和τ*ij分別為平滑前后邊(i，j)上的信息素含量，δ∈[0，1]，τmax為最大的信息素含量。當(dāng)δ∈(0，1)時，螞蟻對路徑的認識信息，即信息素含量，并沒有完全丟失，而只是被弱化了:當(dāng)δ=0時，平滑機制對于信息素含量沒有任何影響;當(dāng)δ=1時，每條邊上的信息素含量都被設(shè)定為一個固定的值τmax。

但是，信息素平滑機制并沒有考慮到邊是否對于構(gòu)造更好路徑有幫助。這樣那些有幫助的邊沒有得到足夠的信息素增強，同時那些沒有幫助，甚至可能對后續(xù)螞蟻的選擇過程產(chǎn)生負面影響的邊上的信息素含量則得到了增強，從而使它們被選擇的機會大大增加。這兩個方面的影響都會在一定程度上降低算法的性能。因此，有必要引入貢獻函數(shù)來對平滑機制進行改進，使得貢獻函數(shù)大的邊能夠獲得更多的信息素增量，而使那些沒有貢獻，甚至對構(gòu)造更好的解產(chǎn)生負面作用的邊獲得較少的更新，以便螞蟻在后續(xù)的探索過程中更多的探索貢獻函數(shù)值比較大的邊，從而構(gòu)造出更好的路徑。改進后的信息素平滑公式如下:

其中，(i，j)是邊(i，j))的貢獻函數(shù)。

2.5.2改進蟻群算法描述

網(wǎng)頁分類的目的是從訓(xùn)練數(shù)據(jù)集中提取出IF-THEN規(guī)則，蟻群算法通過對每個屬性域中的屬性值集合的選取完成分類規(guī)則的構(gòu)建，算法描述具體步驟如下:

1) 清空規(guī)則列表，構(gòu)造訓(xùn)練集;

2) 初始化信息素和啟發(fā)式函數(shù);

3) 放置螞蟻，開始對屬性值集合進行選取，構(gòu)造分類規(guī)則;

4) 對構(gòu)造的規(guī)則進行處理，刪除不相關(guān)的屬性;

5) 根據(jù)構(gòu)造的分類規(guī)則的好壞進行信息素更新，若滿足終止條件，進行第6步，

否則進行第3步;

6) 將提取出的分類規(guī)則加入到規(guī)則列表中，若提取的分類規(guī)則可以涵蓋足夠的訓(xùn)練數(shù)據(jù)集中的數(shù)據(jù)，算法終止，否則，進行第2步。

3 實驗結(jié)果與分析

3.1 試驗結(jié)果

本文試驗在MATLAB7.0 環(huán)境進行仿真，數(shù)據(jù)采用10000篇網(wǎng)頁文檔(根據(jù)網(wǎng)頁主題內(nèi)容共分10個大類別)，通過預(yù)處理后從中隨機抽取20%用于測試評價分類器的性能，剩余80%用于訓(xùn)練，如圖2是在本文方法在訓(xùn)練過程中分別對不同的核函數(shù)(多層感知器核函數(shù)a、多項式核函數(shù)圖b，高斯核函數(shù)圖c)進行優(yōu)化的分類效果圖，結(jié)果表明本方法選用高斯核函數(shù)在網(wǎng)頁分類(特別是高維空間訓(xùn)練集)中效率比較高，明顯由于其它兩種核函數(shù)。

本文提出的方法與其它SVM分類方法相比，在訓(xùn)練樣本規(guī)模較小時分類精度沒有明顯的區(qū)別，但隨著樣本規(guī)模的增大，本文的方法在保證分類精度的同時適應(yīng)性有明顯提高，彌補了SVM本身針對大樣本適應(yīng)性方面的不足。

3.2 分析評價比較

表1是本文提出方法與其它兩種方法在準(zhǔn)確率、召喚率、宏平均和微平均方面的比較。

本文采用傳統(tǒng)的評價方法:正確率(P)，召喚率(R)和F1值來衡量分類的效果，其中

li，mi，ni分別表示第i(i=1，…，10)類分類結(jié)果中正確的網(wǎng)頁數(shù)目，實際包含的網(wǎng)頁數(shù)目和結(jié)果中出現(xiàn)的數(shù)目。微平均計算方法如下公式:

4 結(jié)束語

本文利用改進蟻群算法和支持向量機理論相結(jié)合，提出了基于改進蟻群算法和支持向量機的分類方法，對尋求構(gòu)建高效的網(wǎng)頁分類器進行了研究，并與傳統(tǒng)的分類算法如bayes算法、蟻群算法和支持向量機算法等進行分析比較，結(jié)果表明該方法應(yīng)用在網(wǎng)頁分類中在有效性、準(zhǔn)確性有明顯的改善，尤其在大規(guī)模訓(xùn)練集中適應(yīng)性更強。該方法在提高搜索引擎的速度和質(zhì)量方面有很大的應(yīng)用空間，是進一步學(xué)習(xí)研究的重點。

參考文獻:

[1] VAPNIK V.Universal Learning Technology: Support Vector Machines[J].NEC Journal of Advanced Technology，2005(2):137-144.

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

[3] 朱剛，馬良.TSP問題的蟻群算法求解[J].計算機工程與應(yīng)用，2007，43(10):79-80.

[4] CHEN P H，LIN C J，SCHLKOPF B.A tutorial on v-support vector machines[J].Applied Stochastic Models in Business and Industry，2005，21(2):111-136.

[5] Chang Chin-chang.Lin Chi-hjen.LIBSVM: a Library for support vector machines[J/OL].http://www.csie.ntu.tw/~cjlin/libsvm.2005.

[6] Mlademic D， Grobelink M. Feature Selection on Hierarchy of Web Documents[J].Decision Support System，2006(35).

[7] 賈泂，梁久禎.基于支持向量機的中文網(wǎng)頁自動分類[J].計算機工程，2005(5):18-22.

[8] 彭濤.基于粒子群優(yōu)化算法的網(wǎng)頁分類技術(shù)[J].計算機研究與發(fā)展，2006(6)33-38.

[9] 許建潮，胡明.中文web文本的特征獲取與分類[J].計算機工程，2005(4):24-26.

[10] 牛強，王志曉.基SVM的中文網(wǎng)頁分類方法的研究[J].計算機工程設(shè)計，2007(4):34-36.

[11] Gambardella L M. Dorigo Mf Ant-Q:a reinforcement learning approach to the travelingsalesman problem[C].Proceedings of the 12th International Conference on Wachine Learning，1995:252-260.