【机器学习】决策树算法

小明大学毕业了，去了一家银行当行长，上班第一天就有了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 = Nonebest_threshold = Nonemax_information_gain = -1for 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_indexbest_threshold = thresholdmax_information_gain = gainreturn 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.valueif x[tree.feature_index] < tree.threshold:return predict(tree.left, x)else:return predict(tree.right, x)