课程开源地址及相关视频链接：（当然这里也希望大家支持一下正版西瓜书和南瓜书图书，支持文睿、秦州等等致力于开源生态建设的大佬✿✿ヽ(°▽°)ノ✿）
【吃瓜教程】《机器学习公式详解》（南瓜书）与西瓜书公式推导_哔哩哔哩_bilibili
正文部分
决策树是一种有监督的机器学习算法，可用于解决分类和回归问题，是使用分支方法说明决策的所有可能结果的图，可理解为实现某一特定结果的决策，随机森林是基于树的机器学习算法，是随机创造的决策树组成的森林，该算法利用了多棵决策树来进行决策，是用于分类、回归和其他任务的集成学习方法，输出结果是将单个决策树的输出整合起来生成最后的输出结果。主要区别：
- 输出结果不同
- 复杂度不同
决策树的一些优点是
易于理解和解释。树可以可视化。
需要很少的数据准备。其他技术通常需要数据归一化，需要创建虚拟变量，并删除空白值。一些树和算法组合支持 缺失值。
使用树的成本（即预测数据）与用于训练树的数据点的数量的对数成正比。
能够处理数值数据和分类数据。但是，scikit-learn 实现目前不支持分类变量。其他技术通常专门用于分析仅包含一种变量类型的数据集。有关更多信息，请参阅 算法。
能够处理多输出问题。
使用白盒模型。如果在模型中观察到特定情况，则该条件的解释可以通过布尔逻辑轻松解释。相比之下，在黑盒模型（例如，在人工神经网络中），结果可能更难解释。
可以使用统计检验来验证模型。这使得可以考虑模型的可靠性。
即使其假设在一定程度上被生成数据的真实模型所违反，也能表现良好。
决策树的缺点包括
决策树学习器可以创建过度复杂的树，这些树不能很好地概括数据。这被称为过拟合。为了避免这个问题，需要使用修剪、设置叶节点所需的最小样本数或设置树的最大深度等机制。
决策树可能不稳定，因为数据中的微小变化可能会导致生成完全不同的树。这个问题可以通过在集成中使用决策树来缓解。
决策树的预测既不平滑也不连续，而是如上图所示的分段常数逼近。因此，它们不擅长外推。
学习最优决策树的问题在几个方面（包括最优性和简单概念）都是已知的 NP 完全问题。因此，实际的决策树学习算法基于启发式算法，例如贪婪算法，在每个节点上做出局部最优决策。此类算法不能保证返回全局最优决策树。这可以通过在集成学习器中训练多棵树来缓解，其中特征和样本是随机抽取并替换的。
有一些概念很难学习，因为决策树不容易表达它们，例如 XOR、奇偶校验或多路复用器问题。
如果某些类占主导地位，决策树学习器会创建有偏差的树。因此，建议在使用决策树拟合之前平衡数据集。
决策树算法的主要步骤
（1）选择最优属性（根节点）
决策树判断一个属性是不是当前数据集的最优属性，是依靠信息熵变化的程度来选择的。选择某个属性，依照这个属性的值，对训练集进行划分，划分后的子训练集的信息熵之和，相比未分割前的数据集信息熵，下降最多的，就是当前的最优属性。也就是说，根据这个属性，我们就可以对数据集进行很大程度上的区分，例如猫和狗之间用耳朵区分，非常快。
（2）生成决策树。（叶子节点的选择）
选取最优属性后，根据此属性的取值，对原始数据集划分，得到子数据集，再将每个子数据集当作完整数据集，迭代进行最优属性的选取，直到数据集中样本都是同一个分类标签时，决策树生成过程结束。
有时根据场景业务需求的不同，也不要求数据集分割到无法再分类的程度，而是指定迭代的次数，即决策树到第几层就不再分割了，直接把当前叶子数据集中数量最多的分类标签作为叶子节点。这是不同的停止规则。
而决策树的三种常见算法，则是根据选择最优属性时计算的信息熵函数不同划分的。ID3 是根据信息熵，C4.5是根据信息增益率。CART是采用了基尼Gini系数。
（3）剪枝（防止过拟合）
剪枝就是给决策树瘦身，这一步想实现的目标就是，不需要太多的判断，同样可以得到不错的结果。
之所以这么做，是为了防止“过拟合”（Overfitting）现象的发生。
过拟合：指的是模型的训练结果“太好了”，以至于在实际应用的过程中，会存在“死板”的情况，导致分类错误。
欠拟合：指的是模型的训练结果不理想。
数据集为：
input = [[0.697, 0.460, 1],
[0.774, 0.376, 1],
[0.634, 0.264, 1],
[0.608, 0.318, 1],
[0.556, 0.215, 1],
[0.403, 0.237, 1],
[0.481, 0.149, 1],
[0.437, 0.211, 1],
[0.666, 0.091, 0],
[0.243, 0.267, 0],
[0.245, 0.057, 0],
[0.343, 0.099, 0],
[0.639, 0.161, 0],
[0.657, 0.198, 0],
[0.360, 0.370, 0],
[0.593, 0.042, 0],
[0.719, 0.103, 0]]pandas：决策树的构建涉及到数据集的一些操作，利用pandas的DataFrame数据结构可以很好方便的完成
copy :在递归时浅拷贝会导致问题,使用copy.deepcopy()进行深拷贝
matplot.pyplot:绘制决策树的划分图像
import pandas as pd
import copy
import matplotlib.pyplot as plt
import numpy as np
from math import fabs定义回归树的节点类Node
attrList 节点剩下的属性列表
Dataset 节点划分到的数据集
left/right 左右子树
c 叶节点的预测值
description 该节点的描述（可选）
attr 该节点划分属性
s 划分属性的值
class Node:
def __init__(self, description="", c = -1, Dataset=pd.DataFrame(), attrList=[]):
self.attrList = attrList
self.Dataset = Dataset
self.left = None
self.right = None
self.c = c
self.attr = ""
self.s = -1
self.desciption = description损失函数计算：
def loss(attr, s, data):
D1 = data[data[attr] <= s]
D1_mean = D1['label'].std() * D1.size
D2 = data[data[attr] > s]
D2_mean = D2['label'].std() * D2.size
return D1_mean + D2_mean
def findOptDiv(root):
losses = []
for attr in root.attrList:
for s in root.Dataset[attr]:
losses.append((loss(attr, s, root.Dataset), attr, s))
minLoss = min(losses)
return minLoss二叉树的构建
在以下情况返回IF
len(attrList) == 0：此时所有属性已经划分完毕， 就以该集合所有样本的label的均值作预测值 Dataset.size == 1：此时该节点的样本仅有一个 就 以该样本的label值做预测值
ELSE 将样本按最优划分划分为两个集合D1，D2，并分别构建subTree
def buildTree(root):
# if root.Dataset.size() <= 1:
# description = "leaf node"
# c_p = root.Dataset['label'].mean()
# leaf = Node(description=description, c = c_p)
# 如果样本集合中只有一个样本那么该节点为叶节点，该叶节点的预测值是该唯一样本的label
if root.Dataset.size == 1:
root.c = root.Dataset['label']
return
# 如果已经将属性分完了，那么该节点为叶节点，剩下的样本集中label的期望为该叶节点的预测值
elif len(root.attrList) == 0:
root.description = "leaf node"
root.c = root.Dataset['label'].mean()
return
else:
# 找到最优化分
(_, attr, s) = findOptDiv(root)
# 将节点的划分属性设为找到的attr
root.attr = copy.deepcopy(attr)
# 将按属性attr划分该节点值划分值s设为最优的s
root.s = copy.deepcopy(s)
# 将样本集合按照找到的最优化分划分为D1， D2
D1 = copy.deepcopy(root.Dataset[root.Dataset[attr] <= s])
D2 = copy.deepcopy(root.Dataset[root.Dataset[attr] > s])
# 将划分该节点属性从属性集合中删除
list_notremoved = copy.deepcopy(root.attrList)
root.attrList.remove(attr)
list_removed = copy.deepcopy(root.attrList)
root.attrList = copy.deepcopy(list_notremoved)
# 构建左子树和右子树
root.left = Node(Dataset = D1, attrList=copy.deepcopy(list_removed))
root.right = Node(Dataset = D2, attrList=copy.deepcopy(list_removed))
buildTree(root.left)
buildTree(root.right)
return root
可以大致看出决策过程
- 先看含糖率：
- 小于.13
- 小于.666 坏瓜
- 大于.666 好瓜
- 大于.13
- 小于.697 0.6的概率是好瓜
- 大于.697 1的概率是好瓜
- 小于.13
