关键词：
学习心得
task2学习GYH大佬的回归CART树，并在此基础上改为分类CART树。
更新ing。。
这里做一些对决策树分裂依据更深入的思考引导：我们在task1证明离散变量信息增益非负时曾提到，信息增益本质上就是联合分布和边缘分布乘积的kl散度，而事实上kl散度属于f-divergence（https://en.wikipedia.org/wiki/F-divergence）中的一类特殊情况，由于在分裂时我们衡量的是这两个分布的差异到底有多大，因此f-divergence中的任意一种距离度量都可以用来作为分裂依据，那么在树结构上进行分裂，这些散度究竟对树的生长结果产生了怎样的影响，似乎还没有看到文章讨论过这些（可以试图充分地讨论它们之间的一些理论性质和联系）
（1）可能会发现在与sklearn对比时，有时会产生两者结果预测部分不一致的情况，这种现象主要来自于当前节点在分裂的时候不同的特征和分割点组合产生了相同的信息增益，但由于遍历特征的顺序（和sklearn内的遍历顺序）不一样，因此在预测时会产生差异，并不是算法实现上有问题。
（2）对比的时候作差后要取绝对值，(np.abs(res1-res2)<1e-8).mean()。
文章目录
一、回顾决策树算法
二、代码实践
from CART import DecisionTreeRegressor
from CARTclassifier import DecisionTreeClassifier
from sklearn.tree import DecisionTreeRegressor as dt
from sklearn.tree import DecisionTreeClassifier as dc
from sklearn.datasets import make_regression
from sklearn.datasets import make_classification
if __name__ == "__main__":
# 模拟回归数据集
X, y = make_regression(
n_samples=200, n_features=10, n_informative=5, random_state=0
)
# 回归树
my_cart_regression = DecisionTreeRegressor(max_depth=2)
my_cart_regression.fit(X, y)
res1 = my_cart_regression.predict(X)
importance1 = my_cart_regression.feature_importances_
sklearn_cart_r = dt(max_depth=2)
sklearn_cart_r.fit(X, y)
res2 = sklearn_cart_r.predict(X)
importance2 = sklearn_cart_r.feature_importances_
# 预测一致的比例
print(((res1-res2)<1e-8).mean())
# 特征重要性一致的比例
print(((importance1-importance2)<1e-8).mean())
# 模拟分类数据集
X, y = make_classification(
n_samples=200, n_features=10, n_informative=5, random_state=0
)
# 分类树
my_cart_classification = DecisionTreeClassifier(max_depth=2)
my_cart_classification.fit(X, y)
res3 = my_cart_classification.predict(X)
importance3 = my_cart_classification.feature_importances_
sklearn_cart_c = dc(max_depth=2)
sklearn_cart_c.fit(X, y)
res4 = sklearn_cart_c.predict(X)
importance4 = sklearn_cart_c.feature_importances_
# 预测一致的比例
print(((res3-res4)<1e-8).mean())
# 特征重要性一致的比例
print(((importance3-importance4)<1e-8).mean())
# -*- coding: utf-8 -*-
"""
Created on Sun Oct 17 10:46:08 2021
@author: 86493
"""
import numpy as np
from collections import Counter
def MSE(y):
return ((y - y.mean())**2).sum() / y.shape[0]
# 基尼指数
def Gini(y):
c = Counter(y)
return 1 - sum([(val / y.shape[0]) ** 2 for val in c.values()])
class Node:
def __init__(self, depth, idx):
self.depth = depth
self.idx = idx
self.left = None
self.right = None
self.feature = None
self.pivot = None
class Tree:
def __init__(self, max_depth):
self.max_depth = max_depth
self.X = None
self.y = None
self.feature_importances_ = None
def _able_to_split(self, node):
return (node.depth < self.max_depth) & (node.idx.sum() >= 2)
def _get_inner_split_score(self, to_left, to_right):
total_num = to_left.sum() + to_right.sum()
left_val = to_left.sum() / total_num * Gini(self.y[to_left])
right_val = to_right.sum() / total_num * Gini(self.y[to_right])
return left_val + right_val
def _inner_split(self, col, idx):
data = self.X[:, col]
best_val = np.infty
for pivot in data[:-1]:
to_left = (idx==1) & (data<=pivot)
to_right = (idx==1) & (~to_left)
if to_left.sum() == 0 or to_left.sum() == idx.sum():
continue
Hyx = self._get_inner_split_score(to_left, to_right)
if best_val > Hyx:
best_val, best_pivot = Hyx, pivot
best_to_left, best_to_right = to_left, to_right
return best_val, best_to_left, best_to_right, best_pivot
def _get_conditional_entropy(self, idx):
best_val = np.infty
for col in range(self.X.shape[1]):
Hyx, _idx_left, _idx_right, pivot = self._inner_split(col, idx)
if best_val > Hyx:
best_val, idx_left, idx_right = Hyx, _idx_left, _idx_right
best_feature, best_pivot = col, pivot
return best_val, idx_left, idx_right, best_feature, best_pivot
def split(self, node):
# 首先判断本节点是不是符合分裂的条件
if not self._able_to_split(node):
return None, None, None, None
# 计算H(Y)
entropy = Gini(self.y[node.idx==1])
# 计算最小的H(Y|X)
(
conditional_entropy,
idx_left,
idx_right,
feature,
pivot
) = self._get_conditional_entropy(node.idx)
# 计算信息增益G(Y, X)
info_gain = entropy - conditional_entropy
# 计算相对信息增益
relative_gain = node.idx.sum() / self.X.shape[0] * info_gain
# 更新特征重要性
self.feature_importances_[feature] += relative_gain
# 新建左右节点并更新深度
node.left = Node(node.depth+1, idx_left)
node.right = Node(node.depth+1, idx_right)
self.depth = max(node.depth+1, self.depth)
return idx_left, idx_right, feature, pivot
def build_prepare(self):
self.depth = 0
self.feature_importances_ = np.zeros(self.X.shape[1])
self.root = Node(depth=0, idx=np.ones(self.X.shape[0]) == 1)
def build_node(self, cur_node):
if cur_node is None:
return
idx_left, idx_right, feature, pivot = self.split(cur_node)
cur_node.feature, cur_node.pivot = feature, pivot
self.build_node(cur_node.left)
self.build_node(cur_node.right)
def build(self):
self.build_prepare()
self.build_node(self.root)
def _search_prediction(self, node, x):
if node.left is None and node.right is None:
# return self.y[node.idx].mean()
return self.y[node.idx].min()
if x[node.feature] <= node.pivot:
node = node.left
else:
node = node.right
return self._search_prediction(node, x)
def predict(self, x):
return self._search_prediction(self.root, x)
class DecisionTreeClassifier:
"""
max_depth控制最大深度，类功能与sklearn默认参数下的功能实现一致
"""
def __init__(self, max_depth):
self.tree = Tree(max_depth=max_depth)
def fit(self, X, y):
self.tree.X = X
self.tree.y = y
self.tree.build()
self.feature_importances_ = (
self.tree.feature_importances_
/ self.tree.feature_importances_.sum()
)
return self
def predict(self, X):
return np.array([self.tree.predict(x) for x in X])
输出结果如下，可见在误差范围内，实现的分类树和回归树均和sklearn实现的模块近似。
1.0
1.0
1.0
1.0
Reference
（0）datawhale notebook
（1）CART决策树(Decision Tree)的Python源码实现
（2）https://github.com/RRdmlearning/Decision-Tree
（3）《机器学习技法》—决策树
树模型与集成学习(task4)两种并行集成的树模型(代码片段)
学习总结（1）随机森林中的随机主要来自三个方面：其一为bootstrap抽样导致的训练集随机性，其二为每个节点随机选取特征子集进行不纯度计算的随机性，其三为当使用随机分割点选取时产生的随机性（... 查看详情
机器学习决策树理论第二卷
...1CART算法CART分类与回归树(classificationandregressiontree，CART)模型室友Breiman等人1984年提出，是应用广泛的决策 查看详情
面试笔试题集：集成学习，树模型，randomforests，gbdt，xgboost
文章大纲决策树决策树的优缺点集成学习基本概念sklearn中的集成学习类集成学习分哪几种？他们有何异同？Boosting提升法Bagging装袋法stacking堆叠法方差，偏差与集成学习的关系如何从减小方差和偏差的角度解释Boosting... 查看详情
决策树与迭代决策树(转)
...笔记 cnblogs.com/maybe2030/p/4734645.html阅读目录1.决策树的模型2.决策树的基本知识3.ID3、C4.5&CART4.RandomForest5.GBDT6.参考内容 今天我们来谈一谈机器学习算法中的各种树形算法，包括ID3、C4.5、CART以及基于集成思想的树模型Rando... 查看详情
决策树(id3,c4.5,cart)原理以及实现(代码片段)
...树决策树是一种基本的分类和回归方法.决策树顾名思义,模型可以表示为树型结构,可以认为是if-then的集合,也可以认为是定义在特征空间与类空间上的条件概率分布.[图片上传失败...(image-2e6565-1543139272117)]决策树的中间节点可以看... 查看详情
机器学习笔记——cart树
CART树 CART树与上一篇文章提到的ID3、C4.5的区别在于： （1）CART树只能够生成2个结点，即CART树是一棵二叉决策树，而后两者在进行划分时可以根据特征值的种类生成2个以上的结点。 （2）CART分类树的划分依据... 查看详情
机器学习笔记之三cart分类与回归树
本文结构：CART算法有两步回归树的生成分类树的生成剪枝CART－ClassificationandRegressionTrees分类与回归树，是二叉树，可以用于分类，也可以用于回归问题，最先由Breiman等提出。分类树的输出是样本的类别，回归树的输出是一个实... 查看详情
实验三：cart分类决策树python实现（两个测试集）|机器学习(代码片段)
目录python实现分步源代码（全部）测试集1（鸢尾花集）测试集2（红酒品类数据集）总结python实现分步划分数据子集（注意区分离散特征值和连续特征值）#获取数据子集，分类与回归的做法相同... 查看详情
机器学习-集成学习gbdt(代码片段)
...于决策树的集成学习算法，它通过逐步地训练多个决策树模型来提高预测性能。具体来说，GBDT采用加法模型（additivemodel）的思想，每次训练一个新的决策树来拟合残差（预测误差），然后将所有决策树的预测结果相加作为最终... 查看详情
机器学习gbdt-xgboost决策树提升(代码片段)
...前向分步算法GB再解释GBDT大BOSS——xgboost训练xgboostxgboost模型目标函数正则化项处理理论终章最终章-拨开云雾见月明多说一嘴xgboostxgboost是一个监督模型，它对应的模型就是一堆CART树，即由CART树组成的随机森林。预测的最终结果... 查看详情
《机器学习》（周志华）第4章决策树笔记理论及实现——“西瓜树”——cart决策树
CART决策树（一）《机器学习》（周志华）第4章决策树笔记理论及实现——“西瓜树”参照上一篇ID3算法实现的决策树（点击上面链接直达），进一步实现CART决策树。其实只需要改动很小的一部分就可以了，把原先计算信息熵和... 查看详情
树模型与集成学习(task6)梯度提升树gbdt+lr
学习总结（1）不同问题的提升树学习算法，主要区别在于使用的损失函数不同，如用平方误差损失函数的回归问题、用指数损失函数的分类问题、用一般损失函数的一般决策问题等。（2）不管是二分类问题的提升树，还是回归... 查看详情
lesson8.1决策树的核心思想与建模流程(代码片段)
...知识补充2.1决策树简单构建2.2决策树的分类过程2.3决策树模型本质2.4决策树的树生长过程2.5树模型的基本结构二、决策树的分类与流派1.ID3(IterativeDichotomiser3)、C4.5、C5.0决策树2.CART决策树3.CHAID树与此前的聚类算法类似，树模... 查看详情
一文读懂机器学习大杀器xgboost原理
...集成在一起形成一个强分类器。因为XGBoost是一种提升树模型，所以它是将许多树模型集成在一起，形成一个很强的分类器。而所用到的树模型则是CART回归树模型。讲解其原理前，先讲解一下CART回归树。一 查看详情
决策树算法
...以作为分类算法，也可以作为回归算法，同时也特别适合集成学习比如随机森林。本文就对决策树算法原理做一个总结，上篇对ID3，C4.5的算法思想做了总结，下篇重点对CART算法做一个详细的介绍。选择CART做重点介绍的原因是sci... 查看详情
集成学习之梯度提升树(gbdt)算法
...前向分布算法，但是弱学习器限定了只能使用CART回归树模型，而且GBDT在模型训练的时候，是要求模型预测的样本损失尽可能的小。首先，GBDT使用的决策树是CART回归树，无论是处理回归问题还是二分类以及多分类，GBDT使用的决... 查看详情
机器学习-集成算法(代码片段)
文章目录集成算法1.定义2.具体模型2.1.Bagging2.2.Boosting2.3.Stacking3.随机森林3.1.树模型结构3.2.随机森林的优点3.3.分类与回归问题3.4.树模型个数问题3.5.参数问题(特征重要性)3.6.可视化展示问题4.集成基本思想4.1.硬投票策略步骤4.2.软... 查看详情
笔记︱集成学习ensemblelearning与树模型bagging和boosting
笔记︱集成学习EnsembleLearning与树模型、Bagging和Boosting本杂记摘录自文章《开发|为什么说集成学习模型是金融风控新的杀手锏？》基本内容与分类见上述思维导图。 . .一、机器学习元算法随机森林：决策树+bagging=随机森... 查看详情