欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

决策树之ID3算法

程序员文章站 2022-05-11 13:56:02
一、决策树之ID3算法简述 1976年-1986年,J.R.Quinlan给出ID3算法原型并进行了总结,确定了决策树学习的理论。这可以看做是决策树算法的起点。1993,Quinlan将ID3算法改进成C4.5算法,称为机器学习的十大算法之一。ID3算法的另一个分支是CART(Classificat ......

一、决策树之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.没有考虑过拟合的问题