你也可以编写的决策树ID3算法，快来看看吧

树模型是机器学习中比较基础同时应用很广泛的一大类模型，不仅包括单一的决策树模型，而且还有集成算法如随机森林等等，甚至时下比较流行的xgboost模型也是主要以树模型为基础评估器的。接下来的几篇文章，我们陆续推送树模型相关算法，除了介绍树模型的理论之外，我们将重点放在如何通过numpy库来实现相关的算法，在每篇文章的结束，我们都会编写出我们自己的算法实现程序。本文主要介绍树模型中的分类树——ID3算法。

分类树主要用来解决分类问题，本质上是基于特征变量对数据进行分类。你可以认为它是if-then规则的集合，也可以认为是定义特征变量空间与因变量空间的条件概率分布。这样的描述可能比较抽象，我们举一个不太恰当的例子。比如要判断一个人是男性还是女性，我们需要基于这个人的特征去判断，这些特征可以有头发、喉结、胸围等。首先我们可能先看这个人喉结是否突出，我们可能认为喉结没有突出的是女性，喉结突出的个体中我们再根据头发长短进行判断，头发长的为女性，头发短的为男性。

上面的例子已经道出了决策树算法的基本思想和流程：1）特征选择。所谓特征选择就是在一堆特征变量中依次选出对分类最有用的变量，例如说为什么上面例子中是先用喉结判断，后用头发判断，而不是相反，这里面一定有相关算法；2）决策树生成。选择好特征变量之后，就可以建立一套if-then规则集，用图形来呈现就是表现为一棵树，建好树之后，我们就可以用这棵树对未知数据的类别进行判断；3）决策树剪枝。我们建立的树可能过于庞大，增大了误判的概率，需要进行修剪。例如上面例子中喉结突出的个体，我们可能直接就可以判断为男性，而不必再用头发长短来判断，因为从生理上看，主要还是男性的喉结才会突出。

ID3决策树因为提出较早，并没有完备的决策树剪枝策略，所以这篇文章我们先不进行进行介绍，有关决策树剪枝相关算法我们会在下一篇介绍算法时再进行阐述。接下来的介绍从特征选择，决策树生成、预测三部分来展开。

特征是机器学习中自变量的别名。特征选择就是在一系列自变量中选择出对分类最有用的变量。分类树中ID3算法使用信息增益进行特征选择，想要理解信息增益，需要先理解一些概念。

在信息论中，信息是可以量化的，这个量化指标被称为信息量。一个随机事件的信息量被定义为概率的负对数，或者说是概率倒数的对数：

例如，明天下雨的概率是0.5，那么这句话的信息量就是1。从公式上看，概率越大的事情，信息量越小，反之，概率越小的事情，信息量越大。这是符合我们直觉的。

信息量测量的是一个随机事件包含的信息大小。实际上我们更想知道一次随机试验的信息量，这用熵来定义：

这里的H(X)表示的就是随机变量X的熵，也就是说，如果一个随机试验有k种可能的取值，这个随机试验的熵就等于k个随机事件信息量的数学期望。由于概率通常用样本的频率来估计，实际上计算的熵通常被称为经验熵。

还可以从另一个角度来理解熵，熵描述了随机变量的纯度或不确定性。试想一枚硬币在打造时质地不够均匀，在一次抛硬币的随机试验中出现正面向上的概率为0.99，反面向上的概率为0.01。那么我们随便掷一次硬币，会出现怎样的结果，其不确定性是很低的（99%的概率是出现正面），等价说法是纯度很高或信息量很低（因为我们几乎可以认为一次试验肯定出现正面）。相反，如果硬币的质地均匀，正反面出现的概率都是0.5，那么一次抛硬币试验结果的不确定性就变很高，或者说纯度很低或信息量很大。

defentropy(x):"""计算经验熵，熵被定义为信息量的加权平均，权重为概率。:paramx:numpy数组:return:经验熵，一个标量"""估计x的概率分布x_p=([(i)/len(x)foriinset(x)])取出x中的不重复值x_uni=(x)首先实例化创建一个根节点对象_node=Nodes()self.__plant_tree(X,y,_node)def__plant_tree(self,X,y,node):rows,cols=记录当前节点标签的熵=entropy(y)如果当前节点中所有样本属于同一个类别，就跳出递归过程iflen((y))==1:return循环特征，找出最佳特征best_index=Nonebest_gain=0forcol_iinrange(cols):curr_gain=(X[:,col_i],y)ifcurr_gain!=Noneandcurr_gainbest_gain:best_gain=curr_gainbest_index=col_i记录当前节点的子节点，是一个字典对象，字典的key是当前节点的不同取值，value是一个节点对象_nodes={}将样本拆分到每个子节点中，并在子节点中递归建树foriinx_best_uni:x_new=X[x_best==i]y_new=y[x_best==i]_nodes[i]=Nodes()self.__plant_tree(x_new,y_new,_nodes[i])

建好决策树模型后，就可以用这个决策树模型对未知分类的样本进行预测了。预测的方法很简单，就是遍历模型根节点属性，一直到叶子节点，然后基于叶子结点中标签或者因变量的概率分布得到当前样本属于各类的概率，将当前样本归于概率最大的类别。这里我们设计两个函数，函数pred_prob可以返回样本属于各个类的概率，方法pred返回样本属于哪个类别。

classDTClassifier(object):def__init__(self,criterion=''):==='':=info_gain_=='id3':=info_gainelse:raiseValueErrordeffit(self,X,y):记录当前节点样本量_sample=rows记录当前节点标签的概率分布_prob={i:list(y).count(i)/len(y)(y)}如果当前节点中每一个特征中取值都相同，就跳出递归过程([len((x[:,i]))foriinrange(cols)])==cols:return记录最佳特征的索引_feature=best_index选择信息增益或信息增益率最大的特征，用来生成子节点x_best=X[:,best_index]x_best_uni=(x_best)获取输入数据的行数目rows=[0]遍历每一行数据，检索叶子节点，拿到叶子结点中标签的概率分布。foriinrange(rows):result=self.__search_leaf_node(x[i],_node)(result)returnresultsdef__search_leaf_node(self,x,node):如果输入的节点的子节点不为None，说明有子节点，当前节点还不是叶子结点。else:递归，直到找到叶子结点returnself.__search_leaf_node(x,curr_node)

接下来，我们使用周志华《机器学习》76页的西瓜数据集为例，验证一下上面的id3算法。首先先拟合模型：

根节点是按照文理进行划分的__nodes{'模糊':__main__.Nodesat0x20bb11ad820,'清晰':__main__.Nodesat0x20bb11addc0,'稍糊':__main__.Nodesat0x20bb11ad940}稍糊子节点又按照触感进行划分__nodes['稍糊'].children_nodes{'硬滑':__main__.Nodesat0x20bb11adf70,'软沾':__main__.Nodesat0x20bb11adeb0}稍蜷子节点划分出两个分支，一个是乌黑，一个是青绿，书中此处似乎有误__nodes['清晰'].children_nodes['稍蜷'].children_nodes{'乌黑':__main__.Nodesat0x20bb117f310,'青绿':__main__.Nodesat0x20bb117faf0}____prob{'否':0.52941,'是':0.47058823529411764}

然后我们输入两条数据来预测一下类别：

x1=([['青绿','蜷缩','浊响','清晰','凹陷','硬滑'],['乌黑','稍蜷','浊响','清晰','凹陷','软沾']])prob=_prob(x1)prob[{'否':0,'是':1.0},{'否':1.0,'是':0}]class_=(x1)class_['是','否']

两个样本中，一个被预测为好瓜，一个为坏瓜。