序贯三支监督多粒度决策方法

汪琳娜, 杨 新, 杨习贝

(1.四川交通职业技术学院 轨道交通工程系， 成都 611130) (2.西南财经大学 经济信息工程学院， 成都 611130) (3.江苏科技大学 计算机学院， 镇江 212100)

三支决策是加拿大里贾纳大学姚一豫教授提出的一种基于“三”和粒计算理论的思考、复杂问题求解和信息处理方法，其基本思想可以解释为由三分、治略和成效(trisecting，acting，outcome，TAO)3个基本要素组成的TAO模型[1-3].三支决策方法经过孵化期(1980—2006)和羽化期(2007—2016)正逐渐走向成长期(2017—)，可以大致分为狭义三支决策和广义三支决策[2,4].前者主要是在三支决策发展早期由解释粗糙集理论中三种分类规则(接受、拒绝和延缓/不承诺)演化而来的“三分而治”思想，后者则大大推动了三支决策理论走向更广阔的应用场景.目前三支决策思想被国内外学者成功应用在诸多领域，衍生出一系列的“三支方法”，如三支分类[5-6]、三支聚类[7]、三支冲突分析[8]、三支概念学习[9]、三支主动学习[10]、三支推荐[11]和三支图像识别[12]等.

传统的静态三支决策只是在单一粒度下考虑实施一次三支决策，而动态三支决策提供了一种多层次和多视角的多阶段决策问题解决方法，其典型模型是序贯三支决策.基于粒结构的结构化思维、结构化问题求解方法和结构化信息处理方式的粒计算三元论思想[13]，序贯三支决策框架主要是通过构建多层次的粒度、多样性的对象描述和评价、多元化的粒度代价结构来实现一种快速、低成本、高收益和容错的动态决策，以此来平衡决策过程代价和决策结果代价[14].近年来，围绕序贯三支决策的理论和应用研究层出不穷.文献[12,15]通过构建图像的多粒度结构提出了一种基于序贯三支决策的代价敏感人类识别方法，并推广到基于深度神经网络的特征粒度提取和识别问题中.文献[16]设计了一种基于序贯三支决策思想的粗糙集属性约简方法.文献[17]在局部和全局视角给出一种基于合理信息粒度的序贯三支分类模型.文献[18-20]提出了一种广义的增量序贯三支决策框架，并面对多类和混合动态数据构造了高效的序贯三支处理方法.基于序贯三支决策在理论、方法和应用方面的已有研究成果，文中在邻域系统中用已有或者预测的对象决策类别信息(样本标记信息)来帮助构建和优化多层次的粒度结构，以此来提高序贯三支决策方法的效率.

基于序贯三支决策理论，如何生成和构建合理的多粒度结构是一个关键问题.在邻域系统中，对象的邻域粒化是构建多层次粒度结构的基本操作.为了在多阶段的决策过程中有效快速地降低问题的不确定性，需要在多层次的粒度结构中构造出合适粒度的邻域粒子，过大或者过小的粒子都会影响序贯三支决策的决策过程代价和决策结果代价.目前针对邻域系统普遍的造粒方式都是通过一个邻域阈值δ来定义邻域关系RN，从而得到邻域粒子.但该方法在提高邻域粒子质量方面的效率有限.为了解决这个问题，文献[21]在邻域关系中增加了对象间伪标记相同的约束条件，采用K-means聚类得到的伪标记来优化邻域粒子.文献[22]运用监督粒化策略构建了一个新的邻域关系，并验证了相应的邻域属性约简方法的性能.文献[23]利用已有的决策类别信息构建了一个监督邻域粗糙集模型，提出的类内阈值δIntra和类间阈值δInter能够更好地控制邻域粒子的构造过程，且当类间阈值δInter=1时退化为文献[18-20]提出的方法.

基于以上分析，文中将在邻域三支决策模型中采用类内和类间两种阈值，借助决策类别等监督信息来生成多粒度粒子，以此来提升多层次粒度结构的构造质量，实现高效的序贯三支决策.

1 邻域三支决策模型

传统决策粗糙集模型只能通过等价关系处理名义型数据.文献[24]提出一种可以同时处理数值型和名义型数据的邻域粗糙集分类模型.此后，文献[25]提出了一种基于邻域关系的决策粗糙集模型，并讨论了基于最小决策代价的属性约简方法.与上述两种方法不同，文中运用高斯核函数[26]来构建一种基于邻域相似阈值的三支决策模型.

定义1假设一个四元邻域决策信息系统NDS=(U,A,V,f)，其中论域U表示一个非空有限的对象集合；A表示一个非空有限的属性集合，包含条件属性集C和决策属性集D，A=C∪D；V=∪Vb表示值域，Vb是对象在属性b下的所有可能取值;f:U×A→V是一个映射函数，使得∀b∈A，x∈U,f(x,b)∈Vb.

定义2给定一个邻域决策信息系统，对任意的x∈U和B⊆C，定义对象x的邻域粒子为：

γB(x)={y|y∈U,ΓB(x,y)≥γ}

(1)

式①中：高斯核函数为：

ΓB(x,y)=exp(-‖x-y‖2/σ)

(2)

式中：σ为高斯核函数的宽度参数，相似阈值γ满足0≤γ≤1.

基于上述定义，可以得到相应的邻域关系为：

RB(x)={(x,y)∈U×U|ΓB(x,y)≥γ}

(3)

其中满足以下3条性质：

(1) 0≤ΓB(x,y)≤1；

(2)ΓB(x,x)=1；

(3)ΓB(x,y)=ΓB(y,x).

显然基于相似阈值的邻域关系RB(x)满足自反性和对称性，但不满足传递性.对任意的xi,xj∈U，邻域关系RB(x)也可以表示为一个n×n的关系矩阵MB=(rij)|U|×|U|(i,j=1,2,…,U)，其中：

(4)

下面给出基于相似阈值的邻域三支决策模型.

定义3给定一个邻域决策信息系统，假设一对阈值对(α,β)，其中0≤β<α≤1.对任意的X⊆U和B⊆C，论域U可以被划分为两两不相交的3个区域为：

(5)

其中条件概率Pr(X|γB(x))=|X|γB(x)|/|γB(x)|，也称为粗糙隶属度函数，|·|表示集合的势.

通过贝叶斯最小风险决策理论可以推导出计算定义2中阈值对(α,β)的数学公式.假设考虑一个二分类问题.给定决策状态集合Ω={X,XC}和决策行动集合A={aP,aB,aN}，其中X和XC互补，行动集中aP,aB,aN分别表示将对象分类到正域、边界域和负域的决策动作.给定一个损失函数矩阵为：

(6)

式中：λPP,λBP,λNP分别为当状态为X时采取行动aP,aB,aN下的损失；λPN,λBN,λNN分别为当状态为XC时采取行动aP,aB,aN下的损失.因此可分别采取行动aP,aB,aN下的期望损失为：

(7)

根据贝叶斯决策准则，选择期望损失最小的行动集作为最佳的行动方案.基于此可以推导得出阈值对(α,β)的具体计算公式为：

(8)

2 监督邻域三支决策模型

传统单一的阈值设置不能更好地处理和优化邻域粒化问题.为了降低邻域粒子的不确定性，下面通过引入类内阈值γIntra和类间阈值γInter生成监督邻域粒子来构造一个监督邻域三支决策模型.

定义4给定一个邻域决策信息系统，决策属性D将U划分为N个决策类，表示为D={D1,D2,…,Dk},k=1,2,…,N.假设类内阈值γIntra和类间阈值γInter满足0≤γIntra≤1和0≤γInter≤1，对任意的x∈U和B⊆C，对象x的监督邻域粒子为：

U{y|y∉Dk(x)∧ΓB(x,y)≥γInter}

(9)

式中：Dk(x)为对象x所在的决策类集合.

根据定义4，监督邻域关系可以表示为：

γIntra∨y∉Dk(x)∧ΓB(x,y)≥γInter}

(10)

定义4给出了一种运用决策类别信息生成与对象x相似的监督邻域粒子方法.根据监督类别信息，当两个对象属于同一决策类时，使用类内阈值计算监督邻域粒子；相反，如果两个对象不属于同一决策类时，则使用类间阈值.对比式(1)，监督邻域粒子可以通过控制类内阈值γIntra和类间阈值γInter优化邻域粒化，降低多粒度结构下的不确定性.通常有3种方法来设置这两种阈值，即：

(1) 0≤γIntra<γInter≤1

(2) 0≤γInter<γIntra≤1

(3) 0≤γIntra=γInter≤1

为了增加邻域粒子中的类内对象，同时减小邻域粒子中的类间对象，一般可采用第一种方法，对类间对象采取更加严格的粒化机制，即让类间阈值γInter大于类内阈值γIntra.文中采用第一种方法.显然第三种方法会退化为定义2中邻域粒子的定义.相对于定义2，通过合理设置可以得到邻域粒子的一些性质.

通过定义1和定义4很容易证明以上3个性质.相对于定义1的方法，运用监督邻域的类内和类间两种阈值可以很好地控制邻域粒子的质量，在邻域粒子中增加类内对象，减少类间对象，从而降低多粒度结构的不确定性.

假设把决策类Dk,k=1,2,…,N作为定义3中论域U的子集X，利用监督邻域粒子可以得到一个新的监督邻域三支决策模型.

定义5给定一个邻域决策信息系统，假设一对阈值对(α,β)，其中0≤β<α≤1.对任意的B⊆C和决策类Dk,k=1,2,…,N，决策Dk关于属性B的监督邻域三支决策区域可表示为：

(10)

对于所有决策类D，可以得到：

(11)

为了分析基于监督邻域下的多粒度结构的不确定性变化，给出3种基于监督邻域的度量方法.

定义6给定一个邻域决策信息系统，对任意的B⊆C，监督知识粒度可以定义为：

(12)

定义7给定一个邻域决策信息系统，对任意的B⊆C，监督近似质量可以定义为：

(13)

定义8给定一个邻域决策信息系统，对任意的B⊆C，监督条件熵可以定义为:

(14)

根据三种不确定性度量定义，相对于定义3的邻域三支决策模型，当采用提出的监督邻域方法时，可以的得到一些性质.

性质3给定一个邻域决策信息系统，GKSN表示监督知识粒度(采用类内阈值γIntra和类间阈值γInter)，GK表示非监督知识粒度(采用单一阈值λ)，对任意的x∈U和B⊆C，当0≤λ=γIntra<γInter≤1时，有GKSN≤GK.

性质4给定一个邻域决策信息系统，AQSN表示监督近似质量(采用类内阈值γIntra和类间阈值γInter)，AQ表示非监督近似质量(采用单一阈值λ)，对任意的x∈U和B⊆C，当0≤λ=γIntra<γInter≤1时，有AQSN≥AQ.

性质5给定一个邻域决策信息系统，CESN表示监督条件熵(采用类内阈值γIntra和类间阈值γInter)，CE表示非监督近似质量(采用单一阈值λ)，对任意的x∈U和B⊆C，当0≤λ=γIntra<γInter≤1时，有CESN≤CE.

以上性质可通过定义1、定义4和性质4容易得到.当采用监督邻域方法，设置阈值满足0≤λ=γIntra<γInter≤1时，会获得比非监督邻域方法更小的知识粒度和条件熵，以及更高的近似质量.显然按照这3个度量的解释，运用监督邻域方法可以大大减小邻域粒子和多粒度结构的不确定性.

3 基于监督多粒度的序贯三支决策模型

运用监督邻域方法构建一个多层次的监督多粒度结构来实施序贯三支决策过程，首先给出一个m层的监督多粒度结构定义.

(15)

且监督邻域粒子满足：

则m层的监督多粒度结构可以定义为：

(16)

在定义6中，通过在m层的监督多粒度结构设置不同的类内阈值γIntra和类间阈值γInter，不仅可以得到随着层次增加逐渐单调减小的监督邻域粒子，而且将提升监督邻域粒子的质量，从而可以大大优化多层次的粒度结构.

0≤β1≤β2≤…≤βm<αm≤…≤α2≤α1≤1

(17)

则在监督多粒度结构的第i层，对决策类Dk,k=1,2,…,N，监督邻域三支决策区域的计算可以表示为：

(18)

表1 第i层的7种选择情况

在监督多粒度结构的第i层，所处理的对象Ui全部来自于第i-1层，表1提供了7种选择情况.在传统序贯三支决策模型中，通常会选择第二种情况，即在粒结构的每一层只处理上一层中边界域中的对象.通过多阶段的序贯三支决策，边界域中的对象逐渐单调减小，而正域和负域中的对象逐渐单调增多.其他6种情况也可以被用在多类分类问题、人才选拔和异常检测等应用领域.

4 实验分析

文中运用4组UCI数据集(只包含数值型属性)来验证所提方法的效率，具体数据信息见表2.电脑配置为Intel (R) Core (TM) i5-4210U CPU @ 1.70GHz，12G内存，Windows10操作系统，Matlab2016a实验平台.

表2 数据集描述

针对监督多粒度方法和非监督多粒方法在序贯三支决策的不确定性方面进行比较，采用了3种度量标准，即知识粒度、近似质量和条件熵.

在对比实验中，采用表1的第二种情况，高斯核参数均设置为σ=0.8.考虑5层次的多粒度结构，每一层的属性个数设置采取均匀递增方式.比如数据集Ionosphere，共34个属性，可设置第一层为2个属性，此后每层递增8个属性，即第二层到第五层属性个数分别为10、18、26和34.其它3个数据集按照类似方法设置.监督多粒度方法的类内阈值γIntra和类间阈值γInter、非监督多粒度的相似阈值γ和决策阈值对(α,β)的设置见表3.

表3 阈值设置

表4给出了4个数据集在5层粒度结构下监督和非监督知识粒度的对比情况.GKSN为监督知识粒度，而GK为非监督知识粒度.由实验结果可以看出，从第一层到第五层，两种知识粒度都逐渐递减.此外，对比两种知识粒度，可以发现在大多数情况下，监督知识粒度GKSN都普遍小于非监督知识粒度GK.这表明非监督多粒度方法可以更好地在多层次粒结构上更好地加速知识粒度的由粗到细的变化过.

表4 知识粒度的对比

表5和表6分别给出了监督多粒度和非监督对粒度在近似质量和条件熵上的对比情况.AQSN为监督近似质量，AQ为非监督近似质量；CESN为监督条件熵，CE为非监督条件熵.由表5可以看出,大部分的近似质量都会随着粒度层次的增加而增加，而且监督多粒度方法的近似质量基本上都大于非监督方法.在表6中，大部分的条件熵都会随着粒度层次的增加而减小，而且监督多粒度方法的条件熵基本上都小于非监督方法.由此可见，在序贯三支决策过程中，所提出的监督多粒度方法熵在不确定性方面表现出了更好的性能.

表5 近似质量的对比

表6 条件熵的对比

表7给出了监督多粒度方法和非监督多粒度方法在序贯三支决策过程中三个决策区域的对象百分比变化情况，其中USS3WD表示非监督多粒度方法，而SS3WD表示监督多粒度方法.由表7可看出，随着粒度层次的增加，边界域逐渐减小，而正域和负域逐渐增大，说明决策的不确定性在逐渐减小.对比两种方法发现，监督多粒度会加速样本从边界域转移到正域或负域的速度，即监督多粒度会加快信息不确定性的降低.

表7 序贯三支决策区域的对比

5 结论

传统邻域多粒度方法采用单一阈值粒化得到粒子，大大限制了序贯三支决策中多层次粒结构的构造性能.文中运用已有的对象决策类别信息，采用类内阈值和类间阈值的方法在序贯三支决策过程中实现了对邻域粒子和多粒度结构的优化，大大提升了降低不确定性的速度，提高了多阶段三支决策的性能.序贯三支决策的关键是构建多层次的粒度结构，下一步会考虑更多有用的动态监督信息，研究序贯三支决策中的信息粒化和多粒度结构构建问题.