改進樣本加權K近鄰分類器用于垃圾網頁檢測

吳俊華，譚博覺，高 切，陳木生

（江西理工大學 軟件工程學院，南昌 330013）

搜索引擎已成為人們上網查找資料最常用的工具。CNNIC2019年3月發布的報告稱［1］：截止2018年底，中國網民中使用搜索引擎的用戶規模達6.81億，占全體網民的82.2%，年增長率6.5%。研究表明：85%的搜索引擎用戶只查看返回搜索結果中第1頁的內容［2－3］。這就意味著檢索結果靠前的網站會有更高的關注度、點擊率、訪問量以及由此帶來的更好的廣告收入。于是，各個網站使用搜索引擎優化方法（search engine optimization，SEO）提高自身的排名。然而，通過提升自身價值的方式提高排名非常困難，于是有些網站通過欺騙搜索引擎的不正當手段獲得較高的排名［4］。這種行為稱為網頁作弊（web spamming），這些網頁就是作弊網頁，也稱為垃圾網頁（web spam）。垃圾網頁不僅降低了搜索質量和用戶的信任度，讓用戶轉向其他搜索引擎，而且浪費了大量的計算和存儲資源，侵占了搜索引擎公司及其他內容網站的合法利益［5］。

垃圾網頁檢測至今依然是對抗信息檢索領域的一項極具挑戰性的重要工作。常見的做法是將其視為一個二分類問題，提出各種有效的分類算法用于垃圾網頁檢測。文獻［6］采用支持向量機（support vector machine，SVM）、多層感知器（mulitple level perception，MLP）、貝葉斯網絡（bayesian network，BN）、C4.5決策樹（C4.5 decision tree，DT）、隨機森林（random forest，RF）、樸素貝葉斯（na?ve bayes，NB）、K最近鄰（K-nearest neighbour，KNN）以 及AdaBoost、LogitBoost、Real AdaBoost、Bagging、Dagging和Rotation Forest等分類算法分別基于內容特征、鏈接特征和綜合特征進行垃圾網頁檢測，但其分類結果與其他研究結果相比并非更優。文獻［7］提出一種包含概率映射圖自組織映射（probabilistic mapping graph self-organizing map，PM-G）和圖神經網絡（graph neural network，GNN）的圖層疊架構用于垃圾網頁檢測，其中的FNN（feedforward neural network）、PM-G＋GNN（3）＋GNN（1）算法表現出較好的檢測效果，準確率和AUC等指標都達到當時的最優水平，但其F1-測度指標卻偏低。文獻［8－9］提出一種垃圾網頁檢測框架WSF2，該框架集成了多種分類器，與C5.0、REGEX、SVM、Bayes等方法相比，其AUC指標更優。支持向量機在垃圾網頁檢測的研究也多有出現，一般都采用改進支持向量機［10］、加入新的特征［11］和組合其他智能優化算法［12］等。這些方法雖然改善了支持向量機的分類性能，但與其他最優結果相比，在垃圾網頁檢測領域沒有明顯優勢。由此可見，僅對傳統分類算法加以改進用于垃圾網頁檢測，效果提升并不明顯。這主要是由于垃圾網頁檢測存在兩大難題。首先，垃圾網頁檢測是一個不平衡數據分類問題，因為互聯網中正常網頁與垃圾網頁相比是不平衡的，垃圾網頁僅占10%～15%［4］。其次，用于垃圾網頁檢測的數據集可以從網頁的內容（content）、超級鏈接（hyperlink）和搜索引擎用戶使用信息（usage log）等3個方面提取大量特征，將這眾多的特征同時用于訓練機器學習模型可能陷入“維數災難”問題。為解決垃圾網頁檢測中的不平衡數據分類和可能存在的“維數災難”問題。文獻［13］最早將集成學習算法用于解決垃圾網頁檢測的不平衡分類問題，其提出的基于欠采樣的C4.5集成決策樹分類器的分類性能獲得當年垃圾網頁挑戰競賽的冠軍。文獻［14］則采用過采樣和隨機森林相結合的技術進行垃圾網頁檢測，同樣獲得較好的分類性能。文獻［15］提出一種傳感－感應圖神經網絡（transductive-inductive graph neural networks，TIGNN）方法。文獻［16］提出一種融合人工免疫克隆選擇、欠采樣集成和C4.5決策樹的分類方法，用于垃圾網頁檢測，較好地解決了上述問題。但這些方法需要花費大量時間訓練出模型參數，才能得到較滿意的結果。

本文中提出一種融合Fisher特征選擇和實例加權的K近鄰（K nearest neighbor with instance weighting，KNN-IW）分類方法用于垃圾網頁檢測，不需要花費太多時間訓練模型參數，同樣可以取得理想的效果。

1 理論基礎

1.1 Fisher特征選擇

特征選擇是從一組特征中挑選出一些最有效的特征以降低特征空間維數的過程，是避免“維數災難”的常用方法。依據是否獨立于后續的學習算法分，特征選擇方法可分為過濾式（filter）方法和封裝式（wrapper）方法2種［17］。Fisher準則是一種常見且有效的過濾式特征選擇方法，其主要思想是：若一個特征具有鑒別能力，則該特征表現為類內距離盡可能小，類間距離盡可能大。在歐氏空間中，可以用方差表達樣本之間的距離。方差越大，樣本之間的距離越大；方差越小，樣本之間的距離越小［18］。

假設數據集中共有d種特征n個樣本屬于c個類w1，w2，…，wc，每一類分別包含nk個樣本，fj表示第j個特征，xi（fj）表示第i個樣本x在第j個特征上的取值，則Δb（fj）、Δw（fj）分別表示第j個特征的類間方差、類內方差，其計算分別見式（1）（2）。

其中：μ（fj）表示所有樣本在第j個特征上的期望值；μk（fj）表示第k類樣本在第j個特征上的期望值。

將Fisher Score定義為某一特征的類間方差與類內方差的比值，如式（3）所示。

將式（1）（2）代入式（3）并化簡得到Fisher Score的計算公式如式（4）所示。

某個特征在訓練樣本集上的Fisher Score越大說明該特征的類別區分度越好，即包含更多的鑒別信息，而噪聲特征的Fisher Score趨近于0。對每一個特征的Fisher Score進行排序，即可選出那些鑒別能力較強的特征，從而達到降維的目的，且具有較優的識別性能。利用Fisher Score進行特征選擇的通常做法是：先求出每個特征的Fisher Score，然后設定一個閾值θ，如果某特征的Fisher Score大于θ則保留，否則放棄。

1.2 樣本加權的K近鄰分類

K近鄰（K nearest neighbor，KNN）法最早由Cover和Hart于1968年提出［19］。K近鄰分類對于訓練數據集的平衡性較敏感，即對不平衡數據分類性能較差。解決不平衡數據分類問題的常用方法有重采樣［20］（包括欠采樣和過采樣）、代價敏感分析［21］和核分類器［22］等。欠采樣方法會浪費大量多數類樣本，過采樣方法則會使樣本數增加。隨著樣本數的增加，K近鄰分類器的比較計算量也會急劇增加，導致運行性能下降。K近鄰法一般不會結合核函數一起使用。因此，結合代價敏感分析的K近鄰分類器較為常見。

劉胥影等［23］提出一種代價敏感的K近鄰分類器，命名為樣本加權的K近鄰方法（K nearest neighbor with instance weighting，KNN-IW），在多種數據集上的實驗結果顯示：與K近鄰方法相比，其分類性能提升顯著。假設數據集中有C類樣本，Costc×c是代價矩陣，其中，Cost［i，j］（i，j∈｛1，…，C｝）表示將j類的樣本錯分到i類的代價，并且Cost［i，i］＝0（i∈｛1，…，C｝），即正確分類的代價為0。第i類中有N［i］個樣本，樣本總數為N。設W為權值向量，其中W［i］表示第i類樣本的權值，如式（5）所示。

其中：Cost［i］是第i類樣本被錯分的期望損失。權值反映了代價信息，錯誤分類代價越高，權值越大。

KNN-IW分類時首先計算測試樣本和訓練樣本之間的距離，選擇距離最小的K個近鄰訓練樣本進行加權投票。每個類別標簽得到的票數用式（6）計算得到。

其中：NEI是近鄰樣本的索引組成的集合；y（·）表示樣本所在的類別；W則通過式（5）計算得到。

測試樣本所屬的類別即為Score值最大的那個類別，當不止一個類別的Score值最大時，選取其中Cost［i］最小的類。當所有樣本的權值相同時，樣本加權后的Score值與K近鄰分類算法的投票結果是一致的。

2 方法

將Fisher特征選擇和KNN-IW的分類方法融合一起進行垃圾網頁檢測。首先，使用Fisher特征選擇方法針對訓練數據集進行特征選擇，按Fisher Score從大到小排序；然后，按照Fisher Score從大到小的順序依次選擇特征，對訓練數據集本身使用KNN-IW方法進行分類，以整個訓練數據集分類結果的AUC值作為選擇標準，采用貪婪算法，選擇那些會使AUC值提升的特征；最后，將選擇得到的特征訓練K近鄰分類模型，用此模型對測試數據集進行分類。將此方法命名為基于Fisher最優特征選擇和KNN-IW的分類器（K nearest neighbor classifier with instance weighting based on optimal fisher feature selection，KNN-IW-OFisher），其主要流程如圖1所示。

圖1 方法主要流程框圖

本文方法除了融合Fisher特征選擇和KNNIW兩種方法外，還在以下幾個方面做出了改進。

首先針對訓練數據集在計算出每一個特征的Fisher Score之后，并不是直接設定一個閾值θ，根據特征是否大于θ值來確定其去留，而是采用一種貪婪算法選擇最優特征。該算法稱為最優特征選擇算法，其偽代碼如算法1所示。

算法1最優特征選擇算法

輸入數據集X，數據集標記Y，特征排序向量Features，分類算法Classifier

輸出被選中特征的排序向量SelectedFeatures

步驟

1）MaxAUC＝0

2）SelectedX＝［］

3）SelectedFeatures＝［］

4）for i＝1 to m ／／其中m為特征總個數

5）Temp X＝［Selected X X［Features［i］］］／／其中Features［i］為排在第i個位置的特征下標，X［Features［i］］為數據集針對第Features［i］個特征進行劃分得到的子數據集

6）AUC＝Classifier（Temp X，Y） ／／使用分類器對子數據集Temp X、Y進行分類，采用n－折交叉驗證，根據分類結果計算AUC值

7）if AUC＞MaxAUC then

8）Seletec X＝Temp X

9）SelectedFeatures＝SelectedFeatures Features［i］］

10）MaxAUC＝AUC

11）End if

12）End for

該算法輸入參數中的數據集X及其標記Y僅為訓練數據集，在算法內部通過n－折交叉驗證的辦法驗證特征的有效性。輸入參數中的特征排序向量是指根據Fisher Score從大到小排序后所對應特征的下標向量。例如，設有5個特征的Fisher Score分別為［3 5 1 6 2］，則其特征排序向量為［4 2 1 5 3］。這里的分類算法是指KNN-IW分類器，將其作為輸入參數傳遞使得算法更具通用性，可適用于其他分類器。Fisher特征選擇的計算Fisher Score并排序的過程未包含在算法內，而只根據Fisher Score計算出特征排序向量作為參數傳入，也是為了保持算法的通用性和模塊化。

其次，在使用KNN-IW分類時，對于測試樣本和訓練樣本之間的距離度量，針對連續特征、離散特征和缺失特征值時3種情況，文獻［23］分別給出了不同的距離計算方式。而在本文的垃圾網頁檢測實驗中所用到的數據集無缺失值特征，所以未考慮該情況。對于連續特征值，本文與文獻［23］一樣采用歐氏距離度量。對于離散特征，本文與文獻［23］不同的是將離散特征數量化后依然采用歐氏距離度量。

最后是在進行KNN-IW分類時樣本權值即代價矩陣的確定。樣本加權是一種基于代價敏感的方法，即認為不同類別的樣本被錯誤分類后的代價是不同的。代價矩陣一旦確定，則樣本權值也隨之確定。在垃圾網頁檢測問題中，垃圾網頁與正常網頁被錯誤分類的代價是不一樣的。但問題是，代價矩陣如何確定？在一般的代價敏感分析方法中，常根據用戶經驗確定代價敏感矩陣，但垃圾網頁與正常網頁被錯誤分類的代價難以憑經驗確定。本文在確定代價矩陣時不從錯誤分類的代價入手，而從網頁分布的不平衡性入手。KNN算法針對不平衡數據集進行分類容易偏向大類，使用過采樣方法使得數據集更為平衡后再進行KNN分類，分類性能會顯著提高。假設使用KNN-IW算法進行不平衡數據的二元分類，其代價矩陣為，表示將大類樣本錯分為小類的代價為1，而將小類樣本錯分為大類的代價為7。這樣大類樣本的樣本權值為1，而小類樣本的樣本權值為7。該分類方法的最終效果與使用KNN算法進行分類時將小類樣本重復7次即進行7次過采樣的思路是一致的。本文假設在對垃圾網頁檢測問題采用KNN進行分類時，正負樣本數完全相等時分類效果最好。為此，如果采用過采樣方法，則對小類樣本的采樣比率是大類樣本數對小類樣本數的倍數。同理，如果采用代價敏感方法KNN-IW，則小類樣本的錯分代價與大類樣本的錯分代價的比值應等于訓練集中大類樣本個數對小類樣本個數的倍數。因此，在垃圾網頁檢測問題中，只需將大類樣本的權值設為1，將小類樣本的權值設為訓練集中大類樣本個數與小類樣本個數的比值即可。

3 實驗與討論

3.1 數據集及評價指標

實驗所用數據集為用于垃圾網頁檢測研究的公 開 數 據 集WEBSPAM-UK2006［24］，最 初 用 于2007年網絡對抗信息檢索研討會進行垃圾網頁檢測競賽。WEBSPAM-UK2006數據集本身已按保持法（Hold-out）的要求，分為訓練集和測試集2個部分，擁有多種不同的特征。本文實驗采納了其中4種共274個特征，分別是基于內容的特征96個，基于鏈接的特征41個，基于鏈接轉換的特征135個，基于鄰接圖的特征2個。訓練集和測試集的樣本數情況如表1所示。由表1可知：訓練集中正常網站與垃圾網站的比例約為7∶1，這表明訓練集是不平衡的，與真實情況較為一致。

表1 WEBSPAM-UK2006數據集的樣本數

使用3種指標評估分類模型，分別是準確率（Accuracy），F1-測度（F1-Measure）和AUC值。垃圾網頁檢測是一個二元分類問題。對于二元分類問題，表達測試樣本集分類結果的混淆矩陣由TP、TN、FP和F 4個值構成，其中TP為被正確分類的正例，TN為正確分類的負例，FP為錯誤分類的正例，FN為錯誤分類的負例。于是準確率和F1-測度值可分別用式（7）和式（8）計算得到。

對于二元分類而言，隨機挑選一個正樣本以及一個負樣本，分類算法根據計算得到的分數（Score）值將正樣本排在負樣本前面的概率即為AUC值［25］。AUC值越大，表明當前的分類算法越有可能將正樣本排在負樣本前面，即能夠更好地分類。AUC值相比準確率和F1-測度而言，更適用于不平衡數據集的分類性能評價［26］。

3.2 實驗結果分析

為了比較本文方法的有效性，首先將其與相關方法進行比較。由表2可知：決策樹（classification and regression tree，CART）、支持向量機（support vector machine，SVM）、樸 素 貝 葉 斯（na?ve bayesian classifier，NBC）、K近鄰（KNN）等方法用于垃圾網頁檢測，其分類性能較差。僅有K近鄰法（KNN）的AUC值還比較高，達到90%以上，但其準確率和F1測度依然很低。

KNN-IW方法因為考慮了訓練數據集的不平衡性，與KNN算法相比，準確率提升16%，F1測度提升20%，雖然AUC值降低了1%，但依然可以說，樣本加權方法的引入，使得分類性能得到大幅度提升。將KNN與Fisher特征選擇方法相結合（KNN-Fisher），所得到的分類性能與KNN相比，其準確率、F1測度和AUC值分別提升9%、11%和1.3%。該方法表明Fisher特征選擇對于KNN算法的有效性。進一步，將KNN與樣本加權、Fisher特征選擇三者相結合（KNN-IW-Fisher），與KNN相比，其準確率、F1測度和AUC值分別提升20%、22%和1%，分類性能得到再次提升。最后，將KNN-IW-Fisher方法與最優特征選擇方法相結合（即本文方法KNN-IW-OFisher），與KNN相比，其準確率、F1測度和AUC值分別提升22%、24%和2.6%，成為這眾多分類結果中的最優結果。另外，本文曾選用過互信息、InfoGain、卡方檢驗、Laplacian Score等多種過濾式特征選擇方法進行實驗，最終結果是Fisher特征選擇的方法是最優的。表2中將次優的結果，即采用InfoGain特征選擇方法（KNN-IW-OInfoGain）也一并列出，可見其準確率、F1測度和AUC均比本文方法KNN-IWOFisher差1%左右。

表2 相關方法的有效性

需要說明的是：本文所有KNN相關算法所采納的K值都采用了19。實驗表明：K＝19可以達到較好的分類效果。另外，Fisher特征選擇時，Fisher Score閾值設為1%，此時分類性能達到最優，最終保留的特征數為81個。而本文方法KNN-IW-OFisher無需設置閾值，最終保留的特征只有47個。

表3列出了2007年垃圾網頁挑戰賽各優勝團隊的檢測結果。KNN-IW-OFisher分類器的分類性能在F1-測度這個指標上，其值為0.92，高于競賽團隊的最優結果0.91；而在AUC這個指標上，其值為0.94，僅次于最優結果，即滑鐵盧大學團隊的結果0.96。然而，滑鐵盧大學團隊的F1-測度值僅為0.67，表明其分類準確率很差。跟F1測度和AUC都較優的匈牙利科學院團隊相比，本文方法依然更優，高出1%。

表3 web spam challenge 2007優勝團隊檢測結果

Scarselli等［7］提出一種包含概率映射圖自組織映射（probabilistic mapping graph self-organizing map，PM-G）和圖神經網絡（graph neural network，GNN）的圖層疊架構用于垃圾網頁檢測，同樣基于WEBSPAM UK-2006進行實驗。表4第1行列出其所得最優方法FNN，PM-G＋GNN（3）＋GNN（1）的實驗結果。本文方法與其相比，除了準確率更低外，AUC接近其分類結果，而F1測度則明顯更優。對于不平衡分類而言，F1測度和AUC是更為重要的2個指標。從這2個指標看，本文方法有一定優勢。

表4 Scarselli其他研究團隊的分類結果

Belahcen等［15］提出一種傳感-感應圖神經網絡（transductive-inductive graph neural networks，TIGNN）方法基于WEBSPAM UK-2006數據集實驗。如果采用不同于2007年垃圾網頁挑戰競賽原始的數據切割方式，其方法得到最優（state-ofthe-art）的分類結果，如表4第3行所示。但如果采用原始的數據切割方式，其方法的實驗結果也表現優異，如表4第2行所示。本文方法未考慮數據重新切割的問題，因此與其在原始切割數據集上的實驗結果相比更為合適。與其相比，本文方法的實驗結果也比較接近，F1測度更優，AUC值略少1%。

Lu等［16］提出一種融合人工免疫克隆選擇、欠采樣集成和C4.5決策樹的分類方法，如表4第4行顯示其在WEBSPAM UK-2006上的實驗結果，其方法的分類結果略優于本文方法，但其采用的基于人工免疫克隆選擇的特征選擇方法耗時太長，同時其抗體個數還成為一個超參數，算法的實用性比本文方法更差。

4 結論

提出一種融合最優Fisher特征選擇和樣本加權的K近鄰分類的機器學習算法KNN-IW-OFisher用于垃圾網頁檢測。在WEBSPAM-UK2006數據集上的實驗表明：本文方法的分類效果明顯優于決策樹、支持向量機、樸素貝葉斯、K近鄰等傳統分類器。與其他最優的實驗結果相比，本文方法也接近最優結果。對KNN-IW-OFisher算法在垃圾網頁檢測上取得較好的分類效果的原因進行了分析和探討，并指出了可以進一步研究的相關問題。