ch10決策樹(已修改)
2025-10-10 22:36 本頁面
【正文】 Ch 10. 決策樹 特征類型 ? 數(shù)值數(shù)據(jù) （ numerical data） ? 例： {, , } ? 模式間可以計算距離度量 ? 基于度量的模式分類方法 ? 標(biāo)稱數(shù)據(jù) （ nominal data） ? 例： {紅色，有光澤，甜，小 } ? 模式間沒有距離的概念 ? 非度量方法 決策樹 ? 什么是決策樹？ ? 決策樹是一種類似流程圖的樹形結(jié)構(gòu)，每個內(nèi)部節(jié)點表示一個測試（查詢），該節(jié)點的每個分支表示該測試的一個結(jié)果，每個葉節(jié)點表示一個類別 ? 決策樹的構(gòu)成 ? 根節(jié)點 （ root） ? 分支 （ branch） ? 葉節(jié)點 （ leaf） 決策樹 決策樹 ? 決策樹分類過程 ? 從根節(jié)點開始 ， 首先對某一屬性的取值提問 ? Color? ? 與根節(jié)點相連的不同分支 ， 對應(yīng)這個屬性的不同取值 ? green。 yellow。 red。 ? 根據(jù)不同的回答 ， 轉(zhuǎn)向相應(yīng)的分支 ? green ? 在新到達(dá)的節(jié)點處做同樣的分支判斷 ? Size? – big. ? 這一過程持續(xù) ， 直到到達(dá)某個葉節(jié)點 ， 輸出該葉節(jié)點的類別標(biāo)記 ? Watermelon 決策樹 ? 決策樹的判決面 決策樹 ? 決策樹的優(yōu)勢 ? 語義可表示性 ? 從根節(jié)點到葉節(jié)點表示為合取式 ? （顏色 =黃） AND（形狀 =細(xì)長） 香蕉 ? 利用合取式和析取式獲得某個類別的明確描述 ? 蘋果 =（綠色 AND 中等大?。?OR（紅色 AND 中等大小） ? 分類速度快 ? 只需一系列簡單查詢即可對模式的類別做出判斷 ? 可以很自然的嵌入專家的先驗知識 決策樹學(xué)習(xí)算法 ? 決策樹研究歷史 ? 第一個決策樹算法稱為 CLS (Concept Learning System) [E. B. Hunt, J. Marin, and P. T. Stone’s book “Experiments in Induction”published by Academic Press in 1966] ? 真正引發(fā)決策樹研究熱潮的算法是 ID3 [J. R. Quinlan’s paper in a book “Expert Systems in the Micro Electronic Age” edited by D. Michie, published by Edinburgh University Press in 1979] ? 最流行的決策樹算法 [J. R. Quinlan’s book “: Programs for Machine Learning” published by Man Kaufmann in 1993] 決策樹學(xué)習(xí)算法 ? 決策樹研究歷史 ? 通用的決策樹算法 CART (Classification and Regression Tree) [L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone’s book “Classification and Regression Trees” published by Wadsworth in 1984] ? 基于決策樹的集成學(xué)習(xí)算法： 隨機森林 (Random Forests) [L. Breiman’s MLJ’01 paper “Random Forests”] 構(gòu)造決策樹 ? 基本過程 ? 從上到下，分而治之（ divideandconquer），遞歸生長 ? 最初，所有的樣本都在根節(jié)點 ? 所有屬性都是標(biāo)稱型的（如果是連續(xù)數(shù)值型的，則需要預(yù)先離散化） ? 所有樣本根據(jù)每次選擇出的屬性遞歸的逐漸劃分開來 選擇出來的屬性稱為一個劃分（ split）或測試（ test）或查詢 （ query） ? 查詢的選擇基于啟發(fā)式或者統(tǒng)計特征 構(gòu)造決策樹 ? 基本過程 ? 滿足如下條件之一時，劃分操作停止 ? 所有落入某一節(jié)點的樣本均屬于同一類別 該節(jié)點成為葉節(jié)點，標(biāo)記為該類別 ? 沒有特征能夠進一步用于劃分樣本集 該節(jié)點成為葉節(jié)點，類別標(biāo)簽為落入該節(jié)點的多數(shù)樣本所屬的類別 ? 沒有任何樣本落入某一節(jié)點 該節(jié)點成為葉節(jié)點，類別標(biāo)簽為落入父節(jié)點的多數(shù)樣本所屬的類別 CART ? 分類和回歸樹 （ Classification And Regression Tree, CART) ? CART為通用的樹生長算法框架，涉及如下問題： ? 屬性的值是二值的還是多值的？即節(jié)點可以有幾個分支？ ? 如何確定某節(jié)點處應(yīng)該測試哪個屬性？ ? 何時令某個節(jié)點為葉節(jié)點？ ? 如果樹生長的過
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1