决策树分类算法

#CSDN AI写作助手创作测评

ID3算法

1.算法原理

2.代码实现

3.ID3算法的优缺点分析

C4.5算法

1.原理

2.优缺点

心得感受

决策树表示方法是应用最广泛的逻辑方法之一，它从一组无次序、无规则的事例中推理出决策树表示形式的分类规则。在决策树的内部节点进行属性值的比较，根据不同的属性值判断从该节点向下的分支，在决策树的叶节点得到结论

决策树分类算法的主要优点包括易于理解和解释、对缺失值不敏感、能处理不相关特征等。它的主要缺点是容易过拟合、对噪声敏感、不稳定等问题。

在实践中，决策树分类算法可以使用不同的算法实现，如ID3、C4.5和CART等。这些算法的主要区别在于如何选择属性、如何处理连续值属性和如何处理缺失值等方面。

ID3算法

1.算法原理

ID3算法是一种决策树学习算法，通过对数据集进行递归分割来构建决策树。它基于信息增益选择最佳属性进行分裂。下面是ID3算法的基本原理：

1. 选择最佳分裂属性：对于数据集中的每个属性，计算它们对数据集的信息增益（或信息增益比），选择信息增益最大（或信息增益比最大）的属性作为该节点的分裂属性。
2. 将节点分裂成子节点：用分裂属性将数据集分成几个子集，每个子集对应一个子节点。
3. 递归处理子节点：对每个子节点递归进行操作，直到所有叶子节点都是同一类别或无法继续分裂。
4. 剪枝：使用预留的测试数据集来剪枝以防止过拟合。
5. 生成决策树：所有子节点的递归处理完成后，生成一棵决策树。

ID3算法的缺点是对于具有连续属性和缺失值的数据集处理能力较差。因此，它常与C4.5和CART算法结合使用，用于改进这些限制。

2.代码实现

import mathdef entropy(data):"""计算数据集的熵"""count = {}for item in data:if item[-1] not in count:count[item[-1]] = 0count[item[-1]] += 1entropy = 0for key in count:prob = count[key] / len(data)entropy -= prob * math.log2(prob)return entropydef split_data(data, feature, value):"""根据特征和特征值划分数据集"""sub_data = []for item in data:if item[feature] == value:sub_item = item[:feature]sub_item.extend(item[feature+1:])sub_data.append(sub_item)return sub_datadef info_gain(data, feature):"""计算特征的信息增益"""count = {}for item in data:if item[feature] not in count:count[item[feature]] = 0count[item[feature]] += 1sub_entropy = 0for key in count:prob = count[key] / sum(count.values())sub_data = split_data(data, feature, key)sub_entropy += prob * entropy(sub_data)return entropy(data) - sub_entropydef choose_feature(data):"""选择最优特征"""max_gain = 0best_feature = -1for i in range(len(data[0])-1):gain = info_gain(data, i)if gain > max_gain:max_gain = gainbest_feature = ireturn best_featuredef majority_vote(class_list):"""多数表决"""count = {}for item in class_list:if item not in count:count[item] = 0count[item] += 1return max(count, key=count.get)def create_tree(data, labels):"""创建决策树"""class_list = [item[-1] for item in data]if class_list.count(class_list[0]) == len(class_list):return class_list[0]if len(data[0]) == 1:return majority_vote(class_list)best_feature = choose_feature(data)best_label = labels[best_feature]tree = {best_label: {}}del(labels[best_feature])count = {}for item in data:if item[best_feature] not in count:count[item[best_feature]] = 0count[item[best_feature]] += 1for key in count:sub_labels = labels[:]sub_data = split_data(data, best_feature, key)tree[best_label][key] = create_tree(sub_data, sub_labels)return tree# 测试数据
data = [[1, 1, 'yes'],[1, 1, 'yes'],[1, 0, 'no'],[0, 1, 'no'],[0, 1, 'no'],
]
labels = ['no surfacing', 'flippers']# 构建决策树
tree = create_tree(data, labels)# 输出熵和信息增益
print('Entropy:', entropy(data))
for i in range(len(labels)):print('Info gain of', labels[i], ':', info_gain(data, i))