本文是德国留学生基于个人学习笔记，记录了从零开始构建决策树的详细过程。文章首先梳理了决策树的基本结构和构建逻辑，包括确定根节点、决策节点和叶节点的方法，以及如何通过计算熵、纯度和信息增益来选择最佳特征进行分裂。随后，作者逐步编写了7个辅助函数，实现了判断纯度、获取分裂点、划分数据、计算熵、确定最佳分裂点等关键步骤，最终完成了决策树的构建。文章还计划在后续部分进行预测、与sklearn模型对比，并分析误差。

🌳 决策树由根节点、决策节点和叶节点组成，构建过程涉及特征选择和数据分裂。

🔍 确定根节点需要计算每个特征的分裂点，并选择最佳特征作为根节点，这通常通过最大化信息增益或最小化熵来实现。

⚙️ 作者编写了7个辅助函数，涵盖了判断纯度、获取分裂点、数据划分、计算熵和确定最佳分裂点等关键步骤。

💡 核心思想是递归地选择最佳分裂点，直到叶节点完全纯净，从而构建完整的决策树模型。

不是科普！不是教学！仅仅是个人学习笔记。

因为楼主是德国留学生，所以英文不好，德语也不好，专业名词夹杂中文英文德文，大概只有我自己能看懂吧lol

在开始写代码前，先理一下逻辑和顺序

决策树中3个最基本的结构组成：

root nodedecision nodes --- features splitsleaf nodes --- when completely pure

那么如何确定root node？

对于每一个 feature ，都做 split，然后选择最佳的 feature 作为 root node确定好 root node 后，然后再对剩下的每一个 feature 做 split，选择最佳的 feature 作为 decision nodes以此往复（recursive），直到最后得到 leaf nodes

那么怎么判断哪个 feature 是最佳的root node？

计算entropy/purity/information gain —— maximize purity / minimize impurity/ maximize information gain

那么如何计算entropy/purity/information gain？

首先要确定每个 feature 在 split时的点 —— 遍历每个 feature 唯一值，取相邻2个值的中点，得到这个 feature 所有可能的分割点go left & go right计算left 和 right 两边各自的 entropy计算这个分割点整体的 entropy计算 information gain对所有的 features 和 阈值依次分裂，计算所有的 entropy & information gain —— 选出最佳分裂点递归往复，直到最后的 leaf nodes

那么在不断递归后，如何确定是不是leaf nodes？

可以设置树的深度 或者 节点的个数 或者 leaf nodes 中分到的最少个数（可能不全，也可能不对）我这里 check 节点是否是 completely pure， 如果是，则判断为 leaf nodes

ok，现在所有的顺序步骤可以大概总结为：

选出最佳分裂点作为 root node对每个 features 的所有可能的分裂阈值都计算一遍entropy/information gain选择最小的entropy 或者 最大的 information gain（这里information gain = 上一层的entropy - 当前层的entroy）一般推荐选择最大的 information gain，因为要考虑样本量权重，当然咱们记住直接用information gain作为标准就行了如果节点不是 completely pure 的，那么树需要再分裂，递归第一步选择第二层的最佳分裂节点一直递归直到节点是 completely pure，则判断为 leaf nodes得到 leaf nodes 后，取y中最多数的类别作为预测结果

ok，现在可以开始写代码了

按照上面总结的7步，我打算先写7个 helper function

在写 helper function 之前，我先导入一下包和数据，观察一下数据类型。

import numpy as npimport pandas as pdimport matplotlib.pyplot as plt

简单看一下数据信息

path = "hmeq_modeling.csv"df = pd.read_csv(path,header = 0,index_col = 'index')df.head()

df.info()

除了 “BAD”和“DEROGzero”外，其他所有的 features 都是数值型的，结合数据判断“BAD”是该数据集的 target

那么下面就把数据分成特征集X，目标集y

X = df.drop(['BAD'],axis = 1)y = df[['BAD']]print(type(X),type(y),X.shape,y.shape)

<class 'pandas.core.frame.DataFrame'> <class 'pandas.core.frame.DataFrame'> (5960, 18) (5960, 1)

ok，下面开始写 helper function（7个）

第一步，判断是否是 completely pure？

如果是，直接判断为 leaf nodes

如果不是，进行递归，运行接下去的代码

def check_purity(y):    """    检查当前的 leaf node 是不是完全pure的，对于我们的classification 任务来说，就是检查 leaf node 是不是只包含一个class    """    unique_classes = np.unique(y)    if len(unique_classes) == 1:        return True    else:        return False

第二步，获得所有列（特征）中所有可能的候选分裂点，为计算 overall entropy 做准备

def get_potential_spilts(X):    """    找出每个 feature 所有可能的分割点，数值型的 feature，分割点定义为任意2个相邻唯一特征值的中间值    """    # 初始化空字典，从来存放每一列（每一个特征）的所有候选分裂点，key是列索引，值是该列所有中点构成的候选分裂点的列表    potential_splits = {}    # 获得列的数量，进行遍历    _,n_columns = X.shape        for col_index in range(n_columns):        potential_splits[col_index] = []   # 设置当前列的value是一个空列表        all_values = X[:,col_index]        # 取出当前列所有的值进行下一步分析   长度为 m 的一维数组        unique_values = np.unique(all_values) # 取出当前列所有的唯一值          唯一值升序排列的一维数组        for index in range(len(unique_values)): # 遍历所有唯一值的索引            if index != 0:                      # 跳过第一个，因为我们要取2个值的中点作为分割点                current_value = unique_values[index]  #当前点的值                previous_value = unique_values[index - 1]  # 当前点的前一个点的值                potential_split = (current_value + previous_value) / 2  # 候选分割点                potential_splits[col_index].append(potential_split)     # 将候选分割点保存到字典中当前列的值列表中    return potential_splits      # 最后获得的是一个key包含所有特征列，values包含所有候选分割点的字典

第三步，对数据进行划分 go left & go right，为计算 overall entropy 做准备

def split_data(X,y,split_column,split_value):    """    根据特定的数值对数据进行划分，将会同时对特征   和目标变量   进行划分    """    # 提取需要切分的那一列的数据    split_column_values = X[:,split_column]    X_below = X[split_column_values <= split_value]    X_above = X[split_column_values > split_value]    y_below = y[split_column_values <= split_value]    y_above = y[split_column_values > split_value]    return X_below,X_above,y_below,y_above

第四步，计算各自的entropy

def calculate_entropy(y):    """    对于候选节点的左边和右边的子树分别计算 entropy    """    _,counts = np.unique(y,return_counts = True)   # 找到y中所有唯一的标签，这里是0和1，每个数的值我们不需要，我们需要的是每个标签出现的次数    probabilities = counts/counts.sum()    entropy = sum(probabilities * -np.log2(probabilities))     return entropy

第五步，计算节点整体的entropy

def calculate_overall_entropy(y_below,y_above):    n = len(y_below) + len(y_above)    p_data_below = len(y_below)/n    p_data_above = len(y_above)/n    overall_entropy = (        p_data_below * calculate_entropy(y_below) +         p_data_above * calculate_entropy(y_above)    )    return overall_entropy

第六步，确定最佳分裂点

def determine_best_split(X,y,potential_splits):        # 先设定一个很大的 overall entropy 用来与接下去计算出来的overall entropy 比较 如果后面计算出来的更小 则更新信息    overall_entropy = 999    # 对于字典 potential_splits 中 遍历每一列中的每一个数值   —— 每一个特征的每一个候选分割点    for column_index in potential_splits:        for value in potential_splits[column_index]:                        # 在计算下面一行的 current overall entropy 时需用到y_below,y_above 但是数据中没有定义 需要调用前面的一个叫做 split_data 的 helper function             X_below,X_above,y_below,y_above = split_data(X,y,split_column = column_index,split_value = value)            # 计算当前列的当前候选点分割后的 （current）overall entropy            current_overall_entropy = calculate_overall_entropy(y_below,y_above)                        # 如果当前的 overll entropy 更小  则更新数据 并且判断当前的列和分割点的组合暂时为最佳            if current_overall_entropy <= overall_entropy:                overall_entropy = current_overall_entropy                best_split_column = column_index                best_split_value = value    return best_split_column,best_split_value

第七步，确定好 root node，decision nodes 还有 leaf nodes 后，判断数据应该分为哪一类

def classify_data(y):    unique_classes,counts_unique_classes = np.unique(y,return_counts = True)    index = counts_unique_classes.argmax()    classification = unique_classes[index]    prob = len(y[y==1]) / len(y)    return [classification,prob]

以前做作业时，都是直接用sklearn，3行代码就搞定了，但是最近回国休假，听说找工作面试要求手撕代码，要从零构建，所以还是打算自己搞一搞，就这7个破 helper function 花了我半天的时间。

Part 2 的内容：1 、 完整的从零构建决策树的代码过程

2、 写一个简单的预测

3、 用 sklearn 写一个决策树model

4、 比较 from scratch vs. sklearn 2种构建模型预测的error

PS： 再次强调这篇纯纯是我自己学习的记录，如果有错误的，欢迎大佬指出