树的构建算法 CART（Classification And Regression Trees, 分类回归树）的树构建算法。该算法可以用来分类也可以用来回归。
树回归 原理
原理概述
为了构建以分段常数为叶节点的树，需要度量出数据的一致性。
首先计算所有数据的均值，然后计算每条数据的值到均值的差值。为了对正负差值同等看待，一般用绝对值或者平方值来代替上述差值。
方差是平方误差的均值（均方差），而这里需要的是平方误差的总值（总方差）。总方差是通过均方差乘以数据集中样本点的个数来得到的。
树构建算法 比较
1.ID3 -> 每次选取当前最佳的特征来分隔数据，并按照该特征的所有可能值来切分。
2.二分切分法 -> 每次切分将数据集分成两份。如果数据的某特征等于切分所要求的值，那么这些数据进入树的左子树，反之进入右子树。
3.Cart切分 -> 是一种非常著名且广泛记载的构建树的算法，它使用二元切分来处理连续型变量。
构建决策树常用到的三个方法：
ID3, C4.5, CART 三种方法的主要区分是划分分支方法：
1.ID3是信息增益的分支
2.C4.5是信息增益率的分支
3.CART是GINI系数分支
树回归工作原理：
对每个特征：
对每个特征值：
将数据集切分成两份（小于该特征的数据样本放在左子树，否则放在右子树）
计算切分的误差
如果当前误差小于当前的最小误差，那么当前切分设定为最佳切分并更新最小误差
返回最佳切分的特征和阈值
建树的伪代码：
找到最佳的待切分特征：
如果该节点不能再分，将该节点存为叶子节点
执行二元切分
在右子树调用 createTree() 方法
在左子树调用 createTree() 方法
树回归开发流程：
1.收集数据
2.准备数据
3.分析数据
4.训练算法
5.测试算法
6.使用算法
树剪枝方法：
一个树如果节点过多，表明该模型肯能对数据进行了“过拟合”。
通过降低决策树的复杂度来避免过拟合的过程称为剪枝（pruning）。在函数chooseBestSplit()中提前终止条件，实际上是在进行一种所谓的预剪枝（prepruning）操作。另一个形式的兼职需要使用测试集和训练集，称作后剪枝（postpruning）。
预剪枝（prepruning）
预剪枝就是提早的停止树增长，在构造决策树的同时进行剪枝。
所以决策树的构建方法，都是在无法进一步降低熵的情况下才会停止创建分支的过程，为了避免过拟合，可以设定一个阈值，熵减小的数量小于这个阈值，即使还可以继续降低熵，也停止继续创建分支。
后剪枝（postpruning）
决策树构造完成后进行剪枝。剪枝的过程是对拥有同样父节点的一组节点进行检查，判断如果将其合并，熵的增加量是否小于某一阈值。如果确实小，则这一组节点可以合并一个节点，其中包含了所有的可能结果。合并也称作塌陷处理，在回归树中一般采取需要合并的所有子树的平均值。后剪枝是目前最普遍的做法。
后剪枝 prune() 的伪代码如下：
基于已有的树切分测试数据：
如果存在任一子集是一棵树，则在该子集递归剪枝过程
计算当前两个叶子合并后的误差
计算不合并的误差
如果合并会降低误差的话，就将叶子结点合并
代码部分
# -*- coding:utf-8 -*-__author__='yangxin_ryan'fromnumpyimport*"""树回归"""classRegTees(object): defload_data_set(self, file_name): data_mat= [] fr=open(file_name) forlineinfr.readlines(): cur_line=line.strip().split("\t") flt_line= [float(x) forxincur_line] data_mat.append(flt_line) returndata_matdefbin_split_data_set(self, data_set, feature, value): mat0=data_set[nonzero(data_set[:, feature] <=value)[0], :] mat1=data_set[nonzero(data_set[:, feature] >value)[0], :] returnmat0, mat1defreg_left(self, data_set): returnmean(data_set[:, -1]) defreg_err(self, data_set): returnvar(data_set[:, -1]) *shape(data_set)[0] defchoose_best_split(self, data_set, leaf_type, err_type, ops=(1, 4)): tol_s=ops[0] tol_n=ops[1] iflen(set(data_set[:, -1].T.tolist()[0])) ==1: returnNone, leaf_type(data_set) m, n=shape(data_set) s=err_type(data_set) best_s, best_index, best_value=inf, 0, 0forfeat_indexinrange(n-1): forsplit_valinset(data_set[:, feat_index].T.tolist()[0]): mat0, mat1=self.bin_split_data_set(data_set, feat_index, split_val) if (shape(mat0)[0] <tol_n) or (shape(mat1)[0] <tol_n): continuenew_s=err_type(mat0) +err_type(mat1) ifnew_s<best_s: best_index=feat_indexbest_value=split_valbest_s=new_sif (s-best_s) <tol_s: returnNone, leaf_type(data_set) mat0, mat1=self.bin_split_data_set(data_set, best_index, best_value) if (shape(mat0)[0] <tol_n) or (shape(mat1)[0] <tol_n): returnNone, leaf_type(data_set) returnbest_index, best_valuedefcreate_tree(self, data_set, leaf_type, err_type, ops=(1, 4)): feat, val=self.choose_best_split(data_set, leaf_type, err_type, ops) iffeatisNone: returnvalret_tree= {} ret_tree['spInd'] =featret_tree['spVal'] =vall_set, r_set=self.bin_split_data_set(data_set, feat, val) ret_tree['left'] =self.create_tree(l_set, leaf_type, err_type, ops) ret_tree['right'] =self.create_tree(r_set, leaf_type, err_type, ops) returnret_treedefis_tree(self, obj): return (type(obj).__name__=='dict') defget_mean(self, tree): ifself.is_tree(tree['right']): tree['right'] =self.get_mean(tree['right']) ifself.is_tree(tree['left']): tree['left'] =self.get_mean(tree['left']) return (tree['left'] +tree['right']) /2.0defprune(self, tree, test_data): l_set, r_set=None, Noneifshape(test_data)[0] ==0: returnself.get_mean(tree) ifself.is_tree(tree['right']) orself.is_tree(tree['left']): l_set, r_set=self.bin_split_data_set(test_data, tree['spInd'], tree['spVal']) ifself.is_tree(tree['left']): tree['left'] =self.prune(tree['left'], l_set) ifself.is_tree(tree['right']): tree['right'] =self.prune(tree['right'], r_set) ifnotself.is_tree(tree['left']) andnotself.is_tree(tree['right']): l_set, r_set=self.bin_split_data_set(test_data, tree['spInd'], tree['spVal']) error_no_merge=sum(power(l_set[:, -1] -tree['left'], 2)) +sum(power(r_set[:, -1] -tree['right'], 2)) tree_mean= (tree['left'] +tree['right']) /2.0error_merge=sum(power(test_data[:, -1] -tree_mean, 2)) iferror_merge<error_no_merge: returntree_meanelse: returntreeelse: returntreedefmodel_leaf(self, data_set): ws, X, Y=self.linear_solve(data_set) returnwsdefmodel_err(self, data_set): ws, X, Y=self.linear_solve(data_set) y_hat=X*wsreturnsum(power(Y-y_hat, 2)) deflinear_solve(self, data_set): m, n=shape(data_set) X=mat(ones((m, n))) Y=mat(ones((m, 1))) X[:, 1: n] =data_set[:, 0: n-1] Y=data_set[:, -1] xTx=X.T*Xiflinalg.det(xTx) ==0.0: raiseNameError('This matrix is singular, cannot do inverse,\ntry increasing the second value of ops') ws=xTx.I* (X.T*Y) returnws, X, Ydefreg_tree_eval(self, model, in_dat): returnfloat(model) defmodel_tree_eval(self, model, in_dat): n=shape(in_dat)[1] X=mat(ones((1, n+1))) X[:, 1: n+1] =in_datreturnfloat(X*model) deftree_fore_cast(self, tree, in_data, model_eval): ifnotself.is_tree(tree): returnmodel_eval(tree, in_data) ifin_data[tree['spInd']] <=tree['spVal']: ifself.is_tree(tree['left']): returnself.tree_fore_cast(tree['left'], in_data, model_eval) else: returnmodel_eval(tree['left'], in_data) else: ifself.is_tree(tree['right']): returnself.tree_fore_cast(tree['right'], in_data, model_eval) else: returnmodel_eval(tree['right'], in_data) defcreate_fore_cast(self, tree, test_data, model_eval): m=len(test_data) y_hat=mat(zeros((m, 1))) foriinrange(m): y_hat[i, 0] =self.tree_fore_cast(tree, mat(test_data[i]), model_eval) returny_hatif__name__=="__main__": reg_tress=RegTees() train_mat=mat(reg_tress.load_data_set('data/xxxx/bikeSpeedVsIq_train.txt')) test_mat=mat(reg_tress.load_data_set('data/xxxx/bikeSpeedVsIq_test.txt')) my_tree1=reg_tress.create_tree(train_mat, ops=(1, 20)) y_hat1=reg_tress.create_fore_cast(my_tree1, test_mat[:, 0]) my_tree2=reg_tress.create_tree(train_mat, reg_tress.model_leaf, reg_tress.model_err, ops=(1, 20)) y_hat2=reg_tress.create_fore_cast(my_tree2, test_mat[:, 0], reg_tress.model_tree_eval) ws, X, Y=reg_tress.linear_solve(train_mat) m=len(test_mat[:, 0]) y_hat3=mat(zeros((m, 1))) foriinrange(shape(test_mat)[0]): y_hat3[i] =test_mat[i, 0] *ws[1, 0] +ws[0, 0]
