给女朋友做网站,房产中介网站排名,wordpress登陆名,wordpress如何去掉显示文章的分类机器学习中#xff0c;决策树是一个预测模型#xff1b;它代表的是对象属性值与对象值之间的一种映射关系。树中每个节点表示某个对象#xff0c;每个分叉路径则代表的某个可能的属性值#xff0c;而每个叶结点则对应具有上述属性值的子对象。决策树仅有单一输出#xff1… 机器学习中决策树是一个预测模型它代表的是对象属性值与对象值之间的一种映射关系。树中每个节点表示某个对象每个分叉路径则代表的某个可能的属性值而每个叶结点则对应具有上述属性值的子对象。决策树仅有单一输出若需要多个输出可以建立独立的决策树以处理不同输出。 每个决策树都表述了一种树型结构它由它的分支来对该类型的对象依靠属性进行分类。每个决策树可以依靠对源数据库的分割进行数据测试。这个过程可以递归式的对树进行修剪。当不能再进行分割或一个单独的类可以被应用于某一分支时递归过程就完成了。另外随机森林分类器将许多决策树结合起来以提升分类的正确率。 决策树同时也可以依靠计算条件概率来构造。决策树如果依靠数学的计算方法可以取得更加理想的效果。1986年Quinlan提出了著名的ID3算法。在ID3算法的基础上1993年Quinlan又提出了C4.5算法。为了适应处理大规模数据集的需要后来又提出了若干改进的算法其中SLIQ (super-vised learning in quest)和SPRINT (scalable parallelizableinduction of decision trees)是比较有代表性的两个算法。 决策树的工作原理 决策树一般都是自上而下的来生成的。 选择分割的方法有多种但是目的都是一致的即对目标类尝试进行最佳的分割。 从根节点到叶子节点都有一条路径这条路径就是一条“规则”。决策树可以是二叉的也可以是多叉的。对每个节点的衡量 通过该节点的记录数 如果是叶子节点的话分类的路径 对叶子节点正确分类的比例。 (1) ID3算法 ID3算法的核心是在决策树各级结点上选择属性时用信息增益information gain作为属性的选择标准以使得在每一个非叶结点进行测试时能获得关于被测试记录最大的类别信息。其具体方法是检测所有的属性选择信息增益最大的属性产生决策树结点由该属性的不同取值建立分支再对各分支的子集递归调用该方法建立决策树结点的分支直到所有子集仅包含同一类别的数据为止。最后得到一棵决策树它可以用来对新的样本进行分类。 ID3算法的优点是算法的理论清晰方法简单学习能力较强。其缺点是只对比较小的数据集有效且对噪声比较敏感当训练数据集加大时决策树可能会随之改变。 (2) C4.5算法 C4.5算法继承了ID3算法的优点并在以下几方面对ID3算法进行了改进 用信息增益率来选择属性克服了用信息增益选择属性时偏向选择取值多的属性的不足 在树构造过程中进行剪枝 能够完成对连续属性的离散化处理 能够对不完整数据进行处理。 C4.5算法与其它分类算法如统计方法、神经网络等比较起来有如下优点产生的分类规则易于理解准确率较高。其缺点是在构造树的过程中需要对数据集进行多次的顺序扫描和排序因而导致算法的低效。此外C4.5只适合于能够驻留于内存的数据集当训练集大得无法在内存容纳时程序无法运行。 (3) SLIQ算法 SLIQ算法对C4.5决策树分类算法的实现方法进行了改进在决策树的构造过程中采用了“预排序”和“广度优先策略”两种技术。 预排序。对于连续属性在每个内部结点寻找其最优分裂标准时都需要对训练集按照该属性的取值进行排序而排序是很浪费时间的操作。为此SLIQ算法采用了预排序技术。所谓预排序就是针对每个属性的取值把所有的记录按照从小到大的顺序进行排序以消除在决策树的每个结点对数据集进行的排序。具体实现时需要为训练数据集的每个属性创建一个属性列表为类别属性创建一个类别列表。 广度优先策略。在C4.5算法中树的构造是按照深度优先策略完成的需要对每个属性列表在每个结点处都进行一遍扫描费时很多为此SLIQ采用广度优先策略构造决策树即在决策树的每一层只需对每个属性列表扫描一次就可以为当前决策树中每个叶子结点找到最优分裂标准。 SLIQ算法由于采用了上述两种技术使得该算法能够处理比C4.5大得多的训练集在一定范围内具有良好的随记录个数和属性个数增长的可伸缩性。然而它仍然存在如下缺点 由于需要将类别列表存放于内存而类别列表的元组数与训练集的元组数是相同的这就一定程度上限制了可以处理的数据集的大小。 由于采用了预排序技术而排序算法的复杂度本身并不是与记录个数成线性关系因此使得SLIQ算法不可能达到随记录数目增长的线性可伸缩性。 (4) SPRINT算法 为了减少驻留于内存的数据量SPRINT算法进一步改进了决策树算法的数据结构去掉了在SLIQ中需要驻留于内存的类别列表将它的类别列合并到每个属性列表中。这样在遍历每个属性列表寻找当前结点的最优分裂标准时不必参照其他信息将对结点的分裂表现在对属性列表的分裂即将每个属性列表分成两个分别存放属于各个结点的记录。 SPRINT算法的优点是在寻找每个结点的最优分裂标准时变得更简单。其缺点是对非分裂属性的属性列表进行分裂变得很困难。解决的办法是对分裂属性进行分裂时用哈希表记录下每个记录属于哪个孩子结点若内存能够容纳下整个哈希表其他属性列表的分裂只需参照该哈希表即可。由于哈希表的大小与训练集的大小成正比当训练集很大时哈希表可能无法在内存容纳此时分裂只能分批执行这使得SPRINT算法的可伸缩性仍然不是很好。 下面以ID3和C4.5为例说明 ID3算法 从信息论知识中我们直到期望信息越小信息增益越大从而纯度越高。所以ID3算法的核心思想就是以信息增益度量属性选择选择分裂后信息增益最大的属性进行分裂。下面先定义几个要用到的概念。 设D为用类别对训练元组进行的划分则D的熵entropy表示为 其中pi表示第i个类别在整个训练元组中出现的概率可以用属于此类别元素的数量除以训练元组元素总数量作为估计。熵的实际意义表示是D中元组的类标号所需要的平均信息量。 现在我们假设将训练元组D按属性A进行划分则A对D划分的期望信息为 而信息增益即为两者的差值 ID3算法就是在每次需要分裂时计算每个属性的增益率然后选择增益率最大的属性进行分裂。下面我们继续用SNS社区中不真实账号检测的例子说明如何使用I D3算法构造决策树。为了简单起见我们假设训练集合包含 10个元素 其中s、m和l分别表示小、中和大。 设L、F、H和R表示日志密度、好友密度、是否使用真实头像和账号是否真实下面计算各属性的信息增益。 因此日志密度的信息增益是0.276。 用同样方法得到H和F的信息增益分别为0.033和0.553。 因为F具有最大的信息增益所以第一次分裂选择F为分裂属性分裂后的结果如下图表示 在上图的基础上再递归使用这个方法计算子节点的分裂属性最终就可以得到整个决策树。 上面为了简便将特征属性离散化了其实日志密度和好友密度都是连续的属性。对于特征属性为连续值可以如此使用ID3算法 先将D中元素按照特征属性排序则每两个相邻元素的中间点可以看做潜在分裂点从第一个潜在分裂点开始分裂D并计算两个集合的期望信息具有最小 期望信息的点称为这个属性的最佳分裂点其信息期望作为此属性的信息期望。 3.3.2、C4.5算法 ID3算法存在一个问题就是偏向于多值属性例如如果存在唯一标识属性ID则ID3会选择它作为分裂属性这样虽然使得划分充分纯净但这种划分对分类几乎毫无用处。ID3的后继算法C4.5使用增益率gain ratio的信息增益扩充试图克服这个偏倚。 C4.5算法首先定义了“分裂信息”其定义可以表示成 其中各符号意义与ID3算法相同然后增益率被定义为 C4.5选择具有最大增益率的属性作为分裂属性其具体应用与ID3类似不再赘述。 参考来源 http://www.cnblogs.com/kidoln/archive/2012/01/05/2312679.html http://www.cnblogs.com/leoo2sk/archive/2010/09/19/1831151.html
