大數(shù)據(jù)經(jīng)典算法演示

(第四組)分類與回歸樹算法(CART)當前1頁，總共22頁。分類與回歸分類——劃分離散變量回歸——劃分連續(xù)變量當前2頁，總共22頁。什么是CARTwelcometousethesePowerPointtemplates,NewContentdesign,10yearsexperience分類與回歸樹CART采用一種二分遞歸分割的技術，將當前的樣本集分為兩個子樣本集，使得生成的決策樹的每個非葉子節(jié)點都有兩個分支。CART算法生成的決策樹是結構簡潔的二叉樹。當前3頁，總共22頁。摘要遞歸劃分自變量空間驗證數(shù)據(jù)進行剪枝模型評價當前4頁，總共22頁。Hunt算法設Dt是與節(jié)點t相關聯(lián)的訓練記錄集，y={y1,y2,…,yc}是類標號。Hunt算法的遞歸定義如下：(1)如果Dt中所有記錄都屬于同一個類yt，則t是葉子節(jié)點。(2)如果Dt中包含屬于多個類的記錄，則選擇一個屬性測試條件，將記錄劃分成較小的子集。對于測試條件的每一個輸出創(chuàng)建一個子女結點，并根據(jù)測試結果將Dt中的記錄分布到子女結點中。然后，對于每個子女結點，遞歸調用該算法。當前5頁，總共22頁。一遞歸劃分自變量空間tid有房者

婚姻狀況年收入拖欠貸款者12345678910是否否是否否是否否否單身已婚單身已婚離異已婚離異單身已婚單身125K100K70K120K95K60K220K85K75K90K否否否否是否否是否是訓練集

如何以遞歸方式建立決策樹？當前6頁，總共22頁。決策樹如何劃分訓練記錄？

如何表示屬性測試條件？

如何確定最佳劃分？如何構建測試條件效果最好的樹？當前7頁，總共22頁。如何確定最佳劃分貪婪法：根據(jù)子女結點類分布的一致性程度來

選擇最佳劃分度量結點的不純度Gini熵誤分類誤差當前8頁，總共22頁。對于一個給定的結點t：

是結點t中類j的相對頻率最大值：(1-1/nc)，記錄在所有類中等分布最小值：0，所有記錄屬于同一個類不純度度量——GINI當前9頁，總共22頁。如何劃分訓練記錄

根據(jù)屬性類型的不同：

標稱屬性

序數(shù)屬性

連續(xù)屬性根據(jù)分割的數(shù)量

二元劃分

多元化分如何表示測試條件當前10頁，總共22頁。選擇最佳分割點數(shù)值型變量

對記錄的值從小到大排序，計算每個值作為臨界點產(chǎn)生的子節(jié)點的異質性統(tǒng)計量。能夠使異質性減小程度最大的臨界值便是最佳的劃分點。分類型變量

列出劃分為兩個子集的所有可能組合，計算每種組合下生成子節(jié)點的異質性。同樣，找到使異質性減小程度最大的組合作為最佳劃分點。當前11頁，總共22頁。有房無房否34是03Gini(t1)=1-(3/3)2-(0/3)2=0Gini(t2)=1-(4/7)2-(3/7)2=0.4849Gini=0.3×0+0.7×0.4898=0.343當前12頁，總共22頁。單身已婚離異否241是201單身或已婚離異否

61是

21單身或離異已婚否

34是

30離異或已婚單身否52是12Gini(t1)=1-(2/4)2-(2/4)2=0.5Gini(t2)=1-(0/4)2-(4/4)2=0Gini(t3)=1-(1/2)2-(1/2)2=0.5Gini=4/10×0.5+4/10×0+2/10×0.5=0.3Gini(t1)=1-(6/8)2-(2/8)2=0.375Gini(t2)=1-(1/2)2-(1/2)2=0.5Gini=8/10×0.375+2/10×0.5=0.4Gini(t1)=1-(3/6)2-(3/6)2=0.5Gini(t2)=1-(4/4)2-(0/4)2=0Gini=6/10×0.5+4/10×0=0.3Gini(t1)=1-(5/6)2-(1/6)2=0.2778Gini(t2)=1-(2/4)2-(2/4)2=0.5Gini=6/10×0.2778+4/10×0.5=0.3667當前13頁，總共22頁。60707585909510012012522055657280879297110122172230≤>≤>≤>≤>≤>≤>≤>≤>≤>≤>≤>030303031221303030303007162534343434435261700.4200.4000.3750.3430.4170.4000.3000.3430.3750.4000.420是否Gini當前14頁，總共22頁。測試條件效果為確定測試條件劃分，比較父節(jié)點（劃分前）的不純度和子女結點的不純度，差越大測試效果就越好

不變值當前15頁，總共22頁。決策樹停止生長條件節(jié)點達到完全純度樹的深度達到用戶所要的深度異質性指標下降的最大幅度小于用戶指定的幅度節(jié)點中樣本個數(shù)少于用戶指定個數(shù)當前16頁，總共22頁。決策樹(Hunt算法)拖欠貸款者=否拖欠貸款者=是拖欠貸款者=否拖欠貸款者=否拖欠貸款者=是有房者婚姻狀況拖欠貸款者=否拖欠貸款者=否有房者年收入是是否否單身離異已婚<80K≥80K拖欠貸款者=是拖欠貸款者=否拖欠貸款者=否有房者婚姻狀況是否單身離異已婚當前17頁，總共22頁。剪枝前剪枝：停止生長策略后剪枝：在允許決策樹得到最充分生長的基礎上，再根據(jù)一定的規(guī)則，自下而上逐層進行剪枝。當分類回歸樹劃分得太細時，會對噪聲數(shù)據(jù)產(chǎn)生過擬合作用。因此我們要通過剪枝來解決當前18頁，總共22頁。剪枝方法231最小誤差剪枝代價復雜性

悲觀誤差剪枝當前19頁，總共22頁。代價復雜性剪枝當前20頁，總共22頁。模型評價

減少在冒險因素或損失因素方面的不確定性