统计学习：决策树实现与梯度下降法（python实现， ID3算法）

一、ID3算法
ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归的构建决策树。具体方法是：从根节点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子节点；在对子结点递归的调用以上方法，构建决策树；直到所有特征的信息增益均很小或者没有特征可以选择为止。
在统计论里，熵是表示随机变量不确定性的度量。熵越大，随机变量的不确定性越大。
信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。
简而言之：信息增益大的特征具有更强的分类能力
计算信息增益的步骤：
1、计算数据集D的经验熵
2、计算特征A对数据集D的经验条件熵
3、计算信息增益

二、 代码实现求解信息增益
下面的代码实现了对西瓜的分类求解熵和信息增益的过程，其中特征值取了前六个特征。

import numpy as np
import pandas as pd

defcalc_entropy(labels):"""
    计算信息熵
    :param labels: 当前选择的数据集对应的类别值。
    :return: 信息熵
    """
    entropy =0# 获取不同的类别值
    x_label_array = np.unique(labels)for x in x_label_array:# 布尔索引每个类别的样本
        sub_y = labels[labels == x]# 计算各类别所占数据集的比例
        p =len(sub_y)/len(labels)# 对应公式， 累加信息熵
        entropy -= p*np.log2(p)return entropy

defcalc_condition_entropy(feature, y_label):"""
   当前属性为划分结点的条件熵
    :param feature: 传入的某一个特征
    :param y_label: 对应某一特征的类别值
    :return:
    """# 获取某特征的不同取值,unique会把列表元素去重
    feature_label = np.unique(feature)
    cond_ent =0for f in feature_label:# 提取出来当下特征的正负样本数
        sub_y = y_label[f == feature]# 当下特征对应的信息熵
        feature_ent = calc_entropy(sub_y)
        cond_ent +=len(sub_y)/len(y_label)* feature_ent
    return cond_ent

defgain_info(feature, y_label):"""
    计算当前特征的信息增益，
    :param feature:
    :param y_label:
    :return:
    """return calc_entropy(y_label)- calc_condition_entropy(feature, y_label)defdata_processing(path):
    data = pd.read_csv(path).iloc[:,1:]# 将数据特征和标签分别进行提取# 传入最后一列，就是西瓜种类的标签，好瓜还是坏瓜
    label = data.iloc[:,-1]# 最后一列是标签# 提取每一列特征
    features =[]for i inrange(8):
        features.append(data.iloc[:, i])return data, label, features

if __name__ =='__main__':
    gain_information ={}
    feature_label =['色泽','根蒂','敲声','纹理','脐部','触感','甜度','含糖率']
    data, label, features = data_processing('ID3tree\\datasets\\watermelon.csv')
    entropy = calc_entropy(label)for i inrange(6):
        gain = gain_info(features[i], label)
        gain_information.update({feature_label[i]:gain})print(gain_information)

最后以字典形式保存计算完成的每个特征所对应的信息增益

三、构建决策树
有了各个特征的信息增益 ，就可按照前面提到的构建方法进行构建决策树，先选择信息增益大的特征，其具有更好的分类效果。
1、程序运行文件代码：

import numpy as np
import pandas as pd
from ID3tree.tree_utils.TreeUtils import TreeUtils
from ID3tree.tree_utils.Data_Encoding import target_encode
global class_num
global epsilon

defcalc_entropy(labels):"""
    计算信息熵
    :param labels: 当前选择的数据集对应的类别值。
    :return: 信息熵
    """
    entropy =0# 获取不同的类别值
    x_label_array = np.unique(labels)for x in x_label_array:# 布尔索引每个类别的样本
        sub_y = labels[labels == x]# 计算各类别所占数据集的比例
        p =len(sub_y)/len(labels)# 对应公式， 累加信息熵
        entropy -= p*np.log2(p)return entropy

defcalc_condition_entropy(feature, y_label):"""
   当前属性为划分结点的条件熵
    :param feature: 传入的某一个特征
    :param y_label: 对应某一特征的类别值
    :return:
    """# 获取某特征的不同取值,unique会把列表元素去重
    feature_label = np.unique(feature)
    cond_ent =0for f in feature_label:# 提取出来当下特征的正负样本数
        sub_y = y_label[f == feature]# 当下特征对应的信息熵
        feature_ent = calc_entropy(sub_y)
        cond_ent +=len(sub_y)/len(y_label)* feature_ent
    return cond_ent

defgain_info(feature, y_label):"""
    计算当前特征的信息增益，
    :param feature:
    :param y_label:
    :return:
    """return calc_entropy(y_label)- calc_condition_entropy(feature, y_label)defdata_processing(path):
    data = pd.read_csv(path).iloc[:,1:]# 将数据特征和标签分别进行提取# 传入最后一列，就是西瓜种类的标签，好瓜还是坏瓜
    label = data.iloc[:,-1]# 最后一列是标签# 提取每一列特征
    features =[]for i inrange(8):
        features.append(data.iloc[:, i])return data, label, features

defid3_tree_fit(train_set, train_label, features):"""
    递归实现ID3算法，以信息增益最大的特征作为划分方法
    1、 递归出口是什么
    2、 递归体是什么
    :param train_set:递归产生的样本数据集
    :param train_label:递归产生的，对应样本数据的类别标签值
    :param features: 特征索引列表
    :return:
    """# 标签列表
    y_label =["好瓜","坏瓜"]
    feature_label =['色泽','根蒂','敲声','纹理','脐部','触感']# 叶子结点
    LEAF ="leaf"# 内部结点类型
    INTERNAL ="internal"
    label_unique = np.unique(train_label)# 当前结点包含的样本属于同一类别，无需划分iflen(label_unique)==1:print("类别：", y_label[int(label_unique[0])])return TreeUtils(LEAF, Class=label_unique[0])# 不同类别所对应的样本量
    class_len =[(i,len(list(filter(lambda x: x == i, train_label))))for i inrange(class_num)]
    max_class, max_len =max(class_len, key=lambda x : x[1])# 特征集为空的话，投票法来做，取样本量最大所对应的类别iflen(features)==0:print("类别：", max_class)return TreeUtils(LEAF, Class=max_class)
    max_feature, max_gain =0,0# 计算每个特征的信息增益，选择信息增益最大特征划分结点依据for feature in features:
        feature_data = train_set.iloc[:, feature]# 计算信息增益
        feature_gain = gain_info(feature_data, train_label)print("特征是： %s, 信息增益是; %f"%(feature_label[feature], feature_gain))if feature_gain > max_gain:
            max_feature, max_gain = feature, feature_gain
    # 如果最大信息增益也比较小，那么就将不再划分if max_gain < epsilon:print("类别：", max_class)return TreeUtils(LEAF, Class=max_class)# 构造内部结点
    tree = TreeUtils(INTERNAL, Class=max_feature)print('-'*60)print("最佳划分特征： %s，最大信息增益： %f "%(feature_label[max_feature], max_gain))print("="*60)# 构建完当前的最大信息增益特征之后，需要删除该特征，不让其再出现在接下来的位置
    sub_feature =list(filter(lambda x : x !=max_feature, features))# 当前最佳划分结点的样本值
    max_feature_col = train_set.iloc[:, max_feature]# 提取该特征的对应的特征变量
    max_feature_unique_values = np.unique(max_feature_col)for feature_value in max_feature_unique_values:print("当特征为【%s】时， 值为【%s】"%(feature_label[max_feature], feature_value))# 提取特征变量对应的样本
        sub_train_set = train_set[train_set.iloc[:, max_feature]== feature_value]# 提取样本对应的标签
        sub_train_label = train_label[train_set.iloc[:, max_feature]== feature_value]
        sub_tree = id3_tree_fit(sub_train_set, sub_train_label, sub_feature)
        tree.add_tree(feature_value, sub_tree)return tree

if __name__ =='__main__':# 信息增益阈值，小于该值即为叶子结点
    epsilon =1e-3

    data, label, features = data_processing('ID3tree\\datasets\\watermelon.csv')# 对于二分类问题，将类别的文字叙述改为用0和1来表示
    y_encode, class_num, y_label_dict = target_encode(label)
    train_set = data.iloc[:,:-3]
    feature_index =list(range(train_set.shape[1]))
    id3_tree_fit(train_set, y_encode, feature_index)

2、工具包软件代码

# -*- coding: UTF-8 -*-"""
@author:Lenovo
@file:Data_Encoding.py
@time:2021/04/21
"""import numpy as np
import cv2  # pip install opencv-python，pip install opencv-contrib-pythonimport pandas as pd

defbinarization_features(train_set, feature_len):"""
    对训练集中数据进行二值化
    :param train_set: 训练集图片数组
    :return: 二值化后的图片数组
    """
    features =[]# 存储二值化后的图像for img in train_set:
        img = np.reshape(img,(28,28))# 重排28*28
        cv_img = img.astype(np.uint8)# 像素范围0-255# cv2.threshold (源图片, 阈值, 填充色, 阈值类型)
        _, cv_img = cv2.threshold(cv_img,50,1, cv2.THRESH_BINARY_INV)
        features.append(cv_img)# 追加到列表
    features = np.reshape(np.array(features),(-1, feature_len))# 重排为784return pd.DataFrame(features)deftarget_encode(y_target):"""
    对非数值类别进行数值化
    :param y_target: 类别
    :return:
    """
    y_labels =list(set(y_target))
    y_labels_dict =dict()for i, label inenumerate(y_labels):
        y_labels_dict[str(float(i))]= label
    y_encode = np.zeros(len(y_target))for i, y inenumerate(y_target):
        y_encode[i]= y_labels.index(y)return y_encode,len(y_labels), y_labels_dict

TreeUtils:

classTreeUtils:"""
    决策树工具类， 封装树的信息
    """def__init__(self, node_type, Class=None, best_feature=None):# 决策树结点类型（内部结点， 叶子结点）
        self.node_type = node_type
        # 键是最佳信息增益对应特征 值：以最佳特征的某个取值为根节点的子树
        self.tree_dict =dict()# 叶子结点所对应类别值
        self.Class = Class
        # 最佳划分特征
        self.best_feature = best_feature

    defadd_tree(self, key, tree):
        self.tree_dict[key]= tree

全部代码包含数据集已经上传至资源区，欢迎使用

运行效果：