调频96.8有一种游戏：出题者写下一件东西

调幅96.8有一种游戏：游戏中，出题者写下一件东西，其他人须要猜出这件东西是哪些。其实，倘若游戏规则仅此而已的话，几乎是难以猜进去的，由于问题的规模太大了。为了增加游戏的难度，答题者可以向出题者询问题，而出题者应当精确回答是或则否，答题者根据回答提出下一个问题，假若才能在指定次数内确定谜底，即为胜出。 #

我们先试验一下，今天我早已写下了一个质点，而你和我的问答记录如下： #

在后面的游戏中，我们针对性的提出问题，每一个问题都可以将我们的答案范围缩小，在提问中和回答者有相似知识背景的前提下，得出答案的难度比我们想像的要小太多。

在每一个节点，根据问题答案，可以将答案界定为左右两个分支，左分支代表的是Yes，右分支代表的是No，但是为了简化，我们只画出了其中的一条路径，并且也可以显著看出这是一个树状结构，这便是决策树的原型。

#

决策树算法 #

我们面对的样本一般具备这些个特点，正何谓对事物的判定不能只从一个视角，那怎么结合不同的特性呢？决策树算法的思想是，先从一个特点入手，就犹如我们里面的游戏中一样，倘若未能直接分类，那就先按照一个特性进行分类，但是分类结果达不到理想疗效，并且通过此次分类，我们的问题规模变小了，同时分类后的子集相比原先的样本集愈发便于分类了。之后针对上一次分类后的样本子集，重复这个过程。在理想的状况下，经过单层的决策分类，我们将得到完全纯净的子集，也就是每一个子集中的样本都属于同一个分类。由这个分类的过程产生一个树状的裁定模型，树的每一个非树叶节点都是一个特性分割点，树叶节点是最终的决策分类。 #

后面我们介绍决策树算法的思想，可以简略归纳为如下两点：

#

在第一个方法中，我们还要考虑的一个最重要的策略是，选用何种样的特性可以实现最好的分类疗效，而何谓的分类疗效优劣，必定也须要一个评价的指标。 #

直观来说就是集合中样本所属类型比较集中，最理想的是样本都属于同一个分类。样本集的含量可以用熵来进行考量。 #

在信息论中，熵代表了一个系统的纷乱程度，熵越大，说明我们的数据集含量越低，当我们的数据集都是同一个类型的时侯，熵为0，熵的估算公式如下： #

其中，P(xi)表示机率，b在此处取2。例如抛纸币的时侯，正面的机率就是1/2，背面的机率只是1/2，这么这个过程的熵为：

可见，因为抛纸币是一个完全随机风波，其结果正面和背面是等机率的，因此具备很高的熵。

如果我们观察的是纸币最终飞行的方向，这么纸币最后往下落的机率是12024决策树应用在哪些方面，往天上飞的机率是0，带入前面的公式中，可以得到这个过程的熵为0，因此，熵越小，结果的可预测性就越强。在决策树的生成过程中，我们的目标就是要界定后的子集中其熵最小，那样后续的的迭代中，就更容易对其进行分类。 #

倘若是卷积过程，这么就须要 #

起草数组的停止规则。

#

在两种状况下我们停止逐步对子集进行界定，其二是界定早已达到可以理想疗效了，另外一种就是逐步界定收效甚佳，不值得再继续了。 #

用专业术语小结中止条件有以下几个： #

子集的熵达到信噪比 #

子集规模够小 #

逐步界定的增益大于信噪比

#

其中，条件3中的增益代表的是一次界定对数据含量的提高疗效，也就是界定之后，熵降低越多，说明增益越大，这么此次界定也就越有价值，增益的估算公式如下： #

上述公式可以理解为：估算此次界定后来两个子集的熵之和相对界定之前的熵降低了多少，还要留意的是，估算子集的熵之和还要乘上各个子集的权重，权重的估算方式是子集的规模占分割前父集的比重，例如界定前熵为e，界定为子集A和B，大小分别为m和n，熵分别为e1和e2，这么增益就是e–m/(m+n)*e1–n/(m+n)*e2。 #

决策树算法实现 #

有了上述概念，我们就可以开始开始决策树的训练了，训练过程分为：

选用特性，分割样本集

#

估算增益，假如增益够大，将分割后的样本集作为决策树的子节点，否则停止分割

数组执行上两步

上述方法是根据ID3的算法思想（根据信息增益进行特性选用和分裂），除此此外也有C4.5以及CART等决策树算法。

#

1
2
3
4
5
6
7
8
9
10
11
12
13
1class DecisionTree(object):

2 ? ?def fit(self, X, y):

3 ? ? ? ?# 依据输入样本生成决策树

4 ? ? ? ?self.root = self._build_tree(X, y)

5 

6 ? ?def _build_tree(self, X, y, current_depth=0):

7 ? ? ? ?#1. 选取最佳分割特征，生成左右节点

8 ? ? ? ?#2. 针对左右节点递归生成子树

9 ? ? ?

10 ? ?def predict_value(self, x, tree=None):

11 ? ? ? ?# 将输入样本传入决策树中，自顶向下进行判定

12 ? ? ? ?# 到达叶子节点即为预测值

13
 
#
 

在上述代码中，实现决策树的关键是数组构造子树的过程，为了实现这个过程2024决策树应用在哪些方面，我们还要做好三件事：分别是 #

节点的定义， #

最佳分割特性的选择， #

数组生成子树。

#

1
2
3
4
1作者：ZPPenny ?

2链接：http://www.jianshu.com/p/c4d0837e9439 ?

3來源：简书

4
 # 

#

小结 #

决策树是一种简略常用的 #

分类器，通过训练好的决策树可以实现对未知的数据进行高效分类。 #

决策树模型具备较差的可读性和描述性，有助于辅助人工剖析； #

决策树的分类效率高，一次建立后可以反复使用，并且每一次预测的估算次数不少于决策树的深度。

#

决策树还有其劣势：

#

对于连续的特性，比较无法处理。

对于多分类问题，估算量和精确率都不理想。 #

在实际应用中，因为其最底层树叶节点是通过父节点中的单一规则生成的，因此通过自动更改样本特性比较容易误导分类器，例如在拦击电邮辨识系统中，用户或许通过更改某一个关键特性，就可以骗过垃圾电邮辨识系统。从实现上来讲，因为树的生成选用的是数组，随着样本规模的减小，估算量以及显存消耗会显得越来越大。 #

过拟合只是决策树面临的一个问题，完全训练的决策树(未进行泥塑，未限制Gain的信噪比)才能100%精确地预测训练样本，由于其是对训练样本的完全拟合，然而，对与训练样本以外的样本，其预测疗效或许会不理想，这就是过拟合。 #

解决决策树的过拟合，不仅上文说到的通过设置Gain的信噪比作为停止条件此外，一般还须要对决策树进行修剪，常用的修剪策略有

#

１.Error：消极错误修剪

２.Error：最小偏差修剪

３.Cost-：代价复杂修剪 #

４.Error-Based：基于错误的修剪，即对每一个节点，都用一组检测数据集进行检测，假如分裂以后，才能减少错误率，再继续分裂为两棵子树，否则直接作为树叶节点。

#

５.Value：关键值修剪，这就是上文中提及的设置Gain的信噪比作为停止条件。 #

以最简略的形式展示了ID3决策树的实现方法，假如想要了解不同类别的决策树的差异，可以参考这个链接。 #

另外，关于各类机器学习算法的实现，强烈推荐参考库房ML-From-，下载代码然后，通过pip-r.txt安装依赖库即可运行代码。

posts:决策树算法生态圈介绍ASP.NETCore皇爷务实操系列数据挖掘十大精典算法整理 #