基于三支決策模型的代價敏感數(shù)據(jù)分類方法

孫海霞,許厚棣

(1.安徽三聯(lián)學院，計算機工程學院，安徽 合肥，230601； 2.駐中國電科三十八所軍事代表室，安徽 合肥，230088)

三支決策模型[1]是加拿大著名學者Yao在2009年提出的一種決策理論，該模型是在傳統(tǒng)的二支決策理論[2]基礎上的進一步推廣。三支決策模型將決策的結果分為三種形式，分別為接受決策、拒絕決策和延遲決策，對于目前已有的信息不能判斷決策對象是否接受或拒絕，三支決策便將這種情況判定為延遲決策，即等待進一步分析[1-2]。由于這種決策模式的新穎性，三支決策理論的提出便立即成為決策分析領域的一個研究熱點。

經(jīng)過這幾年的不斷研究，三支決策模型目前已經(jīng)得到了大量的推廣和應用。Sun等[3]學者在復雜數(shù)據(jù)環(huán)境下提出了一種組決策模型的三支決策方法；Xu等[4]學者將三支決策運用于流計算方面，提出了一種基于三支決策的流計算學習；在聚類方面，Yu等[5]學者根據(jù)三支決策給出一種確定聚類數(shù)量的方法，并且進一步提出了數(shù)據(jù)的三支決策聚類[6]；Zhang等[7]學者根據(jù)三支決策模型提出了三支個性化推薦算法；在其他應用領域，Nauman等[8]學者將三支決策模型運用于軟件的測試和分析；謝騁等[9]學者運用三支決策提出一種視頻異常行為檢測方法；Zhou等[10]學者運用三支決策用于郵箱垃圾郵件的檢測；李建林等[11]學者將三支決策運用于垃圾短信的判別和分析；張越兵等[12]學者將三支決策運用于自然語言處理中，提出一種文本的情感分類方法?？傊壳暗娜Q策模型已經(jīng)應用于各個信息領域之中。

三支決策作為一種優(yōu)越的決策模型，然而目前很少運用于數(shù)據(jù)的分類中，因此在文中根據(jù)三支決策提出一種代價敏感的數(shù)據(jù)分類方法，首先根據(jù)三支決策模型，提出一種新的誤分類代價定義，并且提出啟發(fā)式搜索的最小化誤分類代價特征選擇算法，根據(jù)該特征選擇算法得到的特征子集，進一步提出三支決策模型的代價敏感數(shù)據(jù)分類算法，該算法將分類結果分成三個部分，即標記為特定類、不標記為特定類以及暫不標記，使得分類的結果更加具體明確。最后通過仿真實驗，驗證了文中所提出的算法具有更高的分類性能。

1 三支決策模型

在分類學習等任務中，數(shù)據(jù)集一般表示成S=(U,At),其中U為整個數(shù)據(jù)集S的樣本集,?x∈U稱為樣本集U中的樣本,At為整個數(shù)據(jù)集的特征集。對于一個標記類別的數(shù)據(jù)集表示為S=(U,At=C∪d),這里的U同樣為整個數(shù)據(jù)集S的樣本集,C稱為特征集At中的條件特征集，d為類特征，那么U中的樣本x可以表示為〈x,y〉，其中y為樣本x的類標記。

對于二分類問題，設分類的結果包含兩個類別Ω={Cl,～Cl},三支決策將分類的結果表示成動作集A={aP,aB,aN},其中aP、aB和aN分別表示樣本被分類為類別Cl的正區(qū)域POS(Cl)、邊界域BUN(Cl)和負區(qū)域NEG(Cl)。當樣本原本屬于類別Cl,而被分類進Cl的正區(qū)域、邊界域和負區(qū)域所產(chǎn)生的代價分別為λPP、λBP和λNP;當樣本原本不屬于類別Cl，而被分類進Cl的正區(qū)域、邊界域和負區(qū)域所產(chǎn)生的代價分別為λPN、λBN和λNN，這些類別代價可以構成一個代價矩陣，具體如表1所示[1]。

表1 分類代價矩陣
Table1Classifiedcostmatrix

原本類別POS(Cl)BUN(Cl)NEG(Cl)ClλPPλBPλNP～ClλPNλBNλNN

根據(jù)表1中各類情形的分類代價矩陣，可以得到進行三種決策時的決策代價。對于樣本x,類別集Ω={Cl,～Cl},樣本x進行aP、aB和aN三種決策動作的預期代價分別為

c(aP|x)=λPP·P(Cl|x)+λPN·P(～Cl|x);

c(aB|x)=λBP·P(Cl|x)+λBN·P(～Cl|x);

c(aN|x)=λNP·P(Cl|x)+λNN·P(～Cl|x)。

這里的P(Cl|x)表示樣本x關于類別Cl的條件概率，即樣本對類別Cl的隸屬程度。c(aP|x)、c(aB|x)和c(aN|x)即為樣本分類入類別Cl的正區(qū)域、邊界域和負區(qū)域時所產(chǎn)生的分類代價。

Yao認為在三種決策動作中，分類代價最小的決策行為即為最佳的決策，因此Yao根據(jù)這一思想提出了三支決策規(guī)則[1-2]，即：

1)如果c(aP|x)

2)如果c(aB|x)

3)如果c(aN|x)

三支決策模型表明，如果樣本x分類入類別Cl正區(qū)域的代價是最小的，那么就直接將樣本x分類入類別Cl。如果樣本x分類入類別Cl負區(qū)域的代價是最小的，那么就直接將樣本x分類入類別～Cl。如果樣本x分類入類別Cl邊界域的代價是最小的，那么三支決策模型認為樣本x的分類情況不確定，因此對于樣本x進行延遲決策并作進一步分析[1-2],正是由于這種延遲決策，使得三支決策模型在決策應用中具有更好的優(yōu)越性[2]。

2 三支決策模型的代價敏感數(shù)據(jù)分類

根據(jù)三支決策模型的決策模式，文章將提出一種三支決策的數(shù)據(jù)分類方法。

在數(shù)據(jù)分類任務中，數(shù)據(jù)集中大量的特征不僅影響了分類算法的學習效率，而且數(shù)據(jù)集中的很多特征包含了冗余和不相關的信息，這些特征的存在不利于分類算法的分類性能[13]。為了改善這類問題，常用的處理方法便是特征降維，即特征選擇[14]。在文章中首先提出一種最小化誤分類代價的特征選擇算法，然后進一步的提出三支決策的代價敏感數(shù)據(jù)分類。

2.1 最小化誤分類代價特征選擇

對于二分類問題,設類標記數(shù)據(jù)集為S=(U,C∪d)，給定樣本x和特征子集B?C，類別劃分為Ω={Cl,～Cl}，類別Cl的代價矩陣如表1所示，令給定樣本x在特征子集B下的三支決策結果為ΓB(x)?；谶@個結果提出三支決策模型下樣本x的誤分類代價mcB(x)，其定義為

1)當ΓB(x)=POS(Cl)，那么mcB(x)=λPN·PB(～Cl|x);

2)當ΓB(x)=BUN(Cl)，那么mcB(x)=λBP·PB(Cl|x)+λBN·PB(～Cl|x);

3)當ΓB(x)=NEG(Cl)，那么mcB(x)=λNP·PB(Cl|x)。

這里的PB(Cl|x)和PB(～Cl|x)分別表示樣本x關于類別Cl和～Cl在特征子集B下的條件概率。根據(jù)三支決策模型，若樣本x判定為類別Cl，那么誤分類代價即為樣本x原先屬于類別～Cl而判定為類別Cl時所付出的代價，因此代價結果為λPN·PB(～Cl|x)。同理若樣本x判定為類別～Cl，那么誤分類代價即為樣本x原先屬于類別Cl而判定為類別～Cl時所付出的代價。若樣本x判定結果為進一步分析，那么誤分類代價為x原先屬于類別Cl或x原先屬于類別～Cl時兩種情況代價之和。

在誤分類代價的計算中，代價矩陣是一個事先給定的常量，因此誤分類代價的結果取決于條件概率PB(Cl|x)和PB(～Cl|x)。對于給定的樣本x和類別劃分Ω={Cl,～Cl}，不同特征子集B下，將有不同的PB(Cl|x)和PB(～Cl|x)值，因此可以看出誤分類代價的大小與特征子集B直接相關?？紤]S=(U,C∪d)的代價敏感分類，目標是對于特征集C尋找出一個特征子集B′，使得樣本空間U中所有對象的誤分類代價之和最小，具體如定義1所示。

定義1 對于數(shù)據(jù)樣本集S=(U,C∪d),類別劃分為Ω={Cl,～Cl},并且類別的代價矩陣如表1所示。若特征子集B′?C是樣本集S的一個最小誤分類代價特征子集，那么必須同時滿足：

定義1表明，找到最小誤分類代價特征子集B′可以通過遍歷特征集C的所有子集來實現(xiàn)，當特征集C規(guī)模較小時，可以采用這種方法，但是當特征集C規(guī)模較大時，其求解的計算量非常巨大，因而這種方法不再適用。求解特征子集通常采用啟發(fā)式搜索的方法來逼近理論結果[14],文章在其他學者相關研究的基礎上[14-15]，提出一種特征重要度的啟發(fā)式函數(shù)，用于特征選擇結果的啟發(fā)式搜索。

sigB(a)=MC(B)-MC(B∪{a})。

根據(jù)定義2中關于特征重要度的啟發(fā)式函數(shù)，可以進一步的提出基于啟發(fā)式的最小誤分類代價特征選擇算法，具體算法如圖1所示。

輸入:數(shù)據(jù)樣本集S=(U,C∪d),類別代價矩陣 輸出:最小誤分類代價特征子集BStep1:初始化B=?,對特征集C中的每個特征計算誤分類代價,選擇誤代價最小的特征加入B中,即B=B∪argmin?a∈CMC({a})。Step2:對于?a∈C-B,計算特征a的重要度sigB(a)=MC(B)-MC(B∪{a})。Step3:找出Step2中sigB(a)值最大的特征,記為a。Step4:判斷sigB(a)值的大小,若sigB(a)>0那么B=B∪{a},并重新進入Step2,若sigB(a)≤0,那么進入Step5。Step5:返回特征子集B

圖1最小誤分類代價特征選擇算法

Fig.1The feature selection algorithm of minimum misclassification cost

圖1中算法是一個貪心選擇的過程，算法在每輪的迭代過程中，通過選取局部最優(yōu)值來確定特征，直到在候選特征集中沒有能使總誤分類代價進一步減小的特征時，此時終止算法，輸出特征子集結果。

2.2 三支決策模型的代價敏感數(shù)據(jù)分類

在2.1節(jié)中，提出了最小誤分類代價特征選擇算法，接下來在其基礎上提出三支決策模型的代價敏感數(shù)據(jù)分類方法。

對于樣本對象x,類別代價矩陣如表1所示，可以得到：

若c(aP|x)

λPP·P(Cl|x)+λPN·P(～Cl|x)≤λBP·P(Cl|x)+λBN·P(～Cl|x)
λPP·P(Cl|x)+λPN·P(～Cl|x)≤λNP·P(Cl|x)+λNN·P(～Cl|x)

若c(aB|x)

λBP·P(Cl|x)+λBN·P(～Cl|x)≤λPP·P(Cl|x)+λPN·P(～Cl|x)
λBP·P(Cl|x)+λBN·P(～Cl|x)≤λNP·P(Cl|x)+λNN·P(～Cl|x)

若c(aN|x)

λNP·P(Cl|x)+λNN·P(～Cl|x)≤λPP·P(Cl|x)+λPN·P(～Cl|x)
λNP·P(Cl|x)+λNN·P(～Cl|x)≤λBP·P(Cl|x)+λBN·P(～Cl|x)

由于P(Cl|x)=1-P(～Cl|x),所以

1)若P(Cl|x)≥α且P(Cl|x)≥γ，那么x分類入POS(Cl);

2)若P(Cl|x)<α且P(Cl|x)>β，那么x分類入BUN(Cl);

3)若P(Cl|x)≤β且P(Cl|x)≤γ，那么x分類入NEG(Cl)。

這里的

根據(jù)上面一系列的推導可以發(fā)現(xiàn)，在給定類別代價矩陣的基礎上，只需要計算樣本x關于類別Cl的條件概率，將這個條件概率與閾值α,β和γ之間進行比較便可以判定x與Cl之間的關系，即樣本x是否標記為類別Cl或不作分類進一步分析。因此接下來最關鍵的問題是研究樣本與類別之間條件概率的估計，文中采用文獻[16]的處理方法，通過類別占據(jù)樣本鄰域的比重來進行評估概率。

定義3[16]對于數(shù)據(jù)樣本S=(U,C∪d),特征子集B?C，并且B中的離散型特征集表示為B1，連續(xù)型特征集表示為B2，那么樣本x∈U在特征子集B下的鄰域樣本集定義為

δB(x)={y∈U|dB2(x,y)≤δ∧(?b∈B1,xb=yb)}

其中xb和yb分別表示樣本x和y在特征b下的取值，dB2(x,y)表示樣本x和y的距離度量，δ為鄰域半徑。

解決條件概率的計算問題后，另一個需要解決的問題是，文章之前的假設全部基于二分類問題進行討論，而現(xiàn)實中的分類問題一般都是多分類的，對于這類情形，可以將多分類問題轉化為二分類情形進行分析。對于多分類問題，若樣本數(shù)據(jù)的類別劃分為Ω={Cl1,Cl2,…,Clm}，需要對每個類別Cli設定分類代價矩陣，如表2所示。

表2 類別Cli代價矩陣
Table2ThecostmatrixofclassCli

原本類別POS(Cli)BUN(Cli)NEG(Cli)CliλiPPλiBPλiNP～CliλiPNλiBNλiNN

根據(jù)多分類情形下各個類別的代價矩陣，便可以給出基于三支決策模型的數(shù)據(jù)分類方法，具體算法如圖2所示。

輸入:樣本數(shù)據(jù)集S=(U,C∪d),類別劃分Ω={Cl1,Cl2,…,Clm},類別Cli(1≤i≤m)的代價矩陣,算法1選擇出的特征子集B,待標記類別的測試樣本x;輸出:測試樣本x的類標記。Step1:初始化類別序號k=0。Step2:根據(jù)類別Cli(1≤i≤m)的代價矩陣計算出對應的閾值αi,βi和γi。Step3:k=k+1,并計算測試樣本x關于Clk的條件概率P(Clk|x)。Step4:若P(Clk|x)≥αk且P(Clk|x)≥γk,那么進入Step5;若P(Clk|x)<αk且P(Clk|x)>βk,那么進入Step6;若P(Clk|x)≤βk且P(Clk|x)≤γk,那么進入Step3。Step5:將測試樣本x標記為類別Clk,算法終止。Step6:對測試樣本x暫不進行類別標記并作進一步分析,算法終止。

圖2三支決策模型的代價敏感數(shù)據(jù)分類算法
Fig.2The cost-sensitive data classification algorithm of three-way decision models

圖2中算法相當于將測試樣本x對類別劃分Ω={Cl1,Cl2,…,Clm}中每個類別進行三支決策分析。算法剛開始時，首先將x對{Cl1,～Cl1}進行判別，如果P(Cl1|x)≥α1且P(Cl1|x)≥γ1,那么將樣本x標記為Cl1；如果P(Cl1|x)<α1且P(Cl1|x)>β1,那么延遲樣本x的判別；如果P(Cl1|x)≤β1且P(Cl1|x)≤γ1,那么將測試樣本x判別為～Cl1，由于～Cl1=Cl2∪Cl3…∪Clm，因此需要重復如上步驟在{Cl2,～Cl2}中進行分析，然后一直按照這樣的流程最后便可以確定x的分類情況。

3 實驗分析

在本節(jié)中將所提出的三支決策模型的代價敏感分類算法與支持向量機分類算法(SVM)、樸素貝葉斯分類算法(NB)以及決策樹分類算法(C4.5)對同一組數(shù)據(jù)集進行分類學習，然后比較他們的分類結果性能，從而驗證文中算法的有效性。實驗中所運用的6個UCI數(shù)據(jù)集如表3所示。

表3 實驗數(shù)據(jù)集
Table3Experimentaldataset

編號數(shù)據(jù)集樣本特征類1glass214962wdbc5693023credit6901524car1728645abalone41778296chess28056618

3.1 實驗設置

在進行實驗之前，首先介紹本實驗相關的實驗設置問題。文中所提出的分類算法中，樣本關于類別的條件概率估計至關重要，文中通過樣本的鄰域樣本集在類別上占據(jù)的比重作為條件概率的計算，其中涉及一個參數(shù)，即鄰域半徑δ。在文獻[17]中，徐波等學者提出了一種自適應的鄰域半徑設定方式。

對于連續(xù)型特征子集B={b1,b2,…,bc},設特征子集B下的鄰域半徑集為εB={εb1,εb2,…,εbc},其中

本實驗同樣采用徐波等[17]學者的方法進行鄰域半徑的設定，并將調整參數(shù)ω的值取為2進行實驗。

在算法2中，樣本數(shù)據(jù)中每個類別都需要設定代價矩陣,對于Ω={Cl1,Cl2,…,Clm},Cli的分類代價矩陣設置如表4所示。

表4 類別Cli代價矩陣設置
Table4ThesettingofthecostmatrixofclassCli

原本類別POS(Cli)BUN(Cli)NEG(Cli)CliλiPP=0λiBP∈[0,1]λiNP=3λiBP～CliλiPN=3λiBNλiBN∈[0,1]λiNN=0

3.2 實驗結果分析

文中將參與實驗的所有分類算法按照十折交叉的方式對表3中的各個數(shù)據(jù)集進行分類實驗。設nPP表示被分類正確的樣本數(shù)量，nBP表示被延遲分類的樣本數(shù)量，nNP表示被錯誤分類的樣本數(shù)量，那么分類準確率accuracy和分類覆蓋率coverage分別表示為

進一步可以得到F-measure為

文中所提出的三支決策模型分類算法為TWD，表5所示的是四種分類算法在各個數(shù)據(jù)集下的分類準確率，其中結果采用“均值±標準差”的格式來表示。觀察表5可以看出，文中所提出的TWD分類算法在大部分數(shù)據(jù)集中具有更高的分類準確率，這主要是由于TWD在傳統(tǒng)分類方法的基礎上建立了一種延遲決策的方式，在分類中對于模棱兩可的對象給予暫不分類的處理，這樣減小了數(shù)據(jù)誤分類的樣本數(shù)量，提高了分類準確率。而在少部分數(shù)據(jù)集中，其他分類算法的準確率更高一點，例如SVM分類算法在數(shù)據(jù)集wdbc上的分類準確率更高，C4.5分類算法在chess上的分類準確率更高。這主要是由于在wdbc數(shù)據(jù)集中，每個特征均為連續(xù)型的，并且只有兩個類別，SVM作為一種建立在統(tǒng)計學習基礎上的分類模型，對于這類問題具有更好的分類效果。而對于數(shù)據(jù)集chess，其每個特征均為離散類型的，C4.5算法是一種基于決策樹的分類算法，僅適用于離散型數(shù)據(jù)的分類，同時對離散型數(shù)據(jù)也具有較好的分類效果，因此C4.5算法在數(shù)據(jù)集chess上的分類準確率稍高。不過仔細比較一下可以發(fā)現(xiàn)，在數(shù)據(jù)集wdbc和chess中，TWD分類算法的準確率也僅次于最高的分類準確率，因此可以看出TWD分類算法同樣具有較高的分類性能。

表5 各個分類算法分類結果的準確率比較
Table 5 Comparison of the accuracy of the classification results of each classification algorithm

分類算法各數(shù)據(jù)集分類準確率glasswdbccreditcarabalonechessSVM0.6256±0.01240.9846±0.00630.8257±0.00550.8694±0.01470.9656±0.00390.7636±0.0125NB0.6628±0.00850.9551±0.00730.8157±0.00670.8519±0.01180.9282±0.00760.7573±0.0198C4.50.6852±0.01450.9372±0.01060.7974±0.01000.8369±0.01430.9551±0.00540.7965±0.0187TWD0.7185±0.00760.9673±0.00820.8414±0.00470.8864±0.01220.9762±0.00270.7752±0.0128

表6所示的是四種分類算法在各個數(shù)據(jù)集下的F-measure值，其結果同樣采用“均值±標準差”的格式來表示，觀察表6可以看出，TWD分類算法的F-measure值均比其余三種算法要低，這主要是由于在TWD分類算法中，由于有樣本延時分類情況的存在，因此分類覆蓋率coverage的值小于1，而其余三種算法的分類覆蓋率coverage的值等于1，因此TWD分類算法的F-measure值會偏低一點。

表6 各個分類算法分類結果的F-measure比較
Table 6 F-measure comparison of classification results of each classification algorithm

分類算法各數(shù)據(jù)集分類F-measure值glasswdbccreditcarabalonechessSVM0.8337±0.00540.9723±0.00610.8435±0.00640.8747±0.01410.9734±0.01190.8025±0.0112NB0.8416±0.00650.9455±0.00430.8271±0.01170.8994±0.01260.9417±0.00850.7924±0.0152C4.50.8873±0.01050.9638±0.00760.8054±0.00920.8564±0.01210.9535±0.01240.7865±0.0147TWD0.8273±0.00610.9538±0.00420.8244±0.01170.8543±0.01020.9525±0.00770.7652±0.0088

在基于代價敏感的分類算法中，誤分類代價是衡量分類性能的又一重要指標。表7所示的是四種算法分類結果的誤分類代價，觀察表7可以看出，文中所提出的TWD分類算法在所有數(shù)據(jù)集上具有最小的誤分類代價，這主要是由于兩個方面，第一是TWD分類算法在進行分類之前，已對樣本數(shù)據(jù)進行了最小化誤分類代價的特征選擇，然后利用選擇后的特征子集進行數(shù)據(jù)分類，從而使得整體的誤分類代價很低，另一方面，TWD分類算法的分類結果中包含延遲決策的分類情形，即對于分類不確定的樣本進行了延遲分類，進一步降低了最終分類結果的誤分類代價，因此綜合起來TWD算法具有更小的誤分類代價。

表7 各個分類算法分類結果的誤分類代價比較
Table 7 Comparison of misclassification cost for classification results of each classification algorithm

分類算法各數(shù)據(jù)集分類誤分類代價glasswdbccreditcarabalonechessSVM35.63±13.536.84±3.1716.55±2.55156.46±15.47165.63±9.592836.96±20.25NB25.82±11.867.95±4.2315.78±3.43144.28±10.18189.27±10.763164.25±27.98C4.531.47±11.259.67±5.1213.51±4.25134.46±11.44175.39±12.202465.86±22.47TWD22.56±10.165.63±2.2611.48±3.28121.46±13.62150.63±11.242352.51±28.28

根據(jù)以上相關的實驗結果，可以證明文中所提出的三支決策模型的分類算法具有更好的代價敏感分類效果。

4 總結

三支決策是近年來提出的一種新形式的決策理論模型，它通過對決策結果引入一種延遲決策的方式，使得更加適用于現(xiàn)實環(huán)境下決策應用。在文中三支決策模型的基礎上提出一種代價敏感的數(shù)據(jù)分類算法。首先根據(jù)三支決策模型，提出了數(shù)據(jù)分類問題中的誤分類代價，并基于啟發(fā)式搜索提出了數(shù)據(jù)集的最小化誤分類代價的特征選擇算法，然后根據(jù)該特征選擇算法得到的特征子集，提出基于三支決策模型的數(shù)據(jù)分類算法，該算法在數(shù)據(jù)分類過程中，加入了一種延遲分類的結果形式，使得提高了數(shù)據(jù)的分類性能，實驗分析表明該分類算法具有更高的分類優(yōu)越性。在將來的研究中，可以致力于更加復雜數(shù)據(jù)環(huán)境下三支決策模型的分類應用。