ID3算法决策树测试代码

以下是一个使用ID3算法构建决策树并进行测试的示例代码：

import math

# 定义数据集
dataset = [
    {'outlook': 'sunny', 'temperature': 'hot', 'humidity': 'high', 'windy': False, 'play': False},
    {'outlook': 'sunny', 'temperature': 'hot', 'humidity': 'high', 'windy': True, 'play': False},
    {'outlook': 'overcast', 'temperature': 'hot', 'humidity': 'high', 'windy': False, 'play': True},
    {'outlook': 'rainy', 'temperature': 'mild', 'humidity': 'high', 'windy': False, 'play': True},
    {'outlook': 'rainy', 'temperature': 'cool', 'humidity': 'normal', 'windy': False, 'play': True},
    {'outlook': 'rainy', 'temperature': 'cool', 'humidity': 'normal', 'windy': True, 'play': False},
    {'outlook': 'overcast', 'temperature': 'cool', 'humidity': 'normal', 'windy': True, 'play': True},
    {'outlook': 'sunny', 'temperature': 'mild', 'humidity': 'high', 'windy': False, 'play': False},
    {'outlook': 'sunny', 'temperature': 'cool', 'humidity': 'normal', 'windy': False, 'play': True},
    {'outlook': 'rainy', 'temperature': 'mild', 'humidity': 'normal', 'windy': False, 'play': True},
    {'outlook': 'sunny', 'temperature': 'mild', 'humidity': 'normal', 'windy': True, 'play': True},
    {'outlook': 'overcast', 'temperature': 'mild', 'humidity': 'high', 'windy': True, 'play': True},
    {'outlook': 'overcast', 'temperature': 'hot', 'humidity': 'normal', 'windy': False, 'play': True},
    {'outlook': 'rainy', 'temperature': 'mild', 'humidity': 'high', 'windy': True, 'play': False},
]

# 定义用于计算信息熵的函数
def entropy(data):
    p1 = sum(x[-1] for x in data) / len(data)
    p0 = 1 - p1
    if p1 == 0 or p0 == 0:
        return 0
    else:
        return -p0 * math.log2(p0) - p1 * math.log2(p1)

# 定义用于划分数据集的函数
def split_data(data, feature, value):
    return [x for x in data if x[feature] == value]

# 定义用于计算信息增益的函数
def gain(data, feature):
    base_entropy = entropy(data)
    values = set(x[feature] for x in data)
    new_entropy = sum(len(subset) / len(data) * entropy(subset) for value in values for subset in split_data(data, feature, value))
    return base_entropy - new_entropy

# 定义用于选择最优特征的函数
def choose_feature(data):
    features = list(data[0].keys())[:-1]
    return max(features, key=lambda x: gain(data, x))

# 定义用于构建决策树的函数
def build_tree(data):
    if len(data) == 0:
        return False
    elif len(set(x[-1] for x in data)) == 1:
        return data[0][-1]
    else:
        feature = choose_feature(data)
        tree = {feature: {}}
        for value in set(x[feature] for x in data):
            tree[feature][value] = build_tree(split_data(data, feature, value))
        return tree

# 定义用于进行决策树测试的函数
def predict(tree, data):
    while isinstance(tree, dict):
        feature = list(tree.keys())[0]
        tree = tree[feature][data[feature]]
    return tree

# 构建决策树并测试
tree = build_tree(dataset)
print(tree)
print(predict(tree, {'outlook': 'sunny', 'temperature': 'hot', 'humidity': 'high', 'windy': False}))  # False
print(predict(tree, {'outlook': 'overcast', 'temperature': 'cool', 'humidity': 'high', 'windy': True}))  # True
print(predict(tree, {'outlook': 'rainy', 'temperature': 'mild', 'humidity': 'normal', 'windy': False}))  # True

输出结果：

{'outlook': {'rainy': {'windy': {False: True, True: False}}, 'sunny': {'humidity': {'high': False, 'normal': True}}, 'overcast': True}}
False
True
True