从底层实现决策树并分类实战

import mathimport collections

# 构建数据集def createDataSet():
    data_set = [[0, 0, 0, 0, 0],
               [0, 0, 0, 1, 0],
               [0, 1, 0, 1, 1],
               [0, 1, 1, 0, 1],
               [0, 0, 0, 0, 0],
               [1, 0, 0, 0, 0],
               [1, 0, 0, 1, 0],
               [1, 1, 1, 1, 1],
               [1, 0, 1, 2, 1],
               [1, 0, 1, 2, 1],
               [2, 0, 1, 2, 1],
               [2, 0, 1, 1, 1],
               [2, 1, 0, 1, 1],
               [2, 1, 0, 2, 1],
               [2, 0, 0, 0, 0]]
    labels = ['年龄大小', '工作与否', '是否有房', '信贷情况']    return data_set, labels

data_set,labels=createDataSet()

# 计算香农熵def entropy(data_set):
    n = len(data_set)
    labels=[line[-1] for line in data_set]    # print(labels)
    labels_dict=collections.Counter(labels)    # print(labels_dict)
    entropy = 0
    for key in labels_dict:
        prob = labels_dict[key] / n
        entropy -= prob * math.log2(prob)    return entropy

entropy(data_set)

# 根据指定特征划分数据集def splitDataSet(data_set, col, value):
    reduce_dataset = []    for line in data_set:        if line[col] == value:
            line_split=line[:col]+line[col+1:]
            reduce_dataset.append(line_split)    return reduce_dataset

splitDataSet(data_set,4,1)

# 选择最好的特征def chooseBestFeature(data_set):
    num_features = len(data_set[0]) - 1
    entropy_dataset = entropy(data_set)
    info_gain_end = 0
    best_feature = -1
    # 遍历所有特征
    for i in range(num_features):        # 每个特征中的所有取值
        unique_vals = set([example[i] for example in data_set])
        new_entropy = 0
        for value in unique_vals:
            sub_dataSet = splitDataSet(data_set, i, value)
            prob = len(sub_dataSet) / len(data_set)            # 条件熵
            new_entropy += prob * entropy(sub_dataSet)

        info_gain = entropy_dataset - new_entropy        
        # print(f"第{i}个特征的信息增益为{info_gain:.3f}")
        if (info_gain > info_gain_end):
            info_gain_end = info_gain
            best_feature = i    return best_feature

l_num=chooseBestFeature(data_set)print(f'最高的信息增益对应的特征列号为：{l_num}',end='')

# 获取label中出现次数最多的标签def majorityCnt(class_list):
    class_count = collections.Counter(class_list)
    sorted_class_count = sorted(class_count.items(), key = lambda c:c[1], reverse = True)    # print(sorted_class_count)
    return sorted_class_count[0][0]

majorityCnt([1,1,1,0,0,1,1])

# 递归创建决策树def createTree(data_set, labels, feat_labels):
    class_list = [example[-1] for example in data_set]    #类别完全相同停止划分
    if class_list.count(class_list[0]) == len(class_list):        return class_list[0]    #遍历到就剩下一个特征时，返回当前最多的lable
    if len(data_set[0]) == 1:                                       
        return majorityCnt(class_list)    #返回最高的信息增益对应的特征列号
    best_feat = chooseBestFeature(data_set)
    best_featlabel = labels[best_feat]
    feat_labels.append(best_featlabel)    #根据最优特征的标签生成树
    tree = {best_featlabel:{}}
    labels.remove(best_featlabel)    #得到训练集中所有最优特征的属性值
    feat_values = [example[best_feat] for example in data_set]
    unique_values = set(feat_values)    for value in unique_values:
        sub_labels=labels[:]        #遍历最优特征的属性值，使用splitDataSet分割
        tree[best_featlabel][value] = createTree(splitDataSet(data_set, best_feat, value), sub_labels, feat_labels)    return tree

# 使用决策树执行分类def classify(input_tree, feat_labels, test_value):
    first_str = next(iter(input_tree))
    second_dict = input_tree[first_str]
    feat_index = feat_labels.index(first_str)    for key in second_dict.keys():        if test_value[feat_index] == key:            if type(second_dict[key]).__name__ == 'dict':
                classLabel = classify(second_dict[key], feat_labels, test_value)            else:
                classLabel = second_dict[key]    return classLabel

# 测试dataSet, labels = createDataSet()
featLabels = []
tree = createTree(dataSet, labels, featLabels)print(tree)print(featLabels)print(f'测试数据 无房有工作 [0, 1] ->',end=' ')
test_value = [0, 1]
result = classify(tree, featLabels, test_value)if result == 1:    print('放贷')if result == 0:    print('不放贷')print(f'测试数据 无房无工作 [0, 0] ->',end=' ')
test_value = [0, 0]
result = classify(tree, featLabels, test_value)if result == 1:    print('放贷')if result == 0:    print('不放贷')print(f'测试数据 有房无工作 [1, 0] ->',end=' ')
test_value = [1, 0]
result = classify(tree, featLabels, test_value)if result == 1:    print('放贷')if result == 0:    print('不放贷')print(f'测试数据 有房有工作 [1, 1] ->',end=' ')
test_value = [1, 1]
result = classify(tree, featLabels, test_value)if result == 1:    print('放贷')if result == 0:    print('不放贷')

<br/>