{高中生能看懂的}再见香农，决策树的本质是什么
本文首发于CSDN @Ai酱 的博客，转载请注明出处。
机器学习算法看起来那么多，其实套路就一个。那么多算法是背不下来的，自己知道他们怎么根据套路想出来的就可以。
套路就三步：
套路想出来的就可以。
套路就三步：选取一种数学模型来对数据进行分类预测。线性回归是用直线这个数学模型来划分数据。逻辑回归是用sigmoid这个函数来输出一个概率值。决策树是想用一个二叉树来对数据分类（二叉树也是一个数学模型）
根据
2.中的评估模型来遍历找让评估指标达到最高的参数。如果可以遍历那就遍历，如果参数是无法遍历那就用梯度下降（或者其他反正是用来求比较好的参数的）。其实有时候找到不一定是最好的参数，但是能用。差不多就行。就像你开车，没必要精确转方向盘转到16°，你只需要转到差不多就够了。
决策树的本质
决策树本质就是想在每个特征上找一个阈值，根据这些阈值来对数据分类。这个阈值是通过遍历来找到的。
比如：
我想根据{年龄，身高，体重}来判断一个人性别{男，女}。
给模型输入的数据长这样：
{年龄，身高，体重，标签} {10，100，60，男} {45，155，110，女} {21，171，114，男} ... ...
然后决策树是这么做的：
剩下没确定阈值特征们 = {年龄，身高，体重}。
只要剩下没确定阈值特征们不为空。那么就遍历剩下没确定阈值特征们的特征。
下面是遍历的过程：
剩下没确定阈值特征们 = {年龄，身高，体重}。
只要剩下没确定阈值特征们不为空。那么就遍历剩下没确定阈值特征们的特征。
下面是遍历的过程：现在我取出
年龄这个特征，为了找到一个年龄划分点（根据年龄区别男女）。我得遍历所有年龄。从1~125岁遍历（因为人最最多活125岁，最小我认为是1岁。这个你可以自己设定多少的。）。比如现在我猜测10是划分点。那么我认为大于10的是男人，小于10的是女人。我还可以猜20岁是划分点，猜32岁是划分点。那么哪个划分点是最好的呢？后面会讲，这个要根据评估指标计算取让评估指标最高的那个作为实际的划分点。每设定一个划分点计算一次评估指标。。（是不是很有意思？后面会讲怎么评估划分点好不好的指标）取出
身高这个特征。然后找身高划分点。从20~260cm（身高也就这个范围）遍历划分点。遍历过程举例小于150cm认为是女，大于150认为是男。小于151cm认为是女，大于151cm认为是男…就这样每设定一个划分点计算一次评估指标。体重同上 然后，这三种特征的每个划分点对对应一个评估指标值。指标值最大的情况作为第一次划分。现在你不用关系评估指标是什么你只需要知道每种划分情况都可以计算一次评估指标值。举个例子：
可以看到(身高,160cm) 0.8这个划分方法让评估指标最大，然后我们就选他。这是第一层划分。因为决策树它是树嘛，所以是分层来的。现在身高的阈值已经确定是160cm了。把现在的决策树用个图形表示就是下面这样子：
现在剩下没确定阈值特征们 = {年龄，体重}。
遍历各种情况。重复上面那个过程，选选一种划分方法，让评估指标最大。直到所有的特征都确定划分点的阈值。当然现在出现新的情况。身高有个两个分支。到底哪个分支好？还是遍历，选择让评估指标最大的那种情况。比如是下面这个情况：
现在确定了体重的阈值，接下来就要确定年龄的阈值。反正都是遍历，取让评估指标最大的那个情况。
上述过程仅仅是本人用于说明决策树的过程的用途。里面数据是用于假设性说明不针对任何人群
ID3算法构造决策树评估指标到底是什么？
答：当前所设定的参数所确定的模型 它会将数据进行划分，划分后的数据的混乱程度就是评价指标。这个混乱程度叫做信息熵。混乱程度听起来像那么回事，具体是什么下面会解释。ID3全称什么根本不重要，重要的是如果你出生早很多年，知道用混乱程度评估决策树模型好不好说不定也可以想到这个方法。知道原理就可以。
什么是信息熵
答：是衡量信息混乱程度的数学指标。什么叫做混乱？什么叫做不混乱？我举个例子：
一个袋子有10个球。如果红球5个白球5个这叫做混乱，如果红球9个白球1个这叫做不混乱。从直观理解就是如果各种东西比例都一样那么我想判断这个袋子里面有什么东西就比较困难，所以叫做混乱。如果这个袋子只有一种东西，那么我判断这个袋子里面有什么东西就很容易，这叫做不混乱。总结：一个集合里面各部分比例越均衡越混乱，各部分越两极分化越不混乱。我们要想把数据分类那就越不混乱越好。比如我把标签为男的数据都划分到一个集合，那判断一个样本它是分类成男还是女不就很简单了。
那怎么用数学来衡量混乱程度呢？ 我们找找规律，看下面这个发现什么规律没有？加起来相同的情况下，把两种球数目相乘的数越大越混乱，越小越不混乱。那么是不是我们可以用这个相乘的结果来衡量数据混乱程度？当年香农就发现了这个规律，然后写了它第一篇研究生论文（woc原来这么简单其实你早出生也可以写出来的，香农最牛逼的不是发现这个，而是它根据这个进行泛化然后衍生出来一门新学科《信息论》。可以发现牛逼的学科往往起点是很简单的，最关键是专注于这个方向进行演化出新学科）。：
10个球，它可以有这些情况：
一般我们是用占比来相乘而不是数量相乘（其实反正都一样）。
如果这个袋子不止两种球还有很多种球怎么办？一样的，把他们占比连乘。
但是连乘有个缺点：不好求导。比如f(x)*g(x)f(x)∗g(x)我想对这个求导，它得用乘法求导规则展开。所以大家一般喜欢把它变成加法。怎么变？取对数，因为对数单调递增所以不会影响原先数值的单调性的，原先x大的现在的函数值仍然大。
取对数也有个缺点ln(x)确实是单调增的，但是x不能为0啊。x是占比，范围是[0,1]。所以x是可以取0的。当x=0时，ln(x)没有意义它的极限是负无穷。我能不能让0乘这个负无穷呢让它变成0呢？于是就衡量混乱程度的指标就变成了xln(x)xln(x)，x单调增，ln(x)单调增。所以乘起来还是单调增。原先x大的现在的函数值仍然大。而当x \rightarrow 0x→0时，x*ln(x)=0x∗ln(x)=0
总结： 信息熵=各个部分的占比乘在一起的结果值*ln(各个部分的占比乘在一起的结果值)=x*ln(x)
举个例子说明信息熵在决策树中起的作用
关注知乎 @Ai酱 持续更新易懂的从本质看机器学习。
阅读相关
Ai酱：[易懂]如何理解论文中的那些评估方法性能指标概念名词{召回率 ROC AUC 交叉验证}
Last updated
