博客

python实现ID3决策树算法

  • Post category:Python

下面是详细讲解“Python实现ID3决策树算法”的完整攻略，包含两个示例说明。

ID3决策树算法简介

ID3决策树算法是一种用于分类的算法。它使用信息增益来选择最佳特征，并递归地构建决策树。该算法可以用于二元分类和多元分类。

ID3决策树算法实现

下面是Python实现ID3决策树算法的代码：

import math

def entropy(data):
    n = len(data)
    counts = {}
    for item in data:
        label = item[-1]
        if label not in counts:
            counts[label] = 0
        counts[label] += 1
    entropy = 0
    for label in counts:
        p = counts[label] / n
        entropy -= p * math.log2(p)
    return entropy

def split_data(data, feature_index):
    values = {}
    for item in data:
        value = item[feature_index]
        if value not in values:
            values[value] = []
        values[value].append(item)
    return values

def information_gain(data, feature_index):
    n = len(data)
    gain = entropy(data)
    for value, subset in split_data(data, feature_index).items():
        p = len(subset) / n
        gain -= p * entropy(subset)
    return gain

def best_feature(data):
    best_index = 0
    best_gain = 0
    for i in range(len(data[0]) - 1):
        gain = information_gain(data, i)
        if gain > best_gain:
            best_gain = gain
            best_index = i
    return best_index

def majority_label(data):
    counts = {}
    for item in data:
        label = item[-1]
        if label not in counts:
            counts[label] = 0
        counts[label] += 1
    return max(counts, key=counts.get)

def build_tree(data):
    if len(data) == 0:
        return None
    if len(set(item[-1] for item in data)) == 1:
        return data[0][-1]
    feature_index = best_feature(data)
    feature_values = split_data(data, feature_index)
    tree = {feature_index: {}}
    for value, subset in feature_values.items():
        subtree = build_tree(subset)
        tree[feature_index][value] = subtree
    return tree

entropy函数计算数据集的熵。split_data函数将数据集拆分为特征值的子集。information_gain函数计算特征的信息增益。best_feature函数选择最佳特征。majority_label函数返回数据集中出现最多的标签。build_tree函数递归地构建决策树。

示例1：使用鸢尾花数据集构建决策树

让我们使用鸢尾花数据集构建决策树：

from sklearn.datasets import load_iris

iris = load_iris()
data = iris.data.tolist()
labels = iris.target.tolist()
for i in range(len(data)):
    data[i].append(labels[i])
tree = build_tree(data)
print(tree)

这将输出构建的决策树。

示例2：使用自定义数据集构建决策树

让我们使用自定义数据集构建决策树：

data = [
    ['sunny', 'hot', 'high', 'false', 'no'],
    ['sunny', 'hot', 'high', 'true', 'no'],
    ['overcast', 'hot', 'high', 'false', 'yes'],
    ['rainy', 'mild', 'high', 'false', 'yes'],
    ['rainy', 'cool', 'normal', 'false', 'yes'],
    ['rainy', 'cool', 'normal', 'true', 'no'],
    ['overcast', 'cool', 'normal', 'true', 'yes'],
    ['sunny', 'mild', 'high', 'false', 'no'],
    ['sunny', 'cool', 'normal', 'false', 'yes'],
    ['rainy', 'mild', 'normal', 'false', 'yes'],
    ['sunny', 'mild', 'normal', 'true', 'yes'],
    ['overcast', 'mild', 'high', 'true', 'yes'],
    ['overcast', 'hot', 'normal', 'false', 'yes'],
    ['rainy', 'mild', 'high', 'true', 'no']
]
tree = build_tree(data)
print(tree)

这将输出构建的决策树。

希望这个攻略能够帮助你理解如何使用Python实现ID3决策树算法！

Tags: ,