模式識別決策樹分類

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

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

其中，E(S)為劃分樣本集S為c個類的熵；E(S,A)為屬性A劃分樣本集S導(dǎo)致的期望熵。2023/4/115第5頁，共12頁，2023年，2月20日，星期五熵（Entropy）劃分樣本集S為c個類的熵E(S)為：其中，pi＝ni/n，為S中的樣本屬于第i類Ci的概率，n為S中樣本的個數(shù)。2023/4/116第6頁，共12頁，2023年，2月20日，星期五期望熵（ExpectedEntropy）屬性A劃分樣本集S導(dǎo)致的期望熵E(S,A)為：

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

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

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

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