id3算法决策树

❶ 决策树算法原理

决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到什么值的类似规则的方法。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。

如果不考虑效率等，那么样本所有特征的判断级联起来终会将某一个样本分到一个类终止块上。实际上，样本所有特征中有一些特征在分类时起到决定性作用，决策树的构造过程就是找到这些具有决定性作用的特征，根据其决定性程度来构造一个倒立的树--决定性作用最大的那个特征作为根节点，然后递归找到各分支下子数据集中次大的决定性特征，直至子数据集中所有数据都属于同一类。所以，构造决策树的过程本质上就是根据数据特征将数据集分类的递归过程，我们需要解决的第一个问题就是，当前数据集上哪个特征在划分数据分类时起决定性作用。

一棵决策树的生成过程主要分为以下3个部分:

特征选择：特征选择是指从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准标准，从而衍生出不同的决策树算法。

决策树生成： 根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止生长。 树结构来说，递归结构是最容易理解的方式。

剪枝：决策树容易过拟合，一般来需要剪枝，缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。

划分数据集的最大原则是：使无序的数据变的有序。如果一个训练数据中有20个特征，那么选取哪个做划分依据？这就必须采用量化的方法来判断，量化划分方法有多重，其中一项就是“信息论度量信息分类”。基于信息论的决策树算法有ID3、CART和C4.5等算法，其中C4.5和CART两种算法从ID3算法中衍生而来。

CART和C4.5支持数据特征为连续分布时的处理，主要通过使用二元切分来处理连续型变量，即求一个特定的值-分裂值：特征值大于分裂值就走左子树，或者就走右子树。这个分裂值的选取的原则是使得划分后的子树中的“混乱程度”降低，具体到C4.5和CART算法则有不同的定义方式。

ID3算法由Ross Quinlan发明，建立在“奥卡姆剃刀”的基础上：越是小型的决策树越优于大的决策树（be simple简单理论）。ID3算法中根据信息论的信息增益评估和选择特征，每次选择信息增益最大的特征做判断模块。ID3算法可用于划分标称型数据集，没有剪枝的过程，为了去除过度数据匹配的问题，可通过裁剪合并相邻的无法产生大量信息增益的叶子节点（例如设置信息增益阀值）。使用信息增益的话其实是有一个缺点，那就是它偏向于具有大量值的属性--就是说在训练集中，某个属性所取的不同值的个数越多，那么越有可能拿它来作为分裂属性，而这样做有时候是没有意义的，另外ID3不能处理连续分布的数据特征，于是就有了C4.5算法。CART算法也支持连续分布的数据特征。

C4.5是ID3的一个改进算法，继承了ID3算法的优点。C4.5算法用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足在树构造过程中进行剪枝；能够完成对连续属性的离散化处理；能够对不完整数据进行处理。C4.5算法产生的分类规则易于理解、准确率较高；但效率低，因树构造过程中，需要对数据集进行多次的顺序扫描和排序。也是因为必须多次数据集扫描，C4.5只适合于能够驻留于内存的数据集。

CART算法的全称是Classification And Regression Tree，采用的是Gini指数（选Gini指数最小的特征s）作为分裂标准,同时它也是包含后剪枝操作。ID3算法和C4.5算法虽然在对训练样本集的学习中可以尽可能多地挖掘信息，但其生成的决策树分支较大，规模较大。为了简化决策树的规模，提高生成决策树的效率，就出现了根据GINI系数来选择测试属性的决策树算法CART。

决策树算法的优点：

（1）便于理解和解释，树的结构可以可视化出来

（2）基本不需要预处理，不需要提前归一化，处理缺失值

（3）使用决策树预测的代价是O(log2m)，m为样本数

（4）能够处理数值型数据和分类数据

（5）可以处理多维度输出的分类问题

（6）可以通过数值统计测试来验证该模型，这使解释验证该模型的可靠性成为可能

（7）即使该模型假设的结果与真实模型所提供的数据有些违反，其表现依旧良好

决策树算法的缺点:

（1）决策树模型容易产生一个过于复杂的模型,这样的模型对数据的泛化性能会很差。这就是所谓的过拟合.一些策略像剪枝、设置叶节点所需的最小样本数或设置数的最大深度是避免出现该问题最为有效地方法。

（2）决策树可能是不稳定的，因为数据中的微小变化可能会导致完全不同的树生成。这个问题可以通过决策树的集成来得到缓解。

（3）在多方面性能最优和简单化概念的要求下，学习一棵最优决策树通常是一个NP难问题。因此，实际的决策树学习算法是基于启发式算法，例如在每个节点进行局部最优决策的贪心算法。这样的算法不能保证返回全局最优决策树。这个问题可以通过集成学习来训练多棵决策树来缓解,这多棵决策树一般通过对特征和样本有放回的随机采样来生成。

（4）有些概念很难被决策树学习到,因为决策树很难清楚的表述这些概念。例如XOR，奇偶或者复用器的问题。

（5）如果某些类在问题中占主导地位会使得创建的决策树有偏差。因此，我们建议在拟合前先对数据集进行平衡。

（1）当数据的特征维度很高而数据量又很少的时候，这样的数据在构建决策树的时候往往会过拟合。所以我们要控制样本数量和特征的之间正确的比率；

（2）在构建决策树之前，可以考虑预先执行降维技术（如PCA，ICA或特征选择），以使我们生成的树更有可能找到具有辨别力的特征；

（3）在训练一棵树的时候，可以先设置max_depth=3来将树可视化出来，以便我们找到树是怎样拟合我们数据的感觉，然后在增加我们树的深度；

（4）树每增加一层，填充所需的样本数量是原来的2倍，比如我们设置了最小叶节点的样本数量，当我们的树层数增加一层的时候，所需的样本数量就会翻倍，所以我们要控制好树的最大深度，防止过拟合；

（5）使用min_samples_split（节点可以切分时拥有的最小样本数） 和 min_samples_leaf（最小叶节点数）来控制叶节点的样本数量。这两个值设置的很小通常意味着我们的树过拟合了，而设置的很大意味着我们树预测的精度又会降低。通常设置min_samples_leaf=5；

（6）当树的类比不平衡的时候，在训练之前一定要先平很数据集，防止一些类别大的类主宰了决策树。可以通过采样的方法将各个类别的样本数量到大致相等，或者最好是将每个类的样本权重之和(sample_weight)规范化为相同的值。另请注意，基于权重的预剪枝标准（如min_weight_fraction_leaf）将比不知道样本权重的标准（如min_samples_leaf）更少偏向主导类别。

（7）如果样本是带权重的，使用基于权重的预剪枝标准将更简单的去优化树结构，如mn_weight_fraction_leaf，这确保了叶节点至少包含了样本权值总体总和的一小部分；

（8）在sklearn中所有决策树使用的数据都是np.float32类型的内部数组。如果训练数据不是这种格式，则将复制数据集，这样会浪费计算机资源。

（9）如果输入矩阵X非常稀疏，建议在调用fit函数和稀疏csr_matrix之前转换为稀疏csc_matrix，然后再调用predict。 当特征在大多数样本中具有零值时，与密集矩阵相比，稀疏矩阵输入的训练时间可以快几个数量级。

❷ 决策树（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.hu.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.hu.com/p/85731206

❸ 决策树的原理及算法

决策树基本上就是把我们以前的经验总结出来。我给你准备了一个打篮球的训练集。如果我们要出门打篮球，一般会根据“天气”、“温度”、“湿度”、“刮风”这几个条件来判断，最后得到结果：去打篮球？还是不去？

上面这个图就是一棵典型的决策树。我们在做决策树的时候，会经历两个阶段：构造和剪枝。

构造就是生成一棵完整的决策树。简单来说，构造的过程就是选择什么属性作为节点的过程，那么在构造过程中，会存在三种节点：
根节点：就是树的最顶端，最开始的那个节点。在上图中，“天气”就是一个根节点；
内部节点：就是树中间的那些节点，比如说“温度”、“湿度”、“刮风”；
叶节点：就是树最底部的节点，也就是决策结果。

剪枝就是给决策树瘦身，防止过拟合。分为“预剪枝”（Pre-Pruning）和“后剪枝”（Post-Pruning）。

预剪枝是在决策树构造时就进行剪枝。方法是在构造的过程中对节点进行评估，如果对某个节点进行划分，在验证集中不能带来准确性的提升，那么对这个节点进行划分就没有意义，这时就会把当前节点作为叶节点，不对其进行划分。

后剪枝就是在生成决策树之后再进行剪枝，通常会从决策树的叶节点开始，逐层向上对每个节点进行评估。如果剪掉这个节点子树，与保留该节点子树在分类准确性上差别不大，或者剪掉该节点子树，能在验证集中带来准确性的提升，那么就可以把该节点子树进行剪枝。

1是欠拟合，3是过拟合，都会导致分类错误。

造成过拟合的原因之一就是因为训练集中样本量较小。如果决策树选择的属性过多，构造出来的决策树一定能够“完美”地把训练集中的样本分类，但是这样就会把训练集中一些数据的特点当成所有数据的特点，但这个特点不一定是全部数据的特点，这就使得这个决策树在真实的数据分类中出现错误，也就是模型的“泛化能力”差。

p(i|t) 代表了节点 t 为分类 i 的概率，其中 log2 为取以 2 为底的对数。这里我们不是来介绍公式的，而是说存在一种度量，它能帮我们反映出来这个信息的不确定度。当不确定性越大时，它所包含的信息量也就越大，信息熵也就越高。

ID3 算法计算的是信息增益，信息增益指的就是划分可以带来纯度的提高，信息熵的下降。它的计算公式，是父亲节点的信息熵减去所有子节点的信息熵。

公式中 D 是父亲节点，Di 是子节点，Gain(D,a) 中的 a 作为 D 节点的属性选择。

因为 ID3 在计算的时候，倾向于选择取值多的属性。为了避免这个问题，C4.5 采用信息增益率的方式来选择属性。信息增益率 = 信息增益 / 属性熵，具体的计算公式这里省略。

当属性有很多值的时候，相当于被划分成了许多份，虽然信息增益变大了，但是对于 C4.5 来说，属性熵也会变大，所以整体的信息增益率并不大。

ID3 构造决策树的时候，容易产生过拟合的情况。在 C4.5 中，会在决策树构造之后采用悲观剪枝（PEP），这样可以提升决策树的泛化能力。

悲观剪枝是后剪枝技术中的一种，通过递归估算每个内部节点的分类错误率，比较剪枝前后这个节点的分类错误率来决定是否对其进行剪枝。这种剪枝方法不再需要一个单独的测试数据集。

C4.5 可以处理连续属性的情况，对连续的属性进行离散化的处理。比如打篮球存在的“湿度”属性，不按照“高、中”划分，而是按照湿度值进行计算，那么湿度取什么值都有可能。该怎么选择这个阈值呢，C4.5 选择具有最高信息增益的划分所对应的阈值。

针对数据集不完整的情况，C4.5 也可以进行处理。

暂无

请你用下面的例子来模拟下决策树的流程，假设好苹果的数据如下，请用 ID3 算法来给出好苹果的决策树。

“红”的信息增益为：1“大”的信息增益为：0
因此选择“红”的作为根节点，“大”没有用，剪枝。

数据分析实战45讲.17 丨决策树（上）：要不要去打篮球？决策树来告诉你

❹ 5.10 决策树与ID3算法

https://blog.csdn.net/dorisi_h_n_q/article/details/82787295

决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。决策过程是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。

决策树的关键步骤是分裂属性。就是在某节点处按某一特征属性的不同划分构造不同的分支，目标是让各个分裂子集尽可能地“纯”。即让一个分裂子集中待分类项属于同一类别。

简而言之，决策树的划分原则就是：将无序的数据变得更加有序

分裂属性分为三种不同的情况 ：

构造决策树的关键性内容是进行属性选择度量，属性选择度量（找一种计算方式来衡量怎么划分更划算）是一种选择分裂准则，它决定了拓扑结构及分裂点split_point的选择。

属性选择度量算法有很多，一般使用自顶向下递归分治法，并采用不回溯的贪心策略。这里介绍常用的ID3算法。

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。

此概念最早起源于物理学，是用来度量一个热力学系统的无序程度。
而在信息学里面，熵是对不确定性的度量。
在1948年，香农引入了信息熵，将其定义为离散随机事件出现的概率，一个系统越是有序，信息熵就越低，反之一个系统越是混乱，它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。

熵定义为信息的期望值，在明晰这个概念之前，我们必须知道信息的定义。如果待分类的事务可能划分在多个分类之中，则符号x的信息定义为：

在划分数据集之前之后信息发生的变化称为信息增益。
知道如何计算信息增益，就可计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。

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

根据上面公式，我们假设将训练集D按属性A进行划分，则A对D划分的期望信息为

则信息增益为如下两者的差值

ID3算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂

步骤：1. 对当前样本集合，计算所有属性的信息增益；

是最原始的决策树分类算法，基本流程是，从一棵空数出发，不断的从决策表选取属性加入数的生长过程中，直到决策树可以满足分类要求为止。CLS算法存在的主要问题是在新增属性选取时有很大的随机性。ID3算法是对CLS算法的改进，主要是摒弃了属性选择的随机性。

基于ID3算法的改进，主要包括：使用信息增益比替换了信息增益下降度作为属性选择的标准；在决策树构造的同时进行剪枝操作；避免了树的过度拟合情况；可以对不完整属性和连续型数据进行处理；使用k交叉验证降低了计算复杂度；针对数据构成形式，提升了算法的普适性。

信息增益值的大小相对于训练数据集而言的，并没有绝对意义，在分类问题困难时，也就是说在训练数据集经验熵大的时候，信息增益值会偏大，反之信息增益值会偏小，使用信息增益比可以对这个问题进行校正，这是特征选择
的另一个标准。
特征对训练数据集的信息增益比定义为其信息增益gR( D,A) 与训练数据集的经验熵g(D,A)之比 ：

gR(D,A) = g(D,A) / H(D)

sklearn的决策树模型就是一个CART树。是一种二分递归分割技术，把当前样本划分为两个子样本，使得生成的每个非叶子节点都有两个分支，因此，CART算法生成的决策树是结构简洁的二叉树。
分类回归树算法(Classification and Regression Trees,简称CART算法)是一种基于二分递归分割技术的算法。该算法是将当前的样本集，分为两个样本子集，这样做就使得每一个非叶子节点最多只有两个分支。因此，使用CART
算法所建立的决策树是一棵二叉树，树的结构简单，与其它决策树算法相比，由该算法生成的决策树模型分类规则较少。

CART分类算法的基本思想是：对训练样本集进行递归划分自变量空间，并依次建立决策树模型，然后采用验证数据的方法进行树枝修剪，从而得到一颗符合要求的决策树分类模型。

CART分类算法和C4.5算法一样既可以处理离散型数据，也可以处理连续型数据。CART分类算法是根据基尼(gini)系
数来选择测试属性，gini系数的值越小，划分效果越好。设样本集合为T，则T的gini系数值可由下式计算：

CART算法优点：除了具有一般决策树的高准确性、高效性、模式简单等特点外，还具有一些自身的特点。
如，CART算法对目标变量和预测变量在概率分布上没有要求，这样就避免了因目标变量与预测变量概率分布的不同造成的结果；CART算法能够处理空缺值，这样就避免了因空缺值造成的偏差；CART算法能够处理孤立的叶子结点，这样可以避免因为数据集中与其它数据集具有不同的属性的数据对进一步分支产生影响；CART算法使用的是二元分支，能够充分地运用数据集中的全部数据，进而发现全部树的结构；比其它模型更容易理解，从模型中得到的规则能获得非常直观的解释。

CART算法缺点：CART算法是一种大容量样本集挖掘算法，当样本集比较小时不够稳定；要求被选择的属性只能产生两个子结点，当类别过多时，错误可能增加得比较快。

sklearn.tree.DecisionTreeClassifier

1.安装graphviz.msi ， 一路next即可

ID3算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂

按照好友密度划分的信息增益：

按照是否使用真实头像H划分的信息增益

**所以，按先按好友密度划分的信息增益比按真实头像划分的大。应先按好友密度划分。

❺ 决策树——ID3算法应用实例

在ID3决策树归纳方法中，通常是使用信息增益方法来帮助确定生成每个节点时所应采用的合适属性。这样就可以选择具有最高信息增益（熵减少的程度最大）的属性最为当前节点的测试属性，以便对之后划分的训练样本子集进行分类所需要的信息最小，也就是说，利用该属性进行当前（节点所含）样本集合划分，将会使得所产生的样本子集中的“不同类别的混合程度”降为最低。因此，采用这样一种信息论方法将有效减少对象分来所需要的次数，从而确保所产生的决策树最为简单。

一、实验目的

1、理解分类

2、掌握分类挖掘算法ID3

3、为改进ID3打下基础

二、实验内容

1、选定一个数据集（可以参考教学中使用的数据集）

2、选择合适的实现环境和工具实现算法 ID3

3、给出分类规则

三、实验原理

决策树是一种最常见的分类算法，它包含有很多不同的变种，ID3算法是其中最简单的一种。ID3算法中最主要的部分就是信息熵和信息增益的计算。

❻ id3算法是什么

ID3算法是一种贪心算法，用来构造决策树。ID3算法起源于概念学习系统（CLS），以信息熵的下降速度为选取测试属性的标准，即在每个节点选取还尚未被用来划分的具有最高信息增益的属性作为划分标准，然后继续这个过程，直到生成的决策树能完美分类训练样例。

ID3算法的背景

ID3算法最早是由罗斯昆（J. Ross Quinlan）于1975年在悉尼大学提出的一种分类预测算法，算法的核心是“信息熵”。ID3算法通过计算每个属性的信息增益，认为信息增益高的是好属性，每次划分选取信息增益最高的属性为划分标准，重复这个过程，直至生成一个能完美分类训练样例的决策树。

❼ 决策树是什么东东

小白自学路上的备忘记录。。。

参考：
决策树(分类树、回归树)
决策树 :这个博客的图真好看，通俗易懂。哈哈
决策树详解

决策树（Decision Tree）是一种有监督学习算法，常用于分类和回归。本文仅讨论分类问题。

决策树模型是运用于分类以及回归的一种树结构。决策树由节点和有向边组成，一般一棵决策树包含一个根节点、若干内部节点和若干叶节点。决策树的决策过程需要从决策树的根节点开始，待测数据与决策树中的特征节点进行比较，并按照比较结果选择选择下一比较分支，直到叶子节点作为最终的决策结果。

简而言之，决策树是一个利用树的模型进行决策的多分类模型

为了找到最优的划分特征，我们需要先了解一些信息论的知识：

纯度 ：
你可以把决策树的构造过程理解成为寻找纯净划分的过程。数学上，我们可以用纯度来表示，纯度换一种方式来解释就是让目标变量的分歧最小

信息熵 ：表示信息的不确定度
在信息论中，随机离散事件出现的概率存在着不确定性。为了衡量这种信息的不确定性，信息学之父香农引入了信息熵的概念.
当不确定性越大时，它所包含的信息量也就越大，信息熵也就越高 。
信息熵越大，纯度越低。当集合中的所有样本均匀混合时，信息熵最大，纯度最低

经典的 “不纯度”的指标有三种，分别是信息增益（ID3 算法）、信息增益率（C4.5 算法）以及基尼指数（Cart 算法）
信息增益 ：
信息增益指的就是划分可以带来纯度的提高，信息熵的下降。它的计算公式，是父亲节点的信息熵减去所有子节点的信息熵。
信息增益率
信息增益率 = 信息增益 / 属性熵
基尼指数
基尼指数（基尼不纯度）：表示在样本集合中一个随机选中的样本被分错的概率。
即 基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率
基尼系数的性质与信息熵一样：度量随机变量的不确定度的大小；
G 越大，数据的不确定性越高；
G 越小，数据的不确定性越低；
G = 0，数据集中的所有样本都是同一类别
详细参考： 机器学习——基尼指数

ID3 算法是建立在奥卡姆剃刀（用较少的东西，同样可以做好事情）的基础上：越是小型的决策树越优于大的决策树
ID3算法的核心是在决策树各个节点上根据信息增益来选择进行划分的特征，然后递归地构建决策树。算法采用自顶向下的贪婪搜索遍历可能的决策树空间。

具体方法 ：

ID3的局限 ：

C4.5与ID3相似，但大的特点是克服了 ID3 对特征数目的偏重这一缺点，引入信息增益率来作为分类标准。

C4.5的实现基于ID3的改进 ：

信息增益率对可取值较少的特征有所偏好（分母越小，整体越大），因此 C4.5 并不是直接用增益率最大的特征进行划分，而是使用一个 启发式方法 ：先从候选划分特征中找到信息增益高于平均值的特征，再从中选择增益率最高的。

C4.5的局限 ：

ID3 和 C4.5 生成的决策树分支、规模都比较大，CART 算法的二分法可以简化决策树的规模，提高生成决策树的效率。
CART(),分类回归树算法，既可用于分类也可用于回归，在这一部分我们先主要将其分类树的生成。区别于ID3和C4.5,CART假设决策树是二叉树，内部节点特征的取值为“是”和“否”，左分支为取值为“是”的分支，右分支为取值为”否“的分支。这样的决策树等价于递归地二分每个特征，将输入空间(即特征空间)划分为有限个单元。
CART的分类树用基尼指数来选择最优特征的最优划分点，具体过程如下

剪枝就是给决策树瘦身，这一步想实现的目标就是，不需要太多的判断，同样可以得到不错的结果。之所以这么做，是为了防止“过拟合”（Overfitting）现象的发生。
过拟合：指的是模型的训练结果“太好了”，以至于在实际应用的过程中，会存在“死板”的情况，导致分类错误。
欠拟合：指的是模型的训练结果不理想.
剪枝的方法 ：

参考： 【机器学习】决策树（上）——ID3、C4.5、CART（非常详细）

更多模型不断更新中。。。。

❽ C4.5算法

C4.5是一系列用在机器学习和数据挖掘的分类问题中的算法。它的目标是监督学习：给定一个数据集，其中的每一个元组都能用一组属性值来描述，每一个元组属于一个互斥的类别中的某一类。C4.5的目标是通过学习，找到一个从属性值到类别的映射关系，并且这个映射能用于对新的类别未知的实体进行分类。
C4.5由J.Ross Quinlan在ID3的基础上提出的。ID3算法用来构造决策树。决策树是一种类似流程图的树结构，其中每个内部节点（非树叶节点）表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶节点存放一个类标号。一旦建立好了决策树，对于一个未给定类标号的元组，跟踪一条有根节点到叶节点的路径，该叶节点就存放着该元组的预测。决策树的优势在于不需要任何领域知识或参数设置，适合于探测性的知识发现。

决策树呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型；预测时，对新的数据，利用决策模型进行分类。

决策树是一种通过对特征属性的分类对样本进行分类的树形结构，包括有向边以及三类节点：

上图给出了（二叉）决策树的示例。决策树具有以下特点：

决策树学习的本质是从训练集中归纳出一组分类规则。但随着分裂属性次序的不同，所得到的决策树也会不同。如何得到一棵决策树既对训练数据有较好的拟合，又对未知数据有很好的预测呢？

首先，我们要解决两个问题：

一般的，一颗决策树包含一个根节点、若干个内部结点和若干个叶结点；叶结点则对应于一个属性册书；每个叶结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集，从根结点到每个叶结点的路径对饮过了一个判定测试序列。决策树学习的目的是为了产生一颗泛化能力强的决策树，其基本流程遵循简单且只管的“分而治之”（divide-and-conquer）策略，如下图所示：

显然，决策树的生成是一个递归的过程。在决策树基本算法中，有三种情形会导致递归返回：

在第二种情形下，我们把当前结点标记为叶结点，并且将其类别设定为该结点所含样本最多的类别；在第三种情形下，同样把当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多类别。注意这两种情形的处理实质不同：情形二是在利用当前结点的后验分布，而情形三则是把父结点的样本分布当做当前结点的先验分布。

决策树学习的关键在于如何选择最优划分属性。一般而言，随着划分过程的不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。

“信息熵”（information entropy）是度量样本集合纯度最常用的一种指标。假定当前样本集合 中第k类样本所占比例为 ，则 的信息熵定义为

的值越小，则 的纯度越高。
假定离散属性 有 个可能的取值 ,若使用 来对样本集合 进行划分，则会产生 个分支结点，其中第v个分支结点包含了 中所有在属性 上取值为 的样本，记为 ，我们根据上述公式计算出 的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重 ，即样本越多的分支结点影响越大，于是可以计算出用属性 对样本集合 进行划分所获得的"信息增益"（information gain）

一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升越大”。因此，我们可用信息增益来进行决策树的划分属性选择。

实际上，信息增益准则对可取值数目较多的属性有所偏好（如何以序号作为划分属性，每一个事物作为一个单独存在的类别的时候，信息增益往往会很高，但是这样进行划分并没有什么意义），为了减少这种偏好可能带来的不利影响，着名的C4.5算法并不是直接使用信息增益，而是使用增益率（gain ratio）来选择最优的划分属性。增益率的定义为：

值得注意的是： 增益率准则对可取值数目较少的属性有所偏好，因此C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式： 先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的

CART决策树使用“基尼指数”来选择划分属性。数据集 的纯度可用基尼值来度量：

直观来说， 反映了从数据集 中随机抽取两个样本，其类别标记不一致的概率，因此 值越小，则数据集 的纯度就越高。属性 的基尼指数定义为：

于是，我们在候选属性集合 中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即

银行希望能够通过一个人的信息（包括职业、年龄、收入、学历）去判断他是否有贷款的意向，从而更有针对性地完成工作。下表是银行现在能够掌握的信息，我们的目标是通过对下面的数据进行分析建立一个预测用户贷款一下的模型。

上表中有4个客户的属性，如何综合利用这些属性去判断用户的贷款意向？决策树的做法是每次选择一个属性进行判断，如果不能得出结论，继续选择其他属性进行判断，直到能够“肯定地”判断出用户的类型或者是上述属性都已经使用完毕。比如说我们要判断一个客户的贷款意向，我们可以先根据客户的职业进行判断，如果不能得出结论，再根据年龄作判断，这样以此类推，直到可以得出结论为止。决策树用树结构实现上述的判断流程，如图所示：

以熵作为节点复杂度的统计量，分别求出下面例子的信息增益，图3.1表示节点选择属性1进行分裂的结果，图3.2表示节点选择属性2进行分裂的结果，通过计算两个属性分裂后的信息增益，选择最优的分裂属性。

属性一

属性二

由于 ，所以属性1是比属性2更优的分裂属性，故而选择属性1作为分裂属性。

由于 ，故而选择属性2作为分裂属性。

剪枝（pruning）是决策树学习算法对付“过拟合”的主要手段。在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有事会造成决策树分支过多，这是就可能因为训练样本学得太好了，以致把训练集自身的一些特点党组哟所有数据都具有的一般性质而导致过拟合。因此，可通过主动去掉一些分支来降低过拟合的风险。

其中{1,2,3,6,7,10,14,15,16,17}为测试集，{4,5,8,9,11,12,13}为训练集。

预剪枝是要对划分前后泛化性能进行评估。对比决策树某节点生成前与生成后的泛化性能。

2.计算训练集的信息增益，得知脐部的信息增益最大，因此按照脐部进行划分。又因为在训练集中，凹陷特征好瓜的占比多，因此凹陷划分为好瓜，稍凹特征好过占比多，因此将其标记为好瓜，因此按照脐部划分的子树结果如下：

划分后，对比结果如下：

由图可知，预剪枝使得很多分支没有展开，这不仅降低了过拟合的风险，还显着减少了决策树的训练时间开销和测试时间。但是，有些分支虽当前不能提升泛化性。甚至可能导致泛化性暂时降低，但在其基础上进行后续划分却有可能导致显着提高，因此预剪枝的这种贪心本质，给决策树带来了欠拟合的风险。

后剪枝表示先从训练集中生成一颗完整决策树。

对比标记节点的划分类与各数据的真实分类，计算准确率，如下表所示：

生成的决策树，在验证集上的准确度为3/7*100%=42.9%.

对比预剪枝与后剪枝生成的决策树，可以看出，后剪枝通常比预剪枝保留更多的分支，其欠拟合风险很小，因此后剪枝的泛化性能往往由于预剪枝决策树。但后剪枝过程是从底往上裁剪，因此其训练时间开销比前剪枝要大。

❾ 决策树（Decision Tree）

通俗来说，决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：

      女儿：多大年纪了？

      母亲：26。

      女儿：长的帅不帅？

      母亲：挺帅的。

      女儿：收入高不？

      母亲：不算很高，中等情况。

      女儿：是公务员不？

      母亲：是，在税务局上班呢。

      女儿：那好，我去见见。

      这个女孩的决策过程就是典型的分类树决策。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见。假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，图1表示了女孩的决策逻辑。

如果你作为一个女生，你会优先考虑哪个条件：长相？收入？还是年龄。在考虑年龄条件时使用25岁为划分点，还是35岁为划分点。有这么多条件，用哪个条件特征先做if，哪个条件特征后做if比较优呢？还有怎么确定用特征中的哪个数值作为划分的标准。这就是决策树机器学习算法的关键了。

首先，我们需要熟悉信息论中熵的概念。熵度量了事物的不确定性，越不确定的事物，它的熵就越大。具体的，随机变量X的熵的表达式如下：

如抛一枚硬币为事件 ， ， ，

掷一枚骰子为事件 ， ，

，显然掷骰子的不确定性比投硬币的不确定性要高。 

熟悉了单一变量的熵，很容易推广到多个个变量的联合熵，这里给出两个变量X和Y的联合熵表达式：

有了联合熵，又可以得到条件熵的表达式H(X|Y)，条件熵类似于条件概率,它度量了我们在知道Y以后X剩下的不确定性。表达式：

我们刚才提到 度量了 的不确定性，条件熵 度量了我们在知道 以后 剩下的不确定性，那么 呢？它度量了 在知道 以后不确定性减少程度，这个度量我们在信息论中称为互信息，记为 。

信息熵 ，联合熵 ，条件熵 ，互信息 之间的关系由图2所示：

在决策树的ID3算法中，互信息 被称为信息增益。ID3算法就是用信息增益来判断当前节点应该用什么特征来构建决策树。信息增益大，则越适合用来分类。

下面我们用SNS社区中不真实账号检测的例子说明如何使用ID3算法构造决策树。为了简单起见，我们假设训练集合包含10个元素：

设L、F、H和D表示日志密度、好友密度、是否使用真实头像和账号是否真实，下面计算各属性的信息增益：

 因此日志密度的信息增益是0.276。用同样方法得到H和F的信息增益分别为0.033和0.553。因为F具有最大的信息增益，所以第一次分裂选择F为分裂属性，分裂后的结果图3表示：

在上图的基础上，再递归使用这个方法计算子节点的分裂属性，最终就可以得到整个决策树。

但是ID3算法中还存在着一些不足之处：

1.ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。

2.ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为 ，另一个变量为3个值，各为 ，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。（信息增益反映的给定一个条件以后不确定性减少的程度,必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大）如河校正这个问题呢？为了解决这些问题我们有了C4.5算法。

对于第一个问题，不能处理连续特征， C4.5的思路是将连续的特征离散化。比如m个样本的连续特征A有m个，从小到大排列为 。则C4.5取相邻两样本值的平均数，一共取得m-1个划分点，其中第i个划分点 表示为： 。对于这m-1个点，分别计算以该点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。比如取到的增益最大的点为 ，取大于 为类别1，小于 为类别2。这样我们就做到了连续特征的离散化。

对于第二个问题，信息增益作为标准容易偏向于取值较多的特征。C4.5中提出了信息增益比：

即特征 的对数据集 的信息增益与特征 信息熵的比，信息增益比越大的特征和划分点，分类效果越好。某特征中值得种类越多，特征对应的特征熵越大，它作为分母，可以校正信息增益导致的问题。

回到上面的例子：

 

同样可得：  ， 。

因为F具有最大的信息增益比，所以第一次分裂选择F为分裂属性，分裂后的结果图3表示。

再递归使用这个方法计算子节点的分裂属性，最终就可以得到整个决策树。

看完上述材料，我们知道在ID3算法中我们使用了信息增益来选择特征，信息增益大的优先选择。在C4.5算法中，采用了信息增益比来选择特征，以减少信息增益容易选择特征值种类多的特征的问题。但是无论是ID3还是C4.5,都是基于信息论的熵模型的，这里面会涉及大量的对数运算。能不能简化模型同时也不至于完全丢失熵模型的优点呢？有！CART分类树算法使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益(比)是相反的。

在分类问题中，假设有 个类别，第 个类别的概率为 ,则基尼系数为：

对于给定的样本 ，假设有 个类别，第 个类别的数量为 ，则样本的基尼系数为:

特别的，对于样本D,如果根据特征A的某个值a,把D分成D1和D2两部分，则在特征A的条件下，D的基尼系数为：

回到上面的例子：

同理得： ， 。

因为L具有最小的基尼系数，所以第一次分裂选择L为分裂属性。

再递归使用这个方法计算子节点的分裂属性，最终就可以得到整个决策树。

小伙伴们如果觉得文章还行的请点个赞呦！！同时觉得文章哪里有问题的可以评论一下  谢谢你！

❿ 决策树算法

决策树算法的算法理论和应用场景

算法理论：

我了解的决策树算法，主要有三种，最早期的ID3，再到后来的C4.5和CART这三种算法。

这三种算法的大致框架近似。

决策树的学习过程

1.特征选择

在训练数据中 众多X中选择一个特征作为当前节点分裂的标准。如何选择特征有着很多不同量化评估标准，从而衍生出不同的决策树算法。

2.决策树生成

根据选择的特征评估标准，从上至下递归生成子节点，直到数据集不可分或者最小节点满足阈值，此时决策树停止生长。

3.剪枝

决策树极其容易过拟合，一般需要通过剪枝，缩小树结构规模、缓解过拟合。剪枝技术有前剪枝和后剪枝两种。

有些算法用剪枝过程，有些没有，如ID3。

预剪枝：对每个结点划分前先进行估计，若当前结点的划分不能带来决策树的泛化性能的提升，则停止划分，并标记为叶结点。

后剪枝：现从训练集生成一棵完整的决策树，然后自底向上对非叶子结点进行考察，若该结点对应的子树用叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。

但不管是预剪枝还是后剪枝都是用验证集的数据进行评估。

ID3算法是最早成型的决策树算法。ID3的算法核心是在决策树各个节点上应用信息增益准则来选择特征，递归构建决策树。缺点是，在选择分裂变量时容易选择分类多的特征，如ID值【值越多、分叉越多，子节点的不纯度就越小，信息增益就越大】。

ID3之所以无法 处理缺失值、无法处理连续值、不剪纸等情况，主要是当时的重点并不是这些。

C4.5算法与ID3近似，只是分裂标准从 信息增益 转变成  信息增益率。可以处理连续值，含剪枝，可以处理缺失值，这里的做法多是 概率权重。

CART：1.可以处理连续值 2.可以进行缺失值处理 3.支持剪枝 4.可以分类可以回归。

缺失值的处理是 作为一个单独的类别进行分类。

建立CART树

我们的算法从根节点开始，用训练集递归的建立CART树。

1) 对于当前节点的数据集为D，如果样本个数小于阈值或者没有特征，则返回决策子树，当前节点停止递归。

2) 计算样本集D的基尼系数， 如果基尼系数小于阈值 （说明已经很纯了！！不需要再分了！！），则返回决策树子树，当前节点停止递归。

3) 计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数。

4) 在计算出来的各个特征的各个特征值对数据集D的基尼系数中，选择 基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值，把数据集划分成两部分D1和D2，同时建立当前节点的左右节点，做节点的数据集D为D1，右节点的数据集D为D2。 (注：注意是二叉树，故这里的D1和D2是有集合关系的，D2=D-D1)

5) 对左右的子节点递归的调用1-4步，生成决策树。

CART采用的办法是后剪枝法，即先生成决策树，然后产生所有可能的剪枝后的CART树，然后使用交叉验证来检验各种剪枝的效果，选择泛化能力最好的剪枝策略。

应用场景

比如欺诈问题中，通过决策树算法简单分类，默认是CART的分类树，默认不剪枝。然后在出图后，自行选择合适的叶节点进行拒绝操作。

这个不剪枝是因为欺诈问题的特殊性，欺诈问题一般而言较少，如数据的万几水平，即正样本少，而整个欺诈问题需要解决的速度较快。此时只能根据业务要求，迅速针对已有的正样本情况，在控制准确率的前提下，尽可能提高召回率。这种情况下，可以使用决策树来简单应用，这个可以替代原本手工选择特征及特征阈值的情况。