决策树之CART分类树

CART分类树的算法理解和代码实现，真亲自手算带你理解算法。

冰淇淋加点糖

5113人浏览 · 2022-11-25 19:26:45

冰淇淋加点糖 · 2022-11-25 19:26:45 发布

一、基尼系数

基尼系数（Gini）是一种不等性的度量，经济学上用基尼系数度量收入不平衡的情况，在机器学习中，基尼系数可以用于度量信息的不纯度。基尼系数是一个介于0~1之间的值。计算公式为：

$Gini(D)=1-\sum_{i=1}^{m}p_{i}^{2}$

上式中，D表示训练集，pi为训练集中划分的类别Ci在D中的概率，m为不同属性的取值个数。基尼系数考虑的是每个属性的二元划分。

（1）离散型属性

设A为离散型属性，包含v个不同的取值，根据集合的概念，则对于离散型属性A则有2^v个子集，但是对于空集和全集是不具备划分意义的，所以对于离散型属性A的二元划分有2^v-2种划分方法。当考虑二元划分时，计算每个结果分区的不纯度加权和。例如，离散型属性A的二元划分将D划分为D1,D2。则给定该划分，D的基尼系数为：

$Gini_{A}(D)=\frac{\left | D_{1} \right |}{\left | D \right |}Gini(D_{1})+\frac{\left | D_{2} \right |}{\left | D \right |}Gini(D_{2})$

选择基尼系数最小即信息纯度最高的作为划分依据。

（2）连续型属性

对于连续型属性，有一种有效的计算方法，操作步骤如下：

①将属性在值上进行升序排序。

②线性扫描这些属性值，然后实时更新计数矩阵和对应的Gini指标值。

③选择具有最小Gini指标的划分位置。

二、cart算法的步骤

（1）设节点的训练集为D，计算现有的特征属性对该数据集的基尼系数。根据特征属性A的取值，将训练集划分为两类。例如根据特征属性A=a将训练集划分为A=a和A≠a两类，记为D1、D2，计算这两部分的基尼系数以及属性A的基尼系数。

（2）在所有可能的属性A以及它们所有可能的切分点a中，选择基尼系数最小的特征属性及其对应的切分点作为最优特征属性与最优切分点。根据最优特征和最优切分点，从当前结点生成两个子节点，将训练集依据特征属性分配到两个子节点中。

（3）对两个子节点递归调用步骤（1）和步骤（2），直到满足停止条件为止。（停止计算条件：没有更多的特征属性或结点中的样本个数小于预定阈值或训练集中的基尼系数小于预定阈值）

（4）生成决策树。

三、举个栗子

买电脑案例数据如下图

计算过程如下图：

四、代码实现过程

import numpy as np
from sklearn import tree
from sklearn.tree import DecisionTreeClassifier
import graphviz

def load_data():
     dataSet = [['<=30', 'high', 'no', 'fair', 'no'],
                ['<=30', 'high', 'no', 'excellent', 'no'],
                ['31…40', 'high', 'no', 'fair', 'yes'],
                ['>40', 'medium', 'no', 'fair', 'yes'],
                ['>40', 'low', 'yes', 'fair', 'yes'],
                ['>40', 'low', 'yes', 'excellent', 'no'],
                ['31…40', 'low', 'yes', 'excellent', 'yes'],
                ['<=30', 'medium', 'no', 'fair', 'no'],
                ['<=30', 'low', 'yes', 'fair', 'yes'],
                ['>40', 'medium', 'yes', 'fair', 'yes'],
                ['<=30', 'medium', 'yes', 'excellent', 'yes'],
                ['31…40', 'medium', 'no', 'excellent', 'yes'],
                ['31…40', 'high', 'yes', 'fair', 'yes'],
                ['>40', 'medium', 'no', 'excellent', 'no']
                ]
     lable = [data[-1] for data in dataSet]  # 标签属性->分类结果
    # 除去标签列的其余数据
     data_cindex = len(dataSet[0])-1  #除去标签的数据属性个数
     new_data_set = [] #除去标签属性的数据集，每一行数据表示原来数据每一列的属性值
     for i in range(data_cindex):
        shuxing = [] #存放每一个属性的值
        for data in  dataSet:
            shuxing.append(data[i])
        new_data_set.append(shuxing)
     return new_data_set,lable,dataSet
# 标签转换函数
def transform_lable(lable):
    lable_set = list(set(lable))
    lable_set.sort()
    print(lable_set)
    new_lable = []
    for liebei in lable:
        for i in range(len(list(lable_set))):
            if liebei == list(lable_set)[i]:
                new_lable.append(int(liebei.replace(liebei, str(i))))
    return new_lable

# 数据集转换函数
def transform_data(data, data_cindex):
    new_data = []
    temp = []
    for i in range(data_cindex):
        lable_set = list(set(data[i]))
        lable_set.sort()
        new_lable = []
        for liebei in data[i]:  # 循环每一行除去标签的数据集
            for i in range(len(list(lable_set))):
                if liebei == list(lable_set)[i]:
                    new_lable.append(int(liebei.replace(liebei, str(i))))
        temp.append(new_lable)
        print(lable_set)
    for j in range(len(temp[0])):  # 字列表的长度
        lie = []
        for i in range(len(temp)):  # 子列表的个数
            lie.append(temp[i][j])
        new_data.append(lie)
    return new_data
# 数据导入
new_data_set, lable, dataSet = load_data()
# 除去标签的数据属性个数  # 除去标签的数据属性个数
data_cindex = len(dataSet[0]) - 1
# 标签
final_lable = np.array(transform_lable(lable))
print(final_lable)
# 数据
final_data = transform_data(new_data_set, data_cindex)
print(final_data)
clf = DecisionTreeClassifier(criterion="gini")
clf.fit(final_data,final_lable)
# pre = clf.predict([[2,1,1,0]])
# print(pre)
dot_data = tree.export_graphviz(clf, out_file=None)  # 导出决策树
graph = graphviz.Source(dot_data)                    # 创建图形
graph.render('111')

运行结果解释：

['no', 'yes']
0为no，1为yes
[0 0 1 1 1 0 1 0 1 1 1 1 1 0]

下面集合中的为序对应的数字是0 1 2
['31…40', '<=30', '>40']
['high', 'low', 'medium']
['no', 'yes']
['excellent', 'fair']

将文字转化为离散的数字，sklearn不支持字符串形式的数据
[[1, 0, 0, 1], [1, 0, 0, 0], [0, 0, 0, 1], [2, 2, 0, 1], [2, 1, 1, 1], [2, 1, 1, 0], [0, 1, 1, 0], [1, 2, 0, 1], [1, 1, 1, 1], [2, 2, 1, 1], [1, 2, 1, 0], [0, 2, 0, 0], [0, 0, 1, 1], [2, 2, 0, 0]]

决策树图形如下：