2020-06-06 阅读量: 4281
一,决策树-解决分类问题的一般方法
1、模型构建（归纳）
通过对训练集合的归纳，建立分类模型。
2、预测应用（推论）
根据建立的分类模型，对测试集合进行测试
二, 决策树的本质
•决策树是一种典型的分类方法
•首先对数据进行处理，利用归纳算法生成可读的规则和决策树，
•然后使用决策对新数据进行分析。
•本质上决策树是通过一系列规则对数据进行分类的过程。
三,决策树的优点
•1、推理过程容易理解，决策推理过程可以表示成If Then形式；
•2、推理过程完全依赖于属性变量的取值特点；
•3、可自动忽略目标变量没有贡献的属性变量，也为判断属性变量的重要性，减少变量的数目提供参考。
四,决策树和归纳算法
•决策树技术发现数据模式和规则的核心是归纳算法。
•归纳是从特殊到一般的过程。
•归纳推理从若干个事实中表征出的特征、特性和属性中，通过比较、总结、概括而得出一个规律性的结论。
•归纳推理试图从对象的一部分或整体的特定的观察中获得一个完备且正确的描述。即从特殊事实到普遍性规律的结论。
•归纳对于认识的发展和完善具有重要的意义。人类知识的增长主要来源于归纳学习。
•归纳学习由于依赖于检验数据，因此又称为检验学习。
•归纳学习存在一个基本的假设：
•任一假设如果能够在足够大的训练样本集中很好的逼近目标函数，则它也能在未见样本中很好地逼近目标函数。该假定是归纳学习的有效性的前提条件。
•归纳过程就是在描述空间中进行搜索的过程。
•归纳可分为自顶向下，自底向上和双向搜索三种方式。
•自底向上法一次处理一个输入对象。将描述逐步一般化。直到最终的一般化描述。
•自顶向下法对可能的一般性描述集进行搜索，试图找到一些满足一定要求的最优的描述。
五.决策树算法
•与决策树相关的重要算法包括：
•CLS, ID3，C4.5，CART
•算法的发展过程
•Hunt,Marin和Stone 于1966年研制的CLS学习系统，用于学习单个概 念。
•1979年, J.R. Quinlan 给出ID3算法，并在1983年和1986年对ID3 进行了总结和简化，使其成为决策树学习算法的典型。
•Schlimmer 和Fisher 于1986年对ID3进行改造，在每个可能的决策树节点创建缓冲区，使决策树可以递增式生成，得到ID4算法。
•1988年，Utgoff 在ID4基础上提出了ID5学习算法，进一步提高了效率。
•1993年，Quinlan 进一步发展了ID3算法，改进成C4.5算法。
•另一类决策树算法为CART，与C4.5不同的是，CART的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正例与反例。
六,决策树的表示
决策树的基本组成部分：决策结点、分支和叶子
决策树中最上面的结点称为根结点。
是整个决策树的开始。每个分支是一个新的决策结点，或者是树的叶子。
每个决策结点代表一个问题或者决策.通常对应待分类对象的属性。
每个叶结点代表一种可能的分类结果
在沿着决策树从上到下的遍历过程中，在每个结点都有一个测试。对每个结点上问题的不同测试输出导致不同的分枝，最后会达到一个叶子结点。这一过程就是利用决策树进行分类的过程，利用若干个变量来判断属性的类别.
七,决策树与条件概率分布
•决策树表示给定特征条件下类的条件概率分布。
•条件概率分布定义在特征空间的一个划分(partition)上.将特征空间划分为互不相交的单元(cell)或区域(region),并在每个单元定义一个类的概率分布就构成了一个条件概率分布。
•决策树的一条路径对应于划分中的一个单元。
•决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成
•决策树学习本质上是从训练数据集中归纳出一组分类规则，与训练数据集不相矛盾的决策树。
•能对训练数据进行正确分类的决策树可能有多个，也可能 一个也没有.我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的 泛化能力.
•决策树学习是由训练数据集估计条件概率模型.基于特征空间划分的类的条件概率模型有无穷多个.
•我们选择的条件概率模型应该不仅对训练数据有很好的拟合，而且对未知数据有很好的预测.
八,决策树CLS算法
•CLS（Concept Learning System）算法
•CLS算法是早期的决策树学习算法。它是许多决策树学习算法的基础
•CLS基本思想
•从一棵空决策树开始，选择某一属性（分类属性）作为测试属性。该测试属性对应决策树中的决策结点。根据该属性的值的不同，可将训练样本分成相应的子集：
•如果该子集为空，或该子集中的样本属于同一个类，则该子集为叶结点，
•否则该子集对应于决策树的内部结点，即测试结点，需要选择一个新的分类属性对该子集进行划分，直到所有的子集都为空或者属于同一类。
•步骤：
•生成一颗空决策树和一张训练样本属性集;
•若训练样本集T 中所有的样本都属于同一类,则生成结点T , 并终止学习算法;否则
•根据某种策略从训练样本属性表中选择属性A 作为测试属性, 生成测试结点A
•若A的取值为v1,v2,…,vm, 则根据A 的取值的不同,将T 划分成 m个子集T1,T2,…,Tm;
•从训练样本属性表中删除属性A;
•转步骤2, 对每个子集递归调用CLS;
•CLS算法问题：
•在步骤3中，根据某种策略从训练样本属性表中选择属性A作为测试属性。没有规定采用何种测试属性。实践表明，测试属性集的组成以及测试属性的先后对决策树的学习具有举足轻重的影响。
九,决策树ID3算法
•ID3算法是一种经典的决策树学习算法，由Quinlan于1979年提出。
•ID3算法主要针对属性选择问题。是决策树学习方法中最具影响和最为典型的算法。
• 该方法使用信息增益度选择测试属性。
•当获取信息时，将不确定的内容转为确定的内容，因此信息伴着不确定性。
•从直觉上讲，小概率事件比大概率事件包含的信息量大。如果某件事情是“百年一见”则肯定比“习以为常”的事件包含的信息量大。
信息增益
•Shannon 1948年提出的信息论理论：
•熵(entropy)：信息量大小的度量，即表示随机变量不确定性的度量。
•熵的通俗解释：事件ai的信息量I( ai )可如下度量：
•其中p(ai)表示事件ai发生的概率。
•假设有n个互不相容的事件a1,a2,a3,….,an,它们中有且仅有一个发生，则其平均的信息量(熵)可如下度量：
•熵的理论解释：
•设X是一个取有限个值的离散随机变量，其概率分布为：
•则随机变量X的熵定义为：
•对数以2为底或以e为底(自然对数)，这时熵的单位分别称作比特(bit)或纳特(nat),熵只依赖于X的分布，与X的取值无关。
•熵的理论解释：
•熵越大，随机变量的不确定性越大
•定义5.2 (信息增益):特征A对训练数据集D的信息增益，g(D,A), 定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即
g(D,A)=H(D)-H(D|A)
•(Information gain)表示得知特征X的信息而使得类Y的信息的不确定性减少的程度.
•—般地，熵H(Y)与条件熵H(Y|X)之差称为互信息（mutual information)
•决策树学习中的信息增益等价于训练数据集中类与特征的互信息.
.....
后续再更
