《数据挖掘 决策树..docx》由会员分享，可在线阅读，更多相关《数据挖掘 决策树..docx（11页珍藏版）》请在三一文库上搜索。
1、数据挖掘决策树算法数据挖掘决策树算法书本DATA Mining concepts and techniques third edition 关于决策树的描述算法Generation_decision_tree的创建过程如下：1、 创建一个节点N2、 IF D的元组都在同一类C中，then返回N作为叶节点，以类C标记3、 IF attribute_list为空，then返回N作为叶节点，标记D中的多数类4、 使用Attribute_lselection_method(D, attribute_list)找出最好的splitting_criterion5、 用splitting_criterion
2、标记节点N6、 IF splitting_criterion是离散值，并且多路划分，删除分裂属性7、 For splitting_criterion的每个输出j:设Dj中D满足输出j的数据元组的集合，if Dj为空，加一个树叶到节点N，标记为D中的多数类，else 加一个由Generation_decision_tree(D, attribute_list)返回的节点到N8、 返回N在实际操作中，选取数据很重要，决策树是分类算法，在网http:/archive.ics.uci.edu/ml/选取数据时，选择Classification类，由于第一次做数据分析，以及对R语言不懂，对于数据的属性类
3、Attributes选择在510之间，最终数据定位在BreastTissue，Auto-Mpg，car三个数据之一在数据的导入过程，各种数据类型不一样，导入的方式不一样，最终各种尝试之后，选择导入text文本文档在这个过程还是属性跟数值对不齐，至于数据框输入实现不了，Attribute有七个，但是数值有1728个手动输入是不可行的R语言实现过程，参照Generation_decision_tree的创建过程，通过先用c实现，再根据c结构试探性用r构造，期间参考了Python对于决策树算法的实现过程，以及实际案例Iris的实际案例。1）数据输入以及数据判断是否合理,计算刚开始类别的Info(熵)
4、2）计算训练集合D对特征值A的条件熵3）计算训练集合D对特征值A的信息增益4）根据训练集合生成决策树：先根据之前的分类统计类别出现次数，然后进行排序过D中都属于同一类，那么树就是单节点树，如果属性向量为空，那么将D频数最高的类返回，计算属性向量中各特征值对D的信息增益，选择信息增益最大的特征值Ag及其信息增益如果最大信息增益小于阈值e，将D中频数最高的类别返回，否则，对Ag的每一可能值ai，依Ag=ai将D分割为若干非空子集Di，将Di中实例数最大的类作为标记，构建子节点由节点及其子节点构成树T，返回T，然后递归调用，提出已使用的属性5）出现问题，理论上可行但是在实际用的过程，return总是
5、出错，重复调用有问题，还有就是在开始用的数据包有但是不知道怎么把构建的树画出来在分析这个简单数据的过程中，决策树的构建过程已经掌握，用C可以实现构造，但是没有掌握R的而且指令语法都不熟，只能进行少数据手动输入的简单分析，对于大数据数据导入的分析存在难度，问题症结所在是对R的不熟悉，对于数据的预处理，理论上掌握，手动输入少量数据也可以实现，但是对于数据大规模整体导入，也有点觉得束手无策，解决的办法就是尽快熟练掌握R语言。数据挖掘技术决策树决策树是通过一系列规则对数据进行分类的过程。建决策树，首先根据记录字段的不同取值建立树的分支，以及在每个分支子集中重复建立下层结点和分支。对于建立分支时对记录字
6、段不同取值的选择，采用information gain进行属性选择。ID3是基于信息熵的决策树分类算法，该算法是根据属性集的取值选择实例的类别。它的核心是在决策树中各级结点上选属性，用信息增益率作为属性选择标准，使得在每一非叶结点进行测试时，能获得关于被测试例子最大的类信息。使用该属性将例子集分成子集后，系统的熵值最小，期望该非叶结点到达各后代叶节点的平均路径最短，我们组选用数据为是新切除的组织从乳房样品的电阻抗测量数据集，对其构造决策树。首先应当对数据进行分类，用information gain进行属性分类，我们将数据按照属性进行分类之后，计算此分类下的期望l(S1,S2,Sm)=-ilog
7、2(i)(i=1,m，数据集为S，m为S的分类数目, i,(|Sj|)/(|S|),计算各个属性的熵，求由属性划分为子集的熵E(A)=(S1j+S2j+,+Smj)/S*I(S1j+S2j+,+Smj)，(A为属性，具有A个不同的取值)，求出信息增益Gain(A)=l(S1,S2,Sm )-E(A)，这时候开始选择Gain(A)最大的也就是E(A)最小的属性A作为根节点，用于划分的属性。对于A不同的取值对应不同E的V个子集Ej 递归调用上述过程，生成A的子节点B1，B2,BV。决策树任务：用weka实现数据预处理，用C4.5算法构建决策树和通过10折交叉验证评估模型的性能，以及模型验证的结果。
8、l 数据集：breast-cancer.arffl 数据预处理：（选择分类器错分的样本）点击apply，可以看到样本的数量从286减少到了72 ，l 用C4.5算法构建的决策树：模型性能的评估结果：l decision tree决策树的C4.5算法：（1） 用信息增益比例的概念。一个属性的信息增益比例用下面的公式给出：决策树C4.5算法的伪代码如下所示：Function C4.5(R,C,S) /建立一个决策树 /R:除目标属性外的所有属性；C：目标属性；S：一个训练集 Begin If S is empty then Returm 一个值为failure的结点； If训练集S中所有的记录的目
9、标属性为同一个a then Return具有值为a的结点； If R为空then Return一个节点，节点的值为训练集中目标属性中出现最多的目标属性： /这将出现错误，也就是说记录不能正确分类 For R中的每个属性Ri do If Ri 值为连续值then Begin Al=min(Ri)； Am=max(Ri)；m值手工设置 For j=2 to m-1 do Aj=Al+j*(Al-Am)/m； 使A为Ri的值，Ri具有最大Gain(Ri,S)Aj; End;D为R属性具有最大Gain(D,S)的属性；D的属性值为dj | j=1, 2, , m;S的子集Sj | j=1, 2, ,
10、m各自包含属性D的值为dj的记录；Return根节点标记为D树和到d1, d2, ,dm的弧；C4.5(R-D, C, SI),C4.5(R-D,C,S2), ,C4.5(R-D,C,Sm);EndC4.5使用以下的标准终止树的增长：（1） 当前节点的所有的训练集样本属于同一类别。（2） 每一个可能测试的潜在子树中少于两个的子树有比预定义数量多的样本。该数量的缺省值是2.（3） 找不到具有真正测试评估函数值得测试。l evaluate the model performance1. 10-fold cross-validation，用来测试精度。是常用的精度测试方法.将数据集分成十分，轮流将其
11、中9份做训练1份做测试，10次的结果的均值作为对算法精度的估计，一般还需要进行多次10倍交叉验证求均值，例如10次10倍交叉验证，更精确一点。2. Metrics for Performance Evaluationl Most widely-used metric:书是我们时代的生命别林斯基书籍是巨大的力量列宁书是人类进步的阶梯高尔基书籍是人类知识的总统莎士比亚书籍是人类思想的宝库乌申斯基书籍举世之宝梭罗好的书籍是最贵重的珍宝别林斯基书是唯一不死的东西丘特书籍使人们成为宇宙的主人巴甫连柯书中横卧着整个过去的灵魂卡莱尔人的影响短暂而微弱，书的影响则广泛而深远普希金人离开了书，如同离开空气一样不能生活科洛廖夫书不仅是生活，而且是现在、过去和未来文化生活的源泉 库法耶夫书籍把我们引入最美好的社会，使我们认识各个时代的伟大智者史美尔斯书籍便是这种改造灵魂的工具。人类所需要的，是富有启发性的养料。而阅读，则正是这种养料雨果