第三周決策樹和Boostingppt課件

1、1分類: 根本概念分類: 根本概念決策樹基于規(guī)那么分類貝葉斯分類方法提高分類準確率的技術小結2什么是分類？分類，分類器銀行貸款員需求分析數(shù)據(jù)，以便搞清楚哪些貸款懇求者是“平安的；醫(yī)學研討人員分析癌癥數(shù)據(jù)，以便選擇治療方案數(shù)據(jù)分析義務都是分類，都需求構造一個分類器來預測類標號數(shù)值預測，預測器銷售經(jīng)理希望預測一位給定的顧客在雙11的一次購物期間將花多少錢數(shù)據(jù)分析義務就是數(shù)值預測，所構造的模型預測器預測一個延續(xù)值函數(shù)或有序值，而不是類標號3分類預測類標號 (離散的或標稱的)基于訓練集和類標號構建分類器，并對新的數(shù)據(jù)進展分類數(shù)值預測所構造的模型預測一個延續(xù)值函數(shù)，而不是類標號典型運用信譽卡/貸款同意:

2、醫(yī)療診斷: 腫瘤是良性的還是惡性的欺詐檢測: 一次買賣能否是欺詐的網(wǎng)頁分類: 屬于哪一類預測問題: 分類與數(shù)值預測4分類一個兩階段過程兩階段：學習階段構建分類模型和分類階段運用模型預測給定數(shù)據(jù)的類標號分類模型構建(學習階段): 描畫預先定義的類假設每個元組都屬于一個預先定義的類，由類標號屬性確定，類標號屬性是離散值的和無序的用于模型構建的元組集合稱為訓練集模型用分類規(guī)那么，決策樹，或數(shù)學公式表示模型運用(分類階段): 用于分類未知對象評價模型的準確性檢驗樣本的知標簽與模型的分類結果比較準確率是被模型正確分類的檢驗樣本所占的百分比檢驗集是獨立于訓練集的 (否那么過分擬合) 假設準確性是可接受的，

3、那么運用模型來分類新的數(shù)據(jù)5監(jiān)視和無監(jiān)視學習監(jiān)視學習 (分類)監(jiān)視:提供了每個訓練元組的類標號即分類器的學習在被告知每個訓練元組屬于哪個類的“監(jiān)視下進展的新的數(shù)據(jù)基于訓練集被分類無監(jiān)視學習 (聚類)每個訓練元組的類標號是未知的要學習的類的個數(shù)或集合也能夠事先不知道6階段 (1): 模型構建訓練數(shù)據(jù)分類算法IF rank = professorOR years 6THEN tenured = yes 分類器(模型)學習：用分類算法分析訓練數(shù)據(jù)7階段 (2): 運用模型預測分類器檢驗數(shù)據(jù)新數(shù)據(jù)(Jeff, Professor, 4)Tenured?分類：檢驗數(shù)據(jù)用于評價分類規(guī)那么的準確率8分類:

4、根本概念分類: 根本概念決策樹基于規(guī)那么分類貝葉斯分類方法提高分類準確率的技術小結9決策樹從有類標號的訓練元組中學習決策樹樹構造每個內(nèi)部結點非樹葉結點表示在一個屬性上的測試每個分枝代表該測試的一個輸出每個樹葉結點存放一個類標號樹的最頂層結點是根結點如何運用決策樹分類？給定一個類標號未知的元組X，在決策樹上測試該元組的屬性值。跟蹤一條由根到葉結點的途徑，該葉結點就存放著該元組的類預測。10決策樹歸納: 一個例子age?overcaststudent?credit rating?40noyesyesyes31.40nofairexcellentyesno訓練數(shù)據(jù)集: Buys_computer決策

5、樹:11決策樹歸納算法根底算法 (貪婪算法)決策樹以自頂向下遞歸的分治方式構造從訓練元組集和它們相關聯(lián)的類標號開場構造決策樹一切屬性是具有類別的 (假設是延續(xù)數(shù)值型的，那么它們需求事先離散化)基于選擇的屬性對元組進展遞歸劃分測試屬性基于統(tǒng)計學度量來選擇 (例如, 信息增益)停頓劃分的條件給定結點的一切元組都屬于同一個類沒有剩余屬性可以用來進一步劃分元組給定的分枝沒有元組算法根本戰(zhàn)略三個參數(shù)：D為數(shù)據(jù)分區(qū)，開場時，它是訓練元組和它們相應類標號的完選集。參數(shù)attribute_list是描畫元組屬性的列表。參數(shù)Attribute_selection_method用來選擇可以按類“最好地區(qū)分給定元組

6、的屬性，該過程運用一種屬性選擇度量信息增益或基尼指數(shù)。樹從單個結點N開場，N代表D中的訓練元組假設D中的元組都為同一類，那么結點N變成樹葉，并用該類標志它否那么，算法調(diào)用Attribute_selection_method確定分裂準那么。分裂準那么指定分裂屬性，并且也指出分裂點或分裂子集對分裂準那么的每個輸出，由結點N生長一個分枝。根據(jù)分裂屬性A的類型，有三種能夠的情況A是離散值的: 結點N的測試輸出直接對應于A的知值A是延續(xù)值的: 結點N的測試有兩個能夠的輸出，分別對應于條件Asplit_point, 其中split_point是分裂點A是離散值并且必需產(chǎn)生二叉樹: 在結點N的測試形如“A

7、SA？，其中SA是A的分裂子集算法: Generate_decision_tree。由數(shù)據(jù)分區(qū)D中的訓練元組產(chǎn)生決策樹。輸入:數(shù)據(jù)分區(qū)D, 訓練元組和他們對應類標號的集合attribute_list, 候選屬性的集合。Attribute_selection_method, 一個確定“最好地劃分數(shù)據(jù)元組為個體類的分裂準那么的過程。這個準那么由分裂屬性(splitting_attribute)和分裂點或劃分子集組成。輸出: 一棵決策樹。方法:(1) 創(chuàng)建一個結點N；(2) if D中的元組都在同一類C中 then(3) 前往N作為葉結點, 以類C標志;(4) if attribute_list為空

8、 then(5) 前往N作為葉結點, 標志為D中的多數(shù)類; /多數(shù)表決(6) 運用Attribute_selection_method (D, attribute_list), 找出“最好的splitting_criterion;(7) 用splitting_criterion標志結點N;(8) if splitting_attribute是離散值的，并且允許多路劃分 then /不限于二叉樹(9) 從attribute_list中刪除分裂屬性 ；(10) for splitting_criterion的每個輸出 j / 劃分元組并對每個分區(qū)產(chǎn)生子樹(11) 設Dj是D中 滿足輸出 j 的數(shù)據(jù)

9、元組的集合； /一個分區(qū)(12) if Dj為空 then(13) 加一個樹葉到結點N, 標志為D中的多數(shù)類 ；(14) else 加一個由Generate_decision_tree (Dj, attribute_list)前往的結點到N； endfor(15) 前往N；14屬性選擇度量: 信息增益 (ID3/C4.5)符號定義 ：設數(shù)據(jù)分區(qū)D為標志類元組的訓練集。假定類標號屬性具有m個不同值，定義m個不同類。設Ci,D是D中Ci類元組的集合。選擇具有最高信息增益的屬性A作為結點N的分裂屬性對D中的元組分類所需求的期望信息由下式給出:基于按A劃分對D的元組分類所需求的期望信息:按屬性A劃分的

10、信息增益Pi用|Ci,D|/|D| 估計15屬性選擇: 信息增益Class P: buys_computer = “yesClass N: buys_computer = “no 意思為14個樣本中有5個 “age split-point的元組集合.17屬性選擇: 增益率 (C4.5)信息增益度量傾向于選擇具有大量值的屬性C4.5 (ID3的后繼) 采用增益率來抑制這個問題 (規(guī)范化信息增益)GainRatio(A) = Gain(A)/SplitInfo(A)Ex.gain_ratio(income) = 0.029/1.557 = 0.019具有最大增益率的屬性作為分裂屬性18基尼指數(shù) (

11、CART)假設一個數(shù)據(jù)集D包含n個類，那么D的基尼指數(shù)定義為 其中 pj 是D中元組屬于類 j 的概率, 并用|Ci,D|/|D|估計假設數(shù)據(jù)集D基于屬性 A 被劃分成兩個子集D1 和 D2, 那么基尼指數(shù)定義為不純度降低:對于離散值屬性, 選擇該屬性產(chǎn)生最小基尼指數(shù)的子集作為它的分裂子集；對于延續(xù)值屬性，選擇產(chǎn)生最小基尼指數(shù)的點作為分裂點；產(chǎn)生最小基尼指數(shù)或最大不純度降低的屬性選為分裂屬性19基尼指數(shù)的計算例如數(shù)據(jù)集D 有 9 個buys_computer = “yes的元組和 5 個 “no的元組假設按income屬性子集low, medium將數(shù)據(jù)集劃分為D1(10個元組)和D2(4個元

12、組) Ginilow,high 是 0.458; Ginimedium,high 是 0.450. 因此在income的子集 low,medium上劃分, 由于 它的基尼指數(shù) 最小20過分擬合與樹剪枝過分擬合: 樹創(chuàng)建時，由于數(shù)據(jù)中的噪聲和離群點，會過分擬合訓練數(shù)據(jù)有很多分枝，一些是由于噪聲和離群點導致的異常預測準確率下降兩種方法來防止過分擬合先剪枝: 假設劃分一個結點后的元組低于預定義閾值，那么提早停頓樹的構建選取一個適當?shù)拈撝凳抢щy的后剪枝: 由 “完全生長的樹剪去子樹用回溯方式去除樹的一些點Use a set of data different from the training dat

13、a to decide which is the “best pruned tree21分類: 根本概念分類: 根本概念決策樹基于規(guī)那么分類貝葉斯分類方法提高分類準確率的技術小結22運用IF-THEN 規(guī)那么分類以 IF-THEN 規(guī)那么的方式表示學習得到的模型R: IF age = youth AND student = yes THEN buys_computer = yes“IF 部分稱為規(guī)那么前件或前提, “THEN 部分稱為規(guī)那么的結論在規(guī)那么前件，條件由一個或多個用邏輯銜接詞AND銜接的屬性測試組成；規(guī)那么的結論包含一個類預測對于給定的元組，假設規(guī)那么前件中的條件都成立，那么規(guī)那么

14、覆蓋了該元組規(guī)那么的評價: 覆蓋率和準確率ncovers 表示規(guī)那么R覆蓋的元組數(shù)ncorrect 表示規(guī)那么R正確分類的元組數(shù)coverage(R) = ncovers /|D| /* D: 訓練數(shù)據(jù)集*/accuracy(R) = ncorrect / ncovers23運用IF-THEN 規(guī)那么分類如何運用基于規(guī)那么的分類來預測給定元組X的類標號？假設規(guī)那么被X滿足，那么稱該規(guī)那么被觸發(fā)。例如，X=(age=youth, income=medium, student=yes, credit_rating=fair)X滿足規(guī)那么R，觸發(fā)該規(guī)那么。假設R是獨一滿足的規(guī)那么，那么該規(guī)那么激活，

15、前往X的類預測留意，觸發(fā)并不總意味激活，由于能夠有多個規(guī)那么被滿足假設多個規(guī)那么被觸發(fā)，那么需求處理沖突規(guī)模序: 把最高優(yōu)先權賦予具有“最苛刻要求的被觸發(fā)的規(guī)那么 (即, 具有最多屬性測試的)規(guī)那么序: 預先確定規(guī)那么的優(yōu)先次序?；陬惖男? 按類的普遍性降序排序基于規(guī)那么的序 (決策表): 根據(jù)規(guī)那么質(zhì)量的度量，規(guī)那么被組織成一個優(yōu)先權列表。最先出如今決策表中的被觸發(fā)的規(guī)那么具有最高優(yōu)先權，因此激活它的類預測。24age?student?credit rating?40noyesyesyes31.40nofairexcellentyesno例子: 從 buys_computer 決策樹提取規(guī)

16、那么R1: IF age = young AND student = no THEN buys_computer = noR2: IF age = young AND student = yes THEN buys_computer = yesR3: IF age = mid-age THEN buys_computer = yesR4: IF age = old AND credit_rating = excellent THEN buys_computer = noR5: IF age = old AND credit_rating = fair THEN buys_computer =

17、yes由決策樹提取規(guī)那么與決策樹相比，IF-THEN規(guī)那么能夠更容易了解，尤其是當決策樹非常大時對每條從根到樹葉結點的途徑創(chuàng)建一個規(guī)那么給定途徑上的每個分裂準那么的邏輯AND構成規(guī)那么的前件(“IF部分); 存放類預測的樹葉結點構成規(guī)那么的后件(“THEN部分)規(guī)那么是互斥的和窮舉的25規(guī)那么歸納:順序覆蓋算法順序覆蓋算法: 直接從訓練集中提取規(guī)那么典型的順序覆蓋算法: FOIL, AQ, CN2, RIPPER規(guī)那么被順序地學習, 給定類的每個規(guī)那么覆蓋該類的許多元組并且希望不覆蓋其他類的元組步驟: 一次學習一個規(guī)那么每學習一個規(guī)那么, 就刪除該規(guī)那么覆蓋的元組在剩下的元組上反復該過程，直到

18、滿足終止條件, 例如, 不再有訓練元組，或前往規(guī)那么的質(zhì)量低于用戶指定的閾值與決策樹對比: 決策樹歸納是同時學習一組規(guī)那么26根本順序覆蓋算法算法：順序覆蓋。學習一組IF-THEN分類規(guī)那么。輸入： D，類標志元組的數(shù)據(jù)集合。 Att-vals, 一切屬性與它們能夠值的集合。輸出：IF-THEN規(guī)那么的集合。方法：Rule_set=; /學習的規(guī)那么集初始為空for每個類c do repeat Rule=Learn_One_Rule (D, Att-vals, c); 從D中刪除被Rule覆蓋的元組； until 終止條件滿足； Rule_set=Rule_set+Rule /將新規(guī)那么添加到

19、規(guī)那么集endfor前往Rule_set;27如何Learn-One-Rule?從最普通的規(guī)那么開場: condition = empty(條件為空)經(jīng)過采用一種貪婪的深度優(yōu)先戰(zhàn)略添加新的屬性選擇最能提高規(guī)那么質(zhì)量的屬性規(guī)那么質(zhì)量度量: 同時思索覆蓋率和準確率Foil-gain (in FOIL & RIPPER): 用下式估計擴展條件而獲得的信息偏向于具有高準確率并且覆蓋許多正元組的規(guī)那么28分類: 根本概念分類: 根本概念決策樹基于規(guī)那么分類貝葉斯分類方法提高分類準確率的技術小結29貝葉斯定理: 根底貝葉斯定理:X 表示數(shù)據(jù)元組: 類標號未知H為某種假設，如數(shù)據(jù)元組X屬于某個特定類 C 分

20、類是確定P(H|X) (即后驗概率): 在條件X下，H的后驗概率，例如，X是一位35歲的顧客，其收入為4萬美圓。令H為某種假設，如顧客將購買計算機，那么P(H|X) 反映當我們知道顧客的年齡和收入時，顧客X將購買計算機的概率 。P(H) (先驗概率): H的先驗概率如, 恣意給定顧客將購買計算機的概率P(X): X的先驗概率，如顧客集合中的年齡為35歲并且收入為4萬美圓的概率P(X|H): 在條件H下，X的后驗概率例如, 知顧客X將購買計算機，該顧客是35歲并且收入為4萬美圓的概率30分類就是導出最大后驗概率設D是訓練元組和它們相關聯(lián)的類標號的集合。每個元組用一個n維屬性向量 X = (x1,

21、 x2, , xn)表示假定有m 個類C1, C2, , Cm.分類法將預測X屬于具有最高后驗概率的類, 即, 最大的P(Ci|X)。 假設P(Ci|X) 在一切k個類的P(Ck|X) 中最大，那么預測 X 屬于類Ci每個類的后驗概率可根據(jù)以下貝葉斯定理計算得到由于P(X)對一切類為常數(shù)，所以只需求最大化31樸素貝葉斯分類簡單假定: 屬性有條件地相互獨立 (即屬性之間不存在依賴關系):假設 Ak 是分類屬性, 那么P(xk|Ci)是D中屬性Ak的值為xk的Ci類的元組數(shù)除以D中Ci類的元組數(shù) |Ci, D|假設 Ak 是延續(xù)值屬性, P(xk|Ci) 通?；诰?和規(guī)范差 的高斯分布計算假定

22、延續(xù)值屬性服從均值為 、規(guī)范差為 的高斯分布，由下式定義32樸素貝葉斯分類Class:C1:buys_computer = yesC2:buys_computer = no待分類數(shù)據(jù): X = (age =30, Income = medium,Student = yes,Credit_rating = Fair)33樸素貝葉斯分類: 例子P(Ci): P(buys_computer = “yes) = 9/14 = 0.643 P(buys_computer = “no) = 5/14= 0.357為每個類計算 P(X|Ci) P(age = “=30 | buys_computer = “

23、yes) = 2/9 = 0.222 P(age = “= 30 | buys_computer = “no) = 3/5 = 0.6 P(income = “medium | buys_computer = “yes) = 4/9 = 0.444 P(income = “medium | buys_computer = “no) = 2/5 = 0.4 P(student = “yes | buys_computer = “yes) = 6/9 = 0.667 P(student = “yes | buys_computer = “no) = 1/5 = 0.2 P(credit_ratin

24、g = “fair | buys_computer = “yes) = 6/9 = 0.667 P(credit_rating = “fair | buys_computer = “no) = 2/5 = 0.4 X = (age = 30 , income = medium, student = yes, credit_rating = fair) P(X|Ci) : P(X|buys_computer = “yes) = 0.222 x 0.444 x 0.667 x 0.667 = 0.044 P(X|buys_computer = “no) = 0.6 x 0.4 x 0.2 x 0.

25、4 = 0.019P(X|Ci)*P(Ci) : P(X|buys_computer = “yes) * P(buys_computer = “yes) = 0.028 P(X|buys_computer = “no) * P(buys_computer = “no) = 0.007因此, X 屬于類(“buys_computer = yes)34防止零概率問題樸素貝葉斯分類預測需求每個條件概率是非零的，否那么，預測概率將會為零例如，假設一個具有1000個元組的數(shù)據(jù)集, income=low (0), income= medium (990), 和 income = high (10)運用拉普

26、拉斯校準 (或拉普拉斯估計法)每個組元組數(shù)加1Prob(income = low) = 1/1003Prob(income = medium) = 991/1003Prob(income = high) = 11/1003“校準的概率估計與對應的“未校準的估計很接近35樸素貝葉斯分類: 評價優(yōu)點易于實施大部分情況下可以獲得好的結果缺陷假設: 類條件獨立，因此損失準確性實踐中, 屬性之間經(jīng)常存在依賴性屬性之間存在依賴的情況不能經(jīng)過樸素貝葉斯分類建模怎樣處置這些依賴性? 貝葉斯信心網(wǎng)絡36分類: 根本概念分類: 根本概念決策樹基于規(guī)那么分類貝葉斯分類方法提高分類準確率的技術小結組合方法: 提高分類準確率組合方法把k個學習得到的模型, M1, M2, , Mk, 組合在一同，旨在創(chuàng)建 一個改良的復合分類模型M*流行的組合方法裝袋: 在一組分類器上平均預測提升: 基于一組分類器的加權表決37給定一個待分類元組X，它搜集由基分類器前往的類標號預測，并輸出占多數(shù)的類。裝袋: 自助聚集類似: 基于多個醫(yī)生多數(shù)表決的診斷訓練每次迭代i，d個元組的訓練集Di采用有放回抽樣從原始數(shù)據(jù)集D抽取從每個訓練集Di學習一個分類器模型Mi分類: 對一個未知元組X分類每個分類器Mi 前往它的類預測裝袋分類器M* 統(tǒng)計得票，并將得票最高的類賦予X預測: 經(jīng)過取給定元組的每個預測的