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

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

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

import numpy as np
import pandas as pd

def calc_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


def calc_condition_entropy(feature, y_label):
    """
   当前属性为划分结点的条件熵
    :param feature: 传入的某一个特征
    :param y_label: 对应某一特征的类别值
    :return:
    """
    # 获取某特征的不同取值,unique会把列表元素去重
    feature_label = np.unique(feature)
    cond_ent = 0
    for 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


def gain_info(feature, y_label):
    """
    计算当前特征的信息增益，
    :param feature:
    :param y_label:
    :return:
    """
    return calc_entropy(y_label) - calc_condition_entropy(feature, y_label)


def data_processing(path):
    data = pd.read_csv(path).iloc[:, 1:]
    # 将数据特征和标签分别进行提取
    # 传入最后一列，就是西瓜种类的标签，好瓜还是坏瓜
    label = data.iloc[:, -1] # 最后一列是标签
    # 提取每一列特征
    features = []
    for i in range(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 in range(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

def calc_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


def calc_condition_entropy(feature, y_label):
    """
   当前属性为划分结点的条件熵
    :param feature: 传入的某一个特征
    :param y_label: 对应某一特征的类别值
    :return:
    """
    # 获取某特征的不同取值,unique会把列表元素去重
    feature_label = np.unique(feature)
    cond_ent = 0
    for 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


def gain_info(feature, y_label):
    """
    计算当前特征的信息增益，
    :param feature:
    :param y_label:
    :return:
    """
    return calc_entropy(y_label) - calc_condition_entropy(feature, y_label)


def data_processing(path):
    data = pd.read_csv(path).iloc[:, 1:]
    # 将数据特征和标签分别进行提取
    # 传入最后一列，就是西瓜种类的标签，好瓜还是坏瓜
    label = data.iloc[:, -1] # 最后一列是标签
    # 提取每一列特征
    features = []
    for i in range(8):
        features.append(data.iloc[:, i])
    return data, label, features


def id3_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)
    # 当前结点包含的样本属于同一类别，无需划分
    if len(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 in range(class_num)]
    max_class, max_len = max(class_len, key=lambda x : x[1])
    # 特征集为空的话，投票法来做，取样本量最大所对应的类别
    if len(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-python
import pandas as pd

def binarization_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))  # 重排为784
    return pd.DataFrame(features)

def target_encode(y_target):
    """
    对非数值类别进行数值化
    :param y_target: 类别
    :return:
    """
    y_labels = list(set(y_target))
    y_labels_dict = dict()
    for i, label in enumerate(y_labels):
        y_labels_dict[str(float(i))] = label
    y_encode = np.zeros(len(y_target))
    for i, y in enumerate(y_target):
        y_encode[i] = y_labels.index(y)
    return y_encode, len(y_labels), y_labels_dict

TreeUtils:

class TreeUtils:
    """
    决策树工具类， 封装树的信息
    """
    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

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

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

运行效果：