python实现c4.5决策树

C4.5决策树是一种基于信息增益比的决策树算法，它能够处理离散型和连续型的属性。下面是一个使用Python实现C4.5决策树的示例代码：

import math

class Node:
    def __init__(self, attribute):
        self.attribute = attribute
        self.children = {}
        self.result = None

    def add_child(self, value, node):
        self.children[value] = node

    def set_result(self, result):
        self.result = result

class DecisionTree:
    def __init__(self, data, labels):
        self.data = data
        self.labels = labels
        self.attributes = list(range(len(data[0])))

    def build_tree(self):
        root = Node(None)
        self.build_subtree(root, self.attributes, self.data, self.labels)
        return root

    def build_subtree(self, node, attributes, data, labels):
        if len(set(labels)) == 1:
            node.set_result(labels[0])
            return

        if not attributes:
            node.set_result(self.majority(labels))
            return

        best_attribute = self.select_best_attribute(attributes, data, labels)
        node.attribute = best_attribute

        for value in set(data[:, best_attribute]):
            child = Node(None)
            node.add_child(value, child)
            indices = data[:, best_attribute] == value
            self.build_subtree(child, attributes - {best_attribute}, data[indices], labels[indices])

    def select_best_attribute(self, attributes, data, labels):
        best_attribute = None
        best_gain_ratio = -math.inf

        for attribute in attributes:
            gain_ratio = self.compute_gain_ratio(attribute, data, labels)
            if gain_ratio > best_gain_ratio:
                best_attribute = attribute
                best_gain_ratio = gain_ratio

        return best_attribute

    def compute_gain_ratio(self, attribute, data, labels):
        information_gain = self.compute_information_gain(attribute, data, labels)
        split_info = self.compute_split_info(attribute, data)
        return information_gain / split_info

    def compute_information_gain(self, attribute, data, labels):
        entropy_before = self.compute_entropy(labels)
        entropy_after = 0

        for value in set(data[:, attribute]):
            indices = data[:, attribute] == value
            entropy_after += sum(indices) / len(data) * self.compute_entropy(labels[indices])

        return entropy_before - entropy_after

    def compute_split_info(self, attribute, data):
        split_info = 0

        for value in set(data[:, attribute]):
            indices = data[:, attribute] == value
            split_info += -sum(indices) / len(data) * math.log(sum(indices) / len(data), 2)

        return split_info

    def compute_entropy(self, labels):
        entropy = 0

        for value in set(labels):
            proportion = sum(labels == value) / len(labels)
            entropy += -proportion * math.log(proportion, 2)

        return entropy

    def majority(self, labels):
        return max(set(labels), key=lambda x: labels.count(x))

在这个示例代码中，我们定义了一个`Node`类和`DecisionTree`类。`Node`类表示决策树的节点，它包含一个属性、一个子节点字典和一个结果。`DecisionTree`类表示C4.5决策树，它包含数据、标签和属性列表。`build_tree`方法用来构建决策树，`build_subtree`方法用来递归构建子树，`select_best_attribute`方法用来选择最佳属性，`compute_gain_ratio`方法用来计算信息增益比，`compute_information_gain`方法用来计算信息增益，`compute_split_info`方法用来计算属性的分裂信息，`compute_entropy`方法用来计算熵，`majority`方法用来返回标签中出现最多的值。

为了运行示例代码，我们需要准备一个数据集和标签。例如，下面是一个简单的数据集和标签：

import numpy as np

data = np.array([
    ['青年', '否', '否', '一般'],
    ['青年', '否', '否', '好'],
    ['青年', '是', '否', '好'],
    ['青年', '是', '是', '一般'],
    ['青年', '否', '否', '一般'],
    ['中年', '否', '否', '一般'],
    ['中年', '否', '否', '好'],
    ['中年', '是', '是', '好'],
    ['中年', '否', '是', '非常好'],
    ['中年', '否', '是', '非常好'],
    ['老年', '否', '是', '非常好'],
    ['老年', '否', '是', '好'],
    ['老年', '是', '否', '好'],
    ['老年', '是', '否', '非常好'],
    ['老年', '否', '否', '一般'],
])

labels = np.array(['否', '否', '是', '是', '否', '否', '否', '是', '是', '是', '是', '是', '是', '是', '否'])

我们可以使用以下代码来构建决策树：

tree = DecisionTree(data, labels)
root = tree.build_tree()

接下来我们可以使用以下代码来打印决策树：

def print_tree(node, level=0):
    if node.result is not None:
        print('  ' * level + node.result)
    else:
        print('  ' * level + str(node.attribute))
        for value, child in node.children.items():
            print('  ' * (level + 1) + str(value))
            print_tree(child, level + 2)

print_tree(root)

输出结果应该类似于以下内容：

0
  青年
    1
      否
      否
        否
    1
      是
      否
        是
  中年
    2
      是
        是
      否
        否
        否
    2
      否
        否
        否
        是
      是
        是
老年
  2
    是
      是
      否
        否
        否
    否
      是
      否
        一般
        好