【正文】 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)督和無監(jiān)督學(xué)習(xí) ? 有監(jiān)督學(xué)習(xí) (分類 ) – 訓(xùn)練集是帶有類標簽的 – 新的數(shù)據(jù)是基于訓(xùn)練集進行分類的。 – 用于創(chuàng)建模型的數(shù)據(jù)集叫 :訓(xùn)練集 – 模型可以用分類規(guī)則，決策樹，或者數(shù)學(xué)方程的形式來表達。2020年 9月 16日星期三 Data Mining: Concepts and Techniques 1 第七章：分類和預(yù)測 什么是分類？什么是預(yù)測 關(guān)于分類和預(yù)測的一些問題 使用決策樹進行分類 貝葉斯分類 （向后傳播分類）帶回饋的分類 基于關(guān)聯(lián)規(guī)則的分類 其他分類方法 預(yù)測 分類法的準確性 總結(jié) 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 2 分類： – 預(yù)測種類字段 – 基于訓(xùn)練集形成一個模型，訓(xùn)練集中的類標簽是已知的。 ? 模型使用 : 用創(chuàng)建的模型預(yù)測未來或者類別未知的記錄 – 估計模型的準確率 ? 使用創(chuàng)建的模型在一個測試集上進行預(yù)測，并將結(jié)果和實際值進行比較。 ? 無監(jiān)督學(xué)習(xí) (聚集 ) – 訓(xùn)練集是沒有類標簽的。 ? 規(guī)則好壞的評價 – 決策樹的大小 – 分類規(guī)則的簡明性 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 9 （ 188頁） ? 決策樹 – 一個類似流程圖的樹狀結(jié)構(gòu) – 內(nèi)部節(jié)點上選用一個屬性進行分割 – 每個分叉都是分割的一個部分 – 葉子節(jié)點表示一個分布 ? 決策樹生成算法分成兩個步驟 – 樹的生成 ? 開始，數(shù)據(jù)都在根節(jié)點 ? 遞歸的進行數(shù)據(jù)分片 – 樹的修剪 ? 去掉一些可能是噪音或者異常的數(shù)據(jù) ? 決策樹使用 : 對未知數(shù)據(jù)進行分割 – 按照決策樹上采用的分割屬性逐層往下，直到一個葉子節(jié)點 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ù)據(jù)都在根節(jié)點 – 屬性都是離散值字段 (如果是連續(xù)的，將其離散化 ) – 所有記錄用所選屬性遞歸的進行分割 – 屬性的選擇是基于一個啟發(fā)式規(guī)則或者一個統(tǒng)計的度量 (如 , information gain) ? 停止分割的條件 – 一個節(jié)點上的數(shù)據(jù)都是屬于同一個類別 – 沒有屬性可以再用于對數(shù)據(jù)進行分割 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 13 屬性選擇的統(tǒng)計度量 ? Information gain (ID3/) – 所有屬性假設(shè)都是離散值字段 – 經(jīng)過修改之后可以適用于連續(xù)值字段 ? Gini index (IBM Intelligent Miner) – 能夠適用于離散值和連續(xù)值字段 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 14 Information Gain (ID3/) 190頁 ? 選擇屬性的標準：具有最高 Information Gain ? 假設(shè)有兩個類 , P 和 N – 假設(shè)集合 S中含有 p個類別 P的記錄 ,n個類別 N的記錄 – 決定任意一個記錄屬于類別 P或者 N所需要的 information. npnnpnnppnppnpI??????? 22 l o gl o g),(2020年 9月 16日星期三 Data Mining: Concepts and Techniques 15 Information Gain 在決策樹中的使用 ? 假設(shè)使用屬性 A將把集合 S分成 V份 {S1, S2 , …, Sv} – 如果 Si 中包含 pi 個類別為 P的記錄 , ni 個類別為 N,的記錄。 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ù)庫中進行分類 ? 分類 —在統(tǒng)計和機器學(xué)習(xí)中有廣泛的研究 ? 伸縮性 : 對幾百萬記錄和幾百個屬性進行訓(xùn)練的時候，能夠達到一定的速度。 屬性值 187。 ? 引進的數(shù)據(jù)結(jié)構(gòu)：類分布表 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). ? 在最低概念層上進行分類 – 例如 , precise temperature, humidity, outlook, etc. – 低的層次，分散的類別，過多的葉子節(jié)點 – 模型解釋的問題 . ? 基于 Cube的多層分類 – 在多個層次上進行相關(guān)性分析 . – 在多個層次上進行 Information Gain的計算 . 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 ? 后驗概率 (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 ? 計算 P(X|Ci),樸素貝葉斯分類假設(shè)類條件獨立 .即給定樣本屬性值相互條件獨立 . P(x1,…,xk|C) = P(x1|C)P(hot|p)2/9P(n) = P(rain|n)P(n) = 2/55/14 = ? 樣本 X 分配給 類 n (don’t play) 2020年 9月 16日星期三 Data Mining: Concepts and Techniques 39 貝葉斯網(wǎng)絡(luò) ? 樸素貝葉斯算法假定類條件獨立 ,當(dāng)假定成立時 ,該算法是最精確的 .然而實踐中 ,變量之間的依賴可能存在 . ? 貝葉斯網(wǎng)絡(luò)解決了這個問題 ,它包括兩部分 ,有向無環(huán)圖和條件概率表 (CPT). 2020年 9月 16日