決策樹(shù)ppt課件

1、決策樹(shù).決策樹(shù)簡(jiǎn)介決策樹(shù)算法.A1,A2兩方案投資分別為450萬(wàn)和240萬(wàn)，運(yùn)營(yíng)年限為5年，銷(xiāo)路好的概率為0.7，銷(xiāo)路差的概率為0.3，A1方案銷(xiāo)路好年、差年的損益值分別為300萬(wàn)和負(fù)60萬(wàn)，A2方案分別為120萬(wàn)和30萬(wàn)。決策樹(shù)簡(jiǎn)介.決策樹(shù)簡(jiǎn)介決策形狀形狀結(jié)結(jié)果點(diǎn)A1A20.70.30.70.33006012030.決策樹(shù)簡(jiǎn)介決策形狀形狀結(jié)結(jié)果點(diǎn)最后選擇的最正確方案代表備選方案的經(jīng)濟(jì)效果將每個(gè)方案在各種自然形狀下獲得的損益值標(biāo)注于結(jié)果節(jié)點(diǎn)的右端.決策樹(shù)的普通流程：1搜集數(shù)據(jù)2預(yù)備數(shù)據(jù)3分析數(shù)據(jù)4訓(xùn)練算法5測(cè)試算法6運(yùn)用算法決策樹(shù)簡(jiǎn)介. 劃分?jǐn)?shù)據(jù)集的大原那么就是將無(wú)序的數(shù)據(jù)變得更加有序。 劃分

2、數(shù)據(jù)集前后信息發(fā)生的變化成為信息增益。 決策樹(shù)簡(jiǎn)介. 集合信息的度量方式稱(chēng)為香農(nóng)熵熵 條件熵決策樹(shù)簡(jiǎn)介.計(jì)算給定數(shù)據(jù)集的香農(nóng)熵from math import log def calcShannonEnt(dataSet) :numEntries = len(dataSet)labelCounts = for featVec in dataSet:currentLabel = featVec-1if currentLabel not in labelCounts.keys():labelCountscurrentLabel= 0labelCountscurrentLabel+=1shannon

3、Ent = 0.0for key in labelCounts: prob = float(labelCountkey)/numEntries shannonEnt-=prob*log(prob,2) return shannonEnt 決策樹(shù)簡(jiǎn)介(1)(2).計(jì)算給定數(shù)據(jù)集的香農(nóng)熵首先，計(jì)算數(shù)據(jù)集中實(shí)例的總數(shù)。為了提高代碼效率，我們顯式的聲明一個(gè)變量保管實(shí)例總數(shù)。然后，創(chuàng)建一個(gè)數(shù)據(jù)字典，它的鍵值是最后一列的數(shù)值1。假設(shè)當(dāng)前鍵值不存在，那么擴(kuò)展字典并將當(dāng)前鍵值參與字典。每個(gè)鍵值都記錄了當(dāng)前類(lèi)別出現(xiàn)的次數(shù)。最后，運(yùn)用一切類(lèi)標(biāo)簽的發(fā)生頻率計(jì)算類(lèi)別出現(xiàn)的頻率2。我們將用這個(gè)概率計(jì)算香農(nóng)熵。決策樹(shù)簡(jiǎn)介

4、.選擇最好的數(shù)據(jù)集劃分方式要求： 1 數(shù)據(jù)必需是一種列表元素組成的列表，而且一切的列表元素都要具有一樣的數(shù)據(jù)長(zhǎng)度。 2 數(shù)據(jù)的最后一列或者每個(gè)實(shí)例的最后一個(gè)元素是當(dāng)前實(shí)例的類(lèi)別標(biāo)簽。決策樹(shù)簡(jiǎn)介.遞歸構(gòu)建決策樹(shù)def createTree(dataSet,labels): classList = example-1 for example in dataSet if classList.count(classList0) = len(classList): return classList0#stop splitting when all of the classes are equal if

5、len(dataSet0) = 1: #stop splitting when there are no more features in dataSet return majorityCnt(classList) bestFeat = chooseBestFeatureToSplit(dataSet) bestFeatLabel = labelsbestFeat myTree = bestFeatLabel: del(labelsbestFeat) featValues = examplebestFeat for example in dataSet uniqueVals = set(fea

6、tValues) for value in uniqueVals: subLabels = labels: #copy all of labels, so trees dont mess up existing labels myTreebestFeatLabelvalue = createTree(splitDataSet(dataSet, bestFeat, value),subLabels) return myTree 決策樹(shù)簡(jiǎn)介(1)(2)(3).遞歸構(gòu)建決策樹(shù)首先創(chuàng)建了名為classList列變量，其中包含了數(shù)據(jù)集的一切類(lèi)標(biāo)簽。遞歸函數(shù)的第一個(gè)停頓條件是一切的類(lèi)標(biāo)簽完全一樣，那么直接

7、前往該類(lèi)標(biāo)簽(1)。遞歸函數(shù)的第二個(gè)停頓條件是運(yùn)用完了一切特征，依然不能將數(shù)據(jù)集劃分成僅包含獨(dú)一類(lèi)別的分組(2)。決策樹(shù)簡(jiǎn)介.遞歸構(gòu)建決策樹(shù)第二步，開(kāi)場(chǎng)創(chuàng)建樹(shù)，這里運(yùn)用python言語(yǔ)的字典類(lèi)型存儲(chǔ)樹(shù)的信息(3)。決策樹(shù)簡(jiǎn)介.遞歸構(gòu)建決策樹(shù)第三步，代碼遍歷當(dāng)前選擇特征包含的一切屬性值，在每個(gè)數(shù)據(jù)集劃分上遞歸調(diào)用函數(shù)createTree(),得到的前往值將被插入到字典變量MyTree中。決策樹(shù)簡(jiǎn)介.3種算法比較ID3 較小數(shù)據(jù) 算法明晰C4 添加信息增益率 可以處置延續(xù)數(shù)值型屬性 規(guī)那么后修剪C5 Unix決策樹(shù)算法. 一 ID3根本思想 二 ID3算法 三 實(shí)例 四 ID3缺陷決策樹(shù)算法. 在

8、決策樹(shù)各個(gè)結(jié)點(diǎn)上運(yùn)用信息增益準(zhǔn)那么選擇特征遞歸地構(gòu)建決策樹(shù)。 天氣，取值為：晴，多云，雨。 氣溫，取值為：冷，適中，熱。 濕度，取值為：高，正常。 風(fēng)，取值為：有風(fēng)，無(wú)風(fēng)。決策樹(shù)算法ID3根本思想.某天早晨氣候描畫(huà)為：天氣多云；氣溫冷；濕度正常；風(fēng)無(wú)風(fēng)。它屬于哪類(lèi)氣候呢？要處理這個(gè)問(wèn)題，需求用某個(gè)原那么來(lái)斷定，這個(gè)原那么來(lái)自于大量的實(shí)踐例子，從例子中總結(jié)出原那么，有了原那么就可以斷定任何一天的氣候了。每個(gè)實(shí)體在世界中屬于不同的類(lèi)別，為簡(jiǎn)單起見(jiàn)，假定僅有兩個(gè)類(lèi)別，分別為P、N。在這種兩個(gè)類(lèi)別的歸納義務(wù)中，P類(lèi)和N類(lèi)的實(shí)體分別稱(chēng)為概念的正例和反例。將一些知正例和反例放在一同便得到訓(xùn)練集。決策樹(shù)算法

9、ID3根本思想.決策樹(shù)算法ID3根本思想.決策樹(shù)算法晴多云雨P(guān)正常PNNP有風(fēng)無(wú)風(fēng)濕度風(fēng)天氣高ID3根本思想.決策樹(shù)算法PN多云 (12)雨 (14)風(fēng)有風(fēng)(2,6,7,11,12,14)溫度高 (2,12,14)正常 (6,7,11)氣溫氣溫N熱 (2)適中 (12,14)天氣P適中 (11)冷 (6,7)NP多云 (6)雨 (7)天氣高 (1,3,4,8)無(wú)風(fēng)(1,3,4,5,8,9,10,13)正常 (5,9,10,13)適中 (4,8)P熱 (1,3)PNPN晴 (1)多云 (3)晴 (8)雨 (4)溫度氣溫天氣天氣ID3算法.從根結(jié)點(diǎn)root node開(kāi)場(chǎng)，對(duì)結(jié)點(diǎn)計(jì)算一切能夠的特征的

10、信息增益，選擇信息增益最大的特征作為結(jié)點(diǎn)的特征，由該特征的不同取值建立子結(jié)點(diǎn)；再對(duì)子結(jié)點(diǎn)遞歸的調(diào)用以上方法，構(gòu)建決策樹(shù)；直到一切特征的信息增益均很小或者沒(méi)有特征可以選擇為止。最后，得到一個(gè)決策樹(shù)。決策樹(shù)算法ID3算法.決策樹(shù)算法三 實(shí)例 對(duì)于氣候分類(lèi)問(wèn)題進(jìn)展以下詳細(xì)計(jì)算。 1、信息熵計(jì)算： 類(lèi)別ui出現(xiàn)概率： |S|表例如子集S的總數(shù)，|ui|表示類(lèi)別 ui的例子數(shù)。 對(duì)9個(gè)正例u1和5個(gè)反例u2有：.2條件熵計(jì)算 條件熵： 屬性A1取值vj時(shí)，類(lèi)別ui的條件概率： A1天氣的取值：v1晴，v2多云，v3雨在A1處取值“晴的例子5個(gè)，取值“多云的例子4個(gè)，取值“雨的例子5個(gè)，故：決策樹(shù)算法三

11、實(shí)例. 取值為晴的5個(gè)例子中有兩個(gè)正例、3個(gè)反例，故： 同理有決策樹(shù)算法三 實(shí)例.3互信息計(jì)算 對(duì)A1天氣，有： 類(lèi)似可得： 氣溫0.029bit 濕度0.151bit 風(fēng)0.048bit決策樹(shù)算法三 實(shí)例.決策樹(shù)算法三 實(shí)例.4建決策樹(shù)的樹(shù)根和分支ID3算法將選擇互信息最大的屬性“天氣作為樹(shù)根，在14個(gè)例子中對(duì)“天氣的3個(gè)取值進(jìn)展分支，3個(gè)分支對(duì)應(yīng)3個(gè)子集，分別是：F1晴1，2，8，9，11，F(xiàn)2多云3，7，12，13，F(xiàn)3雨4，5，6，10，14其中，F(xiàn)2中的例子全屬于P類(lèi)，因此對(duì)應(yīng)分支標(biāo)志為P，其他兩個(gè)子集既含有正例P又含有反例，將遞歸調(diào)用建樹(shù)算法決策樹(shù)算法三 實(shí)例.5遞歸建樹(shù)分別對(duì)F1

12、和F3子集利用ID3算法，在每個(gè)子集中對(duì)各屬性仍為4個(gè)屬性求互信息。1F1中的天氣全取“晴值，那么HUHUV，有IUV0，在余下3個(gè)屬性中求出“濕度互信息最大，以它為該分支的根結(jié)點(diǎn)。再向下分支，“濕度取“高的例子全為N類(lèi)，該分支標(biāo)志N；取值“正常的例子全為P類(lèi)，該分支標(biāo)志P。決策樹(shù)算法三 實(shí)例.2在F3中，對(duì)4個(gè)屬性求互信息，得到“風(fēng)屬性互信息最大，那么以它為該分支的根結(jié)點(diǎn)。再向下分支，“風(fēng)取“有風(fēng)時(shí)全為N類(lèi)，該分支標(biāo)志N；取“無(wú)風(fēng)時(shí)全為P類(lèi)，該分支標(biāo)志P。 這樣就得到如圖 所示的決策樹(shù)。決策樹(shù)算法三 實(shí)例晴多云雨P(guān)高正常PNNP有風(fēng)無(wú)風(fēng)濕度風(fēng)天氣圖1. ID3算法的缺陷： 1只適宜屬性值為離散的； 2決策樹(shù)層次較多時(shí)，決策質(zhì)量低； 3傾向于選擇取值較多的屬性；決策樹(shù)算法四 ID3缺陷.決策樹(shù).優(yōu)點(diǎn)：決策樹(shù)易于了解和實(shí)現(xiàn)，人們?cè)谠趯W(xué)習(xí)過(guò)程中不需求運(yùn)用者了解很多的背景知識(shí)這同時(shí)是它的可以直接表達(dá)數(shù)據(jù)的特點(diǎn)，只需經(jīng)過(guò)解釋后都有才干去理處理策樹(shù)所表達(dá)的意義。對(duì)于決策