决策树（Decision Tree）是一种简单但是广泛使用的分类器。通过训练数据构建决策树，可以高效的对未知的数据进行分类。
决策数有两大优点：1）决策树模型可以读性好，具有描述性，有助于人工分析；2）效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。
由于构建决策树的过程存在很多分岔情形，因此决策树引入了十分重要的一个概念：信息熵；下面咱们先讲一下【信息熵】
信息熵
信息熵在1948年由克劳德·艾尔伍德·香农提出，解决对信息的量化度量问题；那什么是“信息的量化度量”问题？首先看下面的数学公式：
信息熵公式
信息熵解决的是对信息的度量问题，那么信息是什么？它是可以计算的吗？
回答： 我们先从现实出发，看看信息是否有量化的可能。例如今天邱告诉我，“明天的太阳会从东边升起。”这时我就想，这话虽然很正确，但是我觉得没什么用啊，太阳从东边升起不是确定的事件吗，还有说的价值吗？所以，我的想法是这句话的信息量为零。这时候，邱看着我不屑的表情，顿时狡猾一笑说，虽然明天的太阳还是从东边升起，但是明天北京会下雪哦~听到这里，我就觉得震惊了，顿时就说“这不太可能把，你这话信息量好大，我赶紧去查查天气预报。”（请关注2019年的第一场雪，比以往都来的晚些）
从上面的例子我们就发现，信息确实可以划分出信息量大小的，而且我们发现这件事情的信息量大小，是和这件事情的发生概率相关，好了，既然如此，那么我们该如何构造信息量的表达式？
我们先提炼一下信息量的表达式应该满足的条件：
（1）信息量和事件发生的概率有关，当事件发生的概率越低，传递的信息量越大；
（2）信息量应当是非负的，必然发生的信息量为0；
（3）两个事件的信息量可以相加，并且两个独立事件的联合信息量应该是他们各自信息量的和；
对于（1），前面我们已经讨论过了，不再阐述；
对于（2），一个信息要么帮助我们降低不确定性，要么不能降低不确定性，但是不会出现知道这个消息后，现有的消息会消失的情况；
对于（3）对于两个独立事件，因为p(AB)=p(A)p(B),若信息量的计算公式为f(p(x)),则应当有f(p(AB))=f(p(A))+f(p(B))
解决了信息量的计算问题，接下来聊聊熵这个概念
在1948年，信息论之父克劳德·艾尔伍德·香农提出了信息熵的概念，用来描述随机事件的“混乱”程度，也即该随机事件所有结果所带来平均不确定性；显然，我们可以看出信息熵的计算就是信息量的数学期望。特点如下：
（1）信息熵与事件的可能性数量有关，在概率均等的情况下，存在的可能越多，信息熵越大，信息也约不确定；
（2）信息熵与事件的概率分布情况有关，概率分布越平均，信息熵越大，当所有概率均等的情况下，信息熵达到最大；
信息熵对决策树的意义
我们引入“信息熵”来作为度量样本集合不确定度（纯度）的指标，采用信息增益这个量来作为纯度的度量，选取信息增益最大的特征进行分裂（即作为结点）。
信息增益是=信息熵-条件熵
信息熵代表随机变量的复杂度（不确定度），条件熵代表在某一个条件下，随机变量的复杂度（不确定度）。
信息熵表达式
条件熵表达式
信息增益的意义？信息增益量越大，这个属性作为一棵树的根节点就能使这棵树更简洁；因此，决策树的构造原则：选信息增益最大的
我们计算得到的信息增益表示得知某属性的信息而使得样本集合不确定度减少的程度。
所以在构建决策树的过程中，我们的关键就是每次选择什么进行决策树的构建。什么样的特征作为结点，那么如何在这么多的特征中进行一个选择呢，我们采用最大信息增益（信息不确定性减少的程度最大）来度量。好了，现在我们知道怎么选择特征作为结点的指标是什么了。
如何构建决策树
例如：有个预测【瓜】的好坏的难题，形形色色的条件太多了，没办法人为全覆盖进行打标签，该怎么办呢？
第一步，确定维度-【色泽】【根蒂】【敲声】【纹理】【脐部】【触感】
第二步，均匀抽样，进行打标；监督学习，定义基础训练集合如下：
训练数据集合
第三步，进行数学计算（掌握理论过程）
判定表
正例（好瓜）占8/17，反例（坏瓜）占9/17，则根结点的信息熵为：
计算当前属性集合{色泽，根蒂，敲声，纹理，脐带，触感}中每个属性的信息增益。
色泽有三个可能的取值：青绿、乌黑、浅白
D1{色泽=青绿}={1,4,6,10,13,17}，正例3/6，反例3/6
D2{色泽=乌黑}={2,3,7,8,9,15}，正例4/6，反例2/6
D3{色泽=浅白}={5,11,12,14,16}，正例1/5，反例4/5
这三个分支结点的信息熵为：
由此我们可以计算出色泽属性的信息增益是：
同理，按照一样的方法我们可以求出其他属性的信息增益，分别如下：
经过比较，我们得出信息增益最大的属性为纹理，于是我们得到第一个划分属性结点（纹理）。
到现在可得出如下初步构建的决策树：
我们依据结点标签（清晰、稍糊、模糊）划分了三个子结点对应的集合。这里的3个子集合相当于一个类似总集合D一样的地位。重复上面找的纹理结点的方法进行递归。利用信息增益最大的方法来进行特征选择。
比如;D1{纹理=清晰}={1,2,3,4,5,6,8,10,15}，第一个分支结点可用属性集合为{色泽、根蒂、敲声、脐部、触感}，则基于集合D1计算出的各属性信息增益分别如下;
于是我们可以选择根蒂、脐部、触感这3个特征属性中的任何一个（因为他们的信息增益值相等且最大），其他两个结点同理。这样就可以得到新一层的结点。通过递归就能构建出整个决策树了。
如何利用决策树进行预测
第一步：读取数据（分析：featurelist[特征维度] | tableMap[数据阵列] | featureValueTableList[各特征维度中的特征点]）
featurelist[特征维度] | tableMap[数据阵列]
featureValueTableList[各特征维度中的特征点]
第二步：得到数据集列表[tableMap]角标和特征列表[featureList]的角标
下角标计算
第三步：构建决策树
个人比较喜欢构造函数，直接上代码
定义类的属性，这里设计的信息比较少（仅供参考）
构造决策树
attrNames(特征维度)
samples信息
树的构建：
递归方式构建树
信息熵的使用
样本列表归类
信息熵指导目标挑选
第四步：使用决策树
预期分类结果的检验
打印测试结果
应用场景：对未知数据进行分类是决策树的一大优势，由于多数情况下我们不知道得到数据意味着什么，也不知道数据维度之间的关联关系，因此一上来直接开始使用决策树进行粗分类是一种不错的选择；然而不清楚在数据维度更大或者维度间隐含关系到了什么程度的时候应该如何应对？是否需要使用贝叶斯或者BP神经网络？有待以后有机会通过实践论证！
写在最后：好瓜坏瓜其实只要来到这个世界上都是瓜，没有必要区分好坏，甚至让机器都学会如何区分好瓜和坏瓜了，让瓜本身情何以堪？！不过，机器学习的过程是十分有趣的，深刻体会到了用数学去解决问题这背后强大的逻辑思想，向前辈们致敬！
补充：
修改代码获得决策树对分类属性在数据集中的权重排列：
权重分类
网友评论