博客

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

  • Post category:Python

决策树C4.5算法简介

C4.5算法是在ID3算法的基础上进行改进的一种决策树算法。C4.5算法在ID3算法的基础上，对连续属性进行了处理，并且使用信息增益比来选择最优划分属性，避免了ID3算法中对取值数目较多的属性的偏好。C4.5算法的核心思想是通过信息增益比来选择最优划分属性，同时使用剪枝技术来避免过拟合。

C4.5算法流程

C4.5算法的流程如下：

  1. 从根节点开始，选择最优划分属性，将数据集划分为多个子集。
  2. 对每个子集递归执行步骤1，直到所有子集都为同一类别或者无法再划分。
  3. 使用剪枝技术对决策树进行剪枝，避免过拟合。

C4.5算法实现

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

import math
import pandas as pd

class Node:
    def __init__(self, feature=None, value=None, label=None, left=None, right=None):
        self.feature = feature
        self.value = value
        self.label = label
        self.left = left
        self.right = right

class C45:
    def __init__(self, epsilon=0.1):
        self.epsilon = epsilon

    def fit(self, X, y):
        self.root = self.build_tree(X, y)

    def predict(self, X):
        return [self._predict(x, self.root) for x in X]

    def _predict(self, x, node):
        if node.label is not None:
            return node.label
        if x[node.feature] <= node.value:
            return self._predict(x, node.left)
        else:
            return self._predict(x, node.right)

    def build_tree(self, X, y):
        if len(set(y)) == 1:
            return Node(label=y[0])
        if len(X.columns) == 0:
            return Node(label=self.majority(y))
        feature, value = self.choose_feature(X, y)
        left = self.build_tree(X[X[feature] <= value], y[X[feature] <= value])
        right = self.build_tree(X[X[feature] > value], y[X[feature] > value])
        return Node(feature=feature, value=value, left=left, right=right)

    def choose_feature(self, X, y):
        max_gain_ratio = -1
        best_feature = None
        best_value = None
        H_D = self.entropy(y)
        for feature in X.columns:
            values = set(X[feature])
            for value in values:
                Dv = y[X[feature] == value]
                H_Dv = self.entropy(Dv)
                gain_ratio = (H_D - H_Dv) / self.split_info(X, feature, value)
                if gain_ratio > max_gain_ratio:
                    max_gain_ratio = gain_ratio
                    best_feature = feature
                    best_value = value
        if max_gain_ratio < self.epsilon:
            return None, self.majority(y)
        return best_feature, best_value

    def entropy(self, y):
        n = len(y)
        if n == 0:
            return 0
        p = [len(y[y == c]) / n for c in set(y)]
        return -sum([pi * math.log2(pi) for pi in p])

    def split_info(self, X, feature, value):
        n = len(X)
        Dv = len(X[X[feature] == value])
        Dv_bar = n - Dv
        return -Dv / n * math.log2(Dv / n) - Dv_bar / n * math.log2(Dv_bar / n)

    def majority(self, y):
        return pd.Series(y).mode()[0]

在这个示例中，我们首先定义了一个名为Node的类，用于表示决策树的节点。每个节点包含一个划分属性feature、一个划分值value、一个类别标签label、以及左右子节点left和right。

我们还定义了一个名为C45的类，用于实现C4.5算法。在构造函数中，我们定义了一个参数epsilon，用于控制决策树的生长程度。在fit方法中，我们使用build_tree方法构建决策树。在predict方法中，我们使用_predict方法对新数据进行预测。在_build_tree方法中，我们首先判断数据集是否为同一类别，如果是，返回一个叶子节点。然后判断属性集是否为空，如果是，返回一个叶子节点，类别为数据集中出现次数最多的类别。然后选择最优划分属性和划分值，递归构建左右子树。在_choose_feature方法中，我们计算每个属性的信息增益比，选择信息增益比最大的属性作为划分属性。如果信息增益比小于epsilon，返回None和数据集中出现次数最多的类别。在_entropy方法中，我们计算数据集的熵。在_split_info方法中，我们计算属性的分裂信息。在_majority方法中，我们返回数据集中出现次数最多的类别。

示例1：使用C4.5算法进行鸢尾花分类

在这个示例中，我们将使用C4.5算法对鸢尾花数据集进行分类。我们首先加载数据集，然后将数据集分为训练集和测试集。我们使用C45类对训练集进行训练，然后对测试集进行预测，计算预测准确率。

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
import pandas as pd

iris = load_iris()
X = pd.DataFrame(iris.data, columns=iris.feature_names)
y = iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

model = C45()
model.fit(X_train, y_train)
y_pred = model.predict(X_test)
print(accuracy_score(y_test, y_pred))

在这个示例中，我们首先使用sklearn.datasets中的load_iris函数加载鸢尾花数据集。然后使用pandas将数据集转换为DataFrame格式。我们使用train_test_split函数将数据集分为训练集和测试集。然后使用C45类对训练集进行训练，使用predict方法对测试集进行预测，计算预测准确率。

示例2：使用C4.5算法进行泰坦尼克号生还预测

在这个示例中，我们将使用C4.5算法对泰坦尼克号数据集进行生还预测。我们首先加载数据集，然后进行数据预处理，包括填充缺失值、转换类别变量为数值变量等。然后将数据集分为训练集和测试集。我们使用C45类对训练集进行训练，然后对测试集进行预测，计算预测准确率。

import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

data = pd.read_csv('titanic.csv')
data = data.drop(['PassengerId', 'Name', 'Ticket', 'Cabin'], axis=1)
data = data.dropna()
data['Sex'] = data['Sex'].map({'male': 0, 'female': 1})
data['Embarked'] = data['Embarked'].map({'S': 0, 'C': 1, 'Q': 2})
X = data.drop(['Survived'], axis=1)
y = data['Survived']
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

model = C45()
model.fit(X_train, y_train)
y_pred = model.predict(X_test)
print(accuracy_score(y_test, y_pred))

在这个示例中，我们首先使用pandas的read_csv函数加载泰坦尼克号数据集。然后使用drop函数删除无用的列。我们使用dropna函数删除缺失值。然后使用map函数将类别变量转换为数值变量。然后将数据集分为训练集和测试集。我们使用C45类对训练集进行训练，使用predict方法对测试集进行预测，计算预测准确率。

Tags: ,