基于三支决策的多类分类模型

徐 怡 魏贵莹

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={d}。给定误分类代价矩阵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