python机器学习理论与实战（二）决策树

        决策树也是有监督机器学习方法。 电影《无耻混蛋》里有一幕游戏，在德军小酒馆里有几个人在玩20问题游戏，游戏规则是一个设迷者在纸牌中抽出一个目标（可以是人，也可以是物），而猜谜者可以提问题，设迷者只能回答是或者不是，在几个问题（最多二十个问题）之后，猜谜者通过逐步缩小范围就准确的找到了答案。这就类似于决策树的工作原理。（图一）是一个判断邮件类别的工作方式，可以看出判别方法很简单，基本都是阈值判断，关键是如何构建决策树，也就是如何训练一个决策树。

（图一）

构建决策树的伪代码如下：

Check if every item in the dataset is in the same class:    If so return the class label    Else       find the best feature to split the data       split the dataset        create a branch node       for each split          call create Branch and add the result to the branch node      return branch node

         原则只有一个，尽量使得每个节点的样本标签尽可能少，注意上面伪代码中一句说：find the best feature to split the data，那么如何find thebest feature?一般有个准则就是尽量使得分支之后节点的类别纯一些，也就是分的准确一些。如（图二）中所示，从海洋中捞取的5个动物，我们要判断他们是否是鱼，先用哪个特征？

（图二）

         为了提高识别精度，我们是先用“离开陆地能否存活”还是“是否有蹼”来判断？我们必须要有一个衡量准则，常用的有信息论、基尼纯度等，这里使用前者。我们的目标就是选择使得分割后数据集的标签信息增益最大的那个特征，信息增益就是原始数据集标签基熵减去分割后的数据集标签熵，换句话说，信息增益大就是熵变小，使得数据集更有序。熵的计算如（公式一）所示：

有了指导原则，那就进入代码实战阶段，先来看看熵的计算代码：

def calcShannonEnt(dataSet):   numEntries = len(dataSet)   labelCounts = {}   for featVec in dataSet: #the the number of unique elements and their occurance     currentLabel = featVec[-1]     if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0     labelCounts[currentLabel] += 1 #收集所有类别的数目，创建字典   shannonEnt = 0.0   for key in labelCounts:     prob = float(labelCounts[key])/numEntries     shannonEnt -= prob * log(prob,2) #log base 2 计算熵   return shannonEnt