• 决策树原理及Python代码实现 - CSDN

from math import log
import operator

'''
创建决策树进行分类的流程如下：
    1.创建数据集
    2.计算数据集的信息熵 !!
    3.遍历所有特征，选择信息熵最小的特征，即为最好的分类特征 !!
    4.根据上一步得到的分类特征分割数据集，并将该特征从列表中移除
    5.执行递归函数，返回第三步，不断分割数据集，直到分类结束 !!
    6.使用决策树执行分类，返回分类结果
'''

# 创建海洋生物数据集，判断是否是鱼类
my_labels = ['no surfacing', 'flippers']  # 是否浮出水面，是否有脚蹼
my_data = [
    [1, 1, 'yes'],
    [1, 1, 'yes'],
    [1, 0, 'no'],
    [0, 1, 'no'],
    [0, 1, 'no']
]


# 计算给定数据集的香农熵（信息熵）
def calc_shannon_entropy(dataset):
    # 实例总数 entry (计算机)事项
    num_entries = len(dataset)

    # 为所有可能分类创建字典，计算每一类的出现频数
    label_counts = {}
    for fv in dataset:
        label = fv[-1]  # 特征向量最后一个数据是label
        if label not in label_counts.keys():
            label_counts[label] = 0  # 如果不在，添加新label，并设为0
        label_counts[label] += 1  # 如果已在，老label+1

    # 计算熵
    shannon_entropy = 0.0
    for key in label_counts:
        prob = float(label_counts[key]) / num_entries  # 选择每一类的概率
        shannon_entropy -= prob * log(prob, 2)
    return shannon_entropy


# 划分数据集 执行一次得到一个子集
# axis: 用来划分数据的 特征
# value: 需要返回的特征值
def split_dataset(dataset, axis, value):
    ret_dataset = []
    for fv in dataset:
        if fv[axis] == value:
            reduced_fv = fv[:axis]  # 去掉 axis 表示的特征 去掉 fv[axis] 减1维
            reduced_fv.extend(fv[axis + 1:])
            ret_dataset.append(reduced_fv)  # 分割后的 fv 加入数据集
    return ret_dataset


# 选择最好的数据集划分方式，返回 最佳特征 所在位置
def choose_best_feature(dataset):
    base_entropy = calc_shannon_entropy(dataset)  # 信息熵
    base_info_gain = 0.0  # 信息增益
    base_feature = -1

    num_features = len(dataset[0]) - 1  # 减去最后一个label
    for i in range(num_features):
        # 以 fv[i] 分割数据集
        feature_list = [fv[i] for fv in dataset]  # 所有样本的 第i维特征值 组成的list
        unique_vals = set(feature_list)  # 去掉相同项

        # 计算熵变
        new_entropy = 0.0
        for val in unique_vals:
            sub_dataset = split_dataset(dataset, axis=i, value=val)  # 第i个特征 = 不同的val
            prob = len(sub_dataset) / len(dataset)  # 第i维=val的比例
            new_entropy += prob * calc_shannon_entropy(sub_dataset)  # 子集的熵
        # print(i, new_entropy)
        info_gain = base_entropy - new_entropy

        # 熵变越大，new_entropy 越小，剩下的混乱度越小
        if info_gain > base_info_gain:
            base_info_gain = info_gain
            base_feature = i

    return base_feature


# 如果数据集已经使用了所有特征向量属性，最后的类标签还不是唯一的
# 此时通过多数表决的方式 决定叶子节点的分类 比如 yes:no = 3:2 则认为该叶子节点是 yes
# class_list 是 一系列 labels 要统计每一类的数量
def majority_cnt(class_list):
    # 统计每一项 label 的 example 数量
    class_cnt = {}
    for vote in class_list:
        if vote not in class_cnt.keys():
            class_cnt[vote] = 0
        class_cnt[vote] += 1

    # 从大到小排序
    sorted_class_cnt = sorted(class_cnt.items(), key=operator.itemgetter(1), reverse=True)
    return sorted_class_cnt[0][0]


# 递归创建树
# labels 不是必要的，但是可以使树的结构清晰，每一次分割所用的特征很清楚地表示在字典的 key 里
def create_tree(dataset, labels):
    # 如果 dataset 中实例的类标签都相同，递归结束
    class_list = [fv[-1] for fv in dataset]
    if class_list.count(class_list[0]) == len(class_list):  # 说明class_list中只有一项
        return class_list[0]  # 返回label

    # 如果使用完了所有特征，递归结束
    # 因为这一情况下，还可能存在不同的类标签，所以使用多数表决
    if len(dataset[0]) == 1:  # 划分的 fv 只剩下最后一维: label
        return majority_cnt(class_list)

    # 得到当前分割的 最佳 特征
    best_feature = choose_best_feature(dataset)
    best_feature_label = labels[best_feature]

    # 字典类型
    tree = {
        best_feature_label: {}
    }

    # 特征集中去掉 这一特征
    labels.remove(best_feature_label)

    feature_vals = [fv[best_feature] for fv in dataset]
    unique_vals = set(feature_vals)
    for val in unique_vals:
        sub_labels = labels[:]  # 拷贝一份labels给一个递归位置使用，避免全局的labels可能在不同的递归位置出错
        tree[best_feature_label][val] = create_tree(split_dataset(dataset, axis=best_feature, value=val), sub_labels)

    return tree


# 使用决策树返回分类结果
def classify(tree, labels, test_vec):
    first_feature = list(tree.keys())[0]
    second_dict = tree[first_feature]
    label_index = labels.index(first_feature)

    class_label = 'null'
    for key in second_dict.keys():
        if test_vec[label_index] == key:
            if type(second_dict[key]).__name__ == 'dict':
                class_label = classify(second_dict[key], labels, test_vec)
            else:
                class_label = second_dict[key]
    return class_label


# 1.测试熵
def test_entropy():
    print(calc_shannon_entropy(my_data))  # 0.9709505944546686

    # 熵越高，说明混乱度越大，混合的数据越多
    # 修改第一个数据项，增加1个分类
    my_data[0][-1] = 'maybe'
    print(calc_shannon_entropy(my_data))  # 1.3709505944546687

    # 继续增加分类
    my_data[3][-1] = 'perhaps'
    print(calc_shannon_entropy(my_data))  # 1.9219280948873623

    # 全改成同一类
    for fv in my_data:
        fv[-1] = 'yes'
    print(calc_shannon_entropy(my_data))  # 0.0


# 2.测试划分数据集
def test_split():
    # 按照 fv[0] 划分数据集
    sub_dataset_axis01 = split_dataset(my_data, axis=0, value=1)  # 返回 fv[0]==1 的
    sub_dataset_axis00 = split_dataset(my_data, axis=0, value=0)  # 返回 fv[0]==0 的
    print(sub_dataset_axis01)
    print(sub_dataset_axis00)


# 3.测试获取最佳特征
def test_best_fv():
    print(choose_best_feature(my_data))


if __name__ == '__main__':
    tmp_labels = my_labels[:]  # create_tree 函数会改变 my_labels，所以存一份拷贝
    my_tree = create_tree(my_data, tmp_labels)
    fvs = [fv[:-1] for fv in my_data]
    for fv in fvs:
        print(fv, classify(my_tree, my_labels, fv))