机器学习-决策树 Decision Tree

内容导航：

机器学习-决策树 Decision Tree

决策树（Decision Tree）

决策树(decisionTree)

ML - 决策树(decision tree)

一、机器学习-决策树 Decision Tree

咱们正式进入了机器学习的模型的部分，虽然现在最火的的机器学习方面的库是Tensorflow, 但是这里还是先简单介绍一下另一个数据处理方面很火的库叫做sklearn。其实咱们在前面已经介绍了一点点sklearn，主要是在categorical data encoding那一块。其实sklearn在数据建模方面也是非常666的。一般常用的模型都可以用sklearn来做的。既然它都这么牛逼了，咱们为啥还要学TensorFlow呢？其实主要的原因有两个，一是因为Google在流量方面的强势推广，导致绝大部分的机器学习方面的应用都是用TensorFlow, 二是因为TensorFlow包括的常用库确实要更加多一点。所以导致现在TensorFlow直接火到爆。所以sklearn在模型方面的应用，咱们只在决策树这里讲一下，都免绝大部分的模型还是用TensorFlow来解释，毕竟它的市场更加大嘛。这里没有啥好坏之分的，他们的API都写的很清楚，无论选什么框架，大家自己起看看文档都可以的。这节内容主要分两部分，第一部分介绍决策树在sklearn中的应用，第二部分作为补充内容介绍决策树的原理（决策树的构建原理）。

Decision Tree 在sklearn中的实现

决策树其实很简单，就是将一条数据中的每一个feature作为一个node，然后根据不同的条件分成不同的分支branch，每一个branch还有一个node，这个node可能还是feature也可能是leave（target）。具体一个决策树种有多少个node，有多少个leaves，咱们后面再说，这设计到了很多概率和信息熵方面的知识。咱们现在只需要知道一个大致的概念就是，决策树中的node是咱们的feature，leaves是咱们的target，branch是咱们的split conditions 就行了，具体其中的细节咱们暂时不需要了解，咱们这里的重点是如何用sklearn这个框架搭建出咱们的决策树模型。咱们这里先直接用一个代码示例来展示，然后再来解释他的过程。

from sklearn.tree import DecisionTreeRegressor#1.Definemelb_model = DecisionTreeRegressor()#2. fitmelb_model.fit(X,y)#3. predictmelb_house_prediction = melb_model.predict(X)#4.Mean Absolute Error (MAE)from sklearn.metrics import mean_absolute_errormean_absolute_error(y,melb_house_prediction)

上面是一个最简单的用sklearn建模一个decision tree的实例了，其总共包括：实例化决策树，训练决策树，预测，和验证四个步骤。当然在实际中会有很多的细节部分需要处理，例如第一步实例化的过程有可能会有很多的参数需要调整，如max_depth, min_sample_split等等这些参数，这些都需要根据咱们后面的模型表现来不断的调整； 其次在验证阶段也是的，咱们得把咱们的数据集分割成training dataset和validation dataset, 这里面也包括了很多技术来分割和random的；具体这些细节，咱们在后面遇到了再说哈。对于绝大部分的决策树模型，咱们都可以用上面的4个步骤来创建。既然说到这里了，咱现在也就简单的数据分割的api也给大家展示一下。

from sklearn.model_selection import train_test_splittrain_X, validate_X, train_y, validate_y = train_test_split(X,y,random_state=0)

上面是一个最简单的数据分割代码，默认是将（X，y）按照80%，20%比例分割，分别用于training和validation；当然啦，这里的分割比例也可以自行通过train_test_split函数的参数进行调节。random_state是当做random generator的seed，是将数据打乱后在分割。既然如何用sklearn建模决策树的内容讲了，咱们也顺带把random forest 随机森林模型在sklearn中如何建模的内容也说了把，毕竟random forest是基于decision tree的，而且random forest建模过程跟decision tree几乎是一模一样的，见下面代码展示如何创建random forest的，

from sklearn.model_selection import train_test_splittrain_X, val_X, train_y, val_y = train_test_split(X, y, random_state = 1)from sklearn.ensemble import RandomForestRegressor#definemelb_model = RandomForestRegressor(random_state=1)#trainingmelb_model.fit(train_X,train_y)#predictionpredictions = melb_model.predict(val_X)#validationfrom sklearn.metrics import mean_absolute_errormae = mean_absolute_error(val_y, predictions)

在解释上面的代码之前，咱们先来说说什么是random forest。大家想一想，既然前面咱们创建了一颗决策树，那咱们就自然而然的可以建造许多的决策树然后就可以创建一个森林啦，就叫做随机森林。用random forest预测的时候，咱们就把test data放进这个随机森林的每一颗树里面去预测，最后咱们取预测的平均值。就是怎么简单so easy。咱们现在就理解到这个程度就够了，实际的底层的创建原理，等咱们把decision tree的创建原理弄懂了以后大家就知道了。咱们看上面的代码，它跟decision tree只有几个小区别，第一个就是random forest是一个ensemble，相当于把许多小decision tree模型打包成了一个ensemble；第二个就是他的实例化名称是RandomForestRegressor。其他都差不多，大家在这里不需要死记硬背这些代码，关键要了解这里面的每一步有什么作用，为什么需要这些步骤就行了。再一个就是一定得对decision tree和random forest的结构从上层有一个大致的了解，对于他们的底层细节结构，咱们可以看看下面的一部分。

决策树的创建原理

由于在博客中画图不方便，我特地花了一张解释decision tree创建原理的一张图，然后这部分内容主要是围绕着这张图作为一个解释。这里面还涉及到一些数学计算和概率的一些内容。所以这幅图的信息量还是蛮大的。其实说白了，这里讲决策树的创建原理实际上就是解释如何每一步从n个features中选择一个特点的feature作为node，具体是根据一个什么指标来选择feature作为node的。好了废话不多说，直接上图啦

先来解释一下一个简单的概念，就是entropy, 中文咱们可以称作是信息熵。它是一种衡量信息量的值，具体这个值是怎么的计算的咱们可以看上面的图片，我上面的图片还配备了一个简单的数字实例给演示。在正式解释之前咱们先来问一问咱们自己一个最基本的问题，那就是decision tree到底是来干什么的？？？decision tree最本质的功能是根据feature的条件来最终分离出不同的信息（这里的信息咱们可以理解为target）。因而这里信息熵咱们可以理解为这一组数据可以被分辨（分离的）能力，信息熵越小，越容易被分辨，信息熵越大（1），就越难被分辨出来。Information Gain是父节点的信息熵跟他子节点信息熵之差， I（A）的值越大，则说明从这个节点获取的信息就越大，那么就选这个获取信息量越大的feature。这个过程就是决策树中选择feature的方法。如果上面的理解了，咱们也就顺理成章的理解了是如何构建decision tree和random forest的了，他们之间还有一个小区别是，decision tree每一个都要算每一个feature的Information Gain然后才来选择Information Gain最大的那个feature；而random forest创建它的每一颗tree的过程则是每一步都是随机选几个features来就算Information Gain,然后选最大的，从而确保了tree的多样性。

一、决策树（Decision Tree）

决策树是一种非参数有监督的机器学习方法，可以用于解决回归问题和分类问题。通过学习已有的数据，计算得出一系列推断规则来预测目标变量的值，并用类似流程图的形式进行展示。决策树模型可以进行可视化，具有很强的可解释性，算法容易理解，以决策树为基础的各种集成算法在很多领域都有广泛的应用。

熵的概念最早起源于物理学，用于度量一个热力学系统的无序程度。在信息论里面，信息熵代表着一个事件或一个变量等所含有的信息量。 在信息世界，熵越高，则能传输越多的信息，熵越低，则意味着传输的信息越少。

发生概率低的事件比发生概率高的事件具有更大的不确定性，需要更多的信息去描述他们，信息熵更高。

我们可以用计算事件发生的概率来计算事件的信息，又称“香农信息”（ Shannon Information ）。一个离散事件x的信息可以表示为：
h(x) = -log(p(x))
p() 代表事件x发生的概率， log() 为以二为底的对数函数，即一个事件的信息量就是这个事件发生的概率的负对数。选择以二为底的对数函数代表计算信息的单位是二进制。因为概率p(x)小于1，所以负号就保证了信息熵永远不为负数。当事件的概率为1时，也就是当某事件百分之百发生时，信息为0。

熵（ entropy ），又称“香农熵”（ Shannon entropy ），表示一个随机变量的分布所需要的平均比特数。一个随机变量的信息熵可以表示为：
H(x) = -sum(each k in K p(k)log(p(k)))
K表示变量x所可能具有的所有状态（所有事件），将发生特定事件的概率和该事件的信息相乘，最后加和，即可得到该变量的信息熵。可以理解为，信息熵就是平均而言发生一个事件我们得到的信息量大小。所以数学上，信息熵其实是事件信息量的期望。

当组成该随机变量的一个事件的概率为1时信息熵最小，为0， 即该事件必然发生。当组成该随机变量的所有事件发生的概率相等时，信息熵最大，即完全不能判断那一个事件更容易发生，不确定性最大。

当一个事件主导时，比如偏态分布（ Skewed Probability Distribution ），不确定性减小，信息熵较低（low entropy）；当所有事件发生概率相同时，比如均衡分布（ Balanced Probability Distribution ），不确定性极大，信息熵较高（high entropy）。

由以上的香农信息公式可知，信息熵主要有三条性质：
- 单调性 。发生概率越高的事件，其所携带的信息熵越低。比如一个真理的不确定性是极低的，那么它所携带的信息熵就极低。
- 非负性 。信息熵不能为负。单纯从逻辑层面理解，如果得知了某个信息后，却增加了不确定性，这也是不合逻辑的。
- 可加性 。即多随机事件同时发生存在的总不确定性的量度是可以表示为各事件不确定性的量度的和。

若两事件A和B同时发生，两个事件相互独立。 p(X=A,Y=B) = p(X = A)*p(Y=B) , 那么信息熵为 H(A,B) = H(A) + H(B) 。但若两事件不相互独立，那么 H(A,B) = H(A) + H(B) - I(A,B) 。其中 I(A,B) 是互信息（ mutual information，MI ），即一个随机变量包含另一个随机变量信息量的度量。即已知X的情况下，Y的分布是否会改变。

可以理解为，两个随机变量的互信息度量了两个变量间相互依赖的程度。X 和 Y的互信息可以表示为：
I(X;Y) = H(X) - H(X|Y)
H(X)是X的信息熵，H(X|Y)是已知Y的情况下，X的信息熵。结果的单位是比特。
简单来说，互信息的性质为：
- I(X;Y)>=0 互信息永远不可能为负
- H(X) - H(X|Y) = I(X;Y) = I (Y;X) = H(Y) - H(Y|X) 互信息是对称的
-当X，Y独立的时候， I(X;Y) = 0 互信息值越大，两变量相关性越强。
-当X，Y知道一个就能推断另一个的时候， I(X;Y) = H(Y) = H(X)

在数据科学中，互信息常用于特征筛选。在通信系统中互信息也应用广泛。在一个点到点的通信系统中，发送信号为X，通过信道后，接收端接收到的信号为Y，那么信息通过信道传递的信息量就是互信息 I(X,Y) 。根据这个概念，香农推导出信道容量（即临界通信传输速率的值）。

信息增益（ Information Gain ）是用来按照一定规则划分数据集后，衡量信息熵减少量的指数。

那数据集的信息熵又是怎么计算的呢？比如一个常见的0,1二分类问题，我们可以计算它的熵为：
Entropy = -(p(0) * log(P(0)) + p(1)\ * log(P(1)))
当该数据集为50/50的数据集时，它的信息熵是最大的（1bit）。而10/90的数据集将会大大减少结果的不确定性，减小数据集的信息熵（约为0.469bit）。

这样来说，信息熵可以用来表示数据集的纯度（ purity ）。信息熵为0就表示该数据集只含有一个类别，纯度最高。而较高的信息熵则代表较为平衡的数据集和较低的纯度。

信息增益是提供了一种可以使用信息熵计算数据集经过一定的规则（比如决策树中的一系列规则）进行数据集分割后信息熵的变化的方法。
IG(S,a) = H(S) - H(S|a)
其中，H(s) 是原数据集S的信息熵（在做任何改变之前），H(S|a)是经过变量a的一定分割规则。所以信息增益描述的是数据集S变换后所节省的比特数。

信息增益可以用做决策树的分枝判断方法。比如最常用CART树（ Classification and Regression Tree ）中的分枝方法，只要在python中设置参数 criterion 为 “entropy” 即可。

信息增益也可以用作建模前的特征筛选。在这种场景下，信息增益和互信息表达的含义相同，会被用来计算两变量之间的独立性。比如scikit-learn 中的函数 mutual_info_classiif()

信息增益在面对类别较少的离散数据时效果较好，但是面对取值较多的特征时效果会有 偏向性 。因为当特征的取值较多时，根据此特征划分得到的子集纯度有更大的可能性会更高(对比与取值较少的特征)，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益比较偏向取值较多的特征。举一个极端的例子来说，如果一个特征为身份证号，当把每一个身份证号不同的样本都分到不同的子节点时，熵会变为0，意味着信息增益最大，从而该特征会被算法选择。但这种分法显然没有任何实际意义。

这种时候，信息增益率就起到了很重要的作用。
gR(D,A)=g(D,A)/HA(D)
HA(D) 又叫做特征A的内部信息，HA(D)其实像是一个衡量以特征AA的不同取值将数据集D分类后的不确定性的度量。如果特征A的取值越多，那么不确定性通常会更大，那么HA(D)的值也会越大，而1/HA(D)的值也会越小。这相当于是在信息增益的基础上乘上了一个惩罚系数。即 gR(D,A)=g(D,A)∗惩罚系数 。

在CART算法中，基尼不纯度表示一个随机选中的样本被分错类别的可能性，即这个样本被选中的概率乘以它被分错的概率。当一个节点中所有样本均为一种时（没有被分错的样本），基尼不纯度达到最低值0。

举例来说，如果有绿色和蓝色两类数据点，各占一半（蓝色50%，绿色50%）。那么我们随机分类，有以下四种情况：
-分为蓝色，但实际上是绿色（❌），概率25%
-分为蓝色，实际上也是蓝色（✔️），概率25%
-分为绿色，实际上也是绿色（✔️），概率25%
-分为绿色，但实际上是蓝色（❌），概率25%
那么将任意一个数据点分错的概率为25%+25% = 50%。基尼不纯度为0.5。

在特征选择中，我们可以选择加入后使数据不纯度减少最多的特征。

噪音数据简单来说就是会对模型造成误导的数据。分为类别噪声（ class noise 或 label noise ）和 变量噪声（ attribute noise ）。类别噪声指的的是被错误标记的错误数据，比如两个相同的样本具有不同的标签等情况。变量噪声指的是有问题的变量，比如缺失值、异常值和无关值等。

决策树其实是一种图结构，由节点和边构成。
-根节点：只有出边没有入边。包含样本全集，表示一个对样本最初的判断。
-内部节点：一个入边多个出边。表示一个特征或是属性。每个内部节点都是一个判断条件，包含数据集中从根节点到该节点所有满足条件的数据的集合。
-叶节点：一个入边无出边。表示一个类，对应于决策结果。

决策树的生成主要分为三个步骤：
1. 节点的分裂 ：当一个节点不够纯（单一分类占比不够大或者说信息熵较大）时，则选择将这一节点进行分裂。
2. 决策边界的确定 ：选择正确的决策边界（ Decision Boundary ），使分出的节点尽量纯，信息增益（熵减少的值）尽可能大。
3. 重复及停止生长 ：重复1，2步骤，直到纯度为0或树达到最大深度。为避免过拟合，决策树算法一般需要制定树分裂的最大深度。到达这一深度后，即使熵不等于0，树也不会继续进行分裂。

下面以超级知名的鸢尾花数据集举例来说明。
这个数据集含有四个特征：花瓣的长度（ petal length ）、花瓣的宽度( petal width )、花萼的长度( sepal length )和花萼的宽度( sepal width )。预测目标是鸢尾花的种类 iris setosa, iris versicolor 和 iris virginica 。

建立决策树模型的目标是根据特征尽可能正确地将样本划分到三个不同的“阵营”中。

根结点的选择基于全部数据集，使用了贪婪算法：遍历所有的特征，选择可以使信息熵降到最低、基尼不纯度最低的特征。

如上图，根节点的决策边界为' petal width = 0.8cm '。那么这个决策边界是怎么决定的呢？
-遍历所有可能的决策边界（需要注意的是，所有可能的决策边界代表的是该子集中该特征所有的值，不是以固定增幅遍历一个区间内的所有值！那样很没有必要的～）
-计算新建的两个子集的基尼不纯度。
-选择可以使新的子集达到最小基尼不纯度的分割阈值。这个“最小”可以指两个子集的基尼不纯度的和或平均值。

ID3是最早提出的决策树算法。ID3算法的核心是在决策树各个节点上根据 信息增益 来选择进行划分的特征，然后递归地构建决策树。
- 缺点 ：
（1）没有剪枝
（2）只能用于处理离散特征
（3）采用信息增益作为选择最优划分特征的标准，然而信息增益会偏向那些取值较多的特征(例如，如果存在唯一标识属性身份证号，则ID3会选择它作为分裂属性，这样虽然使得划分充分纯净，但这种划分对分类几乎毫无用处。)

C4.5 与ID3相似，但对ID3进行了改进：
-引入“悲观剪枝”策略进行后剪枝
-信息增益率作为划分标准
-将连续特征离散化，假设 n 个样本的连续特征 A 有 m 个取值，C4.5 将其排序并取相邻两样本值的平均数共 m-1 个划分点，分别计算以该划分点作为二元分类点时的信息增益，并选择信息增益最大的点作为该连续特征的二元离散分类点；
-可以处理缺失值

对于缺失值的处理可以分为两个子问题：
（1）在特征值缺失的情况下进行划分特征的选择？（即如何计算特征的信息增益率）
C4.5 中对于具有缺失值特征，用没有缺失的样本子集所占比重来折算；
（2）选定该划分特征，对于缺失该特征值的样本如何处理？（即到底把这个样本划分到哪个结点里）
C4.5 的做法是将样本同时划分到所有子节点，不过要调整样本的权重值，其实也就是以不同概率划分到不同节点中。

（1）剪枝策略可以再优化；
（2）C4.5 用的是多叉树，用二叉树效率更高；
（3）C4.5 只能用于分类；
（4）C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；
（5）C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。

可以用于分类，也可以用于回归问题。CART 算法使用了基尼系数取代了信息熵模型，计算复杂度更低。

CART 包含的基本过程有 分裂，剪枝和树选择 。
分裂 ：分裂过程是一个二叉递归划分过程，其输入和预测特征既可以是连续型的也可以是离散型的，CART 没有停止准则，会一直生长下去；
剪枝 ：采用“代价复杂度”剪枝，从最大树开始，每次选择训练数据熵对整体性能贡献最小的那个分裂节点作为下一个剪枝对象，直到只剩下根节点。CART 会产生一系列嵌套的剪枝树，需要从中选出一颗最优的决策树；
树选择 ：用单独的测试集评估每棵剪枝树的预测性能（也可以用交叉验证）。

（1）C4.5 为多叉树，运算速度慢，CART 为二叉树，运算速度快；
（2）C4.5 只能分类，CART 既可以分类也可以回归；
（3）CART 使用 Gini 系数作为变量的不纯度量，减少了大量的对数运算；
（4）CART 采用代理测试来估计缺失值，而 C4.5 以不同概率划分到不同节点中；
（5）CART 采用“基于代价复杂度剪枝”方法进行剪枝，而 C4.5 采用悲观剪枝方法。

（1）决策树易于理解和解释，可以可视化分析，容易提取出规则
（2）可以同时处理分类型和数值型数据
（3）可以处理缺失值
（4）运行速度比较快（使用Gini的快于使用信息熵，因为信息熵算法有log）

（1）容易发生过拟合（集成算法如随机森林可以很大程度上减少过拟合）
（2）容易忽略数据集中属性的相互关联；
（3）对于那些各类别样本数量不一致的数据，在决策树中，进行属性划分时，不同的判定准则会带来不同的属性选择倾向。

写在后面：这个专辑主要是本小白在机器学习算法学习过程中的一些总结笔记和心得，如有不对之处还请各位大神多多指正！（关于决策树的剪枝还有很多没有搞懂，之后弄明白了会再单独出一篇总结哒）

参考资料链接：
1.
2.
3.
4.
5.
6.
7.
8.

二、决策树(decisionTree)

决策树(decisionTree)是一种基本的分类和回归方法。此文仅讨论用于分类方法的决策树。

决策树的学习通常分为3步：

决策树的学习的思想主要源于

定义决策树 ：

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directed edge)组成。结点又分为内部结点(internal node)和叶结点(leaf node)。内部结点表示一个特征或属性，叶结点表示一个类。
形如：

其中，圆表示内部结点，方框表示叶结点。

if-then规则，简单来说就是 ：

举例：对于一个苹果，外表是红色的是红苹果，外表是绿色的是青苹果。可以表示为：

if-then规则集合具有一个重要的性质：

这就是说每一个实例都被一条路径或规则覆盖，并且只被一条路径或规则覆盖。这里所谓的覆盖是指实例的特征与路径上的特征一致，或实例满足规则的条件。

给定数据集：

其中， 为输入实例（特征向量），含有 个特征， 为类标记， , 为样本容量。

目标 ：
根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确分类。

特征选择在于选取对训练数据具有分类能力的特征，这样可以提高决策树学习的效率。

如果我们利用某一个特征进行分类的结果与随机分类的结果没什么很大的差别的话，则称这个特征没有分类能力。

那么问题来了，怎么选择特征呢？

通常特征选择的准则是

下面通过例子来说明一下。

目标 ：
希望通过所给的训练集数据，学习一个贷款申请的决策树。当新的客户提出贷款申请的时候，根据申请人的特征利用决策树决定是否批准贷款申请。

可见这里共有4个特征可供选择。用特征选择的准则是 。接下来介绍 。

：
熵是表示随机变量不确定性的度量。

设 是一个取有限个值的随机变量，其概率分布为

则随机变量 的熵定义为

若 ，则定义 。通常对数取以2为底，或是以 为底，熵的单位分布为比特（bit）或是纳特（nat）。
由上式可知，熵只依赖 的分布，而已 的值无关，则 的熵还可记作 ，即

则从定义可知

当随机变量只取2个值的时候，例如 时， 的分布为

熵为

熵随概率变化的曲线为

当 或 时 ，随机变量完全没有不确定性，当 时 ，熵取值最大，随机变量不确定性最大。

设随机变量 ，其联合概率分布

条件熵 表示在已知随机变量 的条件下随机变量 的不确定性。随机变量 给定条件下随机变量 的条件熵(conditional entropy)，定义为 给定条件下 的条件概率分布的熵对 的数学期望

信息增益
特征 对训练集 的信息增益

根据信息增益准则的特征选择方法：对训练集 ，计算其每个特征的信息增益，并比较大小，选择信息增益最大的特征。

前期定义各个量：

信息增益的算法
输入：训练集 和特征 ；
输出：特征 对训练集 的信息增益

回看刚才的例子，

解 ：

这一次我很无聊的想用一下.csv文件类型。

所以训练数据集部分如下，我存在一个loan.csv文件里了。对.csv文件的各种处理一般由python的pandas模块完成。

第一步，导入相关模块

第二步，读入数据

若是使用jupyter，可以即刻查看一下数据，和数据标签。

可以看出，除了'ID'之外前4个标签 'age', 'work', 'own house', 'Credit conditions'为我们一直在说的特征 ，而最后一个标签'label'是我们所说的类 ，所以要处理一下这些标签，

第三步，计算训练集 的熵 ：

这里会用到pandas的一个统计数据的功能， groupby(by = [列]).groups ，将数据统计成字典的形式，这么说比较抽象，看下图，将我们用pandas读入的data，分为2类， ， Index 表示索引，即第0，1，4，5，6，14（python计数从0开始）个数据的 ，第2，3，7，8，9，10，11，12，13个数据的 .

那么计算训练集 的熵

第四步，计算特征 对数据集 的条件熵

第五步 ，计算信息增益

输入：训练集 和特征 和阈值 ；
输出：决策树
(1) 中所有实例都属于同一类 ，则 为单结点树，并将类 作为该结点的类标记，返回 ；
(2) 若 ，则 为单结点树，并将 中实例数最大的类 作为该结点的类标记，返回 ；
(3)否则，按照上述信息增益的算法，计算 中各个特征对 的信息增益，选择信息增益最大的特征 ；
(4)如果特征 的信息增益小于阈值 ，将置 为单结点树，并将 中实例数最大的类 作为该结点的类标记，返回 ；
(5)否则，对 的每一个可能值 ，依 将 分割为若干非空子集 ，将 中实例数最大的类 作为该结点的类标记，构建子结点，由结点及其子结点构成树 ，返回 ；
(6)对第 个子结点，以 为训练集，以 为特征集，递归的调用步骤(1)~步骤(5)，得到子树 ，返回 。

对上述表的训练集数据，利用ID3算法建立决策树。

解 ：

第一次迭代 ：

【特征：有自己的房子】将数据集 划分为2个子集 （有自己的房子）和 （没有自己的房子），观察一下 和 ：

：

由于 所有实例都属于同一类 ，所以它是一个叶结点，结点的类标记为“是”。

：

对于 则需从特征 中选择新的特征。

第二次迭代 ：

将 看作新的数据集 。【特征：有工作】有2个可能值，划分为2个子集 （有工作）和 （没有工作），观察一下 和 ：

：

由于 所有实例都属于同一类 ，所以它是一个叶结点，结点的类标记为“是”。

：

三、ML - 决策树(decision tree)

机器学习中分类和预测算法的评估：

判定树是一个类似于流程图的树结构：其中，每个内部结点表示在一个 属性上的测试 ，每个分支代表一个 属性输出 ，而每个树叶结点代表 类或类分布 。树的最顶层是根结点。
机器学习中分类方法中的一个重要算法

信息和抽象，如何度量？

1948年，香农提出了 ”信息熵(entropy)“的概念

一条信息的信息量大小和它的不确定性有直接的关系，要搞清楚一件非常非常不确定的事情，或者

是我们一无所知的事情，需要了解大量信息==> 信息量的度量就等于不确定性的多少

例子：猜世界杯冠军，假如一无所知，猜多少次？

每个队夺冠的几率不是相等的

比特(bit)来衡量信息的多少

变量的不确定性越大，熵也就越大

3.1 决策树归纳算法 （ ID3 ）

1970-1980， J.Ross. Quinlan, ID3算法

选择属性（A为age时）判断结点

信息获取量(Information Gain) ：
Gain(A) = Info(D) - Infor_A(D)
Gain(A) =按yes/no分的熵 - 按A属性分类的熵

通过A来作为节点分类获取了多少信息

类似
Gain(income) = 0.029
Gain(student) = 0.151
Gain(credit_rating)=0.048
所以，选择age作为第一个根节点

重复。。。

算法：

*其他算法：

C4.5 : Quinlan

Classification and Regression Trees (CART): (L. Breiman, J. Friedman, R. Olshen, C. Stone)

共同点：都是贪心算法，自上而下(Top-down approach)

区别：属性选择度量方法不同： C4.5 （gain ratio), CART(gini index), ID3 (Information Gain)

先剪枝

后剪枝

直观，便于理解，小规模数据集有效

处理连续变量不好（离散化，阈值选择对结果影响大）

类别较多时，错误增加的比较快

可规模性一般

1. Python

2. Python机器学习的库： scikit-learn

2.1： 特性：

简单高效的数据挖掘和机器学习分析

对所有用户开放，根据不同需求高度可重用性

基于Numpy, SciPy和matplotlib

开源，商用级别：获得 BSD许可

2.2 覆盖问题领域：

分类（classification), 回归（regression), 聚类（clustering), 降维(dimensionality reduction)

模型选择(model selection), 预处理(preprocessing)

3. 使用用scikit-learn

安装scikit-learn: pip, easy_install, windows installer

安装必要package：numpy， SciPy和matplotlib， 可使用 Anaconda (包含numpy, scipy等科学计算常用package）

4. 例子：

文档：

安装 Graphviz：
配置环境变量
转化dot文件至pdf可视化决策树：dot -Tpdf iris.dot -o outpu.pdf