尚硅谷大數(shù)據(jù)技術(shù)之spark機(jī)器學(xué)習(xí)決策樹

機(jī)器學(xué)習(xí)-決策樹講師：武玉飛0102030405線性回歸解決的問題一元線性回歸多元線性回歸最小二乘法梯度下降法目錄Contents06操作與實(shí)踐一種描述概念空間的有效的歸納推理辦法?；跊Q策樹的學(xué)習(xí)方法可以進(jìn)行不相關(guān)的多概念學(xué)習(xí)，具有簡單快捷的優(yōu)勢，已經(jīng)在各個(gè)領(lǐng)域取得廣泛應(yīng)用。決策樹是一種樹型結(jié)構(gòu)，其中每個(gè)內(nèi)部結(jié)點(diǎn)表示在一個(gè)屬性上的測試，每個(gè)分支代表一個(gè)測試輸出，每個(gè)葉結(jié)點(diǎn)代表一種類別。什么是決策樹？決策樹示意圖決策樹學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)。決策樹學(xué)習(xí)采用的是自頂向下的遞歸方法，其基本思想是以信息熵為度量構(gòu)造一棵熵值下降最快的樹，到葉子節(jié)點(diǎn)處的熵值為零，此時(shí)每個(gè)葉節(jié)點(diǎn)中的實(shí)例都屬于同一類。決策樹學(xué)習(xí)算法的最大優(yōu)點(diǎn)是，它可以自學(xué)習(xí)。在學(xué)習(xí)的過程中，不需要使用者了解過多背景知識(shí)，只需要對(duì)訓(xùn)練例子進(jìn)行較好的標(biāo)注，就能夠進(jìn)行學(xué)習(xí)。顯然，屬于有監(jiān)督學(xué)習(xí)。從一類無序、無規(guī)則的事物(概念)中推理出決策樹表示的分類規(guī)則。決策樹的思想信息熵熵在信息論中代表隨機(jī)變量不確定度的度量。一個(gè)離散型隨機(jī)變量的熵定義為：信息熵兩個(gè)隨機(jī)變量X，Y的聯(lián)合分布，可以形成聯(lián)合熵JointEntropy，用H(X,Y)表示H(X,Y)–H(Y)(X,Y)發(fā)生所包含的信息熵，減去Y單獨(dú)發(fā)生包含的信息熵=在Y發(fā)生的前提下，X發(fā)生的信息熵該式子定義為Y發(fā)生前提下，X的熵：條件熵H(X|Y)=H(X,Y)–H(Y)聯(lián)合熵和條件熵信息增益概念：當(dāng)熵和條件熵中的概率由數(shù)據(jù)估計(jì)(特別是極大似然估計(jì))得到時(shí)，所對(duì)應(yīng)的熵和條件熵分別稱為經(jīng)驗(yàn)熵和經(jīng)驗(yàn)條件熵。信息增益表示得知特征A的信息而使得類X的信息的不確定性減少的程度。定義：特征A對(duì)訓(xùn)練數(shù)據(jù)集D的信息增益g(D,A)，定義為集合D的經(jīng)驗(yàn)熵H(D)與特征A給定條件下D的經(jīng)驗(yàn)條件熵H(D|A)之差，即：g(D,A)=H(D)–H(D|A)信息增益比單純的信息增益只是個(gè)相對(duì)值，因?yàn)檫@依賴于H(D)的大小，所以信息增益比更能客觀地反映信息增益。特征A對(duì)訓(xùn)練數(shù)據(jù)集D的信息增益比gR(D,A)定義為其信息增益g(D,A)與訓(xùn)練數(shù)據(jù)集D關(guān)于特征A的值的熵HA(D)之比，即

其中，，n是特征A取值的個(gè)數(shù)。決策樹學(xué)習(xí)的生成算法建立決策樹的關(guān)鍵，即在當(dāng)前狀態(tài)下選擇哪個(gè)屬性作為分類依據(jù)。根據(jù)不同的目標(biāo)函數(shù)，建立決策樹主要有一下三種算法。ID3C4.5CARTID3生成算法決策樹的例子決策樹的例子極小熵生成決策樹,設(shè)表1給的數(shù)據(jù)集為D，根據(jù)最大信息增益選擇最優(yōu)特征生成極小熵決策樹,計(jì)算各特征A1、A2、A3、A4、A5對(duì)數(shù)據(jù)D的信息增益，統(tǒng)計(jì)結(jié)果為：上表中的D1和D2，D3分別表示在各個(gè)特征中取值為1、2和3的樣本子集，根據(jù)計(jì)算后統(tǒng)計(jì)在表格中的數(shù)據(jù)可得：H(D)=-8/15*log2(8/15)—7/15*log2(7/15)=0.9968g(D,A1)=H(D)-[8/15*H(D1)+7/15*H(D2)]=0.2880g(D,A2)=H(D)-[5/15*H(D1)+4/15*H(D2)+6/15*H(D3)]=0.1398g(D,A3)=H(D)-[3/15*H(D1)+12/15*H(D2)]=0.0292g(D,A4)=H(D)-[7/15*H(D1)+8/15*H(D2)]=0.2880g(D,A5)=H(D)-[6/15*H(D1)+4/15*H(D2)+5/15*H(D3)]=0.4131決策樹的例子所以選擇A1作為集合S33的根節(jié)點(diǎn)。根據(jù)A1的取值劃分后的集合也都為葉子節(jié)點(diǎn)，至此極小熵決策樹就建立起來了，如下圖所示。決策樹的例子根據(jù)上面的計(jì)算結(jié)果，特征A5的信息增益最大，所以選擇A5為根節(jié)點(diǎn)。根據(jù)A5的取值將樣本分成3個(gè)集合，S1={2,3,6,8,12,13}，S2={1,5,7,14}，S3={4,9,10,11,15}其中集合S2已全部屬于同一個(gè)類，不需要再分，已成為葉子節(jié)點(diǎn)。對(duì)于集合S1，計(jì)算統(tǒng)計(jì)結(jié)果為：H(D)=0.6500g(D,A1)=0.0484g(D,A2)=0.1909g(D,A3)=0.0484g(D,A4)=0.6500決策樹的例子所以選擇A1作為集合S33的根節(jié)點(diǎn)。根據(jù)A1的取值劃分后的集合也都為葉子節(jié)點(diǎn)，至此極小熵決策樹就建立起來了，如下圖所示。決策樹的例子

根據(jù)計(jì)算結(jié)果，集合S1選擇A4為根結(jié)點(diǎn)。根據(jù)A4的取值，將S1集合劃分為S11={3,6,8,12,13}

S12={2}，集合S11和集合S12已成為葉節(jié)點(diǎn)。對(duì)于集合S3，計(jì)算統(tǒng)計(jì)結(jié)果為：H(D)=0.9710g(D,A1)=0.4200g(D,A2)=0.5710g(D,A3)=0g(D,A4)=0.0200決策樹的例子所以選擇A1作為集合S33的根節(jié)點(diǎn)。根據(jù)A1的取值劃分后的集合也都為葉子節(jié)點(diǎn)，至此極小熵決策樹就建立起來了，如下圖所示。決策樹的例子根據(jù)計(jì)算結(jié)果，所以集合S3選擇A2作為根結(jié)點(diǎn)，根據(jù)A2的取值將S3分成集合S31={4,11}集合S32={9}集合S33={10,15}集合S32和集合S32已為葉子節(jié)點(diǎn)。對(duì)于集合S33，計(jì)算統(tǒng)計(jì)結(jié)果為H(D)=1

g(D,A1)=1g(D,A3)=0

g(D,A4)=0決策樹的例子所以選擇A1作為集合S33的根節(jié)點(diǎn)。根據(jù)A1的取值劃分后的集合也都為葉子節(jié)點(diǎn)，至此極小熵決策樹就建立起來了，如下圖所示。決策樹的剪枝決策樹生成算法對(duì)于訓(xùn)練集是很準(zhǔn)確的，也就是生成的樹枝很詳細(xì)，但這樣會(huì)過擬合，需要通過剪枝操作來提高泛化能力，思路很簡單，就是在決策樹對(duì)訓(xùn)練集數(shù)據(jù)的預(yù)測誤差和樹復(fù)雜度之間找一個(gè)平衡。

預(yù)測誤差就是所有葉子節(jié)點(diǎn)的經(jīng)驗(yàn)熵的和，其中表示該葉節(jié)點(diǎn)的樣本點(diǎn)個(gè)數(shù)，而表示該葉子節(jié)點(diǎn)的經(jīng)驗(yàn)熵：樹的復(fù)雜度由葉子節(jié)點(diǎn)的個(gè)數(shù)來表示：T。所以，剪枝的標(biāo)準(zhǔn)就是極小化損失函數(shù)：其