什么是CART算法？怎么对CART进行建树？怎么对CART进行减枝叶？CART Python实现代码

一.什么是决策树？

首先来看一个图，这是根据西瓜的属性来判断西瓜的好坏。其中纹理，触感，色泽等就是特征属性，每一个叶节点表示是否是好瓜。

决策树是一种基本的分类与回归方法。决策树的生成算法主要有ID3,C4.5和CART等。决策树是一种树形结构，每一个内部的节点代表的是样本特征属性上的判断，每一个分支是根据判断后划分成两部分的结果，叶节点表示一个类。

`

二.什么是CART树

CART是分类与回归树（classification and regression tree, CART）的简称。它与ID3,C4.5的区别是，ID3决策树可以有多个分支，但是不能处理特征值为连续的情况，C4.5中是用信息增益比率(gain ratio)来作为选择分支的准则，存在过拟合的情况。CART树既可以用来回归，又可以用来分类。注意决策树是一颗二叉树。
分类：如晴天/阴天/雨天、用户性别、邮件是否是垃圾邮件；
回归：预测实数值，如明天的温度、用户的年龄等；

三.基尼指数

CART根据信息增益最大化准则，来完成递归地构建二叉树的过程。
$$Gini(D)=\sum _{k=1}^k{p}_k(1-p_k)=1-\sum _{k=1}^k{p}_k^2$$
如果样本集给定的话，其基尼指数为：
$$Gini(D)=1-\sum _{k=1}^k{\left(\frac{|C_k|}{|D|}\right)}^2$$
在这里K表示的是类别个数，D表示的是样本集的个数，Ck表示的是类别K中的样本数。

#基尼系数的计算公式
def Gini_Function( dataset):
	#判断数据集是否为空
	Length = len(dataset)
	if Length == 0:
		return 0
	#统计样本中个数
	Class_number = Class_count(dataset)
	sum_p = 0.0
	#有两个样本。所以循环两次,对应公式上面的求和
	for i in range(2):
		sum_p =sum_p + (Class_number[i] / Length) * (Class_number[i] / Length)    
	return 1 - sum_p

四.基尼指数在这里为什么Gini(D)系数越小，样本纯度越高？

这里这样来理解，如果这里样本中只有两个类别，分别是瓜甜，瓜酸。

在这里随机抽取两个瓜。（c1 = 瓜甜，c2 = 瓜酸），
$$\begin{array}{l}p(c_1)=\frac{10}{30}=\frac{1}{3}\\ \\ p(c_2)=\frac{20}{30}=\frac{2}{3}\end{array}$$
在这里p(c1)*p(c2)可以理解为，抽到两个样本不同的概率为多少，在这里是 2/9。

如果样本个数为：

对应的概率为：
$$\begin{array}{l}p(c_1)=\frac{5}{30}=\frac{1}{6}\\ \\ p(c_2)=\frac{25}{30}=\frac{5}{6}\end{array}$$
在这里两个概率的乘积为 5/36 。 很明显 5/36 < 2/9，对应的样本纯度是第二次的样本纯度明显优于第一次。希望可以帮助你理解。
下面袋面就是找最佳划分点和对应的特征值:

	for value in uniqueColSet:
	        #划分数据集，dataSet是该父节点的数据，leftDataSet, rightDataSet是划分过后的左节点，右节点的数据
			leftDataSet, rightDataSet = SplitDataSet(dataSet, value,i)
			#获取左节点，右节点的样本数
			prop_l = len(leftDataSet)/rowLength
			prop_r = len(rightDataSet)/rowLength
			#算取基尼系数的增益率，增益率越大则划分后的样本纯度越高
			gain1 = Gain - prop_l*Gini_Function(leftDataSet) - prop_r*Gini_Function(rightDataSet)
			if gain1 > bestGain:    #如果增益比比当前的大，更换
				bestGain = gain1
				bestValue = (value, i)   #保存最优划分点和对应的列数

五.什么是剪枝？

就是按照字面意思，把树的一部分枝叶减去，就叫剪枝。

六.为什么需要剪枝叶？

我们首先来看一下代码是怎么判断到叶节点了。这里只是一种判断方法(大佬，务喷)。

gain1 = Gain - prop_l*Gini_Function(leftDataSet) - prop_r*Gini_Function(rightDataSet)
			if gain1 > bestGain:    #如果增益比比当前的大，更换
				bestGain = gain1
				bestValue = (value, i)   #保存最优划分点和对应的列数

	if 	dataSet is not None:        
		if bestGain > 0.00:
				#继续判断是否每个叶节点的类别是一致的
			DataSet = SplitDataSet(dataSet,bestValue[0],bestValue[1])  #根据最优划分点进行划分为左子树，右子树
			node.rightnum = len(DataSet[1])
			node.leftnum = len(DataSet[0])
			node.value = bestValue[0]
			node.bestcol = bestValue[1]           #保存节点对应的最优划分点
			node.left = buildDecisionTree(DataSet[0],list1)
			node.right = buildDecisionTree(DataSet[1],list3)
			return node
		else:
			result = Class_count(dataSet)
			if result[0] > result[1] :
				node.class_n = 0
			else:
				node.class_n = 1
			return node

如果我们把bestGain > 0 就认为没有到达叶节点，那么就只有bestGain = 0 的时候，我们才能认为他已经到叶节点了。那么bestGain == 0的代表的什么了？

先来看看在样本类别，个数已知的情况下， 计算基尼系数的公式：
$$Gini(D)=1-\sum _{k=1}^k{\left(\frac{|C_k|}{|D|}\right)}^2$$
在这里假设只有一个类别：C1, D是此时的样本数，你会发现C1 的个数与D相等。

带进公式你会发现Gini = 0，那么不管根据那个特征继续划分下去，左右节点都只有一个类别，对应的Gini都等于0.
就是叶节点只有一个类别了（此时：Gini_Function(dataSet) = 0），这里就会造成过拟合，通俗理解，就是你分的太仔细了，如果稍微有点偏差，你就会分类错误。泛化性太差（对于测试集的准确率较低），所以为了提高准确率，需要减去一部分节点。

七. 如何去剪枝

我们都知道减枝的方式共有两种，预剪枝，和后剪枝。

一. 预剪枝:

就是一边建树，一边剪枝。比如说如下图。当在根节点的时候，根据增益最大，选择了脐带这个特征进行划分。在划分之前，先把脐带当做一个叶节点（意思是这棵树就只有一个节点），然后把测试集代入，看正确率是多少。然后划分到色泽，坏瓜，根蒂第二层，依次把这三个节点当做叶节点，把测试集带进去测试，看正确率是否提高了，提高了则划分，反之不划分。

二. 后剪枝

等树建好了，从叶节点依次往上面剪枝。其实思路很简单，就是把叶节点上面的父节点减掉（前提是：父节点的两个子节点都是叶节点），比如说在这里把节点6的两个子节点减掉，测试集的正确率提高了，则剪枝，然后把样本中类别数多的一类归为该叶节点的类别。


剪枝代码，代码有详细注释：

#后期减树
def postProcessing(tree ,minalpha):
	# 如果左节点不为空，继续探查左节点
	if tree.right.bestcol is not None:
		postProcessing(tree.right ,minalpha)
	# 如果右节点不为空，继续探查右节点
	if tree.left.bestcol is not None:
		postProcessing(tree.left ,minalpha)
    # 如果两个节点都为空，则到了也节点
	if tree.right.bestcol is None and tree.left.bestcol is None:
		#计算左子，右子叶节点的样本数
		col_left = len( tree.left.dataSet)
		col_right = len( tree.right.dataSet)
		#父子节点的样本数
		col_1 = col_left+col_right
		#算基尼系数
		best_gain = Gini_Function( tree.dataSet)  #父节点的基尼系数
		best_gain_right = Gini_Function( tree.right.dataSet) #父节点的右子基尼系数
		best_gain_left = Gini_Function( tree.left.dataSet) #父节点的左子基尼系数
		best_gain_increase = best_gain - (col_left/col_1)*best_gain_left - (col_right/col_1)*best_gain_right
		#算基尼增益，best_gain_increase小于了minalpha，则剪枝叶
		if minalpha > best_gain_increase: 
			tree.bestcol =None
			#把该节点归为类别数多的类别
			#result返回的类别的个数
			result = Class_count(tree.dataSet)
			if result[0] > result[1] :
				tree.class_n = 0
			else:
				tree.class_n = 1
			#减枝叶
			tree.right = None
			tree.left = None

八. 后剪枝是根据什么来剪枝的？

与回归一样，CART函数也有自己的损失函数:
$$C_a\left(T\right)=C\left(T\right)+a|T|$$
其中C(T) =
$$C\left(T\right)=\sum _{t=1}^{|T|}{N}_t{H}_t\left(T\right)$$
Ca(T)是参数是a时的整体树的损失，C(T）是训练数据的预测误差（如：基尼指数），|T|为叶节点的个数。
t是树的叶节点，Nt表示该叶节点的样本数量，Ht（T）表示结点t上的经验熵，所以右边第一项相当于对决策树的所有叶节点求熵，并以每个叶节点包含的样本数量为权重。又因为熵的含义为随机变量不确定性的度量，所以右边第一项的计算意义为模型对训练集的预测误差。
那么右边第二项又是什么含义，T表示树的叶节点个数，即表示树的复杂度，a为参数，相当于a越大，叶节点的个数对损失函数的影响越大，剪枝之后的决策树更容易选择复杂度较小的树，a越小，表示叶节点的个数对损失函数的影响越小，所以a的大小控制了预测误差与树的复杂度对剪枝的影响
所以当a确定时，损失函数最小的子树越大，表明与训练数据的拟合越好，但是树也越复杂，子树越小，与训练数据的拟合越差，但树的复杂度较小，避免了过拟合，提高决策树的一般性，损失函数正好表示了对两者的平衡。

九. 分类对于连续值怎么处理？

给定样本集的某一个特征D和连续值a，假设在D中有n个不同的取值，将这些值从大到小排列。
$$D=\left\{a^1,a^2,a^3,.....,a^n\right\}$$
划分点为：
$$T_a=\left\{\frac{a_i+a_{i+1}}{2}|1<i<n\right\}$$
假设现在的划分点是Ta ,则把样本点中这个特征中的特征值小于Ta的样本集划分给左子树，然后大于Ta的样本集划分给右子树。然后算其增益率，如果大于之前的最大增益率，则更换，反之不更换，然后进入下一个划分点继续计算,最终找到最优划分点。

举一个列子好理解,看下图样本集的某一个特征：

排序之后：

算其

$$T_a=\left\{\frac{1900+1903}{2}\right\}$$
可以把D划分为：

然后算其增益率。

继续算：
$$T_a=\left\{\frac{1903+1960}{2}\right\}$$
可以把D划分为：

然后在算其增益率。
把所有的划分点寻找完，保留最大的增益率，既保存最佳划分点。然后进入下一个特征继续计算。

十，测试结果

训练集：
部分训练集：

这个训练集共有两个类别，分别是0,1。共有八个属性。

实验结果：
父节点显示的是对于那个特征进行的划分，比如根节点是对应特征7 进行的划分。叶节点显示的该节点的类别。minalphy对应的是剪枝的阈值。
没有剪枝前：


剪枝后：

十一. 代码

import pandas as pd 
import numpy as np
import operator as op
import sys 
import turtle
########画二叉树#########
def draw_tree(root) -> None:

	def jump_to(x, y):
		t.penup()
		t.goto(x, y)
		t.pendown()

	def draw(node, x, y, dx):
		if node:
			t.goto(x, y)
			jump_to(x, y - 20)
			if node.left == None and node.right == None:
				best_num = {
   node.class_n}
			else:
				best_num = node.bestcol

			t.write(best_num , align="center")
			draw(node.left, x - dx, y - 60, dx / 2)
			jump_to(x, y - 20)
			draw(node.right, x + dx, y - 60, dx / 2)

	t = turtle.Turtle()
	t.speed(0)
	turtle.delay(0)
	h = 8
	jump_to(0, 30 * h)
	draw(root, 0, 30 * h, 50 * h)
	t.hideturtle()
	turtle.mainloop()

class Node(object):
 	"""docstring for ClassName"""
 	def __init__(self, gain=None):
 		self.Gain = None
 		self.value = None
 		self.bestcol = None
 		self.right = None
 		self.left = None
 		self.Gain = None
 		self.dataSet = None
 		self.cutting_dim = None
 		self.class_n = None
 		self.best = None
 		self.leftnum = None
 		self.rightnum = None
 		self.nownum = None

############类别个数的计算########
####在这个训练集中只有两个类别： 0,1
def Class_count(dataSet):
	result = [0,0]
	for i in range(len(dataSet)):
		if dataSet[i][0] == 0.0:
			result[0] = result[0]+1
		if dataSet[i][0] == 1.0:
			result[1] = result[1]+1
	return result


#########根据标签进行分类######3
#########DataSet数据集########
#########value划分区间的值####
#########columu 对应的列值####
def SplitDataSet(DataSet, Value, column):
	leftList = []
	rightList = []
	for RowData in DataSet:
		if RowData[column] >= Value:
			rightList.append(RowData)
		else:
			leftList.append(RowData)
	return leftList,rightList

def Gini_Function( dataset):
	Length = len(dataset)
	if Length == 0:
		return 0
	Class_number = Class_count(dataset)
	imp = 0.0
	for i in range(2):
		imp =imp + (Class_number[i] / Length) * (Class_number[i] / Length)     # gini = 1 - 求和（p）
	return 1 - imp

#########建树##########
#####dataSet:输入数据集
#####list1:储存已经划分了的特征
def buildDecisionTree(dataSet, list1):
	Gain = Gini_Function( dataSet)
	bestGain = 0.0
	bestValue = None
	bestSet = None    #最开始把这三个值为空
	columnLength = len(dataSet[0])  #求得样本的特征个数
	rowLength = len(dataSet)   #测得样本的大小
	#用for循环的原因是为了排除已用特征
	for i in range(1,columnLength):
		k = 0
		for j in range(0,len(list1)):
			if i == list1[j]:
				k = 1
				break
		#若该特征没有进行划分，则其判断是否为最佳划分特征
		if k == 0:
			colSet = [example[i] for example in dataSet]
			uniqueColSet = set(colSet)
			data9 = list(uniqueColSet)
			data9.sort()
			for value in uniqueColSet:
				leftDataSet, rightDataSet = SplitDataSet(dataSet, value,i)
				prop_l = len(leftDataSet)/rowLength
				prop_r = len(rightDataSet)/rowLength
				gain1 = Gain - prop_l*Gini_Function(leftDataSet) - prop_r*Gini_Function(rightDataSet)
				if gain1 > bestGain:
					bestGain = gain1
					bestValue = (value, i)   #保存最优划分点和对应的列数
	#print(list1) 
	if bestValue is not None:
		list1.append(bestValue[1])
	list2 = []
	for i in range(len(list1)): 
		list2.append(list1[i])
	list3 = []
	for i in range(len(list2)): 
		list3.append(list2[i])
	node = Node()
	node.nownum = len(dataSet)
	node.best =  bestGain
	node.dataSet = dataSet
	if 	dataSet is not None:        
		if bestGain > 0.00:
				#继续判断是否每个叶节点的类别是一致的
			DataSet = SplitDataSet(dataSet,bestValue[0],bestValue[1])  #根据最优划分点进行划分为左子树，右子树
			node.rightnum = len(DataSet[1])
			node.leftnum = len(DataSet[0])
			node.value = bestValue[0]
			node.bestcol = bestValue[1]           #保存节点对应的最优划分点
			node.left = buildDecisionTree(DataSet[0],list1)
			node.right = buildDecisionTree(DataSet[1],list3)
			return node
		else:
			result = Class_count(dataSet)
			if result[0] > result[1] :
				node.class_n = 0
			else:
				node.class_n = 1
			return node
#把叶节点的路径打印出来
def SearchDecisionTree( node, testSet):
	if node.bestcol != None:
		if testSet[node.bestcol] < node.value:
			if node.left is not None:
				if node.left.bestcol is not None:
					classAtrribute = SearchDecisionTree( node.left,testSet)
					return classAtrribute
				else:
					return node.left.class_n

		else:
			if node.right is not None:
				if node.right.bestcol is not None:
						classAtrribute = SearchDecisionTree( node.right,testSet)
						return classAtrribute
				else:
					return node.right.class_n
	return node.class_n


################交叉验证##### 
def Change_number( dataSet):
    trainList = []
    testList = []
    for i in range(len(dataSet)):
        if i % 10 == 1:
            testList.append(dataSet[i])
            
        else:
            trainList.append(dataSet[i])
    return testList,trainList

def traversingTwoTree( node):

	#print("节点数据行数为：",len(node.dataSet))
	

	if node.right is not None:
		#print("左子节点：")
		traversingTwoTree( node.right)
	if node.left is not None:
		#print("右子节点：")
		traversingTwoTree( node.left)
	#if node.right is None and node.left is None:
		#print("到达叶子节点")


#后期减树
def postProcessing(tree ,minalpha):
	# 如果左节点不为空，继续探查左节点
	if tree.right.bestcol is not None:
		postProcessing(tree.right ,minalpha)
	# 如果右节点不为空，继续探查右节点
	if tree.left.bestcol is not None:
		postProcessing(tree.left ,minalpha)
    # 如果两个节点都为空，则到了也节点
	if tree.right.bestcol is None and tree.left.bestcol is None:
		#计算左子，右子叶节点的样本数
		col_left = len( tree.left.dataSet)
		col_right = len( tree.right.dataSet)
		#父子节点的样本数
		col_1 = col_left+col_right
		#算基尼系数
		best_gain = Gini_Function( tree.dataSet)  #父节点的基尼系数
		best_gain_right = Gini_Function( tree.right.dataSet) #父节点的右子基尼系数
		best_gain_left = Gini_Function( tree.left.dataSet) #父节点的左子基尼系数
		best_gain_increase = best_gain - (col_left/col_1)*best_gain_left - (col_right/col_1)*best_gain_right
		#算基尼增益，best_gain_increase小于了minalpha，则剪枝叶
		if minalpha > best_gain_increase: 
			tree.bestcol =None
			#把该节点归为类别数多的类别
			result = Class_count(tree.dataSet)
			if result[0] > result[1] :
				tree.class_n = 0
			else:
			#减树
				tree.class_n = 1
			tree.right = None
			tree.left = None
if __name__ == '__main__':  
	list1 = []    #注意Python链表的使用 
	correct_num = 0
	minalpha = 0.0
	df = pd.read_excel('D:\研究生资料\模式识别\第4章作业\第4章作业\data1.xlsx')
	data = df.values
	data3 = data.tolist()
	dataSet = Change_number(data3)

	testSet = dataSet[0]

	node = buildDecisionTree(dataSet[1],list1)
	postProcessing(node ,minalpha)
	for i in range(len(testSet)):
		data=SearchDecisionTree(node,testSet[i])
		if data == testSet[i][0]:
			correct_num = correct_num + 1
	print("当minalpha:",minalpha," 测试集正确率为",correct_num / len(testSet))
	minalpha = 0.3
	correct_num = 0
	postProcessing(node ,minalpha)
	for i in range(len(testSet)):
		data=SearchDecisionTree(node,testSet[i])
		if data == testSet[i][0]:
			correct_num = correct_num + 1
	print("当minalpha:",minalpha," 测试集正确率为",correct_num / len(testSet))
	draw_tree(node)