【正文】 式基 中每個(gè)項(xiàng)的計(jì)數(shù) ? 構(gòu)造模式基中 頻繁項(xiàng)的 FP樹(shù) m條件 模式基 : fca:2, fcab:1 {} f:3 c:3 a:3 m條件 FP樹(shù) m的所有頻繁模式 m, fm, cm, am, fcm, fam, cam, fcam ? ? {} f:4 c:1 b:1 p:1 b:1 c:3 a:3 b:1 m:2 p:2 m:1 頭表 Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 39 遞歸 : 挖掘每個(gè)條件 FP樹(shù) {} f:3 c:3 a:3 m條件 FP樹(shù) ―am‖的條件模式基 : (fc:3) {} f:3 c:3 am條件 FP樹(shù) ―cm‖的條件模式基 : (f:3) {} f:3 cm條件 FP樹(shù) ―cam‖的條件模式基 : (f:3) {} f:3 cam條件 FP樹(shù) 40 特殊情況 : FP樹(shù)中的單個(gè)前綴路徑 ? 假定 (條件 ) FP樹(shù) T 具有單個(gè)共享的前綴路徑 P ? 挖掘可以分解成兩步 ? 將單個(gè)前綴路徑歸約成 一個(gè)結(jié)點(diǎn) ? 連接兩部分的挖掘結(jié)果 ? a2:n2 a3:n3 a1:n1 {} b1:m1 C1:k1 C2:k2 C3:k3 b1:m1 C1:k1 C2:k2 C3:k3 r1 + a2:n2 a3:n3 a1:n1 {} r1 = 41 使用 FP樹(shù)挖掘頻繁模式 ? 基本思想 : 頻繁模式增長(zhǎng) ? 通過(guò)模式和數(shù)據(jù)庫(kù)劃分遞歸地增長(zhǎng)頻繁模式 ? 方法 ? (1)對(duì)于每個(gè)頻繁項(xiàng) , 構(gòu)造它的條件模式基 ? (2)然后構(gòu)造它的條件 FP樹(shù) ? (3)在新構(gòu)造的條件 FP樹(shù)上重復(fù)這一過(guò)程 ?直到結(jié)果條件 FP樹(shù)為空 , 或者它只包含一條路徑 —單個(gè)路徑將產(chǎn)生其子路徑的所有組合 , 每個(gè)子路徑是一個(gè)頻繁模式 42 FP樹(shù)結(jié)構(gòu)的優(yōu)點(diǎn) ? 完全性 ? 保留頻繁模式挖掘的完整信息 ? 不截?cái)嗳魏问聞?wù)的長(zhǎng)模式 ? 壓縮性 ? 壓縮無(wú)關(guān)信息 —非頻繁的項(xiàng)被刪除 ? 項(xiàng)按頻率的降序排列 : 越是頻繁出現(xiàn) , 越可能被共享 ? 絕對(duì)不比原來(lái)的數(shù)據(jù)庫(kù)大 (不計(jì)結(jié)點(diǎn)鏈和計(jì)數(shù)字段 ) 43 FP增長(zhǎng)的規(guī)模化 ? FP樹(shù)不能放在內(nèi)存 , 怎么辦 ?—數(shù)據(jù)庫(kù)投影 ? 數(shù)據(jù)庫(kù)投影 ? 首先將數(shù)據(jù)庫(kù)劃分成一組投影 數(shù)據(jù)庫(kù) ? 然后對(duì)每個(gè)投影數(shù)據(jù)庫(kù)構(gòu)造并挖掘 FP樹(shù) 44 FP增長(zhǎng) vs. Apriori: 隨支持度增長(zhǎng)的可伸縮性 01020304050607080901000 0 . 5 1 1 . 5 2 2 . 5 3S up po r t t hre s ho l d( % )Run time(sec.)D 1 F P g r o w t h r u n t i m eD 1 A p r i o r i r u n t i m eData set T25I20D10K 45 FP增長(zhǎng) vs. 樹(shù) 投影 :隨支持度增長(zhǎng)的可伸縮性 0204060801001201400 1 2Support threshold (%)Runtime (sec.)D2 FPgrowthD2 TreeProjectionData set T25I20D100K 46 為什么 FP增長(zhǎng)是贏家 ? ? 分治 : ? 根據(jù)已經(jīng)得到的頻繁模式劃分任務(wù)和數(shù)據(jù)庫(kù) ? 導(dǎo)致較小的數(shù)據(jù)庫(kù)的聚焦的搜索 ? 其它因素 ? 沒(méi)有候選產(chǎn)生 , 沒(méi)有候選測(cè)試 ? 壓縮數(shù)據(jù)庫(kù) : FP樹(shù)結(jié)構(gòu) ? 不重復(fù)地掃描整個(gè)數(shù)據(jù)庫(kù) ? 基本操作 —局部頻繁項(xiàng)計(jì)數(shù)和建立子 FP樹(shù) , 沒(méi)有模式搜索和匹配 47 有關(guān)的其他方法 ? 挖掘頻繁閉項(xiàng)集合和最大模式 ? CLOSET (DMKD’00) ? 挖掘序列模式 ? FreeSpan (KDD’00), PrefixSpan (ICDE’01) ? 頻繁模式的基于限制的挖掘 ? Convertible constraints (KDD’00, ICDE’01) ? 計(jì)算具有復(fù)雜度量的冰山數(shù)據(jù)方 ? Htree and Hcubing algorithm (SIGMOD’01) 48 最大模式 ? 頻繁模式 {a1, …, a 100} 包含 (1001) + (1002) + … + ( 110000) = 21001 = *1030 頻繁子模式 ! ? 最大模式 : 頻繁模式 , 其真超模式都不是頻繁的 ? BCDE, ACD 是最大模式 ? BCD 不是最大模式 Tid Items 10 A,B,C,D,E 20 B,C,D,E, 30 A,C,D,F Min_sup=2 49 MaxMiner: 挖掘最大模式 ? 掃描 1: 找出頻繁項(xiàng) ? A, B, C, D, E ? 掃描 2: 找出以下項(xiàng)集的支持度 ? AB, AC, AD, AE, ABCDE ? BC, BD, BE, BCDE ? CD, CE, CDE, DE ? 由于 BCDE 是最大模式 , 不必在此后的掃描時(shí)檢查 BCD, BDE, CDE ? R. Bayato. Efficiently mining long patterns from databases. In SIGMOD’98 Tid Items 10 A,B,C,D,E 20 B,C,D,E, 30 A,C,D,F 潛在的最大模式 50 關(guān)聯(lián)規(guī)則的可視化 : Pane Graph 51 第 5章：挖掘關(guān)聯(lián)規(guī)則 ? 關(guān)聯(lián)規(guī)則挖掘 ? 事務(wù)數(shù)據(jù)庫(kù)中 (單維布爾 )關(guān)聯(lián)規(guī)則挖掘的可伸縮算法 ? 挖掘各種關(guān)聯(lián) /相關(guān)規(guī)則 ? 基于限制的關(guān)聯(lián)挖掘 ? 順序模式挖掘 ? 小結(jié) 52 挖掘各種規(guī)則或規(guī)律性 ? 多層關(guān)聯(lián)規(guī)則 , ? 多維關(guān)聯(lián)規(guī)則， ? 量化關(guān)聯(lián)規(guī)則 , ? 相關(guān)性和因果關(guān)系 , 比率規(guī)則 , 序列模式 , 顯露模式 , 時(shí)間關(guān)聯(lián) , 局部周期性 53 多層關(guān)聯(lián)規(guī)則 ? 項(xiàng)常常形成層次結(jié)構(gòu) 概念分層 ? 多個(gè)抽象層次上挖據(jù)得到的關(guān)聯(lián)規(guī)則 多層關(guān)聯(lián)規(guī)則 ? 靈活的支持度設(shè)定 : 較低層中的項(xiàng)一般具有較低的支持度 . 一致的支持度 Milk [support= 10%] 2% Milk [support= 6%] Skim Milk [support= 4%] 層 1 min_sup = 5% 層 2 min_sup = 5% Level 1 min_sup = 5% Level 2 min_sup = 3% 遞減的支持度 54 多層關(guān)聯(lián) : 冗余過(guò)濾 ? 由于項(xiàng)之間的 ―祖先” 聯(lián)系 , 有些規(guī)則可能是多余的 . ? 例 ? milk ? wheat bread [support = 8%, confidence = 70%] ? 2% milk ? wheat bread [support = 2%, confidence = 72%] ? 其中 2% milk 占 milk的 1/4 ? 我們可以說(shuō)第一個(gè)規(guī)則是第二個(gè)規(guī)則的祖先 . ? 一個(gè)規(guī)則是冗余的 , 如果根據(jù)規(guī)則的祖先 , 其支持度和置信度都接近于“期望”值 . 55 多層挖掘 : 逐步深入 ? 一種自頂向下 , 逐步深入的方法 : ? 首先挖掘最高層的頻繁模式 : milk (15%), bread (10%) ? 然后挖掘它們下層 “較弱的” 頻繁模式 : 2% milk (5%), wheat bread (4%) ? 多層之間的不同的最小支持度閾值導(dǎo)致不同的算法 : ? 如果不同層之間采用相同的 min_support 則丟棄 t 如果 t’的任意祖先是非頻繁的 . ? 如果在較低層采用遞減的 min_support 則只考察其祖先為頻繁的項(xiàng)集 . 56 多維關(guān)聯(lián)規(guī)則 ? 單維規(guī)則 :包括單個(gè)謂詞（可以多次出現(xiàn)）或單個(gè)維 buys(X, ―milk‖) ? buys(X, ―bread‖) ? 多維規(guī)則 : 維或謂詞 ? 2 ? 維間關(guān)聯(lián)規(guī)則 (不含重復(fù)謂詞 ) age(X,‖1925‖) ? occupation(X,―student‖) ? buys(X,―coke‖) ? 混合維關(guān)聯(lián)規(guī)則 (含重復(fù)謂詞 ) age(X,‖1925‖) ? buys(X, ―popcorn‖) ? buys(X, ―coke‖) ? 數(shù)據(jù)的屬性可分為兩類(lèi) ? 分類(lèi)屬性 ? 有限個(gè)不同值 , 值之間無(wú)序 ? 量化屬性 ? 數(shù)值的 , 值之間隱含次序 57 挖掘多維關(guān)聯(lián)規(guī)則的技術(shù) ? 搜索頻繁 k謂詞集 :包含 k個(gè)合取謂詞的集合 ? 例 : {age, occupation, buys} 是一個(gè) 3謂詞集 . ? 可以按如何處理 age 對(duì)技術(shù)分類(lèi) . 1. 使用量化屬性的靜態(tài)離散化 ? 使用預(yù)先定義的概念分層 , 對(duì)量化屬性靜態(tài)地離散化 . 2. 量化關(guān)聯(lián)規(guī)則 ? 根據(jù)數(shù)據(jù)的分布 , 將量化屬性離散化到 ―箱” . 3. 基于距離的關(guān)聯(lián)規(guī)則 ? 是一種動(dòng)態(tài)的離散化過(guò)程 , 它考慮數(shù)據(jù)點(diǎn)之間的距離 . 58 量化屬性的靜態(tài)離散化 (ine) (age) () (buys) (age, ine) (age,buys) (ine,buys) (age,ine,buys) ? 使用概念分層 , 在挖掘之前離散化 . ? 數(shù)值用區(qū)間值替換 . ? 在關(guān)系數(shù)據(jù)庫(kù)中 , 找出所有的頻繁 k謂詞集需要 k 或 k+1 次表掃描 . ? 數(shù)據(jù)立方體非常適合挖掘 . ? n維方體 對(duì)應(yīng)于謂詞集合的方體 . ? 從數(shù)據(jù)立方體挖掘可以快得多 . 59 量化關(guān)聯(lián)規(guī)則 ? 數(shù)值屬性 動(dòng)態(tài) 地離散化 ? 使挖出的規(guī)則的置信度或緊湊性最大化 . ? 2維量化關(guān)聯(lián)規(guī)則 : Aquan1 ? Aquan2 ? Acat（分類(lèi)屬性） ? ARCS方法：使用 2D柵格 , ? 1)對(duì)屬性進(jìn)行（等寬）分箱 ? 2)找頻繁謂詞集 ? 3)規(guī)則聚類(lèi)：對(duì)“相鄰的” 關(guān)聯(lián)規(guī)則 聚類(lèi) 形成一般關(guān)聯(lián)規(guī)則 . ? 例 : age(X,‖3435‖) ? ine(X,‖31K 50K‖) ? buys(X,‖high resolution TV‖) 60 挖掘基于距離的關(guān)聯(lián)規(guī)則 ? 分箱方法不能緊扣區(qū)間數(shù)據(jù)的語(yǔ)義 ? 基于距離的劃分 , 更有意義的離散化考慮 : ? 區(qū)間內(nèi)點(diǎn)的密度 /數(shù)量 ? 區(qū)間內(nèi)點(diǎn)的“緊密性” P r i c e ( $ )E q u i w i d t h( w i d t h $ 1 0 )E q u i d e p t h( d e p t h 2 )Dis t a n c e b a s e d7 [ 0 , 1 0 ] [ 7 , 2 0 ] [ 7 , 7 ]20 [ 1 1 , 2 0 ] [ 2 2 , 5 0 ] [ 2 0 , 2 2 ]22 [ 2 1 , 3 0 ] [ 5 1 , 5 3 ] [ 5 0 , 5 3 ]50 [ 3 1 , 4 0 ]51 [ 4 1 , 5 0 ]53 [ 5 1 , 6 0 ]61 具有靈活的支持度限制的 多層 ML/MD多維關(guān)聯(lián)規(guī)則 ? 為什么 ? ? 現(xiàn)實(shí)中項(xiàng)的出現(xiàn)頻率差異很大 ? 購(gòu)物中的鉆石 , 表 , 筆 ? 一致的支持度可能不是一種好的模型 ? 靈活的模型 ? 通常 , 層越低 , 維的組合越多 , 長(zhǎng)模式越長(zhǎng) , 支持度越小 ? 一般規(guī)則應(yīng)當(dāng)是特指的 , 易于理解的 ? 特殊的項(xiàng)或特殊的項(xiàng)群可能被個(gè)別地指定 , 并具有較高的優(yōu)先權(quán) 62 興趣度度量 : 相關(guān)性 (Lift) ? play basketball ? eat cereal [40%, %] 是誤導(dǎo) ? 吃谷類(lèi)食品的學(xué)生所占的百分比為 75%, 比 %還高 . ? play basketball ? not eat cereal [20%, %] 更準(zhǔn)確 , 其支持度和置信度都較低 ? 依賴(lài) /相關(guān)事件的度量 : Basketball Not basketball Sum (row) Cereal谷類(lèi) 2022 1750 3750 Not cer