基于聚類分類法的信息過濾技術(shù)研究

李全鑫，魏海平

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

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

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

1 相關(guān)技術(shù)介紹

1.1 支持向量機

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

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

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

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

1.2 聚類分類法

聚類分類法（CLC）的參數(shù)選擇及使用相當?shù)暮唵?。在其它相關(guān)領(lǐng)域的應(yīng)用中，CLC已有相當不錯的表現(xiàn)，本研究將CLC應(yīng)用于信息過濾，并且跟SVM進行準確度的比較。

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

訓(xùn)練階段

1）設(shè)定聚類的數(shù)量k等于類別的數(shù)量；

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

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

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

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

預(yù)測階段

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

2）找出與測試數(shù)據(jù)最相似的支持向量，而此支持向量的類別信息就是預(yù)測的結(jié)果。

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

2 信息過濾架構(gòu)模型

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

圖1 信息過濾架構(gòu)模型圖Fig.1 Diagram of information filter model architecture

本研究的基本架構(gòu)模型建立的步驟如下：

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

2）網(wǎng)頁內(nèi)容轉(zhuǎn)換：將每一個網(wǎng)頁內(nèi)容轉(zhuǎn)換成向量，而網(wǎng)頁內(nèi)容中文字出現(xiàn)的次數(shù)則是每一個向量中的分量。這些分量即是每個網(wǎng)頁的特征值；

3）網(wǎng)頁特征選?。捍瞬襟E將由步驟2）的輸出結(jié)果中，挑選出與網(wǎng)頁類別相關(guān)性較高的特征來作為SVM及CLC產(chǎn)生訓(xùn)練模型的依據(jù)。在特征選擇法方面，使用的是互動信息多項式模型（MI Multinomial Model），該模型是由互動信息（MI）發(fā)展而來的，特征值數(shù)量為500時對分類法可以有較高的準確度；

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

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

3 實驗與分析

3.1 實驗環(huán)境

本實驗在Windows 2008操作系統(tǒng)、2G內(nèi)存、1.6GHz雙核CPU環(huán)境下進行，從網(wǎng)絡(luò)上搜集500個網(wǎng)頁（合法400份，非法100份）進行前期的訓(xùn)練[6]。

3.2 實驗過程設(shè)計

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

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

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

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

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

表2 CLC的參數(shù)Tab.2 The parameters of CLC

3.3 結(jié)果與分析

在SVM中使用Linear核心函數(shù)對合法及非法網(wǎng)頁的實驗結(jié)果如圖2所示。

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

在SVM中使用Polynomial核心函數(shù)對合法及非法網(wǎng)頁的實驗結(jié)果如圖3所示。

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

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

在SVM中使用RBF核心函數(shù)對合法及非法網(wǎng)頁的實驗結(jié)果如圖4所示。

圖中Y軸表示準確度，X軸表示RBF核心函數(shù)的參數(shù)值?？梢钥闯鯯VM使用RBF核心函數(shù)進行信息過濾的實驗時，得到的準確度也呈現(xiàn)上下震蕩的情況。結(jié)果表示，假使RBF核心函數(shù)使用了不適合的參數(shù)，得到的準確度也會非常的低。要得到滿意的結(jié)果，還是要經(jīng)過多次的測試。

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

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

利用CLC方法對合法及非法網(wǎng)頁的實驗結(jié)果如圖5所示。

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

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

4 結(jié)論

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

[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]黃曉斌.網(wǎng)絡(luò)信息過濾原理與應(yīng)用[M].北京:北京圖書館出版社,2005.

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