【机器学习】决策树算法

摆烂小白敲代码

发布于 2024-09-25 09:44:14

540

发布于 2024-09-25 09:44:14

文章被收录于专栏：学习

人工智能领域在当今可谓炙手可热，在人工智能与机器学习领域，决策树是一种简单直观却又功能强大的分类与回归方法。它的思想是通过构建一棵树状模型来进行决策或数据分类，其结构主要是以二叉树的形式为主。决策树是一种常用的机器学习算法，用于分类和回归任务。它通过学习简单的决策规则推断出目标值。

算法引入

小明大学毕业了，去了一家银行当行长，上班第一天就有了10人申请了贷款，刚刚入行的小明仔细地整理了客户信息。包括是否有工作，是否有房子，是否信誉良好，经过了深思熟虑，小明对这10份申请给出了批复。小明想能不能让AI根据自己所做出的规律进行自动批复，这样小明就大大减少了工作量，又可以上班摸鱼了。申请人的信息如下：

申请人	是否工作	有无房子	信誉	结果
1	否	否	一般	拒绝
2	否	否	良好	拒绝
3	是	是	一般	同意
4	是	是	很好	同意
5	否	是	很好	同意
6	否	是	一般	拒绝
7	是	否	一般	同意
8	否	是	很好	同意
9	否	否	很好	拒绝
10	是	否	良好	同意

根据上面信息我们能不能推出某一个规律，使规律都满足上面的结果，如果我们按照是否有工作分类，有工作的批准，没工作的不批准，显然不行，在第5个申请人没有工作也批准了。那么我们按照有无房子分类？在第7、10个申请人没有房子也通过了申请，那按照信誉？第9个申请人信誉很好也被拒绝了。那么我们如何进行批准，这就是要我们的决策树出马了。

基尼系数：

那么在建树的时候，谁当那个头结点呢，这就要引出了我们的基尼系数的概念。

根据上面的公式我们可以计算出Gini=1-(5/10)^2-(5/10)^2=0.5。 Gini(工作，是)=1-（4/4）^2-0=0，Gini(工作，否)=1-（2/6）^2-（4/6）^2=0.44。根据加权方式求和：Gini(工作)=4/10*（Gini(工作，是)）+6/10*（Gini(工作，否)）=0.27。 Gini(房子，是)=1-（4/5）^2-（1/5）^2=0.32，Gini(房子，否)=1-（2/5）^2-（3/5）^2=0.48。根据加权方式求和：Gini(房子)=5/10*（Gini(房子，是)）+5/10*（Gini(房子，否)）=0.4。 Gini(信誉，一般)=1-（2/4）^2-（2/4）^2=0.5，Gini(信誉，良好)=1-（1/2）^2-（1/2）^2=0.5，Gini(信誉，很好)=1-（3/4）^2-（1/4）^2=0.375。根据加权方式求和：Gini(信誉)=4/10*（Gini(信誉，一般)）+2/10*（Gini(信誉，良好)）+4/10*（Gini(信誉，很好)）=0.45。我们比较这三个数Gini(工作)=0.27、Gini(房子)=0.4、Gini(信誉)=0.45。我们发现这个三个数字中Gini(工作)=0.27最小，所以我们按照它来建立决策树。

此时头结点建立完成，然后我们在没有工作的里面，有2个客户是被批准的，4个客户被拒绝了，那么我们在此基础上继续进行分类，继续求解Gini(房子)，Gini(信誉)。Gini(房子，是)=1-（2/2）^2- 0=0，Gini(房子，否)=1- 0 -（4/4）^2=0。根据加权方式求和：Gini(房子)=2/6*（Gini(房子，是)）+4/6*（Gini(房子，否)）=0。此时Gini(信誉)就不用算了，Gini(房子)已经达到最小0了，下一个结点就放是否有房子，那么此时最终的决策树就出来了。

先根据是否有工作进行判断，如果有，那么直接进行批准，没有的话，再进行判断是否有房子，有房子的话直接批准，没有房子的话直接拒绝，当然，我们这个例子没有涉及到信誉一项，如果在没有房子的人里面还有被批准的，那么需要再加一个内部节点信誉，再根据信誉的三个分类：一般、良好、很好，进行批复。这些判断是建立在前一项的基础之上的，只有进行了前一项的判断才能进行下一项的判断，进而给出批复。

决策树算法概述

决策树通过树状图的形式模拟决策过程，在每一个结点都会有分支（除了叶子结点），每个内部节点都代表一个属性上的判断，如果为是则走一个分支，如果为否则走另外一个分支。每个分支代表判断的结果，每个叶节点代表一种决策结果。

决策树的关键概念

- 节点（Node）：决策树中的一个决策点。 - 根节点（Root）：决策树的起始点。 - 分支（Branch）：从一个节点到另一个节点的连接。 - 叶节点（Leaf）：没有子节点的节点，是一棵树最下面的结点。代表最终决策。 - 路径（Path）：从根节点到叶节点的一系列决策。

决策树的构建

构建决策树通常涉及以下步骤：

1. 选择最佳属性：使用某种度量（如信息增益、基尼不纯度）选择最佳属性进行分割。 2. 创建节点：为所选属性的每个可能值创建一个分支。 3. 分割数据：根据属性值将数据分割成不同的子集。 4. 递归构建：对每个子集递归地重复上述步骤，直到满足停止条件（如所有数据属于同一类别，或已达到树的最大深度）。

代码实现

1. 定义决策树节点

class TreeNode:
    def __init__(self, feature_index=None, threshold=None, left=None, right=None, *, value=None):
        self.feature_index = feature_index  # 特征索引
        self.threshold = threshold          # 阈值
        self.left = left                     # 左子树
        self.right = right                   # 右子树
        self.value = value                   # 节点值（叶节点时的分类结果）

2. 计算信息增益

def information_gain(X, y, split_feature_index, threshold):
    # 计算信息熵
    def calculate_entropy(y):
        # 实现信息熵的计算
        pass

    # 划分数据集
    left_indices = [i for i in range(len(X)) if X[i][split_feature_index] < threshold]
    right_indices = [i for i in range(len(X)) if X[i][split_feature_index] >= threshold]

    # 计算信息增益
    total_entropy = calculate_entropy(y)
    left_entropy = calculate_entropy([y[i] for i in left_indices])
    right_entropy = calculate_entropy([y[i] for i in right_indices])
    weight_left = len(left_indices) / len(X)
    weight_right = len(right_indices) / len(X)

    information_gain = total_entropy - (weight_left * left_entropy + weight_right * right_entropy)
    return information_gain

3. 选择最佳分割特征

def best_split(X, y):
    best_feature = None
    best_threshold = None
    max_information_gain = -1

    for feature_index in range(X.shape[1]):
        for i in range(X.shape[0]):
            threshold = X[i][feature_index]
            gain = information_gain(X, y, feature_index, threshold)
            if gain > max_information_gain:
                best_feature = feature_index
                best_threshold = threshold
                max_information_gain = gain

    return best_feature, best_threshold

4. 构建决策树

def build_tree(X, y, max_depth=None, current_depth=0):
    if len(np.unique(y)) == 1 or current_depth == max_depth:
        return TreeNode(value=np.argmax(np.unique(y)))

    best_feature, best_threshold = best_split(X, y)
    if best_feature is None:
        return TreeNode(value=np.argmax(np.unique(y)))

    left_indices = [i for i in range(len(X)) if X[i][best_feature] < best_threshold]
    right_indices = [i for i in range(len(X)) if X[i][best_feature] >= best_threshold]

    left_X = [X[i] for i in left_indices]
    left_y = [y[i] for i in left_indices]
    right_X = [X[i] for i in right_indices]
    right_y = [y[i] for i in right_indices]

    left_child = build_tree(left_X, left_y, max_depth, current_depth + 1)
    right_child = build_tree(right_X, right_y, max_depth, current_depth + 1)

    return TreeNode(feature_index=best_feature, threshold=best_threshold, left=left_child, right=right_child)

5. 决策树预测

def predict(tree, x):
    if tree.value is not None:
        return tree.value
    if x[tree.feature_index] < tree.threshold:
        return predict(tree.left, x)
    else:
        return predict(tree.right, x)