【正文】 是 pj 類別 j出現(xiàn)的頻率 ? 如果集合 T分成兩部分 N1 and N2 。 那么這個分割的Gini就是 ? 提供最小 Ginisplit 就被選擇作為分割的標(biāo)準(zhǔn) (對于每個屬性都要遍歷所有可以的分割方法 ). ???? nj p jTgini 1 21)()()()( 2211 Tg i n iNNTg i n iNNTg i n i s p l i t ??2020年 9月 16日星期三 Data Mining: Concepts and Techniques 18 幾種經(jīng)典算法介紹 ? CART min(P(c1),P(c2)) 2P(c1)P(c2) [P(c1)logP(c1)]+[P(c2)logP(c2)] (ID3) ? (ID3) ? 對種類字段處理時，缺省是對每個值作為一個分割 ? Gain和 Gain Ratio ? CHAID ? 在 Overfitting前停止樹的生成 ? 必須都是種類字段 ? 選擇分割。 X2檢驗(yàn) 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 19 從樹中生成分類規(guī)則 ? 用 IFTHEN 這種形式來表現(xiàn)規(guī)則 ? 每個葉子節(jié)點(diǎn)都創(chuàng)建一條規(guī)則 ? 每個分割都成為一個規(guī)則中的一個條件 ? 葉子節(jié)點(diǎn)中的類別就是 Then的內(nèi)容 ? 規(guī)則對于人來說更容易理解 ? 例子 IF age = ―=30‖ AND student = ―no‖ THEN buys_puter = ―no‖ IF age = ―=30‖ AND student = ―yes‖ THEN buys_puter = ―yes‖ IF age = ―31…40‖ THEN buys_puter = ―yes‖ IF age = ―40‖ AND credit_rating = ―excellent‖ THEN buys_puter = ―yes‖ IF age = ―=30‖ AND credit_rating = ―fair‖ THEN buys_puter = ―no‖ 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 20 在分類中避免過度適應(yīng)(Overfit) ? 在訓(xùn)練集中生成的會可能會 Overfit – 太多的分支 , 有些可能是對異常例外的反映 – 在進(jìn)行預(yù)測的時候準(zhǔn)確率比較差 ? 兩種 – 預(yù)修剪 : ? 難點(diǎn)：選擇一個域值比較困難 – 后修建 : 先生成完整的樹，然后進(jìn)行修剪 ? 使用另外一個的一個測試集來決定哪個樹最好 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 21 決定最終樹大小的方法 ? 使用部分?jǐn)?shù)據(jù)： ? 使用全部數(shù)據(jù)： – 使用一個統(tǒng)計(jì)測試 (., chisquare) 來估計(jì)保留或者修剪掉一個分支的影響 ? 使用最小描述長度 (MDL) 原則 : – 當(dāng)樹的 Coding最小的時候最佳。 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 22 對基本決策樹的提高 ? 加入對連續(xù)字段的支持 – 采用 A=V的形式 ? 處理空值 – 用最常見的值代替 – 每個可能的值都給一個概率 ? 屬性構(gòu)造 – 在現(xiàn)有屬性上創(chuàng)建新的屬性 ,主要是針對一些稀疏屬性 – 從而降低 fragmentation, repetition, and replication 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 23 在大型數(shù)據(jù)庫中進(jìn)行分類 ? 分類 —在統(tǒng)計(jì)和機(jī)器學(xué)習(xí)中有廣泛的研究 ? 伸縮性 : 對幾百萬記錄和幾百個屬性進(jìn)行訓(xùn)練的時候，能夠達(dá)到一定的速度。 ? 在數(shù)據(jù)挖掘中為什么使用決策樹 ? – 相對比較快的學(xué)習(xí)速度 (和其它學(xué)習(xí)方法比較來說 ) – 能夠轉(zhuǎn)換成容易理解的分類規(guī)則 – 能夠使用 SQL語句查詢數(shù)據(jù)庫 – 分類的準(zhǔn)確率也不差 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 24 Scalable Decision Tree Induction 數(shù)據(jù)挖掘中提出的方法 ? SLIQ (EDBT’96 — Mehta et al.) ? SPRINT (VLDB’96 — J. Shafer et al.) ? PUBLIC (VLDB’98 — Rastogi amp。 Shim) ? RainForest (VLDB’98 — Gehrke, Ramakrishnan amp。 Ganti) – builds an AVClist (attribute, value, class label) 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 25 SLIQ算法介紹 ? 總攬： 預(yù)排序、廣度優(yōu)先、種類字段快速分割、 MDL修剪方法 ? 預(yù)排序： 減少對數(shù)值字段進(jìn)行排序消耗的時間 ? 屬性列表（ attribute list）： 187。 屬性值 187。 索引 ? 類列表（ class list）： 187。 類標(biāo)簽 187。 指向樹中的節(jié)點(diǎn) 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 26 Sliq分類算法 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 27 Sliq分類算法 ? 進(jìn)行節(jié)點(diǎn)的分割： 廣度優(yōu)先 ? 對當(dāng)前樹中所有葉子節(jié)點(diǎn)分割的計(jì)算都是在同一遍中完成的。 ? 引進(jìn)的數(shù)據(jù)結(jié)構(gòu)：類分布表 187。 數(shù)值字段：類標(biāo)簽、頻率 187。 種類字段：屬性值、類標(biāo)簽、頻率 ? 對數(shù)值字段進(jìn)行分割計(jì)算： 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 28 Sliq分類算法 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 29 Sliq分類算法 ? 對種類字段進(jìn)行分割： ? 通過對數(shù)據(jù)的掃描生成類分布表 ? 尋找分割集合 187。如果不同字段的值少于預(yù)定值，進(jìn)行完全搜索 187。如果不同字段的值大于預(yù)定值，使用貪心算法 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 30 Sliq分類算法 ? 樹的修剪： 采用了 MDL策略 ? Cost(M,D)=cost(D|M)+cost(M) ? 整個算法包括兩個部分： ? 編碼方法 ? 不同子樹的比較方法 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 31 基于數(shù)據(jù)立方體的決策樹 ? Integration of generalization with decisiontree induction (Kamber et al’97). ? 在最低概念層上進(jìn)行分類 – 例如 , precise temperature, humidity, outlook, etc. – 低的層次，分散的類別，過多的葉子節(jié)點(diǎn) – 模型解釋的問題 . ? 基于 Cube的多層分類 – 在多個層次上進(jìn)行相關(guān)性分析 . – 在多個層次上進(jìn)行 Information Gain的計(jì)算 . 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 32 結(jié)果顯示 (一 ) 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 33 結(jié) 果 顯 示 (二 ) 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 34 ? 后驗(yàn)概率 (posteriori probabilities):P(H|X)表示條件 X下 H的概率 . ? 貝葉斯定理 : P(H|X)=P(X|H)P(H)/P(X) 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 35 樸素貝葉斯分類 ? 假定有 m個類 C1,…Cm,對于數(shù)據(jù)樣本 X,分類法將預(yù)測 X屬于類 Ci,當(dāng)且僅當(dāng) P(Ci|X) P(Cj|X),1=j=m,j!=i ? 根據(jù)貝葉斯定理 , P(Ci|X)=P(X|Ci)P(Ci)/P(X) 由于 P(X)對于所有類都是常數(shù) ,只需最大化 P(X|Ci) P(Ci) 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 36 ? 計(jì)算 P(X|Ci),樸素貝葉斯分類假設(shè)類條件獨(dú)立 .即給定樣本屬性值相互條件獨(dú)立 . P(x1,…,xk|C) = P(x1|C)…P(xk|C) 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 37 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 38 ? 樣本 X = rain, hot, high, false ? P(X|p)P(p) = P(rain|p)P(hot|p)P(high|p)P(false|p)P(p) = 3/92/93/96/99/14 = ? P(X|n)P(n) = P(rain|n)P(hot|n)P(high|n)P(false|n)P(n) = 2/52/54/52/55/14 = ? 樣本 X 分配給 類 n (don’t play) 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 39 貝葉斯網(wǎng)絡(luò) ? 樸素貝葉斯算法假定類條件獨(dú)立 ,當(dāng)假定成立時 ,該算法是最精確的 .然而實(shí)踐中 ,變量之間的依賴可能存在 . ? 貝葉斯網(wǎng)絡(luò)解決了這個問題 ,它包括兩部分 ,有向無環(huán)圖和條件概率表 (CPT). 2020年 9月