TVP

# 使用Python中从头开始构建决策树算法

Entropy(S) = -p_pos * log2(p_pos) - p_neg * log2(p_neg)

P_pos表示数据集中正标签的比例，P_neg表示数据集中负标签的比例。

Information Gain(S, A) = Entropy(S) - ∑ (|S_v| / |S|) * Entropy(S_v)

S 表示原始数据集，A表示要拆分的属性。S_v表示属性A保存值v的S的子集。

import numpy as np

class DecisionTree:

def __init__(self, max_depth=None):

self.max_depth = max_depth

def fit(self, X, y, depth=0):

n_samples, n_features = X.shape

unique_classes = np.unique(y)

# Base cases

if (self.max_depth is not None and depth >= self.max_depth) or len(unique_classes) == 1:

self.label = unique_classes[np.argmax(np.bincount(y))]

return

best_attribute = None

best_info_gain = -1

for feature in range(n_features):

info_gain = self._information_gain(X, y, feature)

if info_gain > best_info_gain:

best_info_gain = info_gain

best_attribute = feature

if best_attribute is None:

self.label = unique_classes[np.argmax(np.bincount(y))]

return

self.attribute = best_attribute

self.threshold = np.median(X[:, best_attribute])

left_indices = X[:, best_attribute]

right_indices = ~left_indices

self.left = DecisionTree(max_depth=self.max_depth)

self.right = DecisionTree(max_depth=self.max_depth)

self.left.fit(X[left_indices], y[left_indices], depth + 1)

self.right.fit(X[right_indices], y[right_indices], depth + 1)

def predict(self, X):

if hasattr(self, 'label'):

return np.array([self.label] * X.shape[0])

_information_gain方法计算给定属性的信息增益。它计算分裂后子熵的加权平均值，并从父熵中减去它。

def _information_gain(self, X, y, feature):

parent_entropy = self._entropy(y)

unique_values = np.unique(X[:, feature])

weighted_child_entropy = 0

for value in unique_values:

is_value = X[:, feature] == value

child_entropy = self._entropy(y[is_value])

weighted_child_entropy += (np.sum(is_value) / len(y)) * child_entropy

return parent_entropy - weighted_child_entropy

def _entropy(self, y):

_, counts = np.unique(y, return_counts=True)

probabilities = counts / len(y)

return -np.sum(probabilities * np.log2(probabilities))

_entropy方法计算数据集y的熵，它计算每个类的概率，然后使用前面提到的公式计算熵。

C4.5 是 ID3 的改进版本，C4.5 算法在特征选择时使用信息增益比，这是对信息增益的一种归一化，用于解决信息增益在选择特征时偏向于取值较多的特征的问题。

CART 与 ID3 和 C4.5 算法不同，CART(Classification And Regression Tree)又被称为分类回归树，算法采用基尼不纯度（Gini  impurity）来度量节点的不确定性，该不纯度度量了从节点中随机选取两个样本，它们属于不同类别的概率。

ID3、C4.5 和 CART 算法都是基于决策树的经典算法，像Xgboost就是使用的CART 作为基础模型。

• 发表于:
• 原文链接https://page.om.qq.com/page/O2LoqHy1PYkfAJ-A3M1fACEw0
• 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
• 如有侵权，请联系 cloudcommunity@tencent.com 删除。

2018-10-19

2018-07-02

2018-02-24

2018-06-25

2018-03-13

2021-08-02

2018-06-13

2018-03-22

2018-09-02

2018-01-27

2018-10-19

2018-01-26

2018-12-09

2018-05-21

2019-01-17

2018-05-21

2018-01-27

2018-02-10

2018-05-06

2018-03-20