树回归的有点事可以对复杂和非线性的数据建模，缺点则是结果不易理解，使用于数值型和标称型数据。
一般来说树的构建算法是ID3，每次选取当前最佳的特征来分割数据，并按该特征的所有可能的取值来切分。如果一个特征有4种取值，那么数据将被截成4份。另一种是二元切分法，每次把数据集切成两份，如果数据的某特征值等于切分所要求的值，那么这些数据就进入左子树，反之进入右子树。ID3算法还不能直接处理连续型特征，需要转换成离散型。但这种准换过程会破坏连续性变量的内在性质。二元切分法易于对书构建过程进行调整已处理连续型特征。
下面实观CART算法和回归树。回归树叶节点的数据类型不是离散型而是连续性。
使用一部分字典来存储树的数据结构，包含以下四个元素：
1.待切分的特征
2、待切分的特征值
3.右子树，当不需要切分时，也可以是个单值
4.左子树，与右子树类似
首先建立树节点：
class treeNode():
def __init__(self,feat,val,right,left):
featureToSplitOn = feat
valueOfSplit = val
rightBranch = right
leftBranch =left
"""
用来建立树节点
"""
这里会构建两种树，第一种是回归树，期每个叶节点包含单个值。第二种是模型树，期每个叶节点包含一个线性方程。
先给出一些共用代码，函数createTree()的伪代码如下：
找到最佳的待切分特征：
如果该节点不能再分，将该节点存为叶节点
执行二元切分
在右子树调用createTree()方法
在左子树调用createTree()方法
from numpy import *
def loadDataSet(filename):
dataMat = []
fr = open(filename)
for line in fr.readlines():
curLine = line.strip().split('t')
fltLine = map(float,curLine)
dataMat.append(fltLine)
return dataMat
def regLeaf(dataSet):
return mean(dataSet[:,-1])
#负责生成叶节点。当chooseBestSplit()函数确定不再对数据进行切分时，将调用该函数
#来得到叶节点的模型，该模型其实就是目标变量的均值
def regErr(dataSet):
return var(dataSet[:,-1]) * shape(dataSet)[0]
#该函数在给定数据上计算目标变量的平方误差。
def chooseBestSplit(dataSet, leafType=regLeaf, errType=regErr, ops=(1,4)):
tolS = ops[0]; tolN = ops[1]
#用于控制函数的停止时机，其中tols是容许的误差下降值，tolN是切分的最少样本数
#如果所有目标变量的值相同：退出并返回值
if len(set(dataSet[:,-1].T.tolist()[0])) == 1:
return None, leafType(dataSet)
#如果找不到好的二元切分，该函数将返回None斌同时调用creeatTree()方法来产生叶节点
m,n = shape(dataSet)
#最佳特性的选择是通过减少平均值的RSS误差来实现的
S = errType(dataSet)
bestS = inf; bestIndex = 0; bestValue = 0
for featIndex in range(n-1):
for splitVal in set(dataSet[:,featIndex]):
mat0, mat1 = binSplitDataSet(dataSet, featIndex, splitVal)
if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN): continue
newS = errType(mat0) + errType(mat1)
if newS < bestS:
bestIndex = featIndex
bestValue = splitVal
bestS = newS
#如果减少（S-BESTS）小于阈值，则不执行分割。
if (S - bestS) < tolS:
return None, leafType(dataSet)
mat0, mat1 = binSplitDataSet(dataSet, bestIndex, bestValue)
if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN):
return None, leafType(dataSet)
return bestIndex,bestValue
#返回要拆分的最好的特征，并且该特征值会用做该拆分的值
def binSplitDataSet(dataSet,feature,value):
mat0 = dataSet[nonzero(dataSet[:,feature]>value)[0],:][0]
mat1 = dataSet[nonzero(dataSet[:, feature] <= value)[0], :][0]
return mat0,mat1
"""
该函数有三个参数，数据集合，待切分的特征和该特征的某个值
在给定特征和特征值的情况下，该函数通过数组过滤方式将上述数据集合切分的到两个子集并返回
"""
def createTree(dataSet,leafType=regLeaf,errType=regErr,ops=(1.4)):
feat,val = chooseBestSplit(dataSet,leafType,errType,ops)
if feat == None:
return val
retTree = {}
retTree['spInd'] = feat
retTree['spVal'] = val
lSet,rSet = binSplitDataSet(dataSet,feat,val)
retTree['left'] = createTree(lSet,leafType,errType, ops)
retTree['right'] = createTree(rSet, leafType, errType, ops)
return retTree
"""
这个函数有四个参数：数据集和其他三个可选参数，这些可选参数决定了树的类型
leafType给出建立叶节点的函数
errType代表误差计算函数
ops是一个包含树构建所需要其他参数的元组
该函数是一个递归函数，首先尝试将数据集分成两部分，切分由函数chooseBestSplit()来完成
如果满足停止条件，chooseBestSplit()将返回None和某模型的值。
如果构建的是回归树，该模型是一个常数。如果是模型树，其模型是一个线性方程。
如果不满足停止条件，chooseBestSplit()将创建一个新的字典并将数据集分成两份，在这两份数据集上
分别继续递归调用createTree()函数
"""
testMat = mat(eye(4))
print(testMat)
print("-----------------------------------")
mat0,mat1 = binSplitDataSet(testMat,1,0.5)
print(mat0)
print("-----------------------------------")
print(mat1)
[[1. 0. 0. 0.]
[0. 1. 0. 0.]
[0. 0. 1. 0.]
[0. 0. 0. 1.]]
-----------------------------------
[[0. 1. 0. 0.]]
-----------------------------------
[[1. 0. 0. 0.]]
testMat创建了一个简单的矩阵，下面是按照指定列的某个值来切分该矩阵。
chooseBestSplit()函数的伪代码如下：该函数的目标是找到数据集切分的最佳位置，他遍历所有的特征及其可能的取值来找到谁误差最小化的切分阈值。
对每个特征值：
对每个特征值：
将数据集切分成两份
计算切分的误差
如果当前误差小于当前最小误差，那么将当前切分设定为最佳切分并更新最小误差
返回最佳切分的特征和阈值
看一下代码的实际效果，从数据中生成一颗回归树。
myDat = loadDataSet('F:pythonmachinelearninginactionCh09ex00.txt')
myMat = mat(myDat)
print(createTree(myMat))
{'spInd': 0, 'spVal': 0.48813, 'left': 1.0180967672413792, 'right': -0.04465028571428572}
myDat1 = loadDataSet('F:pythonmachinelearninginactionCh09ex0.txt')
myMat1 = mat(myDat1)
print(createTree(myMat1))
{'spInd': 1, 'spVal': 0.39435, 'left': {'spInd': 1, 'spVal': 0.582002, 'left': {'spInd': 1, 'spVal': 0.797583, 'left': 3.9871632, 'right': 2.9836209534883724}, 'right': 1.980035071428571}, 'right': {'spInd': 1, 'spVal': 0.197834, 'left': 1.0289583666666666, 'right': -0.023838155555555553}}
现在已经完成了回归树的构建，下面将介绍树剪枝技术，它通过对决策树剪枝来达到更好的预测效果。
树剪枝
通过降低决策树的复杂度来避免过拟合的过程称为剪枝。
预剪枝这里不多做介绍敏著要讨论一下更理想化的剪枝方法-后剪枝
伪代码如下：
基于已有的树切分测试数据： 如果存在任意子集市一棵树，则在该子集递归剪枝过程 计算当前两个叶节点合并后的误差 计算不合并的误差 如果合并会降低误差的话，就将叶节点合并
def isTree(obj):
import types
return (type(obj).__name__ == 'dict')
'''
用于测试输入变量是否为一棵树，也就是判断当前处理的节点是否是叶节点
'''
def getMean(tree):
if isTree(tree['right']): tree['right'] = getMean(tree['right'])
if isTree(tree['left']): tree['left'] = getMean(tree['left'])
return (tree['left'] + tree['right']) / 2.0
'''
该函数是一个递归函数，从上往下遍历树直到叶节点为止。
如果找到两个叶节点，计算它们的平均值
该函数对树进行塌陷处理（机返回树平均值）
'''
def prune(tree, testData):
# 如果测试集为空,则对树进行塌陷处理
if shape(testData)[0] == 0: return getMean(tree)
# 判断某个分支是子树还是节点
if (isTree(tree['right']) or isTree(tree['left'])):
lSet, rSet = binSplitDataSet(testData, tree['spInd'], tree['spVal'])
# 处理左子树
if isTree(tree['left']): tree['left'] = prune(tree['left'], lSet)
# 处理右子树
if isTree(tree['right']): tree['right'] = prune(tree['right'], rSet)
if not isTree(tree['left']) and not isTree(tree['right']):
#如果不是子树则进行合并
lSet, rSet = binSplitDataSet(testData, tree['spInd'], tree['spVal'])
# 计算没有合并的误差
errorNoMerge = np.sum(np.power(lSet[:, -1] - tree['left'], 2)) + np.sum(
np.power(rSet[:, -1] - tree['right'], 2))
# 计算合并的均值
treeMean = (tree['left'] + tree['right']) / 2.0
# 计算合并的误差
errorMerge = np.sum(np.power(testData[:, -1] - treeMean, 2))
if errorMerge < errorNoMerge:
return treeMean
else:
return tree
else:
return tree
'''
有两个参数：待剪枝的树和剪枝所需的测试数据集
'''
myDat = loadDataSet('F:pythonmachinelearninginactionCh09ex00.txt')
myMat = mat(myDat)
#print(createTree(myMat))
myDat1 = loadDataSet('F:pythonmachinelearninginactionCh09ex0.txt')
myMat1 = mat(myDat1)
#print(createTree(myMat1))
myMat2 = loadDataSet('F:pythonmachinelearninginactionCh09ex2.txt')
myTree = createTree(myMat2,ops=(0,1))
#为了创建所有可能中最大的树
#输入以下命令导入测试数据：
myDatTest = loadDataSet('F:pythonmachinelearninginactionCh09ex2test.txt')
myMat2Test = mat(myDatTest)
#输入以下命令执行剪枝过程
prune(myTree,myMat2Test)
出现报错：TypeError: list indices must be integers or slices, not tuple
我服了，跟书上一样也不对，copy网上的代码也不对，为啥人家能运行出来啊，我真是无语。
找不出来为啥，放弃
