【人工智能】决策树实验

一、实验目的

(1) 熟悉和掌握决策树的分类原理、实质和过程

(2) 掌握典型的学习算法和实现技术

二、实验环境

具有相关编程软件的 PC 机

三、实验内容

根据上一个实验给出的数据集，分别用ID3、C4.5、CART决策树进行西瓜好坏的分类决策。

表1 西瓜数据集的训练样本集和测试样本集划分

四、实验原理

决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度，使用算法ID3，C4.5和C5.0生成树算法使用熵。

最经典的决策树算法有ID3、C4.5、CART，其中ID3算法是最早被提出的，它可以处理离散属性样本的分类，C4.5和CART算法则可以处理更加复杂的分类问题。

利用信息增益选择最优划分属性

样本有多个属性，该先选哪个样本来划分数据集呢？原则是随着划分不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一分类，即“纯度”越来越高。

1.信息熵（information entropy）

样本集合D中第k类样本所占的比例（k=1,2,…,|Y|），|Y|为样本分类的个数，则D的信息熵为：

Ent(D)的值越小，则D的纯度越高。直观理解一下：假设样本集合有2个分类，每类样本的比例为1/2，Ent(D)=1；只有一个分类，Ent（D）= 0，显然后者比前者的纯度高。

2.信息增益（information gain）

使用属性a对样本集D进行划分所获得的“信息增益”的计算方法是，用样本集的总信息熵减去属性a的每个分支的信息熵与权重（该分支的样本数除以总样本数）的乘积，通常，信息增益越大，意味着用属性a进行划分所获得的“纯度提升”越大。因此，优先选择信息增益最大的属性来划分。设属性a有V个可能的取值，则属性a的信息增益为：

3.增益率（gain ratio）

基于信息增益的最优属性划分原则——信息增益准则，对可取值数据较多的属性有所偏好。C4.5算法使用增益率代替信息增益来选择最优划分属性，增益率定义为：

其中

称为属性 a 的固有值。属性 a 的可能取值数目越多（即V VV越大），则 I V ( a ) IV(a)IV(a) 的值通常会越大。这在一定程度上消除了对可取值数据较多的属性的偏好。

事实上，增益率准则对可取值数目较少的属性有所偏好，C 4.5 C4.5C4.5 算法并不是直接使用增益率准则，而是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

4.基尼指数（Gini index）

CART 决策树算法使用基尼指数（Gini index）来选择划分属性。数据集 D 的纯度可用基尼值来度量：

Gini(D) 反应了从数据集 D  中随机抽取两个样本，其类别标记不一致的概率。由此，Gini(D) 越小，纯度越高。属性 a 的基尼指数定义为：

在候选属性集合 A AA 中，选择那个使得划分后基尼指数最小的属性作为最优化分属性。即

五、实验过程

西瓜数据集

西瓜数据集各个特征的含义如下：

（1）使用ID3决策树进行西瓜好坏的分类决策

l 计算信息熵函数

l 划分数据集函数

l 计算信息增益函数

l 递归构建决策树

l 读取数据

l 输出

（2）使用C4.5决策树进行西瓜好坏的分类决策

l 计算信息熵函数

l 划分数据集函数

l 计算信息增益函数

l 递归构建决策树

l 读取数据

l 输出

（3）使用CART决策树进行西瓜好坏的分类决策

l 计算信息熵函数

l 划分数据集函数

l 计算信息增益函数

l 递归构建决策树

l 读取数据

l 输出

上述过程python代码输入如下：

（1）使用ID3决策树进行西瓜好坏的分类决策

import pandas as pdimport numpy as np

#计算信息熵def cal_information_entropy(data):    data_label = data.iloc[:,-1]    label_class =data_label.value_counts() #总共有多少类    Ent = 0    for k in label_class.keys():        p_k = label_class[k]/len(data_label)        Ent += -p_k*np.log2(p_k)    return Ent

#计算给定数据属性a的信息增益def cal_information_gain(data, a):    Ent = cal_information_entropy(data)    feature_class = data[a].value_counts() #特征有多少种可能    gain = 0    for v in feature_class.keys():        weight = feature_class[v]/data.shape[0]        Ent_v = cal_information_entropy(data.loc[data[a] == v])        gain += weight*Ent_v    return Ent - gain

#获取标签最多的那一类def get_most_label(data):    data_label = data.iloc[:,-1]    label_sort = data_label.value_counts(sort=True)    return label_sort.keys()[0]

#挑选最优特征，即信息增益最大的特征def get_best_feature(data):    features = data.columns[:-1]    res = {}    for a in features:        temp = cal_information_gain(data, a)        res[a] = temp    res = sorted(res.items(),key=lambda x:x[1],reverse=True)    return res[0][0]

##将数据转化为（属性值：数据）的元组形式返回，并删除之前的特征列def drop_exist_feature(data, best_feature):    attr = pd.unique(data[best_feature])    new_data = [(nd, data[data[best_feature] == nd]) for nd in attr]    new_data = [(n[0], n[1].drop([best_feature], axis=1)) for n in new_data]    return new_data

#创建决策树def create_tree(data):    data_label = data.iloc[:,-1]    if len(data_label.value_counts()) == 1: #只有一类        return data_label.values[0]    if all(len(data[i].value_counts()) == 1 for i in data.iloc[:,:-1].columns): #所有数据的特征值一样，选样本最多的类作为分类结果        return get_most_label(data)    best_feature = get_best_feature(data) #根据信息增益得到的最优划分特征    Tree = {best_feature:{}} #用字典形式存储决策树    exist_vals = pd.unique(data[best_feature]) #当前数据下最佳特征的取值    if len(exist_vals) != len(column_count[best_feature]): #如果特征的取值相比于原来的少了        no_exist_attr = set(column_count[best_feature]) - set(exist_vals) #少的那些特征        for no_feat in no_exist_attr:            Tree[best_feature][no_feat] = get_most_label(data) #缺失的特征分类为当前类别最多的

    for item in drop_exist_feature(data,best_feature): #根据特征值的不同递归创建决策树        Tree[best_feature][item[0]] = create_tree(item[1])    return Tree

#{'纹理': {'清晰': {'根蒂': {'蜷缩': 1, '稍蜷': {'色泽': {'青绿': 1, '乌黑': {'触感': {'硬滑': 1, '软粘': 0}}}}, '硬挺': 0}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}def predict(Tree , test_data):    first_feature = list(Tree.keys())[0]    second_dict = Tree[first_feature]    input_first = test_data.get(first_feature)    input_value = second_dict[input_first]    if isinstance(input_value , dict): #判断分支还是不是字典        class_label = predict(input_value, test_data)    else:        class_label = input_value    return class_label

if __name__ == '__main__':    #读取数据    data = pd.read_csv('data_word.csv')

    #统计每个特征的取值情况作为全局变量    column_count = dict([(ds, list(pd.unique(data[ds]))) for ds in data.iloc[:, :-1].columns])

    #创建决策树    dicision_Tree = create_tree(data)    print(dicision_Tree)    #测试数据    test_data_1 = {'色泽':'青绿','根蒂':'蜷缩','敲声':'浊响','纹理':'稍糊','脐部':'凹陷','触感':'硬滑'}    test_data_2 = {'色泽': '乌黑', '根蒂': '稍蜷', '敲声': '浊响', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑'}    result = predict(dicision_Tree,test_data_2)    print('分类结果为'+'好瓜'if result == 1 else '坏瓜')

    # 绘制可视化树

    import matplotlib.pylab as plt    import matplotlib

    # 能够显示中文    matplotlib.rcParams['font.sans-serif'] = ['SimHei']    matplotlib.rcParams['font.serif'] = ['SimHei']

    # 分叉节点，也就是决策节点    decisionNode = dict(boxstyle="sawtooth", fc="0.8")

    # 叶子节点    leafNode = dict(boxstyle="round4", fc="0.8")

    # 箭头样式    arrow_args = dict(arrowstyle="