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

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

1. 输入一个数据

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

3. 如果分完数据后发现

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

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

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

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

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

常见的准则有两种，分别是熵和 Gini 系数。这里就主讲实现（Again，我会先讲一个相对朴素的实现，而把支持样本权重的版本放在后面）：

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

 

1.  

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

   2. 输入的 labels 是标签向量

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

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

2. 熵与条件熵

   1. 利用 labels 和 counters 计算

   2. 这里支持用户自己输入各类别的出现次数；如果没有输入，就用内置的类别次数代替
      eps 则是为了数值稳定

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

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

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

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

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

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

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

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

5. 信息增益。这是决策树生长的重点，但有了上面两个函数之后，根据定义的话、直接条件熵减去熵就行（或者更宽泛地说、是混乱程度减去条件混乱程度），最多再做一些小的改动。相信聪明的观众老爷们可以轻松地完成最朴素的实现，所以在这里我就不细讲怎么定义 info_gain 了，等到讲比较复杂的模型时再补吧~
   顺便也可以当做作业和练习呢~
   其实主要是因为懒呢~（被 pia 飞）
   ========== 更新 ==========
   这里提供一个根据 ID3 算法的信息增益实现，C4.5 和 CART 的话会在后面讲~
   

扫一扫获取最新精彩内容与学习资料 

继续阅读：

人工智能技术网 倡导尊重与保护知识产权。如发现本站文章存在版权等问题，烦请30天内提供版权疑问、身份证明、版权证明、联系方式等发邮件至1851688011@qq.com我们将及时沟通与处理。！：首页 > 大数据 » 从零开始学人工智能(13)--Python · 决策树（一）· 准则