# 数据基础算法——分类

通过[聚类算法](数据基础算法——聚类.md)，你应该知道了我们经常把一些复杂的事物通过聚类来进行简化处理。
但是，不一定所有事物在一开始我们都要把它们进行聚类。有的东西我们一开始就知道一些正确和错误事例，
例如我们知道什么是好人什么是坏人，然后得让孩子慢慢明白好人和坏人的差别，让孩子去学会鉴别哪些人是好人还是坏人。

那如果我已知一些条件和试验的结果，具体怎样能让计算机像人一样发现其中的这个逻辑呢？我来给你分享一个最常见的分类算法 `C4.5——决策树`。

我们可以把一个分类器抽象成一棵倒着生长的树，它就是一些不同条件走向了不同的分支，最后走到叶子得出一个分类的结果。
比如我们设计一棵树来区分鸡、鸭子、鹿和马，我们可以用下面这个树来进行表示分类。

![](img/data-thinking/分类1.png)

任何一个人或者机器拿到这棵树，都可以根据这个规则把这些动物区分出来，我们把这棵树叫做决策树。顾名思义，根据这棵树我们就可以做出决策了。
**这棵树就是这个分类算法的最核心的部分**。

但是我们怎么能让计算机把这棵树生成出来呢？关键就在于**我们应该拿什么条件去判断这棵树上的分支节点**。

哪些属性是有用的，哪些属性是没用？究竟应该先拿哪个条件作为最初始的判断条件呢？这些问题的答案就在我下面要给你介绍的 C4.5 决策树算法中。

C4.5 决策树算法我把它也叫做“逐级找领导”算法。

这个分类算法的整体逻辑很简单，最开始计算机也不知道用哪个条件区分出来最好，于是干脆把每个属性都当“领导”全试一遍，能够做出最明显区分的就当这一级的领导，
然后逐级“找领导”，最后再“剪枝”。具体的步骤如下。

### 第 1 步，我们把每一个属性都当领导全试一下

你参考下面这个图会更直观一些，也就是把各种属性测试一遍。

![第 1 步](img/data-thinking/分类2.png)

### 第 2 步，把按这个情况分群出来的差异性通过一个叫信息熵的指标计算出来

信息熵这个词在算法里会经常用到。它表示每一个消息里面所包含信息的平均量有多少。
简单来说，言简意赅的人说的话每个字信息熵比较高，废话连篇的人说的每个字信息熵就比较小。
在这里，我们希望根据这个领导给出的决策逐步减少下一步整体的信息熵，这样将来的小领导更好干活，直到最后做出接近事实的分类。

### 第 3 步，我们要比对一下这几个领导做完决策之后各自信息熵的大小

我们发现这些动物全都长毛也全都有眼睛，用这两个属性来当领导做决策完全没用。那这两个属性我们就不会选到决策树里。
同时，长几条腿这个“领导”的信息熵最小，我们就把它放在第 1 个节点的大领导位置上。即取熵小的。

### 第 4 步，大领导有了，现在我们需要一些小领导

我们来重复前面的 123 步，你就有可能会画出下面的这样的一棵树。

![第 4 步](img/data-thinking/分类3.png)

### 第 5 步，精简领导班子

上面的这棵决策树看上去还是有点冗余，怎么办呢？决策树算法里面还有一个东西叫做“剪枝”，就是把一些没有用的节点去掉。
经过剪枝之后，就得到了我们最终要的这个决策树。

![第 5 步](img/data-thinking/分类4.png)

最终我们可以用一组测试数据来验证一下我们这棵树分得好不好，衡量的标准就是[精准率和召回率](如何评判指标好坏.md)。
关于精简领导班子这个点，我们要把它减恰到好处，才最能适应现实状况。

## 参考资料

- [《数据分析思维课》5 | 初识分类算法：分而治之，不断进化](https://time.geekbang.org/column/article/413734)