四站合一网站建设公司广州网络seo公司

二、决策树

决策树也是机器学习算法中的入门算法，算法原理简单效果良好，尤其是以树模型为基础的各种集成算法，更是功能强大，预测准确，还适用各种数据。决策树作为树一族算法的基模型，我觉得非常有必要认真梳理一下。

（一）决策树的基本原理

语言太苍白，看下图：

1、左边的表格是和决策树算法匹配的数据形式，前面讲KNN时，一开始就是说，了解一个算法之前首先要了解它的数据。决策树算法的数据也是一个二维表格数据，就是有行有列，行表示样本，列表示特征，当然还得有标签列，因为决策树也是一个有监督模型，没标签是没法建树的。这是决策树的数据结构，你别拿一个图片数据说用决策树算法来跑跑，那就见笑了，你必须还得仔细思量一下你的图片数据如何转化成二维表格数据。

2、右边的倒树就是算法从左边数据中学习完毕后创建的单颗决策树，就是我们建立的模型、算法，我们就是用这棵倒树来预测新样本的。

3、你仔细看看，是不是发现，右边的树其实就是对左边表的描述、归纳和总结！对的，是的，所以创建决策树就是对数据规律的学习和挖掘，或者说右边的决策树本质就是左边数据的另外一种表示形式。所以我们创建决策树的本质就是挖掘数据的规律，或者说我们创建决策树的本质就是把二维表格数据用树的形式来表示！

4、你再看是不是发现，树的椭圆结构都是表的特征名称，这些椭圆叫决策树的节点，第一个是根节点，其他的都是中间节点。
树的方框部分都是标签的类别，就是样本的标签，这些方框也是决策树的节点，但它叫叶子节点。

5、你再看，是不是左边表格中的所有样本(10个)都一个不拉得分到了右边决策树的叶子节点！是的，右图叶子节点下面的灰色数字就是对应的样本索引号。就是不管哪个样本，不管你的特征取值是什么，决策树我都会把你分到我的一个叶子节点上，然后给你打个标签！言外之意，决策树是通过递归的方式实现的，这个只有自己手动写决策树算法是才有真正的体会。

6、那么，对应一个不变的数据，就是左边的二维表格数据不变，是不是可以生成一棵唯一的右边的决策树呢？非也！我可以生成很多很多棵不同的倒树！比如我的根节点可以是婚姻情况这个特征啊，我从婚姻情况开始分支生成树难道不可以嘛？是滴，是可以的，那同理我就也可以从年收入开始生，甚至我用ID号生也可以，其他特征都不用，只用ID号，根节点是ID号，下面长10个叶子节点，这也是棵树啊！所以一个表格数据是可以用很多很多棵树结构来表示的。所以后续如何生成一棵最优的树就成了一个大命题。也所以一棵树不行，我建一片森林可否，于是有了后来的集成算法随机森林。

7、那么，到底哪棵树好呢？那就看哪棵树能帮助我们更好的预测新样本了。比如6中的按照ID列生成的10支树，显然是不能帮我们预测新样本的，再来一个ID号是11的样本，那这棵树是不是就懵了，就判断不出11号到底能不能按期偿还债务。再比如上右图的树，是否拥有房产，总共10条样本，也就是10个人，有3个拥有房产，而且3个人都是可以偿还的标签。如果说10个人就是全部样本，那只要你拥有房产，你就100%会按期偿还债务。即使第11号是总体中的新样本，那只要这个11号拥有房产，我们就可以推断出它100%概率会按期还款。如果11号没有房产，即使我们也不知道11号婚姻状况和年收入，那我们也可以推断它4/7的概率是按期偿还，3/7的概率是违约，当然如果再知道11号的婚姻状况和年收入等更多信息，那我们推断它还不还款的概率就更精准了。当我们精准的知道一个还款的概率，我们是不是就可以精准的放贷了。所以上图的决策树帮助了我们进行决策。也所以一颗优秀的树是可以辅助决策的，而一颗不优的树就相当于瞎猜。

8、即使上图的决策树可以帮我们进行决策，那那棵树就是最优的树吗？不一定！在都能帮我们做决策的时候，我们还得找一个最优的树，比如谁的决策最准、谁的决策决策最快，所以这就涉及到决策树生成过程中的一些细节和优化剪枝的一些细节。这里先把一个结论放这儿：即使我们追求的是最优的树，但是在递归的建树过程中，我们只能做到局部最优，无法做到全局最优。而局部最优不一定就是全局最优。有人说“从所有可能的决策树中选取最优决策树是个NP完全问题”。就是无法做到吧，那我们也必须有底线，就是至少要生成一颗有效的树吧。

9、我们继续梳理如何生成一棵有效的决策树？前面6说了，一个二维表格数据可以生成很多很多个不同的树，那是我以我作为人类的眼睛和大脑看到左边的表格数据后做出的树模型的结构，那要用算法生成一棵树，算法只知道数字的加减乘除和if else等判断，所以一个算法工程师要写出一个决策树模型，首先左边的二维表格数据中特征名称都要用0123代替了，每个特征下的取值，比如“是”与“否”的这种非数值型的都得先处理成0123这种数字编码型的，算法工程师才能开始写算法。
其次，算法工程师要继续考虑的是，我以什么依据来提问特征，就是我是从“拥有房产”这个特征开始提问还是从“婚姻情况”开始提问，那对硅基生物来说，你得给它指定规则或者给出计算公式。所以比如针对大型的二维表格数据，比如特征有数万个的情况下，算法工程师是可以给出你随机的规则的，就是你从这万多个特征中随机挑一个特征开始生长吧，所以我们眼花缭乱的决策树算法中就有一个算法叫Extra Tree, 以后你看到Extra Tree你就知道这个算法和别的算法最大的不同就是随机挑选特征进行分支。当然随机太随意了啊，我们必须给出一个计算公式，按照公式计算出哪个特征就用哪个特征来分支，那究竟用什么公式能表示你的特征选择呢？在纠结公式之前先想想我们的目的是什么？我们的目的就是我用这个特征分裂，会把所有训练样本分成的子样本的标签不纯度降低得最多，那我就用这个特征开始分。那用啥公式来计算标签的不纯度呢，那这种事情就不是我们一般人可以想得出的，这种事情一般都是伟人做的，最早就是一个叫香农的大牛，它想出来一个叫“熵”的公式来衡量不纯度，当然后来随着技术的发展，后人又发明了用基尼指数来衡量。所以现在市面上主流的决策树算法：ID3.5、C4.5、CART树，就是用了不同的计算不纯度方式而取得不同名字。其中ID3.5用的是信息增益，而信息增益的底层就是熵，C4.5用的是信息增益率，显然信息增益率是信息增益的改进版，CART树则用的是基尼指数来衡量。

10、第9点虽然说了很多，那按第9点的公式逐个计算每个特征并筛选出要分裂的特征，还是会遇到一些问题。问题1，如果这个特征是个连续特征呢，连续特征我怎么分裂并计算个子样本的不纯度，这里就牵扯到连续特征的离散化技术，具体怎么做，后面我单独再展开讲，总之你现在只要知道这个问题被克服了&