从零开始学人工智能-Python·决策树（一）·准则

作者：射命丸咲Python 与 机器学习 爱好者

知乎专栏：https://zhuanlan.zhihu.com/carefree0910-pyml

本章用到的 GitHub 地址：

https://github.com/carefree0910/MachineLearning/blob/master/Zhihu/CvDTree/one/CvDTree.py

本章用到的数学相关知识和Python相关知识地址：

https://zhuanlan.zhihu.com/p/24482628?refer=carefree0910-pyml & https://zhuanlan.zhihu.com/p/24501172?refer=carefree0910-pyml

这一章主要打算用大白话说一下决策树是什么，然后介绍一个算法中的核心辅助结构——Cluster 的实现（我也不知道中文叫什么我也不知道为什么当初脑子里第一个蹦出来的就是这个名字）（逃）

决策树，顾名思义，就是用来决策的树（废话）。可以这样去想一个决策树的决策过程：

输入一个数据

根据数据的某个特征来把数据分成好几份

如果分完数据后发现

某堆数据里面某一个类别的数据占相当大多数，就不再分隔这堆数据、直接输出类别

某堆数据还很“混乱无序”，那么就这堆数据就要继续分下去（转第 2. 步）

大概就这三步。可以发现，大部分时间都是根据某个“准则”来进行操作的，所以怎样选择这个准则就成了至关重要的问题

我们同时还可以发现，这个过程是个递归过程。通俗点来说，就是整个过程都是对同一类物体做的同一系列操作

以上两个发现对应着两个核心。这一章我们就先讲第一个核心——准则

常见的准则有两种，分别是熵和Gini 系数。它们的定义可以参见这篇文章（地址：https://zhuanlan.zhihu.com/p/24482628?refer=carefree0910-pyml），这里就主讲实现（Again，我会先讲一个相对朴素的实现，而把支持样本权重的版本放在后面）：

预处理数据，准备好接下来可能要用到的变量

其中：

输入的 data 是 n x d 维的；n 代表有 n 个数据，d 代表有 d 个维度

输入的 labels 是标签向量

Counter 是内置库的功能，用于数 labels 中各个类别的出现次数

base 是计算熵的时候对数的底，基本可以不管

熵与条件熵

利用 labels 和 counters 计算熵

这里支持用户自己输入各类别的出现次数；如果没有输入，就用内置的类别次数代替

eps 则是为了数值稳定

利用上述 ent 函数计算相对熵（建议先知道定义是什么再看……）

看上去很复杂，其实就四点：

获取指定维度数据的所有特征

根据这些特征将原数据切分成若干份

将这几份数据分别喂给一个 Cluster 并利用上面第 1. 步定义的 ent 函数算出熵

把这些熵按定义弄出一个条件熵

Gini 系数，这个实现起来比较方便、因为形式比较简单

同样支持用户自己输入各类别的出现次数

信息增益。这是决策树生长的重点，但有了上面两个函数之后，根据定义的话、直接条件熵减去熵就行（或者更宽泛地说、是混乱程度减去条件混乱程度），最多再做一些小的改动。相信聪明的观众老爷们可以轻松地完成最朴素的实现，所以在这里我就不细讲怎么定义 info_gain 了，等到讲比较复杂的模型时再补吧~

顺便也可以当做作业和练习呢~

其实主要是因为懒呢~（被 pia 飞）

========== 更新 ==========

这里提供一个根据 ID3 算法的信息增益实现，C4.5 和 CART 的话会在后面讲~

相当直观吧 ( σ'ω')σ

那么以上就把准则的实现大概说明了一下，接下来就要处理第二个核心问题——递归生成、裁剪我们的决策树了

希望观众老爷们能够喜欢~