决策树优缺点
优点：决策过程更接近人的思维， 因此模型更容易解释；能够更清楚地使用图形化描述模型；速度快；可以处理连续性和离散型数据；不需要任何领域知识和参数假设；适合高维数据。缺点：对于各特征样本量不均衡的数据， 信息增益更偏向于那些数值更多的特征；不支持在线学习；容易过拟合；一般来说， 决策学习方法的准确率不如其他模型。应用决策树决策方法必须具备以下条件：（1）具有决策者期望达到的明确目标。（2）存在决策者可以选择的两个以上的可行的备选方案。（3）存在决策者无法控制的两个以上不确定因素。（4）不同方案在不同因素下的收益或损失可以计算出来。（5）决策者可以估计不确定因素发生的概率。
决策树基本概念及算法优缺点
分类决策树模型是一种描述对实例进行分类的树形结构. 决策树由结点和有向边组成. 结点有两种类型: 内部结点和叶节点. 内部节点表示一个特征或属性, 叶节点表示一个类. 决策树(Decision Tree),又称为判定树, 是一种以树结构(包括二叉树和多叉树)形式表达的预测分析模型. 分类树--对离散变量做决策树 回归树--对连续变量做决策树 优点: (1)速度快: 计算量相对较小, 且容易转化成分类规则. 只要沿着树根向下一直走到叶, 沿途的分裂条件就能够唯一确定一条分类的谓词. (2)准确性高: 挖掘出来的分类规则准确性高, 便于理解, 决策树可以清晰的显示哪些字段比较重要, 即可以生成可以理解的规则. (3)可以处理连续和种类字段 (4)不需要任何领域知识和参数假设 (5)适合高维数据 缺点: (1)对于各类别样本数量不一致的数据, 信息增益偏向于那些更多数值的特征 (2)容易过拟合 (3)忽略属性之间的相关性 若一事假有k种结果, 对应概率为 , 则此事件发生后所得到的信息量I为: 给定包含关于某个目标概念的正反样例的样例集S, 那么S相对这个布尔型分类的熵为: 其中 代表正样例, 代表反样例 假设随机变量(X,Y), 其联合分布概率为P(X=xi,Y=yi)=Pij, i=1,2,...,n;j=1,2,..,m 则条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性, 其定义为X在给定条件下Y的条件概率分布的熵对X的数学期望 在Hunt算法中, 通过递归的方式建立决策树. 使用信息增益, 选择 最高信息增益 的属性作为当前节点的测试属性 ID3( Examples,Target_attribute,Attributes ) Examples 即训练样例集. Target_attribute 是这棵树要预测的目标属性. Attributes 是除目标属性外供学习到的决策树测试的属性列表. 返回能正确分类给定 Examples 的决策树. class sklearn.tree.DecisionTreeClassifier(criterion='gini', splitter='best', max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, class_weight=None, presort=False) 限制决策树层数为4的DecisionTreeClassifier实例 This plot compares the decision surfaces learned by a dcision tree classifier(first column), by a random forest classifier(second column), by an extra-trees classifier(third column) and by an AdaBoost classifier(fouth column). Output: A comparison of a several classifiers in scikit-learn on synthetic datasets. The point of this examples is to illustrate the nature of decision boundaries of different classifiers. Particularly in high-dimensional spaces, data can more easily be separated linearly and the simplicity of classifiers such as naive Bayes and linear SVMs might lead to better generalization than is achieved by other classifiers. This example fits an AdaBoost decisin stump on a non-linearly separable classification dataset composed of two "Gaussian quantiles" clusters and plots the decision boundary and decision scores. Output:
决策树（Decision Tree）
决策树（Decision Tree）是一种基本的分类与回归方法，其模型呈树状结构，在分类问题中，表示基于特征对实例进行分类的过程。本质上，决策树模型就是一个定义在特征空间与类空间上的条件概率分布。决策树学习通常包括三个步骤： 特征选择 、 决策树的生成 和 决策树的修剪 。 分类决策树模型是一种描述对实例进行分类的树形结构，决策树由节点（node）和有向边（directed edge）组成。节点有两种类型：内部节点（internal node）和叶节点（leaf node）。内部节点表示一个特征或属性，叶节点表示一个类。 利用决策树进行分类，从根节点开始，对实例的某一特征进行测试，根据测试结果将实例分配到其子节点；这时，每一个子节点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶节点。最后将实例分到叶节点的类中。 决策树是给定特征条件下类的条件概率分布，这一条件概率分布定义在特征区间的一个划分（partiton）上。将特征空间划分为互不相交的单元（cell）或区域（region），并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应划分中的一个单元，决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。假设X为表示特征的随机变量，Y为表示类的随机变量，那么这个条件概率分布可以表示成P(Y|X)。X取值于给定划分下单元的集合，Y取值于类的集合，各叶节点（单元）上的条件概率往往偏向于某一个类，即属于某一类的概率较大，决策树分类时将该节点的实例分到条件概率大的那一类去。也就以为着决策树学习的过程其实也就是由数据集估计条件概率模型的过程，这些基于特征区间划分的类的条件概率模型由无穷多个，在进行选择时，不仅要考虑模型的拟合能力还要考虑其泛化能力。 为了使模型兼顾模型的拟合和泛化能力，决策树学习使用正则化的极大似然函数来作为损失函数，以最小化损失函数为目标，寻找最优的模型。显然从所有可能的决策树中选取最优决策树是NP完全问题，所以在实际中通常采用启发式的方法，近似求解这一最优化问题： 通过递归的选择最优特征，根据该特征对训练数据进行划分直到使得各个子数据集有一个最好的分类，最终生成特征树 。当然，这样得到的决策树实际上是次最优（sub-optimal）的。进一步的，由于决策树的算法特性，为了防止模型过拟合，需要对已生成的决策树自下而上进行剪枝，将树变得更简单，提升模型的泛化能力。具体来说，就是去掉过于细分的叶节点，使其退回到父节点，甚至更高的节点，然后将父节点或更高的节点改为新的叶节点。如果数据集的特征较多，也可以在进行决策树学习之前，对数据集进行特征筛选。 由于决策树是一个条件概率分布，所以深浅不同的决策树对应着不同复杂度的概率模型，决策树的生成对应模型的局部选择，决策树的剪枝对应着模型的全局选择。 熵（Entropy） 的概念最早起源于物理学，最初物理学家用这个概念度量一个热力学系统的无序程度。在1948年， 克劳德·艾尔伍德·香农 将热力学的熵，引入到 信息论 ，因此它又被称为 香农熵 。在信息论中，熵是对不确定性的量度，在一条信息的熵越高则能传输越多的信息，反之，则意味着传输的信息越少。 如果有一枚理想的硬币，其出现正面和反面的机会相等，则抛硬币事件的熵等于其能够达到的最大值。我们无法知道下一个硬币抛掷的结果是什么，因此每一次抛硬币都是不可预测的。因此，使用一枚正常硬币进行若干次抛掷，这个事件的熵是一 比特 ，因为结果不外乎两个——正面或者反面，可以表示为 0, 1 编码，而且两个结果彼此之间相互独立。若进行 n 次 独立实验 ，则熵为 n ，因为可以用长度为 n 的比特流表示。但是如果一枚硬币的两面完全相同，那个这个系列抛硬币事件的熵等于零，因为 结果能被准确预测 。现实世界里，我们收集到的数据的熵介于上面两种情况之间。 另一个稍微复杂的例子是假设一个 随机变量 X ，取三种可能值 ，概率分别为 ，那么编码平均比特长度是： 。其熵为 。因此熵实际是对随机变量的比特量和顺次发生概率相乘再总和的 数学期望 。 依据玻尔兹曼H定理，香农把随机变量X的熵 定义为： 其中 是随机变量X的信息量，当随机变量取自有限样本时，熵可以表示为： 若 ，则定义 。 同理可以定义条件熵 : 很容易看出，条件熵（conditional entropy） 就是X给定条件下Y的条件概率分布的熵对X的数学期望。当熵和条件熵中的概率有极大似然估计得到时，所对应的熵和条件熵分别称为检验熵（empirical entropy）和经验条件熵（empirical conditional entropy）. 熵越大，随机变量的不确定性就越大，从定义可以验证: 当底数 时，熵的单位是 ；当 时，熵的单位是 ;而当 时，熵的单位是 . 如英语有26个字母，假如每个字母在文章中出现的次数平均的话，每个字母的信息量 为： 同理常用汉字2500有个，假设每个汉字在文章中出现的次数平均的话，每个汉字的信息量 为： 事实上每个字母和汉字在文章中出现的次数并不平均，少见字母和罕见汉字具有相对较高的信息量，显然，由期望的定义，熵是整个消息系统的平均消息量。 熵可以用来表示数据集的不确定性，熵越大，则数据集的不确定性越大。因此使用 划分前后数据集熵的差值 量度使用当前特征对于数据集进行划分的效果（类似于深度学习的代价函数）。对于待划分的数据集 ，其划分前的数据集的熵 是一定的，但是划分之后的熵 是不定的， 越小说明使用此特征划分得到的子集的不确定性越小（也就是纯度越高）。因此 越大，说明使用当前特征划分数据集 时，纯度上升的更快。而我们在构建最优的决策树的时候总希望能更快速到达纯度更高的数据子集，这一点可以参考优化算法中的梯度下降算法，每一步沿着负梯度方法最小化损失函数的原因就是负梯度方向是函数值减小最快的方向。同理：在决策树构建的过程中我们总是希望集合往最快到达纯度更高的子集合方向发展，因此我们总是选择使得信息增益最大的特征来划分当前数据集 。 显然这种划分方式是存在弊端的，按信息增益准则的划分方式，当数据集的某个特征B取值较多时，依此特征进行划分更容易得到纯度更高的数据子集，使得 偏小，信息增益会偏大，最终导致信息增益偏向取值较多的特征。 设 是 个数据样本的集合，假定类别属性具有 个不同的值： ,设 是类 中的样本数。对于一个给定样本，它的信息熵为： 其中， 是任意样本属于 的概率，一般可以用 估计。 设一个属性A具有 个不同的值 ，利用属性A将集合 划分为 个子集 ，其中 包含了集合 中属性 取 值的样本。若选择属性A为测试属性，则这些子集就是从集合 的节点生长出来的新的叶节点。设 是子集 中类别为 的样本数，则根据属性A划分样本的信息熵为： 其中 , 是子集 中类别为 的样本的概率。最后，用属性A划分样本子集 后所得的 信息增益(Gain) 为： 即，属性A的信息增益=划分前数据的熵-按属性A划分后数据子集的熵。 信息增益（information gain）又称为互信息（matual information）表示得知特征X的信息而使得类Y的信息的不确定性减少的程度 。信息增益显然 越小， 的值越大，说明选择测试属性A对于分类提供的信息越多，选择A之后对分类的不确定程度越小。 经典算法 ID3 使用的信息增益特征选择准则会使得划分更偏相遇取值更多的特征，为了避免这种情况。ID3的提出者 J.Ross Quinlan 提出了 C4.5 ,它在ID3的基础上将特征选择准则由 信息增益 改为了 信息增益率 。在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大（类似于正则化）。这个惩罚参数就是 分裂信息度量 的倒数 。 不同于 ID3 和 C4.5 , CART 使用基尼不纯度来作为特征选择准则。基尼不纯度也叫基尼指数 , 表示在样本集合中一个随机选中的样本被分错的概率 则基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率。Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。 样本集合的基尼指数： 样本集合 有m个类别， 表示第 个类别的样本数量,则 的Gini指数为： 基于某个特征划分样本集合S之后的基尼指数： CART是一个二叉树，也就是当使用某个特征划分样本集合后，得到两个集合：a.等于给定的特征值的样本集合 ；b.不等于给定特征值的样本集合 。实质上是对拥有多个取值的特征的二值处理。 对于上述的每一种划分，都可以计算出基于划分特=某个特征值将样本集合划分为两个子集的纯度： 因而对于一个具有多个取值（超过2个）的特征，需要计算以每个取值为划分点，对样本集合划分后子集的纯度 ( 表示特征 的可能取值)然后从所有的划分可能 中找出Gini指数最小的划分，这个划分的划分点，就是使用特征 对样本集合 进行划分的最佳划分点。 参考文献 ： 决策树--信息增益，信息增益比，Geni指数的理解 【机器学习】深入理解--信息熵（Information Entropy） 统计学习方法 （李航） 为了便于理解，利用以下数据集分别使用三种方法进行分类： 在进行具体分析之前，考虑到收入是数值类型，要使用决策树算法，需要先对该属性进行离散化。 在机器学习算法中，一些分类算法（ID3、Apriori等）要求数据是分类属性形式，因此在处理分类问题时经常需要将一些连续属性变换为分类属性。一般来说，连续属性的离散化都是通过在数据集的值域内设定若干个离散的划分点，将值域划分为若干区间，然后用不同的符号或整数数值代表落在每个子区间中的数据值。所以，离散化最核心的两个问题是：如何确定分类数以及如何将连续属性映射到这些分类值。常用的离散化方法有 等宽法 ， 等频法 以及 一维聚类法 等。 在实际使用时往往使用Pandas的 cut() 函数实现等宽离散化: 可以看到与手工计算的离散化结果相同，需要注意的是， 等宽法对于离群点比较敏感，倾向于不均匀地把属性值分布到各个区间，导致某些区间数据较多，某些区间数据很少，这显然不利用决策模型的建立。 使用四个分位数作为边界点，对区间进行划分： 等频率离散化虽然避免了等宽离散化的数据分布不均匀的问题,却可能将相同的数据值分到不同的区间以满足每个区间具有相同数量的属性取值的要求。 使用一维聚类的离散化方法后得到数据集为： 在本次实例中选择使用基于聚类的离散化方法后得到的数据集进行指标计算。为了预测客户能否偿还债务，使用A（拥有房产）、B（婚姻情况）、C（年收入）等属性来进行数据集的划分最终构建决策树。 单身 ： 离婚 ： 已婚 ： 显然，由B属性取值'已婚'划分得到的子数据集属于同一个叶节点，无法再进行分类。 接下来，对由B属性取值'单身'划分得到的子数据集 再进行最优特征选择： 1）计算数据集 总的信息熵，其中4个数据中，能否偿还债务为'是'数据有3，'否'数据有1,则总的信息熵： 2）对于A(拥有房产)属性，其属性值有'是'和'否'两种。其中，在A为'是'的前提下，能否偿还债务为'是'的有1、'否'的有0；在A为'否'的前提下，能否偿还债务为'是'的有2、为'否'的有1，则A属性的信息熵为： 3)对于B（婚姻情况）属性，由于已被确定，在这个数据子集信息熵为0 4)对于C（年收入）属性，其属性值有'中等输入'、'低收入'两种。在C为'中等收入'的前提下，能否偿还作为为'是'的有1,为'否'的有0；在C为'低收入'的前提下，能否偿还作为为'是'的有2,为'否'的有1;则C属性的信息熵为： 5）最后分别计算两个属性的信息增益值： 信息增益值相同，说明以两个属性对数据子集进行划分后决策树的纯度上升是相同的，此时任选其一成为叶节点即可。 同理，对数据子集 进行最优特征选择，发现信息熵为0： 整理得到最终的决策树：
决策树（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. https://machinelearningmastery.com/what-is-information-entropy/ 2. https://zhuanlan.zhihu.com/p/29679277 3. https://machinelearningmastery.com/information-gain-and-mutual-information/ 4. https://victorzhou.com/blog/gini-impurity/ 5. https://sci2s.ugr.es/noisydata 6. https://towardsdatascience.com/understanding-decision-trees-once-and-for-all-2d891b1be579 7. https://blog.csdn.net/weixin_36586536/article/details/80468426 8. https://zhuanlan.zhihu.com/p/85731206
