【正文】 ANK Y E A R S T E N U R E DT o m A s s i s t a n t P r o f 2 noM e r l i s a A s s o c i a t e P r o f 7 noG e o r g e P r o f e s s o r 5 y e sJ o s e p h A s s i s t a n t P r o f 7 y e s未知數(shù)據(jù) (Jeff, Professor, 4) Tenured? 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 6 有監(jiān)督和無(wú)監(jiān)督學(xué)習(xí) ? 有監(jiān)督學(xué)習(xí) (分類(lèi) ) – 訓(xùn)練集是帶有類(lèi)標(biāo)簽的 – 新的數(shù)據(jù)是基于訓(xùn)練集進(jìn)行分類(lèi)的。 – 用于創(chuàng)建模型的數(shù)據(jù)集叫 :訓(xùn)練集 – 模型可以用分類(lèi)規(guī)則，決策樹(shù)，或者數(shù)學(xué)方程的形式來(lái)表達(dá)。2020年 9月 16日星期三 Data Mining: Concepts and Techniques 1 第七章：分類(lèi)和預(yù)測(cè) 什么是分類(lèi)？什么是預(yù)測(cè) 關(guān)于分類(lèi)和預(yù)測(cè)的一些問(wèn)題 使用決策樹(shù)進(jìn)行分類(lèi) 貝葉斯分類(lèi) （向后傳播分類(lèi)）帶回饋的分類(lèi) 基于關(guān)聯(lián)規(guī)則的分類(lèi) 其他分類(lèi)方法 預(yù)測(cè) 分類(lèi)法的準(zhǔn)確性 總結(jié) 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 2 分類(lèi)： – 預(yù)測(cè)種類(lèi)字段 – 基于訓(xùn)練集形成一個(gè)模型，訓(xùn)練集中的類(lèi)標(biāo)簽是已知的。 ? 模型使用 : 用創(chuàng)建的模型預(yù)測(cè)未來(lái)或者類(lèi)別未知的記錄 – 估計(jì)模型的準(zhǔn)確率 ? 使用創(chuàng)建的模型在一個(gè)測(cè)試集上進(jìn)行預(yù)測(cè)，并將結(jié)果和實(shí)際值進(jìn)行比較。 ? 無(wú)監(jiān)督學(xué)習(xí) (聚集 ) – 訓(xùn)練集是沒(méi)有類(lèi)標(biāo)簽的。 ? 規(guī)則好壞的評(píng)價(jià) – 決策樹(shù)的大小 – 分類(lèi)規(guī)則的簡(jiǎn)明性 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 9 （ 188頁(yè)） ? 決策樹(shù) – 一個(gè)類(lèi)似流程圖的樹(shù)狀結(jié)構(gòu) – 內(nèi)部節(jié)點(diǎn)上選用一個(gè)屬性進(jìn)行分割 – 每個(gè)分叉都是分割的一個(gè)部分 – 葉子節(jié)點(diǎn)表示一個(gè)分布 ? 決策樹(shù)生成算法分成兩個(gè)步驟 – 樹(shù)的生成 ? 開(kāi)始，數(shù)據(jù)都在根節(jié)點(diǎn) ? 遞歸的進(jìn)行數(shù)據(jù)分片 – 樹(shù)的修剪 ? 去掉一些可能是噪音或者異常的數(shù)據(jù) ? 決策樹(shù)使用 : 對(duì)未知數(shù)據(jù)進(jìn)行分割 – 按照決策樹(shù)上采用的分割屬性逐層往下，直到一個(gè)葉子節(jié)點(diǎn) 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 10 訓(xùn)練集 a g e i n co me st u d e n t cre d i t _ ra t i n g b u ys_ co mp u t e r=3 0 h i g h no f a i r no=3 0 h i g h no e x ce l l e n t no3 0 …4 0 h i g h no f a i r ye s4 0 me d i u m no f a i r ye s4 0 l o w ye s f a i r ye s4 0 l o w ye s e x ce l l e n t no3 1 …4 0 l o w ye s e x ce l l e n t ye s=3 0 me d i u m no f a i r no=3 0 l o w ye s f a i r ye s4 0 me d i u m ye s f a i r ye s=3 0 me d i u m ye s e x ce l l e n t ye s3 1 …4 0 me d i u m no e x ce l l e n t ye s3 1 …4 0 h i g h ye s f a i r ye s4 0 me d i u m no e x ce l l e n t noID3算法 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 11 Output: A Decision Tree for “buys_puter” age? overcast student? credit rating? no yes fair excellent =30 40 no no yes yes yes 30..40 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 12 決策樹(shù)算法 ? 基本算法（貪心算法） – 自上而下分而治之的方法 – 開(kāi)始時(shí)，所有的數(shù)據(jù)都在根節(jié)點(diǎn) – 屬性都是離散值字段 (如果是連續(xù)的，將其離散化 ) – 所有記錄用所選屬性遞歸的進(jìn)行分割 – 屬性的選擇是基于一個(gè)啟發(fā)式規(guī)則或者一個(gè)統(tǒng)計(jì)的度量 (如 , information gain) ? 停止分割的條件 – 一個(gè)節(jié)點(diǎn)上的數(shù)據(jù)都是屬于同一個(gè)類(lèi)別 – 沒(méi)有屬性可以再用于對(duì)數(shù)據(jù)進(jìn)行分割 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 13 屬性選擇的統(tǒng)計(jì)度量 ? Information gain (ID3/) – 所有屬性假設(shè)都是離散值字段 – 經(jīng)過(guò)修改之后可以適用于連續(xù)值字段 ? Gini index (IBM Intelligent Miner) – 能夠適用于離散值和連續(xù)值字段 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 14 Information Gain (ID3/) 190頁(yè) ? 選擇屬性的標(biāo)準(zhǔn)：具有最高 Information Gain ? 假設(shè)有兩個(gè)類(lèi) , P 和 N – 假設(shè)集合 S中含有 p個(gè)類(lèi)別 P的記錄 ,n個(gè)類(lèi)別 N的記錄 – 決定任意一個(gè)記錄屬于類(lèi)別 P或者 N所需要的 information. npnnpnnppnppnpI??????? 22 l o gl o g),(2020年 9月 16日星期三 Data Mining: Concepts and Techniques 15 Information Gain 在決策樹(shù)中的使用 ? 假設(shè)使用屬性 A將把集合 S分成 V份 {S1, S2 , …, Sv} – 如果 Si 中包含 pi 個(gè)類(lèi)別為 P的記錄 , ni 個(gè)類(lèi)別為 N,的記錄。 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 22 對(duì)基本決策樹(shù)的提高 ? 加入對(duì)連續(xù)字段的支持 – 采用 A=V的形式 ? 處理空值 – 用最常見(jiàn)的值代替 – 每個(gè)可能的值都給一個(gè)概率 ? 屬性構(gòu)造 – 在現(xiàn)有屬性上創(chuàng)建新的屬性 ,主要是針對(duì)一些稀疏屬性 – 從而降低 fragmentation, repetition, and replication 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 23 在大型數(shù)據(jù)庫(kù)中進(jìn)行分類(lèi) ? 分類(lèi) —在統(tǒng)計(jì)和機(jī)器學(xué)習(xí)中有廣泛的研究 ? 伸縮性 : 對(duì)幾百萬(wàn)記錄和幾百個(gè)屬性進(jìn)行訓(xùn)練的時(shí)候，能夠達(dá)到一定的速度。 屬性值 187。 ? 引進(jìn)的數(shù)據(jù)結(jié)構(gòu)：類(lèi)分布表 187。如果不同字段的值大于預(yù)定值，使用貪心算法 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 30 Sliq分類(lèi)算法 ? 樹(shù)的修剪： 采用了 MDL策略 ? Cost(M,D)=cost(D|M)+cost(M) ? 整個(gè)算法包括兩個(gè)部分： ? 編碼方法 ? 不同子樹(shù)的比較方法 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 31 基于數(shù)據(jù)立方體的決策樹(shù) ? Integration of generalization with decisiontree induction (Kamber et al’97). ? 在最低概念層上進(jìn)行分類(lèi) – 例如 , precise temperature, humidity, outlook, etc. – 低的層次，分散的類(lèi)別，過(guò)多的葉子節(jié)點(diǎn) – 模型解釋的問(wèn)題 . ? 基于 Cube的多層分類(lèi) – 在多個(gè)層次上進(jìn)行相關(guān)性分析 . – 在多個(gè)層次上進(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 樸素貝葉斯分類(lèi) ? 假定有 m個(gè)類(lèi) C1,…Cm,對(duì)于數(shù)據(jù)樣本 X,分類(lèi)法將預(yù)測(cè) X屬于類(lèi) 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)對(duì)于所有類(lèi)都是常數(shù) ,只需最大化 P(X|Ci) P(Ci) 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 36 ? 計(jì)算 P(X|Ci),樸素貝葉斯分類(lèi)假設(shè)類(lèi)條件獨(dú)立 .即給定樣本屬性值相互條件獨(dú)立 . P(x1,…,xk|C) = P(x1|C)P(hot|p)2/9P(n) = P(rain|n)P(n) = 2/55/14 = ? 樣本 X 分配給 類(lèi) n (don’t play) 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 39 貝葉斯網(wǎng)絡(luò) ? 樸素貝葉斯算法假定類(lèi)條件獨(dú)立 ,當(dāng)假定成立時(shí) ,該算法是最精確的 .然而實(shí)踐中 ,變量之間的依賴(lài)可能存在 . ? 貝葉斯網(wǎng)絡(luò)解決了這個(gè)問(wèn)題 ,它包括兩部分 ,有向無(wú)環(huán)圖和條件概率表 (CPT). 2020年 9月 16日