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

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

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

如何以遞歸方式建立決策樹(shù)？目前六頁(yè)\總數(shù)二十二頁(yè)\編于十三點(diǎn)決策樹(shù)如何劃分訓(xùn)練記錄？

如何表示屬性測(cè)試條件？

如何確定最佳劃分？如何構(gòu)建測(cè)試條件效果最好的樹(shù)？目前七頁(yè)\總數(shù)二十二頁(yè)\編于十三點(diǎn)如何確定最佳劃分貪婪法：根據(jù)子女結(jié)點(diǎn)類(lèi)分布的一致性程度來(lái)

選擇最佳劃分度量結(jié)點(diǎn)的不純度Gini熵誤分類(lèi)誤差目前八頁(yè)\總數(shù)二十二頁(yè)\編于十三點(diǎn)對(duì)于一個(gè)給定的結(jié)點(diǎn)t：

是結(jié)點(diǎn)t中類(lèi)j的相對(duì)頻率最大值：(1-1/nc)，記錄在所有類(lèi)中等分布最小值：0，所有記錄屬于同一個(gè)類(lèi)不純度度量——GINI目前九頁(yè)\總數(shù)二十二頁(yè)\編于十三點(diǎn)如何劃分訓(xùn)練記錄

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

標(biāo)稱(chēng)屬性

序數(shù)屬性

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

二元?jiǎng)澐?/p>

多元化分如何表示測(cè)試條件目前十頁(yè)\總數(shù)二十二頁(yè)\編于十三點(diǎn)選擇最佳分割點(diǎn)數(shù)值型變量

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

列出劃分為兩個(gè)子集的所有可能組合，計(jì)算每種組合下生成子節(jié)點(diǎn)的異質(zhì)性。同樣，找到使異質(zhì)性減小程度最大的組合作為最佳劃分點(diǎn)。目前十一頁(yè)\總數(shù)二十二頁(yè)\編于十三點(diǎn)有房無(wú)房否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目前十二頁(yè)\總數(shù)二十二頁(yè)\編于十三點(diǎn)單身已婚離異否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目前十三頁(yè)\總數(shù)二十二頁(yè)\編于十三點(diǎn)60707585909510012012522055657280879297110122172230≤>≤>≤>≤>≤>≤>≤>≤>≤>≤>≤>030303031221303030303007162534343434435261700.4200.4000.3750.3430.4170.4000.3000.3430.3750.4000.420是否Gini目前十四頁(yè)\總數(shù)二十二頁(yè)\編于十三點(diǎn)測(cè)試條件效果為確定測(cè)試條件劃分，比較父節(jié)點(diǎn)（劃分前）的不純度和子女結(jié)點(diǎn)的不純度，差越大測(cè)試效果就越好

不變值目前十五頁(yè)\總數(shù)二十二頁(yè)\編于十三點(diǎn)決策樹(shù)停止生長(zhǎng)條件節(jié)點(diǎn)達(dá)到完全純度樹(shù)的深度達(dá)到用戶(hù)所要的深度異質(zhì)性指標(biāo)下降的最大幅度小于用戶(hù)指定的幅度節(jié)點(diǎn)中樣本個(gè)數(shù)少于用戶(hù)指定個(gè)數(shù)目前十六頁(yè)\總數(shù)二十二頁(yè)\編于十三點(diǎn)決策樹(shù)(Hunt算法)拖欠貸款者=否拖欠貸款者=是拖欠貸款者=否拖欠貸款者=否拖欠貸款者=是有房者婚姻狀況拖欠貸款者=否拖欠貸款者=否有房者年收入是是否否單身離異已婚<80K≥80K拖欠貸款者=是拖欠貸款者=否拖欠貸款者=否有房者婚姻狀況是否單身離異已婚目前十七頁(yè)\總數(shù)二十二頁(yè)\編于十三點(diǎn)剪枝前剪枝：停止生長(zhǎng)策略后剪枝：在允許決策樹(shù)得到最充分生長(zhǎng)的基礎(chǔ)上，再根據(jù)一定的規(guī)則，自下而上逐層進(jìn)行剪枝。當(dāng)分類(lèi)回歸樹(shù)劃分得太細(xì)時(shí)，會(huì)對(duì)噪聲數(shù)據(jù)產(chǎn)生過(guò)擬合作用。因此我們要通過(guò)剪枝來(lái)解決目前十八頁(yè)\總數(shù)二十二頁(yè)\編于十三點(diǎn)剪枝方法231最小誤差剪枝代價(jià)復(fù)雜性

悲觀誤差剪枝目前十九頁(yè)\總數(shù)二十二頁(yè)\編于十三點(diǎn)代價(jià)復(fù)雜性剪枝目前二十頁(yè)\總數(shù)二十二頁(yè)\編于十三點(diǎn)模型評(píng)價(jià)

減少在冒險(xiǎn)因素或損失因素方面的不確定性。不僅包括不同模