分類決策樹(shù)_id3算法-在線瀏覽
2025-02-27 11:58本頁(yè)面
【正文】 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 誰(shuí)在買計(jì)算機(jī)？ 年齡？ 學(xué)生？ 信譽(yù)？ 買 青 中 老 否 是 優(yōu) 良 不買 買 買 不買 決策樹(shù)的用途 決策樹(shù)算法 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 132 老 中 是 良 買 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 誰(shuí)在買計(jì)算機(jī)？ 年齡？ 學(xué)生？ 信譽(yù)？ 買 青 中 老 否 是 優(yōu) 良 不買 買 買 不買 決策樹(shù)的用途 決策樹(shù)算法 決策樹(shù)算法 決策樹(shù)的表示 決策樹(shù)的基本組成部分：決策結(jié)點(diǎn)、分支和葉子。 1993年， Quinlan 進(jìn)一步發(fā)展了 ID3算法，改進(jìn)成 。 Schlimmer和 Fisher于 1986年對(duì) ID3進(jìn)行改造，在每個(gè)可能的決策樹(shù)節(jié)點(diǎn)創(chuàng)建緩沖區(qū)，使決策樹(shù)可以遞增式生成，得到 ID4算法。 主要內(nèi)容 決策樹(shù)基本概念 決策樹(shù)算法 決策樹(shù)算法 與決策樹(shù)相關(guān)的重要算法 Hunt,Marin和 Stone 于 1966年研制的 CLS學(xué)習(xí)系統(tǒng)，用于學(xué)習(xí)單個(gè)概 念。本質(zhì)上決策樹(shù)是通過(guò)一系列規(guī)則對(duì)數(shù)據(jù)進(jìn)行分類的過(guò)程。 預(yù)測(cè)應(yīng)用（推論） 根據(jù)建立的分類模型，對(duì)測(cè)試集合進(jìn)行測(cè)試。 分類方法的實(shí)例包括：決策樹(shù)分類法、基于規(guī)則的分類法、 神經(jīng)網(wǎng)絡(luò)、支持向量級(jí)、樸素貝葉斯分類方法等。學(xué)習(xí)算法得到的 模型不僅要很好擬合輸入數(shù)據(jù)，還要能夠正確地預(yù)測(cè)未知樣本的 類標(biāo)號(hào)。用元組 (X,y)表示，其中， X 是屬性集合， y是一個(gè) 特殊的屬性，指出樣例的類標(biāo)號(hào)（也稱為分類屬性或者目標(biāo)屬性） 決策樹(shù)基本概念 關(guān)于分類問(wèn)題 名稱 體溫 表皮覆蓋 胎生 水生動(dòng)物 飛行動(dòng)物 有腿 冬眠 類標(biāo)號(hào) 人類 恒溫 毛發(fā) 是 否 否 是 否 哺乳動(dòng)物 海龜 冷血 鱗片 否 半 否 是 否 爬行類 鴿子 恒溫 羽毛 否 否 是 是 否 鳥(niǎo)類 鯨 恒溫 毛發(fā) 是 是 否 否 否 哺乳類 X y 分類與回歸 分類目標(biāo)屬性 y是離散的，回歸目標(biāo)屬性 y是連續(xù)的 決策樹(shù)基本概念 解決分類問(wèn)題的一般方法 分類技術(shù)是一種根據(jù)輸入數(shù)據(jù)集建立分類模型的系統(tǒng)方法。決策樹(shù) 決策樹(shù)基本概念 決策樹(shù)算法 主要內(nèi)容 決策樹(shù)基本概念 決策樹(shù)算法 決策樹(shù)基本概念 關(guān)于分類問(wèn)題 分類（ Classification）任務(wù)就是通過(guò)學(xué)習(xí)獲得一個(gè)目標(biāo)函數(shù) （ Target Function） f, 將每個(gè)屬性集 x映射到一個(gè)預(yù)先定義好的類 標(biāo)號(hào) y。 分類任務(wù)的輸入數(shù)據(jù)是紀(jì)錄的集合，每條記錄也稱為實(shí)例 或者樣例。 分類技術(shù)一般是用一種學(xué)習(xí)算法確定分類模型，該模型可以很好 地?cái)M合輸入數(shù)據(jù)中類標(biāo)號(hào)和屬性集之間的聯(lián)系。因此，訓(xùn)練算法的主要目標(biāo)就是要建立具有很好的泛化 能力模型，即建立能夠準(zhǔn)確地預(yù)測(cè)未知樣本類標(biāo)號(hào)的模型。 決策樹(shù)基本概念 解決分類問(wèn)題的一般方法 通過(guò)以上對(duì)分類問(wèn)題一般方法的描述，可以看出分類問(wèn)題 一般包括兩個(gè)步驟： 模型構(gòu)建（歸納） 通過(guò)對(duì)訓(xùn)練集合的歸納，建立分類模型。 決策樹(shù)基本概念 解決分類問(wèn)題的一般方法 TID A1 A2 A3 類 1 Y 100 L N 2 N 125 S N 3 Y 400 L Y 4 N 415 M N 學(xué)習(xí)算法 學(xué)習(xí)模型 模型 應(yīng)用模型 TID A1 A2 A3 類 1 Y 100 L ？ 2 N 125 S ？ 3 Y 400 L ？ 4 N 415 M ？ 訓(xùn)練集（類標(biāo)號(hào)已知） 檢驗(yàn)集（類標(biāo)號(hào)未知） 歸納 推論 決策樹(shù)基本概念 決策樹(shù) 決策樹(shù)是一種典型的分類方法，首先對(duì)數(shù)據(jù)進(jìn)行處理，利用 歸納算法生成可讀的規(guī)則和決策樹(shù)，然后使用決策對(duì)新數(shù)據(jù)進(jìn)行 分析。 決策樹(shù)基本概念 決策樹(shù)的優(yōu)點(diǎn) 推理過(guò)程容易理解，決策推理過(guò)程可以表示成 If Then形式； 推理過(guò)程完全依賴于屬性變量的取值特點(diǎn)； 可自動(dòng)忽略目標(biāo)變量沒(méi)有貢獻(xiàn)的屬性變量，也為判斷屬性 變量的重要性，減少變量的數(shù)目提供參考。 1979年 , . Quinlan 給出 ID3算法，并在 1983年和 1986年對(duì) ID3 進(jìn)行了總結(jié)和簡(jiǎn)化，使其成為決策樹(shù)學(xué)習(xí)算法的典型。 1988年， Utgoff 在 ID4基礎(chǔ)上提出了 ID5學(xué)習(xí)算法，進(jìn)一步提高了效率。 另一類決策樹(shù)算法為 CART，與 ， CART的決策樹(shù)由二元邏輯問(wèn)題生成，每個(gè)樹(shù)節(jié)點(diǎn)只有兩個(gè)分枝，分別包括學(xué)習(xí)實(shí)例的正例與反例。 年齡？ 學(xué)生？ 信譽(yù)？ 買 青 中 老 否 是 優(yōu) 良 不買 買 買 不買 決策樹(shù)中最上面的結(jié)點(diǎn)稱為根結(jié)點(diǎn)。每個(gè)分支是一 個(gè)新的決策結(jié)點(diǎn)，或者是樹(shù)的葉子。 每個(gè)葉結(jié)點(diǎn)代表一種可能的分類結(jié)果 在沿著決策樹(shù)從上到下的遍歷過(guò)程中，在每個(gè)結(jié)點(diǎn)都有一個(gè) 測(cè)試。這一過(guò)程就是利用決策樹(shù)進(jìn)行分類的過(guò)程， 利用若干個(gè)變量來(lái)判斷屬性的類別 ID3 決策樹(shù)算法 ID3算法主要針對(duì)屬性選擇問(wèn)題。 該方法使用信息增益度選擇測(cè)試屬性。 從直覺(jué)上講，小概率事件比大概率事件包含的信息量大。 如何度量信息量的大小？ ID3 –信息量大小的度量 決策樹(shù)算法 Shannon1948年提出的信息論理論。 假設(shè)有 n個(gè)互不相容的事件 a1,a2,a3,….,an,它們中有且僅有一個(gè) 發(fā)生，則其平均的信息量可如下度量： ??????ni iiniin apapaIaaaI12121 )(1l o g)()(), . . . ,()(1log)()(2iii apapaI ?ID3 –信息量大小的度量 決策樹(shù)算法 ??????ni iiniin apapaIaaaI12121 )(1l o g)()(), . . . ,(上式，對(duì)數(shù)底數(shù)可以為任何數(shù)，不同的取值對(duì)應(yīng)了熵的不同單位。 更一般地，如果目標(biāo)屬性具有 c個(gè)不同的值，那么 S 相對(duì)于 c個(gè)狀態(tài)的分類的熵定義為 決策樹(shù)算法 用 信息增益 度量 熵的降低程度 屬性 A 的 信息增益 ，使用屬性 A分割樣例集合 S 而導(dǎo)致的熵的降低程度 Gain (S, A)是 在知道屬性 A的值后可以節(jié)省的二進(jìn)制位數(shù) 例子，注意是對(duì)當(dāng)前樣例集合計(jì)算上式 ()( , ) ( ) ( )v vv V a l u e s ASG a i n S A E n t r o p y S E n t r o p y SS??? ?理解信息熵 信息熵是用來(lái)衡量一個(gè)隨機(jī)變量出現(xiàn)的期望值，一個(gè)變量的信息熵越大，那么它出現(xiàn)的各種情況也就越多，也就是包含的內(nèi)容多，我們要描述它就需要付出更多的表達(dá)才可以，也就是需要更多的信息才能
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1