基于欠采樣支持向量機不平衡的網頁分類系統①

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

基于欠采樣支持向量機不平衡的網頁分類系統①

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

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

支持向量機; SMO算法; 訓練集縮減算法; 網頁分類; 多類分類

1 引言

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

2 相關技術

2.1 支持向量機

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

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

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

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

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

解如下問題:

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

相應的分類器為:

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

2.2 SMO算法

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

3 基于欠采樣不平衡SVM算法實現

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

下面是算法的定義:

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

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

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

圖1 不平衡訓練樣本集表現

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

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

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

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

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

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

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

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

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

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

4 實驗結果

大多數不平衡學習的研究更關注兩個類別, 因為多分類問題可以簡化為兩類. 根據慣例, 少數樣本被標記為正類, 而大多數樣本被標記為負類. 通常應用兩個評價標準, 準確率, 召回率[16], 評估不平衡數據集上的分類. 他們描述如下:

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

表1 兩類矩陣

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

傳統SVM: 在支持向量機訓練之前沒有任何操作.

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

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

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

表2 數據集詳情

UCI數據集的向量形式是矩陣形式. 所以, 在我們的實驗之前, 我們應該先格式化樣本集. 樣品的格式如下: ＜label＞ ＜value1＞ ＜value2＞….這里在這里, 標簽是網頁類別, 值是特征權重. 預處理后, UCI數據集轉成到矢量格式. 然后, 我們使用這兩種算法來做的學習. 實驗的結果如下.

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

表3 傳統SVM算法實驗結果

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

表4 隨機抽樣SVM算法實驗結果

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

表5 Under-sampling –SVM實驗結果

從上表的實驗結果, 我們可以看到, 從訓練時間上Under-sampling-SVM比隨機采樣VM算法的時間較長, 但短于傳統的支持向量機. 從少數類別的查準率和查全率來看, Under-sampling-SVM算法具有更優秀的表現, 原因是經過欠采樣, 改善了超平面的位置. Under-sampling-SVM算法比隨機采樣SVM具有更好的表現原因是, Under-sampling-SVM算法通過反饋機制改善了超平面位置.

5 不平衡SVM網頁分類分類系統實現

5.1 實驗環境

本文所設計的網頁分類系統是在visual studio 2010編程工具基礎上開發的, C++設計語言具備結構化控制語句, 程序的執行效率高, 而且C++語言還具有匯編語言的優點, 并支持C語言.

5.2 不平衡SVM網頁分類系統框架

本文設計的不平衡網頁分類系統框架如圖2所示.

圖2 網頁分類流程

5.2.1 網頁預處理子系統

網頁預處理主要包括3個步驟:

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

圖3 HTML DOM樹

所以本文的去噪方法主要是, 去掉網頁中的“script”, “image”, “style”, “form”, “iframe”等標簽.

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

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

5.2.2 預處理子系統

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

圖4 預處理子系統流程

5.2.1 分類子系統

在經過預處子系統處理過之后, 得到一個不平衡SVM模型, 接下來用設計好的分類子系統對網頁進行分類判斷, 主要的過程如圖5所示.

圖5 分類子系統流程

5.3 不平衡SVM網頁分類系統界面以及運行結果本文設計的系統的主界面圖6所示.

圖6 系統的主界面

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

圖7 分類系統選取不平衡測試集界面

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

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

圖8 系統分類結果圖

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

圖9 系統的主界面

內存占用小、運行穩定, 分類精度高等優點, 具有較強的實用價值.

第四步: 接下來點擊”分類器評測”按鈕, 該系統評測界面, 該頁面主要包括查準率和查全率這兩大標準.

圖10 分類系統的評測結果

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劉蘇蘇,丁福利,孫立民.優化支持向量機核參數的核矩陣方法研究.煙臺大學學報(自然科學與工程版),2013, 26(2):131–135.

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

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

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

6劉蘇蘇,孫立民.支持向量機與RBF神經網絡回歸性能比較研究.計算機工程與設計,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李瓊,陳利.一種改進的支持向量機文本分類方法.計算機技術與發展,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算法.系統工程,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曾一平.中文文本情感分類的研究[碩士學位論文].北京:北京交通大學,2011.

16余桂蘭,陳珂,左敬龍.基于云模型的并行蟻群-SVM分類方法.計算機技術與發展,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