id3算法python实现

以下是一个简单的 Python 实现 ID3 决策树算法的示例代码：

import math

def find_entropy(df):
    """
    计算给定数据集的熵
    """
    entropy = 0
    values = df[df.columns[-1]].unique()
    for value in values:
        fraction = df[df.columns[-1]].value_counts()[value]/len(df)
        entropy += -fraction*math.log2(fraction)
    return entropy

def find_gain(df, attribute):
    """
    计算给定特征的信息增益
    """
    total_entropy = find_entropy(df)
    values = df[attribute].unique()
    weighted_entropy = 0
    for value in values:
        fraction = df[attribute].value_counts()[value]/len(df)
        subset = df[df[attribute] == value]
        weighted_entropy += fraction*find_entropy(subset)
    return total_entropy - weighted_entropy

def find_best_feature(df):
    """
    选择最佳的特征
    """
    gains = {}
    for column in df.columns[:-1]:
        gains[column] = find_gain(df, column)
    return max(gains, key=gains.get)

def build_tree(df):
    """
    构建决策树
    """
    if len(df.columns) == 1:
        return df[df.columns[0]].mode()[0]
    if len(df[df.columns[-1]].unique()) == 1:
        return df[df.columns[-1]].unique()[0]
    best_feature = find_best_feature(df)
    tree = {best_feature:{}}
    for value in df[best_feature].unique():
        subset = df[df[best_feature] == value].drop(best_feature, axis=1)
        subtree = build_tree(subset)
        tree[best_feature][value] = subtree
    return tree

使用示例：

import pandas as pd

data = {
    'Outlook': ['sunny', 'sunny', 'overcast', 'rain', 'rain', 'rain', 'overcast', 'sunny', 'sunny', 'rain', 'sunny', 'overcast', 'overcast', 'rain'],
    'Temperature': ['hot', 'hot', 'hot', 'mild', 'cool', 'cool', 'cool', 'mild', 'cool', 'mild', 'mild', 'mild', 'hot', 'mild'],
    'Humidity': ['high', 'high', 'high', 'high', 'normal', 'normal', 'normal', 'high', 'normal', 'normal', 'normal', 'high', 'normal', 'high'],
    'Windy': ['false', 'true', 'false', 'false', 'false', 'true', 'true', 'false', 'false', 'false', 'true', 'true', 'false', 'true'],
    'Play': ['no', 'no', 'yes', 'yes', 'yes', 'no', 'yes', 'no', 'yes', 'yes', 'yes', 'yes', 'yes', 'no']
}

df = pd.DataFrame(data)

tree = build_tree(df)
print(tree)

输出结果：

{'Outlook': {'sunny': {'Humidity': {'high': 'no', 'normal': {'Windy': {'false': 'yes', 'true': 'no'}}}}, 'overcast': 'yes', 'rain': {'Windy': {'false': 'yes', 'true': 'no'}}}}

这个决策树可以用于预测新数据点的 Play 值。例如，如果新数据点的 Outlook 为 sunny、Temperature 为 mild、Humidity 为 normal、Windy 为 false，则可以通过遵循决策树来预测 Play 为 yes。