手撕机器学习算法 | 决策树 | DecisionTree

❗写在前面 ❗：
 
… … … … … … … … . … … …
1️⃣ 提供两种语言实现：本文提供两种语言实现，分别为python和c++，分别依赖的核心库为numpy和eigen.
 
2️⃣ 提供关键步的公式推导：写出详尽的公式推导太花时间，所以只提供了关键步骤的公式推导。更详尽的推导，可移步其他博文或相关书籍.
 
3️⃣ 重在逻辑实现：文中的代码主要以实现算法的逻辑为主，在细节优化上面，并没有做更多的考虑，如果发现有不完善的地方，欢迎指出.
 
 
🌞 欢迎关注专栏，相应的内容会持续更新，祝大家变得更强！！
… … … … … … … … . … … …

1、原理推导

简单来说，决策树可以看做是一组if-then规则的集合，为决策树的根结点到叶子结点的每一条路径都构建一条规则，路径中的内部结点特征代表规则条件，而叶子结点表示这条规则的结论。

完整的决策树模型包括特征选择、决策树构建和决策树剪枝三大部分。

为了构建一颗决策树，我们需要从训练集中不断选取具有良好分类能力的特征对数据集进行划分。那什么样的特征才算是“好特征”呢？

很简单，当通过某个特征划分之后，左右节点的类别尽可能的是同一类时，该特征就是一个“好特征”，因为它可以使划分后的左右节点“变纯”。

以上只是一个定性的解释，那如何定量得出哪个特征划分最优？这里可以用到三种常用的技术：信息增益、信息增益比、基尼系数。

信息熵

 
    $e(d)=-\sum _{k=1}^y{p}_{k}log{p}_k$
 
其中$d$表示数据集，$k$表示类别，且$k$∈{1, 2, 3, … , $y$}，$p_k$表示该类别所占的比例。

熵是一种混乱程度，在这里可以理解为数据集中包含类别的“单纯”程度，当一个数据集所属类别越“单一”，其熵就越小，也可以说其混乱程度越低。

 
python代码 —— 信息熵

import numpy as np

# 计算信息熵
def entropy(label: list):
    """
    label: 包含类别取值的列表
    返回计算得到的信息熵的值
    """
    # 类别去重
    uniquedlabel = set(label)
    
    # 统计每种类别的比例/概率
    probs = [label.count(lab) / len(label) for lab in uniquedlabel]

    # 计算信息熵
    entropyvalue = - np.sum([pk * np.log2(pk) for pk in probs])

    return entropyvalue

# 信息熵测试
data1 = [1, 2, 3, 4, 4, 4, 3, 2, 1]
data2 = [1, 1, 1, 2, 1, 2, 1, 2, 1]

print("data1的信息熵: ", entropy(data1))
print("data2的信息熵: ", entropy(data2))

# 输出：
data1的信息熵:  1.9749375012019272
data2的信息熵:  0.9182958340544896

可以直观的看出data2中的信息熵比data1中要小，我们的直观感受也是data2比data1更干净，更纯洁。
 
c++代码 —— 信息熵

#include <iostream>
#include <eigen/dense>
#include <algorithm>
#include <unordered_set>

// 计算信息熵
double entropy(const vectorxi& label)
{
    // 类别去重
    unordered_set<int> uniquelabel(label.data(), label.data() + label.size());

    // 有y种类别
    int y = uniquelabel.size();

    // 统计每种类别的概率并计算信息熵
    double entropyvalue = 0.0;
    
    for (auto const& lab: uniquelabel)
    {
        double p = static_cast<double>((label.array() == lab).count()) / label.size();
        entropyvalue -= p * log2(p);
    }

    return entropyvalue;
}

// 信息熵测试
int main()
{
    vectorxi data1(9);
    vectorxi data2(9);
    data1 << 1, 2, 3, 4, 4, 4, 3, 2, 1;
    data2 << 1, 1, 1, 2, 1, 2, 1, 2, 1;
    
    cout << "data1的信息熵为: " << entropy(data1) << endl;
    cout << "data2的信息熵为: " << entropy(data2) << endl;
    
    return 0;
}

// 输出：
data1的信息熵为: 1.97494
data2的信息熵为: 0.918296

信息增益

 
介绍了信息熵，信息增益就很好解释了。简单来说就是数据集$d$在给定条件$a$的情况下变为数据集$d_a$所获得的不确定性增加：
 
    $g(d,a)=e(d)-e(d|a)$
 
用上面的写好的函数可以表示为：
 
    $gain=entropy(d)-entropy(d_a)$
 

信息增益比

 
信息增益已经是一个很好的决定特征划分的指标了，但存在一个缺陷，就是当某个特征分类取值较多时，该特征的信息增益计算结果就会较大。所以，基于信息增益选择特征时，会偏向于取值较大的特征。而使用信息增益比可以解决这个问题：
 
    $g_r(d,a)=\frac{g(d,a)}{e_a(d)}$
 
其中$e_a(d)=-\sum _{i=1}^n\frac{|d_i|}{d}lo{g}_2\frac{|d_i|}{d}$，$n$表示特征a的取值个数。

 
python代码 —— 信息增益比

def gainrateda(fi: ndarray, y: ndarray, a: float):
    """
	fi 某个特征数组
	y  标签数组
	a  划分的阈值条件
	"""
    # 这里的entropy函数就是上面实现的计算信息熵的
    ed = entropy(y.tolist())

    y1, y2 = y[fi < a], y[fi >= a]

    eda =  len(y1) / len(y) * entropy(y1.tolist()) + \
           len(y2) / len(y) * entropy(y2.tolist())

    gda = ed - eda

    grda = gda / (eda + 1e-10)  # 添加一个非常小的数防止分母为0

    return grda

 
c++代码 —— 信息增益比

double gainrateda(const vectorxd& fi, const vectorxi& y, double a)
{
	
    double ed = entropy(y);
    vectorxi y1(y.size()), y2(y.size());

    int n = 0, m = 0;
    for (int i = 0; i < fi.size(); i++)
    {
        if (fi(i) < a)
        {
            y1(n) = y(i);
            n++;
        }
        else
        {
            y2(m) = y(i);
            m++;
        }
    }
    y1.conservativeresize(n);
    y2.conservativeresize(m);
    double eda = double(n) / y.size() * entropy(y1) + 
                 double(m) / y.size() * entropy(y2);
    double gda = ed - eda;
    double erda = gda / (eda + 1e-10);

    return erda;
}

基尼系数

基尼指数也是一种较好的特征选择方法。基尼指数是针对概率分布而言的。假设样本有$k$个类，样本属于第$k$类的概率为$p_k$，则该样本类别概率分布的基尼指数可定义为：
 
    $gini(p)=\sum _{k=1}^k{p}_k(1-p_k)$
 
python代码 —— 基尼指数

def gini(label):
   	"""
   	label 标签列表
   	"""
    probs = [label.count(lab) / len(label) for lab in set(label)]
    ginivalue = np.sum([p * (1 - p) for p in probs])

    return ginivalue

 
c++代码 —— 基尼指数

double gini(const vectorxi& label)
{	// 类别去重
    std::unordered_set<int> uniquelabel(label.data(), label.data() + label.size());
   
    double ginivalue = 0.0;
    for (auto const& lab: uniquelabel)
    {
        double p = double((label.array() == lab).count()) / label.size();
        ginivalue += p * (1 - p);
    }
    
    return ginivalue;
}

 
以上三种特征选择方法，分别对应着三种经典的决策树算法：

{
	"id3决策树": "信息增益",
	"c4.5决策树": "信息增益比",
	"cart决策树": "基尼指数"   # 既可以用来分类, 也可以用于回归, 下面也将重点对它进行实现
}

文字有点写不动了，了解到这里，我们直接上代码，用代码语言直接去感受决策树算法的原理，我尽量在代码中把注释写详细点。

2、算法实现

python

# 这里先声明节点类型
# 该节点类型保存决策树构建时的各种信息以及子节点
import numpy as np
from numpy import ndarray, inf
from abc import abc, abstractmethod
# 这里先声明节点类型
# 该节点类型保存决策树构建时的各种信息以及子节点
class treenode:
    def __init__(self, featrueidx=none, threshold=none, leftbranch=none, rightbranch=none, leafvalue=none):
        # 该节点划分的特征索引
        self.featrueidx = featrueidx
        # 该节点划分时的特征阈值
        self.threshold = threshold
        # 该节点的左支
        self.leftbranch = leftbranch
        # 该节点的右支
        self.rightbranch = rightbranch
        # 该节点的值
        self.leafvalue = leafvalue


# cart回归树和cart分类树, 基本上只有在计算不纯度和预测叶子节点的值方面不同
# 同时他们又都是基于二叉树结构的, 所以直接定义一个二叉决策树类binarydecisiontree作为基类
# 然后把calcimpurity, calcleafvalue两个方法作为抽象方法, 交给子类去实现
class binarydecisiontree(abc):
    
    def __init__(self, minsamplenum=none, maxdepth=none, setminimpurity=none):
        # 决策树的根节点
        self.root = none
        # 节点最少要包含的样本树
        self.minsamplenum = minsamplenum
        # 决策树构建时的最大深度
        self.maxdepth = maxdepth
        # 划分时最小不纯度值
        self.setminimpurity = setminimpurity
    
    # 留给子类去实现: 用于计算纯度的
    @abstractmethod
    def calcimpurity(self, y, y1, y2):
        pass

    # 留给子类去实现: 用于计算叶节点值的
    @abstractmethod
    def calcleafvalue(self, y):
        pass  
    
    # 划分数据集：根据阈值将数据集划分为左右两部分
    def _splitxy(self, xy, fi, threshold):
        
        xy_left = xy[xy[:, fi] < threshold]
        xy_right = xy[xy[:, fi] >= threshold]

        return xy_left, xy_right

    # 递归构建决策树
    def constructtree(self, x, y, currentdepth=0):
        """
        x  训练的特征集
        y  对应的标签
        currentdepth  当前树的深度
        """
        
        # 设置当前不纯度为最大，在后续寻找划分特征和划分阈值时不断更新...
        minimpurity = inf
        # 最佳划分特征的索引
        bestfi = none
        # 最佳划分特征的阈值
        bestthreshold = none
        # 最佳划分条件下的左支x
        bestleftbranch_x = none
        # 最佳划分条件下的左支y
        bestleftbranch_y = none
        # 最佳划分条件下的右支x
        bestrightbranch_x = none
        # 最佳划分条件下的右支y
        bestrightbranch_y = none
        
        # 拼接合并一下xy方便操作
        xy = np.concatenate((x, y), axis=1)
        
        m, n = x.shape  # 样本数和特征维度

        # 如果当前样本数大于设置的最小样本数 且 当前深度未达最大深度时
        # 遍历寻找最佳划分特征及阈值, 条件是: 划分后的不纯度值最小 且
        # 还得小于 self.setminimpurity
        if (m >= self.minsamplenum and currentdepth <= self.maxdepth):
            
            # 挨个取特征列
            for fi in range(n):
                
                fi_values = np.expand_dims(x[:, fi], axis=1)

                # 挨个取划分值
                for threshold in set(fi_values):

                    # 根据特征值划分数据集
                    xy_left, xy_right = self._splitxy(xy, fi, threshold)
                    
                    # 划分后的数据集不能为空
                    if len(xy_left != 0) and len(xy_right != 0):
                        x_left = xy_left[:, :n]
                        y_left = xy_left[:, n:]
            
                        x_right = xy_right[:, :n]
                        y_right = xy_right[:, n:]

                        # 计算划分后的当前不纯度
                        currentimpurity = self.calcimpurity(y, y_left, y_right)
                        
                        # 判断当前的不纯度是否比最小不纯度低
                        # 若是就更新
                        if (currentimpurity < minimpurity):
                            bestfi = fi
                            bestleftbranch_x = x_left
                            bestleftbranch_y = y_left

                            bestrightbranch_x = x_right
                            bestrightbranch_y = y_right
                            bestthreshold = threshold
                            
                            minimpurity = currentimpurity
            
            # 经过上面两个for循环，我们找到了最佳划分参数
            # 如果当前最佳的划分参数中的不纯度的值，比我们设定的最小不纯度的值还要小
            # 则进行划分构造
            if (minimpurity < self.setminimpurity):
                
                # 递归构造左支
                leftbranch = self.constructtree(bestleftbranch_x, bestleftbranch_y, currentdepth+1)
                # 递归构造右支
                rightbranch = self.constructtree(bestrightbranch_x, bestrightbranch_y, currentdepth+1)
                
                # 返回节点
                return treenode(featrueidx=bestfi, 
                                threshold=bestthreshold, 
                                leftbranch=leftbranch, 
                                rightbranch=rightbranch, 
                                leafvalue=none)
            
            # 不纯度已经满足要求就标记为叶节点
            # 并计算叶节点的值
            else:
                leafvalue = self.calcleafvalue(y)
                return treenode(leafvalue=leafvalue)
            
    # 训练
    def fit(self, x, y):
        self.root = self.constructtree(x, y)

    # 预测单个样本的标签
    def _predict_x(self, x, treenode=none):
        if treenode is none:
            treenode = self.root

        # 若是叶节点直接返回值
        if treenode.leafvalue is not none:
            return treenode.leafvalue
        
        # 判断当前值进入左节点还是右节点
        nextbranch = none
        featruevalue = x[treenode.featrueidx]
        if featruevalue < treenode.threshold:
            nextbranch = treenode.leftbranch
        else:
            nextbranch = treenode.rightbranch
        
        # 走递归
        return self._predict_x(x, nextbranch)
    
    # 预测
    def predict(self, x):
        return [self._predict_x(x) for x in x]
    

def gini(label):
    
    probs = [label.count(lab) / len(label) for lab in set(label)]
    ginivalue = np.sum([p * (1 - p) for p in probs])

    return ginivalue


# cart分类树：实现一下binarydecisiontree中没有实现的两个方法即可
class classificationtree(binarydecisiontree):
    
    # 分类树计算不纯度的方法是算基尼系数
    def calcimpurity(self, y, y1, y2):
        p = len(y1) / len(y)
        
        return p * gini(y1) + (1 - p) * gini(y2)

    # 分类树决定叶节点的类别通过多数投票的方式
    def calcleafvalue(self, y):
        
        leafvalue = none
        mode = 0
        for yi in set(y):
            yinum= list(y).count(yi)
            if yinum > mode:
                mode = yinum
                leafvalue = yi

        return leafvalue        

# cart回归树：实现一下binarydecisiontree中没有实现的两个方法即可
class regressiontree(binarydecisiontree):

    # 回归树计算不纯度的方法是方差减少量
    def calcimpurity(self, y, y1, y2):
        p = len(y1) / len(y)

        return np.sum(np.var(y, axis=0) - (p * np.var(y1, axis=0) + (1 - p) * np.var(y2, axis=0)))

    # 回归树计算节点值的方法是节点的均值
    def calcleafvalue(self, y):
        
        return np.mean(list(y))

下面的cpp代码就不写详细的注释了，只写关键步的逻辑注释，如果需要详细注释的话，在评论区说一下。

c++

#include <iostream>
#include <eigen/dense>
#include <vector>
#include <unordered_set>

using namespace eigen;
using namespace std;

// 树节点
struct treenode
{
    double threshold;
    int featrueidx;
    treenode* leftbranch;
    treenode* rightbranch;
    double leafvalue;

    treenode() : threshold(0.0), featrueidx(0), leftbranch(nullptr), rightbranch(nullptr), leafvalue(0.0) {}
};

// 二叉决策树基类
class binarydecisiontree
{
private:
    treenode* m_root;
    int m_minsamplenum;
    int m_maxdepth;
    double m_setminimpurity;

public:
    binarydecisiontree(int minsamplenum, int maxdepth, double setminimpurity)
        : m_root(nullptr), m_minsamplenum(minsamplenum), m_maxdepth(maxdepth), m_setminimpurity(setminimpurity)
    {
    }

    // 计算不纯度
    virtual double calcimpurity(const vectorxd& y, const vectorxd& y1, const vectorxd& y2) = 0;

    // 计算叶子值
    virtual double calcleafvalue(const vectorxd& y) = 0;

    // 构造决策树
    treenode* construct(const matrixxd& x, const vectorxd& y, int currentdepth = 0)
    {
        double minimpurity = std::numeric_limits<double>::infinity();
        int bestfi = 0;
        double bestthreshold = 0.0;

        matrixxd bestleftbranch_x;
        vectorxd bestleftbranch_y;
        matrixxd bestrightbranch_x;
        vectorxd bestrightbranch_y;

        int m = x.rows();
        int n = x.cols();

        if (m > m_minsamplenum && currentdepth < m_maxdepth)
        {
            for (int fi = 0; fi < n; fi++)
            {
                vectorxd fi_values = x.col(fi);
                std::unordered_set<double> fi_values_set(fi_values.data(), fi_values.data() + fi_values.size());

                for (const double& threshold : fi_values_set)
                {
                    std::vector<int> a, b;
                    for (int idx = 0; idx < m; idx++)
                    {
                        if (fi_values[idx] < threshold)
                            a.push_back(idx);
                        else
                            b.push_back(idx);
                    }

                    if (a.size() != 0 && b.size() != 0)
                    {
                        matrixxd x_left = x(eigen::index(a.size()), eigen::all);
                        matrixxd x_right = x(eigen::index(b.size()), eigen::all);
                        vectorxd y_left = y(eigen::index(a.size()));
                        vectorxd y_right = y(eigen::index(b.size()));

                        double currentimpurity = this->calcimpurity(y, y_left, y_right);

                        if (currentimpurity < minimpurity)
                        {
                            bestfi = fi;
                            bestleftbranch_x = x_left;
                            bestleftbranch_y = y_left;
                            bestrightbranch_x = x_right;
                            bestrightbranch_y = y_right;
                            bestthreshold = threshold;

                            minimpurity = currentimpurity;
                        }
                    }
                }
            }

            if (minimpurity < m_setminimpurity)
            {
                treenode* leftbranch = construct(bestleftbranch_x, bestleftbranch_y, currentdepth + 1);
                treenode* rightbranch = construct(bestrightbranch_x, bestrightbranch_y, currentdepth + 1);

                treenode* node = new treenode();
                node->featrueidx = bestfi;
                node->threshold = bestthreshold;
                node->leftbranch = leftbranch;
                node->rightbranch = rightbranch;

                return node;
            }
            else
            {
                double leafvalue = calcleafvalue(y);
                treenode* node = new treenode();
                node->leafvalue = leafvalue;

                return node;
            }
        }

        return nullptr;
    }

    // 训练
    void fit(const matrixxd& x, const vectorxd& y)
    {
        if (m_root != nullptr)
        {
            deletetree(m_root); // 删除当前树
        }
        m_root = construct(x, y);
    }

    // 删除树的函数，辅助函数
    void deletetree(treenode* node)
    {
        if (node == nullptr)
            return;
        deletetree(node->leftbranch);
        deletetree(node->rightbranch);
        delete node;
    }

    // 预测单样本
    double predict_x(const rowvectorxd& x, const treenode* treenode = nullptr)
    {
        if (treenode == nullptr)
            treenode = m_root;

        if (treenode->leafvalue != 0.0)
            return treenode->leafvalue;

        treenode* nextnode = nullptr;
        double featurevalue = x(treenode->featrueidx);

        if (featurevalue < treenode->threshold)
            nextnode = treenode->leftbranch;
        else
            nextnode = treenode->rightbranch;

        return predict_x(x, nextnode);
    }

    // 预测全部样本
    vectorxd predict(const matrixxd& x)
    {
        vectorxd y_pred(x.rows());

        for (int i = 0; i < x.rows(); ++i)
        {
            y_pred(i) = predict_x(x.row(i));
        }

        return y_pred;
    }
};
// 计算基尼不纯度
double gini(const vectorxd& label)
{
    std::unordered_set<int> uniquelabel(label.data(), label.data() + label.size());
    
    double ginivalue = 0.0;
    for (auto const& lab : uniquelabel)
    {
        double p = double((label.array() == lab).count()) / label.size();
        ginivalue += p * (1 - p);
    }
    
    return ginivalue;
}

// 分类决策树类
class classificationtree : public binarydecisiontree
{
public:
    classificationtree(int minsamplenum, int maxdepth, double setminimpurity)
        : binarydecisiontree(minsamplenum, maxdepth, setminimpurity)
    {
    }

    // 计算分类决策树的不纯度
    double calcimpurity(const vectorxd& y, const vectorxd& y1, const vectorxd& y2) override
    {
        double p = double(y1.size()) / y.size();
        return p * gini(y1) + (1 - p) * gini(y2);
    }

    // 计算叶子值
    double calcleafvalue(const vectorxd& y) override
    {
        double leafvalue = 0.0;
        int mode = 0;
        std::unordered_set<double> unique_y(y.data(), y.data() + y.size());

        for (const auto& yi : unique_y)
        {
            int yinum = (y.array() == yi).count();
            if (yinum > mode)
            {
                mode = yinum;
                leafvalue = yi;
            }
        }
        return leafvalue;
    }
};

// 计算方差
double variance(const vectorxd& y)
{
    return (y.array() - y.mean()).array().square().sum() / y.size();
}

// 回归决策树类
class regressiontree : public binarydecisiontree
{
public:
    regressiontree(int minsamplenum, int maxdepth, double setminimpurity)
        : binarydecisiontree(minsamplenum, maxdepth, setminimpurity)
    {
    }

    // 计算回归决策树的不纯度
    double calcimpurity(const vectorxd& y, const vectorxd& y1, const vectorxd& y2) override
    {
        double p = double(y1.size()) / y.size();
        return variance(y) - (p * variance(y1) + (1 - p) * variance(y2));
    }

    // 计算叶子值
    double calcleafvalue(const vectorxd& y) override
    {
        return y.mean();
    }
};

3、总结

 
这里主要是实现了cart分类和回归树的生成和预测，决策树算法中的剪枝没有涉及，剪枝包括预剪枝和后剪枝两种方式，预剪枝训练的速度快，但容易欠拟合，后剪枝可以解决欠拟合的问题，但是训练速度上不如预剪枝。