基于代价敏感的序贯三支决策最优粒度选择方法

张清华 庞国弘 李新太 张雪秋

(重庆邮电大学计算智能重庆市重点实验室 重庆 400065)

1 引言

在实际决策中，如何处理代价敏感问题一直是研究的热点之一。代价通常分为决策代价(误分类代价和延迟代价)和测试代价(测试成本)。一般地，决策代价随着信息逐步增加而降低，而测试代价随着信息增加而增加，两者呈负相关关系且量纲不同。例如，在医疗诊断中，若患者偏好高精度的诊断，会选择成本较高的检查项目；相反，若患者偏好普通的诊断，往往会选择成本低的检查项目。这两种情况都广泛发生在实际应用中，因此如何实现代价最小的决策是值得研究的。

现阶段许多专家学者将代价敏感研究运用于机器学习理论中，并取得了重要的研究成果[1,2]。目前，代价敏感方面的研究方法主要分为以下3个方面：从决策代价敏感的角度来看，Li等人[3]结合序贯三支决策提出了一种最小化代价的决策模型；Zhang等人[4]基于邻域覆盖方法，根据损失函数改变覆盖半径，来减小分类损失；Jia等人[5]通过定义一种新的属性约简方法使模型的决策代价最小。同时，在降低测试代价方面，Yang等人[6]提出了一种测试代价最优的粒度结构选择回溯算法。Min等人[7]在测试代价中引入代价敏感决策系统的层次结构。另外，在同时考虑决策代价和测试代价的研究中，广大学者也进行了相应的工作[8,9]。

序贯三支决策[10]是近年发展起来的一种处理不确定性决策的方法。作为粒计算[11–13]概念下的具体模型，其目标是提供一种灵活的机制和方法，帮助用户在信息粒化过程中做出合适的决策。目前在图像分析、属性约简、语音识别等方面均已取得了较大的成果[14–17]。代价敏感的序贯三支决策从粒计算的角度提高了三支决策的有效性，实现了粗粒度到细粒度渐进式的决策过程。但在最优粒度选择方面，仍存在一些问题需要改进。首先，在构建多粒度空间过程中，从属性重要度选择方法上来看，存在没有充分考虑数据中有冗余属性或不相关属性的问题，这样可能会增加额外的测试代价或有损模型的性能。其次，随着获取信息的增多，针对两类错误分类和两类不确定性分类[18]的代价参数是保持不变的，使得代价参数在序贯三支决策渐进计算过程中缺乏一定的自适应性，导致在粗粒层产生较低的分类精度，从而影响模型的最优粒度选择。此外，在现有计算总代价的方法中，未能考虑测试代价与决策代价测量尺度或量纲不统一所带来的影响，从而丢失部分关键因素，导致直接进行计算得到的结果不准确。针对这些问题，本文首先利用卡方检验剔除高相关性的条件属性，再借助信息增益计算属性重要度并根据得到的属性重要度序列进行多粒度空间的构建。其次，针对两类错误分类和两类不确定性分类[18]的代价参数缺乏自适应性，结合渐进计算的思想，借助惩罚函数来对代价参数设置相应的惩罚规则，有效提升了模型的分类精度。最后，利用变异系数构建了一种合理的代价结构，实现了同量纲下的代价计算，从而可以有效利用测试代价和决策代价的信息。实验表明所提出的模型在不同的代价场景下能够产生合理的多粒度空间结构，同时所得到的代价最小的粒度空间也更符合实际应用场景代价最小的需求。

2 基础知识

定义1[19,20]给定决策信息系统S=(U,C ∪D,V,f)，其中U表示非空有限论域；C和D分别表示条件属性集和决策属性集，且C ∩D=∅ ；V表示属性值的集合；f:U×C →V表示一个信息函数，用于指定U中每一个对象x的属性值。

定义2[19,20]给定决策信息系统S=(U,C ∪D,V,f)，对于任意属性子集A ⊆C，等价关系EA定义为

等价关系可形成论域U上的一个划分，记为U/EA，简记为U/A。给定对象x∈U，表示在属性子集A所形成的等价关系下的等价类，简记为[x]A或 [x]。

相比于二支决策，三支决策理论的关键在于引入了延迟决策，即当决策对象的信息不足时采用延迟决策，等待收集更多有用信息后再重新进行决策。这种对决策对象的认识从粗粒度向细粒度转化，使边界域中的对象逐渐被正确决策，进而形成一种序贯决策方法。下面介绍序贯三支决策的一些基本概念。

定义3[10]给定决策信息系统S=(U,C ∪D,V,f)，假定A1,A2,...,An表示一组条件属性集，且满足A1⊂A2⊂...⊂An ⊆C。对于∀x∈U，有

定义4[10]给定决策信息系统S=(U,C ∪D,V,f)，设A1,A2,...,An表示一组条件属性集，且满足A1⊂A2⊂...⊂An ⊆C。在这种条件属性集的序贯情形下多粒度空间记为GS，在第i(i=1,2,...,n)层，GS的粒度结构记为GLi,，GLi和GS定义为

在多粒度空间中，给定第i层的阈值(αi,βi)，则第i层的接受域、延迟域和拒绝域可以表示为

粗糙集理论为序贯三支决策奠定了理论基础，从多粒度的角度来看，随着属性的增加，等价类会被进一步的细分。依据条件属性集构建的多粒度空间可以用树形结构来表示，最顶层表示论域的信息，即最粗粒层，随着属性的逐步加入，信息粒度逐步变细。因此，序贯三支决策的决策过程能够构成一个多粒度空间。图1简要介绍了多粒度的构造过程示意图。

图1 多粒度空间的构造过程

3 代价敏感的序贯三支决策最优粒度选择模型

3.1 基于信息增益和卡方检验的属性重要度选择方法

多粒度空间的构建与属性重要度的选择是紧密相连的，如果充分考虑条件属性内在的关系和条件属性与决策属性之间的关系来进行属性重要度选择，所得到的多粒度空间往往会更优。因为数据集中有些条件属性是冗余甚至是不相关的。冗余属性的存在会增加额外的测试代价，而不相关的属性会有损模型的性能。因此，对条件属性进行相关性分析是有必要的，从而使模型泛化能力更强。

卡方检验是一种用途很广的计数资料的假设检验方法，属于非参数检验，主要是比较两个及两个以上样本率(构成比)以及两个分类变量的关联程度。其主要思想在于比较理论频数和实际频数的吻合程度或者拟合优度，用来描述两个事件的独立性。卡方值χ2越大，说明两个事件的相互独立性越弱。

定义5(卡方分布[21])设s个相互独立的随机变量Y1,Y2,...,Ys，且符合标准正态分布N(0,1)，则这s个随机变量的平方和为服从自由度为s的卡方分布，记为Q～χ2(s)。

定义6(卡方检验[21])给定数据的实际值A和理论值T，则卡方检验的公式为

理论上，如果卡方值越大，二者偏差程度越大；反之，二者偏差越小；若两个值完全相等时，卡方值为0，表明理论值与数据的实际值完全符合。因此，通过卡方检验可以更好地剔除条件属性集中的冗余属性，减小测试代价。

同时，多粒度空间的构建与条件属性的划分能力是紧密相连的，如果充分考虑条件属性的划分能力来进行论域的划分，所得到的多粒度空间往往会更优。目前，属性重要度选择的方法大多基于熵。熵是用来描述论域中不确定性的一种度量方法。熵越大，论域的不确定性就越大。因此可以使用信息增益(论域集合划分前后熵的差值)来衡量使用当前属性对于论域划分效果的好坏。

定义7(信息增益[22,23])给定决策信息系统S=(U,C ∪D,V,f),B ⊆C。假设论域U在等价关系EB和ED下的划分分别为U/B={B1,B2,...,Bm}和U/D={D1,D2,...,Dp}，信息增益Gain(D,B)可定义为

基于信息增益的属性重要度做出选择的规则是：对于待划分的论域，在划分前的熵是一定的，而划分后的熵是不定的，且划分后的熵越小说明使用此属性划分所得到的子集的不确定性越小，即纯度越高，因此划分前后熵值差异越大，说明使用当前属性划分论域，其不确定性越小。以信息增益作为划分论域的属性选择的标准，在属性选择上更倾向于选择取值较多的属性，这样在多粒度空间构建的过程中粒度空间往往能够朝着最快到达最细粒度空间的方向发展，因此可以选择使得信息增益最大的属性来划分当前论域。

3.2 惩罚规则下代价参数和阈值的变化规律

因为基于决策粗糙集的三支决策存在一定的容错能力，所以3个域中都可能存在不确定性进而产生相应的代价。在序贯三支决策中，随着属性的增加，等价类被进一步细分，信息粒度逐步变细，对象之间的区分也越明显，边界域中的对象可能会被重新分类，分类精度会进一步的提升，所以针对错误分类和不确定性分类应该给予更高的代价惩罚。本文借助文献[24]中的思想，考虑损失函数在随着粒度变化的情况下，利用惩罚函数对其进行相应的修改。因为在实际应用中，通常可以通过加大惩罚力度的方式来获取“优秀”的目标对象。同时，惩罚力度会随着惩罚次数的增加而增加，因此，惩罚函数必定是一个单调递增函数。进一步地，在序贯三支决策中，通过惩罚规则对代价参数进行修改，进而调整决策阈值(即α值的增大或β值的减小)，这样可以使等价类得到更准确的分类。同时，代价参数的值增大，即错分代价和延迟代价也会增高。所以，通过引入惩罚规则，利用代价参数值的增大进而提高决策精度。

考虑到采取不同行动会产生不同的损失，记和表示在第k层，x属于X时采取行动aB和aN下的损失；相似地，记和表示在第k层，x不属于X时采取行动aP和aB下的损失；另外，代价参数λPP和λNN表示正确划分下的代价，不产生代价损失。代价参数矩阵可以描述为表1。

表1 代价参数矩阵

根据贝叶斯决策理论，将属于目标集合的对象分类到接受域的代价要小于等于将其分类到延迟域和拒绝域中的代价。相似地，将不属于目标集合的对象分类到拒绝域的代价要小于等于将其分类到延迟域和接受域中的代价。基于这两种规则，可以得到代价参数之间存在以下规律，。因此决策阈值可以表示为

一般地，随着属性的增加，粒度变细，形成的等价类将发生变化，代价参数值增大，阈值也会相应地发生改变。

定理1与定理2同理可证。

因此，通过引入惩罚函数来处理实际决策过程中的代价参数变化，使得多粒度空间具有更好的适应性，能够动态地进行决策。

3.3 序贯三支决策模型的代价结构设计

在序贯三支决策中主要存在两种代价，第1种是因对象误分类或者需要延迟决策而产生的决策代价，第2种是因获得新的属性而产生的测试代价，即获取某些属性值的成本。在实际应用场景中，这两种代价都应该被考虑。因此，如何合理地结合决策代价和测试代价来解决问题具有重要意义。为了寻求决策代价和测试代价的最优平衡点，本文设计了一个启发式函数用来综合决策代价和测试代价。

因为产生测试代价的因素(时间、金钱、复杂度等)的维度不同，很难将各因素综合起来考虑。一般地，属性重要度越高的属性，它所拥有的分类能力越强，测试成本越高。

定义8给定决策信息系统S=(U,C∪D,V,f)，条件属性c(c∈C)对决策结果的影响度可以定义为

其中，I(c)的 值越大，该决策属性对属性c的依赖程度越高，说明属性c的影响度越大。属性影响度作为启发式信息来度量某一属性的分类能力，区分能力越大，带来的测试代价越高。因此，测试代价与属性重要度呈现正相关关系，所以条件属性c的测试代价可以定义为

其中，η是一个常数。

一般地，若两个条件属性对决策属性的影响度一致(即划分能力一致)，那么这两个条件属性具有一样的测试代价。

定义9在多粒度空间GS=(GL1,GL2,...,GLn)中，第i层的决策代价可以定义为

其中，GLi表示GS的 第i粒层，COST(POS(αi,βi)(Xi))表示产生第1 类分类错误带来的代价，COST(NEG(αi,βi)(Xi))表示产生第2类分类错误带来的代价，C OST(BND(αi,βi)(Xi))表示产生不确定性分类带来的代价。

因为测试代价和决策代价呈现负相关关系且量纲不相同，所以不能将其直接进行计算。为了更好地计算总代价，本文引入变异系数的概念，并基于变异系数定义一种综合客观的评价函数进行总代价计算的方式

C.V表示变异系数。

变异系数是衡量各组数据变异程度的一种统计量。在统计学中，如果两组数据的测量尺度相差太大，或者数据量纲不同，直接使用标准差来进行综合计算不合适，此时就应当消除测量尺度和量纲的影响，而变异系数可以做到这一点，它是原始数据标准差与原始数据平均数的比。因为变异系数没有量纲，因此得到结果是一个标量，可以客观地将决策代价与测试代价相结合。

4 实验对比及分析

4.1 实验设计

为了更好地说明所提模型的有效性和实用性，本文选取美国加州大学欧文分校(University of California Irvine,UCI)数据库的6个标准数据集进行了对比实验，并且每个数据集在两种不同的代价环境下进行实验。数据集的详细信息如表2所示。实验环境为8GB RAM,3.2 GHz CPU,Windows 10 system，编程语言是Python。

表2 数据集的描述

本文算法的框架如图2所示，可以分为3个过程：属性重要度选择、多粒度空间构建和最优粒度选择。其中属性重要度选择部分由信息增益和卡方检验构成；在多粒度空间构建时，为代价参数设置了惩罚规则；最后利用变异系数消除测试代价与决策代价量纲的差异。

图2 算法框架

在计算算法的时间复杂度时，往往以最坏情况计算。根据上述实验步骤，算法的时间复杂度主要取决于多粒度空间构建，从图1中可知，多粒度空间是一个自顶向下且具有偏序关系的层级结构，层数是由条件属性集的基数(属性个数)所决定的。因属性重要度的选择方法是由卡方检验和信息增益所构成，因此需要对所有的属性进行计算：第1步属性重要度选择过程的时间复杂度为O(n)；多粒度空间的构建是基于经过属性重要度方法计算后条件属性集的属性个数的，所以构建多粒度空间的时间复杂度为O(n)，同时在每一粒层上借助惩罚规则对代价参数进行修改的时间复杂度为O(1)，因此第2步构建多粒度空间的时间复杂度为O(n)；第3步在最优粒度选择过程中，需要对全部粒层进行遍历计算，同样时间复杂度为O(n)。因为算法中3个步骤是递进关系，所以该算法整体的时间复杂度为O(n)，其中n表示序贯三支决策的条件属性集中属性的个数。

4.2 实验结果分析

本节对4.1节所选的UCI数据集进行了实验，为了方便研究，首先将数据集中的字符型数据转化为整数型数据；其次给出2组代价参数，其数值均满足第4节中定义并通过代价参数计算决策阈值对(α,β)，如表3所示；此外，为了体现最优化的思想，设计惩罚函数对代价参数进行惩罚。本文所选的惩罚函数是φ(x)=log2(1+0.1×k)×λσ，其中σ={NP,BP,PN,BN}。

表3 代价参数

通过实验发现，运用上述的算法均可以得到不同数据集的代价最小的最优粒层，验证了算法的实用性。图3和图4给出了不同代价参数下的各数据集的代价变化以及最优粒层。另外，表4和表5分别列出了各数据集最优粒层的详细数据。从图3、图4和表4、表5中清楚地看出，所选的最优粒度较符合人类的认知。同时，所提出的代价结构利用标准化和变异系数进行处理能够消除因测试代价和决策代价尺度和量纲不同所带来的影响。

表4 第1组代价参数下各个数据集最优粒层信息

表5 第2组代价参数下每个数据集最优粒层信息

图3 第1组代价参数下各数据集最优粒层的代价变化

图4 第2组代价参数下各数据集最优粒层的代价变化

具体地，针对Breast Cancer Wisconsin数据集，通过使用最优粒度选择算法，将在不同代价参数环境下寻找一个总代价最小的粒度空间。从实验结果可以看出，在第1组代价参数下，代价最小的最优粒度空间由{c2,c3,c6,c7,c5,c8,c4,c9}诱导而得到并且构造多粒度空间的顺序是c2→c3→c6→c7→c5→c8→c4→c9。此时构建的粒度空间总代价最小，为0.3684(标准化后)；在第2组代价参数下，代价最小的最优粒度空间{c2,c3,c6,c7,c5}由诱导而得到，并且构造多粒度空间的顺序是c2→c3→c6→c7→c5。此时构建的粒度空间总代价最小，为0.4459(标准化后)。

从以上6个数据集的实验结果可以看出，选取不同的代价参数时，所得到的最优粒层不一定是相同的，即便是改变一个代价参数也可能引起整个序贯三支决策粒层结构的改变，进而得到代价最小的最优粒层可能也是不一样的。相比于第1组代价参数，第2组代价参数值更大，所得到的最优属性子集中属性个数更少，这种所得到的代价最小的最优粒层是较为符合人类认知的。同时，两组代价参数通过定理1可以得到αk+1＞αk,βk+1＜βk，随着粒度空间的细化，每一粒层上的决策标准更为严格，分类到接受域(或延迟域)中对象的准确率更高，这与现实生产中的实际情况也是相吻合的。

此外，为了说明惩罚规则的有效性，将所提模型(模型1)与不加惩罚规则的最优粒层选择模型(模型2)在第1组代价参数下进行对比，实验结果如表6所示。从表中可以发现，模型1和模型2均可以得到代价最小的粒层。相比于模型2，模型1所得到的粒层比模型2所得到的最优属性子集中属性个数更多，即当前模型1所得的粒层能够获取的信息更多。通过实验说明，利用惩罚函数对代价参数进行合理的修改，在选取最优粒层的时候逐步提高了阈值要求，能够有效地防止选择测试代价较小同时精度较差的粒层。因此，所提出的模型具有更好的实用性。

表6 最优粒层比较

在一定程度上，本文所提模型在实验过程中给定的代价参数需要在满足一定约束条件下进行随机选择，不同的代价参数组合得到的结果可能不一致。一般地，所给出的代价参数满足λPN-λBN＞λBP和λBN＜λNP-λBP等条件较为合理，在惩罚规则下，阈值α会逐渐增大，阈值β会逐渐减小，每一粒层上分类时的标准更为严格，接受域或拒绝域中的对象精度越大。

5 结论

序贯三支决策作为粒计算概念下的产物，其目标是提供一个灵活的机制和方法，使得用户在信息粒化过程中做出合适的决策，因此如何通过合理的粒度选择，来对复杂问题进行求解是值得研究的。本文介绍了一种新的序贯三支决策中最优粒度选择的方法，其思想是首先通过信息增益对属性的分类能力进行排序，再利用卡方检验进行属性之间的相似度检验，去除冗余属性。其次，设计惩罚函数对代价参数进行处理，使其能够随着粒度自适应变化。进一步地，通过测试代价和决策代价的变异系数建立了一种客观的综合度量代价的方法，消除两种代价量纲不一致带来的影响，实现同量纲下的评价。最后，通过UCI上的标准数据集对本文所提方法进行了验证，实验结果表明了所提方法选取的最优粒度空间具有一定的实用性。