报告人邓少军指导老师林子雨2015

《报告人邓少军指导老师林子雨2015》由会员分享，可在线阅读，更多相关《报告人邓少军指导老师林子雨2015（34页珍藏版）》请在金锄头文库上搜索。

1、 报告人：邓少军 指导老师：林子雨 2015年7月17日 论论文文报报告告厦厦门门大大学学数数据据库库实实验验室室目录一种多类别条件下的代价敏感决策树算法一种多类别条件下的代价敏感决策树算法Cost-sensitive 分类算法分类算法综述与实验综述与实验一种基于一种基于 NNIA 多目标优化的代价多目标优化的代价敏感决策树构建方法敏感决策树构建方法Part 1 一种多类别条件下的代价敏感一种多类别条件下的代价敏感决策树算法决策树算法u论文摘要 代价敏感决策树是代价敏感分类算法中一种，它的目标是在分类代价敏感决策树是代价敏感分类算法中一种，它的目标是在分类过程中保证一定分类准确度条件下产生最少

2、的分类总代价。典型的基过程中保证一定分类准确度条件下产生最少的分类总代价。典型的基于贪心方法而建立的单一代价敏感决策树模型的算法有于贪心方法而建立的单一代价敏感决策树模型的算法有 PM、 MinCost 等，这类算法相比于其它代价敏感分类算法具有较好可理解性、需要等，这类算法相比于其它代价敏感分类算法具有较好可理解性、需要较少时间和空间复杂度的特点。较少时间和空间复杂度的特点。 本文研究了本文研究了 PM、MinCost 以及多类别条件下属性检测代价和误分以及多类别条件下属性检测代价和误分类代价矩阵的特点，提出了多类别问题下的一种基于评分策略的代价类代价矩阵的特点，提出了多类别问题下的一种基于

3、评分策略的代价敏感决策树算法（简称敏感决策树算法（简称 SECSDT_MC）。）。关键词：代价敏感；多类别；决策树关键词：代价敏感；多类别；决策树误分类代价和属性检测代价代价敏感决策树算法分类误分类代价指的是将真实类别为误分类代价指的是将真实类别为 A 的样例错误地分类为类别的样例错误地分类为类别 B 时需要付出的代价；时需要付出的代价； 属性检测指的是为获得样例相关属性的属属性检测指的是为获得样例相关属性的属性值需要付出的代价。性值需要付出的代价。一类是基于贪心方法建立单一的分类模型的代价敏感决策树，一类是基于贪心方法建立单一的分类模型的代价敏感决策树，例如例如 PM和和 MinCost；另

4、一类利用集成学习的方法，通过；另一类利用集成学习的方法，通过 Boosting、 Bagging 等方式综合多个决策树模型构建出最终的代等方式综合多个决策树模型构建出最终的代价敏感分类器模型，例如价敏感分类器模型，例如 MetaCost和和 AdaBoost等。等。u基础理论知识介绍基础理论知识介绍u相关工作MinCost 和和 PM在选择分裂属性时采用的公式具体如下：在选择分裂属性时采用的公式具体如下：其中，其中， ICF 是是 Information Cost Function 的简称；的简称； DMCA 表示在决策树模型表示在决策树模型内部节点上的样例依据属性内部节点上的样例依据属性 A

5、 分拨到各个子节点上后，当前节点上的期望分拨到各个子节点上后，当前节点上的期望误分类代价与各个子节点的期望误分类代价的和的误分类代价与各个子节点的期望误分类代价的和的 差差 值值 。 InfoGainA 表表示属性示属性 A 的信息增益；的信息增益；CA 表示当前节点上的所有样例关于属性表示当前节点上的所有样例关于属性 A 的测试的测试代价的和；代价的和；w是依据专家经验给定的关于属性是依据专家经验给定的关于属性 A 的重要性度量值。的重要性度量值。（ 1）由于代价因素与信息增益的不在同一个数值规模上，因此在公式(2)中容易造成 ICF 的计算结果主要取决于 DMCA 和(CA+1)的商；（

6、2）公式中关于分类准确度的计算采用了信息增益。由于增益越高分类准确度越好，为了获得更高的信息增益，算法倾向于选择属性值较少的属性，但是，属性值越少的属性带来的误分类代价不一定更少。PM算法的缺点算法的缺点MinCost算法不足MinCost 在选择分类属性的启发式函数中只对代价因素进行相关的计算，并未引入信息增益、在选择分类属性的启发式函数中只对代价因素进行相关的计算，并未引入信息增益、基尼系数、模糊规则、隶属函数等信息论方法来计算分类的准确度。基尼系数、模糊规则、隶属函数等信息论方法来计算分类的准确度。 然而，然而，在满足一定分类在满足一定分类准确度条件下获得最少的分类总代价，需要综合考虑分

7、类准确度因素和分类问题涉及到的各种准确度条件下获得最少的分类总代价，需要综合考虑分类准确度因素和分类问题涉及到的各种代价因素。代价因素。u多类别条件下的多类别条件下的 SECSDT_MC 算法算法问题描述问题描述假设数据集假设数据集 S 中有中有 n 个样例；每个样例个样例；每个样例 m 个测试属性以及个测试属性以及 1 个类别属性；类别属性共有个类别属性；类别属性共有 t 种属性值（即种属性值（即样例有样例有 t 种类别）。其中，测试属性标记为种类别）。其中，测试属性标记为A1、 A2、 .、 Am；类别属性标记为；类别属性标记为 AC； t 种类别分别标记种类别分别标记为为 Class1、

8、 Class2、 Classt。误分类代价矩阵的定义如误分类代价矩阵的定义如下下图图 C(i, j) 表表 示示 样样 例例 的的 真真 实实 类类 别别 为为Classj ，被分，被分 类类 Classi 时需时需 要付出要付出 的误的误分类分类 代价。代价。 C(i, i)为为 0，即正确分类的情况下不产生误分类代价。，即正确分类的情况下不产生误分类代价。代价敏感决策树的代价函数可以用公式代价敏感决策树的代价函数可以用公式(3)表示：表示：其中，其中， F(x, i)表示利用代价敏感决策树模型将样例表示利用代价敏感决策树模型将样例 x 分类分类 Classi 所产生的总代价（误分类代所产生

9、的总代价（误分类代价和属性检测代价的和）；价和属性检测代价的和）； p(j|x)表示样例表示样例 x 的真实类别为的真实类别为Classj 的概率的概率；totalTestCost 表示表示为进行分类而检测的相关属性所付出的检测代价的和。为进行分类而检测的相关属性所付出的检测代价的和。分裂属性的选择方法分裂属性的选择方法多类别条件下的基于评分策略的代价敏感决策树的多类别条件下的基于评分策略的代价敏感决策树的总体思想总体思想是在模型的内部节点上选择是在模型的内部节点上选择分裂属性时利用信息论方法（例如信息增益、基尼系数、隶属函数等）作为评估分类准分裂属性时利用信息论方法（例如信息增益、基尼系数、

10、隶属函数等）作为评估分类准确度因素的启发式函数，利用误分类代价与属性检测代价作为评估代价因素的启发式函确度因素的启发式函数，利用误分类代价与属性检测代价作为评估代价因素的启发式函数，然后对这两项启发式函数的计算结果进行加权求和。各个候选属性中最终的计算结数，然后对这两项启发式函数的计算结果进行加权求和。各个候选属性中最终的计算结果最高的那个就作为该节点上的分裂属性果最高的那个就作为该节点上的分裂属性。其中，其中， score(Ai)表示候选属性表示候选属性 Ai 的评分结果；的评分结果；AvgInfoGain(Ai)表示利用平均信息增表示利用平均信息增益作为评估分类准确度的指标，具体定义如公式

11、益作为评估分类准确度的指标，具体定义如公式(5)所示；所示； CostRed(Ai)表示分类代表示分类代价减少量，具体如公式价减少量，具体如公式(6)所示，这里用所示，这里用CostRed(Ai) 作作 为为 评评 估估 代代 价价 因因 素素 的的 指指 标标 。 由由 于于AvgInfoGain(Ai)在数值规模上远小于在数值规模上远小于 CostRed(Ai)的数值规模，为了防止像的数值规模，为了防止像 PM 算法那样，整个公式的计算算法那样，整个公式的计算 结结 果果 主主 要要 受受 代代 价价 因因 素素 影影 响响 ， 这这 里里 要要 对对AvgInfoGain(Ai)和和 C

12、ostRed(Ai)进行归一化处理进行归一化处理，具体的，具体的 方方 法法 如如 公公 式式 (11)(12) 所所 示示 。 求求 得得 归归 一一 化化 的的AvgInfoGain(Ai)和和 CostRed(Ai)后，再对这两项指标进行加权后，再对这两项指标进行加权求和，最后得分最高的候选属性就作为代价敏感决策树模型内部节点上的分裂属性。求和，最后得分最高的候选属性就作为代价敏感决策树模型内部节点上的分裂属性。关于平均信息增益（即关于平均信息增益（即 AvgInfoGain(Ai)）的计算，首先要计算出当前节点上关于数据集）的计算，首先要计算出当前节点上关于数据集 S 的信息的信息熵和

13、子节点上的信息熵；然后计算出关于属性熵和子节点上的信息熵；然后计算出关于属性 Ai 的信息增益的信息增益 Gain(Ai)；接着为了防止算法倾向于接着为了防止算法倾向于选择属性值较多的候选属性作为分裂属性，这里用平均信息增益选择属性值较多的候选属性作为分裂属性，这里用平均信息增益 AvgInfoGain(Ai)来代替来代替 Gain(Ai)，具体公式如下所示：具体公式如下所示：关于分类代价减少量关于分类代价减少量 CostRed(Ai)的计算，具体如公式的计算，具体如公式(6)所所示：示：其中，其中， TestCost(S)表示当前节点上的测试集表示当前节点上的测试集 S 中的所有样例为获得属

14、性中的所有样例为获得属性 Ai 需需要付出的属性检测代价的总和；要付出的属性检测代价的总和； ExpMisCostRed(Ai)表示当前节点上的期望误表示当前节点上的期望误分类代价减少量，具体如公式分类代价减少量，具体如公式(7)所示。所示。其中，其中， ExpMisCost(S)表示当前节点上的所有样例的期望误分类代价。为计算表示当前节点上的所有样例的期望误分类代价。为计算 ExpMisCost(S)，首先，首先需需 要要 计计 算算 出出 当当 前前 节节 点点 上上 将将 样样 例例 判判 为为 某某 个个 类类 别（别（ Classi ） 时时 产产 生生 的的 误误 分分 类类 代代

15、 价价 （ 即即CostOfClass(Classi)），具体如公式），具体如公式(8)所示；所示； 其次，还其次，还 需需 要要 计计 算算 将将 当当 前前 节节 点点 上上 的的 样样 例例 判判 为为 某某 个个 类类 别（别（ Classi）的概率（即）的概率（即 ProOfClass(Classi)），具体如公式），具体如公式(9)所示。所示。其中，其中，nj 表示当前节点上类别为表示当前节点上类别为 Classj 的样例个数。的样例个数。将节点上的所有样例标记为将节点上的所有样例标记为 Classi 时产生的误分类代价越大，则该节点上的样例判定为时产生的误分类代价越大，则该节点上

16、的样例判定为 Classi 的概率就越小的概率就越小，因此将节点上的样例判定为类别，因此将节点上的样例判定为类别 Classi的的 概概 率率 （ ProOfClass(Classi) ） 的的 计计 算算 如如 公公 式式 (9) 所示：所示：其其 中中 ， totalClassCost 为为 各各 个个 类类 别别 的的CostOfClass(Classi)总和。总和。计计 算算 出出 属属 性性 Ai 关关 于于 各各 个个 类类 别别 的的ProOfClass(Classi)和和 CostOfClass(Classi)后，就可以计算当前节后，就可以计算当前节点上的期望误分类代价点上的期

17、望误分类代价 ExpMisCost(S)，具体如公式，具体如公式(10)所示所示:根根 据据 上上 述述 公公 式式 计计 算算 出出 各各 个个 候候 选选 属属 性性 的的AvgInfoGain(Ai)和和 CostRed(Ai)后，就需要对其进后，就需要对其进行行归一化处理归一化处理。具体的方法是分别求得每个属性关于。具体的方法是分别求得每个属性关于AvgInfoGain(Ai) 和和 CostRed(Ai) 的的 最最 大大 值值 ， 记记 为为MaxAvgInfoGain 和和 MaxCostRed，则归一化后的结果（记为，则归一化后的结果（记为 AvgInfoGain(Ai)nor

18、mal 和和 CostRed(Ai)normal）如公式）如公式(11)和和(12)所示：所示：我们尝试探讨我们尝试探讨a 的取值与误分类代价矩阵、当前节点上各个的取值与误分类代价矩阵、当前节点上各个 样样 例例 的的 个个 数数 之之 间间 的的 关关 系系 。 令令 maxMisCost 和和minMisCost 当当 前前 节节 点点 上上 各各 个个 类类 别别 的的CostOfClass(Classi)的最大值和最小值，并将的最大值和最小值，并将a 设定为设定为 minMisCost 和和 maxMisCost 的商。的商。 算法的收敛条件算法的收敛条件（ 1）节点上的某个类别的样例

19、个数占节点上样例总数的比例大于或等于某个阈值）节点上的某个类别的样例个数占节点上样例总数的比例大于或等于某个阈值（例如（例如 95%），并且样例总数也大于或等于给定的阈值。），并且样例总数也大于或等于给定的阈值。（ 2）节点上的样例总数少于某个指定的阈值。）节点上的样例总数少于某个指定的阈值。（ 3）从根节点到该节点的父节点的路径上，已经用尽了所有的测试属性，此时，）从根节点到该节点的父节点的路径上，已经用尽了所有的测试属性，此时，应该将该节点标记为叶子节点应该将该节点标记为叶子节点。（ 4）如果选择出的分裂属性不能使得分类总代价有所减少，则将该节点标记为叶）如果选择出的分裂属性不能使得分类总

20、代价有所减少，则将该节点标记为叶子节点子节点u未来展望在在 未未 来来 的的 研研 究究 工工 作作 中中 ， 我我 们们 将将 尝尝 试试SECSDT_MC 应用到通过应用到通过 Boosting、 Bagging 多方法建多方法建 立立 的的 复复 杂杂 的的 代代 价价 敏敏 感感 决决 策策 树树 算算 法法 （ 例例 如如AdaBoost、 MetaCost），并分析这样的集成方式是否有利于进一步减少分类总代价或者提），并分析这样的集成方式是否有利于进一步减少分类总代价或者提高分类准确度。高分类准确度。SECSDT_MC、 PM、 MinCost 在构建代价敏感决策树模型之前都已经获

21、得在构建代价敏感决策树模型之前都已经获得了各个属性的检测代价和误分类代价矩阵。而如果在模型构建之前或过了各个属性的检测代价和误分类代价矩阵。而如果在模型构建之前或过程中，这些代价因素还处于未知状态，或者在构建过程中，程中，这些代价因素还处于未知状态，或者在构建过程中， 或者分类阶或者分类阶段才获得这些代价因素，很明显段才获得这些代价因素，很明显SECSDT_MC、 PM、 MinCost 都不适合用都不适合用于解决这类问题。因此，在未来研究工作中，我们将尝试提出适合这类于解决这类问题。因此，在未来研究工作中，我们将尝试提出适合这类问题的代价敏感分类算法。问题的代价敏感分类算法。Part 2 一

22、种基于一种基于 NNIA 多目标优化的代价多目标优化的代价敏感决策树构建方法敏感决策树构建方法 u论文摘要 本文提出了一种基于非支配邻域免疫算法本文提出了一种基于非支配邻域免疫算法( NNIA, Nondominated Neighbor Immune Algorithm) 多目标优化的代价敏感决策树构建方法多目标优化的代价敏感决策树构建方法. 将平均误分类代价和平均测试代价作为两个优化目标将平均误分类代价和平均测试代价作为两个优化目标, 然后利用然后利用 NNIA 对决策树进行优化对决策树进行优化, 最终获取了一组最终获取了一组 Pareto 最优的决策树。最优的决策树。关键词：代价敏感关键

23、词：代价敏感; 误分类代价误分类代价; 测试代价测试代价; 多目标优化多目标优化; 决决策树策树u前言介绍在分类过程中同时考虑多种代价的问题通常称为在分类过程中同时考虑多种代价的问题通常称为多代价敏感分类多代价敏感分类, 解决解决这种问题主要有两种策略这种问题主要有两种策略: 一种是将多种代价转换为一种综合代价一种是将多种代价转换为一种综合代价,另外另外一种是将每种代价视作一个目标并利用多目标优化技术寻优一种是将每种代价视作一个目标并利用多目标优化技术寻优. 目前多代价敏感决策树构建方法主要采用第一种方式目前多代价敏感决策树构建方法主要采用第一种方式, 即在构建代价敏即在构建代价敏感的决策树过

24、程中感的决策树过程中, 将不同代价在同一尺度下进行衡量将不同代价在同一尺度下进行衡量 , 或者将不同代或者将不同代价通过加权的方式合并为一种新的代价价通过加权的方式合并为一种新的代价.本文提出了一种基于本文提出了一种基于 NNIA 的代价敏感决策树构建方法的代价敏感决策树构建方法, 将平均误分类代价和平均测试将平均误分类代价和平均测试代价作为两个优化目标代价作为两个优化目标, 利用利用 NNIA 对决策树进行优化对决策树进行优化.NNIA 算法的算法的基本步骤基本步骤包括包括: 初始抗体群的建立、优势抗体群更新、终止条件判断、初始抗体群的建立、优势抗体群更新、终止条件判断、活性抗体群的选择、比

25、例克隆活性抗体群的选择、比例克隆, 以及重组和超变异操作以及重组和超变异操作. 为了使为了使 NNIA 更适应决策树更适应决策树抗体并且进一步降低复杂度抗体并且进一步降低复杂度, 本文在构建代价敏感决策树过程中对本文在构建代价敏感决策树过程中对NNIA 算法进行了算法进行了改进改进, 这种基于这种基于 NNIA 算法的代价敏感决策树的构建框图算法的代价敏感决策树的构建框图 如图如图 1所示所示.u基于NNIA算法的代价敏感决策树构建优化目标的确定优化目标的确定给定决策树给定决策树 t 和训练样本集和训练样本集 D, 则平均误分类代价则平均误分类代价 f 1( t) 可以用式可以用式(1) 定义

26、定义:其中其中, | D| 为训练样本集为训练样本集 D 中所包含的样本数目中所包含的样本数目, d 为训练样本集为训练样本集 D 中的样本中的样本, Id 为样本为样本 d 的实际类别的实际类别, h( t,d) 为决策树为决策树 t 对样本对样本d 的预测类别的预测类别.给定属性集合给定属性集合 A 和公有操作集合和公有操作集合 P, 假设集合假设集合 A中的每个属性中的每个属性 a的获取需要先进的获取需要先进行集合行集合 Pa中的所有操作中的所有操作, 其中其中 Pa 是集合是集合 P 的子集的子集, 则获取属性则获取属性 a所需代价所需代价TA ( a) 的定义如式的定义如式( 2)

27、所示所示:其中其中 Ta是在所需预操作已完成的情况下获取属性是在所需预操作已完成的情况下获取属性 a所需代价所需代价, Tp 是完成是完成公有操作公有操作p 所需代价所需代价,U( a) 和和 U( p ) 是指示函数是指示函数.从决策树的根节点到每一个叶节点的路径组成一条判决规则从决策树的根节点到每一个叶节点的路径组成一条判决规则, 即决策树中的每一个叶节点对应即决策树中的每一个叶节点对应一条判决规则一条判决规则. 由根节点至叶节点顺序累加获取属性由根节点至叶节点顺序累加获取属性 a i 所需代价即为规则所需代价即为规则r 的测试代价的测试代价TR( r) , 定义如式定义如式(3) 所示所

28、示:决策树 t 的平均测试代价 f 2( t) 的定义如式(4) 所示:其中其中 Dl 是训练数据集是训练数据集 D 中满足规则中满足规则rl 的决策属性条件的样本子集的决策属性条件的样本子集, | Dl | 是集合是集合 Dl 的的数据样本数目数据样本数目, rl 是叶节点是叶节点 l 对应的判决对应的判决 规则规则.确定了平均误分类代价确定了平均误分类代价f 1( t) 和平均测试代价和平均测试代价f 2( t)后后,本文提出的方法归结为利用本文提出的方法归结为利用 NNIA 算法解算法解决式决式( 5)中的两个目标的优化问题中的两个目标的优化问题:决策树抗体的随机生成决策树抗体的随机生成

29、本文随机建立的二叉决策树为满二叉树本文随机建立的二叉决策树为满二叉树, 并且建立过程与传统的采用启发式策略自顶向下并且建立过程与传统的采用启发式策略自顶向下建立决策树的方法不同建立决策树的方法不同, 其内部节点决策属性和分裂点都是随机选择的其内部节点决策属性和分裂点都是随机选择的, 这有利于在整个这有利于在整个决策空间搜索决策空间搜索.如果内部节点选择的决策属性为离散型如果内部节点选择的决策属性为离散型, 设该属性的取值集合为设该属性的取值集合为 Vd, 分裂集合则为在集合分裂集合则为在集合 Vd中随机选择的不为空的子集中随机选择的不为空的子集 V* d, 且且 V* d 与与 Vd不相等不相

30、等. 若测试样本的该属性取值属于集若测试样本的该属性取值属于集合合 V* d , 则转向决策树左分支则转向决策树左分支, 否则转向右分支否则转向右分支.对于连续属性对于连续属性, 需要预先根据训练样本集需要预先根据训练样本集 D 来设置候选分裂值集合来设置候选分裂值集合 Vc, 分裂值为在集合分裂值为在集合 Vc 中随机选取的元素中随机选取的元素v. 若测试样本的该属性值不大于若测试样本的该属性值不大于 v, 则转向左分支则转向左分支, 否则转向右分支否则转向右分支.叶节点类别的指派方法为叶节点类别的指派方法为: 对于叶节点对于叶节点 l, 训练样本集训练样本集 D 经决策树经决策树t 测试后

31、测试后, 得到符合叶节点得到符合叶节点 l 对应规则的数据样本子集对应规则的数据样本子集 Dl, 将使将使 Dl 误分类代价最小的类别指定为叶节点误分类代价最小的类别指定为叶节点 l 的类别的类别, 如式如式(6) 所示所示.其中其中 x 为叶节点为叶节点 l 应指派的类别应指派的类别, CId, x含义与式含义与式( 1) 相同相同.决策树剪枝策略决策树剪枝策略本文采用了两个剪枝策略本文采用了两个剪枝策略: ( 1) 最小支持项数目最小支持项数目; ( 2) 基于分类错误代价的剪枝方基于分类错误代价的剪枝方法法.具体剪枝方式为具体剪枝方式为: (1) 若子树若子树 tb 的左右子树支持项的数

32、目都小于的左右子树支持项的数目都小于 m, 则剪除子树则剪除子树 tb, 并并在在 t b 的位置用叶节点代替的位置用叶节点代替, ( 2) 若子树若子树 tb 的左的左( 右右) 子树支持项数目小于子树支持项数目小于 m, 而右而右( 左左) 子树的支持项数目不小于子树的支持项数目不小于m , 则将子树则将子树 t b 的树根及左的树根及左( 右右) 子树剪除子树剪除, 将右将右( 左左) 子树替子树替代原子树代原子树 tb 的位置的位置, 如图如图 所示所示基于分类错误代价的剪枝策略则是利用训练样本集基于分类错误代价的剪枝策略则是利用训练样本集 D 评估决策树的误分类代价评估决策树的误分类

33、代价, 并自顶向下并自顶向下对子树是否被剪枝作出决定对子树是否被剪枝作出决定.对于内部节点对于内部节点 N, 假设以该节点作为根节点的子树为假设以该节点作为根节点的子树为 tn, 若剪除若剪除 tn 后的决策树的平均误分类代价不大于剪枝前的平均误分类代价后的决策树的平均误分类代价不大于剪枝前的平均误分类代价, 则对子树则对子树tn 进行剪枝进行剪枝; 否否则保留该子树则保留该子树.决策树抗体的变异操作决策树抗体的变异操作本文采用了本文采用了 5 种决策树变异操作种决策树变异操作 , 分别是分别是: ( 1) 利用随机创建的子树替代原决策树中随机选利用随机创建的子树替代原决策树中随机选取的子树取

34、的子树; ( 2) 对决策树进行随机剪枝对决策树进行随机剪枝; ( 3)随机改变内部节点决策属性的分裂点随机改变内部节点决策属性的分裂点; ( 4) 随机随机改变内部节点的决策属性和分裂点改变内部节点的决策属性和分裂点; ( 5) 随机分裂叶节点随机分裂叶节点.本文将每个叶节点对应的决策规则视为决策树抗体的基因本文将每个叶节点对应的决策规则视为决策树抗体的基因, 并根据决策规则的分类性能设并根据决策规则的分类性能设置该基因被选择为变异点的概率置该基因被选择为变异点的概率. 在选定变异基因后在选定变异基因后, 进一步随机选择变异操作进一步随机选择变异操作, 并根据选并根据选定的变异操作选择需要变

35、异的节点定的变异操作选择需要变异的节点. 这种选择策略会以较高的概率选择决策树中分类性能这种选择策略会以较高的概率选择决策树中分类性能较差的分支进行变异较差的分支进行变异, 有利于决策树变异后性能的提高有利于决策树变异后性能的提高.Part 3 Cost-sensitive 分类算法分类算法综述与实验综述与实验uCost-sensitive分类算法的研究现状 Cost-sensitive 分类面向的是类型比例不平衡分类面向的是类型比例不平衡的数据集上的分类问题，其主要的数据集上的分类问题，其主要目的是使分类器的分类结果对应的目的是使分类器的分类结果对应的 cost 值最低值最低在如何获得有倾向

36、性的分类算法这一问题上，目前有两种主要的方法。一种方法在如何获得有倾向性的分类算法这一问题上，目前有两种主要的方法。一种方法希望通过对训练数据集的预处理以提高分类算法对于某些分类结果的敏感性，这希望通过对训练数据集的预处理以提高分类算法对于某些分类结果的敏感性，这种方法被称作种方法被称作 rescaling。另外一系列方法则希望通过以。另外一系列方法则希望通过以 cost 为基准修改不同分类为基准修改不同分类在算法中的在算法中的 class membership probability，以获得具有一定数据倾向性的分类算，以获得具有一定数据倾向性的分类算法。这种算法被称为法。这种算法被称为 re

37、weighted。 总体上来说，这两种分类涵盖了目前基本上总体上来说，这两种分类涵盖了目前基本上所有的所有的 cost-sensitive 分类算法。分类算法。u主要算法介绍主要算法介绍Cost-based Sampling对于对于 2-class 的的 cost-sensitive 分类问题，我们实际上是要使得分类算法对于分类问题，我们实际上是要使得分类算法对于 cost 较高的那一类较高的那一类数据的敏感性高于另一类。数据的敏感性高于另一类。 提出可以通过下面的等式来确定提出可以通过下面的等式来确定 positive 实例的比例：实例的比例：在如何对数据集进行采样以获得所需实例的比例的问题

38、上，在如何对数据集进行采样以获得所需实例的比例的问题上， 提出了一种多类别的数据集重提出了一种多类别的数据集重采样方法。具体来说对于采样方法。具体来说对于 n 大小的大小的 x:y 的数据集的数据集 S，如果要获得，如果要获得 u:v 的目标数据集的目标数据集 S，我们，我们将数据集重采样为将数据集重采样为y/xu /v个数据子集，同时为每个子集采样个数据子集，同时为每个子集采样 nx 个个 X 实例，实例， nxv/u个个 Y 实实例。这样就能够获得例。这样就能够获得 u:v 比例的目标数据集。比例的目标数据集。REBALANCE对于训练数据集进行预调整的目标是获得对于训练数据集进行预调整的

39、目标是获得 negative 实例比例为实例比例为 p*的数据集，其中的数据集，其中 p*由由下式给出：下式给出：定理定理 1 说明了为了从比例为说明了为了从比例为 p0 的训练数据集出发获得比例为的训练数据集出发获得比例为 p*的数据集，预处理应该的数据集，预处理应该采取的操作。采取的操作。定理定理 1:为了从比例为为了从比例为 p0 的训练数据集出发获得比例为的训练数据集出发获得比例为 p*的数据集，训练集中的的数据集，训练集中的 negative 实例数目乘以实例数目乘以(p /1p )(1p0/p0) MetaCost 是一种是一种 reweighted 算法，算法，MetaCost

40、的基本思想是利用的基本思想是利用 Bayes 风险风险理论，根据理论，根据 cost 最优分类为训练数据集上的实例进行重标记，从而获得目标非最优分类为训练数据集上的实例进行重标记，从而获得目标非 cost-sensitive 分类算法的对应的分类算法的对应的cost-sensitive 分类算法。分类算法。MetaCost AdaCost 算法由算法由 AdaBoost 分类算法改进而来，也是一种通过分类算法改进而来，也是一种通过 reweighted 方方式获取式获取 cost-sensitive 分类算法的方法。分类算法的方法。 AdaCost 的基本思想是使用若干个较弱的的基本思想是使用

41、若干个较弱的分类器以投票方式集成出一个分类器，各个分类器的权值由评价函数调整确定。分类器以投票方式集成出一个分类器，各个分类器的权值由评价函数调整确定。AdaCostu研究总结 Multi-class 的的 cost-sensitive 分类将会是未来本领域的研究热点之一。分类将会是未来本领域的研究热点之一。 如前文所述，如前文所述， 在在 multi-class 分类中，分类中， rescaling 方法不再能够被简单地运用到其中。机器学习研究者们需要方法不再能够被简单地运用到其中。机器学习研究者们需要研究除了数据集类型比例之外，其他对于研究除了数据集类型比例之外，其他对于 cost-sensitive 分类问题结果有显著影响的因素，分类问题结果有显著影响的因素，从而提高分类算法的从而提高分类算法的 cost-sensitive 分类性能。分类性能。 寻找寻找 cost 的实际意义也有一定的研究价值。的实际意义也有一定的研究价值。除此之外可能的研究点还包括除此之外可能的研究点还包括 cost-sensitive 分类的效率问题，分类的效率问题， cost-sensitive 分类的分类的 benchmark 以及通用性的以及通用性的 cost-sensitive 分类算法等分类算法等Thanks