共计 2715 个字符，预计需要花费 7 分钟才能阅读完成。
决策树算法
[toc]
一、什么是决策树算法
决策树 是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点示意某个对象，而每个分叉门路则代表某个可能的属性值，而每个叶节点则对应从根节点到该叶节点所经验的门路所示意的对象的值。决策树仅有繁多输入，若欲有复数输入，能够建设独立的决策树以解决不同输入。数据挖掘中决策树是一种常常要用到的技术，能够用于剖析数据，同样也能够用来作预测，从数据产生决策树的机器学习技术叫做 决策树学习 , 艰深说就是 决策树
维基百科：https://zh.wikipedia.org/zh-cn/%E5%86%B3%E7%AD%96%E6%A0%91#%E…
不懂？那咱们援用 周志华老师西瓜书 上的例子，立马就能有一个大略理解。
比方你带你表妹当初要去西瓜摊买西瓜，而作为卖西瓜新手的你总是可能一眼挑选出那个最好吃最甜的西瓜，而表妹总是选的不尽人意，表妹突发奇想向你求教怎么选出一个称心如意的西瓜。你说：得价格！不对不对咱们在谈买西瓜，你说咱们啊，先看“它是什么色彩?”，如果是“青绿色”，则咱们再看“它的根蒂是什么状态?”，如果是“伸直”，咱们再判断“它敲起来是什么声音?”，最初，咱们得出最终决策：这个瓜很润，呸呸呸，是很甜！
我置信你当初应该有一个大略理解了，不就是抉择一个目标（咱们须要进行的分类的标签），而后依据一系列的特色从而满足咱们的目标，当前咱们就借用这个特色去筛选“好瓜”。然而！先泼一盆凉水给你，咱们怎么开始第一步呢？这还不简略，间接抉择”色彩“呀！然而咱们为什么不从”根茎“下手呢？上面就是咱们要将的如何进行划分，也就是划分规范。
二、划分规范
2.1 信息增益(ID3 决策树算法划分规范)
必须先理解信息熵这个概念，信息熵 ，维基百科上的定义：是接管的每条音讯中蕴含的信息的均匀量。这里，“音讯”代表来自散布或数据流中的事件、样本或特色。（熵最好了解为不确定性的量度而不是确定性的量度，因为越随机的信源的熵越大）来自信源的另一个特色是样本的概率分布。这里的想法是，比拟不可能产生的事件，当它产生了，会提供更多的信息。因为一些其余的起因，把信息（熵）定义为概率分布的对数的相反数是有情理的。事件的概率分布和每个事件的信息量形成了一个随机变量，这个随机变量的均值（即冀望）就是这个散布产生的信息量的平均值（即熵）。熵的概念最早起源于物理学，用于度量一个热力学零碎的无序水平。在信息论外面，熵是对不确定性的测量。然而在信息世界， 熵越高，则能传输越多的信息，熵越低，则意味着传输的信息越少 。还是不懂？那你无妨记住： 信息熵是对信息量的一种掂量
维基百科：https://zh.wikipedia.org/zh-cn/%E7%86%B5_(%E4%BF%A1%E6%81%AF%E8%AE%BA)
Shannon,C.E.(1948).A Mathematical Theory of Communication. Bell System Technical Journal,27(3),379–423.doi:10.1002/j.1538-7305.1948.tb01338.x
个别地，划分数据集的大准则是：将无序的数据变得更加有序 。在划分数据集之前之后信息产生的变动称为信息增益，晓得如何计算信息增益，咱们就能够计算每个特征值划分数据集取得的信息增益， 取得信息增益最高的特色就是最好的抉择。也就是说咱们可用信息增益来进行决策树的划分属性抉择，他们公式如下：
$$
信息熵：Ent(D)=-\displaystyle\sum_{k=1}^{|y|}p_klog_2p_k \\ 取正数：保障信息熵 >0
$$
其中 $Ent(D)$ 的值越小，则音讯熵越小
$$
信息增益 Gain(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v) \\V: 离散属性 a 的可能取值的个数
$$
怎么应用？再次借用周志华老师书上例子，咱们来辨别好瓜坏瓜。
- 正文：本文都是采纳的 ID3 决策树算法
因为咱们的目标是辨别好瓜坏瓜所以先计算其信息熵：$$Ent(D)=-\sum_{k=1}^{2}p_klog_2p_k=-(\frac{8}{17}log_2(\frac{8}{17})+\frac{9}{17}log_2(\frac{9}{17}))=0.998$$
同理可得假如咱们以色泽进行分类，那么色泽有三种可能 {青绿、漆黑、浅白}，咱们再计算每种色泽下所对应好坏瓜的概率（$p_1: 好，p_2: 坏 $）：青绿：$p_1=0.5,p_2=0.5$；漆黑：$p_1=\frac{4}{6}，p_2=\frac{2}{6}$；浅白：$p_1=\frac{1}{5},p_2=\frac{4}{5}$；这样一来咱们能够计算各种信息增益：$$
Ent(青绿)=1，Ent(漆黑)=0.918，Ent(浅白)=0.722
$$而后计算信息增益:
$$
Gain(D, 色泽)=Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v)=0.998-(\frac{6}{17}\times1+\frac{6}{17}\times0.918+\frac{5}{17}\times0.722)=0.109\\ 同理可得其余的信息增益：Gain(D, 根蒂)=0.143;Gain(D, 敲声)=0.141;Gain(D, 纹理)=0.381;Gain(D, 脐部)=0.289;Gain(D, 触感)=0.006
$$纹理的信息增益最大，所以咱们取纹理作为咱们的划分规范，同理从纹理登程再取计算其余属性，并且失去信息增益，以此类推只到所有规范都划分结束。
2.2 基尼指数(CART 决策树算法划分规范)
三、评估
决策树的长处
1、决策树易于了解和实现. 人们在通过解释后都有能力去了解决策树所表白的意义
2、对于决策树，数据的筹备往往是简略或者是不必要的. 其余的技术往往要求先把数据一般化，比方去掉多余的或者空白的属性
3、可能同时解决数据型和惯例型属性。其余的技术往往要求数据属性的繁多
4、是一个白盒模型如果给定一个察看的模型，那么依据所产生的决策树很容易推出相应的逻辑表达式
5、易于通过动态测试来对模型进行评测。示意有可能测量该模型的可信度
6、在绝对短的工夫内可能对大型数据源做出可行且成果良好的后果
决策树的毛病
对于那些各类别样本数量不统一的数据，在决策树当中信息增益的后果偏差于那些具备更多数值的特色
文章如若有谬误，欢送大佬们批评指正。CART 算法以及 python 代码有空再补充吧，手打内容太累了。💪💪
参考
周志华《西瓜书》
《机器学习实战》
