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

《报告人邓少军指导老师林子雨2015.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、报告人：邓少军指导老师：林子雨2015年7月17日论文报告厦门大学数据库实验室目录一种多类别条件下的代价敏感决策树算法Cost-sensitive分类算法——综述与实验一种基于NNIA多目标优化的代价敏感决策树构建方法Part1一种多类别条件下的代价敏感决策树算法论文摘要代价敏感决策树是代价敏感分类算法中一种，它的目标是在分类过程中保证一定分类准确度条件下产生最少的分类总代价。典型的基于贪心方法而建立的单一代价敏感决策树模型的算法有PM、MinCost等，这类算法相比于其它代价敏感分类算法具有较好可理解性、需要较少时间和空间复杂

2、度的特点。本文研究了PM、MinCost以及多类别条件下属性检测代价和误分类代价矩阵的特点，提出了多类别问题下的一种基于评分策略的代价敏感决策树算法（简称SECSDT_MC）。关键词：代价敏感；多类别；决策树误分类代价和属性检测代价代价敏感决策树算法分类误分类代价指的是将真实类别为A的样例错误地分类为类别B时需要付出的代价；属性检测指的是为获得样例相关属性的属性值需要付出的代价。一类是基于贪心方法建立单一的分类模型的代价敏感决策树，例如PM和MinCost；另一类利用集成学习的方法，通过Boosting、Bagging等方式综合

3、多个决策树模型构建出最终的代价敏感分类器模型，例如MetaCost和AdaBoost等。基础理论知识介绍相关工作MinCost和PM在选择分裂属性时采用的公式具体如下：其中，ICF是InformationCostFunction的简称；DMCA表示在决策树模型内部节点上的样例依据属性A分拨到各个子节点上后，当前节点上的期望误分类代价与各个子节点的期望误分类代价的和的差值。InfoGainA表示属性A的信息增益；CA表示当前节点上的所有样例关于属性A的测试代价的和；w是依据专家经验给定的关于属性A的重要性度量值。（1）由于代价因素

4、与信息增益的不在同一个数值规模上，因此在公式(2)中容易造成ICF的计算结果主要取决于DMCA和(CA+1)的商；（2）公式中关于分类准确度的计算采用了信息增益。由于增益越高分类准确度越好，为了获得更高的信息增益，算法倾向于选择属性值较少的属性，但是，属性值越少的属性带来的误分类代价不一定更少。PM算法的缺点MinCost算法不足MinCost在选择分类属性的启发式函数中只对代价因素进行相关的计算，并未引入信息增益、基尼系数、模糊规则、隶属函数等信息论方法来计算分类的准确度。然而，在满足一定分类准确度条件下获得最少的分类总代价，

5、需要综合考虑分类准确度因素和分类问题涉及到的各种代价因素。多类别条件下的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，即正确分类的情况下不产生误分类代价。代价敏感决策树的代价函数可

6、以用公式(3)表示：其中，F(x,i)表示利用代价敏感决策树模型将样例x分类Classi所产生的总代价（误分类代价和属性检测代价的和）；p(j

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

8、式函数的计算结果进行加权求和。各个候选属性中最终的计算结果最高的那个就作为该节点上的分裂属性。其中，score(Ai)表示候选属性Ai的评分结果；AvgInfoGain(Ai)表示利用平均信息增益作为评估分类准确度的指标，具体定义如公式(5)所示；CostRed(Ai)表示分类代价减少量，具体如公式(6)所示，这里用CostRed(Ai)作为评估代价因素的指标。由于AvgInfoGain(Ai)在数值规模上远小于CostRed(Ai)的数值规模，为了防止像PM算法那样，整个公式的计算结果主要受代价因素影响，这里要对AvgInfo

9、Gain(Ai)和CostRed(Ai)进行归一化处理，具体的方法如公式(11)(12)所示。求得归一化的AvgInfoGain(Ai)和CostRed(Ai)后，再对这两项指标进行加权求和，最后得分最高的候选属性就作为代价敏感决策树模型内部节点上的分裂属性。关