基于聚類分類法的信息過濾技術研究

李全鑫，魏海平

（遼寧石油化工大學 計算機與通信工程學院，遼寧 撫順113001）

隨著互聯網的蓬勃發展與普及Web憑借其方便、快速、低成本的特性成為企業及個人不可或缺的信息發布工具。當Web帶給人們極大便利的同時，卻也產生出負面的嚴重問題，那就是我們每天瀏覽的Web頁面中含有推銷廣告或是一些有害的不良信息，甚至還有病毒，加劇了計算機病毒、網絡詐騙、色情犯罪的傳播與信息安全方面的問題。面對不良信息Web頁面日益嚴重的情況，如何對信息進行分類過濾已是非常重要的問題。

本研究在研究分類算法的基礎上，提出了一個簡單且方便且易于理解適用于文本信息過濾的方法。

1 相關技術介紹

1.1 支持向量機

支持向量機（support vector machine，簡稱 SVM）是以統計學習理論為基礎發展而來的機器學習系統。其核心思想是尋找兩個類別之間進行優化分隔的超平面（Separating Hyper-Plane），也就是尋找該超平面與兩類數據間的最大邊界（Maximized Margin）[1]。SVM 的另一個特點是可以通過不同的核心函數（Kernel Function），將訓練數據映射到不同的高維度空間，來處理線性不可分的情形。

SVM利用已知類別的數據進行訓練，并從這些訓練數據（Training Data）之中，選出一些支持向量（Support Vectors）來代表整體的數據，之后再產生一個訓練模型（Training Model）,這一個訓練模型將被作為后續預測數據類別的依據。由于隨著時間及空間的變化，Web內容的差異也變很大，因此網頁的信息分布難以事先了解，所以無法決定采用哪個SVM核心函數。大部分研究人員都是采用嘗試法來選擇合適的核心函數及相對應參數,因此需要花費漫長的時間，且無法保證可以得到相關參數的最佳值[2]。

在現實的信息過濾中，所面對的頁面內容是隨時變動的，其特征值也會經常改變。當使用機器進行學習時，必須經常的再訓練（Re-train）才能維持較高的準確度，同時，用于機器學習的參數選擇必須合適，這樣所得分類器的再訓練才能有高的準確度。

因此，我們希望設計一種可以適合于現實中信息過濾的方法，不用在乎信息集的習性、特征的選擇、機器學習核心及參數的選定，一樣可以很高的準確度[3]。下面將引入聚類分類法（Clustering Launched Classification，CLC）應用于信息過濾。

1.2 聚類分類法

聚類分類法（CLC）的參數選擇及使用相當的簡單。在其它相關領域的應用中，CLC已有相當不錯的表現，本研究將CLC應用于信息過濾，并且跟SVM進行準確度的比較。

CLC在訓練階段以K-means分群算法將訓練數據分群，并增加聚類的數量，直到每一個聚類中大部分數據屬于相同的類為止。然后再去計算聚類數據間的相似度，以找出聚類間相似度最高的數據，這些數據被稱為支援向量[4]。CLC方法的運行步驟如下所示：

訓練階段

1）設定聚類的數量k等于類別的數量；

2)采用K-means分群算法，將訓練集中的數據Xi，i=1，2，3，…，n，分成 k 個聚類 Ck，k=1，2，3，…，n；

3)在每個聚類 Ck，單一類別的數據數量/總數據數量＜參數 t，則 k=k+1，并返回執行步驟 2），此處的參數 t由用戶設定；

4)將聚類Ck中，數據數量最多的類別留下，其余類別的數據則視為噪聲刪除；

5)在每一個聚類中，尋找每一個訓練數據在每一個不同類別的最近鄰居，稱為支持向量，并以所有的支持向量組成CLC的訓練模型。

預測階段

1）計算測試數據和所有支持向量間的相似度；

2）找出與測試數據最相似的支持向量，而此支持向量的類別信息就是預測的結果。

由以上述步驟可以知道，CLC在訓練階段已經將大量的輸入數據轉換成少量的支持向量，從而在測試階段能夠迅速地完成預測結果。當使用者操作CLC時，只需要設定一個參數t，而且其預測結果對于參數值的大小并不敏感，因此相當容易使用。

2 信息過濾架構模型

本研究所設計的信息過濾架構模型如圖1所示，共包含了信息過濾研究過程所需的3個處理步驟[5]。

圖1 信息過濾架構模型圖Fig.1 Diagram of information filter model architecture

本研究的基本架構模型建立的步驟如下：

1）數據前置處理：此步驟屬于信息文本的前置操作，首先去除不需要的信息數據，例如：照片、HTML程序代碼等。本研究使用的信息文本已經將前置處理完成；

2）網頁內容轉換：將每一個網頁內容轉換成向量，而網頁內容中文字出現的次數則是每一個向量中的分量。這些分量即是每個網頁的特征值；

3）網頁特征選取：此步驟將由步驟2）的輸出結果中，挑選出與網頁類別相關性較高的特征來作為SVM及CLC產生訓練模型的依據。在特征選擇法方面，使用的是互動信息多項式模型（MI Multinomial Model），該模型是由互動信息（MI）發展而來的，特征值數量為500時對分類法可以有較高的準確度；

4)數據分類：本研究使用SVM及CLC進行信息過濾準確度的比較。SVM將選擇不同的核心函數及相對應參數來測試。CLC也將針對單一參數，進行參數值的測試；

5)分類準確度驗證：對信息過濾的準確度進行驗證和評估。

3 實驗與分析

3.1 實驗環境

本實驗在Windows 2008操作系統、2G內存、1.6GHz雙核CPU環境下進行，從網絡上搜集500個網頁（合法400份，非法100份）進行前期的訓練[6]。

3.2 實驗過程設計

本研究將采用CLC，并與SVM在信息過濾的所得結果進行準確度的驗證評估。實驗數據使用戶互動信息多項式模型為特征選擇方法，所產生的訓練數據的特征值數量為500。表1所列出的是SVM在本實驗中所使用的參數。

表1 SVM使用的核心函數和參數Tab.1 Corefunctions and parameters used SVM

由上表可知，3種核心函數都使用了SVM的懲罰函數C，C為大于 0的實數。參數 d（Degree）是 Polynomial核心函數的指數值，必須是大于1的實數。參數g（Gamma）則是RBF核心函數中的系數，可以改變向量相減后的數值大小，該參數必須為大于0的實數。

本文在SVM實驗中，采用較常見的Linear、Polynomial及RBF核心函數，以間隔遞增方式選取SVM各個核心函數的相關參數值。對于核心函數及其相關參數值的選取，并沒有經過特別的演算法去調整及選擇。由于選用的SVM的核心函數有3種，因此以3種核心函數及其相對應參數相互搭配，分別可以如表1所示的實驗參數組合。

由于訓練數據的類別只有兩種，因此CLC分類過程所產生的每一個聚類中，其單一類別數據數量超過全部數量50%（t值）時，該聚類就不再分裂。完成分類步驟之后，從每一個生成的聚類中取出數據數量較多的那一個類別，作為該聚類的代表類別。在本研究實驗中，由于CLC所需要設定的唯一參數t，且最大值為1。這里設定CLC的參數值t從0.5開始遞增，而每一個參數值間隔0.05，總共可以得到11組，如表格2所示。

表2 CLC的參數Tab.2 The parameters of CLC

3.3 結果與分析

在SVM中使用Linear核心函數對合法及非法網頁的實驗結果如圖2所示。

圖中Y軸表示準確度，X軸表示 Linear核心函數的參數值。可以看出SVM使用Linear核心函數進行信息過濾的實驗時，一開始得到的準確度非常的低；當懲罰C>0.01后，才能獲得比較高的準確度。在非法頁面的實驗中，最高與最低的準確度相差14%；而在合法頁面的實驗中也相差40%。由此可知，SVM使用Linear核心函數所得到的準確度，會隨著參數的變化而呈現較大的差異，穩定程度不高。

在SVM中使用Polynomial核心函數對合法及非法網頁的實驗結果如圖3所示。

圖3 實驗二：Polynomial核心函數實驗Fig.3 Diagram of experiment 2

圖中Y軸表示準確度，X軸表示Polynomial核心函數的參數值。可以看出SVM使用 Polynomial核心函數進行信息過濾的實驗時，得到的準確度呈現上下震蕩的情況。在合法頁面的實驗中，當參數d為4所得到的準確度最低。在非法頁面的實驗中，當參數d為3時所得到準確度最低。由此可見準確度對于參數d及懲罰參數C值的變化非常的敏感；要選出能獲得高準確度的參數組合，非常困難。如果選擇的參數不合適，其所得到的準確度將會非常的低，只能以大?的參數組合來測試。

在SVM中使用RBF核心函數對合法及非法網頁的實驗結果如圖4所示。

圖中Y軸表示準確度，X軸表示RBF核心函數的參數值。可以看出SVM使用RBF核心函數進行信息過濾的實驗時，得到的準確度也呈現上下震蕩的情況。結果表示，假使RBF核心函數使用了不適合的參數，得到的準確度也會非常的低。要得到滿意的結果，還是要經過多次的測試。

圖4 實驗三：RBF核心函數實驗Fig.4 Diagram of experiment 3

綜上所述，SVM的準確度對于參數的選值非常敏感，因此用戶很難獲得適合的參數。對于經常改變內容的網頁內容來說，過濾器的訓練模型必須經常進行再訓練（Re-train）才能獲得信息過濾的高準確度，需要花費相當漫長的時間，SVM并不是一種優秀的過濾方法。

利用CLC方法對合法及非法網頁的實驗結果如圖5所示。

圖5 實驗四：CLC方法實驗Fig.5 Diagram of experiment 4

從上圖可知，使用CLC進行信息過濾的實驗中，不同的參數值t對準確度的結果并沒有很明顯的影響。非法頁面的實驗結果顯示，CLC最高與最低準確?的浮動范圍只有2.1%，而合法頁面的實驗結果顯示，CLC最高與最低準確度的浮動范圍也只有2.4%。實驗表明，CLC的準確度對于參數的變化并不敏感，使用CLC進行信息過濾，操作過程簡單而且能夠得到穩定的準確度，比SVM更適合作為信息過濾器。

4 結論

分類算法在圖形識別、文本信息識別等領域具有廣泛的應用。本文研究了一種基于聚類分類法實現信息過濾的技術，詳細介紹了把算法的主要思想，并說明了過濾架構模型和實現的過程。通過實驗表明，該方法是是實現信息過濾的實用工具。將該方法進行動態軟件化是未來的研究方向。

[1]Begg R K,Palaniswami M,Owen B,Support Vector Machines for Automated Gait Classification[C]//IEEE Transactions on Biomedical Engineering,2005:828-838.

[2]Kim D S,Nguyen H,Park J S.Genetic Algorithm to Improve.SVM Based Network Intrusion Detection System[C]//.Proc of the 19th International Conference on Advanced Information Networking and Applications,2005:155-158.

[3]Hammamii M,Chahir Y,Chen L.Web guard:A web filtering engine combining textual,structural,and visual content based analysis [J].IEEE Transactions on Knowledge and Data Engineering,2006,8（2）:272-284.

[4]Chen T S,Lin C C,Chiu Y H,et al.A NewBinary Classifier:Clustering Launched Classification[C]//.Proc of International Conference on Lecture Notes in Artificial Intelligence,2005:278-283.

[5]黃曉斌.網絡信息過濾原理與應用[M].北京:北京圖書館出版社,2005.

[6]中國互聯網違法和不良信息舉報情況公告[EB/OL].[2013-09-13].http://net.china.com.cn/jbqk/node_5957.h-tm.