• C4.5决策树算法：使用增益率选择最优划分特征。通过信息增益/分裂信息的比值克服ID3对多值特征的偏好。递归构建多叉树结构，终止条件与ID3相同。

编程代码：

import math
import json
import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split
import random

file_path = '西瓜数据集.xlsx'
label_list = []
data = pd.read_excel(file_path, skiprows=1,nrows=17)
data_dict = data.to_dict(orient='list')
data_list = list(zip(data['色泽'], data['根蒂'], data['敲声'], data['纹理'], data['脐部'], data['触感'], data['好瓜']))
train_set, test_set = train_test_split(data_list, test_size=2, random_state=random.randint(1, 1000))

print("data_list:",len(data_list),data_list)
print("train_list:",len(train_set),train_set)
print("test_list:",len(test_set),test_set)

keys = []
for index in data.keys():
    keys.append(index)
keys.remove('编号')
keys.remove('好瓜')
print('keys:',keys)

def calculate_entropy(data, label_index):
    labels = [entry[label_index] for entry in data]
    unique_labels = set(labels)
    entropy = 0
    for label in unique_labels:
        prob = labels.count(label) / len(labels)
        entropy -= prob * math.log(prob, 2)
    return entropy

def choose_best_feature(data, features, label_index):
    base_entropy = calculate_entropy(data, label_index)
    best_info_gain_ratio = 0.0
    best_feature = None

    for feature in features:
        new_entropy = 0.0
        values = set(data[i][features.index(feature)] for i in range(len(data)))

        for value in values:
            subset_data = [data[i] for i in range(len(data)) if data[i][features.index(feature)] == value]
            prob = len(subset_data) / float(len(data))
            new_entropy += prob * calculate_entropy(subset_data, label_index)

        info_gain = base_entropy - new_entropy
        split_info = calculate_entropy(data, features.index(feature))

        if split_info == 0:
            continue

        info_gain_ratio = info_gain / split_info

        print(f"Feature: {feature}, Info Gain Ratio: {info_gain_ratio}")

        if info_gain_ratio > best_info_gain_ratio:
            best_info_gain_ratio = info_gain_ratio
            best_feature = feature

    return best_feature

def id3_decision_tree(data, features, label_index):
    if len(set(data[i][label_index] for i in range(len(data)))) == 1:
        return data[0][label_index]

    if len(features) == 0:
        max_class = max(set(entry[label_index] for entry in data), key=lambda x: data.count(x))
        return max_class

    root_feature = choose_best_feature(data, features, label_index)
    if root_feature is None:
        max_class = max(set(entry[label_index] for entry in data), key=lambda x: data.count(x))
        return max_class
    print(root_feature)
    tree = {root_feature: {}}
    for value in set(data[i][features.index(root_feature)] for i in range(len(data))):
        subset_data = [data[i] for i in range(len(data)) if data[i][features.index(root_feature)] == value]
        subset_features = [feat for feat in features if feat != root_feature]
        tree[root_feature][value] = id3_decision_tree(subset_data, subset_features, label_index)
    return tree

# 测试
#'色泽','根蒂','敲声','纹理','脐部','触感'
selected_features = [0,1,2,3,4,5]
label_index = 6
decision_tree = id3_decision_tree(train_set, selected_features, label_index)
print(json.dumps(decision_tree, indent=2, ensure_ascii=False))

def predict(tree, sample):
    if isinstance(tree, dict):
        feature, subtree = next(iter(tree.items()))
        value = sample[feature]
        if value in subtree:
            return predict(subtree[value], sample)
    else:
        return tree

def evaluate(tree, test_set, label_index):
    correct_predictions = 0
    total_samples = len(test_set)
    for sample in test_set:
        prediction = predict(tree, sample)
        if prediction == sample[label_index]:
            correct_predictions += 1
    accuracy = correct_predictions / total_samples
    return accuracy

test_accuracy = evaluate(decision_tree, test_set, label_index)
print("Test Accuracy: {:.2%}".format(test_accuracy))

运行结果：

data_list: 17 [('青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'), ('乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '是'), ('乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'), ('青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '是'), ('浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'), ('青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '是'), ('乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘', '是'), ('乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑', '是'), ('乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑', '否'), ('青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '否'), ('浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '否'), ('浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', '否'), ('青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑', '否'), ('浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑', '否'), ('乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '否'), ('浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '否'), ('青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '否')]
train_list: 15 [('乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'), ('青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '否'), ('浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑', '否'), ('浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '否'), ('乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑', '否'), ('乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘', '是'), ('乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '否'), ('乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑', '是'), ('青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑', '否'), ('青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '是'), ('青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'), ('浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', '否'), ('青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '是'), ('浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '否'), ('乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '是')]
test_list: 2 [('青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '否'), ('浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是')]
keys: ['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']
Feature: 0, Info Gain Ratio: 0.19533970143657706
Feature: 1, Info Gain Ratio: 0.11871517180855008
Feature: 2, Info Gain Ratio: 0.10123475675906583
Feature: 3, Info Gain Ratio: 0.2387598145004855
Feature: 4, Info Gain Ratio: 0.19533970143657708
Feature: 5, Info Gain Ratio: 0.007050851069231331
3
Feature: 0, Info Gain Ratio: 0.0
Feature: 1, Info Gain Ratio: 0.3321743107708565
Feature: 2, Info Gain Ratio: 0.27723627023195957
Feature: 5, Info Gain Ratio: 0.3321743107708565
1
Feature: 0, Info Gain Ratio: 0.274017542121281
0
Feature: 0, Info Gain Ratio: 0.20751874963942188
Feature: 2, Info Gain Ratio: 0.31127812445913283
Feature: 5, Info Gain Ratio: 0.31127812445913283
2
Feature: 0, Info Gain Ratio: 1.0
0
{
  "3": {
    "模糊": "否",
    "清晰": {
      "1": {
        "稍蜷": {
          "0": {
            "青绿": "是",
            "乌黑": "否"
          }
        },
        "硬挺": "否",
        "蜷缩": "是"
      }
    },
    "稍糊": {
      "2": {
        "浊响": {
          "0": {
            "青绿": "否",
            "乌黑": "是"
          }
        },
        "沉闷": "否"
      }
    }
  }
}
Test Accuracy: 100.00%