Python实现CART

糖逗

参考书籍：《机器学习实战》

1.CART回归（预剪枝，通过tolS和tolT两个参数控制）

1. import numpy as np
   
2. 
   
3. def loadDataSet(fileName):     
   
4.     dataMat = []               
   
5.     fr = open(fileName)
   
6.     for line in fr.readlines():
   
7.         curLine = line.strip().split('\t')
   
8.         fltLine = list(map(float,curLine))
   
9.         dataMat.append(fltLine)
   
10.     return np.mat(dataMat)
    
11. 
    
12. def binSplitDataSet(dataSet, feature, value):
    
13.     mat0 = dataSet[np.nonzero(dataSet[:,feature] > value)[0],:]
    
14.     mat1 = dataSet[np.nonzero(dataSet[:,feature] <= value)[0],:]
    
15.     return mat0,mat1
    
16. 
    
17. def regLeaf(dataSet):
    
18.     return np.mean(dataSet[:,-1])
    
19. 
    
20. def regErr(dataSet):
    
21.     return np.var(dataSet[:,-1]) * np.shape(dataSet)[0]
    
22. 
    
23. def chooseBestSplit(dataSet, leafType = regLeaf, errType = regErr, ops=(1,4)):
    
24.     tolS = ops[0]#每次特征选择后的降低总方差的最小值
    
25.     tolN = ops[1]#每次换分后每个子节点的最少样本个数
    
26.     if len(set(dataSet[:,-1].T.tolist()[0])) == 1:#已经没有可分的直接返回成叶子节点
    
27.         return None, leafType(dataSet)
    
28.     m,n = np.shape(dataSet)
    
29.     S = errType(dataSet)
    
30.     bestS = np.inf; bestIndex = 0; bestValue = 0
    
31.     for featIndex in range(n-1):
    
32.         for splitVal in set(dataSet[:,featIndex].tolist()[0]):
    
33.             mat0, mat1 = binSplitDataSet(dataSet, featIndex, splitVal)
    
34.             if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN): continue
    
35.             newS = errType(mat0) + errType(mat1)
    
36.             if newS < bestS:
    
37.                 bestIndex = featIndex
    
38.                 bestValue = splitVal
    
39.                 bestS = newS
    
40.     if (S - bestS) < tolS:
    
41.         return None, leafType(dataSet)#叶子节点
    
42.     mat0, mat1 = binSplitDataSet(dataSet, bestIndex, bestValue)
    
43.     if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN):
    
44.         return None, leafType(dataSet)
    
45.     return bestIndex,bestValue
    
46.                        
    
47. 
    
48. def createTree(dataSet, leafType = regLeaf, errType = regErr, ops=(1,4)):
    
49.     #递归的形式生成树
    
50.     feat, val = chooseBestSplit(dataSet, leafType, errType, ops)
    
51.     if feat == None: return val
    
52.     retTree = {}
    
53.     retTree['spInd'] = feat
    
54.     retTree['spVal'] = val
    
55.     lSet, rSet = binSplitDataSet(dataSet, feat, val)
    
56.     retTree['left'] = createTree(lSet, leafType, errType, ops)
    
57.     retTree['right'] = createTree(rSet, leafType, errType, ops)
    
58.     return retTree  
    
59. 
    
60. 
    
61. if __name__ == "__main__":
    
62.     myDat = loadDataSet(r"C:\...\ex00.txt")
    
63.     res = createTree(myDat)
    
64.    

复制代码

2.CART回归（后剪枝）

1. import numpy as np
   
2. 
   
3. def loadDataSet(fileName):     
   
4.     dataMat = []               
   
5.     fr = open(fileName)
   
6.     for line in fr.readlines():
   
7.         curLine = line.strip().split('\t')
   
8.         fltLine = list(map(float,curLine))
   
9.         dataMat.append(fltLine)
   
10.     return np.mat(dataMat)
    
11. 
    
12. def binSplitDataSet(dataSet, feature, value):
    
13.     mat0 = dataSet[np.nonzero(dataSet[:,feature] > value)[0],:]
    
14.     mat1 = dataSet[np.nonzero(dataSet[:,feature] <= value)[0],:]
    
15.     return mat0,mat1
    
16. 
    
17. def regLeaf(dataSet):
    
18.     return np.mean(dataSet[:,-1])
    
19. 
    
20. def regErr(dataSet):
    
21.     return np.var(dataSet[:,-1]) * np.shape(dataSet)[0]
    
22. 
    
23. def chooseBestSplit(dataSet, leafType = regLeaf, errType = regErr, ops=(1,4)):
    
24.     tolS = ops[0]#每次特征选择后的降低总方差的最小值
    
25.     tolN = ops[1]#每次换分后每个子节点的最少样本个数
    
26.     if len(set(dataSet[:,-1].T.tolist()[0])) == 1:#已经没有可分的直接返回成叶子节点
    
27.         return None, leafType(dataSet)
    
28.     m,n = np.shape(dataSet)
    
29.     S = errType(dataSet)
    
30.     bestS = np.inf; bestIndex = 0; bestValue = 0
    
31.     for featIndex in range(n-1):
    
32.         for splitVal in set(dataSet[:,featIndex].tolist()[0]):
    
33.             mat0, mat1 = binSplitDataSet(dataSet, featIndex, splitVal)
    
34.             if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN): continue
    
35.             newS = errType(mat0) + errType(mat1)
    
36.             if newS < bestS:
    
37.                 bestIndex = featIndex
    
38.                 bestValue = splitVal
    
39.                 bestS = newS
    
40.     if (S - bestS) < tolS:
    
41.         return None, leafType(dataSet)#叶子节点
    
42.     mat0, mat1 = binSplitDataSet(dataSet, bestIndex, bestValue)
    
43.     if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN):
    
44.         return None, leafType(dataSet)
    
45.     return bestIndex,bestValue
    
46. 
    
47. 
    
48. 
    
49. def createTree(dataSet, leafType = regLeaf, errType = regErr, ops=(1,4)):
    
50.     #递归的形式生成树
    
51.     feat, val = chooseBestSplit(dataSet, leafType, errType, ops)
    
52.     if feat == None: return val
    
53.     retTree = {}
    
54.     retTree['spInd'] = feat
    
55.     retTree['spVal'] = val
    
56.     lSet, rSet = binSplitDataSet(dataSet, feat, val)
    
57.     retTree['left'] = createTree(lSet, leafType, errType, ops)
    
58.     retTree['right'] = createTree(rSet, leafType, errType, ops)
    
59.     return retTree  
    
60. 
    
61. 
    
62. def isTree(obj):
    
63.     return (type(obj).__name__=='dict')
    
64. 
    
65. def getMean(tree):#树的递归
    
66.     if isTree(tree['right']): tree['right'] = getMean(tree['right'])
    
67.     if isTree(tree['left']): tree['left'] = getMean(tree['left'])
    
68.     return (tree['left']+tree['right']) / 2.0
    
69.    
    
70. def prune(tree, testData):
    
71.     if np.shape(testData)[0] == 0: return getMean(tree)
    
72.     if (isTree(tree['right']) or isTree(tree['left'])):
    
73.         lSet, rSet = binSplitDataSet(testData, tree['spInd'], tree['spVal'])
    
74.     if isTree(tree['left']): tree['left'] = prune(tree['left'], lSet)
    
75.     if isTree(tree['right']): tree['right'] =  prune(tree['right'], rSet)
    
76.     if not isTree(tree['left']) and not isTree(tree['right']):
    
77.         lSet, rSet = binSplitDataSet(testData, tree['spInd'], tree['spVal'])
    
78.         errorNoMerge = sum(np.power(lSet[:,-1] - tree['left'],2)) +\
    
79.             sum(np.power(rSet[:,-1] - tree['right'],2))
    
80.         treeMean = (tree['left'] + tree['right'])/2.0
    
81.         errorMerge = sum(np.power(testData[:, -1] - treeMean, 2))
    
82.         if errorMerge < errorNoMerge:
    
83.             print("merging")
    
84.             return treeMean
    
85.         else:
    
86.             return tree
    
87.     return tree
    
88. 
    
89. if __name__ == "__main__":
    
90.     myDat = loadDataSet(r"C:\...\ex2.txt")
    
91.     myDatTest = loadDataSet(r"C:\...\ex2test.txt")
    
92.     myTree = createTree(myDat, ops = (0, 1))
    
93.     res = prune(myTree, myDatTest)
    
94. #先基于训练集生成完整的树，然后通过验证集进行后剪枝（相当于调参）。
    

复制代码

3.模型树

1. import numpy as np
   
2. 
   
3. def loadDataSet(fileName):     
   
4.     dataMat = []               
   
5.     fr = open(fileName)
   
6.     for line in fr.readlines():
   
7.         curLine = line.strip().split('\t')
   
8.         fltLine = list(map(float,curLine))
   
9.         dataMat.append(fltLine)
   
10.     return np.mat(dataMat)
    
11. 
    
12. def binSplitDataSet(dataSet, feature, value):
    
13.     mat0 = dataSet[np.nonzero(dataSet[:,feature] > value)[0],:]
    
14.     mat1 = dataSet[np.nonzero(dataSet[:,feature] <= value)[0],:]
    
15.     return mat0,mat1
    
16. 
    
17. def regLeaf(dataSet):
    
18.     return np.mean(dataSet[:,-1])#返回叶子节点的均值
    
19. 
    
20. def regErr(dataSet):
    
21.     return np.var(dataSet[:,-1]) * np.shape(dataSet)[0]
    
22. 
    
23. def chooseBestSplit(dataSet, leafType = regLeaf, errType = regErr, ops=(1,4)):
    
24.     tolS = ops[0]#每次特征选择后的降低总方差的最小值
    
25.     tolN = ops[1]#每次换分后每个子节点的最少样本个数
    
26.     if len(set(dataSet[:,-1].T.tolist()[0])) == 1:#已经没有可分的直接返回成叶子节点
    
27.         return None, leafType(dataSet)
    
28.     m,n = np.shape(dataSet)
    
29.     S = errType(dataSet)
    
30.     bestS = np.inf; bestIndex = 0; bestValue = 0
    
31.     for featIndex in range(n-1):
    
32.         for splitVal in set(dataSet[:,featIndex].tolist()[0]):
    
33.             mat0, mat1 = binSplitDataSet(dataSet, featIndex, splitVal)
    
34.             if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN): continue
    
35.             newS = errType(mat0) + errType(mat1)
    
36.             if newS < bestS:
    
37.                 bestIndex = featIndex
    
38.                 bestValue = splitVal
    
39.                 bestS = newS
    
40.     if (S - bestS) < tolS:
    
41.         return None, leafType(dataSet)#叶子节点
    
42.     mat0, mat1 = binSplitDataSet(dataSet, bestIndex, bestValue)
    
43.     if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN):
    
44.         return None, leafType(dataSet)
    
45.     return bestIndex,bestValue
    
46. 
    
47. 
    
48. 
    
49. def createTree(dataSet, leafType = regLeaf, errType = regErr, ops=(1,4)):
    
50.     #递归的形式生成树
    
51.     feat, val = chooseBestSplit(dataSet, leafType, errType, ops)
    
52.     if feat == None: return val
    
53.     retTree = {}
    
54.     retTree['spInd'] = feat
    
55.     retTree['spVal'] = val
    
56.     lSet, rSet = binSplitDataSet(dataSet, feat, val)
    
57.     retTree['left'] = createTree(lSet, leafType, errType, ops)
    
58.     retTree['right'] = createTree(rSet, leafType, errType, ops)
    
59.     return retTree  
    
60. 
    
61. 
    
62. def linearSolve(dataSet):  
    
63.     m, n = np.shape(dataSet)
    
64.     X = np.mat(np.ones((m,n))); Y = np.mat(np.ones((m,1)))
    
65.     X[:,1:n] = dataSet[:,0:n-1]; Y = dataSet[:,-1]
    
66.     xTx = X.T*X
    
67.     if np.linalg.det(xTx) == 0.0:
    
68.         raise NameError('This matrix is singular, cannot do inverse,\n\
    
69.         try increasing the second value of ops')
    
70.     ws = xTx.I * (X.T * Y)#线性回归公式
    
71.     return ws,X,Y
    
72. 
    
73. def modelLeaf(dataSet):
    
74.     ws,X,Y = linearSolve(dataSet)
    
75.     return ws
    
76. 
    
77. def modelErr(dataSet):
    
78.     ws,X,Y = linearSolve(dataSet)
    
79.     yHat = X * ws
    
80.     return sum(np.power(Y - yHat,2))
    
81. 
    
82. if __name__ == "__main__":
    
83.     myDat = loadDataSet(r"C:\...\ex2.txt")
    
84.     myTree = createTree(myDat, modelLeaf, modelErr, (1, 10))

复制代码

糖逗