面向混合數據的代價敏感三支決策邊界域分類方法

周陽陽，錢文彬,2，王映龍，彭莉莎，曾武序

（1.江西農業大學 計算機與信息工程學院，江西 南昌 330045;2.江西農業大學 軟件學院，江西 南昌 330045;3.南京大學 工程管理學院，江蘇 南京 210046）

三支決策是加拿大學者Yao[1-2]提出的一種“化繁為簡”決策理論，它從粒計算視角將論域劃分為三個互不相交的論域子空間，并對其分別采取不同的應對策略，這種分而治之的思想，可有效提高決策準確度，降低誤分類代價。三支決策理論模擬人類認知、學習和決策的過程，可處理決策過程中出現的不確定性問題。近年來，三支決策理論引起了許多研究者的關注，已成為了粒計算和知識發現領域中的一個重要研究方向。目前，三支決策在眾多應用領域中得到廣泛的應用，如人臉識別[3]、推薦系統[4-5]、決策系統[6]和郵件過濾[7]等；為了處理復雜的應用場景，提出了不同的計算模型，如序貫三支決策[3,8]、優化三支決策[9]、前景三支決策[10]、三支模糊集[11]和三支約簡[12]等。

在實際應用中，代價是影響三支決策劃分的重要因素之一。代價敏感學習能夠有效緩解分類過程中的數據不平衡問題，其主要作用是處理決策過程和結果產生的各類代價問題。代價敏感學習主要研究兩種代價：誤分類代價（結果代價）和測試代價，兩者互相關聯，呈負相關。如在醫療診斷中，患者想要獲得更高的診斷準確率（即決策代價越低），就需要做更多的檢查（即測試代價越高）。由于代價是數據的內在特征，將其與知識發現結合會使得問題更具有普適性，目前，代價敏感學習已經應用到現實生活中的許多領域，如：人臉識別[13]、價格預測[14]和客戶信用評價[15]等。

因此，基于代價敏感的三支決策算法與模型引起了許多學者的關注和研究，已取得重要的研究成果。Fang 等[8]將信息粒度納入決策分析過程，同時考慮決策過程和決策結果的代價，分別設計了兩種不同的算法以最小化決策過程和決策結果代價。Fang 等[16]提出了一種三支決策和可分辨矩陣的框架，在此框架下分別設計了基于刪除和增加的代價敏感近似屬性約簡算法。Jia 等[17]構造了一種可以直接應用于傳統的代價敏感學習問題的三支決策模型，在此基礎上，提出基于多類三支決策模型的多階段代價敏感學習方法。Li等[18]為從輸入圖像中順序提取分層粒度結構，提出了一種基于DNN 的順序粒度特征提取方法，在此基礎上，提出一種代價敏感的序貫三支決策模型。Yang 等[19]考慮了用戶需求， 提出一種基于模糊粗糙集的序貫三支決策模型的優化機制，用來實現對代價敏感的最優粒度選擇。Ma 等[20]定義了三支特定類的最低代價約簡，分別設計了基于添加?刪除策略和刪除策略來構建特定類的最小代價約簡算法。以上算法與模型能夠最小化結果代價或過程代價。而在許多應用領域中往往需要從代價敏感視角來分析三支決策邊界域樣本，目前三支決策的研究對象多為單一性數據的決策系統，對于混合數據邊界域樣本處理的研究相對較少。

為此，本文提出了一種面向混合數據的代價敏感三支決策邊界域分類方法。首先，基于正域約簡，提出了面向混合數據的屬性約簡模型；然后，提出了一種基于代價敏感的三支決策邊界域樣本處理方法，在貝葉斯最小風險的基礎上構造誤分類代價公式，劃分邊界域中的對象。最后，對UCI 上的10個數據集進行實驗，結果表明該方法能夠降低誤分類代價，而且能較準確地劃分邊界域中的對象；這為三支決策的邊界域樣本處理提供了一種可借鑒的方法。

1 基本知識

1.1 鄰域粗糙集

在粗糙集理論[21]中，給定一個四元組決策系統：

其中U={x1,x2,···,xn}表示有限非空的對象全集，稱為論域或者對象空間；At表示有限非空的屬性全集，由條件屬性和決策屬性共同組成；C={a1,a2,···,an}表示有限非空的條件屬性全集；D表示決策屬性；Va表示a∈C的屬性值集；Ia|U×At→V是一個信息函數，能給每個對象的每個屬性賦值，即Ia(x)→Va。

定義1[22]給定混合鄰域決策系統DN={U,FD∪FC,D,Va,Ia,δ}，距離度量函數ΔN:U×U，給定屬性子集B?C和鄰域參數δ，則對象x和y基于B的鄰域關系為

式中：FD為離散屬性集合；FC為連續屬性集合；δ是鄰域參數。

1.2 三支決策粗糙集

三支決策粗糙集[23]通過2個狀態集和3個動作集來描述其決策過程。其中，狀態集S={X,?X}分別表示對象屬于概念X和不屬于概念X，動作集A={aP,aB,aN}表示對于不同狀態分別采取接受、延遲和拒絕3 種不同的動作。由于采取不同動作會產生不同的損失，記λPP、λBP、λNP表示當x∈X時，分別采取動作aP、aB和aN產生的風險損失值；同樣地，記λPN、λBN、λNN表示當x∈?X時，分別采取動作aP、aB和aN產生的風險損失值；損失之間的關系滿足：λPP<λBP<λNP，λNN<λBN<λPN。在實際應用中，這些損失值通過專家的經驗獲取。

定義2[1]在決策系統DS={U,C∪D,Va,Ia}中，令X為論域U基于決策屬性D的劃分，α 和β為三支決策的閾值，P(X|[x])表示對象x的條件概率，對于?x∈U，根據貝葉斯決策過程，計算得到最小成本準則的三支決策規則：

其中，正域POS(X)、負域NEG(X)和邊界域BND(X)分別對應三支決策規則中的接受、拒絕和不承諾規則，且滿足：POS(X)∪BND(X)∪ N EG(X)=X；僅當X=U時，P OS(X)∪BND(X)∪NEG(X)=U。

1.3 代價敏感學習

代價敏感學習主要研究誤分類代價和測試代價，由于本文中考慮了其誤分類代價，誤分類代價表示對對象錯誤劃分后的一種懲罰。用Ck×k表示誤分類代價矩陣，其中k表示k分類問題。為方便理解，以二分類代價矩陣為例；其中c11表示將類別為1 的對象劃分到類別1 中，因此c11的值為0，同理c22的值也為0；c12表示將類別為1 的對象劃分到類別2 中，此時屬于誤分類，在劃分中需付出懲罰代價，因此c12>0，同理c21>0。

2 基于正域約簡的代價敏感三支決策邊界域分類方法

2.1 面向混合鄰域決策系統的正域約簡

由于基于三支決策的粒計算方法大多是處理連續型數據或離散型數據等單一型數據，但是在現實生活的應用領域中數據類型通常是既含有連續型數據又含有離散型數據的混合數據，為此需對混合數據的三支決策模型展開研究。

定義3給定混合鄰域決策系統DN={U,FD∪FC,D,Va,Ia,δ}，Va(x)表示對象x在屬性a上的屬性值：

對于?x,y∈U,?a∈FD，則x和y基于FD的距離為

對于?x,y ∈U,?a ∈FC，則x 和y基于 FC的距離為

其中，當p=1時，ΔNFC(x,y)為曼哈頓距離；當p=2時，ΔNFC(x,y)為歐氏距離；當p→∞時，ΔNFC(x,y)為切比雪夫距離。

定義4給定混合鄰域決策系統FC,D,Va,Ia,δ}，令Di為論域U基于決策屬性D的劃分，則混合鄰域決策系統的上下近似表示為：

通過上下近似集，可知特征子集B上的正域如下：

定義5給定混合鄰域決策系統DN={U,FD∪FC,D,Va,Ia,δ}，令屬性ai∈C，則混合鄰域決策系統中基于三支決策的核屬性集定義為：

以表1 為例，給出一個混合鄰域決策系統，其中，U={x1,x2,···,x10}為對象集，C={a1,a2,···,a6}為條件屬性集,決策類U/D={D1,D2}，分別為D1={x1,x3,x5,x6,x7,x9}，D2={x2,x4,x8,x10}。

表1 混合鄰域決策系統DNTable1 Hybrid neighborhood decision system DN

根據定義5 可計算出混合鄰域決策系統的核屬性集，具體的計算過程為：首先，根據定義3，利用p=2時的歐氏距離計算全體對象的混合鄰域粒度，再根據定義5 計算出POSC(D)={x1,x4,x5,x6,x7}，同理可計算出POSC?{a1}(D)={x1,x4,x5,x6,x7},因為POSC(D)=POSC?{a1}(D),所以屬性a1? C ORE(C)，同理可求出{a2,a3,a5,a6}?CORE(C),只有屬性a4∈CORE(C)。由此可知核屬性集為CORE(C)={a4}。下面將在此基礎上，提出了代價敏感下的三支決策邊界域分類方法。

2.2 基于核屬性集的代價敏感三支決策邊界域分類方法

定義6給定混合鄰域決策系統DN={U,FD∪FC,D,Va,Ia,δ}，設屬性子集B?C，α 和β為三支決策的閾值，Di表 示不同的決策屬性，則不同屬性子集下的三支決策規則定義為：

以表1 為例，可給出混合鄰域決策系統代價矩陣，如表2 所示。結合定義2 和表2，可求出三支決策的閾值α=7/9,β=1/3。

表2 誤分類代價矩陣Table2 Misclassification cost matrix

令B=CORE(C)={a4},根據定義3 可計算出核屬性子集B下的對象之間的鄰域粒度；再根據定義6 計算出核屬性集下決策類D1的的正域、負域和邊界域，具體的計算過程為：由定義3 可計算出核屬性集B下x1的鄰域粒度δB(x1)= {x1,x2,x5,x6,x7,x8,x9,x10},由此求出x1的條件概率P(D1|δB(x1))=5/8<α，所以x1∈BNDB(D1)，同理{x2,x4,x5,x6,x7,x8,x9,x10}∈BNDB(D1)，即BNDB(D1)={x1,x2,x4,x5,x6,x7,x8,x9,x10}。通過相同的計算可求出：

定義7在混合鄰域決策系統DN=U,FD∪FC,D,Va,Ia,δ}中，Di為論域U基于決策屬性D的劃分，給定屬性子集B?C，為了簡化公式，用CPr和(1?CP)r分別代替，對于?xj∈BNDB(Di)，樣本簡化后的誤分類代價計算公式如下：

其中，PCB(Di|x)表示在決策類Di下將對象x劃分到正域產生的誤分類代價，同理，NCB(Di|x)表示在決策類Di下將對象x劃分到負域產生的誤分類代價。λNP和λPN是代價矩陣中的風險損失值，P(Di|δB(x))表示在決策類Di下對象x的條件概率。

性質1在混合鄰域決策系統DN={U,FD∪FC,D,Va,Ia,δ}中，Di是對決策屬性D的劃分，假設屬性子集B?C，對于?x∈BNDB(Di)，可得出如下推論：

1)如果PCB(Di|x)>NCB(Di|x)，則x∈NEGB(Di)；

2) 如果PCB(Di|x)≤NCB(Di|x)，則x∈POSB(Di)。

以表1 為例，令B=Core(C)={a4}，已知D1={x1,x3,x5,x6,x7,x9} 和BNDB(D1)={x1,x2,x4,x5,x6,x7,x8,x9,x10}，根據定義7 和性質1 可將邊界域中的對象劃分到正域和負域，具體的計算過程如下：

對于?x∈BNDB(D1)，根據定義7 可求出劃分對象x1產生的兩種誤分類代價PCB(D1|x1)=6/11，NCB(D1|x1)=5/11，因為PCB(D1|x1)>NCB(D1|x1)，所以x1∈NEGB(D1)，同理可得{x2,x4,x6,x8,x9,x10}∈NEGB(D1)和{x5,x7}∈POSB(D1)。由此可知，該混合鄰域決策系統的正域為POSB(D1)={x5,x7}，負域為NEGB(D1)={x1,x2,x3,x4,x6,x8,x9,x10}。

3 算法描述及復雜度分析

針對混合鄰域決策系統，為了有效劃分其三支決策邊界域中的對象，本文提出了一種面向混合數據的代價敏感三支決策邊界域分類方法，該算法主要分為三個部分。首先，針對混合鄰域決策系統中的數據，通過混合鄰域計算公式計算每個對象的混合鄰域粒度，得到混合鄰域決策表的正域對象集合，由此基于啟發式策略計算核屬性集。其次，在此基礎上，計算混合鄰域決策表中每個對象的鄰域粒度，從而計算出每個對象屬于不同決策類的條件概率，利用三支決策規則將對象分別劃分到不同決策類的正域、邊界域和負域中；最后，針對邊界域中的對象，分別計算其劃分到正域和負域所產生的誤分類代價，通過比較這兩種代價的大小，將邊界域中的對象劃分到正域或負域中，為此，算法的流程圖1 所示。

圖1 算法流程圖Fig.1 The flowchart of algorithm

算法面向混合數據的代價敏感三支決策邊界域分類方法

①若α≤P(Di|δCOREC(D)(x))≤1，則將對象x劃分到決策類Di的正域 P OSCOREC(Di)；

②否則，若0≤P(Di|δCOREC(D)(x))≤β，則將對象x劃分到決策類Di的負域 N EGCOREC(Di)；

③否則將對象x劃分到決策類Di的邊界域BNDCOREC(Di)；

8）對于?xb∈BNDCOREC(Di)計算PCCOREC(Di|xj)和NCCOREC(Di|xj)：

①若滿足PCCOREC(Di|xj)>NCCOREC(Di|xj)，則將對象xj劃分到決策類Di的負域 N EGCOREC(Di)；

②否則將對象xb劃分到決策類Di的正域POSCOREC(Di)；

9）輸出劃分結果正域POSCOREC(Di)，負域NEGCOREC(Di)。//算法結束。

算法時間復雜度分析：

1）算法的時間復雜度為O(|U||C|)；2）劃分決策類所需的時間復雜度為O(|U|)；3）在屬性全集下，通過混合鄰域計算公式得出每個對象的混合鄰域粒度，其時間復雜度為O(|U|2|C|)；4）計算正域對象的時間復雜度為O(|U|)；5）計算核屬性集的時間復雜度為O(|U|2|C|)；6）在核屬性集CORE下，計算每個對象的混合鄰域粒度，其時間復雜度為O(|U|2|COREC(Di)|)；7）計算各決策類正域、邊界域和負域，其時間復雜度為O(|U|)；8）結合代價敏感劃分邊界域中的對象，其時間復雜度為O(|BNDCOREC(Di)|)。綜上所述，算法最壞情況下的時間復雜度是O(|U|2|C|)；由于存儲空間主要用于存放數據，因此算法的空間復雜度為O(|U||C|)。

4 實驗比較與分析

為了驗證本文方法對邊界域對象劃分的可行性和有效性，實驗從UCI 中選取了10個混合數據集進行實驗測試與分析；選用分類準確率、權衡因子、誤分類損失和時間作為評價指標，對實驗結果進行對比與分析。

4.1 數據集與實驗設置

為了更好地說明所提出算法的普適性，本文根據數據集的來源和規模兩個方面，從國際公開的機器學習UCI 數據庫中選取了10個數據集進行實驗結果的對比和分析，數據集的信息描述如表3 所示。表中Speaker Accent 和Ionosphere 數據集中包含連續型數據，Phishing Websites 和Student Evaluation 數據集中包含離散型數據；其余數據集均包含連續型和離散型數據；這些數據集來自欺詐分析、醫學診斷、信號處理和教育評價等應用領域。 同時為了消除量綱的影響，對所有數據集中的連續型數據進行歸一化處理。本次實驗的運行環境為：Win10,Intel(R)Core(TM),i5-6 500 CPU @ 3.20 GHz 3.19 GHz 和8 GB 內存，用Python 編程語言實現算法設計。

表3 數據集的基本信息Table3 Basic information of the data set

4.2 評價指標

實驗將從準確率、權衡因子、誤分類損失和運行時間4 種度量指標[24]對劃分結果進行分析，定義如下：

式中：POS(Di)和Di表示正域和決策類，nb和nn分別表示邊界域、負域中的對象個數；λbp和λnp分別表示將屬于某一決策類的對象錯誤劃分到該類別的邊界域和負域中產生的損失；由于本文算法的輸出只包含正域和負域，因此Cov=1。本實驗的風險損失參數為λbp=0.3，λnp=0.7。

4.3 實驗結果與分析

4.3.1 參數 λPN和λNP對劃分結果的影響

在混合鄰域決策系統中，參數 λPN和λNP通過影響閾值對(α,β)的大小來影響三支決策的劃分。因此，為了詳細分析參數 λPN和λNP的值對劃分準確度的影響。本小節中，為了一般性，從上述數據集中選取6個作為代表進行實驗分析，分別將λPN和λNP的值從3 到10，且每次步長變化1 進行實驗。實驗結果如圖2 所示。

圖2 參數λPN和λNP對準確率的影響Fig.2 Influence of parameters λPNand λNPon the accur acy

在圖2(a) 中，當λPN的取值區間在[4,5]時，Credit Approval 等5個數據集的準確率隨代價的增加而下降，且變化趨勢較為平緩；當 λPN的取值區間在[7,8]時，這些數據集的準確率隨代價的增加而下降，且變化趨勢較為顯著。在圖2(b) 中，當 λNP的取值區間在[4,5]時，Credit Approval 等5個數據集的準確率隨代價的增加而上升，且變化趨勢較為顯著；當 λNP的取值在[6,7]區間時，數據集Speaker Accent 的準確率隨代價的增加而升高，進而達到平穩狀態；當λNP的取值在[7,8]時，Credit Approval 等個5 數據集的準確率隨代價的增加而升高，且變化趨勢較為平緩；當代價 λPN和λNP的取值在[8,10]時，準確率達到平穩狀態，所有數據集的準確率不再隨著代價的變化而變化。

綜上所述，從整體上看，代價 λPN和λNP對分類準確度的影響呈負相關，數據集的準確率隨著代價 λPN的增加，呈現出整體下降的趨勢；而隨著代價λNP的增加，整體呈現上升的趨勢。從局部上看，當代價的取值在[4,5]和[7,8]這兩個區間時，數據集的準確率隨著代價的增加而發生變化，當代價的取值在其他區間時，數據集的準確率趨于穩定的狀態。由此，在實際的決策過程中，可結合上述分析的結論，并根據數據集的分布和代價敏感學習構造合適的代價矩陣。

4.3.2 本文模型與不同三支決策模型的對比分析

本節主要分析不同三支決策模型對分類性能的影響，表4～7 給出了3 種粗糙集模型下準確率Acc、權衡因子F、誤分類損失Cost 和運行時間Time 的實驗結果。其中，NCTM (neighborhood rough set based cost-sensitive three-way decision boundary region processing model)是基于鄰域粗糙集[25]設計考慮了代價敏感的三支決策邊界域處理模型，PCTM (pawlak rough set based cost-sensitive three-way decision boundary region processing model)是基于經典粗糙集[22]設計考慮了代價敏感的三支決策邊界域處理模型，MCTM (mixedneighborhood rough set based cost-sensitive three-way decision boundary region processing model)代表本文基于混合鄰域粗糙集的代價敏感三支決策邊界域處理模型。在PCTM 模型中對數據集進行離散化預處理，在NCTM 和MCTM 模型中對數據集進行了歸一化預處理，另外，為了使距離處于同一量綱下，在NCTM 模型中采取平均距離度量，同時Acc、F、Cost 和Time 的值均為數據集所有決策類的平均值。實驗結果如表4～7 所示，其中，符號 ↑表示度量指標的值越大越好，符號 ↓表示度量指標的值越小越好，加粗字體表示算法在所對應的數據集上的最優值。

表4 三種粗糙集模型的準確率Acc(↑)對比Table4 Comparison of accuracy Acc(↑)under three kinds of rough set models

如表4 所示，使用本文模型的分類準確率高于其他2 種模型，例如，其在數據集Credit Approval 上的準確率比NCTM 和PCTM 模型分別提高了4.8%和2.9%，由于MCTM 能夠針對不同的數據類型采取不同的分類方法，且具有更低的錯誤率，因此其劃分準確率能整體上高于NCTM 和PCTM。此外，在數據集Ionosphere 上，PCTM 模型的優勢更加明顯，而在數據集Speaker Accent上，本文模型和NCTM 模型的準確率相同，由此可知，本文模型能有效地提高分類準確率，且在數據集上整體表現良好。

如表5 所示，對權衡因子而言，由其度量公式可知，權衡因子由準確率和覆蓋率共同決定，由于本文中的三支決策最終轉換成二支決策，因此覆蓋率Cov=1，在本文中權衡因子F很大程度上取決于準確率Acc 的值。對比表4 和表5 的實驗結果可知，權衡因子F的值略高于準確率Acc 的值 ，但是整體上的變化趨勢和Acc 相同。

表5 3 種粗糙集模型的權衡因子F(↑)對比Table5 Comparison of trade-off factorF(↑)under three kinds of rough set models

如表6 所示，使用本文模型的誤分類損失整體上明顯低于其他2 種模型，例如，在數據集Student Evaluation 中，本文模型的誤分類損失比NCTM 和PCTM 分別降低了478.1 和287.0。從不同的模型角度分析，針對混合鄰域決策系統，PCTM對劃分的要求較為苛刻，而NCTM 對劃分的要求較于放松，容錯率低，導致劃分錯誤率提高；本文模型MCTM 可靈活應用于不同類型的決策系統，容錯率高，所以具有更低的誤分類代價。

表6 3 種粗糙集模型的誤分類損失Cost (↓)對比Table6 Comparison of misclassification loss Cost (↓)under three kinds of rough set models

如表7 所示，從整體上看，3 種粗糙集粒計算模型所消耗的時間較少且隨著數據規模的增大而增多；從部分上看，NCTM 模型耗時相對較長，主要是由于NCTM 是用鄰域關系計算鄰域類，每兩個對象之間都要計算，導致其時間復雜度較高。而PCTM 模型和MCTM 模型在耗時方面差異性不大，且差異性隨數據規模的增大而減小。

表7 3 種粗糙集模型的運行時間 Time(↓)對比Table7 Comparison of operation hours Time (↓)under three kinds of rough set models

綜上所述，與其他2 種不同的粗糙集模型進行實驗對比和分析可知，本文模型總體上具有較高的分類準確度和較低的誤分類損失，因此，用其對混合鄰域決策系統進行劃分較為合理。

4.3.3 本文模型和序貫三支決策模型的邊界域分類方法對比

為了進一步驗證本文模型的有效性，本小節將本文模型與序貫三支決策的方法進行實驗對比和分析。其中，MSTM (mixed-neighborhood rough set based sequential three-way decision boundary region processing model)是基于經典序貫三支決策[8]改造的基于混合鄰域粗糙集的序貫三支決策邊界域處理模型。實驗結果如表8 所示，分別給出了MCTM 和MSTM 的分類準確度、權衡因子、誤分類損失和時間的對比。

由表8 的實驗結果可知，在數據集Ionosphere 和Audit Data 上，本文模型MCTM 的分類性能與MSTM 相同，而在另外8個數據集上，本文模型MCTM 的分類性能要優于序貫三支決策模型MSTM。從理論上分析，由于MSTM 直接由代價矩陣計算的閾值劃分邊界域對象，而本文在此基礎上進一步考慮條件概率和誤分類代價來劃分邊界域中的對象，因此本文模型MCTM 在Acc、F、Cost 和Time 上表現較優。為此，在同等條件下，對于混合鄰域決策系統，本文基于屬性約簡的混合代價敏感三支決策邊界域分類方法為處理邊界域對象提供了一種可借鑒的分析方法。

5 結束語

近年來三支決策理論成為熱點研究問題，其研究對象多為單一型決策系統，然而，在許多的應用領域中，數據往往呈現混合類型的特點，目前三支決策對混合數據邊界域樣本處理的研究相對較少。為劃分混合決策系統中的邊界域對象，本文提出了基于混合數據的屬性約簡方法；并在此基礎上，提出了一種基于核屬性的代價敏感三支決策邊界域分類方法。通過在不同的數據集上進行實驗對比與分析，驗證了本文方法的可行性和有效性，獲得了一種相對合理的邊界域對象的劃分方法。由于序貫三支決策更加符合現實生活中的決策過程及人類的認知，下一步工作將研究基于代價敏感的序貫三支決策的粒化問題。