实现简单的决策树最优划分

决策树（Decision Tree）是一种基本的分类与回归方法。是一种典型的非参数学习的机器学习算法。
决策树算法的核心就在于如何选择最优的划分属性，对于一些数值型的数据而言，除了找到最优的划分属性，还需要找到最优的划分阈值。
今天就利用scikit-learn中自带的数据集简单实现一下找最优划分属性和最优划分阈值这个过程。
首先对于决策树而言，寻找最优划分属性和最优划分阈值的问题最终还是要回归到寻找极值的问题。这里就要引入一个概念，信息熵，代表了随机变量的不确定度。不确定性越大的话，随机变量的不确定度就越高。计算公式如下：
H(x) = E[I(xi)] = E[ log(2,1/p(xi)) ] = -∑p(xi)log(2,p(xi)) (i=1,2,..n)
要对数据进行分类的话就是要使得随机变量的不确定度最低，因此要使信息熵的值最小。因此决策树的最优划分问题就转化成了求H(x)最小时的划分属性与阈值。我们只需要遍历所有的属性以及所有的划分阈值，找到一个最小的H(x), 记录下划分属性和阈值即可。

首先加载需要用到的模块

import numpy as np
import matplotlib.pyplot as plt
from math import log
from collections import Counter
from sklearn import datasets

使用scikit-learn中的鸢尾花数据集来进行操作

为了简化运算只使用鸢尾花数据的后两个维度的数据

iris = datasets.load_iris()
X = iris.data[:, 2:]
y = iris.target

定义一个根据阈值以及维度划分数据的函数，模拟决策树的划分操作

def split(X, y, d, v):

    return X[X[:, d] > v], X[X[:, d] <= v], y[X[:, d] > v], y[X[:, d] <= v]

X, y 为传入的数据
d代表的是X的哪一个维度
v代表划分的阈值，小于v的划分为一类，大于v的划分为另一类
该函数返回的结果就是决策树的左右节点以及左右节点中数据对应的分类情况。

定义一个求信息熵的函数

def get_entropy(y):

    counter = Counter(y)
    res = 0.0
    for num in counter.values():
        p = num / len(y)
        res += -p * log(p)
    return res

这里我们只需要传入一个y参数就可以计算信息熵
res就是传入y的信息熵

遍历所有的维度以及划分阈值

def try_split(X, y):
    
    best_entropy = float('inf')
    best_d, best_v = -1, -1
    
    for d in range(X.shape[1]):
        sorted_index = np.argsort(X[:,d])
        for i in range(1, len(X)):
            if X[sorted_index[i-1], d] != X[sorted_index[i], d]:
                v = (X[sorted_index[i-1], d] + X[sorted_index[i], d]) / 2
                x_l, x_r, y_l, y_r = split(X, y, d, v)
                e = get_entropy(y_l) + get_entropy(y_r)
                if e < best_entropy:
                    best_entropy = e
                    best_d = d
                    best_v = v
    return best_entropy, best_d, best_v

使用best_entropy, best_d, best_v 记录最小的信息熵以及最佳的d和v。
求出了最佳的维度以及阈值后我们可以简单看下划分后的信息熵。

结果

entropy1, d1, v1 = try_split(X, y)
x_l, x_r, y_l, y_r = split(X, y, d, v)
print(get_entropy(y_l))
print(get_entropy(y_r))