数据挖掘决策树算法ID3和C4.5

决策树模型ID3C4.5CART算法⽐较决策树模型在监督学习中⾮常常见，可⽤于分类（⼆分类、多分类）和回归。

虽然将多棵弱决策树的Bagging、Random Forest、Boosting等tree ensembel 模型更为常见，但是“完全⽣长”决策树因为其简单直观，具有很强的解释性，也有⼴泛的应⽤，⽽且决策树是tree ensemble 的基础，值得好好理解。

⼀般⽽⾔⼀棵“完全⽣长”的决策树包含，特征选择、决策树构建、剪枝三个过程，这篇⽂章主要是简单梳理⽐较ID3、C4.5、CART算法。

《统计学习⽅法》中有⽐较详细的介绍。

⼀、决策树的优点和缺点优点：1. 决策树算法中学习简单的决策规则建⽴决策树模型的过程⾮常容易理解，2. 决策树模型可以可视化，⾮常直观3. 应⽤范围⼴，可⽤于分类和回归，⽽且⾮常容易做多类别的分类4. 能够处理数值型和连续的样本特征缺点：1. 很容易在训练数据中⽣成复杂的树结构，造成过拟合（overfitting）。

剪枝可以缓解过拟合的负作⽤，常⽤⽅法是限制树的⾼度、叶⼦节点中的最少样本数量。

2. 学习⼀棵最优的决策树被认为是NP-Complete问题。

实际中的决策树是基于启发式的贪⼼算法建⽴的，这种算法不能保证建⽴全局最优的决策树。

Random Forest 引⼊随机能缓解这个问题⼆、ID3算法ID3由Ross Quinlan在1986年提出。

ID3决策树可以有多个分⽀，但是不能处理特征值为连续的情况。

决策树是⼀种贪⼼算法，每次选取的分割数据的特征都是当前的最佳选择，并不关⼼是否达到最优。

在ID3中，每次根据“最⼤信息熵增益”选取当前最佳的特征来分割数据，并按照该特征的所有取值来切分，也就是说如果⼀个特征有4种取值，数据将被切分4份，⼀旦按某特征切分后，该特征在之后的算法执⾏中，将不再起作⽤，所以有观点认为这种切分⽅式过于迅速。

ID3算法⼗分简单，核⼼是根据“最⼤信息熵增益”原则选择划分当前数据集的最好特征，信息熵是信息论⾥⾯的概念，是信息的度量⽅式，不确定度越⼤或者说越混乱，熵就越⼤。

机器学习--决策树算法（ID3C4.5）在⽣活中，“树”这⼀模型有很⼴泛的应⽤，事实证明，它在机器学习分类和回归领域也有着深刻⽽⼴泛的影响。

在决策分析中，决策树可以明确直观的展现出决策结果和决策过程。

如名所⽰，它使⽤树状决策模型。

它不仅仅是在数据挖掘中⽤户获取特定⽬标解的策略，同时也被⼴泛的应⽤于机器学习。

如何使⽤树来表⽰算法为此，我们考虑使⽤泰坦尼克号数据集的⽰例，以预测乘客是否会⽣存。

下⾯的模型使⽤数据集中的3个特征/属性/列，即性别，年龄和SIBSP（配偶或⼉童的数量）。

这是⼀棵体现了⼈性光辉的决策树。

树的形状是⼀棵上下颠倒的决策树，叶⼦节点在下，根节点在上。

在图像中，⿊⾊中的粗体⽂本表⽰条件/内部节点，基于树分成分⽀/边缘。

不再分裂的分⽀结束是决策/叶⼦，在这种情况下，乘客是否被死亡或幸存，分别表⽰为红⾊和绿⾊⽂本。

虽然，⼀个真实的数据集将有很多功能，这只是⼀个更⼤的树中的部分分⽀，但你不能忽略这种算法的简单性。

该特征重要性是明确的，可以轻易查看决策关系。

该⽅法更常见于来⾃数据的学习决策树，并且在树上被称为分类树，因为⽬标是将乘客分类为幸存或死亡，上⾯所展⽰的决策树就是分类树。

回归树以相同的⽅式表⽰，例如⽤于预测房⼦价格的连续价值。

通常，决策树算法被称为CART或分类和回归树。

那么，算法⽣成的背后发⽣了什么呢？如何⽣成⼀个决策树取决于选择什么特征和在何种情况下进⾏分裂，以及在什么时候停⽌。

因为⼀棵树通常是随意⽣长的，你需要修剪它，让它看起来漂亮（研究如何⽣成决策树）。

ID3算法ID3算法⽣成决策树ID3算法（Iterative Dichotomiser 3）是决策树⽣成算法的⼀种，基于奥卡姆剃⼑原理(简约原则) 1。

是Ross Quinlan发明的⼀种决策树算法，这个算法的基础就是上⾯提到的奥卡姆剃⼑原理，越是⼩型的决策树越优于⼤的决策树，尽管如此，也不总是⽣成最⼩的树型结构，⽽是⼀个启发式算法。

机器学习总结（⼋）决策树ID3，C4.5算法，CART算法本⽂主要总结决策树中的ID3,C4.5和CART算法，各种算法的特点，并对⽐了各种算法的不同点。

决策树：是⼀种基本的分类和回归⽅法。

在分类问题中，是基于特征对实例进⾏分类。

既可以认为是if-then规则的集合，也可以认为是定义在特征空间和类空间上的条件概率分布。

决策树模型：决策树由结点和有向边组成。

结点⼀般有两种类型，⼀种是内部结点，⼀种是叶节点。

内部结点⼀般表⽰⼀个特征，⽽叶节点表⽰⼀个类。

当⽤决策树进⾏分类时，先从根节点开始，对实例的某⼀特征进⾏测试，根据测试结果，将实例分配到⼦结点。

⽽⼦结点这时就对应着该特征的⼀个取值。

如此递归对实例进⾏测试分配，直⾄达到叶结点，则该实例属于该叶节点的类。

决策树分类的主要算法有ID3，C4.5。

回归算法为CART算法，该算法既可以分类也可以进⾏回归。

（⼀）特征选择与信息增益准则特征选择在于选取对训练数据具有分类能⼒的特征，⽽且是分类能⼒越强越好，这样⼦就可以提⾼决策树的效率。

如果利⽤⼀个特征进⾏分类，分类的结果与随机分类的结果没有差异，那么这个特征是没有分类能⼒的。

那么⽤什么来判别⼀个特征的分类能⼒呢？那就是信息增益准则。

何为信息增益？⾸先，介绍信息论中熵的概念。

熵度量了随机变量的不确定性，越不确定的事物，它的熵就越⼤。

具体的，随机变量X的熵定义如下：条件熵H(Y|X)表⽰在已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵为H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望：信息增益表⽰在已知特征X的情况下，⽽使得Y的信息的不确定性减少的程度。

信息增益的定义式如下：g(D,A)表⽰特征A对训练集D的信息增益，其为集合D的经验熵H(D)与在特征A给定条件下D的经验条件熵H(D|A)之差。

⼀般熵与条件熵之差，称为互信息。

在决策树中，信息增益就等价于训练数据集中的类与特征的互信息。

决策树分类ID3和C4.5原理Java实现决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。

其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。

使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。

•决策树的构造:•决策树的构造就是通过属性选择来确定拓扑结构。

•构造决策树的关键步骤是分裂属性。

所谓分裂属性就是在某个节点处按照某一特征属性的不同划分构造不同的分支，其目标是让各个分裂子集尽可能地“纯”。

尽可能“纯”就是尽量让一个分裂子集中待分类项属于同一类别。

分裂属性分为三种不同的情况：•1、属性是离散值且不要求生成二叉决策树。

此时用属性的每一个划分作为一个分支。

•2、属性是离散值且要求生成二叉决策树。

此时使用属性划分的一个子集进行测试，按照“属于此子集”和“不属于此子集”分成两个分支。

•3、属性是连续值。

此时确定一个值作为分裂点split_point，按照>split_point和<=split_point生成两个分支。

ID3ID3算法使用信息增益(IG)或者熵(Entropy)值来确定使用哪个属性进行判定，作为最佳属性。

计算熵的公式为：信息增益的公式如下：缺点：1：ID3算法在选择根节点和内部节点中的分支属性时，采用信息增益作为评价标准。

信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息。

例如ID字段等。

2：ID3算法只能对描述属性为离散型属性的数据集构造决策树C4.5C4.5算法采用信息增益率作为选择分支属性的标准，并克服了ID3算法中信息增益选择属性时偏向选择取值多的属性的不足，并能够完成对连续属性离散化是处理；还能够对不完整数据进行处理。

C4.5算法属于基于信息论Information Theory的方法，以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳和分类。

数据挖掘十大经典算法一、 C4.5C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3 算法. C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；2) 在树构造过程中进行剪枝；3) 能够完成对连续属性的离散化处理；4) 能够对不完整数据进行处理。

C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。

其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。

1、机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。

树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。

决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。

2、从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。

3、决策树学习也是数据挖掘中一个普通的方法。

在这里，每个决策树都表述了一种树型结构，他由他的分支来对该类型的对象依靠属性进行分类。

每个决策树可以依靠对源数据库的分割进行数据测试。

这个过程可以递归式的对树进行修剪。

当不能再进行分割或一个单独的类可以被应用于某一分支时，递归过程就完成了。

另外，随机森林分类器将许多决策树结合起来以提升分类的正确率。

决策树是如何工作的？1、决策树一般都是自上而下的来生成的。

2、选择分割的方法有好几种，但是目的都是一致的：对目标类尝试进行最佳的分割。

3、从根到叶子节点都有一条路径，这条路径就是一条―规则4、决策树可以是二叉的，也可以是多叉的。

对每个节点的衡量：1) 通过该节点的记录数2) 如果是叶子节点的话，分类的路径3) 对叶子节点正确分类的比例。

有些规则的效果可以比其他的一些规则要好。

由于ID3算法在实际应用中存在一些问题，于是Quilan提出了C4.5算法，严格上说C4.5只能是ID3的一个改进算法。

决策树的训练算法
决策树的训练算法主要有以下几种：
1. ID3算法：ID3（Iterative Dichotomiser 3）是一种用于决策树学习的经典算法。

它基于信息熵的概念，通过计算每个特征的信息增益来选择最优的划分特征。

2. C4.5算法：C4.5算法是ID3算法的改进版，它在选择划分特征时使用信息增益比来解决ID3算法中对取值较多的特征有偏好的问题。

此外，C4.5算法还支持处理连续特征。

3. CART算法：CART（Classification and Regression Tree）算法是一种用于生成二叉决策树的算法。

它根据基尼系数来选择最优的划分特征，并使用回归树或分类树来处理连续特征。

4. CHAID算法：CHAID（Chi-square Automatic Interaction Detector）算法是一种适用于分类问题的决策树算法。

它使用卡方检验来选择最优的划分特征，并根据卡方统计量的值来评估特征的重要性。

5. 梯度提升决策树（GBDT）算法：GBDT算法是一种集成学习算法，它将多颗决策树进行级联，每颗树的输出作为下一颗树的输入。

GBDT通过梯度下降的方式逐步优化模型的预测能力。

这些算法在决策树的构建过程中采用不同的策略和指标，适用于不同类型的数据和问题。

在实际应用中，可以根据数据特点和问题需
求选择合适的算法进行训练。

决策树模型常用算法决策树是一种常用的机器学习算法，它可以处理分类和回归问题。

在决策树模型中，通过对输入数据进行一系列的判断和分割，最终得到一个决策路径，用于预测新的数据。

决策树模型的构建过程中，常用的算法包括ID3、C4.5和CART。

下面将分别介绍这三种算法的原理和特点。

1. ID3算法ID3算法是决策树模型中最早被提出的算法之一。

它以信息熵为基础，通过计算每个特征的信息增益来选择最优的划分特征。

具体来说，ID3算法将数据集按照特征属性进行划分，并计算每个特征的信息增益，选择信息增益最大的特征作为当前的划分特征。

然后，对每个划分子集递归地应用ID3算法，直到满足终止条件。

ID3算法的优点是简单易懂，计算效率高。

但它对于缺失值敏感，并且容易产生过拟合的问题。

2. C4.5算法C4.5算法是ID3算法的改进版本。

与ID3算法不同的是，C4.5算法使用信息增益比来选择最优的划分特征，解决了ID3算法对于取值较多的特征有偏好的问题。

信息增益比考虑了特征的取值个数，使得算法更加公平地对待不同特征。

C4.5算法在特征选择上更加准确，同时能够处理缺失值。

但它的计算复杂度较高，对于大规模数据集不太适用。

3. CART算法CART算法是一种常用的决策树算法，既可以处理分类问题，也可以处理回归问题。

与ID3和C4.5算法不同的是，CART算法选择的划分特征是基于基尼指数的。

基尼指数反映了数据集的纯度，基尼指数越小，数据集的纯度越高。

CART算法通过计算每个特征的基尼指数，选择基尼指数最小的特征作为当前的划分特征。

然后，对每个划分子集递归地应用CART 算法，直到满足终止条件。

CART算法的优点是可以处理连续特征和缺失值，并且生成的决策树具有较高的准确性。

但它的计算复杂度较高，且生成的决策树结构相对复杂。

决策树模型常用的算法包括ID3、C4.5和CART。

不同的算法在特征选择和处理缺失值上有所区别，根据具体的应用场景选择合适的算法可以提高决策树模型的准确性和效率。

决策树的经典算法ID3与C45决策树是一种常用的机器学习算法，用于分类和回归任务。

决策树算法可以看作是一种基于树结构的分类方法，它将数据集拆分成若干个子集，每个子集对应一个属性测试条件，通过不断递归地划分数据集，最终形成一棵决策树。

经典的决策树算法包括ID3和C5，本文将对这两种算法进行介绍。

ID3（Iterative Dichotomiser 3）是由Ross Quinlan提出的，它是最早的决策树算法之一。

ID3算法采用了信息增益作为属性选择度量，通过计算每个属性的信息增益，选择信息增益最大的属性进行分裂。

我们计算每个属性的信息增益。

信息增益被定义为父节点与子节点之间的信息差异，计算公式为：Gain(S,A)=H(S)-sum(P(a) * H(S_a))其中，H(S)表示节点S的熵，P(a)表示属性A的取值a在节点S中出现的概率，H(S_a)表示子节点S_a的熵。

选择信息增益最大的属性作为当前节点的分裂属性。

根据当前节点的分裂属性将数据集划分成若干个子集，对每个子集递归地执行步骤1和步骤2，直到满足停止条件（例如子集中所有样本都属于同一类别，或每个属性都已使用过）。

C5算法是ID3算法的改进版，它使用了增益率作为属性选择度量，以解决ID3算法中偏好于选择取值较多的属性的问题。

增益率定义为信息增益与分裂信息的比值，分裂信息被定义为：split_info(S,A)=-sum(P(a) * log2(P(a)))其中，P(a)表示属性A 的取值a在节点S中出现的概率。

C5算法的步骤与ID3算法类似，但在选择分裂属性时优先考虑增益率较高的属性。

C5算法还引入了剪枝技术，通过设置一个置信度阈值来避免过拟合，从而生成更加健壮的决策树。

ID3算法和C5算法都是经典的决策树算法，它们在处理分类问题时具有较高的准确率和可解释性。

然而，这两种算法也存在一些局限性，例如对于连续属性和处理缺失值的处理能力有限。

后续的许多研究者对决策树算法进行了改进和优化，如CART、CHD、BOOSTING等，这些算法在处理复杂问题、提高分类准确率和处理连续属性方面做出了更多的探索和实践。

⽤于分类的决策树（DecisionTree）-ID3C4.5决策树（Decision Tree）是⼀种基本的分类与回归⽅法（ID3、C4.5和基于 Gini 的 CART 可⽤于分类，CART还可⽤于回归）。

决策树在分类过程中,表⽰的是基于特征对实例进⾏划分，将其归到不同的类别。

决策树的主要优点是模型可读、易于理解、分类速度快、建模与预测速度快。

本⽂主要介绍 Quinlan 在 1986 年提出的 ID3 算法与 1993 年提出的 C4.5 算法。

下⾯⾸先对决策树模型进⾏简单介绍。

决策树模型决策树是由树节点与边组成的，其节点有两种类型，内部节点和叶节点，内部节点表⽰⼀个特征或者属性，叶节点代表类别，如下如所⽰：图中可见根节点开始到叶节点的每条路径构建⼀条规则，内部节点的特征对应着规则的条件。

整棵树满⾜⼀个重要性质：每⼀个训练数据实例都被⼀条唯⼀的路径覆盖。

决策树的学习算法是做⼀个递归选择最优特征的过程，⽤最优特征对训练数据集进⾏分割，对分割后的两个⼦数据集，选择各⾃⼦数据集的最优特征继续进⾏分割，如果某个⼦数据集已经能够正确分类，则将该节点改为叶节点。

否则⼀直递归寻找最优特征知道没有合适特征为⽌。

决策树可能对训练数据有很好的分类能⼒，对测试数据却未必，这时可能是由于过度拟合训练数据，⽽降低了其泛化性，可以通过剪枝操作合并过分细分的叶⼦节点，将数据归并到⽗节点来增加其泛化性。

所以可以看到决策树⽣成过程对应着局部最优的特征选择，⽽剪枝对应着对模型进⾏全局调优。

对决策树模型有了初步认识之后，接下来将介绍决策树的建模与剪枝过程，这⾥重点介绍 ID3 与 C4.5 ，这两种形式的决策树学习均包括三个步骤：1）特征选择；2）决策树的⽣成；3）减枝。

接下来的段落围绕这三部分展开。

特征选择特征选择在于选取具有分类能⼒的特征，来提⾼决策树的学习效率，通常选择特征的标准为信息增益（ID3）与信息增益⽐（C4.5）。

决策树2-构造决策树的算法ID3、C4.51.决策树的本质if-then规则：决策树可以看做⼀个if-then规则的集合。

我们从决策树的根结点到每⼀个叶结点的路径构建⼀条规则。

并且我们将要预测的实例都可以被⼀条路径或者⼀条规则所覆盖，且只被⼀条路径或者⼀条规则所覆盖（互斥完备）。

2.构造决策树算法决策树学习的关键其实就是选择最优划分属性，希望划分后，分⽀结点的“纯度”越来越⾼。

那么“纯度”的度量⽅法不同，也就导致了学习算法的不同，这⾥我们讲解最常见的俩种算法，ID3算法与C4.5算法。

2.1ID3算法2.1.1算法思想我们既然希望划分之后结点的“纯度”越来越⾼，那么如何度量纯度呢？“信息熵”是度量样本集合不确定度（纯度）的最常⽤的指标。

在我们的ID3算法中，我们采取信息增益这个量来作为纯度的度量。

我们选取使得信息增益最⼤的特征进⾏分裂！那么信息增益⼜是什么概念呢？我们前⾯说了，信息熵是代表随机变量的复杂度（不确定度），条件熵代表在某⼀个条件下，随机变量的复杂度（不确定度）。

⽽我们这⾥说的的信息增益恰好是：信息熵-条件熵。

我们⽤下⾯这个公式计算⼀个系统的熵：在这个公式中，c 代表类别或属性的总数，p_i 代表属于第 i 类的样本所占的⽐例。

举个例⼦来说，我们有两个类别：红⾊（R）和蓝⾊（B）。

第⼀个袋⼦⾥有 25 块红⾊巧克⼒。

巧克⼒总数是 50。

因此，p_i=25/50。

蓝⾊类别也是这样处理。

把这些值代⼊熵⽅程，我们得到以下结果：信息增益的定义为：S 代表整个样本集，A 代表我们想要分割的属性。

|S| 代表样本数量，|Sv| 表⽰当前属性 A 值的样本数量。

信息增益表⽰得知属性 a 的信息⽽使得样本集合不确定度减少的程度那么我们现在也很好理解了，在决策树算法中，我们的关键就是每次选择⼀个特征，特征有多个，那么到底按照什么标准来选择哪⼀个特征。

对于ID3算法来说，这个问题就可以⽤信息增益来度量。

如果选择⼀个特征后，信息增益最⼤（信息不确定性减少的程度最⼤），那么我们就选取这个特征。

决策树（ID3,C4.5,CART）原理以及实现决策树决策树是⼀种基本的分类和回归⽅法.决策树顾名思义,模型可以表⽰为树型结构,可以认为是if-then的集合,也可以认为是定义在特征空间与类空间上的条件概率分布.[图⽚上传失败...(image-2e6565-1543139272117)]决策树的中间节点可以看做是对⼀种特征的判断,也是符合上⼀次判断特征某种取值的数据集,根节点代表所有数据集;叶⼦节点看做是判断所属的类别.决策树学习通常包括3个步骤: 特征选择. 决策树⽣成和决策树剪枝.⽬前常⽤的决策树算法有ID3, C4.5 和CART.特征选择在数据集中的所有特征列表中,选择分类效果最好的特征,或者说让分类效果尽可能的"纯",通俗的说就是让划分的每个结果的尽可能属于同⼀个类别,都是⾃⼰⼈. 那么, 分类效果最好,或者说纯度,怎么定义? ⽤什么衡量特征的分类效果呢? 不同的决策树算法采⽤不同的衡量指标.⽐如说,ID3采⽤信息增益,C4.5采⽤信息增益⽐率,CART分类回归树当⽤于分类时,采⽤Gini指数,⽤于回归问题时采⽤均⽅差差[计算划分之前的均⽅差,划分之后的均⽅差,再做差运算]. ⽆论是哪种指标,本质上,都是⽐较⽤特征划分前后两种状态之间的差异变化,变化越明显越好,⽽各种指标是对这种差异变化的量化. 但是不同的指标会有不同的倾向性,这种倾向性从指标计算公式上可以发现,⽽倾向性⼜会引出不同的问题,进⽽产⽣不同的优化⽅法.另⼀⽅⾯,最佳的特征的选择,总是需要对所有特征进⾏⼀次遍历,分别计算每种特征的划分效果,⽐较求最优特征的最佳特征划分值.信息增益计算信息增益之前,需要先引出信息熵的概念.熵是信息论中的⼀个⾮常重要的概念,信息熵的计算,对于⼀个数据集D,其中N中类别的第k类样本所占⽐例为pk,则数据集D的信息熵:\(Ent(D)= -\sum_{k=1}^{N}p_k log_2 p_k\)从信息熵的计算公式可以知道,Ent(D)的取值范围在[0, \(log_2n\)], 最⼩,或者说节点最纯时[都是同⼀个类别],为0;最⼤,最混乱时[每种类别⽐例都相等],为\(log_2n\).知道了信息熵的计算公式,那么划分前,计算数据集的信息熵, 依据特征f的n种取值划分后的n个节点,分别计算信息熵,然后依据各个节点数据集的⽐率,加权平均,计算划分后的总的信息熵,前后两次做差,得到这次划分的信息增益,⽤来衡量特征f的划分效果如何.信息增益:信息增益表⽰得知特征f的信息⽽使得类Y的信息的不确定性较少的程度.\(Gain(D,f) = Ent(D) - \sum_{i=1}^{n} \frac{|D_i|}{|D|}Ent(D_i)\)信息增益越⼤,特征划分效果越好. 信息增益指标,趋向于选择取值数⽬多的特征.[个⼈观点:特征取值越多,划分到每个⼦节点的数据越少,⼀定程度上,纯度越⾼,混乱程度越低,熵取值越⼩,进⽽,信息增益越⼤.⽐如说,ID特征,因为ID是唯⼀的,所有划分到每个ID取值节点上也就⼀个数据点,纯度100%,熵为0.]信息增益⽐率\(GainRatio(D,f)=\frac{Gain(D,f)}{IV(f)}\)其中,\(IV(f) = -\sum_{v=1}^{V}\frac{|D_v|}{|D|}log_2\frac{|D_v|}{|D|}\)\(D_v\)表⽰特征f取值为v的数据⼦集.因为信息增益会倾向于选择特征取值多的特征,所以,我们对多取值特征进⾏惩罚,除以特征f的固有值[或者说特征f的信息熵,f的信息熵越⼤,相应f的取值情况越多,惩罚⼒度越⼤].Gini指数假设数据集D有K个类,样本点属于第k类的概率为pk,则概率分布的基尼指数定义为:\(Gini(D)=\sum_{k=1}^Kp_k(1-p_k) =1 - \sum_{k=1}^Kp_k^2\)知道了gini指数的计算公式,计算划分前的gini指数,划分后,计算各个节点的gini指数值,然后根据划分后⼦节点的数据⽐例进⾏加权求和,得到划分后的总gini指数,最后对两次结果做差,得到特征f的划分效果, 差值越⼤,分类效果越好.均⽅差MSE[和,不平均]和分类时相似,计算划分前节点的均⽅差,划分后计算⼦节点的均⽅差,依据数据⽐例加权平均,再计算两次结果差值,差值越⼤越好.MAE也可以⽤作特征选择指标,和MSE类似.决策树⽣成决策树本质上也是⼀棵树,所以符合数据结构中树的⼀般性构造过程,也就是递归.既然是递归构建过程,⾸先要明⽩的是递归终⽌条件,否则就会陷⼊死循环.那么决策树的终⽌条件是什么呢?决策树中符合终⽌条件时,停⽌继续划分,⽣成叶节点.如果是分类树:1. 如果节点数据全是同⼀类别,停⽌递归[没有必要了,都是⾃⼰⼈];2. 如果特征列表为空,停⽌递归[在分类问题中,⼀般情况下,每种划分特征只会⽤⼀次,⽤完就扔了---负⼼汉];3. 如果所有样本在所有特征上取值都相同,停⽌递归[特征没⽤,不具有区分度---所有特征上取值都相同,千篇⼀律]如果是回归树,回归树通常会设定⾃定义的参数,⽐如均⽅差变化最⼩值,每个节点容忍的最⼩样本数,相应的条件:1. 均⽅差变化太⼩[⼩于预定义的阈值];2. 划分后节点的样本量太少[⼩于预定义的阈值,⽐如只有2,3个,⼩猫两三只没有必要继续划分了];[终⽌条件]检测数据集中的每个⼦项是否属于同⼀分类,or 特征集为空：If so: return 类标签Else:寻找划分数据集的最好特征（--基于信息增益）划分数据集创建分⽀结点for 每个划分的⼦集调⽤⾃⼰，并增加返回结果到分⽀结点中return 分⽀结点上⾯伪代码中存在⼀个问题, 类标签怎么确定?如果叶⼦节点都属于同⼀类别,那么给定所属类别即可;如果叶⼦节点数据属于不同的类别,⼤家进⾏投票决定,服从多数⼈的利益[少数服从多数].树剪枝因为在决策树的构建过程中,可能会存在过拟合现象,或者说决策树深度太深,太过于复杂;因此,我们可以对决策树进⾏剪枝处理.剪枝⼜分为预剪枝和后剪枝.预剪枝是指在决策树⽣成过程中,对每个节点在划分前先进⾏估计,如果当前的划分不能带来决策树泛化性能的提升[泛化性能可以⽤错误率,或者说均⽅差衡量],则停⽌划分将当前节点标记为叶节点.后剪枝过程是⼀个不断尝试的过程:找到叶⼦节点,尝试合并[将叶⼦节点的双亲变成叶⼦节点],⽐较合并前后的变化效果.变化效果需要定量分析,这个数据量指标分类问题可以使⽤错误率,回归树可以使⽤均⽅差, ⽽指标的计算需要数据,因此我们需要⼀定的测试数据,然后使⽤测试数据在已经⽣成的决策树上进⾏不断测试,假如合并后⽐合并前效果好,分类问题上就是错误率降低了,回归问题上均⽅差减少了,我们就进⾏合并处理[或者说是剪枝处理].其他问题决策树使⽤范围,或者说对数据集的要求: 标称数据或数值型数据.本质上,决策树只适⽤于标称型数据[也就是离散数据],但如果是连续数据[在特征取值上连续],我们需要进⾏离散处理.不同类型的决策树处理问题不同,有的决策树需要对数据进⾏预先离散化处理;但有的决策树本⾝可以处理连续数据.决策树在⽣成过程中会遇到各种各样的问题.有数据集的问题,也有决策树本⾝的问题,⽽决策树本⾝也有⾃⼰的适⽤范围,不可能适⽤于所有问题[⼀招鲜吃遍天impossible].⽐如说:连续数据: 离散化处理;空缺数据: 如果在某个特征上数据存在空缺值,怎么处理? 我们可以先将取特征上⾮空的数据⼦集,当做⾮空数据处理,然后将特征取值为空记录按照⼦节点数据的⽐率划分到所有⼦节点上.etc.具体问题具体分析,依据不同的任务,数据集的不同特点选择适合的算法模型.代码实现欢迎fork,star.。

决策树ID3与C4.5算法原理1. 决策树决策树（decision tree）是⼀种基本的分类与回归⽅法（本⽂主要是描述分类⽅法），是基于树结构进⾏决策的，可以将其认为是if-then规则的集合。

⼀般的，⼀棵决策树包含⼀个根节点、若⼲内部节点和若⼲叶节点。

其中根节点包含所有样本点，内部节点作为划分节点（属性测试），叶节点对应于决策结果。

⽤决策树进⾏分类，是从根节点开始，对实例的某⼀特征进⾏测试，根据测试结果，将实例分配到其⼦节点，若该⼦节点仍为划分节点，则继续进⾏判断与分配，直⾄将实例分到叶节点的类中。

若对以上描述不太明⽩，可以结合以下图进⾏理解。

根据以上决策树，现在给你⼀个实例：{⾊泽：青绿，根蒂：稍蜷，敲声：清脆，纹理：清晰，脐部：稍凹，触感：光滑}，来判断该⽠是否是好⽠。

其过程是：脐部（稍凹）-->根蒂（稍蜷）-->⾊泽（青绿）-->好⽠。

以上是由决策树来进⾏分类的过程。

⽽决策树的学习（构建）通常是⼀个递归地选择最优特征的过程。

那么构建决策树时如何选择特征作为划分点（即选择哪个特征作为根节点或者选择哪个特征作为⾮叶⼦节点）？当训练数据量⼤、特征数量较多时构建的决策树可能很庞⼤，这样的决策树⽤来分类是否好？ 由这些问题我们可以知道，构建决策树的三个要点： （1）特征选择 （2）决策树的⽣成 （3）决策树修剪2. ID3算法 基于ID3算法的决策树构建，其选择特征的准则是信息增益。

信息增益（information gain）表⽰得知特征 XX 的信息⽽使得类 YY 的信息的不确定性减少的程度。

也就是说，信息增益越⼤，通过特征 XX ，就越能够准确地将样本进⾏分类；信息增益越⼩，越⽆法准确进⾏分类。

在介绍信息增益之前，我们需要先对熵进⾏⼀下讲解。

2.1 熵（Entropy） 熵是度量样本集合纯度最常⽤的⼀种指标，它是信息的期望值。

我们⾸先了解⼀下什么是信息。

由《机器学习实战》中定义：如果待分类的事务可能划分在多个分类之中，则符号（特征） kk 的信息定义为：l(k)=−log2p(k)l(k)=−log2p(k)其中 p(k)p(k) 为选择该分类的概率。

数据挖掘十大算法及经典案例一、数据挖掘十大经典算法国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 2006年12月评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART。

不仅仅是选中的十大算法，其实参加评选的18种算法，实际上随便拿出一种来都可以称得上是经典算法，它们在数据挖掘领域都产生了极为深远的影响。

（一）C4.5C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法。

C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：1. 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；2. 在树构造过程中进行剪枝；3. 能够完成对连续属性的离散化处理；4. 能够对不完整数据进行处理。

C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。

其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。

（二）The k-means algorithm 即K-Means算法k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k < n。

它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。

它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。

（三）Support vector machines支持向量机，英文为Support Vector Machine，简称SV机（论文中一般简称SVM）。

它是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。

支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。