邓少军-厦门大学数据库室

报告人：邓少军指导老师：林子雨2015年7月17日论文报告厦门大学数据库实验室目录一种多类别条件下的代价敏感决策树算法Cost-sensitive分类算法——综述与实验一种基于NNIA多目标优化的代价敏感决策树构建方法Part1一种多类别条件下的代价敏感决策树算法论文摘要代价敏感决策树是代价敏感分类算法中一种，它的目标是在分类过程中保证一定分类准确度条件下产生最少的分类总代价。典型的基于贪心方法而建立的单一代价敏感决策树模型的算法有PM、MinCost等，这类算法相比于其它代价敏感分类算法具有较好可理解性、需要较少时间和空间复杂度的特点。本文研究了PM、MinCost以及多类别条件下属性检测代价和误分类代价矩阵的特点，提出了多类别问题下的一种基于评分策略的代价敏感决策树算法（简称SECSDT_MC）。关键词：代价敏感；多类别；决策树误分类代价和属性检测代价代价敏感决策树算法分类误分类代价指的是将真实类别为A的样例错误地分类为类别B时需要付出的代价；属性检测指的是为获得样例相关属性的属性值需要付出的代价。一类是基于贪心方法建立单一的分类模型的代价敏感决策树，例如PM和MinCost；另一类利用集成学习的方法，通过Boosting、Bagging等方式综合多个决策树模型构建出最终的代价敏感分类器模型，例如MetaCost和AdaBoost等。基础理论知识介绍相关工作MinCost和PM在选择分裂属性时采用的公式具体如下：其中，ICF是InformationCostFunction的简称；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、Class2、…、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(Ai)作为评估代价因素的指标。由于AvgInfoGain(Ai)在数值规模上远小于CostRed(Ai)的数值规模，为了防止像PM算法那样，整个公式的计算结果主要受代价因素影响，这里要对AvgInfoGain(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)和CostOfClass(Classi)后，就可以计算当前节点上的期望误分类代价ExpMisCost(S)，具体如公式(10)所示:根据上述公式计算出各个候选属性的AvgInfoGain(Ai)和CostRed(Ai)后，就需要对其进行归一化处理。具体的方法是分别求得每个属性关于AvgInfoGain(Ai)和CostRed(Ai)的最大值，记为MaxAvgInfoGain和MaxCostRed，则归一化后的结果（记为AvgInfoGain(Ai)normal和CostRed(Ai)normal）如公式(11)和(12)所示：我们尝试探讨a的取值与误分类代价矩阵、当前节点上各个样例的个数之间的关系。令maxMisCost和minMisCost当前节点上各个类别的CostOfClass(Classi)的最大值和最小值，并将a设定为minMisCost和maxMisCost的商。算法的收敛条件（1）节点上的某个类别的样例个数占节点上样例总数的比例大于或等于某个阈值（例如95%），并且样例总数也大于或等于给定的阈值。（2）节点上的样例总数少于某个指定的阈值。（3）从根节点到该节点的父节点的路径上，已经用尽了所有的测试属性，此时，应该将该节点标记为叶子节点。（4）如果选择出的分裂属性不能使得分类总代价有所减少，则将该节点标记为叶子节点未来展望在未来的研究工作中，我们将尝试SECSDT_MC应用到通过Boosting、Bagging多方法建立的复杂的代价敏感决策树算法（例如AdaBoost、MetaCost），并分析这样的集成方式是否有利于进一步减少分类总代价或者提高分类准确度。SECSDT_MC、PM、MinCost在构建代价敏感决策树模型之前都已经获得了各个属性的检测代价和误分类代价矩阵。而如果在模型构建之前或过程中，这些代价因素还处于未知状态，或者在构建过程中，或者分类阶段才获得这些代价因素，很明显SECSDT_MC、PM、MinCost都不适合用于解决这类问题。因此，在未来研究工作中，我们将尝试提出适合这类问题的代价敏感分类算法。Part2一种基于NNIA多目标优化的代价敏感决策树构建方法论文摘要本文提出了一种基于非支配邻域免疫算法(NNIA,NondominatedNeighborImmuneAlgorithm)多目标优化的代价敏感决策树构建方法.将平均误分类代价和平均测试代价作为两个优化目标,然后利用NNIA对决策树进行优化,最终获取了一组Pareto最优的决策树。关键词：代价敏感;误分类代价;测试代价;多目标优化;决策树前言介绍在分类过程中同时考虑多种代价的问题通常称为多代价敏感分类,解决这种问题主要有两种策略:一种是将多种代价转换为一种综合代价,另外一种是将每种代价视作一个目标并利用多目标优化技术寻优.目前多代价敏感决策树构建方法主要采用第一种方式,即在构建代价敏感的决策树过程中,将不同代价在同一尺度下进行衡量,或者将不同代价通过加权的方式合并为一种新的代价.本文提出了一种基于NNIA的代价敏感决策树构建方法,将平均误分类代价和平均测试代价作为两个优化目标,利用NNIA对决策树进行优化.NNIA算法的基本步骤包括:初始抗体群的建立、优势抗体群更新、终止条件判断、活性抗体群的选择、比例克隆,以及重组和超变异操作.为了使NNIA更适应决策树抗体并且进一步降低复杂度,本文在构建代价敏感决策树过程中对NNIA算法进行了改进,这种基于NNIA算法的代价敏感决策树的构建框图如图1所示.基于NNIA算法的代价敏感决策树构建优化目标的确定给定决策树t和训练样本集D,则平均误分类代价f1(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)是指示函数.从决策树的根节点到每一个叶节点的路径组成一条判决规则,即决策树中的每一个叶节点对应一条判决规则.由根节点至叶节点顺序累加获取属性ai所需代价即为规则r的测试代价TR(r),定义如式(3)所示:决策树t的平均测试代价f2(t)的定义如式(4)所示:其中Dl是训练数据集D中满足规则rl的决策属性条件的样本子集,|Dl|是集合Dl的数据样本数目,rl是叶节点l对应的判决规则.确定了平均误分类代价f1(t)和平均测试代价f2(t)后,本文提出的方法归结为利用NNIA算法解决式(5)中的两个目标的优化问题:决策树抗体的随机生成本文随机建立的二叉决策树为满二叉树,并且建立过程与传统的采用启发式策略自顶向下建立决策树的方法不同,其内部节点决策属性和分裂点都是随机选择的,这有利于在整个决策空间搜索.如果内部节点选择的决策属性为离散型,设该属性的取值集合为Vd,分裂集合则为在集合Vd中随机选择的不为空的子集V*d,且V*d与Vd不相等.若测试样本的该属性取值属于集合V*d,则转向决策树左分支,否则转向右分支.对于连续属性,需要预先根据训练样本集D来设置候选分裂值集合Vc,分裂值为在集合Vc中随机选取的元素v.若测试样本的该属性值不大于v,则转向左分支,否则转向右分支.叶节点类别的指