基于相似度量的自適應三支垃圾郵件過濾器

2019-11-15 01:49:02張清華王國胤

計算機研究與發展 2019年11期

謝秦張清華王國胤

(計算智能重慶市重點實驗室(重慶郵電大學) 重慶 400065)

互聯網時代使人類獲取信息的方式更加便捷多樣,但也給人類帶來了諸如垃圾郵件等有害信息.對于某些人群來說,若郵件被錯分則會帶來非常大的損失,如風險投資者因一封投資分析報告郵件被錯分到了垃圾郵件類,則其投資計劃將會因為信息獲取不及時而遭受巨大損失.因而提高過濾器的分類準確率及召回率等指標對于垃圾郵件過濾來說至關重要.在業界,垃圾郵件過濾通常被視為一個二分類問題.目前,機器學習領域中的大量二分類模型都可被用來處理垃圾郵件過濾問題,如k近鄰分析法[1]、樸素貝葉斯(Naive Bayes, NB)分類器[2]、基于集成學習的分類器[3]等.然而,由于二分類模型武斷地把郵件歸類為垃圾郵件類或合法郵件類,因此會導致決策過程中產生較大的錯分代價進而導致分類精度較低.此外,由于二分類模型在分類時過于直接,因此常常無法確定最優閾值.

三支決策模型實質上是在二分類模型的基礎上加入了延遲決策域.換言之,三支決策模型的主要優點在于其允許延遲決策的可能性.如果做出延遲決策的代價不高,則三支決策模型是一個有效的選擇.此外,從人類認知的角度出發,三支決策模型將不能確定類別的郵件放到延遲決策域,用戶可以依據實際需求查看延遲決策域里的郵件,可達到靈活選擇有價值的郵件的目的.目前,三支決策研究領域已有不少的成果,如文獻[4]將不能合理地判別是垃圾郵件或合法郵件的郵件稱為灰色郵件,并提出了4種原型檢測方法.此外,根據粗糙集[5-6],文獻[7-9]提出了決策理論粗糙集模型,并受到了廣大學者的關注,如文獻[10]基于決策粗糙集提出了一種解決修飾和不修飾情感詞語情況下的否定句情感分類模型.進一步地,為給決策粗糙集中的3個域賦予一定的語義,文獻[11-12]提出了基于決策理論粗糙集的三支決策(three-way decision with decision-theoretic rough sets, 3WD-DTRSs)模型.3WD-DTRSs模型是一種依據貝葉斯決策規則,以最小化期望代價為目標來確定一對閾值并將待判對象劃分為3個域(接受域、拒絕域及延遲決策域)的三支決策模型.3WD-DTRSs模型的研究成果同樣豐富,如文獻[13]提出了一種基于猶豫模糊決策理論粗糙集的風險決策方法.文獻[14]給出了一種用于在給定接受域對象數量的情況下,建立具有給定屬性值的三支決策模型.值得提出的是,在3WD-DTRSs模型研究中,閾值的計算一直是一個研究熱點,研究者已給出一些計算方法[15-19],如文獻[20]提出了一種利用相對值確定3WD-DTRSs模型的損失函數的方法.垃圾郵件過濾過程從代價的角度可以解釋為,將一個實為垃圾郵件的郵件判斷為垃圾郵件的代價小于將其判斷為延遲決策的代價,而將其判斷為延遲決策的代價又小于將其判斷為合法郵件的代價.同理,將一個實為合法郵件的郵件判斷為合法郵件的代價小于將其判斷為延遲決策的代價,而將其判斷為延遲決策的代價又小于將其判斷為垃圾郵件的代價.而3WD-DTRSs模型中的代價邏輯正好與之契合.因此,文獻[21]將3WD-DTRSs模型用于解決垃圾郵件分類問題,并從代價敏感等角度闡明了模型的優勢.

然而,在3WD-DTRSs模型研究領域,存在這樣一種情況,當2個等價類的粗糙隸屬度相同時,2個等價類必定會劃分到同一個區域.從模型原理的角度出發,這種現象存在的原因為在3WD-DTRSs模型中,粗糙隸屬函數反映的是等價類與目標集的交叉程度,而由專家給定的損失函數是將所有對象視作等價的,換言之,對于每一個等價類,只要等價類中的對象與目標集合的交叉度相同,則粗糙隸屬度相同,且損失函數都是相同的.然而,當二者所對應的各條件屬性值相差比較大的時候,二者在直觀上不應該屬于同一區域.從條件屬性值的角度出發,等價類與目標集合的相似度越大,該等價類在同等條件下更應該被劃分到正域,換言之,等價類之間是存在差異的.若仍然按照3WD-DTRSs模型的原理,忽略等價類之間的差異性,則在貝葉斯決策準則下推導出來的閾值并不能使得所有等價類達到全局的最小劃分代價,進而導致模型精度表現不夠理想.然而,目前少有研究在給定或者構造損失函數時考慮由于等價類之間存在差異而帶來的影響.因此,現有的3WD-DTRSs模型在模型性能上還存在一定的研究價值.已有工作[22]考慮等價類之間存在差異性等因素,基于效用理論給出了一種改進的基于決策粗糙集的三支決策模型.然而該模型在基于效用函數構造風險度量函數時,需要主觀給定風險偏好參數,則該模型的泛化能力還有待提高.此外,相似度量是一種度量2個對象之間相似度的工具,且相似度量的方法相當豐富[23-24],如相關系數、歐氏距離及集合相似度等.在垃圾郵件過濾領域,文獻[25]提出了一種用于垃圾郵件圖像聚類分析的非負稀疏相似性度量方法. 此外,劉伍穎等人[26]給出了一種基于結構化集成學習的垃圾郵件過濾器.因此,為了解決上述各問題,從集合相似度量角度出發,考慮等價類之間存在差異性等因素,提出了一種基于相似度量的自適應三支垃圾郵件分類器(similarity measure based adaptive three-way spam filter, SBA-3WD-SF).

首先根據集合方差給出了一種計算屬性重要度的方法,并基于此提出了一種計算條件屬性權重的方法；其次,根據集合相似度給出了一種度量等價類中條件屬性值與目標集合中相應屬性值的貼近度的方法；然后,進一步給出一種自動確定綜合評價函數的方法以度量風險,并根據貝葉斯準則,給出了一種計算自適應閾值的方法.實驗結果表明,所提的SBA-3WD-SF在準確率及召回率方面優于二元NB分類器及3WD-DTRSs分類器.換言之,SBA-3WD-SF是合理有效的.

1 基礎知識

1.1 基本定義

定義1.不可分辨關系.[2]給定一個信息系統S=(U,C∪D,V,f),對于屬性子集?B(B?C∪D),論域U上的一個不可分辨關系IND(B)可定義為

IND(B)={(x,y)|(x,y)∈U2,
?b∈B∧(b(x)=b(y))}.

(1)

定義2.近似集.[2]給定一個信息系統S=(U,C∪D,V,f),對于?X(X?U)及不可分辨關系IND(B),集合X的上下近似集可分別定義為

(2)

其中,

UIND(B)={X|X?U∧?x,y∈X∧
?b∈B∧(b(x)=b(y))}

表示由等價關系IND(B)在論域U上誘導的劃分.

從而,非空有限論域可被劃分為3個互不相交的區域,即正域(POS(X))、負域(NEG(X))及邊界域(BND(X))：

(3)

定義3.粗糙隸屬函數.[27]給定一個信息系統S=(U,C∪D,V,f),則對于?X(X?U)及不可分辨關系IND(B),關于目標集合X的粗糙隸屬函數可定義為

(4)

1.2 相關研究

為了突出貢獻,本節將分別簡要介紹一個二分類及一個三分類垃圾郵件分類器的代表模型,即二元NB分類器與3WD-DTRSs分類器.

1.2.1 二元NB分類器

文獻[28]提出了貝葉斯理論,文獻[29]提出了特征條件獨立性假設,文獻[30]將二者結合并提出了NB垃圾郵件過濾器.二元NB分類器是垃圾郵件過濾的一種最常用的二分類方法. 假設每一個待判的郵件對象x均可用一個m維的特征向量V(x)=(v1(x),v2(x),…,vm(x))表示,X表示垃圾郵件類,X表示合法郵件類. 有別于定義3中的條件概率Pr(X|Ej),可根據等價類與目標集的交并而獲得,而NB分類器主要是通過將面向單一對象的條件概率Pr(X|V(x))轉換為易于求解的后驗條件概率Pr(V(x)|X)的方式來解決難以直接求解Pr(X|V(x))的問題.根據貝葉斯定理及全概率公式,給定一個郵件V(x)=(v1(x),v2(x),…,vm(x)),其屬于垃圾郵件類X的后驗概率(一種判別函數)為

(5)

其中,

Pr(V(x))=Pr(X)Pr(V(x)|X)+
Pr(X)Pr(V(x)|X),

Pr(X)為X的先驗概率,Pr(V(x)|X)表示給定郵件V(x)時,V(x)∈X的似然函數.事實上,似然函數Pr(V(x)|X)是一個聯合條件概率Pr(v1(x),v2(x),…,vm(x)|X),然而,當m比較大時,在實踐中很難分析v1(x),v2(x),…,vm(x)之間的相互作用.因此,條件獨立性假設被應用于貝葉斯分類器,即假設當給定垃圾郵件類X時,每一個特征vi(x)(i=1,2,…,m)與其余特征都是條件獨立的,在表達式上體現為

(6)

其中,Pr(vi(x)|X)能很容易地從數據中估計得到.從而式(5)可以表示為

(7)

同理,后驗概率Pr(X|V(x))可以表示為

Pr(X|V(x))=

(8)

因此,概率Pr(V(x))可以被消除,即有：

(9)

1.2.2 3WD-DTRSs模型

作為三分類模型的一個代表模型,本節將簡要介紹3WD-DTRSs模型[11].首先,決策理論粗糙集模型[8]包含2個狀態T={X,X}及3個動作A={aP,aB,aN}.根據3個動作,由專家經驗給出的損失函數如表1所示：

Table 1 Loss Function Given by Expertise表1 由專家經驗給定的損失函數

由表1得知：在垃圾郵件過濾這個背景下,狀態X及X分別表示垃圾郵件類及合法郵件類.λPP,λBP,λNP分別表示一個本應該屬于垃圾郵件類的對象分別采取動作aP,aB,aN而產生的損失.同理λPN,λBN,λNN分別表示一個本應該屬于合法郵件類的對象分別采取動作aP,aB,aN而產生的損失.對于任意待判郵件x(x∈Ej),采取不同動作而產生的期望損失可表示為

(10)

根據貝葉斯決策過程中最小化損失原則,則決策規則為

(P)如果R(aP|Ej)≤R(aB|Ej)且R(aP|Ej)≤R(aN|Ej),則Ej?POS(X)；

(B)如果R(aB|Ej)≤R(aP|Ej)且R(aB|Ej)≤R(aN|Ej),則Ej?BND(X)；

(N)如果R(aN|Ej)≤R(aP|Ej)且R(aN|Ej)≤R(aB|Ej),則Ej?NEG(X).

由于Pr(X|Ej)+Pr(X|Ej)=1,則上述規則只與損失函數及判別函數Pr(X|Ej)有關,一個合理假設為λPP<λBP<λNP,λNN<λBN<λPN.且簡記為

(11)

則決策規則(P)(B)(N)可等價地表示為

(P)如果Pr(X|Ej)≥α,則Ej?POS(X)；

(B)如果β

(N)如果Pr(X|Ej)≤β,則Ej?NEG(X).

綜上所述,二分類模型及三支決策模型的差異如圖1所示.對于二分類模型,如果對象的判別函數Pr(X|x)≥ξ,則該對象被接受;反之,該對象被拒絕.對于三支決策模型,如果對象的判別函數Pr(X|x)≥α,則該對象被接受;如果該對象的判別函數Pr(X|x)≤β,則該對象被拒絕;如果該對象的判別函數α>Pr(X|x)>β,則該對象被歸入延遲決策域.

Fig. 1 Binary and three-way classification圖1 二支及三支分類

2 基于相似度量的三支決策模型

當前,作為一種簡單而有效的方法,距離度量被廣泛地應用于各個領域.其中,歐氏距離是距離度量中的一種簡單且易于理解的方法.在統計領域,歐氏距離[31]常被用來度量2個向量的距離.

2個向量Y=(y1,y2,…,ym)和Z=(z1,z2,…,zm)之間的歐氏距離定義為

(12)

其中,歐氏距離d(Y,Z)的取值范圍為[0,+).

在一個信息系統S=(U,C∪D,V,f)中,對于任意對象x(x∈U),各條件屬性的取值可以視為一個向量V(x)=(v1(x),v2(x),…,vm(x)),因而歐氏距離不僅可用于度量任意2個對象之間的距離而且同樣可用于度量2個集合之間的距離.基于歐氏距離,用以度量等價類與目標集合間相似度的歐氏距離描述如下.

給定一個信息系統S=(U,C∪D,V,f),其中,條件屬性集合為C={c1,c2,…,cm},目標集合為X={x1,x2,…,x|X|},?X?U.有限論域U上由等價關系IND(C)誘導的劃分為UIND(C)={E1,E2,…,Es},則對于?Ei(Ei∈UIND(C),i=1,2,…,s),等價類Ei和目標集X間的歐氏距離公式表示為

(13)

其中,

表示任意2個特征向量V(xi)=(v1(xi),v2(xi),…,vm(xi))和V(xj)=(v1(xj),v2(xj),…,vm(xj))之間的歐氏距離,且xi表示等價類Ei中任意對象,xj表示目標集X中的對象.

為了便于說明問題,所有例子所用的信息表中的數據都是數值型的,且每個屬性的量綱都相同.對于存在非數值型數據的信息表,當前研究中有很多方法可以將字符型數據轉換成數值型數據,如LDA[32]等方法.對于存在不同量綱屬性的信息表,采用min-max標準化等方法對數據進行統一量綱處理即可.

例1.給定一個信息表S=(U,C∪D,V,f),其中,有限論域為U={x1,x2,x3,x4,x5,x6,x7,x8},條件屬性集合為C={c1,c2,c3,c4},目標集合為X={x1,x2,x7,x8}.例1的信息表如表2所示：

Table 2 Information Table of Example 1表2 例1的信息表

由等價關系IND(C)誘導的論域U上的劃分為UIND(C)={E1,E2,E3,E4}={{x1,x3},{x2,x4},{x5,x6},{x7,x8}}.根據式(12),可以得到目標集合中任意對象xi(xi∈X,i=1,2,…,|X|)分別與任意等價類Ej(Ej∈UIND(C),j=1,2,3,4)中任意對象的距離值(為了行文的簡潔,僅給出部分結果)：

d(V(xi),V(xi))=0,i=1,2,…,8,
d(V(x1),V(x2))=2.160 3,
d(V(x1),V(x5))=3.582 4,
d(V(x2),V(x3))=2.857 8,
d(V(x2),V(x5))=4.183 4,
d(V(x2),V(x7))=3.055 1,
d(V(x6),V(x7))=2.645 8.

然后,根據式(13),等價類E1,E2,E3,E4與目標集X之間的歐氏距離分別為

d(X,E1)=1.620 2,d(X,E2)=2.067 6,

d(X,E3)=3.648 7,d(X,E4)=1.303 9.

考慮到不同等價類與目標集之間距離的不同,則可認為等價類之間是存在差異的.因此,每個等價類對應的損失函數也應該是不同的.進一步地,借助例2闡述說明在構建綜合評價函數以度量風險時考慮等價類之間的差異性能提高分類器性能的原因.

例2.根據例1,各等價類與目標集合的歐氏距離分別為d(X,E1)=1.620 2,d(X,E2)=2.067 6,d(X,E3)=3.648 7,d(X,E4)=1.303 9. 又目標集合為X={x1,x2,x7,x8},則對于等價類E1={x1,x3} 和E2={x2,x4},其粗糙隸屬度均為Pr(X|E1)=Pr(X|E2) =0.500 0. 而由于d(X,E1)=1.620 2≠d(X,E2)= 2.067 6,所以二者與目標集的距離不同. 且d(X,E2)>d(X,E1),則相比于等價類E2,等價類E1與目標集合X更相似.換言之,盡管二者的粗糙隸屬度相同,若僅有一個等價類能夠被劃分到正域,考慮到等價類之間的差異性,相比于等價類E2,等價類E1更應該被劃分到正域.

根據例1和例2,由等價關系誘導的論域劃分中的確存在一些與目標集合之間的相似度不相同的等價類,即相對于目標集合來說,等價類之間確實存在差異.因此,在度量風險時,應該對這些等價類有所區分.另外,根據3WD-DTRSs模型[11-12],由于根據專家經驗給定的損失函數面向整個論域,即對于任意等價類,其損失函數集合均相同,從而在貝葉斯決策準則下推導的閾值并不能使得所有等價類達到全局最優劃分.

2.1 基于方差的屬性權重度量

在決策過程中,決策者一般通過綜合考慮各條件屬性而進行決策計劃的制定.因此,提出了一種獲取信息表中屬性權重的方法.給定一個信息表S=(U,C∪D,V,f),可以得到論域U中所有對象x在條件屬性ci上的取值,不妨表示為集合Vi={vi(x)|x∈U}.考慮到集合Vi的離散程度越大,則屬性ci對論域U的劃分能力越好,因此,采用方差來度量條件屬性的權重,樣本方差描述為：

設x1,x2,…,xn為取自某總體X的樣本,則它關于樣本均值的樣本方差(平均偏差平方和)為

(14)

定義4.基于方差的屬性權重. 給定一個信息系統S=(U,C∪D,V,f),其中,條件屬性集合為C={c1,c2,…,cm},目標集合為X(X?U).則對于?ci(ci∈C,i= 1,2,…,m),基于方差的屬性權重函數可定義為

(15)

例3.給定一個信息系統S=(U,C∪D,V,f),其中,論域為U={x1,x2,x3,x4,x5,x6,x7,x8},條件屬性集合為C={c1,c2,c3,c4},目標集合為X={x1,x2,x7,x8}.例3的信息表如表3所示：

Table 3 Information Table of Example 3表3 例3的信息表

根據表3,條件屬性c1對應的條件屬性值集合為V1={v1(x)|x∈U}={3,1,3,1,3,3,3,3},則根據式(14),條件屬性c1對應的條件屬性值集合V1的集合方差為var(V1)=0.857 1.同理,條件屬性c2,c3,c4對應的條件屬性值集合V2,V3,V4的集合方差分別為var(V2)=0.285 7,var(V3)=0.125 0,var(V4)=0.982 1.再根據式(15),條件屬性c1,c2,c3,c4的權重分別為

ω1=0.381 0,
ω2=0.127 0,
ω3=0.055 6,
ω4=0.436 5.

2.2 基于相似度量的風險度量

如前所述,在說明等價類與目標集合之間存在差異這個問題時,為便于簡單直接地說明問題,所采用的是簡單的歐氏距離公式.然而,在使用歐氏距離度量等價類與目標集合的差異時,會存在2個等價類與目標集合在距離上相同的情況,而實際上2個等價類所對應的屬性值集合是不同的情況.因此,為了將等價類之間由于屬性值不同而產生的差異作為一個影響因子加入到風險度量的模型中,將基于集合相似度量方法[33]給出一種考慮等價類與目標集合之間差異性的綜合評價函數以度量風險.

定義5.集合之間的相似度.[33]假設集合A和B是非空有限論域U上的2個子集,S:U×U→[0,1]是一個映射函數,即(A,B)→S(A,B).則S(A,B)是集合A和B之間的相似度函數,當且僅當S(A,B)滿足4個條件：

1) 對于?A,B?U,有0≤S(A,B)≤1；

2) 對于?A,B?U,有S(A,B)=S(B,A)；

3) 對于?A,B?U,有S(A,A)=1；

4) 對于?A,B?U,當且僅當A∩B=?時,有S(A,B)=0.

定義6.改進的相似度量函數. 給定一個信息系統S=(U,C∪D,V,f),其中,條件屬性集合為C={c1,c2,…,cm},目標集合為X(X?U). 則對于?ci(ci∈C),?Ej(Ej∈UIND(C))與目標集合X之間的改進的相似度量函數可定義為

(16)

其中,|·|表示集合的勢,Ej表示由等價關系IND(C)在有限論域U上誘導的等價類,vi(Ej)表示等價類Ej在條件屬性ci上的值,vi(x)表示任意對象x(x∈U)在條件屬性ci上的取值.

將一個本屬于目標集合的對象劃分到正域帶來的風險要小于將其劃分到邊界域所帶來的風險,且將其劃分到邊界域帶來的風險也小于將其劃分到負域帶來的風險,同理,對于一個本不屬于目標集合的對象,同樣有類似的規律.此外,對于目標集來說,任意等價類所對應的條件屬性值與之越相似,則將該等價類劃分到正域所產生的風險越小.因此,為使得評價函數滿足以上規律,不妨借用對數函數的簡潔形式,基于集合相似度量的概念,提出對條件屬性值打分的評價函數的定義.

定義7.基于相似度量的評價函數. 給定一個信息系統S=(U,C∪D,V,f),其中,條件屬性集合為C={c1,c2,…,cm},目標集合為X(X?U).則在任意劃分情況δ(δ∈H,H={PP,BP,NP,NN,BN,PN})下,對于?ci(ci∈C,i=1,2,…,m),基于相似度量的評價函數可定義為

(17)

其中,常數序列ηPP,ηBP,ηNP和ηPN,ηBN,ηNN是基于相似度量的評價函數的系數,且其須滿足：

2<ηPP<ηBP<ηNP,2<ηNN<ηBN<ηPN.

(18)

例4.給定一個信息系統S=(U,C∪D,V,f),其中,論域為U={x1,x2,x3,x4,x5,x6,x7,x8},條件屬性集合為C={c1,c2,c3,c4},目標集合為X={x1,x2,x7,x8}.信息表的具體信息如例3中的表3所示.

由等價關系IND(C)誘導的論域U上的劃分為UIND(C)={E1,E2,E3,E4}={{x1,x3},{x2,x4},{x5,x6,x7},{x8}}.根據定義6,在屬性c1上,等價類E1與目標集合X之間的改進的相似度量函數為

根據定義7,不妨將基于相似度量的評價函數的系數取為ηPP=3.000 0,ηBP=5.000 0,ηNP=9.000 0,ηNN=3.500 0,ηBN=7.000 0,ηPN=12.000 0.則根據定義7,對于條件屬性c1,在任意的劃分情況δ(δ∈H)下,等價類E1={x1,x3}與目標集X之間基于相似度量的評價函數分別為

同理,對于條件屬性c2,c3,c4,在任意劃分情況δ(δ∈H)下,等價類E1={x1,x3}與目標集X之間的改進的相似度量函數分別為

ψc3(E1,X)=0.800 0,
ψc4(E1,X)=0.600 0.

同理,對于等價類E2,E3,E4,在任意條件屬性下及任意劃分情況下,基于相似度量的評價函數都可以計算.

性質1.給定一個信息表S=(U,C∪D,V,f),其中,條件屬性集合為C={c1,c2,…,cm}.則給定?ci(ci∈C,i=1,2,…,m)的條件下,對于?Ej(Ej∈UIND(C)),基于相似度量的評價函數滿足(-,+).

證明. 因為對于 ?ci(ci∈C,i=1,2,…,m),?Ej(Ej∈UIND(C))及給定的目標集合X(?X?U),不等式0<ψci(Ej,X)≤1成立. 則當滿足條件 2<ηPP<ηBP<ηNP,2<ηNN<ηBN<ηPN時,(-,+)成立.

證畢.

值得指出的是,對于給定的條件屬性及在相同的劃分動作下,評價值越高的等價類被劃分到正域而產生的風險越小.

性質2.給定一個信息系統S=(U,C∪D,V,f),對于?Ej(Ej∈UIND(C)),?ci(ci∈C,i=1,2,…,m),如果常數序列滿足條件(ηPN-ηBN)(ηNP-ηBP)>(ηBP-ηPP)(ηBN-ηNN),則基于相似度量的評價函數滿足不等式

證畢.

性質3.給定一個信息系統S=(U,C∪D,V,f),對于?Ej(Ej∈UIND(C)),?ci(ci∈C,i=1,2,…,m),如果常數序列滿足不等式 (ηPN-ηBN)(ηNP-ηBP)<(ηBP-ηPP)(ηBN-ηNN),則基于相似度量的評價函數滿足不等式

證明. 證明過程類似于性質2.

決策者在做決策時一般是綜合考慮每個對象的各條件屬性,因此根據定義7,給出以下綜合評價函數,以綜合各條件屬性的評價值.

定義8.綜合評價函數.給定一個信息表S=(U,C∪D,V,f),其中,條件屬性集合為C={c1,c2,…,cm},目標集合為X(X?U). 則對于 ?Ej(Ej∈UIND(C)),任意劃分情況δ(δ∈H)下的綜合評價函數可以定義為

(19)

例5.根據例4,對于任意條件屬性ci(ci∈C),已得到在任意劃分情況δ(δ∈H)下,任意等價類Ej(Ej∈UIND(C))與目標集合X間的評價值.如對于等價類E1,相應的評價值為

根據例3,屬性c1,c2,c3,c4的權重分別為ω1=0.381 0,ω2=0.127 0,ω3=0.055 6,ω4=0.436 5.因此,對于E1={x1,x3},在不同的劃分情況δ(δ∈H)下的綜合評價值分別為

μPP(E1)=2.582 4,μBP(E1)=3.604 1,
μNP(E1)=4.779 7,μNN(E1)=2.890 8,
μBN(E1)=4.277 0,μPN(E1)=5.355 0.

性質4.給定一個信息系統S=(U,C∪D,V,f),對于?Ej(Ej∈UIND(C))及?ci(ci∈C,i=1,2,…,m),若成立,則(μPN(Ej)-μBN(Ej))×(μNP(Ej)-μBP(Ej))-(μBP(Ej)-μPP(Ej))(μBN(Ej)-μNN(Ej))成立.

證明. 因為

從而 (μPN(Ej)-μBN(Ej))(μNP(Ej)-μBP(Ej))>(μBP(Ej)-μPP(Ej))(μBN(Ej)-μNN(Ej))成立.

證畢.

2.3 SBA-3WD-SF模型閾值推導

根據決策粗糙集模型[11-12],SBA-3WD-SF模型同樣有2個狀態T={X,X}及3個動作A={aP,aB,aN},則相應的綜合評價函數可由表4表示：

Table 4 Comprehensive Evaluation Function表4 綜合評價函數

根據貝葉斯決策過程[11],采取不同動作aP,aB,aN時,對于?Ej(Ej∈UIND(C)),基于相似度量的期望風險分別為

R(aP|Ej)=μPPPr(X|Ej)+μPNPr(X|Ej),

R(aB|Ej)=μBPPr(X|Ej)+μBNPr(X|Ej),

R(aN|Ej)=μNPPr(X|Ej)+μNNPr(X|Ej).

(20)

根據貝葉斯決策準則,使得期望風險最小的一套動作,便是最優劃分計劃.從而,可得到3條決策規則：

(P)如果R(aP|Ej)≤R(aB|Ej)且R(aP|Ej)≤R(aN|Ej),則Ej?POS(X)；

(B)如果R(aB|Ej)≤R(aP|Ej)且R(aB|Ej)≤R(aN|Ej),則Ej?BND(X)；

(N)如果R(aN|Ej)≤R(aP|Ej)且R(aN|Ej)≤R(aB|Ej),則Ej?NEG(X).

這3條決策規則只與判別函數Pr(X|Ej)及各綜合評價函數有關.根據定義6及性質2,各綜合評價函數滿足條件μPP(Ej)<μBP(Ej)<μNP(Ej),μNN(Ej)<μBN(Ej)<μPN(Ej).因此,在此大小關系的前提下,使得決策風險最小的決策規則表示為

進一步,為了得到決策規則的簡約形式,簡記處理為

(21)

根據性質4,則有不等式：

而因為不等式：

成立,則有不等式:

成立,即0≤βj<γj<αj≤1成立.因此,規則(P)(B)(N)可以等價地表示為

(P)如果Pr(X|Ej)≥αj,則Ej?POS(X);

(B)如果βj

(N)如果Pr(X|Ej)≤βj,則Ej?NEG(X).

綜上所述,根據決策規則,給出了一個閾值自適應的三支決策分類器.

2.4 算法步驟

根據2.1～2.3節,所提模型的基本步驟可由算法1,2,3表示.在算法1,2,3中,m表示條件屬性的個數,ωi(i=1,2,…,m)表示每個條件屬性的權重.δ(δ∈H)表示任意劃分情況.Ej表示由等價關系IND(C)在論域U上誘導的劃分UIND(C)中的任意等價類,s表示UIND(C)中的元素個數.pos,bnd,neg分別表示正域、邊界域及負域.

算法1.計算每個條件屬性的權重.

輸入:S=(U,C∪D,V,f);

輸出:ωi.

① fori=1 tom

Temp+=var(Vi);

② end for

③ fori=1 tom

④ end for

算法2.構造綜合評價函數.

輸入:S=(U,C∪D,V,f),X,ωi,ηδ;

輸出:μδ(Ej).

① for eachci∈C

for eachEj∈UIND(C)

ψci(Ej,X)=

② end for

③ end for

④ fori=1 tom

while 2<ηPP<ηBP<ηNP&& 2<ηNN<

ηBN<ηPN&& (ηPN-ηBN)(ηNP-ηBP)>

(ηBP-ηPP)(ηBN-ηNN) do

⑥ end while

⑦ end for

算法3.計算模型的分類準確率(acc)及召回率(recall).

輸入:S=(U,C∪D,V,f),X,μδ(Ej);

輸出:acc,recall.

① 初始化pos=?,bnd=?,neg=?.

② forj=1 tos

and

③ ifPr(X|Ej)≥αjthen

④pos←pos∪Ej;

⑤ else ifβj

⑥bnd←bnd∪Ej;

⑦ elseneg←neg∪Ej;

⑧ end if

⑨ end for

通過分析算法1,2,3,所提算法的時間復雜度為T(n)=O(n2).因此,所提算法在現實生活中是有效可行的.

3 對比實驗

3.1 實驗指標

在垃圾郵件過濾領域,用戶通常關心的是郵件正確分類數量占總體郵件的比例.當前評價垃圾郵件過濾器性能的方法中,常用的評價指標為準確率(acc)及召回率(recall)等[34].

3.1.1 準確率

對于垃圾郵件過濾器,垃圾郵件被分到垃圾郵件類及合法郵件被分到合法郵件類的數量占郵件總量比例越高,則該過濾器的性能越好.因此,不妨采用準確率來衡量過濾器的性能.

(22)

其中,ns→s表示實為垃圾郵件的對象被分為垃圾郵件類的數量,nl→l表示實為合法郵件的對象被分為合法郵件的數量,|U|表示論域中的所有郵件的數量.

3.1.2 召回率

對于垃圾郵件過濾器,垃圾郵件被劃分到垃圾郵件類的占實際垃圾郵件比例越高,則說明該過濾器對垃圾郵件的識別能力越好,即過濾器的性能也越好.因此,不妨采用召回率來衡量過濾器的性能.

(23)

其中,Ns表示實為垃圾郵件的對象個數.

3.2 數據預處理與參數設置

相較于傳統的二分類模型,由于三支決策模型增加了延遲決策域,則其能有效降低錯誤分類代價,從而有效提高分類的準確率.特別地,相較于3WD-DTRSs模型[11],所提的SBA-3WD-SF模型能提高準確率及召回率.為了驗證這一點,使用當前垃圾郵件過濾研究領域的2個常用數據集,其一是來自UCI機器學習數據資料庫的Spambase數據集,其二是來自文獻[35]提供的PU1 Corpus數據集,二者的基本信息如表5所示：

Table 5 Basic Information of Datasets表5 數據集基本信息

對于Spambase數據集,實驗隨機選取了3 000個樣本作為訓練數據集,剩下的1 601個樣本作為測試數據集.首先,采用Entropy-MDL方法[36]對訓練數據集及測試數據集進行離散化處理,然后選用條件互信息最大化法[37]對數據集進行特征選擇,從57個條件屬性中選取了20個條件屬性.對于PU1 Corpus數據集,由于該語料庫本身已被分為10個部分,因此實驗隨機選取了其中的8個部分作為訓練數據集,剩下的2個部分作為測試數據集.進一步采用基于互信息的單變量特征提取方法(KBest feature selection)對數據集進行特征選擇,并依據互信息最大化原則,選擇了前200個條件屬性.

為測試模型的性能,針對3WD-DTRSs模型[11]及所提SBA-3WD-SF模型,實驗分別隨機給出了5組參數如表6及表7所示.根據1.2節中二元NB分類器[30]的原理,其模型的閾值相應地可擴展表示為ξ=λNPλPN,如表8所示.

Table 6 Loss Functions of 3WD-DTRSs Model[11]表6 3WD-DTRSs模型[11]的損失函數

Table 7 Coefficients of Evaluation Functions Based onSimilarity Measure

Table 8 Threshold of Binary NB Classifier[30]表8 二元NB分類器[30]的閾值

3.3 實驗結果與分析

首先,針對分類器的準確率,SBA-3WD-SF模型與二元NB分類器[30]及3WD-DTRSs模型[11]在數據集Spambase上的表現分別如圖2(a)(b)所示.從圖2(a)(b)中可以發現在Spambase數據集上,3WD-DTRSs模型及SBA-3WD-SF模型的分類準確率均優于二元NB模型,且SBA-3WD-SF模型要優于3WD-DTRSs模型.另外,如圖3(a)(b)所示,可以發現3WD-DTRSs模型及SBA-3WD-SF模型的分類準確率均優于二元NB模型,且SBA-3WD-SF模型的分類準確率優于3WD-DTRSs模型.

其次,針對分類器的召回率,SBA-3WD-SF模型與二元NB分類器及3WD-DTRSs模型在數據集PU1 Corpus上的表現分別如圖3(c)及圖3(d)所示.在PU1 Corpus數據集上,3WD-DTRSs模型及SBA-3WD-SF模型的召回率均優于二元NB模型,且SBA-3WD-SF模型的召回率要優于3WD-DTRSs模型.在Spambase數據集上,如圖2(c)(d)所示,3WD-DTRSs模型及SBA-3WD-SF模型的召回率均優于二元NB模型,且SBA-3WD-SF模型的召回率要優于3WD-DTRSs模型.

Fig. 3 Results of comparative experiments on PU1 Corpus圖3 PU1 Corpus數據上的對比結果

在表6～8中的任意參數條件下,3WD-DTRSs模型[11]及SBA-3WD-SF模型在Spambase或PU1 Corpus數據集上的分類準確率及召回率都要優于二元NB模型[30],且SBA-3WD-SF模型無論在分類準確率還是召回率上也同樣明顯優于3WD-DTRSs模型.而表6～8中的參數都是隨機給定的,因此根據極大似然法原理,3WD-DTRSs模型及SBA-3WD-SF模型的分類準確率及召回率優于二元NB模型,且SBA-3WD-SF模型無論在分類準確率還是召回率上也同樣明顯優于3WD-DTRSs模型.

特別地,由于NB分類器為了求解后驗概率而采用了特征條件獨立性假設這一嚴格的條件,因此該模型犧牲了一定的分類準確率.值得指出的是,如圖3(c)所示,NB模型的魯棒性較差,而3WD-DTRSs及SBA-3WD-SF模型則具有良好的魯棒性.此外,SBA-3WD-SF模型在3WD-DTRSs模型的基礎上,在進行風險度量時考慮了等價類之間差異帶來的影響,因此,在理論上,SBA-3WD-SF模型的分類準確率及召回率都優于3WD-DTRSs模型.而對于二分類及三支決策來說,從理論上,相較于二分類模型,三支決策模型由于增加了延遲決策域而能有效降低分類風險代價,從而提高模型的分類準確率及召回率等.從實驗結果上來看,由圖2和圖3可知在2個垃圾郵件分類的數據集上,SBA-3WD-SF模型及3WD-DTRSs模型的分類準確率及召回率的確都優于二元NB模型,SBA-3WD-SF模型也要明顯優于3WD-DTRSs模型.此外,由圖2(b)(d)、圖3(b)(d)可以發現,在Spambase或者PU1 Corpus數據集上,所提模型SBA-3WD-SF相較于3WD-DTRSs模型來說,分類準確率及召回率提高的幅度沒有特別大,而在垃圾郵件過濾領域,即使只有一封郵件被錯誤分類都會產生不可估量的代價.因此,在垃圾郵件過濾領域,SBA-3WD-SF模型具有顯著的價值.

4 結語

垃圾郵件分類中分類準確率及召回率等是用戶最為關注的問題.相較于二分類模型,增加了延遲決策域的三支決策模型能有效降低錯分代價,從而提高分類準確率及召回率.通過度量等價類與目標集的距離,發現相對于目標集合來說,等價類之間的確存在差異.因此,在3WD-DTRSs模型的基礎上提出了一種基于相似度量的閾值自適應三支垃圾郵件過濾模型.首先根據集合方差提出了一種計算條件屬性權重的方法,然后考慮等價類之間的差異性帶來的影響,基于等價類之間的相似度重新構建了綜合評價函數,然后依據貝葉斯決策準則推導出自適應閾值.在垃圾郵件過濾領域,過濾器的性能至關重要.對比實驗表明所提SBA-3WD-SF模型在分類準確率及召回率等指標上都優于3WD-DTRSs模型[11]及二元NB模型[30],即驗證了SBA-3WD-SF模型的合理性及有效性,同時也說明了SBA-3WD-SF模型在垃圾郵件過濾領域的價值.值得提出的是,除了損失函數,影響垃圾郵件過濾器的性能的因素有很多,如判別函數及參數的求解方式等.因此,今后的研究工作將重點關注判定函數的合理構建及更優的參數求解方式.