【正文】 特征化和比較 ? 什么是概念描述 ? ? 數(shù)據(jù)概化和基于匯總的特征化 ? 分析特征化 : 分析屬性之間的關(guān)聯(lián)性 ? 挖掘類比較 :獲取不同類之間的不同處 ? 在大型數(shù)據(jù)庫中挖掘描述統(tǒng)計度量 ? 討論 ? 總結(jié) 2020/10/5 18 屬性相關(guān)性分析 ? why? ? 哪些維需要包括 ? ? 需要概化到什么層次 ? ? 減少屬性；從而容易理解模型結(jié)果 ? What? ? 使用統(tǒng)計的方法進(jìn)行數(shù)據(jù)預(yù)處理 ? 過濾掉一些不相關(guān)或者相關(guān)性比較弱的字段 ? 保留并對相關(guān)屬性進(jìn)行排序 ? 相關(guān)性和維度、層次有關(guān) ? 分析特征化，分析比較 2020/10/5 19 屬性相關(guān)性分析 ? 步驟： ? 數(shù)據(jù)收集 ? 使用保守的 AOI進(jìn)行預(yù)相關(guān)分析 ? 相關(guān)性分析，刪除不相關(guān)和弱相關(guān)屬性 ? 使用 AOI產(chǎn)生概念描述 2020/10/5 20 相關(guān)性度量標(biāo)準(zhǔn) ? 相關(guān)性度量標(biāo)準(zhǔn)決定了如何對屬性進(jìn)行判斷的標(biāo)準(zhǔn) ? 方法 ? 信息增益 information gain (ID3) ? 增益比 gain ratio () ? Gini索引 gini index ? 不確定性 ? 相關(guān)系數(shù) 2020/10/5 21 Entropy 和 Information Gain ? 集合 S中類別 Ci的記錄個數(shù)是 si 個 i = {1, …, m} ? 期望信息 ? 屬性 A的熵是 ? 信息增益 ssss,...,s,ss imiim2121 lo g)I( ????)s,...,s(Is s...sE ( A ) mjjvjmjj 111?????E ( A ))s, . . . ,s,I(sG ai n( A ) m ?? 212020/10/5 22 一個例子 (131頁例 ) ? 任務(wù) ? 使用分析特征化來了解研究生的一般特征 ? 屬性名稱 gender, major, birth_place, birth_date, phone, and gpa ? Gen(ai) = concept hierarchies on ai ? Ui = attribute analytical thresholds for ai ? Ti = attribute generalization thresholds for ai ? R = attribute relevance threshold 2020/10/5 23 例子：分析特征化（續(xù)） ? 1. 數(shù)據(jù)收集 ? target class: graduate student ? contrasting class: undergraduate student ? Ui分析概化 ? 屬性刪除 ? remove name and phone ? 屬性概化 ? generalize major, birth_place, birth_date and gpa ? accumulate counts ? 候選關(guān)系 : gender, major, birth_country, age_range and gpa 2020/10/5 24 例子：分析特征化 (2) g ende r m a jo r bi rth _ c o untr y a g e_ r a n g e g pa co unt M Scien ce Can ad a 2 1 25 Ver y _ g o o d 16 F Scien ce Fo reign 2 6 30 Excellen t 22 M Eng in eering Fo reign 2 6 30 Excellen t 18 F Scien ce Fo reign 2 6 30 Excellen t 25 M Scien ce Can ad a 2 1 25 Excellen t 21 F Eng in eering Ca n ad a 2 1 25 Excellen t 18 Candidate relation for Target class: Graduate students (?=120) g ende r m a jo r bi rth _ c o untr y a g e_ r a n g e g pa co unt M Scien ce Fo reign = 20 Ver y _ g o o d 18 F Bu sin ess Can ad a = 20 Fair 20 M Bu sin ess Can ad a = 20 Fair 22 F Scien ce Can ad a 2 1 25 Fair 24 M Eng in eering Fo reign 2 1 25 Ver y _ g o o d 22 F Eng in eering Can ad a = 20 Excellen t 2 4 Candidate relation for Contrasting class: Undergraduate students (?=130) 2020/10/5 25 例子：分析特征化 (3) ? 3. 相關(guān)性分析 ? 計算期望信息 ? 計算每個屬性的熵 9 9 8 80250130250130250120250120200120 2221 .l o gl o g),I()s,I ( s ?????F o r m a jo r= ” S ci e n ce” : S11=8 4 S21=4 2 I ( s11,s21) =0 . 9 1 8 3F o r m a jo r= ” En g in eer in g ” : S12=3 6 S22=4 6 I ( s12,s22) =0 . 9 8 9 2F o r m a jo r= ” Bus in ess ” : S13=0 S23=4 2 I ( s13,s23) =0Number of grad students in “Science” Number of undergrad students in “Science” 2020/10/5 26 例子：分析特征化 (4) ? 得出每個屬性的熵 ? 計算每個屬性的 Information Gain ? Information gain for all attributes 7 8 7 302504225082250126 231322122111 .)s,s(I)s,s(I)s,s(IE ( ma j o r ) ????2115021 .E ( m ajor ))s,I ( s)G ain( m ajor ???G a i n ( g e n d e r ) = 0 . 0 0 0 3G a i n ( b i r t h _ c o u n t r y ) = 0 . 0 4 0 7G a i n ( m a j o r ) = 0 . 2 1 1 5G a i n ( g p a ) = 0 . 4 4 9 0G a i n ( a g e _ r a n g e ) = 0 . 5 9 7 12020/10/5 27 例子：分析特征化 (5) ? 4. Initial working relation (W0) derivation ? R = ? 刪除不相關(guān)或者弱相關(guān)的屬性 = drop gender, birth_country ? 刪除比較類的關(guān)系 ? 5. 在 W0進(jìn)行 AOI分析 m a jor a g e_ ra ng e g pa co unt Scien ce 2 1 25 Ver y _ g o o d 16 Scien ce 2 6 30 Excellen t 47 Scien ce 2 1 25 Excellen t 21 Eng in eering 2 1 25 Excellen t 18 Eng in eering 2 6 30 Excellen t 18 Initial target class working relation W0: Graduate students 2020/10/5 28 特征化和比較 ? 什么是概念描述 ? ? 數(shù)據(jù)概化和基于匯總的特征化 ? 分析特征化 : 分析屬性之間的關(guān)聯(lián)性 ? 挖掘類比較 :獲取不同類之間的不同處 ? 在大型數(shù)據(jù)庫中挖掘描述統(tǒng)計度量 ? 討論 ? 總結(jié) 2020/10/5 29 挖掘類比較 ? 比較 :比較兩個或者更多類 . ? 方法 : ? 將相關(guān)的數(shù)據(jù)分成目標(biāo)類和比較類。 ? 概化方法的不同 ? 機(jī)器學(xué)習(xí)：按照元組概化 ? 概念描述：按照屬性概化 2020/10/5 55 特征化和比較 ? 什么是概念描述 ? ? 數(shù)據(jù)概化和基于匯總的特征化 ? 分析特征化 : 分析屬性之間的關(guān)聯(lián)性 ? 挖掘類比較 :獲取不同類之間的不同處 ? 在大型數(shù)據(jù)庫中挖掘描述統(tǒng)計度量 ? 討論 ? 總結(jié) 2020/10/5 56 數(shù)據(jù)挖掘：概念和技術(shù) 56第 5章：挖掘頻繁模式、關(guān)聯(lián)和相關(guān) ? 基本概念和路線圖 ? 有效的和可伸縮的頻繁項集挖掘方法 ? 挖掘各種類型的關(guān)聯(lián)規(guī)則 ? 由關(guān)聯(lián)挖掘到相關(guān)性分析 ? 基于約束的關(guān)聯(lián)挖掘 ? 小結(jié) 2020/10/5 57 數(shù)據(jù)挖掘：概念和技術(shù) 57什么是關(guān)聯(lián)挖掘 ? ? 關(guān)聯(lián)規(guī)則挖掘： ? 在交易數(shù)據(jù)、關(guān)系數(shù)據(jù)或其他信息載體中，查找存在于項目集合或?qū)ο蠹现g的頻繁模式、關(guān)聯(lián)、相關(guān)性、或因果結(jié)構(gòu)。 for each transaction t in database do increment the count of all candidates in Ck that are contained in t Lk = candidates in Ck with min_support end return ?k Lk。 2020/10/5 70 數(shù)據(jù)挖掘：概念和技術(shù) 70Apriori 夠快了嗎 ? — 性能瓶頸 ? Apriori算法的核心 : ? 用頻繁的 (k – 1)項集生成 候選 的頻繁 k項集 ? 用數(shù)據(jù)庫掃描和模式匹配計算候選集的支持度 ? Apriori 的瓶頸 : 候選集生成 ? 巨大的候選集 : ? 104 個頻繁 1項集要生成 107 個候選 2項集 ? 要找尺寸為 100的頻繁模式，如 {a1, a2, …, a 100}, 你必須先產(chǎn)生 2100 ? 1030 個候選集 ? 多次掃描數(shù)據(jù)庫 ： ? 如果最長的模式是 n的話，則需要 (n +1 ) 次數(shù)據(jù)庫掃描 2020/10/5 71 數(shù)據(jù)挖掘：概念和技術(shù) 71挖掘頻繁集 不用生成候選集 ? 頻繁模式增長 (FP增長 )用 FrequentPattern tree (FPtree) 結(jié)構(gòu)壓縮數(shù)據(jù)庫 , ? 高度濃縮，同時對頻繁集的挖掘又完備的 ? 避免代價較高的數(shù)據(jù)庫掃描 開發(fā)一種高效的基于 FPtree的頻繁集挖掘算法 ? 采用分而治之的方法學(xué)：分解數(shù)據(jù)挖掘任務(wù)為小任務(wù) ? 避免生成關(guān)聯(lián)規(guī)則 : 分別挖掘條件數(shù)據(jù)庫 2020/10/5 72 數(shù)據(jù)挖掘：概念和技術(shù) 72用 FPtree挖掘頻繁集 ? 基本思想 (分而