【正文】 機(jī)器學(xué)習(xí) — 歸納學(xué)習(xí)：決策樹 ? 確定子樹根結(jié)點(diǎn) ?當(dāng) A1=0時(shí)，所有對(duì)象類標(biāo)簽均為 1，此分支結(jié)束。 )()()(ASp litiAGainAga inra tio ??????? kjjjjjnNPnNPASp lit i1)log ()(決策理論與方法 智能決策理論與方法 機(jī)器學(xué)習(xí) — 歸納學(xué)習(xí)：決策樹 ?示例計(jì)算 ? 確定根結(jié)點(diǎn) ?I(P， N)=10/16log(10/16)6/16log(6/16)=5/8log53/8log3+3= ?E(A0)=1/2(4/8log(4/8)4/8log(4/8))+1/2(6/8log(6/8)2/8log(2/8))=3/23/8log3= ?E(A1)=13/8log3= ?E(A2)=13/16log3= ?E(A3)=35/8log53/8log3= ?因此選 A1作為起始根結(jié)點(diǎn)。 ?? ???kjjjjj NPINPNPAE1),()(決策理論與方法 智能決策理論與方法 機(jī)器學(xué)習(xí) — 歸納學(xué)習(xí)：決策樹 ? 信息增益率 ： ? 其中： 目前一種比較流行的決策樹算法 就是以信息增益率作為測(cè)試屬性的選擇條件。 )log ()log (),( NP NNP NNP PNP PNPI ???????決策理論與方法 智能決策理論與方法 機(jī)器學(xué)習(xí) — 歸納學(xué)習(xí)：決策樹 以 A為測(cè)試屬性的 期望信息熵 為 以 A為根節(jié)點(diǎn)的 信息增益 是： Gain(A)=I(P,N)E(A) ? ID3的策略就是 選擇信息增益最大的屬性作為測(cè)試屬性 。 ? 窗口技術(shù) ：對(duì)于訓(xùn)練集很大的情形可選擇其某個(gè)子集 (稱為窗口 )構(gòu)造一棵決策樹，如果該決策樹對(duì)訓(xùn)練集中的其它樣本的判決效果很差，則擴(kuò)大窗口，選擇不能被正確判別的樣本加入到窗口中，再建立一個(gè)新的決策樹，重復(fù)這個(gè)過(guò)程得到最終的決策樹， 顯然不同的初始窗口會(huì)產(chǎn)生不同的決策樹。 ? 產(chǎn)生根節(jié)點(diǎn) T， T包含所有的訓(xùn)練樣本； ? 如果 T中的所有樣本都是正例，則產(chǎn)生一個(gè)標(biāo)有“ 1”的節(jié)點(diǎn)作為 T的子節(jié)點(diǎn)，并結(jié)束； ? 如果 T中的所有樣本都是反例，則產(chǎn)生一個(gè)標(biāo)有“ 1”的節(jié)點(diǎn)作為 T的子節(jié)點(diǎn)，并結(jié)束； ? 選擇一個(gè)屬性 A(如何選 ?)，根據(jù)該屬性的不同取值 v1,v2,…, vn將T中的訓(xùn)練集劃分為 n個(gè)子集，并根據(jù)這 n個(gè)子集建立 T的 n個(gè)子節(jié)點(diǎn) T1,T2,…,T n，并分別以 A=vi作為從 T到 Ti的分支符號(hào)； ? 以每個(gè)子節(jié)點(diǎn) Ti為根建立新的子樹。 所有的決策樹都有一等價(jià)的 ANN表示；也可用 SVM實(shí)現(xiàn)相同的功能。 從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)都有唯一的一條路徑，這條路徑就是一條決策“規(guī)則”。 所謂決策樹是一個(gè)類似流程圖的樹結(jié)構(gòu)，其中樹的內(nèi)結(jié)點(diǎn)對(duì)應(yīng)屬性或?qū)傩约總€(gè)分枝表示檢驗(yàn)結(jié)果 (屬性值 )，樹枝上的葉結(jié)點(diǎn)代表所關(guān)心的因變量的取值 (類標(biāo)簽 )，最頂端的結(jié)點(diǎn)稱為根結(jié)點(diǎn)?？朔^(guò)度泛化必須有相應(yīng)的終止泛化算法的策略。設(shè) A表示信息系統(tǒng)中的某個(gè)屬性如 Animal，a,b,… 分別為對(duì)象 u,v,… 在屬性 A上的取值，若 s是概念樹上 a,b,… 的父結(jié)點(diǎn)，則基于概念樹爬升的泛化規(guī)則表示為： Nick等人給出了一種面向?qū)傩缘臍w納算法。該規(guī)則特別有用的方式是通過(guò)擴(kuò)展某個(gè)特定概念的取值范圍而增加選項(xiàng)。消除一個(gè)條件，則該概念被泛化。泛化所得到的結(jié)論并不總是正確的。 決策理論與方法 智能決策理論與方法 機(jī)器學(xué)習(xí) — 歸納學(xué)習(xí)：泛化 ?歸納學(xué)習(xí) 是指從給定的關(guān)于某個(gè)概念的一系列已知的正例和反例中歸納出一個(gè)通用的概念描述。決策理論與方法 (4) —— 智能決策理論與方法 (2) 合肥工業(yè)大學(xué)管理學(xué)院 Wednesday, March 03, 2023 智能決策理論與方法 智能決策理論的形成背景 知識(shí)發(fā)現(xiàn) 粗糙集理論 機(jī)器學(xué)習(xí) 決策理論與方法 智能決策理論與方法 機(jī)器學(xué)習(xí) ?機(jī)器學(xué)習(xí) 是從模擬人類的學(xué)習(xí)行為出發(fā)，研究客觀世界和獲取各種知識(shí)與技能的一些基本方法（如歸納、泛化、特化、類比等），并借助于計(jì)算機(jī)科學(xué)與技術(shù)原理建立各種學(xué)習(xí)模型，從根本上提高計(jì)算機(jī)智能和學(xué)習(xí)能力。 研究?jī)?nèi)容 是根據(jù)生理學(xué)、認(rèn)知科學(xué)對(duì)人類學(xué)習(xí)機(jī)理的了解，建立人類學(xué)習(xí)的計(jì)算模型或認(rèn)知模型；發(fā)展各種學(xué)習(xí)理論和學(xué)習(xí)方法，研究通用的學(xué)習(xí)算法并進(jìn)行理論上的分析；建立面向任務(wù)且具有特定應(yīng)用的學(xué)習(xí)系統(tǒng)。 ?泛化 (Generalization)是用來(lái)擴(kuò)展一假設(shè)的語(yǔ)義信息，使其能夠包含更多的正例。 ?常用泛化方法 ： ? 將常量轉(zhuǎn)為變量規(guī)則 ：對(duì)于概念 F(v)，如果 v的某些取值a,b,… 使 F(v)成立，則這些概念可被泛化為：對(duì)于 v的所有值， F(v)均成立： )()(|)()( vFvbFaF ???? ?決策理論與方法 智能決策理論與方法 機(jī)器學(xué)習(xí) — 歸納學(xué)習(xí)：泛化 ? 消除條件規(guī)則 ：一個(gè)合取條件可看作是對(duì)滿足此概念的可能實(shí)例集的一個(gè)約束。 ? 添加選項(xiàng) ：通過(guò)添加更多條件，使得有更多的實(shí)例滿足概念而使該概念泛化。 ? 將合取轉(zhuǎn)為析取規(guī)則 )()(Re|)()()(Re vApplevdvApplevCi rclevd ???? )()()(Re|)()(Re vApplevBl uevdvApplevd ????)()()(Re|)()()(Re vApplevCi rclevdvApplevCi rclevd ?????決策理論與方法 智能決策理論與方法 機(jī)器學(xué)習(xí) — 歸納學(xué)習(xí)：泛化 ? 爬升概念樹規(guī)則 ：通過(guò)爬升概念樹，低層概念被較高層概念替代。 ? 過(guò)度泛化問(wèn)題 ? 當(dāng)某個(gè)屬性被爬升至過(guò)高的概念層會(huì)導(dǎo)致沖突的產(chǎn)生，這種現(xiàn)象稱為過(guò)度泛化。 sxLxbvAauA??????????)()(|)()(?決策理論與方法 智能決策理論與方法 機(jī)器學(xué)習(xí) — 歸納學(xué)習(xí)：泛化 動(dòng)物 哺乳類 鳥類 企鵝 食肉類 蹄類 飛禽類 走禽類 虎 印度豹 長(zhǎng)頸鹿 斑馬 信天翁 鷹 駝鳥 第 1層 第 2層 第 3層 第 4層 決策理論與方法 智能決策理論與方法 機(jī)器學(xué)習(xí) — 歸納學(xué)習(xí)：決策樹 ? 決策樹學(xué)習(xí) 是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法。 ? 決策樹學(xué)習(xí)采用自頂向下的遞歸方式，在決策樹的內(nèi)部結(jié)點(diǎn)進(jìn)行屬性值比較并根據(jù)不同的屬性值判斷從該結(jié)點(diǎn)向下的分支，在葉結(jié)點(diǎn)得到結(jié)論。 ? 當(dāng)經(jīng)過(guò)一批訓(xùn)練實(shí)例集的訓(xùn)練產(chǎn)生一顆決策樹，那么