決策樹模型與學(xué)習(xí)
決策樹模型
分類決策樹模型是一種描述對(duì)實(shí)例進(jìn)行分類的樹形結(jié)構(gòu)毕匀。決策樹由結(jié)點(diǎn)和有向邊組成腐碱。結(jié)點(diǎn)有兩種類型：內(nèi)部節(jié)點(diǎn)和葉節(jié)點(diǎn)，內(nèi)部節(jié)點(diǎn)表示一個(gè)特征或?qū)傩越伺洌~節(jié)點(diǎn)表示一個(gè)類。
分類的時(shí)候勾栗，從根節(jié)點(diǎn)開始惨篱，當(dāng)前節(jié)點(diǎn)設(shè)為根節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)必定是一種特征围俘，根據(jù)實(shí)例的該特征的取值砸讳，向下移動(dòng)，直到到達(dá)葉節(jié)點(diǎn)界牡，將實(shí)例分到葉節(jié)點(diǎn)對(duì)應(yīng)的類中簿寂。
決策樹與if-then規(guī)則
決策樹的屬性結(jié)構(gòu)其實(shí)對(duì)應(yīng)著一個(gè)規(guī)則集合：由決策樹的根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每條路徑構(gòu)成的規(guī)則組成；路徑上的內(nèi)部特征對(duì)應(yīng)著if條件宿亡，葉節(jié)點(diǎn)對(duì)應(yīng)著then結(jié)論常遂。決策樹和規(guī)則集合是等效的，都具有一個(gè)重要的性質(zhì)：互斥且完備挽荠。也就是說任何實(shí)例都被且僅被一條路徑或規(guī)則覆蓋克胳。
決策樹與條件概率分布
決策樹還是給定特征條件下類的條件概率分布的一種退化表示（非等效平绩，個(gè)人理解）。該條件分布定義在特征空間的劃分上漠另，特征空間被花費(fèi)為互不相交的單元捏雌，每個(gè)單元定義一個(gè)類的概率分布就構(gòu)成了一個(gè)條件概率分布。決策樹的每條路徑對(duì)應(yīng)于劃分中的一個(gè)單元笆搓。給定實(shí)例的特征X性湿，一定落入某個(gè)劃分，決策樹選取該劃分里最大概率的類作為結(jié)果輸出满败。如圖：
關(guān)于b圖肤频，我是這么理解的，將a圖的基礎(chǔ)上增加一個(gè)條件概率的維度P算墨，代表在當(dāng)前特征X的情況下宵荒，分類為+的后驗(yàn)概率。圖中的方塊有些地方完全沒有米同，比如x2軸上[a2,1]這個(gè)區(qū)間骇扇，說明只要X落在這里，Y就一定是-的面粮，同理對(duì)于[0,a1]和[0,a2]圍起來的一定是+的。有些地方只有一半继低，比如x1軸上[a1,1]這個(gè)區(qū)間熬苍，說明決策樹認(rèn)為X落在這里，Y只有一半概率是+的袁翁，根據(jù)選擇條件概率大的類別的原則柴底，就認(rèn)為Y是-的（因?yàn)椴粷M足P(+)>0.5)。
決策樹學(xué)習(xí)
決策樹學(xué)習(xí)算法包含特征選擇粱胜、決策樹的生成與剪枝過程柄驻。決策樹的學(xué)習(xí)算法一般是遞歸地選擇最優(yōu)特征，并用最優(yōu)特征對(duì)數(shù)據(jù)集進(jìn)行分割焙压。開始時(shí)鸿脓，構(gòu)建根節(jié)點(diǎn)，選擇最優(yōu)特征涯曲，該特征有幾種值就分割為幾個(gè)子集野哭，每個(gè)子集分別遞歸調(diào)用此方法，返回節(jié)點(diǎn)幻件，返回的節(jié)點(diǎn)就是上一層的子節(jié)點(diǎn)拨黔。直到數(shù)據(jù)集為空，或者數(shù)據(jù)集只有一維特征為止绰沥。
基本骨架的Python實(shí)現(xiàn)：
def majorityCnt(classList):
"""
返回出現(xiàn)次數(shù)最多的分類名稱
:param classList: 類列表
:return: 出現(xiàn)次數(shù)最多的類名稱
"""
classCount = {} # 這是一個(gè)字典
for vote in classList:
if vote not in classCount.keys(): classCount[vote] = 0
classCount[vote] += 1
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
def createTree(dataSet, labels, chooseBestFeatureToSplitFunc=chooseBestFeatureToSplitByID3):
"""
創(chuàng)建決策樹
:param dataSet:數(shù)據(jù)集
:param labels:數(shù)據(jù)集每一維的名稱
:return:決策樹
"""
classList = [example[-1] for example in dataSet] # 類別列表
if classList.count(classList[0]) == len(classList):
return classList[0] # 當(dāng)類別完全相同則停止繼續(xù)劃分
if len(dataSet[0]) == 1: # 當(dāng)只有一個(gè)特征的時(shí)候篱蝇，遍歷完所有實(shí)例返回出現(xiàn)次數(shù)最多的類別
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplitFunc(dataSet)
bestFeatLabel = labels[bestFeat]
myTree = {bestFeatLabel: {}}
del (labels[bestFeat])
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = labels[:] # 復(fù)制操作
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
return myTree
由于決策樹表示條件概率分布贺待，所以高度不同的決策樹對(duì)應(yīng)不同復(fù)雜度的概率模型。最優(yōu)決策樹的生成是個(gè)NP問題零截，能實(shí)現(xiàn)的生成算法都是局部最優(yōu)的狠持，剪枝則是既定決策樹下的全局最優(yōu)。
特征選擇
特征選擇
樣本通常有很多維特征瞻润，希望選擇具有分類能力的特征喘垂。比如下表：
可以用Python建立數(shù)據(jù)集：
def createDataSet():
"""
創(chuàng)建數(shù)據(jù)集
:return:
"""
dataSet = [[u'青年', u'否', u'否', u'一般', u'拒絕'],
[u'青年', u'否', u'否', u'好', u'拒絕'],
[u'青年', u'是', u'否', u'好', u'同意'],
[u'青年', u'是', u'是', u'一般', u'同意'],
[u'青年', u'否', u'否', u'一般', u'拒絕'],
[u'中年', u'否', u'否', u'一般', u'拒絕'],
[u'中年', u'否', u'否', u'好', u'拒絕'],
[u'中年', u'是', u'是', u'好', u'同意'],
[u'中年', u'否', u'是', u'非常好', u'同意'],
[u'中年', u'否', u'是', u'非常好', u'同意'],
[u'老年', u'否', u'是', u'非常好', u'同意'],
[u'老年', u'否', u'是', u'好', u'同意'],
[u'老年', u'是', u'否', u'好', u'同意'],
[u'老年', u'是', u'否', u'非常好', u'同意'],
[u'老年', u'否', u'否', u'一般', u'拒絕'],
]
labels = [u'年齡', u'有工作', u'有房子', u'信貸情況']
# 返回?cái)?shù)據(jù)集和每個(gè)維度的名稱
return dataSet, labels
也可以根據(jù)特征分割數(shù)據(jù)集：
def splitDataSet(dataSet, axis, value):
"""
按照給定特征劃分?jǐn)?shù)據(jù)集
:param dataSet: 待劃分的數(shù)據(jù)集
:param axis: 劃分?jǐn)?shù)據(jù)集的特征的維度
:param value: 特征的值
:return: 符合該特征的所有實(shí)例（并且自動(dòng)移除掉這維特征）
"""
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis] # 刪掉這一維特征
reducedFeatVec.extend(featVec[axis + 1:])
retDataSet.append(reducedFeatVec)
return retDataSet
如何判斷一個(gè)特征的分類能力呢？
信息增益
先得介紹熵绍撞，應(yīng)該算是NLP和ML的老相好了：
對(duì)于一個(gè)可能有n種取值的隨機(jī)變量：
其熵為：
另外正勒，0log0=0。當(dāng)對(duì)數(shù)的底為2時(shí)傻铣，熵的單位為bit章贞，為e時(shí)，單位為nat非洲。
用Python實(shí)現(xiàn)信息熵（香農(nóng)熵）：
def calcShannonEnt(dataSet):
"""
計(jì)算訓(xùn)練數(shù)據(jù)集中的Y隨機(jī)變量的香農(nóng)熵
:param dataSet:
:return:
"""
numEntries = len(dataSet) # 實(shí)例的個(gè)數(shù)
labelCounts = {}
for featVec in dataSet: # 遍歷每個(gè)實(shí)例鸭限，統(tǒng)計(jì)標(biāo)簽的頻次
currentLabel = featVec[-1]
if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
shannonEnt = 0.0
for key in labelCounts:
prob = float(labelCounts[key]) / numEntries
shannonEnt -= prob * log(prob, 2) # log base 2
return shannonEnt
由定義值，X的熵與X的值無關(guān)两踏，只與分布有關(guān)败京，所以也可以將X的熵記作H(p)，即:
熵其實(shí)就是X的不確定性梦染，從定義可驗(yàn)證：
設(shè)有隨機(jī)變量(X,Y)赡麦，其聯(lián)合分布為：
條件熵H(Y|X)表示在已知隨機(jī)變量X的條件下隨機(jī)變量Y的不確定性，定義為在X給定的條件下帕识，Y的條件概率分布對(duì)X的數(shù)學(xué)期望：
這里泛粹，
當(dāng)上述定義式中的概率由數(shù)據(jù)估計(jì)（比如上一章提到的極大似然估計(jì)）得到時(shí)，所對(duì)應(yīng)的熵和條件熵分別稱為經(jīng)驗(yàn)熵和經(jīng)驗(yàn)條件熵肮疗。
Python實(shí)現(xiàn)條件熵的計(jì)算
def calcConditionalEntropy(dataSet, i, featList, uniqueVals):
'''
計(jì)算X_i給定的條件下晶姊，Y的條件熵
:param dataSet:數(shù)據(jù)集
:param i:維度i
:param featList: 數(shù)據(jù)集特征列表
:param uniqueVals: 數(shù)據(jù)集特征集合
:return:條件熵
'''
ce = 0.0
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet) / float(len(dataSet)) # 極大似然估計(jì)概率
ce += prob * calcShannonEnt(subDataSet) # ∑pH(Y|X=xi) 條件熵的計(jì)算
return ce
有了上述知識(shí)，就可以一句話說明什么叫信息增益了：信息增益表示得知特征X的信息而使類Y的信息的熵減少的程度伪货。形式化的定義如下：
這個(gè)差又稱為互信息（關(guān)于互信息的一個(gè)應(yīng)用：《基于互信息和左右信息熵的短語提取識(shí)別》）们衙，決策樹學(xué)習(xí)中的信息增益等價(jià)于訓(xùn)練數(shù)據(jù)集中類與特征的互信息。
用Python計(jì)算信息增益：
def calcInformationGain(dataSet, baseEntropy, i):
"""
計(jì)算信息增益
:param dataSet:數(shù)據(jù)集
:param baseEntropy:數(shù)據(jù)集中Y的信息熵
:param i: 特征維度i
:return: 特征i對(duì)數(shù)據(jù)集的信息增益g(dataSet|X_i)
"""
featList = [example[i] for example in dataSet] # 第i維特征列表
uniqueVals = set(featList) # 轉(zhuǎn)換成集合
newEntropy = calcConditionalEntropy(dataSet, i, featList, uniqueVals)
infoGain = baseEntropy - newEntropy # 信息增益超歌，就是熵的減少砍艾，也就是不確定性的減少
return infoGain
回到最初的問題，如何判斷一個(gè)特征的分類能力呢巍举？信息增益大的特征具有更強(qiáng)的分類能力脆荷。只要計(jì)算出各個(gè)特征的信息增益，找出最大的那一個(gè)就行。形式化的描述如下：
信息增益比
這種算法有個(gè)缺點(diǎn)蜓谋，信息增益的值是相對(duì)于訓(xùn)練數(shù)據(jù)集而言的梦皮，當(dāng)H(D)大的時(shí)候，信息增益值往往會(huì)偏大桃焕，這樣對(duì)H(D)小的特征不公平剑肯。改進(jìn)的方法是信息增益比：
注：上述公式分母應(yīng)該是特征A的 split information value ：
參考http://www.inf.unibz.it/dis/teaching/DWDM/slides2011/lesson5-Classification-2.pdf
由于《統(tǒng)計(jì)學(xué)習(xí)方法》是我看的第一本機(jī)器學(xué)習(xí)書籍，所以無法對(duì)其中錯(cuò)誤做出全面的勘誤观堂，請(qǐng)帶著質(zhì)疑的精神閱讀让网，謝謝。
Python代碼：
def calcInformationGainRate(dataSet, baseEntropy, i):
"""
計(jì)算信息增益比
:param dataSet:數(shù)據(jù)集
:param baseEntropy:數(shù)據(jù)集中Y的信息熵
:param i: 特征維度i
:return: 特征i對(duì)數(shù)據(jù)集的信息增益g(dataSet|X_i)
"""
return calcInformationGain(dataSet, baseEntropy, i) / baseEntropy
決策樹的生成
ID3算法
從根節(jié)點(diǎn)開始师痕，計(jì)算所有可能的特征的信息增益溃睹，選擇信息增益最大的特征作為當(dāng)前節(jié)點(diǎn)的特征，由特征的不同取值建立空白子節(jié)點(diǎn)胰坟，對(duì)空白子節(jié)點(diǎn)遞歸調(diào)用此方法因篇，直到所有特征的信息增益小于閥值或者沒有特征可選為止。
形式化的描述參考P63笔横，我上面的描述應(yīng)該很好懂了竞滓，老是截圖沒意思。
Python實(shí)現(xiàn)
還是直接上代碼比較痛快吹缔。
ID3特征選擇算法的Python實(shí)現(xiàn)：
def chooseBestFeatureToSplitByID3(dataSet):
"""
選擇最好的數(shù)據(jù)集劃分方式
:param dataSet:
:return:
"""
numFeatures = len(dataSet[0]) - 1 # 最后一列是分類
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 0.0
bestFeature = -1
for i in range(numFeatures): # 遍歷所有維度特征
infoGain = calcInformationGain(dataSet, baseEntropy, i)
if (infoGain > bestInfoGain): # 選擇最大的信息增益
bestInfoGain = infoGain
bestFeature = i
return bestFeature # 返回最佳特征對(duì)應(yīng)的維度
完整調(diào)用
# -*- coding:utf-8 -*-
# Filename: testTree.py
# Author：hankcs
# Date: 2014-04-19 下午9:19
###########中文支持################
import sys
from tree import *
reload(sys)
sys.setdefaultencoding('utf-8')
from pylab import *
mpl.rcParams['font.sans-serif'] = ['SimHei'] # 指定默認(rèn)字體
mpl.rcParams['axes.unicode_minus'] = False # 解決保存圖像時(shí)負(fù)號(hào)'-'顯示為方塊的問題
##################################
# 測(cè)試決策樹的構(gòu)建
myDat, labels = createDataSet()
myTree = createTree(myDat, labels)
# 繪制決策樹
import treePlotter
treePlotter.createPlot(myTree)
此處的可視化使用了《Machine Learning in Action》中的代碼：
# -*- coding:utf-8 -*-
# Filename: treePlotter.py
# Author：hankcs
# Date: 2015/2/9 21:24
import matplotlib.pyplot as plt
# 定義文本框和箭頭格式
decisionNode = dict(boxstyle="round4", color='#3366FF') #定義判斷結(jié)點(diǎn)形態(tài)
leafNode = dict(boxstyle="circle", color='#FF6633') #定義葉結(jié)點(diǎn)形態(tài)
arrow_args = dict(arrowstyle="<-", color='g') #定義箭頭
#繪制帶箭頭的注釋
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction',
xytext=centerPt, textcoords='axes fraction',
va="center", ha="center", bbox=nodeType, arrowprops=arrow_args)
#計(jì)算葉結(jié)點(diǎn)數(shù)
def getNumLeafs(myTree):
numLeafs = 0
firstStr = myTree.keys()[0]
secondDict = myTree[firstStr]
for key in secondDict.keys():
if type(secondDict[key]).__name__ == 'dict':
numLeafs += getNumLeafs(secondDict[key])
else:
numLeafs += 1
return numLeafs
#計(jì)算樹的層數(shù)
def getTreeDepth(myTree):
maxDepth = 0
firstStr = myTree.keys()[0]
secondDict = myTree[firstStr]
for key in secondDict.keys():
if type(secondDict[key]).__name__ == 'dict':
thisDepth = 1 + getTreeDepth(secondDict[key])
else:
thisDepth = 1
if thisDepth > maxDepth:
maxDepth = thisDepth
return maxDepth
#在父子結(jié)點(diǎn)間填充文本信息
def plotMidText(cntrPt, parentPt, txtString):
xMid = (parentPt[0] - cntrPt[0]) / 2.0 + cntrPt[0]
yMid = (parentPt[1] - cntrPt[1]) / 2.0 + cntrPt[1]
createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)
def plotTree(myTree, parentPt, nodeTxt):
numLeafs = getNumLeafs(myTree)
depth = getTreeDepth(myTree)
firstStr = myTree.keys()[0]
cntrPt = (plotTree.xOff + (1.0 + float(numLeafs)) / 2.0 / plotTree.totalW, plotTree.yOff)
plotMidText(cntrPt, parentPt, nodeTxt) #在父子結(jié)點(diǎn)間填充文本信息
plotNode(firstStr, cntrPt, parentPt, decisionNode) #繪制帶箭頭的注釋
secondDict = myTree[firstStr]
plotTree.yOff = plotTree.yOff - 1.0 / plotTree.totalD
for key in secondDict.keys():
if type(secondDict[key]).__name__ == 'dict':
plotTree(secondDict[key], cntrPt, str(key))
else:
plotTree.xOff = plotTree.xOff + 1.0 / plotTree.totalW
plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
plotTree.yOff = plotTree.yOff + 1.0 / plotTree.totalD
def createPlot(inTree):
fig = plt.figure(1, facecolor='white')
fig.clf()
axprops = dict(xticks=[], yticks=[])
createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)
plotTree.totalW = float(getNumLeafs(inTree))
plotTree.totalD = float(getTreeDepth(inTree))
plotTree.xOff = -0.5 / plotTree.totalW;
plotTree.yOff = 1.0;
plotTree(inTree, (0.5, 1.0), '')
plt.show()
python實(shí)現(xiàn)
def chooseBestFeatureToSplitByC45(dataSet):
"""
選擇最好的數(shù)據(jù)集劃分方式
:param dataSet:
:return:
"""
numFeatures = len(dataSet[0]) - 1 # 最后一列是分類
baseEntropy = calcShannonEnt(dataSet)
bestInfoGainRate = 0.0
bestFeature = -1
for i in range(numFeatures): # 遍歷所有維度特征
infoGainRate = calcInformationGainRate(dataSet, baseEntropy, i)
if (infoGainRate > bestInfoGainRate): # 選擇最大的信息增益
bestInfoGainRate = infoGainRate
bestFeature = i
return bestFeature # 返回最佳特征對(duì)應(yīng)的維度
調(diào)用方法只需加個(gè)參數(shù)：
myTree = createTree(myDat, labels, chooseBestFeatureToSplitByC45)
可視化
并沒有變化商佑。
決策樹的剪枝
決策樹很容易發(fā)生過擬合，過擬合的原因在于學(xué)習(xí)的時(shí)候過多地考慮如何提高對(duì)訓(xùn)練數(shù)據(jù)的正確分類涛菠，從而構(gòu)建出過于復(fù)雜的決策樹莉御。解決這個(gè)問題的辦法就是簡(jiǎn)化已生成的決策樹，也就是剪枝俗冻。
決策樹的剪枝往往通過極小化決策樹整體的損失函數(shù)或代價(jià)函數(shù)來實(shí)現(xiàn)。
設(shè)決策樹T的葉節(jié)點(diǎn)有|T|個(gè)牍颈，t是某個(gè)葉節(jié)點(diǎn)迄薄，t有Nt個(gè)樣本點(diǎn)，其中歸入k類的樣本點(diǎn)有Ntk個(gè)煮岁，Ht(T)為葉節(jié)點(diǎn)t上的經(jīng)驗(yàn)熵讥蔽，α≥0為參數(shù)，則損失函數(shù)可以定義為：
其中經(jīng)驗(yàn)熵Ht(T)為：
表示葉節(jié)點(diǎn)t所代表的類別的不確定性画机。損失函數(shù)對(duì)它求和表示所有被導(dǎo)向該葉節(jié)點(diǎn)的樣本點(diǎn)所帶來的不確定的和的和冶伞。我沒有多打一個(gè)“的和”，第二個(gè)是針對(duì)葉節(jié)點(diǎn)t說的步氏。
在損失函數(shù)中响禽，將右邊第一項(xiàng)記作：
則損失函數(shù)可以簡(jiǎn)單記作：
C(T)表示模型對(duì)訓(xùn)練數(shù)據(jù)的預(yù)測(cè)誤差，即模型與訓(xùn)練數(shù)據(jù)的擬合程度，|T|表示模型復(fù)雜度芋类，參數(shù)α≥0控制兩者之間的影響隆嗅，α越大，模型越簡(jiǎn)單侯繁，α=0表示不考慮復(fù)雜度胖喳。
剪枝，就是當(dāng)α確定時(shí)贮竟，選擇損失函數(shù)最小的模型丽焊。子樹越大C(T)越小，但是α|T|越大咕别，損失函數(shù)反映的是兩者的平衡技健。
決策樹的生成過程只考慮了信息增益或信息增益比，只考慮更好地?cái)M合訓(xùn)練數(shù)據(jù)顷级，而剪枝過程則考慮了減小復(fù)雜度凫乖。前者是局部學(xué)習(xí)，后者是整體學(xué)習(xí)弓颈。
樹的剪枝算法
從每個(gè)葉節(jié)點(diǎn)往上走帽芽，走了后如果損失函數(shù)減小了，則減掉葉節(jié)點(diǎn)翔冀，將父節(jié)點(diǎn)作為葉節(jié)點(diǎn)导街。如圖：
說是這么說，實(shí)際上如果葉節(jié)點(diǎn)有多個(gè)纤子，那么父節(jié)點(diǎn)變成葉節(jié)點(diǎn)后搬瑰，新葉節(jié)點(diǎn)到底應(yīng)該選擇原來的葉節(jié)點(diǎn)中的哪一種類別呢？大概又是多數(shù)表決吧控硼，原著并沒有深入展開泽论。
CART算法
分類與回歸樹（CART）模型同樣由特征選取、樹的生成和剪枝組成卡乾，既可以用于分類也可以用于回歸翼悴。CART假設(shè)決策樹是二叉樹，內(nèi)部節(jié)點(diǎn)特征的取值為是和否幔妨，對(duì)應(yīng)一個(gè)實(shí)例的特征是否是這樣的鹦赎。決策樹遞歸地二分每個(gè)特征，將輸入空間劃分為有限個(gè)單元误堡。
CART生成
就是遞歸地構(gòu)建二叉決策樹的過程古话。對(duì)回歸樹用平方誤差最小化準(zhǔn)則，對(duì)分類樹用基尼指數(shù)最小化準(zhǔn)則锁施，進(jìn)行特征選取陪踩，生成二叉樹杖们。
1、回歸樹
回歸樹與分類樹在數(shù)據(jù)集上的不同就是數(shù)據(jù)集的輸出部分不是類別膊毁，而是連續(xù)變量胀莹。
假設(shè)輸入空間已經(jīng)被分為M個(gè)單元
，分別對(duì)應(yīng)輸出值cm婚温，于是回歸樹模型可以表示為：
回歸樹的預(yù)測(cè)誤差：
那么輸出值就是使上面誤差最小的值描焰，也就是均值：
難點(diǎn)在于怎么劃分，一種啟發(fā)式的方法（其實(shí)就是暴力搜索吧）：
遍歷所有輸入變量栅螟，選擇第j個(gè)變量和它的值s作為切分變量和切分點(diǎn)荆秦，將空間分為兩個(gè)區(qū)域：
然后計(jì)算兩個(gè)區(qū)域的平方誤差，求和力图，極小化這個(gè)和步绸，具體的，就是：
當(dāng)j最優(yōu)化的時(shí)候吃媒，就可以將切分點(diǎn)最優(yōu)化：
遞歸調(diào)用此過程瓤介，這種回歸樹通常稱為最小二乘回歸樹。
2赘那、分類樹
與回歸樹算法流程類似刑桑，只不過選擇的是最優(yōu)切分特征和最優(yōu)切分點(diǎn)，并采用基尼指數(shù)衡量募舟§舾基尼指數(shù)定義：
對(duì)于給定數(shù)據(jù)集D，其基尼指數(shù)是：
Ck是屬于第k類的樣本子集拱礁，K是類的個(gè)數(shù)琢锋。Gini(D)反應(yīng)的是D的不確定性（與熵類似），分區(qū)的目標(biāo)就是降低不確定性呢灶。
D根據(jù)特征A是否取某一個(gè)可能值a而分為D1和D2兩部分：
則在特征A的條件下吴超，D的基尼指數(shù)是：
有了上述知識(shí)儲(chǔ)備，可以給出CART生成算法的偽碼：
設(shè)節(jié)點(diǎn)的當(dāng)前數(shù)據(jù)集為D鸯乃，對(duì)D中每一個(gè)特征A烛芬，對(duì)齊每個(gè)值a根據(jù)D中樣本點(diǎn)是否滿足A==a分為兩部分，計(jì)算基尼指數(shù)飒责。對(duì)所有基尼指數(shù)選擇最小的，對(duì)應(yīng)的特征和切分點(diǎn)作為最優(yōu)特征和最優(yōu)切分點(diǎn)仆潮，生成兩個(gè)子節(jié)點(diǎn)宏蛉，將對(duì)應(yīng)的兩個(gè)分區(qū)分配過去，然后對(duì)兩個(gè)子節(jié)點(diǎn)遞歸性置。
CART剪枝
在上面介紹的損失函數(shù)中拾并，當(dāng)α固定時(shí)，一定存在使得損失函數(shù)最小的子樹，記為復(fù)雜度=Tα嗅义，α偏大Tα就偏小屏歹。設(shè)對(duì)α遞增的序列，對(duì)應(yīng)的最優(yōu)子樹序列為Tn之碗，子樹序列第一棵包含第二棵蝙眶，依次類推。
從T0開始剪枝褪那，對(duì)它內(nèi)部的任意節(jié)點(diǎn)t幽纷，只有t這一個(gè)節(jié)點(diǎn)的子樹的損失函數(shù)是：
以t為根節(jié)點(diǎn)的子樹的損失函數(shù)是：
當(dāng)α充分小，肯定有
這個(gè)不等式的意思是復(fù)雜模型在復(fù)雜度影響力小的情況下?lián)p失函數(shù)更小博敬。
當(dāng)α增大到某一點(diǎn)友浸，這個(gè)不等式的符號(hào)會(huì)反過來。
只要
偏窝，損失函數(shù)值就相同收恢，但是t更小啊，所以t更可取祭往，于是把Tt剪枝掉伦意。
為此，對(duì)每一個(gè)t链沼，計(jì)算
表示損失函數(shù)的減少程度默赂，從T中剪枝掉g(t)最小的Tt，取新的α=g(t)括勺，直到根節(jié)點(diǎn)缆八。這樣就得到了一個(gè)子樹序列，對(duì)此序列疾捍，應(yīng)用獨(dú)立的驗(yàn)證數(shù)據(jù)集交叉驗(yàn)證奈辰，選取最優(yōu)子樹，剪枝完畢乱豆。
