機器學習及應用第3章-決策樹課件

1、第03章 決策樹決策樹ID3算法C4.5算法CART算法3.1 引言3.1 引言決策樹（Decision Tree）是一種用于監(jiān)督學習的層次模型。1979年，J.R.Quinlan創(chuàng)立了ID3算法原型。分別于1983年和1986年對ID3進行了總結和改進，確定了決策樹模型。決策樹可以是二叉樹也可以是多叉樹，每個非葉結點表示一個特征屬性上的測試，每個分支代表該特征屬性在某個值域上的輸出，而每個葉結點存放一個（分類）類別。使用決策樹進行決策的過程就是從根結點開始，測試待分類項中相應的特征屬性，并按照其值選擇輸出分支，直到到達葉子結點，將葉子結點存放的類別作為決策結果。決策樹的決策過程非常直觀，容易

2、被人理解。目前，決策樹已經(jīng)成功運用于醫(yī)學、制造產(chǎn)業(yè)、天文學、分支生物學以及商業(yè)等諸多領域。3.2 決策樹一個簡單的互動游戲：20問題約定：長方形結點代表判斷模塊，橢圓形結點代表終止模塊。那么一個簡化的垃圾郵件分類系統(tǒng)。3.2.1 決策樹的基本思想程序設計中，最基本的語句條件分支結構就是if-then結構。而最早的決策樹就是利用這類結構分隔數(shù)據(jù)的一種分類學習方法。3.2 決策樹3.2.2 決策樹的構造表3-1 活躍用戶調查表統(tǒng)計人數(shù)年齡收入是否學生性別是否購買付費游戲裝備64青高不是男不買64青高不是女不買128中高不是男買60老中等不是男買64老低是男買64老低是女不買64中低是女買128青中

3、等不是男不買64青低是男買132老中等是男買64青中等是女買32中中等不是女買32中高是男買64老中等不是女不買CLS(Concept Learning System)算法的思想：首先，將決策樹設計為三類結點，根結點、葉子結點和內部結點。3.2 決策樹3.2.2 決策樹的構造選年齡特征作為根結點，將所有的樣本分為老、中、青三個集合，構成決策樹的第一層。表3-2 按“年齡特征”劃分的表格統(tǒng)計人數(shù)年齡收入是否學生性別是否購買付費游戲裝備64青高不是男不買64青高否女不買128青中等否男不買64青低是男買64青中等是女買128中高不是男買64中低是女買32中中等不是女買32中高是男買60老中等不是男

4、買64老低是男買64老低是女不買132老中等是男買64老中等不是女不買年齡特征為“中”，都會購買游戲裝備。（純結點，不需要再劃分了）3.2 決策樹3.2.2 決策樹的構造接著，將年齡特征等于“青”的選項剪切出一張表格，再選擇第二個特征：收入。表3-3 按“青年-收入”劃分的表格統(tǒng)計人數(shù)年齡收入是否學生性別是否購買付費游戲裝備64青高不是男不買64青高不是女不買128青中等不是男不買64青低是男買64青中等是女買對于“青”年，如果收入“高”，則不會購買游戲裝備。（純結點）對于“青”年，如果收入“低”，則會購買游戲裝備。（純結點）3.2 決策樹3.2.2 決策樹的構造最后，繼續(xù)劃分“中等”收入的下

5、一個特征：是否學生表3-4 按“青年-中等-是否學生”劃分的表格統(tǒng)計人數(shù)年齡收入是否學生性別是否購買付費游戲裝備128 青中等不是男不買64青中等是女買對于“青”年-“中等”收入，如果不是學生，則不會購買游戲裝備。（純結點）對于“青”年-“中等”收入，如果是學生，則會購買游戲裝備。（純結點）3.2 決策樹3.2.2 決策樹的構造按年齡特征-收入-是否學生劃分的決策樹分支3.2 決策樹3.2.2 決策樹的構造表3-5 按老年-性別劃分的表格統(tǒng)計人數(shù)年齡收入是否學生性別是否購買付費游戲裝備60 老 中等不是男 買132 老 中等是 男買64 老 低 是 男 買64 老 中等不是女 不買64 老 低

6、 是 女不買接著，將年齡特征等于“老”年的選項剪切出一張表格，再選擇第二個特征：性別。對于“老”年-“男”性，則會購買游戲裝備。（純結點）對于“老”年-“女”性，則不會購買游戲裝備。（純結點）3.2 決策樹3.2.2 決策樹的構造活躍用戶的分類決策樹3.2 決策樹3.2.2 決策樹的構造非活躍用戶調查決策樹的概率計算（人數(shù)統(tǒng)計）3.2 決策樹3.2.2 決策樹的構造構造決策樹的關鍵步驟是分裂屬性在某個結點處按照某一特征屬性的不同劃分構造不同的分支，其目標是讓各個分裂子集盡可能地“純”。所謂盡可能“純”就是盡量讓一個分裂子集中待分類項屬于同一類別。分裂屬性分為三種不同的情況。屬性是離散值，且不要

7、求生成二叉決策樹。屬性是離散值，且要求生成二叉決策樹。屬性是連續(xù)值。此時確定一個值作為分裂點。構造決策樹的關鍵性內容是進行屬性選擇度量，它決定了拓撲結構及分裂點的選擇。屬性選擇度量算法有很多，一般使用自頂向下遞歸分治法，并采用不回溯的貪心策略。3.2 決策樹3.2.3 決策樹的算法框架決策樹主函數(shù)輸入需要分類的數(shù)據(jù)集和類別標簽；計算最優(yōu)特征子函數(shù)：根據(jù)某種分類規(guī)則得到最優(yōu)劃分特征，并創(chuàng)建特征的劃分結點；劃分數(shù)據(jù)集子函數(shù)：按照該特征的每個取值劃分數(shù)據(jù)集為若干部分；根據(jù)劃分子函數(shù)的計算結果構建出新的結點，作為決策樹生長出的新分支；檢驗是否終止；將劃分的新結點包含的數(shù)據(jù)集和類別標簽作為輸入，遞歸執(zhí)行

8、上述各步驟。3.2 決策樹3.2.2 決策樹的構造計算最優(yōu)特征子函數(shù)ID3算法以信息增益，C4.5算法以信息增益率，CART則是以結點方差的大小等特征，作為屬性選擇度量方法。選擇分裂后信息增益最大的屬性進行分裂。劃分數(shù)據(jù)集函數(shù)分隔數(shù)據(jù)，有時需要刪除某個特征軸所在的數(shù)據(jù)類，返回剩余的數(shù)據(jù)集；有時干脆將數(shù)據(jù)集一分為二。分類器通過遍歷整棵決策樹，使測試集數(shù)據(jù)找到?jīng)Q策樹中葉子結點對應的類別標簽。3.2 決策樹3.2.4 信息增益首先，將屬性特征數(shù)字化，年齡=0（青），1（中），2（老）；收入=0（高），1（中等），2（低）；是否學生=0（是），1（不是）；性別=0（男），1（女）然后，“最好”地分裂結

9、點，將數(shù)據(jù)集從無序變?yōu)橛行驗榱撕饬恳粋€事物特征取值的有（無）序程度，一個重要的概念：信息熵用來衡量一個隨機變量出現(xiàn)的期望值，一個變量的信息熵越大，那么它蘊含的情況（景）就越多，也就是說需要更多的信息才能完全確定它。信息熵的公式表示。3.2 決策樹3.2.4 信息增益兩類問題的熵函數(shù)3.2 決策樹3.2.4 信息增益3.2 決策樹3.2.4 信息增益3.2 決策樹3.2.4 信息增益3.2 決策樹3.2.4 信息增益from numpy import *def calcShannonEnt(dataSet): 輸入：數(shù)據(jù)集 輸出：數(shù)據(jù)集的香農(nóng)熵 描述：計算給定數(shù)據(jù)集的香農(nóng)熵 num = len(

10、 dataSet ) # 樣本集總數(shù) classList = c-1 for c in dataSet # 抽取分類信息 labelCounts = # 詞典形式存儲類別計數(shù) for cs in set(classList): # 對每個類別計數(shù)信息熵的程序代碼如下：3.2 決策樹3.2.4 信息增益labelCountscs = classList.count( cs ) shannonEnt = 0.0 # 信息熵 for key in labelCounts: prob = labelCountskey / float(num) shannonEnt -= prob * log2(pro

11、b) return shannonEntdef CreateDataSet(): dataSet = 1, 1, Yes, 1, 1, Yes, 1, 0, No, 0, 1, No, 0, 1, No labels = no surfacing, flippers3.2 決策樹3.2.4 信息增益 return dataSet, labelsdef CreateDataSet(): dataSet = 1, 1, Yes, 1, 1, Yes, 1, 0, No, 0, 1, No, 0, 1, No labels = no surfacing, flippers return dataSe

12、t, labelsmyDat, labels = CreateDataSet()print(calcShannonEnt(myDat)運行結果：0.9709505944553.3 ID3決策樹3.3.1 ID3算法表3-6天氣與打球關聯(lián)關系表DayOutlookTempHumidityWindyPlayD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainMildHighWeakYesD5RainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCool

13、NormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainMildHighStrongNo3.3 ID3決策樹3.3.1 ID3算法3.3 ID3決策樹3.3.1 ID3算法3.3 ID3決策樹3.3.1 ID3算法3.3 ID3決策樹3.3.1 ID3算法ID3算法中根據(jù)信息論的信息增益評估和選擇特征。每次選

14、擇信息增益最大的候選特征，作為判斷模塊。通過裁剪、合并相鄰的無法產(chǎn)生大量信息增益的葉子結點，去除過度匹配（過擬合）的問題。信息增益與屬性的值域大小成正比。屬性取值種類越多，越有可能成為分裂屬性。ID3也不能處理連續(xù)分布的數(shù)據(jù)特征。3.3 ID3決策樹3.3.2 ID3的實現(xiàn)from math import log2import treePlotterclass ID3Tree(object): def _init_(self): self.tree = # ID3 Tree self.dataSet = # 數(shù)據(jù)集 self.labels = # 標簽集 def getDataSet(self

15、, dataset, labels): self.dataSet = dataset self.labels = labels def train(self): # labels = copy.deepcopy(self.labels) labels = self.labels: self.tree = self.buildTree(self.dataSet, labels)3.3 ID3決策樹3.3.2 ID3的實現(xiàn) def buildTree(self, dataSet, labels): classList = ds-1 for ds in dataSet # 提取樣本的類別 if cl

16、assList.count(classList0) = len(classList): # 單一類別 return classList0 if len(dataSet0) = 1: # 沒有屬性需要劃分了！ return self.classify(classList) bestFeat = self.findBestSplit(dataSet) # 選取最大增益的屬性序號 bestFeatLabel = labelsbestFeat tree = bestFeatLabel: # 構造一個新的樹結點 del (labelsbestFeat) # 從總屬性列表中去除最大增益屬性 featVal

17、ues = dsbestFeat for ds in dataSet # 抽取最大增益屬性的取值列表 uniqueFeatValues = set(featValues) # 選取最大增益屬性的數(shù)值類別3.3 ID3決策樹3.3.2 ID3的實現(xiàn)for value in uniqueFeatValues: # 對于每一個屬性類別 subLabels = labels: subDataSet = self.splitDataSet(dataSet, bestFeat, value) # 分裂結點 subTree = self.buildTree(subDataSet, subLabels) #

18、遞歸構造子樹 treebestFeatLabelvalue = subTree return tree # 計算出現(xiàn)次數(shù)最多的類別標簽 def classify(self, classList): items = dict(classList.count(i), i) for i in classList) return itemsmax(items.keys()3.3 ID3決策樹3.3.2 ID3的實現(xiàn) # 計算最優(yōu)特征 def findBestSplit(self, dataset): numFeatures = len(dataset0) - 1 baseEntropy = self.

19、calcShannonEnt(dataset) # 基礎熵 num = len(dataset) # 樣本總數(shù) bestInfoGain = 0.0 bestFeat = -1 # 初始化最優(yōu)特征向量軸 # 遍歷數(shù)據(jù)集各列，尋找最優(yōu)特征軸 for i in range(numFeatures): featValues = dsi for ds in dataset uniqueFeatValues = set(featValues) newEntropy = 0.0 # 按列和唯一值，計算信息熵 for val in uniqueFeatValues: subDataSet = self.sp

20、litDataSet(dataset, i, val) prob = len(subDataSet) / float(num) # 子集中的概率 newEntropy += prob *3.3 ID3決策樹3.3.2 ID3的實現(xiàn) self.calcShannonEnt(subDataSet) infoGain = baseEntropy - newEntropy # 信息增益 if infoGain bestInfoGain: # 挑選最大值 bestInfoGain = baseEntropy - newEntropy bestFeat = i return bestFeat # 從dat

21、aset數(shù)據(jù)集的feat特征中，選取值為value的數(shù)據(jù) def splitDataSet(self, dataset, feat, values): retDataSet = for featVec in dataset: if featVecfeat = values: reducedFeatVec = featVec:feat reducedFeatVec.extend(featVecfeat + 1:) retDataSet.append(reducedFeatVec) return retDataSet3.3 ID3決策樹3.3.2 ID3的實現(xiàn) # 計算dataSet的信息熵 de

22、f calcShannonEnt(self, dataSet): num = len(dataSet) # 樣本集總數(shù) classList = c-1 for c in dataSet # 抽取分類信息 labelCounts = for cs in set(classList): # 對每個分類進行計數(shù) labelCountscs = classList.count(cs)shannonEnt = 0.0 for key in labelCounts: prob = labelCountskey / float(num) shannonEnt -= prob * log2(prob) ret

23、urn shannonEnt # 預測。對輸入對象進行ID3分類 def predict(self, tree, newObject): 3.3 ID3決策樹3.3.2 ID3的實現(xiàn)# 判斷輸入值是否為“dict” while type(tree)._name_ = dict: key = list(tree.keys()0 tree = treekeynewObjectkey return treeif _name_ = _main_: def createDataSet(): dataSet = 2, 1, 0, 1, No, 2, 1, 0, 0, No, 0, 1, 0, 1, Yes

24、, 1, 2, 0, 1, Yes, 1, 0, 1, 1, Yes, 1, 0, 1, 0, No, 0, 0, 1, 0, Yes, 2, 2, 0, 1, No, 2, 0, 1, 1, Yes,3.3 ID3決策樹3.3.2 ID3的實現(xiàn) 1, 2, 1, 1, Yes, 2, 2, 1, 0, Yes, 0, 2, 0, 0, Yes, 0, 1, 1, 1, Yes, 1, 2, 0, 0, No features = Outlook, Temp, Humidity, Wind # features = no surfacing,flippers return dataSet, f

25、eaturesid3 = ID3Tree() # 創(chuàng)建一個ID3決策樹 ds, labels = createDataSet() id3.getDataSet(ds, labels) id3.train() # 訓練ID3決策樹 print(id3.tree) # 輸出ID3決策樹 print(id3.predict(id3.tree,Outlook:2,Temp:1,Humidity:0,Wind:1) treePlotter.createPlot(id3.tree)3.3 ID3決策樹3.3.2 ID3的實現(xiàn)運行結果Outlook: 0: Yes, 1: Wind: 0: No, 1: Y

26、es, 2: Humidity: 0: No, 1: YesNoID3算法對天氣-打球關系的決策樹3.4 C4.5決策樹3.4.1 C4.5算法3.4 C4.5決策樹3.4.1 C4.5算法C4.5算法使用信息增益率代替信息增益，進行特征選擇，克服了信息增益選擇特征時偏向于特征值個數(shù)較多的不足；其具體算法步驟與ID3類似；C4.5能夠完成對連續(xù)屬性的離散化處理；能夠對不完整數(shù)據(jù)進行處理；分類規(guī)則易于理解、準確率較高；效率低，只適合于能夠駐留于內存的數(shù)據(jù)集。3.4 C4.5決策樹3.4.2 C4.5的實現(xiàn)from math import log2import treePlotterfrom nu

27、mpy import *# 計算信息熵def calcShannonEnt(dataSet): num = len( dataSet ) # 樣本集總數(shù) classList = c-1 for c in dataSet # 抽取分類信息 labelCounts = for cs in set(classList): # 對每個分類進行計數(shù) labelCountscs = classList.count( cs ) shannonEnt = 0.0 # 信息熵 for key in labelCounts: prob = labelCountskey / float(num) shannonEn

28、t -= prob * log2(prob) return shannonEnt3.4 C4.5決策樹3.4.2 C4.5的實現(xiàn)# 從dataset數(shù)據(jù)集的feat特征中，選取值為value的數(shù)據(jù)def splitDataSet(dataset,feat,value): retDataSet = for featVec in dataset: if featVecfeat = value: reducedFeatVec = featVec:feat reducedFeatVec.extend(featVecfeat+1:) retDataSet.append(reducedFeatVec) r

29、eturn retDataSet# 計算最優(yōu)特征def getBestFeat(dataSet): numFeats = len(dataSet0:-1) num = len(dataSet) newEntropy = calcShannonEnt(dataSet) ConditionEntropy = # 初始化條件熵 splitInfo = # for C4.5 計算增益率 allFeatVList = 3.4 C4.5決策樹3.4.2 C4.5的實現(xiàn)# 計算所有屬性的信息增益值 for fe in range(numFeats): # 對于每個屬性 featList = datafe f

30、or data in dataSet splitI, featureValueList = calcSplitInfo(featList) allFeatVList.append(featureValueList) splitInfo.append(splitI) resultGain = 0.0 # 計算第fe個屬性的信息增益 for value in featureValueList: subSet = splitDataSet(dataSet, fe, value) appearNum = float(len(subSet) subEntropy = calcShannonEnt(sub

31、Set) resultGain += (appearNum / num) * subEntropy ConditionEntropy.append( resultGain) # 總條件熵 infoGainArray = newEntropy * ones(numFeats) - array(ConditionEntropy) infoGainRatio = infoGainArray / array(splitInfo) # C4.5信息增益 bestFeatureIndex = argsort(-infoGainRatio)0 return bestFeatureIndex, allFeat

32、VListbestFeatureIndex3.4 C4.5決策樹3.4.2 C4.5的實現(xiàn)# 計算劃分信息def calcSplitInfo(featureVList): numEntries = len( featureVList ) featureValueSetList = list(set(featureVList) valueCounts = featureVList.count(featVect) for featVect in featureValueSetList # calc shannonEnt pList = float(item) / numEntries for it

33、em in valueCounts iList = item * math.log2(item) for item in pList splitInfo = -sum(iList) return splitInfo, featureValueSetList# 計算出現(xiàn)次數(shù)最多的類別標簽def majorityCnt(classList): items = dict(classList.count(i), i) for i in classList) return itemsmax(items.keys()3.4 C4.5決策樹3.4.2 C4.5的實現(xiàn)# 構造C4.5分類決策樹def C45T

34、ree(dataSet, labels): classList = ds-1 for ds in dataSet # 提取樣本的類別 if classList.count(classList0)=len(classList): # 單一類別 return classList0 if len(dataSet0)=1:# 沒有屬性需要劃分了！ return majorityCnt(classList) bestFeat, featValueList = getBestFeat(dataSet)# 選取最大增益的屬性序號 bestFeatLabel = labelsbestFeat myTree =

35、 bestFeatLabel: # 構造一個新的樹結點 del (labelsbestFeat) # 從總屬性列表中去除最大增益屬性 for value in featValueList: # 對于每一個屬性類別 subLabels = labels: subDataSet = splitDataSet(dataSet,bestFeat,value) # 分裂結點 myTreebestFeatLabelvalue = C45Tree(subDataSet,labels) # 遞歸構造子樹 return myTree3.4 C4.5決策樹3.4.2 C4.5的實現(xiàn)def classify(inp

36、utTree, featLabels, testVec): 輸入：決策樹，分類標簽，測試數(shù)據(jù) 輸出：決策結果 描述：應用C4.5決策樹進行分類 firstStr = list(inputTree.keys()0 secondDict = inputTreefirstStr featIndex = featLabels.index(firstStr) for key in secondDict.keys(): if testVecfeatIndex = key: if type(secondDictkey)._name_ = dict: classLabel = classify(secondD

37、ictkey, featLabels, testVec) else: classLabel = secondDictkey return classLabel3.4 C4.5決策樹3.4.2 C4.5的實現(xiàn)def predict(inputTree, featLabels, testDataSet): 輸入：決策樹，分類標簽，測試數(shù)據(jù)集 輸出：決策結果 描述：運行C4.5決策樹，對輸入數(shù)據(jù)進行分類 classLabelAll = for testVec in testDataSet: classLabelAll.append(classify(inputTree, featLabels, te

38、stVec) return classLabelAll3.4 C4.5決策樹3.4.2 C4.5的實現(xiàn)def createDataSet(): dataSet = 2, 1, 0, 1, No, 2, 1, 0, 0, No, 0, 1, 0, 1, Yes, 1, 2, 0, 1, Yes, 1, 0, 1, 1, Yes, 1, 0, 1, 0, No, 0, 0, 1, 0, Yes, 2, 2, 0, 1, No, 2, 0, 1, 1, Yes, 1, 2, 1, 1, Yes, 2, 2, 1, 0, Yes, 0, 2, 0, 0, Yes, 0, 1, 1, 1, Yes, 1

39、, 2, 0, 0, No labels = Outlook, Temp, Humidity, Windy return dataSet, labels3.4 C4.5決策樹3.4.2 C4.5的實現(xiàn)def createTestSet(): testSet = 0, 1, 0, 0, 0, 2, 1, 0, 2, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 2, 1, 0, 1 return testSetdef main(): dataSet, labels = createDataSet() labels_tmp = labels: # 復制c

40、reateTree會改變labels desicionTree = C45Tree(dataSet, labels_tmp) print(desicionTree:n, desicionTree) treePlotter.createPlot(desicionTree) testSet = createTestSet() print(predict result:n, predict(decisionTree, labels, testSet)if _name_ = _main_: main()3.4 C4.5決策樹3.4.2 C4.5的實現(xiàn)decisionTree: Outlook: 0:

41、Yes, 1: Windy: 0: No, 1: Yes, 2: Humidity: 0: No, 1: Yespredict result: Yes, Yes, Yes, Yes, Yes, No, No運行結果3.5 sklearn與回歸樹3.5.1 回歸算法原理CART（Classification And Regression Tree）算法是目前決策樹算法中最為成熟的一類算法，應用范圍也比較廣泛。它既可用于分類，也可用于預測。預測時，CART使用最小剩余方差來判定回歸樹的最優(yōu)劃分，確保劃分之后的子樹與樣本點的誤差方差最小。CART算法的主要流程：輸入需要分類的數(shù)據(jù)集和類別標簽。使用最

42、小剩余方差判定回歸樹的最優(yōu)劃分，并創(chuàng)建特征的劃分結點。最小剩余方差子函數(shù)，計算數(shù)據(jù)集各列的最優(yōu)劃分方差、劃分列、劃分值。在劃分結點，使用二分數(shù)據(jù)集子函數(shù)將數(shù)據(jù)集劃分為兩部分。根據(jù)二分數(shù)據(jù)的結果，構建出新的左、右結點，作為樹生長出的兩個分支。檢驗是否符合遞歸的終止條件。將劃分的新結點包含的數(shù)據(jù)集和類別標簽作為輸入，遞歸執(zhí)行上述步驟。3.5 sklearn與回歸樹3.5.1 回歸算法原理CART（Classification And Regression Tree）算法是目前決策樹算法中最為成熟的一類算法，應用范圍也比較廣泛。它既可用于分類，也可用于預測。預測時，CART使用最小剩余方差來判定回歸

43、樹的最優(yōu)劃分，確保劃分之后的子樹與樣本點的誤差方差最小。CART算法的主要流程：輸入需要分類的數(shù)據(jù)集和類別標簽。使用最小剩余方差判定回歸樹的最優(yōu)劃分，并創(chuàng)建特征的劃分結點。最小剩余方差子函數(shù)，計算數(shù)據(jù)集各列的最優(yōu)劃分方差、劃分列、劃分值。在劃分結點，使用二分數(shù)據(jù)集子函數(shù)將數(shù)據(jù)集劃分為兩部分。根據(jù)二分數(shù)據(jù)的結果，構建出新的左、右結點，作為樹生長出的兩個分支。檢驗是否符合遞歸的終止條件。將劃分的新結點包含的數(shù)據(jù)集和類別標簽作為輸入，遞歸執(zhí)行上述步驟。3.5 sklearn與回歸樹3.5.2 最小剩余方差法CART采用最小剩余方差法來劃分結點，算法描述如下：首先令最佳方差為無限大 bestVar =

44、 inf；依次遍歷所有特征列以及每個特征列的所有樣本點，在每個樣本點上二分數(shù)據(jù)集；計算二分數(shù)據(jù)集的總方差currentVar，如果currentVar bestVar，則bestVar = currentVar；返回計算的最優(yōu)分支特征列、分支特征值，以及左右分支子數(shù)據(jù)集。3.5 sklearn與回歸樹3.5.3 剪枝策略由于使用了連續(xù)型數(shù)據(jù)，CART可以生長出大量的分支樹，為了避免過擬合的問題，預測樹采用了剪枝的方法。方法有兩類：先剪枝，當結點的劃分子集某個標準低于預定義的閾值時，子集劃分將終止。選取適當?shù)拈撝当容^困難，不必生成整棵決策樹，算法簡單，效率高，適合大規(guī)模問題的粗略估計。后剪枝，遞歸估算每個內部結點所覆蓋樣本結點的誤判率，如果內部結點低于這個誤判率就將其變成葉子結點，該葉子結點的類別標簽由原內部結點的最優(yōu)葉子結點所決定。3.5 sklearn與回歸樹3.5.3 剪枝策略3.5 sklearn與回歸樹3.5.4 sklearn實現(xiàn)sklearn.tree提供了CART算法的實現(xiàn)方法，構造函數(shù)如下：主要參數(shù)說明：class sklearn.tree.DecisionTreeRegressor(criterion=mse, splitter=best, max_depth=None, min_samples_