CART算法的树回归：

返回的每个节点最后是一个最终确定的平均值。

#coding:utf-8importnumpyasnp#加载文件数据defloadDataSet(fileName):#generalfunctiontoparsetab-delimitedfloatsdataMat=[]#assumelastcolumnistargetvaluefr=open(fileName)forlineinfr.readlines():curLine=line.strip().split('\t')fltLine=map(float,curLine)#mapallelementstofloat()dataMat.append(fltLine)returndataMat#在dataset中选择特征为feature的这一列，以value值分成两部分defbinSplitDataSet(dataSet,feature,value):mat0=dataSet[np.nonzero(dataSet[:,feature]>value)[0],:][0]mat1=dataSet[np.nonzero(dataSet[:,feature]<=value)[0],:][0]returnmat0,mat1#计算此矩阵的最后一列结果的平均值，用平均值来当做最后的返回结果，后面的模型树返回的是一个线性模型defregLeaf(dataSet):returnnp.mean(dataSet[:,-1])#计算dataset结果的混乱程度，用方差反应，因为是连续数据defregErr(dataSet):returnnp.var(dataSet[:,-1])*np.shape(dataSet)[0]#选择最佳的分离特征和该特征的分离点#这里的ops是预先的给定值，1是差别太小就不分了，4是分开后的各自样本数，太小就舍去，这是一种预剪枝方法defchooseBestSplit(dataSet,leafType=regLeaf,errType=regErr,ops=(1,4)):tolS=ops[0];tolN=ops[1]#ifallthetargetvariablesarethesamevalue:quitandreturnvalueiflen(set(dataSet[:,-1].T.tolist()[0]))==1:#exitcond1returnNone,leafType(dataSet)m,n=np.shape(dataSet)#thechoiceofthebestfeatureisdrivenbyReductioninRSSerrorfrommeanS=errType(dataSet)bestS=np.inf;bestIndex=0;bestValue=0#循环所有的特征forfeatIndexinrange(n-1):#循环该特征下的所有特征值forsplitValinset(dataSet[:,featIndex]):mat0,mat1=binSplitDataSet(dataSet,featIndex,splitVal)#如果更具这个特征值分成的两类有一个小与预先给定值，说明分类太偏，则不考虑if(np.shape(mat0)[0]<tolN)or(np.shape(mat1)[0]<tolN):continuenewS=errType(mat0)+errType(mat1)ifnewS<bestS:bestIndex=featIndexbestValue=splitValbestS=newS#ifthedecrease(S-bestS)islessthanathresholddon'tdothesplitif(S-bestS)<tolS:returnNone,leafType(dataSet)#exitcond2mat0,mat1=binSplitDataSet(dataSet,bestIndex,bestValue)if(np.shape(mat0)[0]<tolN)or(np.shape(mat1)[0]<tolN):#exitcond3returnNone,leafType(dataSet)returnbestIndex,bestValue#创建树defcreateTree(dataSet,leafType=regLeaf,errType=regErr,ops=(1,4)):feat,val=chooseBestSplit(dataSet,leafType,errType,ops)iffeat==None:returnvalretTree={}retTree['spInd']=featretTree['spVal']=vallSet,rSet=binSplitDataSet(dataSet,feat,val)retTree['left']=createTree(lSet,leafType,errType,ops)retTree['right']=createTree(rSet,leafType,errType,ops)returnretTreemyDat=loadDataSet('ex0.txt')myMat=np.mat(myDat)result=createTree(myMat)printresult

结果：

{'spInd': 1, 'spVal': matrix(` 0`.`39435`), 'right': {'spInd': 1, 'spVal': matrix(` 0`.`197834`), 'right': -0.023838155555555553, 'left': 1.0289583666666666}, 'left': {'spInd': 1, 'spVal': matrix(` 0`.`582002`), 'right': 1.980035071428571, 'left': {'spInd': 1, 'spVal': matrix(` 0`.`797583`), 'right': 2.9836209534883724, 'left': 3.9871631999999999}}}

结果的意思是：第几个特征，以多大作为特征值分开，分成左右，依次分下去。

这个算法很好，但是对数据的分类太过于高，容易造成过拟合。因此要采用剪枝技术。

通过降低决策树的复杂度来避免过拟合的过程称为剪枝。

#判断obj是否是一个子树defisTree(obj):return(type(obj).__name__=='dict')#用于坍塌处理，当测试数据集是空是，则取整个树的平均值defgetMean(tree):ifisTree(tree['right']):tree['right']=getMean(tree['right'])ifisTree(tree['left']):tree['left']=getMean(tree['left'])return(tree['left']+tree['right'])/2.0#剪枝函数defprune(tree,testData):#如果测试数据集为空，则坍塌处理ifnp.shape(testData)[0]==0:returngetMean(tree)#如果左或者右是树，则把测试数据集根据决策树进行分割if(isTree(tree['right'])orisTree(tree['left'])):lSet,rSet=binSplitDataSet(testData,tree['spInd'],tree['spVal'])#如果左侧是树，则把数据集和子树带入继续找ifisTree(tree['left']):tree['left']=prune(tree['left'],lSet)#同理ifisTree(tree['right']):tree['right']=prune(tree['right'],rSet)#iftheyarenowbothleafs,seeifwecanmergethem#如果左右都是节点，则计算节点误差ifnotisTree(tree['left'])andnotisTree(tree['right']):lSet,rSet=binSplitDataSet(testData,tree['spInd'],tree['spVal'])#计算不合并的误差errorNoMerge=sum(np.power(lSet[:,-1]-tree['left'],2))+sum(np.power(rSet[:,-1]-tree['right'],2))treeMean=(tree['left']+tree['right'])/2.0#计算将当前两个叶子节点合并后的误差errorMerge=sum(np.power(testData[:,-1]-treeMean,2))iferrorMerge<errorNoMerge:print"merging"#可以合并就返回平均值returntreeMean#不可以合并就返回树，不变else:returntreeelse:returntree

一般来说都是预剪枝和后剪枝合并使用

模型树

每个节点是一个线性模型

其他基本一样：

#对数据集进行线性回归deflinearSolve(dataSet):m,n=np.shape(dataSet)X=np.mat(np.ones((m,n)));Y=np.mat(np.ones((m,1)))#有一列是常数项，因此要多出一列放置常数项X[:,1:n]=dataSet[:,0:n-1];Y=dataSet[:,-1]xTx=X.T*Xifnp.linalg.det(xTx)==0.0:raiseNameError('Thismatrixissingular,cannotdoinverse,\n\tryincreasingthesecondvalueofops')ws=xTx.I*(X.T*Y)returnws,X,Y#产生针对该数据集的线性模型#相当于上面的regLeaf函数defmodelLeaf(dataSet):ws,X,Y=linearSolve(dataSet)returnws#产生针对该数据集的线性模型，并计算误差返回#相当于上面的regErr函数，计算模型的误差，如果分后和不分的误差差不多则选择不分defmodelErr(dataSet):ws,X,Y=linearSolve(dataSet)yHat=X*wsreturnsum(np.power(Y-yHat,2))

模型树回归很好，而且可以用作预测