CART算法
CART 是一种广泛应用的决策树学习方法。它同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。分类树与回归树的区别在样本的输出，如果样本输出是离散值，这是分类树；样本输出是连续值，这是回归树分类树的输出是样本的类别，回归树的输出是一个实数。
在CART算法中，假设决策树是一个二叉树，内部结点特征的取值为 “是” 和 “否” 。左分支取值为"是" ,右分支取值为 “否”。
CART算法由以下两步组成:
1 决策树生成:基于训练数据生成决策树，生成的这棵决策树要尽可能大
2 决策树剪枝: 用验证数据集对已生成的树进行剪枝并选择最优子树(以损失函数最小作为剪枝标准)
CART 回归树的生成
回归树用平方误差最小化准则，进行特征选择，生成二叉树
一棵回归树将输入空间划分为多个单元，假设有M个单元 R1,R2,…,RM ,并且每个单元对应一个输出值Cm
回归树模型可以表示为
这个公式的含义是这样的
若有一个样本点(xi,yi) 属于单元R1 那么 f(xi)=c1 其实就是输出了在决策树中该样本点的类别
设x1,x2,…xn 代表单个样本的n个属性,y表示所属类别，CART算法通过递归的方式将n维的空间划分为不重叠的矩阵,划分步骤如下:
(1) 选一个自变量xi,再选取xi的一个值vi ，vi 把n维空间划分为两部分,一部分的点在xi上的取值a都满足a<=vi ，另一部分的所有点在xi上的取值a满足a > vi
(2) 递归处理,将上面得到的两部分 按步骤(1) 重新选取一个属性进行划分,直到把整个n维空间划分完
如何选取特征xi以及vi来划分特征空间?
在选择特征时，采用启发式算法，选择第j个特征的某个取值s作为一个切点值 将数据集进行划分为两部分。
对 j,s 的选择就要用到下面的公式啦
其中
(为什么 c1 ,c2这样表示，在下面会解释)
首先遍历所有的特征 ，对于一个特征 j 将它的所有取值依次 作为R1，R2 的切分点，计算上述公式，从而找到最佳的 j，s 划分出两个区域，之后对所有的区域重复上述步骤 直到满足停止条件，就生成了一棵回归树啦
当划分好输入空间后，可以使用平方误差
表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。 （ 别忘了 f(xi)=cm )
对平方误差求导
在单个单元中，最优的f(xi)为单元内所有数据对应y值的平均值。
CART回归树具体生成步骤如下：
Step1：获得训练数据集，根据数据集第一个特征的第一个分量将数据集分为大于该分量和小于该分量的两个数据集R1和R2，其中 R1={x|Rj≤s},R2={x|Rj>s}。
Step2：根据两个数据集对应y值的平均获得c1和c2，分别计算两个数据集的平均绝对误差（其实就是各个数据集y值的总均方差。
Step3：重复Step1~2，遍历整个数据集的所有特征所有分量，获得均方误差值的矩阵。
Step4：根据矩阵寻找均方误差最小的分割方案，将该分割点作为树的节点，将分割后的数据集分别赋值给该节点左子树和右子树。
Step5：重复步骤1~4，递归地将数据集分割为更小的部分，直到总均方差的下降值小于某阈值或者数据集中只剩下一类数据为止(停止条件)。
CART 分类树的生成
分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。
基尼指数（基尼不纯度）：表示在样本集合中一个随机选中的样本被分错的概率。
注意： Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。
基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率
下面给出基尼指数的正式定义
如果将数据集D按某一特征A 是否取一可能值a 分为 D1 和 D2 两部分
设当A=a时,数据(xi,yi) 属于D1 当 A不等于a时 数据(xi,yi) 属于D2
则在特征 A 的条件下，集合 D 的基尼指数定义为
基尼指数 Gini(D) 表示集合 D 的不确定性，基尼指数值越大，样本集合的不确定性也就越大。
CART分类树的生成算法
输入: 训练数据集 D， 停止计算的条件
输出 : CART 决策树。
根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树:
(1)设结点的训练数据集为 D， 计算现有特征对该数据集的基尼指数。此时,对每一个特征 A， 对其可能取的每个值 α，根据样本点对 A= α 的测试为"是"或"否" 将 D 分割成 Dl 和 D2 两部分，利用式 
计算 A= α 时的基尼指数。
(2) 在所有可能的特征 A 以及它们所有可能的切分点 α 中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
(3) 对两个子结点递归地调用(1)， (2) ，直至满足停止条件。
(4) 生成 CART 决策树。
算法的停止条件 （满足3者之一即可)
1结点中的样本个数小于预定阈值
2样本集的基尼指数小于预定阈值(样本基本属于同一类)
3 没有更多特征
举个例子,在前文贷款数据上,建立一棵CART 分类树
| ID | 年龄 | 有工作 | 有自己的房子 | 信贷情况 | 类别 |
|---|---|---|---|---|---|
| 1 | 青年 | 否 | 否 | 一般 | 否 |
| 2 | 青年 | 否 | 否 | 好 | 否 |
| 3 | 青年 | 是 | 否 | 好 | 是 |
| 4 | 青年 | 是 | 是 | 一般 | 是 |
| 5 | 青年 | 否 | 否 | 一般 | 否 |
| 6 | 中年 | 否 | 否 | 一般 | 否 |
| 7 | 中年 | 否 | 否 | 好 | 否 |
| 8 | 中年 | 是 | 是 | 好 | 是 |
| 9 | 中年 | 否 | 是 | 非常好 | 是 |
| 10 | 中年 | 否 | 是 | 非常好 | 是 |
| 11 | 老年 | 否 | 是 | 非常好 | 是 |
| 12 | 老年 | 否 | 是 | 好 | 是 |
| 13 | 老年 | 是 | 否 | 好 | 是 |
| 14 | 老年 | 是 | 否 | 非常好 | 是 |
| 15 | 老年 | 否 | 否 | 一般 | 否 |
Gini(D,有房子) = 0.27 最小，所以选择特征 有自己的房子为最优特征，
之后根据类似I的过程可以生成一棵决策树
CART剪枝
设CART 生成算法生成的决策树是T0
CART 剪枝算法由两步组成:
1 从T0的叶结点开始不断进行剪枝形成一个决策树子树序列{T0, T1,…Tn}
2 通过交叉验证法在独立的验证数据集上对每棵子树进行测试选出最优子树
·下面介绍在CART算法中广泛使用的一种剪枝算法-代价复杂性剪枝法CCP(Cost Complexity Pruning)
对于分类回归树中的每一个非叶子节点计算它的表面误差率增益值α。
|NT|是子树中包含的叶子结点个数;
R(t) 是结点t的误差代价，R(t)=r(t)∗p(t)
r(t)是结点t的误差率，如果该结点被剪枝（把该结点当作一个叶子结点); 比如结点t的数据可分为两类 A 50 B 10 根据将一个结点分类为多数数据所在的类 则结点所有数据将被分为A类 也就是B类数据被误分 B类占结点数据的10/60 所以误差率r(t) 就是10/60
p(t)是结点t上的数据占所有数据的比例。
R(Tt) 是子树Tt的误差代价，如果该结点不被剪枝。它等于子树Tt上所有叶子结点的误差代价之和
1举个例子
已知所有的数据总共有60条，则结点t4的节点误差代价为：
子树误差代价为：
以t4为根节点的子树上叶子结点有3个
根据以上运算规则 我们每一轮都计算所有内部结点的a值 并选择a最小的进行剪枝
（直到没有内部结点可供剪枝了为止) 进而形成一个子树序列 T0 ，T1 , T2… Tn 其中对Ti剪枝形成了Ti+1
CART的·Python实现
结点
class Node:
def __init__(self,data,left,right,feature,split,value):
self.data=data#这个结点包含的数据
self.left=left #左孩子
self.right=right #右孩子
self.feature=feature #这个结点是用哪个特征进行划分的
self.split=split # 这个结点的划分点值是多少
self.value=value #这个结点属于哪一类 只有叶子结点才有值
CART算法
class CART:
def __init__(self,Train,features,label,tree_type,feature_name):
self.Train=Train #训练集
self.features=features #特征
self.label=label #标签
if tree_type=="c":
self.root=self.create_classification_tree(Train)
else:
self.root=self.create_regression_tree(Train)
self.feature_name=feature_name
self.roots=[] #存放子树序列
#self.roots.append(self.root)#首先将树的初始形式放入roots中
self.a=sys.maxsize
self.minnode=None
def is_one_class(self, data, label): # 判断data中的数据是否属于同一类 并返回类数组
X = data[:, label:label + 1]
labels = []
for i in range(X.shape[0]):
if X[i][0] not in labels:
labels.append(X[i][0])
if len(labels) == 1:
return True
else:
return False
def cost(self,data):
X=data[:,self.label:self.label+1]
X=X.astype(int)
avg = np.sum(X)/X.shape[0] #平均值
sum = 0
for i in range(X.shape[0]):
sum+= (X[i][0]-avg)**2
return sum
def create_regression_tree(self,data): #生成一棵回归树
node=None
min_cost=sys.maxsize
min_feature=0
min_split=0
min_left=None
min_right=None
if self.is_one_class(data, self.label): # 如果数据都属于一类
node = Node(data, None,None, self.label, 0 ,self.max_num_class(data, self.label)) # 叶子结点
elif len(self.features) == 0: # 没有可供划分的特征了
node = Node(data, None, None, self.label, 0, self.max_num_class(data, self.label)) # 叶子结点
else:
for i in self.features: #遍历所有特征取值
d=data[np.argsort(data[:, i])] #以这个特征的大小来进行排序
for j in range(d.shape[0]-1):#以特征j的每一个取值来分割成两个区域
left = d[0:j+1, :]
right=d[j+1:, ]
left_cost=self.cost(left)
right_cost=self.cost(right)
if left_cost+right_cost < min_cost:
min_cost=left_cost+right_cost
min_feature=i
min_split=d[j][i]
min_left=left
min_right=right
self.features.remove(min_feature)
left_node= self.create_regression_tree(min_left)
right_node = self.create_regression_tree(min_right)
node= Node(data, left_node,right_node, min_feature, min_split ,0)
return node
def class_num(self, data, feature): # 对于某个特征而言 他有多少种取值
X = data[: ,feature:feature + 1]
fea_values = {}
for i in range(X.shape[0]):
# print(X[i])
if X[i][0] not in fea_values:
fea_values[X[i][0]] = 1
else:
fea_values[X[i][0]] += 1
return fea_values
def cal_gini(self,data):#计算一个数据的基尼指数
label=self.class_num(data,self.label)#求每个类有多少条数据
gini=0
for k,v in label.items():
p=v/data.shape[0]
gini+=p*(1-p)
return gini
def basefeature_cal_gini(self,data,feature): #求某一个特征的基尼指数
fea_values=self.class_num(data, feature)
min_gini=sys.maxsize
min_value=None
min_left=None
min_right=None
for k in fea_values.keys(): #对feature的每一个取值计算gini系数
d1=data[(data[:, feature] == k),: ] #特征feature 取值是k的集合
d2=data[(data[:, feature] != k),: ]#特征feature 取值不是k 的集合
r1=d1.shape[0]/data.shape[0]
r2=d2.shape[0]/data.shape[0]
gini=r1*self.cal_gini(d1)+r2*self.cal_gini(d2)
if gini<min_gini:
min_gini=gini
min_value=k
min_left=d1
min_right=d2
return min_gini,min_value,min_left,min_right
def create_classification_tree(self,data): #生成一棵分类树
min_gini=sys.maxsize
min_split=None
min_feature=None
min_left=None
min_right=None
if data.shape[0]==0:
return None
elif self.is_one_class(data, self.label): # 如果数据都属于一类
node = Node(data, None, None, self.label, 0, self.max_num_class(data, self.label)) # 叶子结点
elif len(self.features) == 0: # 没有可供划分的特征了
node = Node(data, None, None, self.label, 0, self.max_num_class(data, self.label)) # 叶子结点
else:
for i in self.features:
gini,value,left,right=self.basefeature_cal_gini(data,i)
if gini<min_gini:
min_gini=gini
min_split=value
min_feature=i
min_left=left
min_right=right
self.features.remove(i)
left_node = self.create_regression_tree(min_left)
right_node = self.create_regression_tree(min_right)
node = Node(data, left_node, right_node, min_feature, min_split, 0)
return node
def max_num_class(self, data, label): # 返回取值最多的那一类
# X = data[:, label:label + 1]
labels = self.class_num(data, label)
max_num = 0
max_class = 0
for k, v in labels.items():
if v > max_num:
max_num = v
max_class = k
return max_class
def error(self,data):
fea_value=self.class_num(data,self.label)
max_class=self.max_num_class(data,self.label)
err=0
for k,v in fea_value.items():
if k!=max_class:
err+= (v/data.shape[0])*(data.shape[0]/self.Train.shape[0])
return err
def copy_tree(self,node):
copy_node=None
if node==None:
copy_node=None
else:
left=self.copy_tree(node.left)
right=self.copy_tree(node.right)
copy_node=Node(node.data,left,right,node.feature,node.split,node.value)
return copy_node
def need_prune(self, node):
if node.left.feature != self.label or node.right.feature != self.label: # 还有内部结点
return True
else:
return False
def prune(self):
root=self.root
now_tree = self.copy_tree(root)
self.roots.append(now_tree)
while self.need_prune(root):
self.a=sys.maxsize
self.minnode=None
self.cal_prune_what(root)
self.minnode.left=None
self.minnode.right=None
self.minnode.feature=self.label
self.split=None
self.value=self.max_num_class(self.minnode.data, self.label)
now_tree=self.copy_tree(root)
self.roots.append(now_tree)
def cal_prune_what(self,node):
leaf_error=0
leaf_num=0
if node.left==None and node.right==None:#如果该结点是叶子结点
return self.error(node.data),1
else:
if node.left!=None:
left_error,left_num=self.cal_prune_what(node.left)
leaf_error += left_error
leaf_num+=left_num
if node.right!=None:
right_error,right_num=self.cal_prune_what(node.right)
leaf_error += right_error
leaf_num+=right_num
node_err=self.error(node.data)
a=(node_err-leaf_error)/(leaf_num-1)
if node!=self.root:
if a<self.a:
self.a=a
self.minnode=node
return leaf_error,leaf_num
def pre_order(self, node):
if node != None:
if node.left == None and node.right == None: # 如果是叶子结点
print(str(node.value) + "\n")
else:
print(self.feature_name[node.feature])
self.pre_order(node.left)
self.pre_order(node.right)
def level_order(self):
queue = []
queue.append(self.root)
while len(queue) > 0:
node = queue.pop(0)
if node.left == None and node.right == None:
print(node.value)
else:
print(self.feature_name[node.feature])
queue.append(node.left)
queue.append(node.right)
def fit(self,node,X):
while node.left!=None and node.right!=None:# 如果不是叶子结点
feature=node.feature
split=node.split
if X[feature] == split:
node=node.left
else:
node=node.right
print("X的预测结果")
print(node.value)
datasets = np.array([['青年', '否', '否', '一般', 0],
['青年', '否', '否', '好', 0],
['青年', '是', '否', '好', 1],
['青年', '是', '是', '一般'
- 文章目录
- 繁
