基于决策树规则分类算法的研究(12-15)

基于决策树规则分类算法的研究报告人：孙秀芳2010年12月15日介绍内容•研究的主要内容•数据挖掘及其分类方法概述•C4.5算法•基于规则排序的决策树分类算法CABRR的研究一、研究的主要内容研究的主要内容：从决策树入手，从中提取决策树规则，并通过对决策树规则进行有效地排序后生成分类器，应用于分类预测。二、数据挖掘及其分类方法概述•数据挖掘的理论•分类概念及算法描述•分类算法度量的方法与尺度2.1数据挖掘的理论•数据挖掘的概念：所谓数据挖掘（又称数据库中的知识发现）是指从大量的、不完全的、有噪声的、模糊的、随机的海量数据中，或是大型数据库或数据仓库中提取隐含的、未知的、非平凡的、有潜在应用价值的信息或模式。•数据挖掘的过程：确定挖掘目的、数据准备、数据挖掘、模式评估与知识表示。•数据挖掘的具体过程如下图所示：数据源清理/集成后数据选择/变换后数据模式提供可供挖掘的知识清理与集成选择与变换数据挖掘评估与表示2.2分类概念及算法描述•分类的概念：所谓分类，就是对己知现存的类别，建立类别的描述规则分类器，然后对未知新例的观察值进行判断归类。•下图为分类过程图：训练集分类模型可接受的模型预测结果通过分类算法建立模型评估模型预测未知数据元组•典型的分类算法:常用的分类方法包括：决策树分类、关联分类、神经网络、贝叶斯分类方法等。基于决策树分类的典型算法有:ID3算法、C4.5算法、PART算法、CABRR算法等。2.3分类算法度量的方法与尺度•每种分类方法都需要用一定的指标来进行评估，常用的分类算法的比较与评估标准有如下几个方面：预测的准确率可理解性可伸缩性速度强壮性三、C4.5算法•决策树算法的基本理论•决策树的基本算法•C4.5算法3.1决策树算法的基本理论•决策树：是一种结构，一种知识的表达形式，它由两种元素组成:节点和分支。在最终生成的决策树上，其中每个内部节点表示数据集的一个属性，每个分支代表对该属性的一个测试输出，每个叶结点代表划分的类别，最顶端节点为根节点。•决策树的生成过程：主要分成两个步骤:一是生成树，二是树的修剪。•树的修剪：即树的剪枝，最常用的剪枝技术有预剪枝和后剪枝。•决策树的工作原理流程图如下：数据源训练集预处理决策树分类算法归纳生成决策树分类规则剪枝3.2决策树的基本算法Generate_decision_tree//根据给定数据集产生一个决策树输入：训练样本，各属性均取离散数值，可供归纳的候选属性集为:attribute_list。输出：决策树。处理流程程：（1）创建一个结点；（2）若该结点中的所有样本均为同一类别C，则（3）返回N作为一个叶结点并标志为类别C；（4）若attribute_list为空，则（5）返回N作为一个叶结点并标记为该结点所含样本中类别个数最多的类别；（6）从attribute_list选择一个信息增益最大的属性test_attribute；（7）并将结点N标记为test_attribute；（8）对于test_attribute中的每一个已知取值ai准备划分结点N所包含的样本集；（9）根据test_attribute=ai条件，从结点N产生相应的一个分支，以表示该测试条件；（10）设si为test_attribute=ai条件所获得的样本集合；（11）若si为空，则将相应叶结点标记为该结点所含样本中类别个数最多的类别；（12）否则将相应叶结点标志为Generate_decision_tree(si,attribute_list-test_attribute)返回值；3.3C4.5算法•C4.5算法：是对ID3的改进算法。该算法采用信息增益率作为对选择分枝属性的分枝准则，计算各属性的信息增益率，然后选取信息增益率最大的属性作为结点，自顶向下生成决策树。•对构造C4.5决策树的相关理论的描述如下:1.首先计算给定的样本所需的期望信息,设S为一个包含s个数据样本的集合，对于类别属性，可以取m个不同的值,对应于m个不同的类别Ci(i{1,2,...,m})。假设类别Ci中的样本个数为si，期望信息为:其中pi是任意样本属于Ci的概率，并用si/s估计。2.接着计算当前样本集合所需要的信息嫡，设一个属性A具有v个不同的值{a1,a2,...,av},利用属性A可以将集合S划分为v个子集{S1,S2,...,Sv}，其中Sj包含了S集合中属性A取aj值的数据样本，如果属性A被选为测试属性(最好的分裂属性)，设Sij为子集Sj中属于Ci类别的样本集，根据A划分计算的熵为:miiimppsssI1221)(log),...,(，其中项为第j个子集的权，也等于子集中样本个数除以S中的样本总数。熵值越小，子集划分的纯度越高。而对于子集sj有：其中，是子集sj中样本属于类别Ci的概率;然后利用属性A对当前分支结点进行相应样本集合划分计算信息增益:),...,(...)(111mjjvjmjjSSIsSSAEsSSmjj...1miijijmjjppssI121)(log),...,(||jijijssp)(),...,,()(21AEsssIAGainm3.最后，求取信息增益率，其表达式为：其中，这个Gainratio(A)值越大，分枝包含的有用信息越多。)()()(ASplitInfoAGainAGainratio||||log||||)(21SSSSASplitInfojvjjC4.5算法的工作流程图：开始读取、存储类信息读取属性信息读取数据库是连续属性划分区域存储至属性哈希表中读取训练样本有缺失数据忽略或用最多的属性值来替代存储样本表Ｋ次迭代交叉验证将数据集划分成K个子集对生成的树进行测试后打印分类信息取K-1个子集用C4.5算法建构树规则提取结束YＮYN四、基于规则排序的决策树分类算法CABRR的研究•CABRR算法的产生•CABRR算法基本概念•CABRR算法的基本思想及规则排序算法•CABRR算法的实例分析4.1CABRR算法的产生•CABRR算法的产生：用规则构造分类器时，对规则的排序分为两种:基于规则的排序和基于类的排序。在使用基于类的排序中，一个质量较差的规则可能碰巧预测较高秩的类，从而导致较高质量的规则被忽略。而基于规则的排序则能弥补这一点的不足，于是出现了基于规则的决策树分类规则算法CABRR。•基于类的排序：按照对类的规则的描述长度由小到大进行排序。•基于规则的排序：结合规则的长度、准确率和覆盖率这三个度量值进行排序。4.2CABRR算法基本概念•规则前件、规则后件：每一个分类规则可以表示为如下形式：，规则左边为规则前件，右边为规则后件。•准确率:是指节点中正确预测的实例与分配给该节点的实例总数之比，度量的是该节点会正确预测目标值的可能性记为：•覆盖率:是指节点中实例数量与构造数据集中实例总数之比，度量的是从构造数据集中分配了多少实例给该节点，记为：其中|A|是满足规则前件的记录数，|Ay|是同时满足规则前件和后件的记录数，|D|是记录总数。iiyir)(:条件||||)(AyArAccuracy||||)(DArCoverage•规则匹配:所谓规则匹配，就是对于新的对象，在规则集中查找匹配的规则，如果只有一条规则与之完全匹配，即各个属性值均相等，则将新对象归至匹配规则决策值对应的类别;如果有多个规则与之相匹配，必须对所有匹配规则进行排序，然后将新对象归至优先值最高的规则所定义的类别。4.3CABRR算法的基本思想及规则排序算法CABRR分类算法的基本思想可用过程图表示如右：数据源训练集C4.5算法归纳生成未剪枝的决策树分类规则规则排序构造分类器分类结果分类未知类别数据集开始读取未排好序的规则集Rules计算Rules中每条规则的长度按规则长度与准确率的乘积对Rules中规则进行排序，乘积大者优先某些规则的长度与准确率的乘积是否相等某些规则的长度是否相等按规则长度对这些规则重新排序按覆盖率对规则进行排序排好序的规则集Rules结束YNＹN基于规则的排序算法的思想流程图：规则集排序后对测试数据集进行分类的流程图：开始读取排好序的规则集Rules和测试数据集test-data-setfor循环读取test-data-set中的对象，并为其寻找匹配的规则设置一个Flag标志，赋初值为0，如果其值变为1，表示Rules中有与所读取对象相匹配得规则从前往后扫描Rules，直到有匹配的规则出现Rules中是否有匹配的规则将新对象归至匹配规则所定义的类别，并使Flag=1寻找覆盖率最大的规则所定义的类别，将新对象归至此类别中分好类的数据集结束NY4.5CABRR算法的实例分析接下来我们通过实验证明使用基于规则排序的CABRR算法的有效性。取脊椎动物数据集来做一个实验，具体的数据如下表（a）所示：表（a）脊椎动物数据集名字体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号人类恒温毛发是否否是否哺乳类蟒蛇冷血鳞片否否否否是爬行类鲑鱼冷血鳞片否是否否否鱼类鲸恒温毛发是是否否否哺乳类青蛙冷血无否半否是是两栖类巨蜥冷血鳞片否否否是否爬行类蝙蝠恒温毛发是否是是是哺乳类鸽子恒温羽毛否否是是否鸟类猫恒温软毛是否否是否哺乳类虹鱂冷血鳞片是是否否否鱼类美洲鳄冷血鳞片否半否是否爬行类企鹅恒温羽毛否半否是否鸟类豪猪恒温刚毛是否否是是哺乳类鳗鲡冷血鳞片否是否否否鱼类蝾螈冷血无否半否是是两栖类从上表中得出的未截枝的决策树如下图所示：体温胎生水生动物哺乳类（5.0）鸟类（2.0）爬行类（2.0）鱼类（3.0）两栖类（3.0/1.0)=恒温=冷血=是=否=否=是=半•对规则进行截枝后，得到的规则如下图所示：•具体的规则信息如下图所示：•然后分别用基于规则的排序算法和基于类的排序算法对规则进行排序，排序后的规则按优先顺序从高到低排序后分别如下表（b）、（c）所示：表（b）基于规则进行排序后的规则列表表（c）基于类进行排序后的规则列表ruleclassconfsuplength体温=冷血AND水生动物=否爬行类50.00%22体温=恒温AND胎生=否鸟类50.00%22胎生=是哺乳类61.20%61水生动物=是鱼类45.30%21Defaultclass:两栖类ruleclassconfsuplength胎生=是哺乳类61.20%61水生动物=是鱼类45.30%21体温=冷血AND水生动物=否爬行类50.00%22体温=恒温AND胎生=否鸟类50.00%22Defaultclass:两栖类•用表（b）和表（c）的规则构造分类器，分别对表（a）中的数据进行预测分类，得出的分类结果如表（d）和表（e）所示：•表（d）用基于规则排序后的分类器进行预测分类的结果名字体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号类排序分类人类恒温毛发是否否是否哺乳类哺乳类蟒蛇冷血鳞片否否否否是爬行类爬行类鲑鱼冷血鳞片否是否否否鱼类鱼类鲸恒温毛发是是否否否哺乳类哺乳类青蛙冷血无否半否是是两栖类两栖类巨蜥冷血鳞片否否否是否爬行类爬行类蝙蝠恒温毛发是否是是是哺乳类哺乳类鸽子恒温羽毛否否是是否鸟类鸟类猫恒温软毛是否否是否哺乳类哺乳类虹鱂冷血鳞片是是否否否鱼类鱼类美洲鳄冷血鳞片否半否是否爬行类两栖类企鹅恒温羽毛否半否是否鸟类鸟类豪猪恒温刚毛是否否是是哺乳类哺乳类鳗鲡冷血鳞片否是否否否鱼类鱼类蝾螈冷血无否半否是是两栖类两栖类•表（e）用基于类排序后的分类器进行预测分类的结果名字体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号类排序分类人类恒温毛发是否否是否哺乳类哺乳类蟒蛇冷血鳞片否否否否是爬行类爬行类鲑鱼冷血鳞片否是否否否鱼类鱼类鲸恒温毛发是是否否否哺乳类哺乳类青蛙冷血无否半否是是两栖类两栖类巨蜥冷血鳞片否否否是否爬行类爬行类蝙蝠恒温毛发是否是是是哺乳类哺乳类鸽子恒温羽毛否否是是否鸟类鸟类猫恒温软毛是否否是否哺乳类哺乳类虹鱂冷血鳞片是是否否否鱼类鱼类美洲鳄冷血鳞片否半否是否爬行类两栖类企鹅恒温羽毛否半否是否鸟类鸟类豪猪恒温刚毛是否否是是哺乳类哺乳类鳗鲡冷血鳞片否是否否否鱼类鱼类蝾螈冷血无否半否是是两