模糊核覆蓋分類器及其應用

摘 要:核覆蓋算法是一種性能優秀的分類算法，但在拒識點處理方面存在不足。對核覆蓋算法的構造過程進行了分析，修改了算法中覆蓋半徑的選取原則，對拒識樣本引入隸屬度函數，將算法推廣為模糊核覆蓋算法。討論了孤立覆蓋對分類器的影響，對覆蓋數進行精簡，降低計算量。通過實驗驗證改進算法的性能，并與其他模糊分類方法進行對比。將模糊核覆蓋算法應用于垃圾郵件過濾，實驗結果表明過濾器的性能得到了有效提高。

關鍵詞:覆蓋算法; 核函數; 拒識樣本; 模糊核覆蓋; 垃圾郵件過濾

中圖分類號:TP391文獻標志碼:A

文章編號:1001-3695(2010)06-2043-04

doi:10.3969/j.issn.1001-3695.2010.06.013

Fuzzy kernel covering classifier and its application

DUAN Zhena，b， CHENG Jia-xinga，b， ZHANG Linga，b

(a.Key Laboratory IC SP， Ministry of Education， b.School of Computer Science Engineering， Anhui University， Hefei 230039， China)

Abstract:While kernel covering algorithm (KCA) is a kind of effective classification algorithm， it still falls short in treating rejection points. This paper analyzed the construction process of kernel covering algorithm. By revising the selection criteria of covering radius and introducing the membership function for rejection points， generalized the algorithm as fuzzy kernel covering algorithm (FKCA). Also discussed isolated covering’s impact on classifier’s performance and lowered the computation cost through reducing the number of coverings. Comparing with other classification methods on experiment results show this fuzzy kernel covering algorithm works well. FKCA is applied to spam filtering and the classifier’s performance is improved effectively.

Key words:covering algorithm; kernel function; rejection sample; fuzzy kernel covering; spam filtering

0 引言

分類器的設計是模式識別中的核心問題。文獻[1]從M-P神經元的幾何意義入手，提出了基于覆蓋的構造性學習方法，在這之后，眾多研究者對覆蓋算法的理論和應用進行了多方面的探討。將覆蓋算法與核函數相結合的核覆蓋算法具有較好的分類能力[2]，但對拒識樣本的處理采用就近原則，不能體現各覆蓋的性質，影響了分類器的效果。

為了彌補核覆蓋算法在拒識樣本處理上的缺陷，提高分類器的整體識別效果，本文對核覆蓋算法的構造過程進行了分析，修改了覆蓋半徑的選取原則，對拒識樣本引入隸屬度函數進行計算。實驗證明，這種方法能夠有效提高分類器對拒識樣本的識別能力，從而提升整體性能。同時，通過精簡孤立覆蓋，在可接受的精度下降程度內，能夠有效減少覆蓋個數，降低計算量。

1 核覆蓋算法(KCA)

覆蓋算法的基本思想是將樣本點映射到空間中的一個超球面Sn上后進行球形領域的劃分[1]。令樣本空間中各樣本的向量的長度均相等(否則可通過投影來實現)。給定ω， x∈Rn，θ∈R，此時的ω′x-θ>0表示球面上由超平面ω′x-θ=0所分割的正半空間的部分，稱為球面上的球形領域，若ω與x等長，則ω就是這個球形領域的中心。以每個球形領域作為一個神經元，取ω′x-θ=0為其功能函數。此時，構造一個網絡，對給定的樣本集進行分類，等價于求出一組領域，對給定樣本集S中的點，按分類的要求用領域覆蓋將它們分隔開來。通過覆蓋算法，在樣本空間構造覆蓋簇{Ci}，使Ci只蓋住某一類點，且所有Ci的并集覆蓋整個S。設已求得覆蓋簇C1，…，Cn，取三層神經網絡，隱層取n個神經元，每個神經元為一個覆蓋，第i個神經元的激勵函數為Ci的特征函數。輸出層取k個神經元，第i個神經元的輸入為覆蓋第i類點的覆蓋的輸出，激勵函數采用或門，這樣的三層網絡下就可對S進行分類。在構造覆蓋時，采用式(1)確定各覆蓋的半徑:

d1=max{〈x，a1〉}，xXi

d2=min{〈x，a1〉|〈x，a1〉>d1}，x∈Xi

θ1=(d1+d2)/2(1)

在統計學習理論中，通過引入核函數，將輸入空間變換到核空間，在核空間中求取最優分類超平面。求解過程中只涉及內積運算，且該運算可用原空間中的函數來實現，而無須知道變換形式。常用的核函數包括多項式核函數、Sigmoid核函數和徑向基核函數(RBF)等。文獻[3]中證明了徑向基核函數的兩個性質。其中的性質1表明，論域X上的任一點都被RBF映射到核空間的單位球面上，這正是覆蓋算法中將樣本投影到球面上的基本出發點，因此可以在核空間中構造覆蓋，實現樣本空間中的分類。

2 模糊核覆蓋算法

2.1 對核覆蓋算法的分析

對分類問題，由于客觀事物自身的模糊性，往往不能精確地確定某個對象屬于某個類，只能給出該對象屬于某個類的可能性，由此產生模糊分類問題。從本質上來說，核覆蓋算法可看做是一種模糊分類器，它根據樣本到各已知類別的距離，選擇最近的類別作為歸屬。

在覆蓋算法中，根據訓練樣本進行學習后得到一系列覆蓋，對球形領域形成分割。由于樣本空間分布的特點，在超球面上一般均存在一部分區域，沒有落入任何覆蓋之中，稱為拒識區域，落入拒識區域的樣本構成拒識點。在核覆蓋算法的識別過程中，依照未知樣本與已有覆蓋領域間的位置關系進行分類。如果樣本落入某個覆蓋，認為樣本與該覆蓋所描述的特征比較接近。當樣本所處位置由覆蓋中心趨向于邊緣時，d(x，Ci)的值逐漸降低，描述了樣本屬于該覆蓋的程度，在覆蓋邊緣處，d(x，Ci)為0。如果樣本落入拒識區域，d(x，Ci)均為負值，描述了樣本距離各覆蓋邊緣的距離，此時同樣依據d(x，Ci)的大小進行判別。

值得思考的是，對拒識樣本處理時所采用的就近原則是否合理。在就近原則中，僅考慮了拒識點到各覆蓋邊界的距離，但是忽略了其他各類因素，如已有覆蓋的大小、質量等，這些因素對拒識點的判定是否存在影響，從而對最終的識別效果產生作用。

在研究中發現，對于部分數據集，采用就近原則的效果尚可，但對于一些數據集，采用就近原則時的效果并不理想。以UCI中的數據集pen-based recognition of handwritten digits為例，采用核覆蓋算法和就近原則進行測試。

由于核函數中的參數q的確定尚不存在成熟的選擇方法，實驗中對q依次取1~100的整數值，在每個值上進行100次計算得到平均識別效果，部分結果如表1所示。

表1 KCA對pen-based數據集的測試結果

參數q25506580

最優識別率/%95.4095.4395.6895.11

平均識別率/%94.3894.4394.4694.41

平均覆蓋數278.12275.90274.48277.16

平均拒識數119.10118.64117.20116.82

平均拒識判定正確數10.7711.5210.6610.04

平均拒識判定正確率/%9.039.719.108.59

Pen-based是一個手寫數字識別的數據集，分為0~9共10種類別。其中訓練樣本7 494個，測試樣本3 498個，每個樣本具有16種特征屬性，取值范圍均在0~100。從測試結果可以看出，隨著參數的變化，識別率成倒U型分布，當q=65時，最優識別率和平均識別率均達到了比較好的結果，因此文中pen-based數據集的核函數參數均取q=65。同時注意到，對于拒識樣本，采用就近原則的效果非常不理想，對整體的識別率造成了非常嚴重的影響。

2.2 覆蓋半徑的選取

覆蓋算法中，每個覆蓋的半徑使用式(1)來確定。其中d1表示當前領域中心與最近異類點的距離(由于采用了內積運算，距離最近時d1取最大值，反之亦然)，d2表示在滿足大于d1的前提下，領域中心與最遠同類點的距離。取θ1=(d1+d2)/2作為半徑，使得兩類覆蓋對領域進行均分，所有覆蓋之外的區域即為拒識區域。這樣處理的目的，一方面是體現各類別的均等性，另一方面是盡量擴大覆蓋區域，使更多的測試樣本落入已有覆蓋，降低拒識率。

采用上述的半徑策略，擴大了超球面上覆蓋區域所占的面積，拒識區域減少，形成了低拒識率的表現。但必須注意到，這種低拒識率是通過對未知區域的猜測來實現的，其本質是在構造過程中直接采取就近原則，對一部分未知空間進行預分類。當就近原則的效果不佳時，這種猜測是危險的，雖然降低了拒識率，但也降低了總體的識別率。如果換一種思路，并不排斥拒識區域的出現，而是通過對拒識樣本進行妥善處理，使這部分樣本也能夠被較準確地分類，從而提升分類器的整體效果。

根據以上分析，在改進算法中，首先將半徑求取原則修改為θ1=d2，讓每個覆蓋只忠實地描述已經學到的知識，即通常所說的“知之為知之，不知為不知”。這樣修改必然導致覆蓋領域縮小，拒識區域增大，拒識點增多，此時通過改進拒識樣本的處理方式來提高分類器的識別率。

2.3 模糊核覆蓋算法(FKCA)

在拒識樣本的判定過程中，引入樣本對第i個覆蓋Ci的隸屬度函數:

μi=(1+K(x，ωi)-θi)×K(x，ωi)/θi(2)

其中:K(x，ωi)是拒識樣本到Ci中心ωi的距離;θi是Ci的半徑;K(x，ωi)-θi是拒識樣本距Ci邊緣的距離，為負值。該函數綜合考慮了樣本與覆蓋邊緣的距離、樣本與覆蓋中心的距離以及覆蓋半徑等因素。當樣本恰好落在覆蓋邊緣時，μi的值為1，即屬于該覆蓋。隨著樣本遠離覆蓋邊緣，μi單調下降，逐漸趨向于0。此時得到模糊核覆蓋算法(fuzzy kernel covering algorithm，FKCA)。該算法分為學習和測試兩部分，分別表述如下:

a)學習算法。設學習樣本X，共k類，即X={X1，X2，…，Xk}，采用徑向基函數K(x，z)=exp(-‖x-z‖2/q)。其中q=2σ2。對k個類別，依次構造各類的覆蓋，直至所有樣本均被包含在某一個覆蓋中。第i類的覆蓋構造過程如下:

(a)取第i類中任一尚未被覆蓋的點，記為a1;

(b)以a1為中心，根據式(1)中的d2求閾值θ1，得到以a1為中心、θ1為半徑的一個覆蓋C(a1);

(c)求覆蓋C(a1)的重心a′1，再按(b)求新閾值θ′1，得到新覆蓋C(a′1)，若C(a′1)比C(a1)覆蓋更多的點，則a′1→a1，θ′1 →θ1，循環操作直到C(a′1)不能覆蓋更多的點;

(d)求a1的平移點a″1(具體算法可參見文獻[1])，得到覆蓋C(a″1)，若C(a″1)比C(a1)覆蓋更多的點，則a″1→a1， θ″1→θ1，轉(c)，否則就求得了一個覆蓋Ci，轉(a)。

b)測試算法如下:

(a)對每一個樣本x，求取d(x，Ci)=max{K(ωi，x)-θi}。其中:ωi是Ci的中心;θi是閾值。

(b)當d(x，Ci)≥0時，取對應的i作為樣本類別;否則轉(c)。

(c)計算樣本對各覆蓋的隸屬度μi=(1+K(x，ωi)-θi)×K(x，ωi)/θi，取max(μi)對應的i作為樣本類別。

2.4 覆蓋數的精簡

分類規則的精簡是分類問題中的一個重要目標。覆蓋算法中的每一個分類超平面將一個領域與球面上的其他區域分隔開來，形成一條規則，覆蓋數即為規則數。文獻[4]中介紹的算法在思想上與本文所研究的覆蓋算法有一些類似，文中所述的支撐覆蓋集即本文的覆蓋，支撐覆蓋點即各個覆蓋的中心。根據文獻[4]的思想，在分類過程中僅需計算并比較測試樣本到各類支撐點的距離，計算量和存儲量均要求較低。因此，如果能縮減覆蓋的數量，減少支撐點，可以進一步降低計算量。在FKCA中，由于半徑選取原則的修改，如果某個樣本周圍均為異類樣本，此時所構造的覆蓋以自身為中心，以1為半徑，退化為超球面上的一個點。這些點狀領域的存在，不僅增加了網絡的復雜性，而且容易產生誤識和拒識，因此可看做孤立點或噪聲。如果將這些領域刪除，并對已有領域進行調整，可以降低分類時的運算量，提高網絡的推廣能力。在實驗中，對學習算法進行調整，將得到的所有孤立覆蓋刪除，并調整之前已得到的覆蓋，稱這種算法為FKCA-ID(fuzzy kernel covering algorithm with isolated point deletion)。此時在FKCA的學習過程增加如下:

當本次覆蓋構造完畢后，計算覆蓋中所包含的樣本數量。如果樣本數為1，視該樣本為孤立點，刪除所得的覆蓋，并從學習樣本集中刪除該樣本，對已構造的覆蓋調整半徑。

3 實驗及分析

3.1 對pen-based數據集的測試

取核函數中的參數q=65，使用KCA、FKCA和FKCA-ID各進行100次運行，結果如表2所示。

表2 KCA、FKCA和FKCA-ID在pen-based上的對比

比較項

方法

KCAFKCAFKCA-ID

最優識別率/%95.6897.5497.13

平均識別率/%94.4696.6496.18

平均覆蓋數274.48277.01187.90

平均拒識數117.20257.43258.19

平均拒識判定正確數10.66194.52193.13

平均拒識判定正確率/%9.1075.5674.80

平均訓練時間/s7.887.897.20

平均測試時間/s0.680.710.52

從表2可以看出，采用FKCA之后，由于半徑規則的修改，拒識點增加，但對拒識點的識別率也有了明顯的提高，分類器的性能得到顯著改善。去除孤立覆蓋之后，在識別率方面略有下降，但覆蓋數僅為原先的2/3，規則數明顯減少。從運行時間上看，在FKCA中，半徑的縮小，覆蓋個數有所增加，且對拒識樣本要重新計算其隸屬度，因此訓練時間和測試時間均稍有增加。而對FKCA-ID來說，在學習過程中減少了對孤立覆蓋的操作，測試過程中參與運算的覆蓋數量減少，因此訓練時間和測試時間都有比較明顯的降低，而此時的識別效果依然保持了較高的水平。在識別率能夠滿足要求的前提下，FKCA-ID能夠有效縮減覆蓋數，降低計算量，這對于海量數據的快速分類是有益的。

在文獻[5]中，使用基于進化式核聚類的模糊分類模型(FCMBEKC)和其他算法在pen-based數據集上進行了測試，表3給出了FKCA與這些方法在識別率上的對比。

表3 FKCA與其他方法在pen-based上的對比

FKCA/bestFKCA/averageFCMBEKCANN靜態/MLP動態/MLP

rate/%97.5496.6497.3491.294.2595.26

根據表3， FKCA的最優識別率較FCMBEKC有所提高，平均識別率略低，但仍優于其他方法。同時，根據文獻[5]，FCMBEKC對訓練集的識別率為99.97%，但覆蓋算法的構造過程能夠確保算法對訓練集的識別率為100%。FCMBEKC中，總的規則數等于855，而覆蓋算法中，由于每個覆蓋對應一個規則，平均規則數約為277，也優于FCMBEKC。

3.2 對其他數據集的測試結果

使用UCI上的另兩個常用數據集Glass和Letter recognition對KCA、FKCA和FKCA-ID進行對比。其中Glass的核函數參數q取60，采用十交叉驗證，Letter recognition的核函數參數q取75，前16 000個樣本進行學習，后4 000個樣本進行測試，結果如表4、5所示。

表4 KCA、FKCA和FKCA-ID在Glass上的對比

比較項

方法

KCAFKCAFKCA-ID

最優識別率/%70.0070.9170.00

平均識別率/%63.8666.5864.72

平均覆蓋數83.3983.2331.77

平均拒識數4.4311.1811.16

平均拒識判定正確數2.156.495.96

平均拒識判定正確率/%48.5358.0553.41

平均訓練時間/s2.362.511.99

平均測試時間/s0.030.030.02

表5 KCA、FKCA和FKCA-ID在L-R上的對比

比較項

方法

KCAFKCAFKCA-ID

最優識別率/%93.3593.5693.38

平均識別率/%92.8693.1292.89

平均覆蓋數2 294.652 512.801 358.95

平均拒識數241.65777.50763.75

平均拒識判定正確數152.10557.60526.10

平均拒識判定正確率/%62.9471.7268.88

平均訓練時間/s115.18126.05107.21

平均測試時間/s7.688.925.07

從結果來看，對這兩個數據集，FKCA和KCA的性能差異不如pen-based那么明顯，但由于綜合考慮了覆蓋中的多個參數，FKCA仍然能夠通過改善對拒識樣本的處理，在不同程度上提高整體性能。對于FKCA-ID，最優識別率和平均識別率較FKCA略有降低，但仍優于KCA，而且覆蓋數有了明顯的下降，分別只占原有覆蓋數的1/3和1/2，與之前在pen-based中的表現一致。同樣，在保持了較高識別率的前提下，分類器的訓練時間和測試時間均有了較大幅度的下降。

根據前面的對比結果，FKCA相對于KCA在不同數據集上的性能提升存在差異。由覆蓋算法的構造思想，從直觀上來看，這與樣本在空間的分布狀態應當存在一定的聯系，這也將是筆者后期在理論研究中的一個主題。

4 基于FKCA的垃圾郵件過濾

隨著互聯網的發展，電子郵件已經成為日常信息交流的一種重要手段，垃圾郵件的日益泛濫也對正常的工作和生活造成了影響，對垃圾郵件進行有效過濾是當前一種重要的網絡應用。筆者將FKCA應用于垃圾郵件過濾，實驗樣本集中共包含垃圾郵件1 724篇，非垃圾郵件1 046篇，平均分為兩份，每份均包含垃圾郵件862篇，非垃圾郵件523篇，分別作為學習樣本和測試樣本。

在郵件的預處理過程中，首先使用向量空間法，通過分詞，將每封郵件轉換為特征向量。在選擇放入信息向量的分量時，將郵件的一些附屬信息，如郵件來源地址、郵件主題、是否包含附件、附件類型等，與郵件正文內容一起綜合考慮，均作為郵件信息向量的分量放入分類器中進行學習。由于在分詞后會產生龐大的詞組集，導致信息向量的維數過高，采用期望交叉熵的方法進行降維，得到特征屬性為2 000維的樣本集。使用學習樣本集在核空間中構造覆蓋，使用測試樣本集來驗證分類器的性能。

由于垃圾郵件過濾中存在的特殊性，假陽性(即正常郵件被判別為垃圾郵件的錯誤)要比假陰性(即垃圾郵件被判別為正常郵件的錯誤)的后果嚴重，遭到用戶投訴的可能性也就更大。因此，對郵件分類，必須確保郵件的最小風險，這種評價機制被稱為代價敏感評價機制[6]，通常采用查準率作為評價指標。如果垃圾郵件的查準率遠小于1，意味著本屬于正常郵件而被系統識別為垃圾郵件的樣本較多，說明該分類中的風險較高。

分別采用KCA、FKCA和FKCA-ID方法進行學習和測試，結果見表6。從測試結果可以看出，使用FKCA時，最優識別率、平均識別率和拒識樣本的判別正確率均達到了較好的水平，且垃圾郵件的查準率較高，但耗時比KCA多。使用FKCA-ID時，在基本保持分類器性能的前提下，覆蓋數得到了顯著降低，且訓練時間和測試時間都明顯下降，這在實際應用中是非常有意義的。

表6 KCA、FKCA和FKCA-ID在郵件過濾中的性能對比

比較項

方法

KCAFKCAFKCA-ID

最優識別率/%96.1796.6896.39

平均識別率/%95.0295.8195.36

平均查準率/%96.3796.8596.49

平均覆蓋數212.61245.25101.80

平均拒識數93.45274.35287.65

平均拒識判定正確數52.30245.60246.50

平均拒識判定正確率/%55.9789.5285.69

平均訓練時間/s67.5671.5654.16

平均測試時間/s19.7223.2112.98

5 結束語

覆蓋算法是一種性能優秀的分類器，通過引入核函數，在核空間中構造分類超平面，得到核覆蓋算法，當參數選取適當時，能夠優化分類器的性能。在構造覆蓋的過程中，通過擴大覆蓋區域來降低拒識率，卻犧牲了識別率。而且在分類時，對拒識點采取的就近原則未考慮覆蓋的其他參數，對類別歸屬造成了一定影響，導致整體識別率的降低。通過改變構造覆蓋時的半徑選取原則，并對拒識樣本給出隸屬函數，得到的模糊核覆蓋分類器能夠提高拒識樣本的識別率，最終在不同程度上提高整體性能。通過刪除孤立點，精簡覆蓋數量，在保持較高識別精度的同時，能夠有效降低分類器的運算量，減少分類器的訓練和測試時間，具有較高的實用價值。

參考文獻:

[1]張鈴，張鈸，殷海風.多層前向網絡的交叉覆蓋設計算法[J].軟件學報，1999，10(7):737-742.

[2]張燕平，張鈴，段震.構造性核覆蓋算法在圖像識別中的應用[J].中國圖象圖形學報，2004，9(11):1304-1308.

[3]張鈴.機器學習中的覆蓋算法與核函數法[C]//第十二屆全國神經計算學術大會論文集.北京:人民郵電出版社，2002:78-83.

[4]楊金福，吳福朝.分類判別的覆蓋算法研究[J].電子與信息學報，2007，29(7):1726-1730.

[5]陽愛民.模糊分類模型及其集成方法[M].北京:科學出版社，2008.

[6]LI Wen-bin，LIU Chun-nian，CHEN Yi-ying. Design and implement cost sensitive email filtering algorithms[C]//Proc of Artificial Intelligence Applications and Innovations. New York: Springer，2005:325-334.