Python实现决策树C4.5算法详解(在ID3基础上改进)

决策树是一种常见的机器学习算法，它可以用于分类和回归问题。C4.5算法是一种基于信息增益比的决策树算法，它在ID3算法的基础上进行了改进，可以处理连续属性和缺失值。在本文中，我们将介绍如何使用Python实现C4.5算法，并详细讲解实现原理。

实现原理

C4.5算法的实现原理比较复杂，我们可以分为以下几个步骤：

1. 首先定义一个名为Node的类，用于表示决策树的节点。每个节点包含一个属性名、一个属性值、一个子节点列表和一个类别标签。
2. 然后定义一个名为C45DecisionTree的类，用于表示C4.5算法的决策树。C45DecisionTree类包含一个根节点、一个属性列表和一个类别列表。
3. 在C45DecisionTree类中，首先定义一个名为build_tree的方法，用于构建决策树。在build_tree方法中，我们首先判断当前节点是否为叶子节点，如果是，返回当前节点的类别标签。否则，选择一个最优的属性，将当前节点分裂成多个子节点，递归调用build_tree方法，构建子树。
4. 然后定义一个名为choose_best_feature的方法，用于选择最优的属性。在choose_best_feature方法中，我们首先计算每个属性的信息增益比，选择信息增益比最大的属性作为最优属性。
5. 最后定义一个名为split_data的方法，用于将数据集按照指定属性的值进行划分。在split_data方法中，我们首先判断属性是否为连续值，如果是，将数据集按照属性值进行排序，然后选择最优的划分点，将数据集划分成两个子集。如果属性不是连续值，将数据集按照属性值进行划分，将每个属性值对应的数据集存储在一个字典中。

Python实现

下面是一个使用Python实现C4.5算法的示例：

import math
import pandas as pd

class Node:
    def __init__(self, attr_name=None, attr_value=None, children=None, label=None):
        self.attr_name = attr_name
        self.attr_value = attr_value
        self.children = children or {}
        self.label = label

class C45DecisionTree:
    def __init__(self, data, class_name):
        self.root = None
        self.attr_list = list(data.columns)
        self.attr_list.remove(class_name)
        self.class_list = data[class_name].unique().tolist()
        self.data = data
        self.class_name = class_name

    def build_tree(self, data):
        labels = data[self.class_name].tolist()
        if len(set(labels)) == 1:
            return Node(label=labels[0])
        if len(data) == 0:
            return Node(label=self.majority_class())
        best_attr = self.choose_best_feature(data)
        node = Node(attr_name=best_attr)
        if self.is_continuous(best_attr):
            split_value = self.choose_best_split(data, best_attr)
            left_data = data[data[best_attr] <= split_value]
            right_data = data[data[best_attr] > split_value]
            node.attr_value = split_value
            node.children['<='] = self.build_tree(left_data)
            node.children['>'] = self.build_tree(right_data)
        else:
            for attr_value, sub_data in data.groupby(best_attr):
                node.children[attr_value] = self.build_tree(sub_data.drop(best_attr, axis=1))
        return node

    def choose_best_feature(self, data):
        entropy = self.entropy(data)
        max_gain_ratio = 0
        best_attr = None
        for attr in self.attr_list:
            if self.is_continuous(attr):
                gain_ratio, split_value = self.continuous_gain_ratio(data, attr, entropy)
                if gain_ratio > max_gain_ratio:
                    max_gain_ratio = gain_ratio
                    best_attr = attr
                    best_split_value = split_value
            else:
                gain_ratio = self.discrete_gain_ratio(data, attr, entropy)
                if gain_ratio > max_gain_ratio:
                    max_gain_ratio = gain_ratio
                    best_attr = attr
        if self.is_continuous(best_attr):
            return best_attr, best_split_value
        else:
            return best_attr

    def split_data(self, data, attr):
        if self.is_continuous(attr):
            split_value = self.choose_best_split(data, attr)
            left_data = data[data[attr] <= split_value]
            right_data = data[data[attr] > split_value]
            return {'<=': left_data, '>': right_data}
        else:
            return dict(tuple(data.groupby(attr)))

    def entropy(self, data):
        labels = data[self.class_name].tolist()
        label_count = {}
        for label in labels:
            if label not in label_count:
                label_count[label] = 0
            label_count[label] += 1
        entropy = 0
        for label in label_count:
            prob = label_count[label] / len(labels)
            entropy -= prob * math.log(prob, 2)
        return entropy

    def majority_class(self):
        labels = self.data[self.class_name].tolist()
        label_count = {}
        for label in labels:
            if label not in label_count:
                label_count[label] = 0
            label_count[label] += 1
        majority_label = None
        max_count = 0
        for label in label_count:
            if label_count[label] > max_count:
                max_count = label_count[label]
                majority_label = label
        return majority_label

    def is_continuous(self, attr):
        return self.data[attr].dtype == 'float64'

    def choose_best_split(self, data, attr):
        values = data[attr].tolist()
        values.sort()
        split_points = [(values[i] + values[i+1]) / 2 for i in range(len(values)-1)]
        max_gain_ratio = 0
        best_split_value = None
        for split_value in split_points:
            left_data = data[data[attr] <= split_value]
            right_data = data[data[attr] > split_value]
            gain_ratio = self.continuous_gain_ratio(data, attr, self.entropy(data), split_value)
            if gain_ratio > max_gain_ratio:
                max_gain_ratio = gain_ratio
                best_split_value = split_value
        return best_split_value

    def continuous_gain_ratio(self, data, attr, entropy, split_value=None):
        if split_value is None:
            split_value = self.choose_best_split(data, attr)
        left_data = data[data[attr] <= split_value]
        right_data = data[data[attr] > split_value]
        left_entropy = self.entropy(left_data)
        right_entropy = self.entropy(right_data)
        split_entropy = (len(left_data) / len(data)) * left_entropy + (len(right_data) / len(data)) * right_entropy
        gain = entropy - split_entropy
        split_info = - (len(left_data) / len(data)) * math.log(len(left_data) / len(data), 2) - (len(right_data) / len(data)) * math.log(len(right_data) / len(data), 2)
        if split_info == 0:
            return 0, split_value
        gain_ratio = gain / split_info
        return gain_ratio, split_value

    def discrete_gain_ratio(self, data, attr, entropy):
        sub_data_dict = self.split_data(data, attr)
        split_entropy = 0
        split_info = 0
        for attr_value in sub_data_dict:
            sub_data = sub_data_dict[attr_value]
            prob = len(sub_data) / len(data)
            split_entropy -= prob * self.entropy(sub_data)
            split_info -= prob * math.log(prob, 2)
        gain = entropy - split_entropy
        if split_info == 0:
            return 0
        gain_ratio = gain / split_info
        return gain_ratio

    def predict(self, data):
        node = self.root
        while node.children:
            attr_name = node.attr_name
            if self.is_continuous(attr_name):
                if data[attr_name] <= node.attr_value:
                    node = node.children['<=']
                else:
                    node = node.children['>']
            else:
                attr_value = data[attr_name]
                if attr_value in node.children:
                    node = node.children[attr_value]
                else:
                    return self.majority_class()
        return node.label

    def fit(self):
        self.root = self.build_tree(self.data)

data = pd.read_csv('data.csv')
tree = C45DecisionTree(data, 'class')
tree.fit()
print(tree.predict({'age': 30, 'income': 50000, 'student': 'no', 'credit_rating': 'fair'}))

在这个示例中，我们首先导入了pandas和math模块。然后定义了一个名为Node的类，用于表示决策树的节点。每个节点包含一个属性名、一个属性值、一个子节点列表和一个类别标签。然后定义了一个名为C45DecisionTree的类，用于表示C4.5算法的决策树。C45DecisionTree类包含一个根节点、一个属性列表和一个类别列表。在C45DecisionTree类中，我们定义了build_tree、choose_best_feature、split_data、entropy、majority_class、is_continuous、choose_best_split、continuous_gain_ratio、discrete_gain_ratio和predict等方法，用于构建决策树、选择最优的属性、划分数据集、计算熵、计算多数类、判断属性是否为连续值、选择最优的划分点、计算连续属性的信息增益比、计算离散属性的信息增益比和预测数据的类别标签。最后，我们读取了一个名为data.csv的数据集，使用C45DecisionTree类构建决策树，并预测了一个新的数据的类别标签。

示例1：使用C4.5算法预测鸢尾花的类别

在这个示例中，我们将使用C4.5算法预测鸢尾花的类别。我们首先读取一个名为iris.csv的数据集，然后使用C45DecisionTree类构建决策树，并预测测试数据的类别标签。

import pandas as pd

data = pd.read_csv('iris.csv')
train_data = data.iloc[:120]
test_data = data.iloc[120:]
tree = C45DecisionTree(train_data, 'class')
tree.fit()
correct_count = 0
for i in range(len(test_data)):
    row = test_data.iloc[i]
    label = tree.predict(row.drop('class'))
    if label == row['class']:
        correct_count += 1
accuracy = correct_count / len(test_data)
print('Accuracy:', accuracy)

在这个示例中，我们首先读取了一个名为iris.csv的数据集，然后将前120个样本作为训练集，后30个样本作为测试集。然后使用C45DecisionTree类构建决策树，并预测测试数据的类别标签。最后计算预测准确率。

示例2：使用C4.5算法预测泰坦尼克号乘客的生还情况

在这个示例中，我们将使用C4.5算法预测泰坦尼克号乘客的生还情况。我们首先读取一个名为titanic.csv的数据集，然后使用pandas模块对数据进行预处理，将缺失值填充为平均值或众数。然后使用C45DecisionTree类构建决策树，并预测测试数据的类别标签。

import pandas as pd

data = pd.read_csv('titanic.csv')
data = data.drop(['PassengerId', 'Name', 'Ticket', 'Cabin'], axis=1)
data['Age'] = data['Age'].fillna(data['Age'].mean())
data['Embarked'] = data['Embarked'].fillna(data['Embarked'].mode()[0])
train_data = data.iloc[:800]
test_data = data.iloc[800:]
tree = C45DecisionTree(train_data, 'Survived')
tree.fit()
correct_count = 0
for i in range(len(test_data)):
    row = test_data.iloc[i]
    label = tree.predict(row.drop('Survived'))
    if label == row['Survived']:
        correct_count += 1
accuracy = correct_count / len(test_data)
print('Accuracy:', accuracy)

在这个示例中，我们首先读取了一个名为titanic.csv的数据集，然后使用pandas模块对数据进行预处理，将缺失值填充为平均值或众数。然后将前800个样本作为训练集，后91个样本作为测试集。然后使用C45DecisionTree类构建决策树，并预测测试数据的类别标签。最后计算预测准确率。

本文链接：http://task.lmcjl.com/news/15133.html