决策树之ID3算法

一、决策树之ID3算法简述

　　1976年-1986年，J.R.Quinlan给出ID3算法原型并进行了总结，确定了决策树学习的理论。这可以看做是决策树算法的起点。1993，Quinlan将ID3算法改进成C4.5算法，称为机器学习的十大算法之一。ID3算法的另一个分支是CART(Classification adn Regression Tree, 分类回归决策树)，用于预测。这样，决策树理论完全覆盖了机器学习中的分类和回归两个领域。

　　本文只做了ID3算法的回顾，所选数据的字段全部是有序多分类的分类变量。C4.5和CART有时间另花篇幅进行学习总结。本文需要有一定的pandas基础、了解递归函数。

　　1、ID3算法研究的核心思想是if-then，本质上是对数据进行分组操作。

　　下表是包含用户信息和购买决策的表。这张表已经对1024个样本进行了分组统计。依此为例解释if-then(决策)和数据分组。

　　对于第0条和第7条数据，唯一的区别是income不同，于是可以认为，此时income不具有参考价值，而应考察student值或reputation的信息。于是：if-then定义了一套规则，用于确定各个分类字段包含的信息计算方法，以及确定优先按照哪个字段进行分类决策。

　　假如根据if-then，确定优先按照age对数据集进行拆分，那么可以确定三个水平(青年、中年、老年)对应的子数据集。然后，继续对着三个子数据集分别再按照剩余的字段进行拆分。如此循环直到除了购买决策之外的所有字段都被遍历。你会发现，对于每个拆分的子数据集，根本不需要关注里面的值是汉字、字符串或数字，只需要关注有几个类别即可。

　　根据if-then的分类结果，对于一个样本，可以根据其各个字段的值和if-then规则来确定它最终属于下表哪个组。

　　决策树强调分组字段具有顺序性，认为字段层级关系是层层递进的；而我们直接看这张表时，所有字段都是并排展开的，存在于同一层级。这或许是最大的区别。

　　当然，你也可以拿一个样本，对照此表，找到它属于的那个组，以及对应的purchase。如果purchase有不同值，根据count计算其概率即可。

	count	age	income	student	reputation	purchase
0	64	青年	高	否	良	不买
1	64	青年	高	否	优	不买
2	128	中年	高	否	良	买
3	60	老年	中	否	良	买
4	64	老年	低	是	良	买
5	64	老年	低	是	优	不买
6	64	中年	低	是	优	买
7	128	青年	中	否	良	不买
8	64	青年	低	是	良	买
9	132	老年	中	是	良	买
10	64	青年	中	是	优	买
11	32	中年	中	否	优	买
12	32	中年	高	是	良	买
13	64	老年	中	否	优	不买

　　2、确定决策规则的两个核心公式：经验熵、条件熵和信息增益

　　1948年，美国信息学家香农(Shannon)定义了信息熵:

　　　　$$I(U) = log(\frac{1}{p}) = -log(p)$$

　　I被称为不确定性函数，代表事件的信息量。log表示取对数。假定对于一个信源，其发生各种事件是相互独立的，并且其值具有可加性。因此使用log函数。可见，发生的概率越大，其不确定性越低。

　　考虑到信源的所有可能发生的事件，假设其概率为$p_1, p_2,..., p_i$，则可以计算其平均值(数学期望)，该值被称为信息熵或者经验熵。涵义即为：一个信源的平均不确定性，或者一个信源的不确定性期望。用公式表示为:

　　$$H(D) = E[-log p_i] = -\sum_{i=1}^{n}p_{i}* $$

　　举个例子。计算purchase的信息熵(经验熵)：

init_dic = {
    "count": [64,64,128,60,64,64,64,128,64,132,64,32,32,64],
    "age": ["青年","青年","中年","老年","老年","老年","中年","青年","青年","老年","青年","中年","中年","老年"],
    "income": ["高","高","高","中","低","低","低","中","低","中","中","中","高","中"],
    "student": ["否","否","否","否","是","是","是","否","是","是","是","否","是","否"],
    "reputation": ["良","优","良","良","良","优","优","良","良","良","优","优","良","优"],
    "purchase": ["不买","不买","买","买","买","不买","买","不买","买","买","买","买","买","不买"]
}
data = pd.DataFrame(init_dic, columns=["count", "age", "income", "student", "reputation", "purchase"])

# 计算买和不买的样本数据
purchase_yes _count= data[data["purchase"] == "买"]["count"].sum()
purchase_no_count = data[data["purchase"] == "不买"]["count"].sum()
# 计算各自的概率
purchase_yes_p = purchase_yes_count / (purchase_yes_count + purchase_no_count)
purchase_no_p = 1 - purchase_yes_p
print(purchase_yes_p, purchase_no_p)
# 计算此时的信息熵
I_purchase = -purchase_yes_p*np.log2(purchase_yes_p) -purchase_no_p*np.log2(purchase_no_p)
print(I_purchase)

# 0.625 0.375
# 0.954434002924965

　　在X发生的情况下，Y的熵称为条件熵H(Y|X)。显然地，有公式：

　　$$H(Y|X) = H(X,Y) - H(X) = \sum_{i} p(i) H(Y|X = x)$$

　　上述公式表示：(X,Y)发生所包含的熵(它是个并集)，减去X的熵，即为Y发生“新”增的熵。条件熵的公式推导略。

　　信息增益：表示得知特征A的信息而使得D集合的信息不确定性减少的程度。它为集合D的经验熵减去特征A的条件熵。公式表示为：

　　$$g(D, A) = H(D) - H(D|A)$$

　　联合上面这两个式子：

　　$$g(D, A) = H(D) - H(D|A) = H(D) - (H(D,A) - H(A)) = H(D) + H(A) - H(D,A)$$

　　它显示是典型的计算两个集合的交集公式，这可以表示D和A之间的互信息。这行公式的理解至关重要。

　　决策树优先从信息增益大的特征列开始划分数据集。这样要更“靠谱”，因为信息增益(互信息)最大，对集合D（实际上也就是决策标签）影响力更大。

　　计算age字段的(经验)条件熵以及它的信息增益。

def shannon(data, column="age"):
    # 找到这个字段的唯一值
    levels = data[column].drop_duplicates().tolist()  # ['青年', '中年', '老年']
    # 计算该字段的所有数据集，显然是整个数据集
    samples = data["count"].sum()
    # 依次计算信息熵
    entropy = 0
    for level in levels:
        # 获取该水平的子数据集，计算买与不买的信息熵
        subdata = data[data[column] == level]
        purchase_yes = subdata[subdata["purchase"] == "买"]["count"].sum()
        purchase_no = subdata[subdata["purchase"] == "不买"]["count"].sum()
        purchase_yes_p = purchase_yes / (purchase_yes + purchase_no)
        purchase_no_p = 1 - purchase_yes_p
        # 计算该水平上的信息熵
        if purchase_yes == 0 or purchase_no == 0: # 这里要处理子数据集为空的情况；这里暂未处理
            pass
        I_purchase = -purchase_yes_p*np.log2(purchase_yes_p) -purchase_no_p*np.log2(purchase_no_p)            
        # 计算该水平上的概率值
        level_p = subdata["count"].sum() / samples
        # 计算信息增益
        if I_purchase > 0:
            entropy += level_p * I_purchase
        # print(level, level_p, I_purchase, purchase_yes, purchase_no, entropy)
    return entropy

entropy_age = shannon(data, "age")
gain_age = I_purchase - entropy_age  # 计算这个字段的信息增益
print(gain_age)
# 0.2657121273840979
# 有报错0除，没做处理。本例只演示如何计算叶节点信息熵。

　　3、决策树流程

　　决策树的流程为：

　　(1)输入需要分类的数据集和类别标签和靶标签。

　　(2)检验数据集是否只有一列，或者是否最后一列(靶标签数据默认放到最后一列)只有一个水平(唯一值)。

　　　　是：返回唯一值水平或者占比最大的那个水平

　　(3)调用信息增益公式，计算所有节点的信息增益，得到最大信息增益所对应的类别标签。

　　(4)建立决策树字典用以保存当次叶节点数据信息。

　　(5)进入循环：

　　　　按照该类别标签的不同水平，依次计算子数据集；

　　　　对子数据集重复(1),(2),(3),(4),(5), (6)步。

　　(6)返回决策树字典。

　　决策树实际上是一个大的递归函数，其结果是一个多层次的字典。

二、python3实现ID3算法

　　1、python3实现ID3决策树

　　参照书上的代码，用的数据结构不是列表而是pandas的DataFrame。数据文件下载地址：https://files.cnblogs.com/files/kuaizifeng/ID3data.txt.zip。

　　信息熵和信息增益其实可以提炼出来，作为单独的计算方法。方便替换其它的计算方式，如信息增益率，基尼不纯度等。

　　LoadDataSet用来载入数据，TreeHandler用来持久化数据。

　　ID3Tree中，

　　　　_best_split用来遍历标签并计算最大信息增益对应的标签；

　　　　_entropy就是计算熵；

　　　　_split_dataSet用于切割数据集；

　　　　_top_amount_level是递归终止条件触发时的返回值。即只有一个特征列的一个水平的子集时，如果对应的purchase还有买和不买(level)，就返回最大占比的level；

　　　　mktree主程序，递归生成决策树，并将其保存在tree字典中；

　　　　predict主程序，用于预测分类；

　　　　_unit_test，单元测试程序，用于测试上面一些函数。

import numpy as np
import pandas as pd
import json

class LoadDataSet(object):
    def load_dataSet(self):
        """数据文件下载地址：https://files.cnblogs.com/files/kuaizifeng/ID3data.txt.zip"""
        data = pd.read_csv("ID3data.txt", sep="\t", header=None)
        data.rename(columns={0: "age", 1: "income", 2: "student", 3: "reputation", 4: "purchase"}, inplace=True)
        return data
    
class TreeHandler(object):
    def __init__(self):
        self.tree = None
    def save(self, tree):
        self.tree = tree
        with open("tree.txt", mode="w", encoding="utf-8") as f:
            tree = json.dumps(tree, indent="  ", ensure_ascii=False)
            f.write(tree)
    def load(self, file):
        with open(file, mode="r", encoding="utf-8") as f:
            tree = f.read()
            self.tree = json.loads(tree)
        return self.tree    

class ID3Tree(LoadDataSet, TreeHandler):
    """主要的数据结构是pandas对象"""
    __count = 0
    def __init__(self):
        super().__init__()
        """认定最后一列是标签列"""
        self.dataSet = self.load_dataSet()
        self.gain = {}
    
    def _entropy(self, dataSet):
        """计算给定数据集的熵"""
        labels= list(dataSet.columns)
        level_count = dataSet[labels[-1]].value_counts().to_dict()  # 统计分类标签不同水平的值
        entropy = 0.0
        for key, value in level_count.items():
            prob = float(value) / dataSet.shape[0]
            entropy += -prob * np.log2(prob)
        return entropy
    
    def _split_dataSet(self, dataSet, column, level):
        """根据给定的column和其level来获取子数据集"""
        subdata = dataSet[dataSet[column] == level]
        del subdata[column] # 删除这个划分字段列
        return subdata.reset_index(drop=True)  # 重建索引
    
    def _best_split(self, dataSet):
        """计算每个分类标签的信息增益"""
        best_info_gain = 0.0  # 求最大信息增益
        best_label = None     # 求最大信息增益对应的标签(字段)
        labels = list(dataSet.columns)[: -1]     # 不包括最后一个靶标签
        init_entropy = self._entropy(dataSet)  # 先求靶标签的香农熵
        for _, label in enumerate(labels):
            # 根据该label(也即column字段)的唯一值(levels)来切割成不同子数据集，并求它们的香农熵
            levels = dataSet[label].unique().tolist()  # 获取该分类标签的不同level
            label_entropy = 0.0  # 用于累加各水平的信息熵；分类标签的信息熵等于该分类标签的各水平信息熵与其概率积的和。
            for level in levels: # 循环计算不同水平的信息熵
                level_data = dataSet[dataSet[label] == level]  # 获取该水平的数据集
                prob = level_data.shape[0] / dataSet.shape[0]  # 计算该水平的数据集在总数据集的占比
                # 计算香农熵，并更新到label_entropy中
                label_entropy += prob * self._entropy(level_data) # _entropy用于计算香农熵
            # 计算信息增益
            info_gain = init_entropy - label_entropy  # 代码至此，已经能够循环计算每个分类标签的信息增益
            # 用best_info_gain来取info_gain的最大值，并获取对应的分类标签
            if info_gain > best_info_gain:  
                best_info_gain = info_gain
                best_label = label
            # 这里保存一下每一次计算的信息增益，便于查看和检查错误
            self.gain.setdefault(self.__count, {})  # 建立本次函数调用时的字段，设其value为字典
            self.gain[self.__count][label] = info_gain  # 把本次函数调用时计算的各个标签数据存到字典里
        self.__count += 1
        return best_label
    
    def _top_amount_level(self, target_list):
        class_count = target_list.value_counts().to_dict()  # 计算靶标签的不同水平的样本量，并转化为字典
        # 字典的items方法可以将键值对转成[(), (), ...]，可以使用列表方法
        sorted_class_count = sorted(class_count.items(), key=lambda x:x[1], reverse=True)
        return sorted_class_count[0][0]
        
    def mktree(self, dataSet):
        """创建决策树"""
        target_list = dataSet.iloc[:, -1]  # target_list 靶标签的那一列数据
        # 程序终止条件一: 靶标签(数据集的最后一列因变量)在该数据集上只有一个水平，返回该水平
        if target_list.unique().shape[0] <= 1:
            return target_list[0] # ！！！
        # 程序终止条件二: 数据集只剩下把标签这一列数据；返回数量最多的水平
        if dataSet.shape[1] == 1:
            return self._top_amount_level(target_list)
        # 不满足终止条件时，做如下递归处理
        # 1.选择最佳分类标签
        best_label = self._best_split(dataSet)   
        # 2.递归计算最佳分类标签的不同水平的子数据集的信息增益
        #   各个子数据集的最佳分类标签的不同水平...
        #   ... 
        #   直至递归结束
        best_label_levels = dataSet[best_label].unique().tolist()
        tree = {best_label: {}}    # 生成字典，用于保存树状分类信息；这里不能用self.tree = {}存储
        for level in best_label_levels:
            level_subdata = self._split_dataSet(dataSet, best_label, level)  # 获取该水平的子数据集
            tree[best_label][level] = self.mktree(level_subdata)  # 返回结果
        return tree
    
    def predict(self, tree, labels, test_sample):
        """
        对单个样本进行分类
        tree: 训练的字典
        labels: 除去最后一列的其它字段
        test_sample: 需要分类的一行记录数据
        """
        firstStr = list(tree.keys())[0]           # tree字典里找到第一个用于分类键值对
        secondDict = tree[firstStr]
        featIndex = labels.index(firstStr)  # 找到第一个建(label)在给定label的索引
        for key in secondDict.keys():
            if test_sample[featIndex] == key:  # 找到test_sample在当前label下的值
                if secondDict[key].__class__.__name__ == "dict":
                    classLabel = self.predict(secondDict[key], labels, test_sample)
                else:
                    classLabel = secondDict[key]
        return classLabel
    
    def _unit_test(self):
        """用于测试_entropy函数"""
        data = [[1, 1, "yes"], 
                [1, 1, "yes"],
                [1, 0, "no"],
                [0, 1, "no"],
                [0, 1, "no"],]
        data = pd.DataFrame(data=data, columns=["a", "b", "c"])
        # return data # 到此行，用于测试_entropy
        # return self._split_dataSet(data, "a", 1)  # 到此行，用于测试_split_dataSet
        # return self._best_split(data)  # 到此行，用于测试_best_split
        # return self.mktree(self.dataSet)  # 到此行，用于测试主程序mktree
        self.tree = self.mktree(self.dataSet)  # 到此行，用于测试主程序mktree
        labels = ["age", "income", "student", "reputation"]
        test_sample = [0, 1, 0, 0]   # [0, 1, 0, 0, "no"]
        outcome = self.predict(self.tree, labels, test_sample)
        print("The truth class is %s, The ID3Tree outcome is %s." % ("no", outcome))

　　测试代码如下:

model = ID3Tree()
model._unit_test()
# print(json.dumps(model.gain, indent="  "))  # 可以查看每次递归时的信息熵
# print(json.dumps(model.tree, indent="  "))  # 查看树

# The truth class is no, The ID3Tree outcome is no.

　　2、sklearn实现ID3算法

　　sklearn将决策时算法分为两类:DecisionTreeClassifier和DecisionTreeRegressor。在实例化对象时，可以选择设置一些参数。DecisionTreeClassifier适用于分类变量，DecisionTreeRegressor适用于连续变量。

import sklearn
from sklearn.datasets import load_iris
from sklearn.model_selection import cross_val_score
from sklearn.tree import DecisionTreeClassifier
clf = DecisionTreeClassifier(random_state=0, criterion="entropy", )
data = np.array(model.dataSet.iloc[:, :-1])  # model是上面代码的model
target = np.array(model.dataSet.iloc[:, -1])
clf.fit(data, target)
clf.predict([data[0]])  # 预测第一条数据

# array(['no'], dtype=object)  # target[0]也为no

　　3、ID3的局限性：

　　　　1.ID3没有考虑连续特征

　　　　2.ID3采用信息增益大的特征优先建立决策树的节点。在相同条件下，取值比较多的特征比取值少的特征信息增益大。

　　　　3.ID3算法对于缺失值的情况没有做考虑

　　　　4.没有考虑过拟合的问题