代码
import numpy as np
data = np.array([
['老年', '短发', '平底', '深色', '男性'],
['老年', '短发', '平底', '浅色', '男性'],
['老年', '中发', '平底', '花色', '女性'],
['老年', '长发', '高跟', '浅色', '女性'],
['老年', '短发', '平底', '深色', '男性'],
['中年', '短发', '平底', '浅色', '男性'],
['中年', '短发', '平底', '浅色', '男性'],
['中年', '长发', '高跟', '花色', '女性'],
['中年', '中发', '高跟', '深色', '女性'],
['中年', '中发', '平底', '深色', '男性'],
['青年', '长发', '高跟', '浅色', '女性'],
['青年', '短发', '平底', '浅色', '女性'],
['青年', '长发', '平底', '深色', '男性'],
['青年', '短发', '平底', '花色', '男性'],
['青年', '中发', '高跟', '深色', '女性']
])
columns = ['年龄', '发长', '鞋跟', '服装', '性别']
# 计算信息熵
def entropy(labels):
unique_labels, label_counts = np.unique(labels, return_counts=True)
probabilities = label_counts / len(labels)
return -np.sum(probabilities * np.log2(probabilities))
# 多数表决函数
def majority_vote(labels):
unique_values, counts = np.unique(labels, return_counts=True)
return unique_values[np.argmax(counts)]
# 选择最佳特征
def choose_best_feature(data):
base_entropy = entropy(data[:, -1]) # 计算整个数据集的原始熵
best_info_gain = 0.0
best_column = -1
# 遍历每个特征，计算信息增益
for index in range(data.shape[1] - 1):
unique_values = np.unique(data[:, index])
new_entropy = 0.0
# 计算每个特征值导致的信息熵
for value in unique_values:
subset = data[data[:, index] == value]
prob = len(subset) / len(data)
new_entropy += prob * entropy(subset[:, -1])
info_gain = base_entropy - new_entropy
if info_gain > best_info_gain:
best_info_gain = info_gain
best_column = index
return best_column
# 切割数据集
def split_data(data, index, value):
"""根据特征和特征值切割数据集."""
subset = data[data[:, index] == value]
return np.delete(subset, index, axis=1)
# 递归构建决策树
def create_decision_tree(data, feature_names):
"""递归构建决策树，选择最佳分割特征."""
# 如果数据集中所有元素属于同一类别，则返回该类别
if len(np.unique(data[:, -1])) == 1:
return data[0, -1]
# 如果没有更多的特征可用来进一步划分数据，应用多数表决
if len(data[0]) == 1:
return majority_vote(data[:, -1])
# 选择最佳特征并继续分割
best_feature_index = choose_best_feature(data)
best_feature = feature_names[best_feature_index]
tree = {best_feature: {}}
# 对每个特征值递归构建子树
feature_values = np.unique(data[:, best_feature_index])
for value in feature_values:
sub_data = split_data(data, best_feature_index, value)
sub_features = feature_names[:best_feature_index] + feature_names[best_feature_index + 1:]
tree[best_feature][value] = create_decision_tree(sub_data, sub_features)
return tree
# 打印决策树
def print_decision_tree(tree, indent=''):
for key, val in tree.items():
if isinstance(val, dict):
print(indent + str(key) + ':')
print_decision_tree(val, indent + ' ')
else:
print(indent + ' ' + str(key) + ': ' + str(val))
# 构建并打印决策树
decision_tree = create_decision_tree(data, columns)
print_decision_tree(decision_tree)结果
改进
1.可以使用如graphviz来生成决策树的图形可视化表示
2..查阅资料得知，当数据集够大时需要采用
剪枝（Pruning）
剪枝可以帮助减少决策树的复杂性，避免过拟合。通常有两种主要的剪枝技术：
-
预剪枝（Pre-pruning）：在构建决策树的过程中提前停止树的生长。可以通过设置一个最大深度、要求节点中的最小样本数量或信息增益的最小值来实现。
-
后剪枝（Post-pruning）：先构建决策树，然后删除那些提供较小增益的分支。可以使用交叉验证来测试每次剪枝的效果，保留表现最佳的配置。
但是这个里面，没想懂剪枝在本题的作用，因为本题就15个样本，没必要限制树的深度，剪枝效果不大
3.预测功能
# 预测函数
def predict(tree, sample):
if not isinstance(tree, dict):
return tree
root_node = next(iter(tree))
feature_value = sample.get(root_node)
if feature_value in tree[root_node]:
return predict(tree[root_node][feature_value], sample)
return None4.用其他算法来分类，如C4.5算法
C4.5算法是用于生成决策树的一种经典算法，是ID3算法的一种延伸和优化。
C4.5算法对ID3算法进行了改进 ，改进点主要有：
-
用信息增益率来选择划分特征，克服了用信息增益选择的不足，但信息增益率对可取值数目较少的属性有所偏好；
-
能够处理离散型和连续型的属性类型，即将连续型的属性进行离散化处理；
-
能够处理具有缺失属性值的训练数据；
-
在构造树的过程中进行剪枝；
计算步骤
-
计算信息增益：首先，和ID3一样，计算每个属性的信息增益。
-
计算分割信息：对于每个属性，计算其分割信息，这是对属性可能取值的总体信息量的度量。
-
计算信息增益率：信息增益率是信息增益和分割信息的比值。选择信息增益率最高的属性作为分割节点。
数据集中的特征如“服装”和“发长”在不同分类下的分布相对均匀，使用ID3可能会优先选择这些特征，因为它们可能带来更高的信息增益。而C4.5在计算信息增益率时，会考虑到分割信息，可能不会选择这些特征，尤其是当这些特征的分割信息较高时。
本题中用C4.5算法可能时先年龄后服装，而不是先服装后年龄。
手动计算方法
