基于欠采樣支持向量機不平衡的網(wǎng)頁分類系統(tǒng)①

李村合, 唐 磊(中國石油大學(xué) 計算機與通信工程學(xué)院, 青島 266580)

基于欠采樣支持向量機不平衡的網(wǎng)頁分類系統(tǒng)①

李村合, 唐 磊
(中國石油大學(xué) 計算機與通信工程學(xué)院, 青島 266580)

在這個信息爆炸的時代, 如何處理這些海量的數(shù)據(jù)如何有效的分類已經(jīng)引起了人們的高度重視, 尤其是在互聯(lián)無技術(shù)迅速發(fā)展的階段, 網(wǎng)頁分類這領(lǐng)域已成為熱點. 與傳統(tǒng)的分類方法相比, 支持向量機具有高維、小樣本、適應(yīng)性強的特點, 能夠非常有效率的解決網(wǎng)頁分類問題, 但是不平衡數(shù)據(jù)的分類這一方面, 存在著分類不精確的問題. 所以本文提出了新的解決不平衡數(shù)據(jù)樣本策略, 便是將欠采樣策略與傳統(tǒng)的支持向量機結(jié)合起來,在減少多數(shù)類樣本集中噪聲數(shù)據(jù)的基礎(chǔ)上增加少數(shù)類的樣本集數(shù)量, 從而使得不平衡樣本集趨向于平衡, 最后結(jié)合SMO(Senquential Minimal Optimization)算法改進分類器, 提高了分類的準(zhǔn)確性.

支持向量機; SMO算法; 訓(xùn)練集縮減算法; 網(wǎng)頁分類; 多類分類

1 引言

隨著互聯(lián)網(wǎng)的發(fā)展, 網(wǎng)絡(luò)的信息量爆炸式的增長,人們從互聯(lián)網(wǎng)中獲取有用的信息越來越困難, 也給互聯(lián)網(wǎng)的企業(yè)帶來的挑戰(zhàn), 由此, 網(wǎng)頁分類技術(shù)如雨后春筍般發(fā)展起來, 在眾多的分類方法中, 支持向量機具有較強的學(xué)習(xí)能力, 經(jīng)成為網(wǎng)頁分類界研究的熱點尤其是搜索引擎領(lǐng)域[1]. 在分類的算法里, 支持向量機是非常優(yōu)秀的算法, 支持向量機是一統(tǒng)計學(xué)理論和結(jié)構(gòu)風(fēng)險最小化原則為基礎(chǔ)的學(xué)習(xí)機器[2], 在分類領(lǐng)域具有非常廣泛的應(yīng)用, 在平衡問題的表現(xiàn)上效果非常好, 可以克服局部最小值問題, 但是在支持向量機在處理不平衡樣本集時其分類效果并不理想[3]. 出現(xiàn)上述問題的原因是傳統(tǒng)的分類算法都是以提高整體分類準(zhǔn)確率作為目標(biāo), 然而, 實際問題中存在大量的不平平衡樣本集: 某一類的樣本數(shù)量遠(yuǎn)少于其他樣本數(shù)量, 例如信用卡欺詐行為檢測, 網(wǎng)絡(luò)入侵行為檢測醫(yī)學(xué)疾病診斷[4], 產(chǎn)品合格檢查. 不平衡樣本集的分類問題是, 總體準(zhǔn)確率還可以, 然而少數(shù)樣本的分類準(zhǔn)確率很低, 可是在很多的實際問題中, 比如在癌癥檢測中, 健康細(xì)胞現(xiàn)相對于癌細(xì)胞是多數(shù)類, 對癌細(xì)胞的正確分類更重要[5], 在辨別垃圾郵件中, 垃圾郵件是少數(shù)類, 然而對垃圾郵件的辨別更重要. 在眾多解決支持向量機不平衡分類的研究中, 比較出色的的策略是欠采樣算法, 和修改核函數(shù)[6]. 本文紹了支持向量機, 并且在傳統(tǒng)的支持向量機中結(jié)合欠采樣策略在一定程度上解決了不平衡網(wǎng)頁分類的問題.

2 相關(guān)技術(shù)

2.1 支持向量機

最早, 是由Vapnik提出支持向量機(SVM)理論[7].該方法采用結(jié)構(gòu)風(fēng)險最小化原則代替?zhèn)鹘y(tǒng)經(jīng)驗啊風(fēng)險最小化原則, 可以使其在訓(xùn)練樣本數(shù)量有限的情況下,很好的兼顧分類識別準(zhǔn)確率和分類推廣能力, 因此SVM被廣泛的運用到模式識別和分類問題中[8]. 其原理如下:假設(shè)存在一個具有兩類樣本的訓(xùn)練樣本集合如公式(1)所示:

其中, ω代表的是該超平面的法線的方向.

求解最優(yōu)分類超平面w, x+b=0, 即在訓(xùn)練集一定的情況下, 確定參數(shù)ω和b的最佳值, 以最小化下面的公式(3):

該問題的求解是一個尋優(yōu)問題, 在此為凸二次規(guī)劃問題[9], 通過引進拉格朗日算子αi≥0,i=1,...,l , 得到如下拉格朗日公式:

這里L(fēng)的極值點為鞍點, 可取L對α的最大值α=α*, 和對ω、b的最小值ω=ω*, b=b*, 將原問題的求解最小化問題轉(zhuǎn)換成求解最大化問題, 滿足約束條件:

解如下問題:

得到最優(yōu)超平面:其中, xr,xs為任意支持向量. 從公式(8)中可以發(fā)現(xiàn),當(dāng)一個樣本的αi=0時, 它對分類沒有任何影響, 只有當(dāng) αi＞0才會影響到ω* , 進而對分類結(jié)果產(chǎn)生影響分類, 這種對分類結(jié)果有影響的樣本稱之為支持向量.

相應(yīng)的分類器為:

對于一個未知類別的樣本x, 若f( x)=+1, 則樣本x屬于正類, 即當(dāng)前類別, 若f( x)=-1, 則樣本x屬于負(fù)類, 即非當(dāng)前類別.

2.2 SMO算法

SMO算法的全稱是Senquential Minimal Optimization, 是由John C. Platttu提出來的[10]. 支持向量機訓(xùn)練的問題實際上是一個凸優(yōu)化問題, 即求解一個受約束的二次規(guī)劃(quadratic programming, QP)問題,其中比較有名的就是SMO算法, SMO算法的思想是循環(huán)迭代: 都是將原有大規(guī)模的QP問題分解成一系列小的QP問題, 按照某種迭代策略, 反復(fù)求解小的QP問題, 構(gòu)造出原有的大規(guī)模QP問題的近似解, 并使該近似解逐漸收斂到最優(yōu)解[11].

3 基于欠采樣不平衡SVM算法實現(xiàn)

針對不平衡數(shù)據(jù)集上使用傳統(tǒng)支持向量機的時候,少數(shù)類的分類精度非常低. 最近有許多解決不平衡SVM分類的方法, 這些解決方法主要是從數(shù)據(jù)和算法方面入手[12]. 從數(shù)據(jù)這方面入手, 主要有重采樣方法,隨機下采樣方法, 向下采樣方法[13]. 把訓(xùn)練數(shù)據(jù)集中的的多數(shù)類樣本減少, 以提高分類性能, 被稱為欠采樣方法[14]. 為了減少樣不平衡樣本集中多數(shù)類, 本文對多數(shù)類樣本集進行欠采樣處理, 于是提出了基于欠采樣不平衡SVM算法(Under-sampling-SVM ).

下面是算法的定義:

定義1. (距離)給定兩個數(shù)據(jù)集, xi, xj, 在特征空間上兩個樣本之間的距離可以表示為:

定義2. 這些發(fā)樣本的平均特征成為這些樣品的中心. 給定訓(xùn)練樣本{x1, x2,...,xn}, 所以這些樣本的中心可以表達為:

如果使用不平衡訓(xùn)練數(shù)據(jù)集, 傳統(tǒng)SVM分類分級后, 將接收到的樣本的類別是相同的少數(shù)類訓(xùn)練數(shù)據(jù)集的有準(zhǔn)確的分類. 每當(dāng)在不平衡數(shù)據(jù)樣本集上采用傳統(tǒng)的SVM進行分類, 得到的超平面會靠近少數(shù)類的側(cè)面. 分類后, 少數(shù)類的幾個樣品被分類為多數(shù), 一邊, 多數(shù)類的樣品幾乎列為多數(shù)的側(cè)面. 因此少數(shù)類的分類精度不高. 如示于圖1.

圖1 不平衡訓(xùn)練樣本集表現(xiàn)

根據(jù)支持向量機的幾何特征確定如何減少大多數(shù)類的不平衡支持向量機學(xué)習(xí)的大小應(yīng)該考慮一個樣本的大多數(shù)類和少數(shù)類的中心之間的距離. 基于定義1的結(jié)果, 增加不平衡支持向量機學(xué)習(xí)中的少數(shù)類的大小應(yīng)該考慮不平衡支持向量機分類的結(jié)果因此, 當(dāng)做不平衡的支持向量機學(xué)習(xí)時, 我們使用下面的篩選機制: 盡我們所能選擇的樣本, 大多數(shù)類封閉的少數(shù)類的中心作為新的大多數(shù)樣本, 增加少數(shù)類的樣本添加到少數(shù)樣本的不平衡支持向量機分類.

所以, 基于欠采樣不平衡SVM算法可以概括如下: (設(shè)置原始不平衡樣本集作為一個A,設(shè)置少數(shù)類樣本A+, 設(shè)置多數(shù)類樣本集為A-)

本文使用的是核函數(shù)為: 高斯核函數(shù)(RBF)

第一步: 在多數(shù)類樣本集A-上, 通過欠采樣獲得一個新的樣本集1newA. 首先, 如果A-和A+比例超過了2, 對多數(shù)類樣本集A-進行欠采樣, 得到一個新的多數(shù)類樣本集A-new1, (保持A-new1和A+比例為2)那么,新的樣本集Anew1=A+∪A-new1. 那么A-和 A+中心的距離表示為: 根據(jù)公式(2), A+的中心表示為:

其中x+i是A+中的一個樣本. 通過公式(1), A-中的一個樣本x-i和A+的中心c+距離為:

第二步: 對于經(jīng)過欠采樣處理的樣本集Anew1, 通過使用SMO算法對其進行訓(xùn)練[15],從而的得到一個訓(xùn)練模型M1, 即得到一個分類器(分類函數(shù)), 如2.1所講

第三步: 通過使用得到的模型(分類器)M1對測試集B進行分類, 測試樣本的分類結(jié)果為B+(和A+標(biāo)記一樣, 為少數(shù)類), B-(和A-的標(biāo)記一樣, 為多數(shù)類)

第四步: 獲得新的訓(xùn)練樣本集Anew2. 首先, 往A+添加B+, 于是我們就可以得到一個新的少數(shù)類樣本集A+new2, 那么A+new2=A+∪B+. 接下來, 通過對少數(shù)類樣本集A-進行向下采樣得到一個新的樣本集A-new2(保證A-new2和A+new2的比率為2), 那么Anew2=A+new2∪A-new2, 向下采樣的方法和第一步相同.

第五步: 通過SMO算法對新得到的樣本集Anew2進行訓(xùn)練, 從而得到一個新的訓(xùn)練模型M2, 即得到一個新的分類器.

第六步: 利用這新得到的模型M2對測試集進行分類.

4 實驗結(jié)果

大多數(shù)不平衡學(xué)習(xí)的研究更關(guān)注兩個類別, 因為多分類問題可以簡化為兩類. 根據(jù)慣例, 少數(shù)樣本被標(biāo)記為正類, 而大多數(shù)樣本被標(biāo)記為負(fù)類. 通常應(yīng)用兩個評價標(biāo)準(zhǔn), 準(zhǔn)確率, 召回率[16], 評估不平衡數(shù)據(jù)集上的分類. 他們描述如下:

TP(真正類), TN(真負(fù)類), 分別代表正類和負(fù)類樣本的數(shù)量要正確分類的次數(shù). FN(假負(fù)類), FP(假正類),分別代表被錯誤分類的樣本數(shù). 他們描述如下. 表1代表著兩類矩陣.

表1 兩類矩陣

為了測試Under-sampling-SVM算法的性能, 我們將該算法應(yīng)用到網(wǎng)頁分類. 我們比較Under-sampling -SVM算法下采樣對不平衡數(shù)據(jù)集傳統(tǒng)的SVM算法和隨機抽樣SVM. 所有的算法都是在用libsvm-3.1工具包進行. 三種算法的簡單描述如下:

傳統(tǒng)SVM: 在支持向量機訓(xùn)練之前沒有任何操作.

隨機抽樣SVM: 在該算法中, 一些訓(xùn)練樣本被隨機刪除之前, 支持向量機訓(xùn)練.

Under-sampling-SVM: 該算法不僅消除了一些樣品(非支持向量)的基礎(chǔ)上的距離, 也提高了少數(shù)類反饋機制.

在這實驗中, 我們使用了四種不同的UCI數(shù)據(jù)集[17], 包括 Iris, Abalone, Balance Scale and Yeast數(shù)據(jù)集. 在四個UCI數(shù)據(jù)集, 一種是選擇作為一個少數(shù)類和其余類型分為多數(shù)類. 每個數(shù)據(jù)集被隨機分為訓(xùn)練集和測試集. 還我們給他們不同的不平衡比(少數(shù)類與多數(shù)類的比率), 描述4個數(shù)據(jù)集具體況如表2所示.

表2 數(shù)據(jù)集詳情

UCI數(shù)據(jù)集的向量形式是矩陣形式. 所以, 在我們的實驗之前, 我們應(yīng)該先格式化樣本集. 樣品的格式如下: ＜label＞ ＜value1＞ ＜value2＞….這里在這里, 標(biāo)簽是網(wǎng)頁類別, 值是特征權(quán)重. 預(yù)處理后, UCI數(shù)據(jù)集轉(zhuǎn)成到矢量格式. 然后, 我們使用這兩種算法來做的學(xué)習(xí). 實驗的結(jié)果如下.

(1) 傳統(tǒng)支持向量機算法的實驗結(jié)果如表3所示.

表3 傳統(tǒng)SVM算法實驗結(jié)果

(2) 隨機抽樣SVM 算法等結(jié)果如表4所示.

表4 隨機抽樣SVM算法實驗結(jié)果

(3) Under-sampling-SVM 算法等結(jié)果如表5所示.

表5 Under-sampling –SVM實驗結(jié)果

從上表的實驗結(jié)果, 我們可以看到, 從訓(xùn)練時間上Under-sampling-SVM比隨機采樣VM算法的時間較長, 但短于傳統(tǒng)的支持向量機. 從少數(shù)類別的查準(zhǔn)率和查全率來看, Under-sampling-SVM算法具有更優(yōu)秀的表現(xiàn), 原因是經(jīng)過欠采樣, 改善了超平面的位置. Under-sampling-SVM算法比隨機采樣SVM具有更好的表現(xiàn)原因是, Under-sampling-SVM算法通過反饋機制改善了超平面位置.

5 不平衡SVM網(wǎng)頁分類分類系統(tǒng)實現(xiàn)

5.1 實驗環(huán)境

本文所設(shè)計的網(wǎng)頁分類系統(tǒng)是在visual studio 2010編程工具基礎(chǔ)上開發(fā)的, C++設(shè)計語言具備結(jié)構(gòu)化控制語句, 程序的執(zhí)行效率高, 而且C++語言還具有匯編語言的優(yōu)點, 并支持C語言.

5.2 不平衡SVM網(wǎng)頁分類系統(tǒng)框架

本文設(shè)計的不平衡網(wǎng)頁分類系統(tǒng)框架如圖2所示.

圖2 網(wǎng)頁分類流程

5.2.1 網(wǎng)頁預(yù)處理子系統(tǒng)

網(wǎng)頁預(yù)處理主要包括3個步驟:

第一步: 網(wǎng)頁去噪, 因為分類系統(tǒng)處理的對象主要是web頁面, 但是頁面中含有的元素豐富, 像文本,圖像, 音樂, 動態(tài)圖片, 視頻, 以及html標(biāo)簽, 這些因素會干擾我們處理信息. 經(jīng)過大量的研究發(fā)現(xiàn)HTML的網(wǎng)頁大多具有相同的格式, 如圖3所示.

圖3 HTML DOM樹

所以本文的去噪方法主要是, 去掉網(wǎng)頁中的“script”, “image”, “style”, “form”, “iframe”等標(biāo)簽.

第二步: 相關(guān)信息的提取主要是提取的TD標(biāo)簽,表標(biāo)簽, div標(biāo)簽的里的信息和相關(guān)鏈接的信息, 在這個時候只有去除對分類的貢獻沒有HTML標(biāo)簽, 保留中文字符即可.

第三步: 對提取好的有用信息, 進行中文分詞,本文采用的是中科院分詞軟件(ICTCLA).

5.2.2 預(yù)處理子系統(tǒng)

在經(jīng)過對原始網(wǎng)頁樣本集進行凈化之后, 這些網(wǎng)頁就被變成了分類系統(tǒng)能識別的樣本, 訓(xùn)練的過程用這測試數(shù)據(jù)得帶基于欠采樣不平衡SVM分類的初始模型,不平衡SVM數(shù)據(jù)預(yù)處理子系統(tǒng)的過程如圖4所示.

圖4 預(yù)處理子系統(tǒng)流程

5.2.1 分類子系統(tǒng)

在經(jīng)過預(yù)處子系統(tǒng)處理過之后, 得到一個不平衡SVM模型, 接下來用設(shè)計好的分類子系統(tǒng)對網(wǎng)頁進行分類判斷, 主要的過程如圖5所示.

圖5 分類子系統(tǒng)流程

5.3 不平衡SVM網(wǎng)頁分類系統(tǒng)界面以及運行結(jié)果本文設(shè)計的系統(tǒng)的主界面圖6所示.

圖6 系統(tǒng)的主界面

第一步. 先將本地的測試數(shù)據(jù)集讀取到該系統(tǒng)中, 在點擊界面中的“選擇本地樣本集”, 如圖7所示.

圖7 分類系統(tǒng)選取不平衡測試集界面

第二步. 按“訓(xùn)練分類器”按鈕, 此時該分類系統(tǒng)變會對本地的樣本集進行訓(xùn)練, 經(jīng)過訓(xùn)練之后, 分類器系統(tǒng)會把樣本訓(xùn)練集進行提取, 之后得到本地樣本集的特征.

第三步. 訓(xùn)練結(jié)段結(jié)束后, 點擊“測試分類器”按鈕,接下來, 該系統(tǒng)會顯示分類效果的界面, 如圖8所示.

圖8 系統(tǒng)分類結(jié)果圖

該系統(tǒng)還有一個特點, 當(dāng)你點擊其中一個主題是時, 該體統(tǒng)會彈出一個界面, 上面顯示著網(wǎng)頁的具體信息, 像網(wǎng)頁的大小、類別, 如圖9所示.

圖9 系統(tǒng)的主界面

內(nèi)存占用小、運行穩(wěn)定, 分類精度高等優(yōu)點, 具有較強的實用價值.

第四步: 接下來點擊”分類器評測”按鈕, 該系統(tǒng)評測界面, 該頁面主要包括查準(zhǔn)率和查全率這兩大標(biāo)準(zhǔn).

圖10 分類系統(tǒng)的評測結(jié)果

1 Priore P, Parreno J, Pino R, et al. Learning-based scheduling of flexible manufacturing systems using support vector machines. Applied Artificial Intelligence, 2010, 24(3): 194–209

2劉蘇蘇,丁福利,孫立民.優(yōu)化支持向量機核參數(shù)的核矩陣方法研究.煙臺大學(xué)學(xué)報(自然科學(xué)與工程版),2013, 26(2):131–135.

3韓芳,孫立民.不平衡樣本集分類算法研究.計算機應(yīng)用研究, 2015,32(8):2323–2325.

4楊智明.面向不平衡數(shù)據(jù)的支持向量機分類方法研究[博士學(xué)位論文].哈爾濱:哈爾濱工業(yè)大學(xué),2009.

5丁福利,孫立民.基于支持向量機的不平衡樣本分類研究.科學(xué)技術(shù)與工程,2014,14(3):81–85.

6劉蘇蘇,孫立民.支持向量機與RBF神經(jīng)網(wǎng)絡(luò)回歸性能比較研究.計算機工程與設(shè)計,2012,32(12):4202–4205.

7 Vapnik VN. The nature of statistical learning theory. IEEE Trans. on Neural Networks, 1995, 8(6): 1564–1564.

8李瓊,陳利.一種改進的支持向量機文本分類方法.計算機技術(shù)與發(fā)展,2015,(5):78–82.

9 Joachims T. Making large-scale SVM learning practial. Advances in Kernel Methods-Support Vector Learning, MIT Press, 1999.

10 Platt JC. Sequential minimal optimization: A fast algorithm for training support vector machines. Advances in Kernel Methods-Support Vector Learning, 1998: 212–223.

11柴巖,王慶菊.基于邊界向量的樣本取樣SMO算法.系統(tǒng)工程,2015,(6):142–145.

12 Hwang JP, Park S, Kim E. A new weighted approach to imbalanced data classification problem via support vector machine with quadratic cost function. Expert Systems with Applications, 2011, 38: 8580–8585.

13 Liu Y, Yu XH, Huang JX, An A. Combining integrated sampling with SVM ensembles for learning from imbalanced datasets. Information Processing and Management, 2011, 47: 617–631.

14 Dendamrongvit S, Kubat M. Undersampling approach for imbalanced training sets and induction from multi-label text-categorization domains. New Frontiers in Applied Data Mining, 2010, 5669: 40–52.

15曾一平.中文文本情感分類的研究[碩士學(xué)位論文].北京:北京交通大學(xué),2011.

16余桂蘭,陳珂,左敬龍.基于云模型的并行蟻群-SVM分類方法.計算機技術(shù)與發(fā)展,2014,(4):131–134.

17 Frank A, Asuncion A. UCI machine learning repository. Irvine. CA: University of California, School of Information and Computer Science, 2010.

Realization of Web Page Classificationn System Based on Under-Sampling Support Vector Machine

LI Cun-He, TANG Lei
(College of Computer and Communication Engineering, China University of Petroleum, Qingdao 266580, China)

In this era of information explosion, how to handle these vast amounts of data and how to classify the data effectively has attracted much attention, especially in the stage of rapid development of Internet technology free, the field of web classification has become a hot spot. Compared with the traditional classification methods, support vector machine has the characters of high-dimensional, small sample size, strong adaptability, and can be very effective to solve the problem of web page classification. But in the field of classification of imbalanced data, there is a problem of inaccurate classification. Therefore, this paper proposes a new strategy to solve the imbalance data samples, that is, combining the under-sampling strategy with the traditional support vector machines to increase the number of samples set in the minority class and to reduce the concentrated noise data in the majority class, so that imbalanced sample set tends to be balanced. Finally SMO algorithm is used to improve the accuracy of classification.

support vector machine; SMO algorithm; reduction in the training set; classification of web page; multi-class classification

2016-07-09;收到修改稿時間:2016-08-08

10.15888/j.cnki.csa.005671