决策树的CART算法

CART名为分类与回归树，顾名思义生成的决策树既可以用于分类，也可以用于回归，这里主要讨论分类树。

决策树的CART算法大体上的框架与ID3/C4.5相似，最大的区别在于CART生成的是一棵二叉树，而ID3/C4.5的子节点数量取决于特征取值数量。二叉的切分点依据某一特定的特征取值，按照取该值与不取该值将数据集一分为二。

由于二叉分类的特性，CART树比较适用于特征取值为二值的情况，当然也可用于多值。取多值时由于仅按照具体的某一特征取值分类，因此可能造成该特征的其他取值的浪费。这一问题可以通过保留未使用的特征取值来解决，但这里并没有这样做。

切分点的选择依赖于基尼系数（GINI）的计算，与熵类似，基尼系数可以表示某一特征取值不确定性的程度。实际计算时取基尼系数最小的某一特征取值作为该特征的最优二值切分点。

CART分类树的生成大致流程如下：

1. 终止条件判断（如当所有实例属于同一类，无更多特征，基尼指数小于规定阈值）；
2. 计算各个特征取值的基尼指数；
3. 选择基尼指数最小的特征和取值作为切分点，数据集按照是否取该特征取值二分；
4. 递归的构造是或否左右子节点。

每个节点类具有基本的如下属性：特征、特征取值、左节点、右节点。每次递归生成时需要传入当前的数据集和特征集。查询时按照验证数据的特征取值是否满足节点条件进入左右子树，直到到达叶节点。

给出完整代码如下。

from math import log2

class node:
    def __init__(self):
        #类标记或特征
        self.target = None
        #特征取值
        self.condition = None
        #左子树，取特征取值时
        self.left = None
        #右子树，不取特征取值时
        self.right = None

    def generate(self, dataSet, features, e=0):
        
        x_ranges = [set([i[j] for i in dataSet]) for j in range(len(dataSet[0]) - 1)]   #特征取值集合
        y_ranges = set([i[-1] for i in dataSet])                 #类标记取值集合

        #若所有实例属于同一类，则将该类作为类标记
        t = y_ranges
        if len(t) == 1:
            self.target = t.pop()
            return
        
        #若特征集为空，则将数据集中实例数最大的类作为类标记
        if not features:
            t_dict = {}
            for x in y_ranges:
                t_dict[x] = len([i[-1] for i in dataSet if i[-1] == x])
            t_ls = list(t_dict.items())
            t_ls.sort(key=lambda a: a[1])
            self.target = t_ls[-1][0]
            return

        #计算各特征取值的基尼系数
        gini = {}
        for f in range(len(features)):
            gini[features[f]] = {}
            for value in x_ranges[f]:
                part_y1 = len([x[f] for x in dataSet if x[f] == value]) / len(dataSet)
                part_y2 = 1 - sum([(len([x[-1] for x in dataSet if x[f] == value and x[-1] == a]) / len([x[-1] for x in dataSet if x[f] == value])) ** 2 for a in y_ranges])
                part_n1 = len([x[f] for x in dataSet if x[f] != value]) / len(dataSet)
                part_n2 = 1 - sum([(len([x[-1] for x in dataSet if x[f] != value and x[-1] == a]) / len([x[-1] for x in dataSet if x[f] != value])) ** 2 for a in y_ranges])
                gini[features[f]][value] = part_y1 * part_y2 + part_n1 * part_n2
        
        #排序找到基尼指数最小的特征和取值
        gini_list = []
        for item in gini.items():
            for i in item[1].items():
                gini_list.append((item[0],)+i)
        gini_list.sort(key=lambda a: a[-1])

        #若基尼指数小于阈值，则将数据集中实例数最大的类作为类标记
        if gini_list[0][-1] < e:
            t_dict = {}
            for x in y_ranges:
                t_dict[x] = len([i[-1] for i in dataSet if i[-1] == x])
            t_ls = list(t_dict.items())
            t_ls.sort(key=lambda a: a[1])
            self.target = t_ls[-1][0]
            return

        #递归的构造左右子节点
        self.target = gini_list[0][0]
        self.condition = gini_list[0][1]
        f_index = features.index(self.target)
        f = features[:]
        f.remove(self.target)
        d = [x[:] for x in dataSet if x[f_index] == self.condition]
        for j in range(len(d)):
            d[j].pop(f_index)
        self.left = node()
        self.left.generate(d,f,e)
        d = [x[:] for x in dataSet if x[f_index] != self.condition]
        for j in range(len(d)):
            d[j].pop(f_index)
        self.right = node()
        self.right.generate(d,f,e)


    def query(self, term):
        #判断是否查询到叶节点
        if not self.condition:
            result = self.target
            return result
        else:
            if term[self.target] == self.condition:
                result = self.left.query(term)
                return result
            else:
                result = self.right.query(term)
                return result


if __name__ == "__main__":
    features = ['年龄','有工作','有自己的房子','信贷情况']        #特征集
    train_data = [['青年','否','否','一般','否'],                #训练数据集
                ['青年','否','否','好','否'],
                ['青年','是','否','好','是'],
                ['青年','是','是','一般','是'],
                ['青年','否','否','一般','否'],
                ['中年','否','否','一般','否'],
                ['中年','否','否','好','否'],
                ['中年','是','是','好','是'],
                ['中年','否','是','非常好','是'],
                ['中年','否','是','非常好','是'],
                ['老年','否','是','非常好','是'],
                ['老年','否','是','好','是'],
                ['老年','是','否','好','是'],
                ['老年','是','否','非常好','是'],
                ['老年','否','否','一般','否']]

    n = node()
    n.generate(train_data,features,e=0)

    z = {'有自己的房子':'是','有工作':'否','年龄':'青年','信贷情况':'一般'}
    print(n.query(z))