# Python手写决策树并应对过度拟合问题

## 基尼不纯度和熵

defgini_impurity(y):
#calculategini_impuritygivenlabels/classesofeachexamplem=y.shape[0]
cnts=dict(zip(*np.unique(y, return_counts=True)))
impurity=1-sum((cnt/m)**2forcntincnts.values())
returnimpuritydefentropy(y):
#calculateentropygivenlabels/classesofeachexamplem=y.shape[0]
cnts=dict(zip(*np.unique(y, return_counts=True)))
disorder=-sum((cnt/m)*log(cnt/m) forcntincnts.values())
returndisorder

## 构建树

defget_split(X, y):
#loopthroughfeaturesandvaluestofindbestcombinationwiththemostinformationgainbest_gain, best_index, best_value=0, None, Nonecur_gini=gini_impurity(y)
n_features=X.shape[1]
forindexinrange(n_features):
values=np.unique(X[:, index], return_counts=False)
forvalueinvalues:
left, right=test_split(index, value, X, y)
ifleft['y'].shape[0] ==0orright['y'].shape[0] ==0:
continuegain=info_gain(left['y'], right['y'], cur_gini)
ifgain>best_gain:
best_gain, best_index, best_value=gain, index, valuebest_split= {'gain': best_gain, 'index': best_index, 'value': best_value}
returnbest_splitdeftest_split(index, value, X, y):
returnleft, rightdefinfo_gain(l_y, r_y, cur_gini):
#calculatetheinformationgainforacertainsplitm, n=l_y.shape[0], r_y.shape[0]
p=m/ (m+n)
returncur_gini-p*gini_impurity(l_y) - (1-p) *gini_impurity(r_y)

classDecision_Node:
self.index, self.value=index, valueself.left, self.right=left, rightclassLeaf:
#definealeafnodedef__init__(self, y):
self.counts=dict(zip(*np.unique(y, return_counts=True)))
self.prediction=max(self.counts.keys(), key=lambdax: self.counts[x])

defdecision_tree(X, y):
#recursivelybuildthetreesplit=get_split(X, y)
ifsplit['gain'] ==0:
nonlocalcorrect_predictionleaf=Leaf(y)
correct_prediction+=leaf.counts[leaf.prediction]
returnleafleft, right=test_split(split['index'], split['value'], X, y)
left_node=build_tree(left['X'], left['y'])
right_node=build_tree(right['X'], right['y'])
returnDecision_Node(split['index'], split['value'], left_node, right_node)
root=build_tree(X, y)
returncorrect_prediction/y.shape[0], root

## 预测

defpredict(x, node):
ifisinstance(node, Leaf):
returnnode.predictionifx[node.index] <node.value:
returnpredict(x, node.left)
else:
returnpredict(x, node.right)

## 如何应对过度拟合？

defdecision_tree(X, y, max_dep=5, min_size=10):
#recursivelybuildthetreesplit=get_split(X, y)
ifsplit['gain'] ==0ordep>=max_depory.shape[0] <=min_size:
nonlocalcorrect_predictionleaf=Leaf(y)
correct_prediction+=leaf.counts[leaf.prediction]
returnleafleft, right=test_split(split['index'], split['value'], X, y)
left_node=build_tree(left['X'], left['y'], dep+1)
right_node=build_tree(right['X'], right['y'], dep+1)
returnDecision_Node(split['index'], split['value'], left_node, right_node)
root=build_tree(X, y, 0)
returncorrect_prediction/y.shape[0], root

## 树的可视化

defprint_tree(node, indent="|---"):
#printthetreeifisinstance(node, Leaf):
print(indent+'Class:', node.prediction)
returnprint(indent+'feature_'+str(node.index) +' <= '+str(round(node.value, 2)))
print_tree(node.left, '|   '+indent)
print(indent+'feature_'+str(node.index) +' > '+str(round(node.value, 2)))
print_tree(node.right, '|   '+indent)

|---feature_1<=1.87||---feature_1<=-0.74|||---feature_1<=-1.79||||---feature_1<=-2.1|||||---Class: 2||||---feature_1>-2.1|||||---Class: 2|||---feature_1>-1.79||||---feature_0<=1.62|||||---feature_0<=-1.31||||||---Class: 2|||||---feature_0>-1.31||||||---feature_1<=-1.49|||||||---Class: 1||||||---feature_1>-1.49|||||||---Class: 1||||---feature_0>1.62|||||---Class: 2||---feature_1>-0.74|||---feature_1<=0.76||||---feature_0<=0.89|||||---feature_0<=-0.86||||||---feature_0<=-2.24|||||||---Class: 2||||||---feature_0>-2.24|||||||---Class: 1|||||---feature_0>-0.86||||||---Class: 0||||---feature_0>0.89|||||---feature_0<=2.13||||||---Class: 1|||||---feature_0>2.13||||||---Class: 2|||---feature_1>0.76||||---feature_0<=-1.6|||||---Class: 2||||---feature_0>-1.6|||||---feature_0<=1.35||||||---feature_1<=1.66|||||||---Class: 1||||||---feature_1>1.66|||||||---Class: 1|||||---feature_0>1.35||||||---Class: 2|---feature_1>1.87||---Class: 2

## 总结

|
1月前
|
Python
【Leetcode刷题Python】剑指 Offer 26. 树的子结构

34 4
|
1天前
|

【9月更文挑战第12天】决策树算法作为机器学习领域的一颗明珠，凭借其直观易懂和强大的解释能力，在分类与回归任务中表现出色。相比传统统计方法，决策树通过简单的分支逻辑实现了数据的精准分类。本文将借助Python和scikit-learn库，以鸢尾花数据集为例，展示如何使用决策树进行分类，并探讨其优势与局限。通过构建一系列条件判断，决策树不仅模拟了人类决策过程，还确保了结果的可追溯性和可解释性。无论您是新手还是专家，都能轻松上手，享受机器学习的乐趣。
13 9
|
4天前
|

【9月更文挑战第9天】在数据科学领域，机器学习如同璀璨明珠，吸引无数探索者。尤其对于新手而言，纷繁复杂的算法常让人感到迷茫。本文将以决策树为切入点，带您从Python机器学习的新手逐步成长为高手。决策树以其直观易懂的特点成为入门利器。通过构建决策树分类器并应用到鸢尾花数据集上，我们展示了其基本用法及效果。掌握决策树后，还需深入理解其工作原理，调整参数，并探索集成学习方法，最终将所学应用于实际问题解决中，不断提升技能。愿这棵智慧之树助您成为独当一面的大师。
14 3
|
6天前
|

【9月更文挑战第7天】当我们身处数据海洋，如何提炼出有价值的洞察？决策树作为一种直观且强大的机器学习算法，宛如智慧之树，引领我们在繁复的数据中找到答案。通过Python的scikit-learn库，我们可以轻松实现决策树模型，对数据进行分类或回归分析。本教程将带领大家从零开始，通过实际案例掌握决策树的原理与应用，探索数据中的秘密。
15 1
|
16天前
|
Python
Python笔下那些神奇的树
Python笔下那些神奇的树
12 1
|
1月前
|

58 9
|
1月前
|

【python】python客户信息审计风险决策树算法分类预测（源码+数据集+论文）【独一无二】
【python】python客户信息审计风险决策树算法分类预测（源码+数据集+论文）【独一无二】
50 1
|
1月前
|

【2023高教社杯】C题 蔬菜类商品的自动定价与补货决策 问题分析、数学模型及python代码实现

58 1
|
1月前
|
Python
【Leetcode刷题Python】538. 把二叉搜索树转换为累加树
LeetCode上538号问题"把二叉搜索树转换为累加树"的Python实现，使用反向中序遍历并记录节点值之和来更新每个节点的新值。
17 3
|
1月前
|

【8月更文挑战第2天】决策树算法以其直观性和解释性在机器学习领域中独具魅力，尤其擅长处理非线性关系。相较于复杂模型，决策树通过简单的分支逻辑实现数据分类，易于理解和应用。本示例通过Python的scikit-learn库演示了使用决策树对鸢尾花数据集进行分类的过程，并计算了预测准确性。虽然决策树优势明显，但也存在过拟合等问题。即便如此，无论是初学者还是专家都能借助决策树的力量提升数据分析能力。
25 4