论文报告厦门大学数据库实验室目录一种多类别条件下的代价敏感决策树
算法Cost-sensitive 分类算法——综述与实验一种基于 NNIA 多目标优化的代价敏感决策树构建方法论文摘要
代价敏感决策树是代价敏感分类算法中一种，它的目标是在分类过程中保证一定分类准确度条件下产生最少的分类总代价。典型的基于贪心方法
而建立的单一代价敏感决策树模型的算法有 PM、 MinCost 等，这类算法相比于其它代价敏感分类算法具有较好可理解性、需要较少时
间和空间复杂度的特点。 本文研究了 PM、MinCost 以及多类别条件下属性检测代价和误分类代价矩阵的特点，提出
了多类别问题下的一种基于评分策略的代价敏感决策树算法（简称 SECSDT_MC）。关键词：代价敏感；多类别；决策树误分类代价和属性
检测代价代价敏感决策树算法分类误分类代价指的是将真实类别为 A 的样例错误地分类为类别 B 时需要付出的代价； 属性检测指的是为获
得样例相关属性的属性值需要付出的代价。一类是基于贪心方法建立单一的分类模型的代价敏感决策树，例如 PM和 MinCost；另一类利
用集成学习的方法，通过 Boosting、 Bagging 等方式综合多个决策树模型构建出最终的代价敏感分类器模型，例如 Meta
Cost和 AdaBoost等。基础理论知识介绍相关工作MinCost 和 PM在选择分裂属性时采用的公式具体如下：其中， ICF
是 Information Cost Function 的简称； DMCA 表示在决策树模型内部节点上的样例依据属性 A 分拨到
各个子节点上后，当前节点上的期望误分类代价与各个子节点的期望误分类代价的和的 差 值 。 InfoGainA 表示属性 A 的信息
增益；CA 表示当前节点上的所有样例关于属性 A 的测试代价的和；w是依据专家经验给定的关于属性 A 的重要性度量值。（ 1）由于
代价因素与信息增益的不在同一个数值规模上，因此在公式(2)中容易造成 ICF 的计算结果主要取决于 DMCA 和(CA+1)的商；
（ 2）公式中关于分类准确度的计算采用了信息增益。由于增益越高分类准确度越好，为了获得更高的信息增益，算法倾向于选择属性值较少的属
性，但是，属性值越少的属性带来的误分类代价不一定更少。PM算法的缺点MinCost算法不足MinCost 在选择分类属性的启发式函
数中只对代价因素进行相关的计算，并未引入信息增益、基尼系数、模糊规则、隶属函数等信息论方法来计算分类的准确度。 然而，在满足一定分
类准确度条件下获得最少的分类总代价，需要综合考虑分类准确度因素和分类问题涉及到的各种代价因素。多类别条件下的 SECSDT_MC
算法问题描述假设数据集 S 中有 n 个样例；每个样例 m 个测试属性以及 1 个类别属性；类别属性共有 t 种属性值（即样例有
t 种类别）。其中，测试属性标记为A1、 A2、 ...、 Am；类别属性标记为 AC； t 种类别分别标记为 Class1、 C
lass2、…、 Classt。误分类代价矩阵的定义如下图 C(i, j) 表 示 样 例 的 真 实 类 别 为Classj ，
被分 类 Classi 时需 要付出 的误分类 代价。 C(i, i)为 0，即正确分类的情况下不产生误分类代价。代价敏感决策树的
代价函数可以用公式(3)表示：其中， F(x, i)表示利用代价敏感决策树模型将样例 x 分类 Classi 所产生的总代价（误分
类代价和属性检测代价的和）； p(j|x)表示样例 x 的真实类别为Classj 的概率；totalTestCost 表示为进行分
类而检测的相关属性所付出的检测代价的和。分裂属性的选择方法多类别条件下的基于评分策略的代价敏感决策树的总体思想是在模型的内部节点上
选择分裂属性时利用信息论方法（例如信息增益、基尼系数、隶属函数等）作为评估分类准确度因素的启发式函数，利用误分类代价与属性检测代价
作为评估代价因素的启发式函数，然后对这两项启发式函数的计算结果进行加权求和。各个候选属性中最终的计算结果最高的那个就作为该节点上的
分裂属性。其中， score(Ai)表示候选属性 Ai 的评分结果；AvgInfoGain(Ai)表示利用平均信息增益作为评估分类
准确度的指标，具体定义如公式(5)所示； CostRed(Ai)表示分类代价减少量，具体如公式(6)所示，这里用CostRed(A
i) 作 为 评 估 代 价 因 素 的 指 标 。 由 于AvgInfoGain(Ai)在数值规模上远小于 CostRed(Ai
)的数值规模，为了防止像 PM 算法那样，整个公式的计算 结 果 主 要 受 代 价 因 素 影 响 ， 这 里 要 对AvgIn
foGain(Ai)和 CostRed(Ai)进行归一化处理，具体的 方 法 如 公 式 (11)(12) 所 示 。 求 得 归
一 化 的AvgInfoGain(Ai)和 CostRed(Ai)后，再对这两项指标进行加权求和，最后得分最高的候选属性就作为代
价敏感决策树模型内部节点上的分裂属性。关于平均信息增益（即 AvgInfoGain(Ai)）的计算，首先要计算出当前节点上关于数据
集 S 的信息熵和子节点上的信息熵；然后计算出关于属性 Ai 的信息增益 Gain(Ai)；接着为了防止算法倾向于选择属性值较多的
候选属性作为分裂属性，这里用平均信息增益 AvgInfoGain(Ai)来代替 Gain(Ai)，具体公式如下所示：关于分类代价减
少量 CostRed(Ai)的计算，具体如公式(6)所示：其中， TestCost(S)表示当前节点上的测试集 S 中的所有样例为
获得属性 Ai 需要付出的属性检测代价的总和； ExpMisCostRed(Ai)表示当前节点上的期望误分类代价减少量，具体如公式
(7)所示。其中， ExpMisCost(S)表示当前节点上的所有样例的期望误分类代价。为计算 ExpMisCost(S)，首先需
要 计 算 出 当 前 节 点 上 将 样 例 判 为 某 个 类 别（ Classi ） 时 产 生 的 误 分 类 代 价
（ 即CostOfClass(Classi)），具体如公式(8)所示； 其次，还 需 要 计 算 将 当 前 节 点 上 的 样
例 判 为 某 个 类 别（ Classi）的概率（即 ProOfClass(Classi)），具体如公式(9)所示。其中，nj
表示当前节点上类别为 Classj 的样例个数。将节点上的所有样例标记为 Classi 时产生的误分类代价越大，则该节点上的样例判
定为 Classi 的概率就越小，因此将节点上的样例判定为类别 Classi的 概 率 （ ProOfClass(Classi)
） 的 计 算 如 公 式 (9) 所示：其 中 ， totalClassCost 为 各 个 类 别 的CostOfClass(
Classi)总和。计 算 出 属 性 Ai 关 于 各 个 类 别 的ProOfClass(Classi)和 CostOfCla
ss(Classi)后，就可以计算当前节点上的期望误分类代价 ExpMisCost(S)，具体如公式(10)所示:根 据 上 述
公 式 计 算 出 各 个 候 选 属 性 的AvgInfoGain(Ai)和 CostRed(Ai)后，就需要对其进行归一化处理
。具体的方法是分别求得每个属性关于AvgInfoGain(Ai) 和 CostRed(Ai) 的 最 大 值 ， 记 为MaxAv
gInfoGain 和 MaxCostRed，则归一化后的结果（记为 AvgInfoGain(Ai)normal 和 CostRe
d(Ai)normal）如公式(11)和(12)所示：我们尝试探讨a 的取值与误分类代价矩阵、当前节点上各个 样 例 的 个 数
之 间 的 关 系 。 令 maxMisCost 和minMisCost 当 前 节 点 上 各 个 类 别 的CostOfCla
ss(Classi)的最大值和最小值，并将a 设定为 minMisCost 和 maxMisCost 的商。 算法的收敛条件（ 1
）节点上的某个类别的样例个数占节点上样例总数的比例大于或等于某个阈值（例如 95%），并且样例总数也大于或等于给定的阈值。（ 2）
节点上的样例总数少于某个指定的阈值。（ 3）从根节点到该节点的父节点的路径上，已经用尽了所有的测试属性，此时，应该将该节点标记为叶
子节点。（ 4）如果选择出的分裂属性不能使得分类总代价有所减少，则将该节点标记为叶子节点未来展望在 未 来 的 研 究 工 作 中
， 我 们 将 尝 试SECSDT_MC 应用到通过 Boosting、 Bagging 多方法建 立 的 复 杂 的 代 价
敏 感 决 策 树 算 法 （ 例 如AdaBoost、 MetaCost），并分析这样的集成方式是否有利于进一步减少分类总代价或
者提高分类准确度。SECSDT_MC、 PM、 MinCost 在构建代价敏感决策树模型之前都已经获得了各个属性的检测代价和误分类
代价矩阵。而如果在模型构建之前或过程中，这些代价因素还处于未知状态，或者在构建过程中， 或者分类阶段才获得这些代价因素，很明显SE
CSDT_MC、 PM、 MinCost 都不适合用于解决这类问题。因此，在未来研究工作中，我们将尝试提出适合这类问题的代价敏感分
类算法。论文摘要 本文提出了一种基于非支配邻域免疫算法( NNIA, Nondominated Neighbor I
mmune Algorithm) 多目标优化的代价敏感决策树构建方法. 将平均误分类代价和平均测试代价作为两个优化目标, 然后利用
NNIA 对决策树进行优化, 最终获取了一组 Pareto 最优的决策树。关键词：代价敏感; 误分类代价; 测试代价; 多目标优
化; 决策树前言介绍在分类过程中同时考虑多种代价的问题通常称为多代价敏感分类, 解决这种问题主要有两种策略: 一种是将多种代价转换
为一种综合代价,另外一种是将每种代价视作一个目标并利用多目标优化技术寻优. 目前多代价敏感决策树构建方法主要采用第一种方式, 即在
构建代价敏感的决策树过程中, 将不同代价在同一尺度下进行衡量 , 或者将不同代价通过加权的方式合并为一种新的代价.本文提出了一种基
于 NNIA 的代价敏感决策树构建方法, 将平均误分类代价和平均测试代价作为两个优化目标, 利用 NNIA 对决策树进行优化.NN
IA 算法的基本步骤包括: 初始抗体群的建立、优势抗体群更新、终止条件判断、活性抗体群的选择、比例克隆, 以及重组和超变异操作.
为了使 NNIA 更适应决策树抗体并且进一步降低复杂度, 本文在构建代价敏感决策树过程中对NNIA 算法进行了改进, 这种基于 N
NIA 算法的代价敏感决策树的构建框图 如图 1所示.基于 NNIA 算法的代价敏感决策树构建优化目标的确定给定决策树 t 和训练
样本集 D, 则平均误分类代价 f 1( t) 可以用式(1) 定义:其中, | D| 为训练样本集 D 中所包含的样本数目, d
为训练样本集 D 中的样本, Id 为样本 d 的实际类别, h( t,d) 为决策树 t 对样本d 的预测类别.给定属性集合
A 和公有操作集合 P, 假设集合 A中的每个属性 a的获取需要先进行集合 Pa中的所有操作, 其中 Pa 是集合 P 的子集,
则获取属性 a所需代价TA ( a) 的定义如式( 2) 所示:其中 Ta是在所需预操作已完成的情况下获取属性 a所需代价, Tp
是完成公有操作p 所需代价,U( a) 和 U( p ) 是指示函数.从决策树的根节点到每一个叶节点的路径组成一条判决规则, 即
决策树中的每一个叶节点对应一条判决规则. 由根节点至叶节点顺序累加获取属性 a i 所需代价即为规则r 的测试代价TR( r) ,
定义如式(3) 所示:决策树 t 的平均测试代价 f 2( t) 的定义如式(4) 所示:其中 Dl 是训练数据集 D 中满足规
则rl 的决策属性条件的样本子集, | Dl | 是集合 Dl 的数据样本数目, rl 是叶节点 l 对应的判决 规则.确定了平均
误分类代价f 1( t) 和平均测试代价f 2( t)后,本文提出的方法归结为利用 NNIA 算法解决式( 5)中的两个目标的优化
问题:决策树抗体的随机生成本文随机建立的二叉决策树为满二叉树, 并且建立过程与传统的采用启发式策略自顶向下建立决策树的方法不同,
其内部节点决策属性和分裂点都是随机选择的, 这有利于在整个决策空间搜索.如果内部节点选择的决策属性为离散型, 设该属性的取值集合为
Vd, 分裂集合则为在集合 Vd中随机选择的不为空的子集 V d, 且 V d 与 Vd不相等. 若测试样本的该属性取值属于
集合 V d , 则转向决策树左分支, 否则转向右分支.对于连续属性, 需要预先根据训练样本集 D 来设置候选分裂值集合 Vc,
分裂值为在集合 Vc 中随机选取的元素v. 若测试样本的该属性值不大于 v, 则转向左分支, 否则转向右分支.叶节点类别的指派方
法为: 对于叶节点 l, 训练样本集 D 经决策树t 测试后, 得到符合叶节点 l 对应规则的数据样本子集 Dl, 将使 Dl 误
分类代价最小的类别指定为叶节点 l 的类别, 如式(6) 所示.其中 x 为叶节点 l 应指派的类别, CId, x含义与式( 1
) 相同.决策树剪枝策略本文采用了两个剪枝策略: ( 1) 最小支持项数目; ( 2) 基于分类错误代价的剪枝方法.具体剪枝方式为
: (1) 若子树 tb 的左右子树支持项的数目都小于 m, 则剪除子树 tb, 并在 t b 的位置用叶节点代替, ( 2)
若子树 tb 的左( 右) 子树支持项数目小于 m, 而右( 左) 子树的支持项数目不小于m , 则将子树 t b 的树根及左(
右) 子树剪除, 将右( 左) 子树替代原子树 tb 的位置, 如图 所示基于分类错误代价的剪枝策略则是利用训练样本集 D 评估决
策树的误分类代价, 并自顶向下对子树是否被剪枝作出决定.对于内部节点 N, 假设以该节点作为根节点的子树为 tn, 若剪除 tn
后的决策树的平均误分类代价不大于剪枝前的平均误分类代价, 则对子树tn 进行剪枝; 否则保留该子树.决策树抗体的变异操作本文采用了
5 种决策树变异操作 , 分别是: ( 1) 利用随机创建的子树替代原决策树中随机选取的子树; ( 2) 对决策树进行随机剪枝;
( 3)随机改变内部节点决策属性的分裂点; ( 4) 随机改变内部节点的决策属性和分裂点; ( 5) 随机分裂叶节点.本文将每个
叶节点对应的决策规则视为决策树抗体的基因, 并根据决策规则的分类性能设置该基因被选择为变异点的概率. 在选定变异基因后, 进一步随
机选择变异操作, 并根据选定的变异操作选择需要变异的节点. 这种选择策略会以较高的概率选择决策树中分类性能较差的分支进行变异, 有
利于决策树变异后性能的提高.Cost-sensitive 分类算法的研究现状 Cost-sensitive 分类面
向的是类型比例不平衡的数据集上的分类问题，其主要目的是使分类器的分类结果对应的 cost 值最低在如何获得有倾向性的分类算法这一问
题上，目前有两种主要的方法。一种方法希望通过对训练数据集的预处理以提高分类算法对于某些分类结果的敏感性，这种方法被称作 resca
ling。另外一系列方法则希望通过以 cost 为基准修改不同分类在算法中的 class membership probabili
ty，以获得具有一定数据倾向性的分类算法。这种算法被称为 reweighted。 总体上来说，这两种分类涵盖了目前基本上所有的 c
ost-sensitive 分类算法。主要算法介绍Cost-based Sampling对于 2-class 的 cost-sen
sitive 分类问题，我们实际上是要使得分类算法对于 cost 较高的那一类数据的敏感性高于另一类。 提出可以通过下面的等式来确
定 positive 实例的比例：在如何对数据集进行采样以获得所需实例的比例的问题上， 提出了一种多类别的数据集重采样方法。具体来
说对于 n 大小的 x:y 的数据集 S，如果要获得 u:v 的目标数据集 S’，我们将数据集重采样为y/x×u /v个数据子集，
同时为每个子集采样 nx 个 X 实例， nxv/u个 Y 实例。这样就能够获得 u:v 比例的目标数据集。REBALANCE对于
训练数据集进行预调整的目标是获得 negative 实例比例为 p的数据集，其中 p由下式给出：定理 1 说明了为了从比例为
p0 的训练数据集出发获得比例为 p的数据集，预处理应该采取的操作。定理 1:为了从比例为 p0 的训练数据集出发获得比例为 p
的数据集，训练集中的 negative 实例数目乘以(p?/1?p?)(1?p0/p0) MetaCost 是一种
reweighted 算法，MetaCost 的基本思想是利用 Bayes 风险理论，根据 cost 最优分类为训练数据集上的实
例进行重标记，从而获得目标非 cost-sensitive 分类算法的对应的cost-sensitive 分类算法。MetaCost AdaCost 算法由 AdaBoost 分类算法改进而来，也是一种通过 reweighted 方式获取 cost-sensitive 分类算法的方法。 AdaCost 的基本思想是使用若干个较弱的分类器以投票方式集成出一个分类器，各个分类器的权值由评价函数调整确定。AdaCost研究总结 Multi-class 的 cost-sensitive 分类将会是未来本领域的研究热点之一。 如前文所述， 在 multi-class 分类中， rescaling 方法不再能够被简单地运用到其中。机器学习研究者们需要研究除了数据集类型比例之外，其他对于 cost-sensitive 分类问题结果有显著影响的因素，从而提高分类算法的 cost-sensitive 分类性能。 寻找 cost 的实际意义也有一定的研究价值。除此之外可能的研究点还包括 cost-sensitive 分类的效率问题， cost-sensitive 分类的 benchmark 以及通用性的 cost-sensitive 分类算法等Thanks |
|
