王玲玲，吕王勇，高艳萍，蔡林芝

（1.四川师范大学 数学与软件科学学院；2.可视化计算与虚拟现实四川省重点实验室，成都 610068）

0 引言

三支决策是一种在不确定或不完整信息条件下的决策方式，主要用于当可用信息不足时，做出待判从而进一步观察的决策。自三支决策理论提出以来[1]，三支决策理论迅速发展，并取得了众多成果。如针对三支决策中阀值对的确定进行的研究，贾修一等[2,3]提出的一种自适应求三支决策中决策阀值的算法，及一种求三支决策阈值的模拟退火算法；陈刚等[4]给出了求三支决策最优阀值的新算法。另外，很多学者从三支决策的理论扩展方面进行了深入研究，张艳萍等[5]研究了基于CCA的代价敏感三支决策模型，薛占熬等[6]进行的基于概率图的三支决策模型研究，李丽红等[7]提出了三支决策中不承诺决策的转化代价与风险控制。三支决策理论在应用方面也取得了很多成果，如李建林等[8]研究出了多阶段三支决策垃圾短信过滤模型，谢骋等[9]给出了基于三支决策粗糙集的视频异常行为检测模型，黄顺亮等[10]提出了基于三支决策理论的客户细分方法，徐久成等[11]研究的基于三支决策的支持向量机增量学习方法等。

目前三支决策理论只能将对象最终划分到接受域、拒绝域和暂时不能判定的待判域，在处理需要将对象划分到更多区域的问题面前就无能为力了。本文在传统三支决策理论的基础上进行扩展，使其能够应用于将对象划分到任意多区域的问题上。

1 三支决策理论

其中，|·|表示集合的基数。

首先给出对象的价值信息表 T=(U，B，{Vb|b∈B}，{Ib|b∈B})，其中，U是所需要研究的全部对象组成的有穷集合；B是研究对象的所有属性组成的集合，这里具体指的是对象的评价指标组成的集合；Vb是各属性所有取值组成的非空集合；Ib:U→Vb是信息函数，它将U中每一个对象的某个属性b映射到Vb上，定义了每个对象在各个指标上的取值，即，Ib(x)∈Vb。

对于全集U，在客观上可以将其划分为两个子集C和Cc，分别表示满足条件的对象组成的集合和不满足条件的对象所组成的集合，且有U=C∪CC。

定义U上的一个等价关系R，若有Ib(x)=Ib(y)，则x和y等价，记为xRy。所有满足等价关系R的对象可以组成等价类[x]。引入评价函数P(C|[x])，表示将等价类[x]中对象x划分到集合C的概率，由评价函数P(C|[x])和一对阀值(α，β)可以将全集U划分为三个两两不交的区域，分别表示为正域POS(C)、边界域BND(C)和负域NEG(C)，且有 U=POS(α，β)(C)∪ BND(α，β)(C)∪NEG(α，β)(C)：

由于将对象x划分到不同区域所需要付出的代价不同，记λap、λrp、λdp分别表示当对象 x属于集合C时，被划分到POS(C)、NEG(C)、BND(C)所需要付出的代价，λapˉ、λrpˉ、λdpˉ分别表示当对象 x 属于集合CC时，被划分到POS(C)、NEG(C)、BND(C)所需要付出的代价。给出形如表1的一张三支决策代价表[10]。

表1 三支决策代价表

在表1给出的六个代价中，λap、λap表示正确分类的代价，λrp、λapˉ表示错误分类的代价，λdp、λdpˉ表示将对象划分到边界域的代价，因此决策代价值有如下关系成立：0≤ λap≤ λdp≤ λrp,0 ≤ λrpˉ≤ λdpˉ≤ λapˉ。

下面给出对象x的决策代价函数：

RPOS(x)、RNEG(x)、RBND(x)分别表示对象x被划分到POS(C)、NEG(C)、BND(C)所需要付出的总代价。

选择决策损失最小的行动方案为最优方案，因此决策规则可以描述为：

若 RPOS(x)≤RNEG(x)，且 RPOS(x)≤RBND(x)，则 x∈POS(C)

若 RNEG(x)≤RPOS(x)，且 RNEG(x)≤RBND(x)，则 x∈NEG(C)

若 RBND(x)≤RPOS(x)，且 RBND(x)≤RNEG(x)，则 x∈BND(C)

则阀值 (α，β)可以表示为[12]：

下面就给出评价函数P(C|[x])的求解方法[13]。

借助贝叶斯理论,P(C|[x])可以如下计算：

式（3）中P([x])不易直接求得，因此借助公式P(C|[x])=O(P(C|[x]))·P(CC|[x]) 求解 P(C|[x])，为求解 P(C|[x])，先求解O(P(C|[x]))：

又P(CC|[x])=1-P(C|[x])，因此：

至此评价函数和阀值都已经确定，则可以将对象划分到正域、负域和边界域中。

2 N支决策理论

第i支：

第N支：

引入评价函数P(Ci|[x])，定义为：

进一步将式（6）用如下形式表示：

第i支：

第N支：

rgN={x∈U|0＜P(Ci|[x])＜1，i=1，2，…，N-1} （7）

从上面公式可以看到，虽然借助极端值0和1可以将全集分成互不相交的N个区域，但当0＜P(Ci|[x])＜1时，P(Ci|[x])的具体取值大小在分类中却并没有发挥作用，而且概率取1的可能性太小，并没有很好地将所有客户划分开来，因此本文提出用阀值 (α0，α`1，α2，…，α2(N-1)-1)来代替公式中的0和1，（7）式可以表示为如下形式：

第i支：

第N支：

至此已经给出了N支决策模型，接下来就是评价函数 P(Ci|[x])(i=1，2，…，N-1) 和 阀值 (α1，α2，…，α2(N-1)-1) 的确定。

由于将对象x划分到不同区域所需要付出的代价不同，设λj，i表示将属于集合Ci的对象划分到rgj的代价，如，λ1，N-1表示将属于集合CN-1的对象划分到rg1的代价。因此给出形如表2的一张N个分类结果N-1个状态的决策代价表。

表2 N支决策代价表

划分为rgj的对象x的代价函数就是该对象属于集合Ci的概率P(Ci|[x])与该对象属于集合Ci又被划分为rgj的代价值 λj，i(i=1，2，…，N-1)的乘积的累加之和。

则对象x被划分到rgj的决策代价函数为：

由于总是选择决策损失最小的行动方案为最优方案，因此决策规则可以描述为：

若对∀j，有：

成立，则 x∈rgj。

此决策过程的实际意义是：当采取某种决策动作所带来的风险代价不超过其他N-1种决策动作所带来的风险时，就采取该决策动作，表现形式为将对象划分到相应区域。

根据式（10）解得 P(Ci|[x])(i=1，2，…，N-1)满足的条件：

其中当 i=r时，λd，i-λj，i=0 。

由P(C1|[x])的值来确定α1的取值，由P(C2|[x])的值来确定α2，α3的取值，依此类推，由 P(CN-1|[x])的值来确定α2(N-1)-2，α2(N-1)-1的取值，下面是阀值 α1，α2，…， α2(N-1)-1的表达式：

其中，当i=1时，α2i-2=α0=1；当 i=N-1时，α2i-1=α2(N-1)-1=1。

阀值确定后，下面确定评价函数P(Ci|[x])，i=1,2,…，N-1。

借助公式（5），可以求得P(Ci|[x])。由于其中，P(C)为先验概率，且

下面就分析式（11）中P([x]|Ci)和P([x]|)的求解。

[x]在这里描述为对象集合在属性 (b1，b2，…，bn)下所对应的取值 (v1，v2，…，vn)，且 Ibk(x)=vk，其中，n 为指标的个数，vk为等价类[x]中某对象x在第k个指标下的取值。

再借助朴素贝叶斯独立性假设，即假设对任意的k≠l有vk与vl相互独立，有如下公式成立：

将式（12）代入式（11）即可求得O(P(Ci|[x]))，从而由式（5）可以解得 P(Ci|[x])。

至此，评价函数P(Ci|[x])就最终确定了。

3 仿真实验

检验N支决策理论的有效性和K-均值聚类方法进行对比，主要通过对比此两种分类结果误判率的大小来最终验证N支决策模型分类方法的有效性。

主要用误判率的大小来检验N支决策理论的有效性。选取鸢尾花的150个数据[14]进行扩展三支决策理论分类的仿真实验。

3.1 仿真步骤及相关理论推导

此组数据收集了150朵鸢尾花的4个属性萼片长、萼片宽、花瓣长、花瓣宽的取值，序号为1～150，也给出了先验信息：序号为1～50的鸢尾花分为第一类，51～100的鸢尾花为第二类，101～150的鸢尾花为第三类，则每类的先验概率为接下来就依N支决策模型的步骤对这150朵鸢尾花进行分类。首先将150朵鸢尾花数据标准化、离散化，再将具有相同属性值的花划分到同一类，至此获得此组数据的众多等价类；接下来获得分类的决策代价表，以及根据决策规则获得的阈值；最后求每一等价类下的评价函数p(Ci|[x])，由第三部分知此评价函数的求解公式如下：

且有：

令先验概率 P(C1)、P(C2)、P(C3)分别为 π1、π2、π3，化简可得：

同理可得到 p(C2|[x])、p(C3|[x])的表达式。

3.2 数据仿真结果

首先将此150个数据进行标准化和离散化处理，进一步以所有对象的属性为依据，划分为以下18个等价类（见表3）。

然后给出分类所需要的决策代价，获得如下决策代价表，见表4。

借助上一部分 p(Ci|[x])的求解方法对每一等价类的概率进行求解，结果见表5。

将每个对象的概率值代入决策代价函数式中，可以得到此N支决策的阈值，而后可以将对象做如下划分，见表6。其中括号中表示与原始分类有差异的四个对象对应的序号。对于以上四个对象，本文进一步分析：

表3 等价类的划分

表4 决策代价表

表5 每个等价类的概率值

表6 分类结果对比

由于原始分类时每类都有类中心，那么若对象离该类类中心最近，就会被划分到该类别中去，对以上四个有差异的对象，有如下结论，见表7。

表7 个别分类有差异的对象的进一步分析

其中b1表示萼片长，b2表示萼片宽，b3表示花瓣长，b4表示花瓣宽；d1表示对象到第一类类中心的距离，d2表示对象到第二类类中心的距离，d3表示对象到第三类类中心的距离。

可以看到，将对象107和120划分到第二类更合理，从而说明此N支决策理论误判率为1.3%。

而在用K-均值快速聚类法时，同样可以对与给定的标准有偏差的14个对象与三个类的类中心的距离进行比较，可以得到此判断方法的误判率为6%，因此可以看到N支决策理论分类效果更好，此方法更有效。

4 总结

本文立足于传统的三支决策理论，对传统的三支决策理论在决策中只能把对象划分为正域、负域和边界域三个区域的局限性进行改进，提出了N支决策理论，它借助贝叶斯理论和决策代价表，以决策的平均损失代价最小为原则，对N支决策理论的决策规则进行了合理的定义，从而确定了N支决策中最为重要的阈值。另外还给出了评价函数的求解方法，并给出了详细的推导过程，从而借助阈值和评价函数就能将对象划分为N类。本文最后借助N支决策模型对鸢尾花的分类问题进行分析验证，并与K-均值快速聚类法分类结果进行比较，说明了本文提出的N支决策理论的有效性。N支决策理论使传统的三支决策理论成为特例，拓宽了三支决策理论的应用领域，使三支决策理论能够应用到更多的实际问题中。