关注公众号：用Python学机器学习，获取更多更新。

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

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

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

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

特征选择

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

信息量

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

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

熵entropy

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

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

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

def entropy(x):
    """
    计算经验熵，熵被定义为信息量的加权平均，权重为概率。
    :param x:numpy数组
    :return: 经验熵，一个标量
    """
    # 将ndarray数组转化为列表
    x = list(x)
    # 估计x的概率分布
    x_p = np.array([x.count(i)/len(x) for i in set(x)])
    # 计算熵
    return -np.sum([p*np.log2(p) for p in x_p])

条件熵

分类树中，相较于熵，我们更感兴趣的是条件熵，也就是在已知某个随机变量的前提下，计算另一个随机变量的熵：

很显然，条件熵评估了一个随机变量X对另一个随机变量Y信息量的影响程度。

def con_entropy(x,y):
    """
    计算条件熵
    :param x: 一维数组
    :param y: 一维数组
    :return: 返回x条件下y的熵
    """
    # 取出x中的不重复值
    x_uni = np.unique(x)
    # 取出不同的x中的所有y熵来计算条件熵
    con_ent = 0
    for i in x_uni:
        y_new = y[x == i]
        y_ent = entropy(y_new)
        con_ent += len(y_new)*y_ent/len(x)

    return con_ent

ID3算法正是借助熵和条件熵来计算信息增益，接下来我们介绍信息增益。

ID3算法特征选择标准——信息增益

信息增益的定义很简单，也很直观：

很显然，信息增益衡量了已知随机变量X后，随机变量Y的信息量减少的程度，减少的越多，说明了在对Y分类过程中，随机变量X提供了越多的信息，我们就应该选择这个变量。

def info_gain(x,y):
    """
    计算信息增益，ID3算法使用
    :param x: 一个一维列表或数组
    :param y: 一个一维列表或数组
    :return: 返回信息增益
    """
    return entropy(y)-con_entropy(x,y)

决策树生成

决策树的生成就是一个重复地调用特征选择的过程。在ID3算法中，我们首先遍历所有特征变量，计算每个特征变量的信息增益，将信息增益最大的特征变量作为树模型的根节点，根据根节点特征变量的不同取值，发出树枝，对于每条树枝所包含的样本再次调用特征选择过程，选择出最佳特征建立子节点，重复上述过程一直到：当前节点包含的所有样本都属于同一个类别（无需分类），或者已经没有特征变量可供使用，或者当前样本中每一个特征变量的取值都相同（无法分类）。

根据上面的思想，用编程来实现其实就是一个递归调用的问题。接下来，我们用numpy来实现这一递归算法。

用python来编程，最主要就是设计类。初步考虑，我们的程序中应该至少包括两个类，一个类用来描述树的结构，即树有哪些节点，以及每个节点所包含的信息。特别的，我们需要知道每个节点尤其是叶子节点样本中因变量的概率分布，我们还需要知道每个节点有哪些子节点。只有知道了这些信息，我们才能对未知数据进行分类。

class Nodes(object):
    def __init__(self
                 ,n_sample=None
                 ,entro=None
                 ,children_nodes=None
                 ,best_feature=None
                 ,class_prob=None):
        """
        存储节点的信息，包括当前节点的样本量，标签的经验熵，最佳分割特征，子节点等。
        Parameters
        ----------
        n_sample : 当前节点样本量.
        entro : 当前节点因变量的熵
        children_nodes : 当前节点的子节点
        best_feature : 当前节点使用的特征索引
        class_prob : 当前节点因变量的概率分布
        Returns
        -------
        None.

        """
        self.n_sample = n_sample
        self.entro = entro
        self.children_nodes = children_nodes
        self.best_feature = best_feature
        self.class_prob = class_prob

另一个类就是模型类了，参考sklearn的思想，我们可以设计一个fit方法来拟合模型，fit方法内部可以递归调用特征选择过程来建树：

class DTClassifier(object):
    def __init__(self, criterion='c4.5'):
        self.criterion = criterion
        if self.criterion == 'c4.5':
            self.func = info_gain_rate
        elif self.criterion == 'id3':
            self.func = info_gain
        else:
            raise ValueError

    def fit(self,X,y):
        # 首先实例化创建一个根节点对象
        self.root_node = Nodes()
        self.__plant_tree(X,y,self.root_node)


    def __plant_tree(self,X,y,node):
        rows,cols = X.shape
        # 记录当前节点样本量
        node.n_sample = rows
        # 记录当前节点标签的熵
        node.entro = entropy(y)
        # 记录当前节点标签的概率分布
        node.class_prob = {i: list(y).count(i)/len(y) for i in np.unique(y)}
        
        # 如果当前节点中所有样本属于同一个类别，就跳出递归过程
        if len(np.unique(y))==1:
            return
        # 如果当前节点中每一个特征中取值都相同，就跳出递归过程
        if np.sum([len(np.unique(x[:,i])) for i in range(cols)])==cols:
            return
        
        # 循环特征，找出最佳特征
        best_index = None
        best_gain = 0
        for col_i in range(cols):
            curr_gain = self.func(X[:,col_i], y)
            if curr_gain != None and curr_gain > best_gain:
                best_gain = curr_gain 
                best_index = col_i 
            
        # 记录最佳特征的索引
        node.best_feature = best_index
        # 记录当前节点的子节点，是一个字典对象，字典的key是当前节点的不同取值，value是一个节点对象
        node.children_nodes = {}

        # 选择信息增益或信息增益率最大的特征，用来生成子节点
        x_best = X[:,best_index]
        x_best_uni = np.unique(x_best)
        # 将样本拆分到每个子节点中，并在子节点中递归建树
        for i in x_best_uni:
            x_new = X[x_best==i]
            y_new = y[x_best==i]
            
            node.children_nodes[i] = Nodes()
            self.__plant_tree(x_new,y_new,node.children_nodes[i])

预测

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

class DTClassifier(object):
    def __init__(self, criterion='c4.5'):
        self.criterion = criterion
        if self.criterion == 'c4.5':
            self.func = info_gain_rate
        elif self.criterion == 'id3':
            self.func = info_gain
        else:
            raise ValueError

    def fit(self,X,y):
        # 首先实例化创建一个根节点对象
        self.root_node = Nodes()
        self.__plant_tree(X,y,self.root_node)


    def __plant_tree(self,X,y,node):
        rows,cols = X.shape
        # 记录当前节点样本量
        node.n_sample = rows
        # 记录当前节点标签的熵
        node.entro = entropy(y)
        # 记录当前节点标签的概率分布
        node.class_prob = {i: list(y).count(i)/len(y) for i in np.unique(y)}
        
        # 如果当前节点中所有样本属于同一个类别，就跳出递归过程
        if len(np.unique(y))==1:
            return
        # 如果当前节点中每一个特征中取值都相同，就跳出递归过程
        if np.sum([len(np.unique(x[:,i])) for i in range(cols)])==cols:
            return
        
        # 循环特征，找出最佳特征
        best_index = None
        best_gain = 0
        for col_i in range(cols):
            curr_gain = self.func(X[:,col_i], y)
            if curr_gain != None and curr_gain > best_gain:
                best_gain = curr_gain 
                best_index = col_i 
            
        # 记录最佳特征的索引
        node.best_feature = best_index
        # 记录当前节点的子节点，是一个字典对象，字典的key是当前节点的不同取值，value是一个节点对象
        node.children_nodes = {}

        # 选择信息增益或信息增益率最大的特征，用来生成子节点
        x_best = X[:,best_index]
        x_best_uni = np.unique(x_best)
        # 将样本拆分到每个子节点中，并在子节点中递归建树
        for i in x_best_uni:
            x_new = X[x_best==i]
            y_new = y[x_best==i]
            
            node.children_nodes[i] = Nodes()
            self.__plant_tree(x_new,y_new,node.children_nodes[i])
    
    def predict(self,x):
        results = self.predict_prob(x)
        pred = []
        for i in range(len(results)):
            p = max(results[i],key=lambda k : results[i][k])
            pred.append(p)
        
        return pred
    
    def predict_prob(self,x):
        # 获取输入数据的行数目
        rows = x.shape[0]
        # 定义一个列表，用来存储结果
        results = []
        # 遍历每一行数据，检索叶子节点，拿到叶子结点中标签的概率分布。
        for i in range(rows):
            result = self.__search_leaf_node(x[i],self.root_node)
            results.append(result)
        return results
            
            
    def __search_leaf_node(self,x,node):
        # 如果输入节点的子节点为None，说明当前节点为叶子节点，那么就从叶子节点中拿到标签的概率分布，这里定义为一个字典。
        if node.children_nodes is None:
            result = {i:node.class_prob.get(i,0) for i in self.root_node.class_prob.keys()}
            return result
        # 如果输入的节点的子节点不为None，说明有子节点，当前节点还不是叶子结点。
        else:
            # 那么就进入当前节点的子节点
            curr_node = node.children_nodes[x[node.best_feature]]
            # 递归，直到找到叶子结点
            return self.__search_leaf_node(x, curr_node)

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

# 创建数据集
>>>x = np.array([['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑'],
       ['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑'],
       ['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑'],
       ['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑'],
       ['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑'],
       ['青绿', '稍蜷', '浊响', '清晰', '稍凹', '软沾'],
       ['乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软沾'],
       ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑'],
       ['乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑'],
       ['青绿', '硬挺', '清脆', '清晰', '平坦', '软沾'],
       ['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑'],
       ['浅白', '蜷缩', '浊响', '模糊', '平坦', '软沾'],
       ['青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑'],
       ['浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑'],
       ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软沾'],
       ['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑'],
       ['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑']])
>>>y = np.array(['是','是','是','是','是','是','是','是','否','否','否','否','否','否','否','否','否'])

>>>dt = DTClassifier(criterion='id3')
>>>dt.fit(x, y)
# 根节点是按照文理进行划分的
>>>dt.root_node.children_nodes
{'模糊': <__main__.Nodes at 0x20bb11ad820>,
 '清晰': <__main__.Nodes at 0x20bb11addc0>,
 '稍糊': <__main__.Nodes at 0x20bb11ad940>}
# 稍糊子节点的子节点为空，说明已经是叶子节点了
>>>dt.root_node.children_nodes['模糊'].children_nodes

# 稍糊子节点又按照触感进行划分
>>>dt.root_node.children_nodes['稍糊'].children_nodes
{'硬滑': <__main__.Nodes at 0x20bb11adf70>,
 '软沾': <__main__.Nodes at 0x20bb11adeb0>}

# 清晰子节点又按照根蒂进行划分
>>>dt.root_node.children_nodes['清晰'].children_nodes
{'硬挺': <__main__.Nodes at 0x20bb117fdf0>,
 '稍蜷': <__main__.Nodes at 0x20bb117f490>,
 '蜷缩': <__main__.Nodes at 0x20bb117fe20>}

# 稍蜷子节点划分出两个分支，一个是乌黑，一个是青绿，书中此处似乎有误
>>>dt.root_node.children_nodes['清晰'].children_nodes['稍蜷'].children_nodes
{'乌黑': <__main__.Nodes at 0x20bb117f310>,
 '青绿': <__main__.Nodes at 0x20bb117faf0>}

>>>dt.root_node.n_sample
17
>>>dt.root_node.class_prob
{'否': 0.5294117647058824, '是': 0.47058823529411764}

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

>>>x1 = np.array([['青绿','蜷缩','浊响','清晰','凹陷','硬滑'],
               ['乌黑','稍蜷','浊响','清晰','凹陷','软沾']])

>>>prob = dt.predict_prob(x1)

>>>prob
[{'否': 0, '是': 1.0}, {'否': 1.0, '是': 0}]

>>>class_ = dt.predict(x1)

>>>class_
['是', '否']

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