王玲玲,吕王勇,2*

(1.四川师范大学 数学与软件科学学院,四川 成都 610066;2.可视化计算与虚拟现实四川省重点实验室,四川 成都 610066)

扩展的三支决策理论

王玲玲1,吕王勇1,2*

(1.四川师范大学 数学与软件科学学院,四川 成都 610066;2.可视化计算与虚拟现实四川省重点实验室,四川 成都 610066)

三支决策理论只能将决策对象划分到接受域、拒绝域和边界域3类,不能处理把决策对象划分为更多类的情况,因此,立足于传统的三支决策理论,对其进行推广,提出扩展的三支决策理论,结合贝叶斯理论,以决策的平均损失最小为原则,给出扩展的三支决策理论详细推导过程,使经典的三支决策理论成为特例.

扩展的三支决策; 贝叶斯理论; 三支决策;阀值; 评价函数

1 预备知识

三支决策理论是对传统的二支决策理论的发展,它在接受和拒绝2种选择的基础上引入延迟决策,使最终的决策结果保留待判类,从而避免直接接受或拒绝带来的风险,也更符合人类直观的信息处理模式,具有很强的现实意义.

Yao.Y.Y[1]在2012年给出三支决策理论的框架性描述;田海龙等[2]提出基于三支决策的中文微博观点句识别研究;张聪等[3]提出一种三支决策软增量聚类算法;薛占熬等[4]提出基于三支决策理论的条件属性权重构造方法;徐久成等[5]提出基于三支决策的支持向量机增量学习方法;杜丽娜等[6]给出基于三支决策风险最小化的风险投资评估应用研究;王磊等[7]给出基于主题与三支决策的文本情感分析;周哲等[8]提出一种基于动态词典和三支决策的情感分析方法;黄顺亮等[9]提出客户细分的三支决策方法.此外,还有谢骋等[10]提出的基于三支决策粗糙集的视频异常行为检测;李建林等[11]提出的多阶段三支决策垃圾短信过滤模型;张燕平等[12]提出的基于CCA的代价敏感三支决策模型.可以看到,三支决策理论的发展侧重于应用方面的多样化,而缺乏对其理论的推广.

三支决策的思想和方法简单有效,在解决实际问题时具有很强的应用价值,但是,该理论只能将对象最终决策到接受域、拒绝域和待判域这3类,无法处理需要将对象决策为更多类的问题,因此,在传统三支决策理论的基础上进行扩展,三支决策理论的思想能够应用在将对象划分为更多类的问题上,不仅保持了三支决策理论应用在对象细分上的优越性,也突破了三支决策理论只能将对象划分为2类及一个待判类的局限性,扩大其应用范围.

2 三支决策理论

首先给出对象的价值信息表T=(U,B,{Vb|b∈B},{Ib|b∈B}),其中,U是所需要研究的全部对象组成的有穷集合,在客观上划分为2个子集C和Cc,且U=C∪Cc.B是研究对象所有属性组成的集合,这里具体指对象的评价指标组成的集合,Vb是各属性所有取值组成的非空集合.Ib:U→Vb是信息函数,将U中每一个对象的某个属性b映射到Vb上,定义为每个对象在各个指标上的取值,即Ib(x)∈Vb.

定义U上的一个等价关系R,若Ib(x)=Ib(y),则xRy.所有满足关系R的对象组成等价类[x],则由等价类[x]、阀值(α,β)和评价函数P(C|[x])将全集U划分为3个两两不交的集合,分别表示为接受域POS(C)、待判域BND(C)和拒绝域NEG(C):

(1)

(2)

(3)

这3个概率区间两两不交,且其并集就是有限集合U.

由于将某对象划分到不同区域所需要付出的代价不同,因此,给出形如表1的一张三支决策代价表[13](见表1).

表1 三支决策分类代价表Table 1 The loss table of three-way decision

(4)

则每个对象的决策代价函数为:

(5)

(6)

(7)

RPOS(x)、RNEG(x)、RBND(x)分别表示对象x划分到POS(C)、NEG(C)、BND(C)所需要付出的总代价,则阀值对(α,β)[14]可以表示为

至此阀值对(α,β)已经可以根据损失函数λxy确定,至于损失函数λxy,直接根据专家评分法可以得到.下面就评价函数P(C|[x])的求解方法[15],借助贝叶斯理论有

(9)

该计算公式中P([x])的求解比较困难,因此选择求(9)式的近似解

(10)

易知

(11)

其中

最后结合研究对象的评价函数P(C|[x])以及阀值对(α,β),可以将全体研究对象划分到三支决策的3个域中.

3 扩展的三支决策理论

第一支:rg1={x∈U|[x]⊆C1},

第二支:rg2={x∈U|[x]⊆C2},

第三支:rg3={x∈U|[x]⊆C3},

第四支:rg4={x∈U|[x]∩C1≠φ且[x]C1,[x]∩C2≠φ,且[x]C2,[x]∩C3≠φ,且[x]C3}.

引入评价函数P(Ci|[x]),将上面4个区域换一种描述形式,其中,P(Ci|[x])描述等价类[x]中的对象x属于集合Ci的概率,则P(Ci|[x])(i=1,2,3)定义为

(12)

其中|·|表示集合的基数.(12)式可表示为:

第一支:rg1={x∈U|P(C1|[x]=1),

第二支:rg2={x∈U|P(C2|[x]=1)},

第三支:rg3={x∈U|P(C3|[x]=1)},

第四支:rg4={x∈U|0

可以看到,虽然借助极端值0和1可以将全集分成互不相交的4个区域,但当0

由于已经定义C1、C2、C3分别表示高价值、较高价值和低价值对象所属的类别,那么,P(Ci|[x]),i=1,2,3的取值会受到对象各个指标数据的影响,本身存在大小关系,因此,给出如下的扩展三支决策表达形式:

第一支:rg1={x∈U|P(C1|[x])≥α1},

第二支:rg2={x∈U|α3≤P(C2|[x])≤α2},

第三支:rg3={x∈U|P(C3|[x])≤α4},

易知阀值满足条件0≤α4<α3<α2<α1≤1.

至此,给出四支决策模型,接下来确定评价函数P(Ci|[x])(i=1,2,3)和阀值(α1,α2,α3,α4).

由于将某对象划分到不同区域所需要付出的代价不同,因此给出一张三状态四分类结果的代价表(见表2).

表2 扩展的三支决策分类代价表Table 2 The loss table of extended three-way decision

λxy表示采取不同决策时所需要付出的代价,如λ1,1′表示将属于集合C1的对象划分为rg1需要付出的代价,且决策代价大小满足

划分为rgh的某对象x的代价函数,就是该对象属于集合C1的概率P(C1|[x])与该对象属于集合C1又判断为rgh的代价值λh,1′的乘积,加上该对象属于集合C2的概率P(C2|[x])与该对象属于集合C2又被判断为rgh的代价值λh,2′的乘积,再加上该对象属于集合C3的概率P(C3|[x])与该对象属于集合C3又被判断为rgh的代价值λh,3′的乘积.函数表达式为

(14)

由于总是选择决策代价最小的行动方案为最优方案,因此决策规则可以描述为:

若Rrg1(x)≤Rrg2(x),且Rrg1(x)≤Rrg3(x),Rrg1(x)≤Rrg4(x),则x∈rg1;

若Rrg2(x)≤Rrg1(x),且Rrg2(x)≤Rrg3(x),Rrg2(x)≤Rrg4(x),则x∈rg2;

若Rrg3(x)≤Rrg1(x),且Rrg3(x)≤Rrg2(x),Rrg3(x)≤Rrg4(x),则x∈rg3;

若Rrg4(x)≤Rrg1(x),且Rrg4(x)≤Rrg2(x),Rrg4(x)≤Rrg3(x),则x∈rg4.

由此可以算出P(C1|[x])、P(C2|[x])、P(C3|[x])满足条件:

下面就结合前面的决策代价函数关系式,给出4个阀值的表达式.

根据P(C1|[x])来确定阀值组中最大的那个阀值α1.同理,通过次大的条件概率值P(C2|[x])确定阀值α2、α3,通过最小条件概率P(C3|[x])确定阀值α4,则阀值α1、α2、α3、α4表示为

(18)

接下来确定评价函数P(Ci|[x]),i=1,2,3.

借助贝叶斯理论有

(19)

该计算公式中P([x])的求解比较困难,因此选择先求解

(20)

(21)

先求解出O(P(Ci|[x])),然后根据(21)式最终确定P(Ci|[x])的值,下面分析(20)式的求解.

[x]描述为该等价类中对象在属性(b1,b2,…,bn)下所对应的取值(v1,v2,…,vn),且Ibk(x)=vk,其中,n为指标的个数,vk为等价类[x]中对象x在第k个指标下的取值.再借助朴素贝叶斯独立性假设,即假设对任意的k≠l,有vk与vl相互独立,则有

(22)

其中

最后再根据每个对象的条件概率值P(C|[x])和阈值(α1,α2,α3,α4)实现决策.

4 结束语

立足于传统的三支决策理论,对传统三支决策在决策中只能把对象划分到接受域、拒绝域这2类和待判类的局限性进行改进,提出扩展的三支决策理论,借助贝叶斯理论,以决策的平均损失代价最小为原则,并给出决策代价表,对扩展三支决策理论的三类决策规则进行了合适的描述,从而确定决策中最为重要的4个阀值.接下来还研究了在扩展的三支决策理论下,评价函数的求解方法,最终借助阀值和评价函数成功地将对象划分为更多类,使传统的三支决策理论成为特例,将三支决策的思想应用到更多的领域.

致谢 可视化计算与虚拟现实四川省重点实验室项目 (KJ201410)对本文给予了资助,谨致谢意.

[1] YAO Y Y.An outline of a theory of three-way decisions[C]//Proceedings of the RSCTC 2012.Berlin:Springer-Varlag,2012:1-17.

[2] 田海龙,朱艳辉,梁韬,等.基于三支决策的中文微博观点句识别研究[J].山东大学学报(理学版),2014,49(8):58-65.

[3] 张聪,于洪.一种三支决策软增量聚类算法[J].山东大学学报(理学版),2014,49(8):40-47.

[4] 薛占熬,朱泰隆,薛天宇,等.基于三支决策理论的条件属性权重构造方法[J].计算机科学,2015,42(8):265-268.

[5] 徐久成,刘洋洋,杜丽娜,等.基于三支决策的支持向量机增量学习方法[J].计算机科学,2015,42(6):82-87.

[6] 杜丽娜,徐久成,刘洋洋,等.基于三支决策风险最小化的风险投资评估应用研究[J].山东大学学报(理学版),2014,49(8):66-72.

[7] 王磊,黄河笑,吴兵,等.基于主题与三支决策的文本情感分析[J].计算机科学,2015,42(6):93-96.

[8] 周哲,商琳.一种基于动态词典和三支决策的情感分析方法[J].山东大学学报(工学版),2015,45(1):19-23.

[9] 黄顺亮,李建林,王琦.客户细分的三支决策方法[J].计算机科学与探索,2014,8(6):743-750.

[10] 谢骋,商琳.基于三支决策粗糙集的视频异常行为检测[J].南京大学学报(自然科学),2013,49(4):475-482.

[11] 李建林,黄顺亮.多阶段三支决策垃圾短信过滤模型[J].计算机科学与探索,2014,8(2):226-233.

[12] 张燕平,邹慧锦,赵姝.基于CCA的代价敏感三支决策模型[J].南京大学学报(自然科学),2015,51(2):447-452.

[13] 黄顺亮,王琦.基于三支决策理论的对象细分方法[J].计算机应用,2014,34(1):244-248.

[14] 刘盾,姚一豫,李天瑞.三支决策粗糙集[J].计算机科学,2011,38(1):246-250.

[15] YAO Y Y,ZHOU B.Naive bayesian rough sets[C]//Proceedings of the 5th International Conference on Rough Sets and Knowledge Technology,6401.Berlin:Springer-Verlag,2010:719-726.

2010 MSC：68T37

(编辑 郑月蓉)

Extension of Three-way Decision Theory

WANG Lingling1,LYU Wangyong1,2

(1.CollegeofMathematicsandSoftwareScience,SichuanNormalUniversity,Chengdu610066,Sichuan;2.VisualComputingandVirtualRealityKeyLaboratoryofSichuanProvince,Chengdu610066,Sichuan)

In the traditional three-way decision theory,the objects can only be divided into 3 regions: acceptance,rejection or deferment.Therefore the theory can not be applied when the objects must be divided into more than 3 regions.In this paper,an extended theory is proposed,in which,combining the Bayes theory,taking the average minimum loss criterion as principle,the detailed derivation of the extended theory is presented so that the classic three-way dicision theory becomes a special case.

extension-three-way decision; the Bayesian theory; three-way decision; the threshold; evaluation function

2015-10-29

国家自然科学青年基金(11601357)和四川省教育厅自然科学重点基金(15ZA0030)

TP181

A

1001-8395(2017)02-0262-05

10.3969/j.issn.1001-8395.2017.02.019

*通信作者简介：吕王勇(1979—),女,副教授,主要从事随机信号处理的研究,E-mail:lvwangy@163.com