[机器学习]实验二：决策树回归算法实践(RegressonTree)

决策树实际是一种分类算法，先有树，再有决策

一、决策树概述

确定五个人是否打篮球的决策树：

节点上是决策属性判断，叶子就是预测值！每个决策点实现一个具有离散输出的函数

1. 训练阶段：从给定训练数据集DB，构造一颗决策树
2. 分类阶段：从根节点开始，按照决策树的判别属性，依次向下直到叶节点，获得分类或者决策结果。

---

二、熵

用于描述当前分直接点的纯度(purity)，“信息熵”度量样本集合纯度最常用的一种指标

不确定性与发生概率互斥

• 此公式在西瓜书上对数底是2，此公式结果表明：熵越小,样本的纯度越大(发生概率大)。

---

三、决定根节点

构造决策树的基本思想：

随着树的深度增加，节点的熵迅速的降低。熵降低的速度越快越好（这样有望可得到一个高度较矮的树）

ID3：信息增益

1. 对候选节点进行相同的操作(计算熵S)，熵需要乘以类型的发生概率得到E（entroy）
2. 信息增益 gain(属性)= S-E，(熵值变化 信息增益>0，划分结果好），期望信息增益越大越好
3. 信息增益gain越大，则选择作为根节点，数据接着处理（递归余下节点）

优化

原因：如果属性下的结果太多，甚至一个样本一个结果，那么信息增益就会最大化

引入信息增益率（C4.5），信息增益率 = 信息增益/自身熵

能够有处理连续型的属性。首先将连续型属性离散化，属性值分为不同的区间，依据各个分裂点Gain值大小

缺失数考虑：可简单忽略缺失数据，即在计算gain时，仅考虑具有属性的记录

CART: Gini系数

---

四、评价函数

• H(t) ：当前叶节点的熵值（信息增益率、Gini系数）
• Nt：当前叶子节点的样本数
• 希望评价函数越小，则在叶节点的分类效果越好

---

五、连续型值切分

1.贪婪

1. 排序
2. 二分

2.决策树剪枝

避免决策树太大，过拟合，求最矮决策树

预剪枝：构建决策树的过程中，提前停止（预防过拟合）

后剪枝：决策树构建完成之后，再开始剪枝（自底向上，判断是否需要剪枝）

• T：叶子节点个数
• C(T)：评价函数

---

六、随机森林

Bootstrap：有放回的采样

Bagging：有放回的采样n个样本一共建立分类器

随机森林构造每一个决策树的时候，有放回采样比例随机采样。

---

七、Example

上面讲的是分类树，走错方向了

# -*- coding: utf-8 -*-
from sklearn.datasets import load_boston
from sklearn.utils import shuffle
from sklearn.model_selection import train_test_split


# list 分割
def list_split(X, idxs, feature, split):
    ret = [[], []]
    while idxs:
        if X[idxs[0]][feature] < split:
            ret[0].append(idxs.pop(0))
        else:
            ret[1].append(idxs.pop(0))
    return ret


# 计算准确度
def get_accuracy(reg, X, y):
    sse = sum((yi_hat - yi) ** 2 for yi_hat, yi in zip(reg.predict(X), y))
    y_avg = sum(y) / len(y)
    sst = sum((yi - y_avg) ** 2 for yi in y)
    result = 1 - sse / sst
    print("准确度： %.3f!" % result)
    return result


# 节点类
class Node(object):
    def __init__(self, score=None):
        self.score = score
        self.left = None
        self.right = None
        self.feature = None
        self.split = None


# 回归树类
class RegressionTree(object):
    def __init__(self):
        self.root = Node()
        self.depth = 1
        self._rules = None

    def _get_split_mse(self, X, y, idx, feature, split):
        """
        y_hat = Sum(y_i) / n, i <- [1, n]
        Loss(y_hat, y) = Sum((y_hat - y_i) ^ 2), i <- [1, n]
        Loss = LossLeftNode+ LossRightNode
        """
        split_sum = [0, 0]
        split_cnt = [0, 0]
        split_sqr_sum = [0, 0]
        # 迭代每个xi 并比较分割点
        for i in idx:
            xi, yi = X[i][feature], y[i]
            if xi < split:
                split_cnt[0] += 1
                split_sum[0] += yi
                split_sqr_sum[0] += yi ** 2
            else:
                split_cnt[1] += 1
                split_sum[1] += yi
                split_sqr_sum[1] += yi ** 2
        # 计算y的mse, D(X) = E{[X-E(X)]^2} = E(X^2)-[E(X)]^2
        split_avg = [split_sum[0] / split_cnt[0], split_sum[1] / split_cnt[1]]
        split_mse = [split_sqr_sum[0] - split_sum[0] * split_avg[0],
                     split_sqr_sum[1] - split_sum[1] * split_avg[1]]
        return sum(split_mse), split, split_avg

    def _choose_split(self, X, y, idx, feature):
        # 只有一个点无法分割
        unique = set([X[i][feature] for i in idx])
        if len(unique) == 1:
            return None
        # 无分割
        unique.remove(min(unique))
        # 得到分割点并找到最小的
        mse, split, split_avg = min(
            (self._get_split_mse(X, y, idx, feature, split)
             for split in unique), key=lambda x: x[0])
        return mse, feature, split, split_avg

    # 得到最小的mse
    def _choose_feature(self, X, y, idx):
        m = len(X[0])
        # 比较每个功能的mse并选择最佳功能。
        split_rets = map(lambda j: self._choose_split(X, y, idx, j), range(m))
        split_rets = filter(lambda x: x is not None, split_rets)
        # 如果不能拆分任何功能，则终止
        return min(split_rets, default=None, key=lambda x: x[0])

    # 拟合一个回归树
    def fit(self, X, y, max_depth=5, min_samples_split=2):
        # 初始化深度、节点、索引
        idxs = list(range(len(y)))
        que = [(self.depth + 1, self.root, idxs)]
        # 广度优先搜索
        while que:
            depth, nd, idxs = que.pop(0)
            # 如果超过max_depth,则停止循环
            if depth > max_depth:
                depth -= 1
                break
            # min_samples_split or Node is 100% 纯.
            if len(idxs) < min_samples_split or \
                    set(map(lambda i: y[i], idxs)) == 1:
                continue
            # 如果任何要素没有超过2个唯一要素，则停止拆分
            split_ret = self._choose_feature(X, y, idxs)
            if split_ret is None:
                continue
            # Split
            _, feature, split, split_avg = split_ret
            # 更新当前节点的属性
            nd.feature = feature
            nd.split = split
            nd.left = Node(split_avg[0])
            nd.right = Node(split_avg[1])
            # 将当前节点的子节点放入队列中
            idxs_split = list_split(X, idxs, feature, split)
            que.append((depth + 1, nd.left, idxs_split[0]))
            que.append((depth + 1, nd.right, idxs_split[1]))
        # 更细规则
        self.depth = depth

    def _predict(self, Xi):
        nd = self.root
        while nd.left and nd.right:
            if Xi[nd.feature] < nd.split:
                nd = nd.left
            else:
                nd = nd.right
        return nd.score

    def predict(self, X):
        return [self._predict(Xi) for Xi in X]


if __name__ == '__main__':
    boston = load_boston()
    X, y = shuffle(boston.data, boston.target, random_state=13)
    X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=10)

    reg = RegressionTree()
    reg.fit(X=X_train, y=y_train, max_depth=5)

    # 计算准确度
    get_accuracy(reg, X_test, y_test)

运行效果：

准确度： 0.836!

Process finished with exit code 0