模式識(shí)別決策樹分類

模式識(shí)別決策樹分類2023/7/141第1頁，課件共12頁，創(chuàng)作于2023年2月數(shù)據(jù)實(shí)例PlayTennis數(shù)據(jù)庫片段：2023/7/142第2頁，課件共12頁，創(chuàng)作于2023年2月決策樹實(shí)例關(guān)于PlayTennis的決策樹：2023/7/143第3頁，課件共12頁，創(chuàng)作于2023年2月決策樹學(xué)習(xí)算法的代表早在1986年的時(shí)候，Quinlan就提出了著名的ID3算法。（PublishedonMLJ）用ID3算法長(zhǎng)樹的基本思想：分類能力最好的屬性被測(cè)試并創(chuàng)建樹的根結(jié)點(diǎn)測(cè)試屬性每個(gè)可能的值產(chǎn)生一個(gè)分支訓(xùn)練樣本劃分到適當(dāng)?shù)姆种纬蓛鹤咏Y(jié)點(diǎn)重復(fù)上面的過程，直到所有的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)兩個(gè)問題：什么屬性最好？什么結(jié)點(diǎn)才是葉子結(jié)點(diǎn)？2023/7/144第4頁，課件共12頁，創(chuàng)作于2023年2月信息增益（InformationGain）屬性A劃分樣本集S的信息增益Gain(S,A)為：

Gain(S,A)=E(S)–E(S,A)

其中，E(S)為劃分樣本集S為c個(gè)類的熵；E(S,A)為屬性A劃分樣本集S導(dǎo)致的期望熵。2023/7/145第5頁，課件共12頁，創(chuàng)作于2023年2月熵（Entropy）劃分樣本集S為c個(gè)類的熵E(S)為：其中，pi＝ni/n，為S中的樣本屬于第i類Ci的概率，n為S中樣本的個(gè)數(shù)。2023/7/146第6頁，課件共12頁，創(chuàng)作于2023年2月期望熵（ExpectedEntropy）屬性A劃分樣本集S導(dǎo)致的期望熵E(S,A)為：

其中，Values(A)為屬性A取值的集合；Sv為S中A取值為v的樣本子集，Sv={sSA(s)=v}；E(Sv)為將Sv中的樣本劃分為c個(gè)類的信息熵。|Sv|/|S|為Sv和S中的樣本個(gè)數(shù)之比。2023/7/147第7頁，課件共12頁，創(chuàng)作于2023年2月回味ID3算法ID3算法每一步選擇具有最大信息增益的屬性作為測(cè)試屬性來長(zhǎng)樹。直到最大的信息增益為也零為止。（兩個(gè)問題的解決）熵（Entropy）刻畫了樣本集的純度，長(zhǎng)樹的過程是一個(gè)熵降低、信息增益、從混沌到有序的過程。（長(zhǎng)樹的物理意義）2023/7/148第8頁，課件共12頁，創(chuàng)作于2023年2月偽代碼算法Decision_Tree（samples,attribute_list）輸入由離散值屬性描述的訓(xùn)練樣本集samples；候選屬性集合atrribute_list。輸出一棵決策樹。方法

(1)創(chuàng)建節(jié)點(diǎn)N；(2)ifsamples

都在同一類C中then(3)返回N作為葉節(jié)點(diǎn)，以類C標(biāo)記；(4)ifattribute_list為空then2023/7/149第9頁，課件共12頁，創(chuàng)作于2023年2月偽代碼（續(xù)）(5)返回N作為葉節(jié)點(diǎn)，以samples中最普遍的類標(biāo)記；//多數(shù)表決(6)選擇attribute_list中具有最高信息增益的屬性test_attribute；(7)以test_attribute標(biāo)記節(jié)點(diǎn)N；(8)foreachtest_attribute的已知值v//劃分samples

(9)由節(jié)點(diǎn)N分出一個(gè)對(duì)應(yīng)test_attribute=v的分支；(10)令Sv為samples中test_attribute=v的樣本集合；//一個(gè)劃分塊(11)ifSv為空then(12)加上一個(gè)葉節(jié)點(diǎn)，以samples中最普遍的類標(biāo)記；(13)else加入一個(gè)由Decision_Tree(Sv,attribute_list–test_attribute)返回的節(jié)點(diǎn)。2023/7/1410第10頁，課件共12頁，創(chuàng)作于2023年2月ID3算法的不足及改進(jìn)ID3算法存在的主要不足：過度擬合問題(treeprunning)處理連續(xù)屬性值問題(discretization)處理缺少屬性值問題(replacement)屬性選擇的度量標(biāo)準(zhǔn)問題(heuristicmeasure)針對(duì)這些不足，Quinlan做了一系列的改進(jìn)，并于1993年形成了C4.5算法。（C4.5:ProgramsforMachineLearning）2023/7/1411第11頁，課件共12頁，創(chuàng)作于2023年2月決策樹學(xué)習(xí)總結(jié)決策樹（DecisionTree）學(xué)習(xí)是以樣本為基礎(chǔ)的歸納學(xué)習(xí)方法，它采用自頂向下的遞歸方式來構(gòu)造決策樹。（貪心算法）決策樹的表現(xiàn)形式是類似于流程圖的樹結(jié)構(gòu)，在決策樹的內(nèi)部結(jié)點(diǎn)進(jìn)行屬性值測(cè)試，并根據(jù)屬性值判斷由該結(jié)點(diǎn)引出的分支，最后在決策樹的葉子結(jié)點(diǎn)分類。（學(xué)習(xí)階段、訓(xùn)練階段）由訓(xùn)練樣本