DYBOY's Blog

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

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

一、决策树概述

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

分类决策

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

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

二、熵

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

不确定性与发生概率互斥

信息熵公式

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

Gini系数


三、决定根节点

构造决策树的基本思想:

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

例子

ID3:信息增益

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

优化

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

引入信息增益率(C4.5),信息增益率 = 信息增益/自身熵

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

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

CART: Gini系数


四、评价函数

评价函数

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

五、连续型值切分

1.贪婪

  1. 排序
  2. 二分

2.决策树剪枝

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

预剪枝:构建决策树的过程中,提前停止(预防过拟合)

后剪枝:决策树构建完成之后,再开始剪枝(自底向上,判断是否需要剪枝)

DYBOY

  • 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
版权声明:《 [机器学习]实验二:决策树回归算法实践(RegressonTree) 》为DYBOY原创文章未经允许不得转载。

 DYBOY
 作者签名:安全从业者,爱好安全产品开发,渗透测试,Web漏洞研究

发表评论:

用心评论~

帅人已评:

况况
2018-10-31 16:43
不错,还有提升的空间
TOP
Powered by Emlog | Theme:Monkey by DYBOY
渝ICP备16008772号
sitemap