基于三支決策的多類分類模型

徐 怡 魏貴瑩

1(安徽大學計算機科學與技術學院 安徽 合肥 230601)2(安徽大學計算智能與信號處理教育部重點實驗室 安徽 合肥 230039)

基于三支決策的多類分類模型

徐 怡1,2魏貴瑩1

1(安徽大學計算機科學與技術學院 安徽 合肥 230601)2(安徽大學計算智能與信號處理教育部重點實驗室 安徽 合肥 230039)

在多類分類問題的實際應用中，決策者通常希望得到的決策結果是唯一的，即避免出現決策冗余與沖突。因此，借鑒三支決策的思想，通過增加延遲決策類，將m個多類分類問題變為m+1個多類分類問題，使得原本的代價參數減少，又使得最終的決策結果不存在冗余與沖突。提出一種基于三支決策的多類分類模型，并用實例說明了該方法的實用性。

決策粗糙集 三支決策 代價 多類分類 沖突

0 引 言

三支決策(Three-way Decision)[1-3]是決策粗糙集在方法論層次上的進一步提升，給出了粗糙集[4-5]正域、負域和邊界域的三支決策語義解釋，將邊界域看作是一種延遲決策，從而規避了錯誤拒絕或錯誤接受造成的損失，符合人們在決策過程中的思維習慣，減少了對不確定性知識做出錯誤決定的代價，具有一定的優越性[6]。目前，三支決策理論已成功應用在多個領域中。如，Yu等提出了一種基于決策粗糙集的自動聚類方法[7]，Zhou等將三支決策的思想運用到郵件過濾中[8]，Yang等根據三支決策提出了一種多用戶決策模型[9]，Yao等給出了決策粗糙集在醫療網絡支持系統中的應用方法[10]。同時，由于多類分類問題[11]的普遍性，Yao通過將m類分類問題轉化為m個兩類分類問題，為解決多類分類問題提供了一種新的思路[12]。但是Yao的方法假設不同決策類的誤分類代價是相同的，這種假設在實際應用中存在一定的不合理性。因此Zhou提出了一種新的多類分類模型[13-14]，該模型考慮了誤分類一個對象到不同的決策類會產生不同的損失函數，針對每個類給定三個代價參數(接受、延遲和拒絕)，針對每個類找到代價最小的行動，采取相應的決策。但是該模型的最終決策結果可能存在決策沖突，也就是說，對于某個對象，并不是對應唯一的一個代價最小的決策類的正域，而是可能存在滿足條件的多個決策類的正域，從而將對象劃分到不同決策類的正域，這顯然不符合實際問題的求解需要。同時，Zhou所提模型中會判斷研究對象是否屬于某個類的負域，這會造成很多沒有必要的決策，現實生活中，對于多類分類問題我們只需要判斷研究對象是否劃分到某個類(即該類的正域)，不需要判斷其是否不劃分到某個類(即該類的負域)。如醫生診斷病人時，不需要判斷病人不患感冒，不患肺炎，不患其他疾病等，而是希望能夠判斷病人是患感冒，肺炎，或其他疾病中的某一種即可。

綜上，本文在Zhou提出的模型的基礎上，通過增加延遲決策類，將m個多類分類問題變為m+1個多類分類問題，減少了誤分類代價參數，使得最終的決策結果不存在冗余與沖突。運用貝葉斯最小風險決策，降低了不確定知識造成的誤分類總代價，提出一種基于三支決策的多類分類模型。

1 決策粗糙集下的多類分類模型

賈修一等[15]將前人給出的多類分類模型的算法用矩陣的形式進行表達，使得計算更加淺顯易懂，但沒有考慮不同決策類之間誤分類代價的不同。為此，Zhou提出了多類分類模型[14]，考慮了誤分類一個對象到不同的決策類會產生不同的損失代價，針對每個類找到代價最小的行動，采取相應的決策。下面簡單介紹決策粗糙集的基本理論與多類分類模型。

定義1 一個決策信息表可以表示成一個四元組S=(U,A=C∪D,V,f)，其中U是一個非空有限集合，稱為論域；A為屬性集，C稱為條件屬性集，D稱為決策屬性集，C∩D=φ；V=∪a∈AVa，a∈A，Va是屬性a的值域；f為信息函數，f:U×A→V，即f(x,a)∈Va，它指定了U中每個對象x的屬性值[15]。

定義2 對于一個決策信息表S=(U,A=C∪D,V,f)，若B?C，基于B的不可分辨關系定義為[15]：

IND(B)={(x,y)∈U×U|?b∈B,f(x,b)=f(y,b)}

(1)

如果(x,y)∈IND(B)，則稱x和y基于B是不可分辨的。符號U/IND(B)表示不可分辨關系IND(B)在U上導出的所有等價類，可簡記為U/B。[x]B表示基于B得到的x的等價類。

POS(α,β)(X)={x|x∈U,Pr(X|[x]B)≥α}

(2)

BND(α,β)(X)={x|x∈U,β

(3)

NEG(α,β)(X)={x|x∈U,Pr(X|[x]B)≤β}

(4)

條件概率大于等于α表示接受一個對象x是X的成員。條件概率小于等于β表示拒絕x是X的成員。條件概率介于α和β之間表示既不接受也不拒絕x是X的一個成員，也就是延遲決策。

定義4 設Ω={D1,D2,…,Ds}是一個有限的狀態集合，A={a1,a2,…,am}是有限的行動集合，Pr(Dj|x)是x處于Dj狀態下的條件概率，λ(ai|Dj)(i∈[1,m],j∈[1,s])表示x的狀態為Dj，采取行動ai的代價(損失)，那么x采取行動ai最終的期望代價(損失)是[14]：

(5)

定義5 給定一個決策信息表S=(U,A=C∪D,V,f)，Ω=U/D={D1,D2,…,Dm}表示m個狀態集合，則一個研究對象可以劃分到任一決策類Dk(k=1,2,…,m)，給定行動集A={aPj,aBj,aNj}，其中aPj、aBj、aNj分別表示將對象分類到POS(Dj)、BND(Dj)、NEG(Dj)的三種行為。λPjDk表示將一個屬于Dk的對象分類到Dj正域POS(Dj)的損失，λBj Dk表示將一個屬于Dk的對象分類到Dj邊界域BND(Dj)的損失，λNjDk表示將一個屬于Dk的對象分類到Dj負域NEG(Dj)的損失[15]。

定義6 給定一個決策信息表S=(U,A=C∪D,V,f)，U/C={X1,X2,…,Xn}，U/D={D1,D2,…,Dm}，隸屬度矩陣PC=(Pr(Dj|Xi))n×m，是一個n×m的矩陣，其中，Pr(Dj|Xi)=|Dj∩Xi|/|Xi|。記為[15]：

(6)

定義7 給定一個決策信息表S=(U,A=C∪D,V,f)，U/C={X1,X2,…,Xn}，U/D={D1,D2,D3,…,Dm}，則代價矩陣M是一個m×3m矩陣，記為[14]：

D1D2…Dm

(7)

考慮到不同決策類的誤分類代價是不同的，即具有代價敏感性，所以該代價矩陣的元素具有下列特征：

λPiD1≠λPiD2≠…≠λPiD(i-1)≠λPiD(i+1)≠…≠λPiDm

λBiD1≠λBiD2≠…≠λBiDmλNiD1≠λNiD2≠…≠λBiDm

定義8 給定一個決策信息表S=(U,A=C∪D,V,f)，U/C={X1,X2,…,Xn}，U/D={D1,D2,D3,…,Dm}，決策風險矩陣R=PC×M是一個n×3m的矩陣，記為[15]：

D1…Dm

(8)

在決策風險矩陣中，三種行為下的期望損失可以分別表示為：

(9)

(10)

(11)

根據最小風險貝葉斯決策準則，可以得到如下形式的決策規則：

(P)IFR(aPj|Xi)≤R(aBj|Xi)ANDR(aPj|Xi)≤R(aNj|Xi)THENXi∈POS(Dj)

(B)IFR(aBj|Xi)≤R(aPj|Xi)ANDR(aBj|Xi)≤R(aNj|Xi)THENXi∈BND(Dj)

(N)IFR(aNj|Xi)≤R(aPj|Xi)ANDR(aNj|Xi)≤R(aBj|Xi)THENXi∈NEG(Dj)

通常正確接受的代價小于錯誤拒絕的代價，而延遲決策的代價介于正確接受的代價和錯誤拒絕的代價之間，反之亦然。

2 基于三支決策的多類分類模型

文獻[14]所提出的多類分類模型中，最終決策結果可能存在決策沖突或決策冗余，是因為任意一個對象針對每個決策類分別對應接受、拒絕和延遲三種行動，也就是任意一個對象xi在每一個決策類Dk(k∈[1,m],m表示決策類的個數)下都會從該對象接受到此決策類(x∈POS(Dk))，拒絕到此決策類(x∈NEG(Dk))，延遲決策到此決策類(x∈BND(Dk))中選擇一個代價最小的行動。所以可能會出現某個對象xi∈BND(D1)，xi∈NEG(D2)，xi∈NEG(D3)，甚至會出現xi∈POS(D1)，xi∈POS(D2)，xi∈BND(D3)。前者我們稱為決策冗余，后者稱為決策沖突。同時，任意一個對象xi針對每個決策類Dk需要根據三種誤分類代價(λPkDj，λNkDj,λBkDj)來計算三種決策代價，對應于該對象在某個決策類下的三種行動代價，從而判斷該對象是接受、拒絕、還是延遲到某個決策類中，那么所需要的誤分類代價參數為m×3m個(m表示決策類的個數)。

然而在實際應用中，并不需要知道任意一個對象在每個決策類下是被接受、被拒絕、還是被延遲決策，只需要知道任意一個對象xi采取不同決策類Dk(k∈[1,m])的代價，判斷出代價最小的決策類，對應的接受該對象到代價最小決策類中即可。此時所需要的誤分類代價參數為m×m個(m表示決策類的個數)。但是這樣三支決策中延遲決策行為能夠減少誤分類總代價的優勢就不能體現，為此，可以增加一個延遲決策類，然后從所有決策類Dk(k∈[1,m])與延遲決策類中選擇一個代價最小的決策類，對應的采取接受對象xi到Dk類，或者延遲決策對象xi。此時所需要的誤分類代價參數為m×(m+1)。這樣做出的最終決策是一個劃分，不會出現冗余，可以解決規則沖突的問題。同時，增加一個延遲決策的行為，可以減少誤分類總代價，從而降低決策風險。此外，所需的誤分類代價參數比Zhou所提出模型中的代價參數要少，使得模型在計算過程中變得簡便。以下給出這種模型的相關定義。

定義9 給定一個決策信息表S=(U,A=C∪D,V,f)，Ω=U/D={D1,D2,…,Dm}表示m個狀態集合，可能的決策集合定義為DES={POS(D1),POS(D2),…,POS(Dm),BND}，其中POS(D1),POS(D2),…,POS(Dm)表示m個決策類的正域，BND表示延遲決策類。則任給一研究對象，其或者劃分到某一決策類Dk(k=1,2,…,m)的正域，或者不能劃分到任意決策類Dk(k=1,2,…,m)的正域，此時對其進行延遲決策，即劃分到延遲決策類BND。與上述決策集合相對應給定行動集A={a1,a2,…,am,am+1}，其中ai(i∈[1,m])表示接受對象劃分到Di類，即對象屬于POS(Di)，am+1表示對對象采取第m+1種行為：延遲決策行為，即對象屬于延遲決策類BND。λi,j(i∈[1,m],j∈[1,m])表示將一個屬于Dj的對象分類到Di的損失；λm+1,j(j∈[1,m])表示將屬于Dj類的對象進行延遲決策的損失。

定義10 給定一個信息系統S=(U,A=C∪D,V,f)，U/C={X1,X2,…,Xn}，U/D={D1,D2,D3,…,Dm}，則基于三支決策的多類分類模型的代價矩陣M0，是一個m×(m+1)矩陣，記為：

POS(D1)POS(D2) …POS(Dm)BND

(12)

式中，M0稱為帶延遲決策類的代價矩陣。由于不同決策類誤分類到同一決策類的代價是不同的，所以滿足λi,1≠λi,2≠…≠λi,m(i∈[1,m])，同時，延遲劃分的行動代價通常小于錯誤劃分的代價，所以滿足0<λm+1,j

隸屬度矩陣的計算和定義6相同，則基于三支決策的多類分類模型的決策風險矩陣定義如下。

定義11 給定一個信息系統S=(U,A=C∪D,V,f)，U/C={X1,X2,…,Xn}，U/D={D1,D2,…,Dm}，帶延遲決策類的決策風險矩陣R0=PC×M0是一個n×(m+1)的矩陣，記為：

POS(D1)POS(D2…POS(Dm)BND

(13)

在決策風險矩陣中，不同決策行為下的期望損失可以表示為：

(14)

根據最小風險貝葉斯決策準則，可以得到如下形式的決策規則：

(P1)如果?R0(ak|Xi)(k∈[1,m+1],k≠j)，滿足R0(aj|Xi)≤R0(ak|Xi)，那么Xi∈POS(Dj)，j∈[1,m]。

(B1)如果?R0(ak|Xi)(k∈[1,m+1],k≠j)，滿足R0(am+1|Xi)≤R0(ak|Xi)，那么Xi∈BND，即此時對Xi采取延遲決策行為。

最終決策時，對Xi所采取的決策需要比較Xi采取不行動時的代價，并找到代價最小的行動。也就是在上述帶延遲決策類的風險矩陣中找到第i行中最小代價值所對應的決策。

為了更加形象地說明以上多類分類模型，我們用矩形框表示所有研究對象的集合，實線表示正域，虛線表示邊界域，陰影部分用于表示兩個類之間重疊的元素。則圖1給出了所有決策集合之間的關系。

圖1 基于三支決策的多類分類模型的決策集合的關系

以圖1可以看出不存在任何陰影部分，即表示所有決策集合：POS(Di) (i∈[1,m])、BND集合之間是不存在交集的。同時，基于三支決策的多類分類模型的決策結果就是將對象劃分到以上決策集合中的任一個集合中。所以，決策的結果不會存在沖突，也不會存在冗余的決策。

3 實例與分析

以下以一個簡單的決策信息表為實例，如表1所示，其中U={x1,x2,…,x16,x17}，條件屬性集合C={a1,a2,a3,a4}，決策屬性集合D=g0gggggg。給定誤分類代價矩陣M0如表2所示。分別運用傳統多類分類的模型(以下簡稱模型一)與本文中基于三支決策的多類分類模型(以下簡稱模型二)來計算最終的決策結果，比較兩種模型中決策結果的優劣，以此說明基于三支決策多類分類方法在實際生活中的實用價值。

表1 決策信息表

表2 三種決策屬性之間的誤分類代價

根據式(1)可以得到決策信息表對條件屬性與決策屬性的劃分：

U/C={X1，X2，X3，X4}

其中:

X1={x1,x7}

X2={x3,x4，x6，x8，x15}

X3={x5,x12，x14，x16}

X3={x2,x9，x10，x11，x13}

U/D={D1，D2，D3}

其中：

D1={x1}

D2={x2，x3，x4，x5，x6，x7，x8}

D3={x9，x10，x11，x12，x13，x14，x15，x16}

根據式(6)可以計算得到隸屬度矩陣：

由表2與式(7)知道其代價矩陣：

D1D2D3

根據式(8)可以得到其風險矩陣：

D1D2D3

根據規則(P-N)可知：X1∈POS(D1),X1∈POS(D2),X1∈NEG(D3)此時將X1既劃分到D1又劃分到D2，是一種決策沖突；同時，任何一個將對象Xi∈NEG(Di)，即將對象Xi劃分到負域，這種不劃分到某個類的決策都是一種多余的決策，因為決策者并不需要知道是否將一個對象Xi不劃分到某個類，僅僅需要知道是否將一個對象劃分到某個類即可，這是一種決策冗余；此外可以看到該模型下需要的誤分類代價矩陣的維數是m×3m(m表示決策類的個數)，代價矩陣的參數較多。

接下來用本文方法重新計算上述例子。由于本文方法的代價矩陣和模型一中的代價矩陣是不一樣的。為了便于比較，以下給定的代價矩陣中滿足λi,j=λPiDj(i,j∈[1,4])，即屬于Dj類的對象分類到Di類的損失等于屬于Dj的對象分類到Di正域的損失，同時滿足0<λ5,j

POS(D1)POS(D2)POS(D3)BND

矩陣的第一行表示將D1疾病誤分類到D1，D2，D3，BND(延遲決策類)的代價，即λ1,1，λ2,1，λ3,1，λ4,1。

根據式(13)可以計算出不同等價類采取不同決策行動的帶延遲決策類的風險矩陣：

POS(D1)POS(D2)POS(D3)BND

從以上可以看出X1劃分到D1的代價最小，根據規則(P1-B1)可以明確將X1劃分到D1，不存在決策沖突。同時，從決策的結果可以看出，所有的劃分只存在劃分到正域或者邊界域，不存在劃分到負域，也就不存在不必要的決策，使得決策的結果不存在冗余。此外，該模型的誤分類代價矩陣的維數是m×(m+1)(m是決策類的個數)，相對于模型一中代價矩陣維數m×3m，參數減少了很多，使得計算簡便。以上傳統方法與本文方法都是運用了三支決策理論思想，通過增加延遲域減小誤分類總代價，降低了決策風險。

綜合以上分析可以看出，本文的方法通過增加延遲決策類，將m個多類分類問題變為m+1個多類分類問題。根據最小風險貝葉斯決策準則，既考慮了不同決策類的誤分類代價是不同的，即具有代價敏感性，又使得最終的決策結果不存在沖突與冗余，而且代價矩陣中所需的代價參數相比模型一明顯減少，降低了計算的復雜度，提高了計算效率。同時，由于運用了三支決策中增加延遲域減少誤分類總代價的方法，降低了決策風險。

4 結 語

本文針對傳統的決策粗糙集模型處理多類分類問題中存在的決策沖突與冗余，借鑒三支決策的思想，將m個多類分類問題變為m+1個多類分類問題，提出一種基于三支決策的多類分類模型，并運用貝葉斯最小風險決策，降低了決策風險，給出了該模型下的決策規則。通過實例表明該模型減少了誤分類代價矩陣的參數，同時使得最終的決策結果不存在冗余與沖突。在以后的工作中，需要進一步研究該模型的相關性質以及相關的屬性約簡算法。

[1]YaoY.Anoutlineofatheoryofthree-waydecisions[C]//8thInternationalConferenceonRoughSetsandCurrentTrendsinComputing.Springer,2012:1-17.

[2]YaoY.Three-waydecisionswithprobabilisticroughsets[J].InformationSciences,2010,180(3):341-353.

[3]YaoY,DengX.Sequentialthree-waydecisionswithprobabilisticroughsets[C]//CognitiveInformatics&CognitiveComputing(ICCI*CC),2011 10thIEEEInternationalConferenceon.IEEE,2011:120-125.

[4]PawlakZ,SkowronA.Rudimentsofroughsets[J].InformationSciences,2007,177(1):3-27.

[5]PawlakZ.Roughsets[J].InternationalJournalofComputer&InformationSciences,1982,11(5):341-356.

[6]YaoY.Thesuperiorityofthree-waydecisionsinprobabilisticroughsetmodels[J].InformationSciences,2011,181(6):1080-1096.

[7]YuH,ChuS,YangD.Autonomousknowledge-orientedclusteringusingdecision-theoreticroughsettheory[J].FundamentaInformaticae,2012,115(2-3):141-156.

[8]ZhouB,YaoY,LuoJ.Athree-waydecisionapproachtoemailspamfiltering[C]//Proceedingsofthe23rdCanadianConferenceonAdvancesinArtificialIntelligence.Springer,2010:28-39.

[9]YangX,YaoJ.Amodellingmulti-agentthree-waydecisionswithdecision-theoreticroughsets[J].FundamentalInformation,2012,115(2-3):157-171.

[10]YaoJ,HerbertJP.Web-basedsupportsystemswithroughsetanalysis[C]//InternationalConferenceonRoughSetsandIntelligentSystemsParadigms.Springer,2007:360-370.

[11]LiuD,LiT,HuP,etal.Multiple-categoryclassificationwithdecision-theoreticroughsets[C]//5thInternationalConferenceonRoughSetandKnowledgeTechnology.Springer,2010:703-710.

[12]YaoY.Decision-theoreticroughsetmodels[C]//SecondInternationalConferenceonRoughSetsandKnowledgeTechnology.Springer,2007:1-12.

[13]ZhouB.Multi-classdecision-theoreticroughsets[J].InternationalJournalofApproximateReasoning,2014,55(1):211-224.

[14]ZhouB.Anewformulationofmulti-categorydecision-theoreticroughsets[C]//6thInternationalConferenceonRoughSetsandKnowledgeTechnology.Springer,2011:514-522.

[15] 賈修一,商琳,周獻中,等.三支決策理論與應用[M].南京:南京大學出版社,2012:151-158.

A MULTI-CATEGORY CLASSIFICATION MODEL BASED ON THREE-WAY DECISION

Xu Yi1,2Wei Guiying1

1(SchoolofComputerScienceandTechnology,AnhuiUniversity,Hefei230601,Anhui,China)2(KeyLabofIC&SPatAnhuiUniversity,MinistryofEducation,Hefei230039,Anhui,China)

In the practical applications of multi-category classification, the decision makers usually want the decision result to be unique, which can avoid decision redundancy and conflict. Therefore, we use the idea of three-way decision, by increasing the delay decision class, and themmulti-classclassificationproblembecomesm+1multi-classclassificationproblem.Itmakestheoriginalcostparametersreduced,butalsomakesthefinaldecisionresultswithoutredundancyandconflict.Thispaperproposesamulti-categoryclassificationmodelbasedonthree-waydecision,andthepracticalityofthemethodisverifiedbyanexample.

Decision-theoretic rough set Three-way decision Cos Multi-category classification Conflict

2016-04-12。國家自然科學基金項目(61402005)；安徽省自然科學基金項目(1308085QF114)；安徽省高等學校省級自然科學基金項目(KJ2013A015)；安徽大學計算智能與信號處理教育部重點實驗室課題項目。徐怡，副教授，主研領域：智能信息處理，粗糙集理論。魏貴瑩，碩士生。

TP

ADOI:10.3969/j.issn.1000-386x.2017.05.025