文档介绍:1、
机器学习中,决策树是一个预测模型;他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象,而每个分叉路径那么代表的某个可能的属性值,而每个叶结点那么对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出,假设欲有复数输出,可以建立独立的决策树以处理不同输出。从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。
决策树学习也是数据挖掘中一个普通的方法。在这里,每个决策树都表述了一种树型构造,他由他的分支来对该类型的对象依靠属性进展分类。每个决策树可以依靠对源数据库的分割进展数据测试。这个过程可以递归式的对树进展修剪。 当不能再进展分割或一个单独的类可以被应用于某一分支时,递归过程就完成了。另外,随机森林分类器将许多决策树结合起来以提升分类的正确率。决策树同时也可以依靠计算条件概率来构造。决策树如果依靠数学的计算方法可以取得更加理想的效果。决策树一般都是自上而下的来生成的。
选择分割的方法有好几种,但是目的都是一致的:对目标类尝试进展最正确的分割。从根到叶子节点都有一条路径,这条路径就是一条“规那么〞。决策树可以是二叉的,也可以是多叉的。对每个节点的衡量:
1)通过该节点的记录数
2)如果是叶子节点的话,分类的路径
3)对叶子节点正确分类的比例。
有些规那么的效果可以比其他的一些规那么要好。由于ID3算法在实际应用中存在一些问题,,。,这里就不做介绍。
,并在以下几方面对ID3算法进展了改良:
1) 用信息增益率来选择属性,克制了用信息增益选择属性时偏向选择取值多的属性的缺乏;
2) 在树构造过程中进展剪枝;
3) 能够完成对连续属性的离散化处理;
4) 能够对不完整数据进展处理。
:产生的分类规那么易于理解,准确率较高。其缺点是:在构造树的过程中,需要对数据集进展屡次的顺序扫描和排序,因而导致算法的低效。此外,,当训练集大得无法在内存容纳时程序无法运行。
来自搜索的其他内容:,其核心算法是ID3算法. 分类决策树算法是从大量事例中进展提取分类规那么的自上而下的决策树.
决策树的各局部是: 根: 学习的事例集. 枝: 分类的判定条件. 叶: 分好的各个类.
ID3算法
1) 初始化参数C={E},E包括所有的例子,为根.
2) IF C中的任一元素e同属于同一个决策类那么创立一个叶子节点YES终止.
ELSE 依启发式标准,选择特征Fi={V1,V2,V3,...Vn}并创立判定节点划分C为互不相交的N个集合C1,C2,C3,...,Cn;
3) 对任一个Ci递归.
2. ID3算法
1) 随机选择C的一个子集W (窗口).
2) 调用CLS生成W的分类树DT(强调的启发式标准在后).
3) 顺序扫描C搜集DT的意外(即由DT无法确定的例子).
4) 组合W与已发现的意外,形成新的W.
5) 重复2)到4),直到无例外为止.
启发式标准:
只跟本身与其子树有关,采取信息理论用熵来量度.
熵是选择事件时选择自由度的量度,其计算方法为
P = freq(Cj,S)/|S|;
INFO(S)= - SUM( P*LOG(P) ) ; SUM()函数是求j从1到n和.
Gain(X)=Info(X)-Infox(X);
Infox(X)=SUM( (|Ti|/|T|)*Info(X);
为保证生成的决策树最小,ID3算法在生成子树时,选取使生成的子树的熵(即Gain(S))最小的的特征来生成子树.
§: ID3算法对数据的要求
1. 所有属性必须为离散量.
2. 所有的训练例的所有属性必须有一个明确的值.
3. 一样的因素必须得到一样的结论且训练例必须唯一.
§: :
1. 熵的改良,加上了子树的信息.
Split_Infox(X)= - SUM(