【正文】 eal 1000 250 1250 Sum(col.) 3000 2022 5000 *5000/3000 5000/2022),( ??CBl i f t)()()(BPAPBAPlif t ??*5000/3000 5000/1000),( ??? CBl i f t)s up(_m a x_)s up(_Xi t e mXc onfal l ?63 Which Measures Should Be Used? ? 提升度和 ?2 不是好的相關度量，對于大的交易數據庫 ? allconf or coherence could be good measures (OmiecinskiTKDE’03) ? Over 20 interestingness measures have been proposed (see Tan, Kumar, Sritastava KDD’02) ? Which are good ones? 64 第 5章：挖掘關聯(lián)規(guī)則 ? 關聯(lián)規(guī)則挖掘 ? 事務數據庫中 (單維布爾 )關聯(lián)規(guī)則挖掘的可伸縮算法 ? 挖掘各種關聯(lián) /相關規(guī)則 ? 基于限制的關聯(lián)挖掘 ? 順序模式挖掘 ? 頻繁模式挖掘的應用 /擴展 ? 小結 65 基于約束的數據挖掘 ? 自動地 找出數據庫中的 所有 模式 ? — 不現實 ! ? 模式可能太多 , 并不聚焦 ! ? 數據挖掘應當是一個 交互的 過程 ? 用戶使用 數據挖掘查詢語言 (或圖形用戶界面 ) 指導需要挖掘什么 ? 基于約束的挖掘 ? 用戶靈活性 : 提供挖掘的 約束 ? 系統(tǒng)優(yōu)化 : 考察限制 , 尋找有效的挖掘 —基于約束的挖掘 66 數據挖掘的約束 ? 知識類型約束 : ? 分類 , 關聯(lián) , 等 . ? 數據約束 （指定任務相關的數據集） — 使用類 SQL查詢 ? 找出 Vancouver 2022年 12月份一起銷售的產品對 ? 維 /層約束 指定數據屬性 /概念分層結構的層次 ? 關于 region, price, brand, customer category ? 興趣度約束 ? 強規(guī)則 : min_support ? 3%, min_confidence ? 60% ? 規(guī)則 (或模式 ) 約束 指定規(guī)則形式 ? 小額銷售 (價格 $10) 觸發(fā)大額銷售 (sum $200) 67 元規(guī)則制導挖掘 MetaRule Guided Mining ? 元規(guī)則是帶有部分約束謂詞和常量的規(guī)則 P1(X, Y) ^ P2(X, W) = buys(X, ―iPad‖) ? 一個導致的規(guī)則 age(X, ―1525‖) ^ profession(X, ―student‖) = buys(X, ―iPad‖) ? 通常情況 , 元規(guī)則如下形式的規(guī)則模板 P1 ^ P2 ^ … ^ P l = Q1 ^ Q2 ^ … ^ Q r ? 挖掘過程 ? 找出所有的頻繁 (l+r) 謂詞集 (基于最小支持度閾值 ) ?比須保留 l子集的支持度 /計數（計算規(guī)則的置信度） ? （挖掘過程中）盡可能推進約束 (見約束推進技術 ) ? 盡可能地應用置信度 , 相關和其他度量 68 規(guī)則約束 剪枝搜索空間 ? 規(guī)則約束的分類 ? 反單調性 Antimonotonic ? 單調性 Monotonic ? 簡潔性 Succinct: ? 可轉變的 Convertible: ? 不可轉變的 69 規(guī)則約束 反單調性 ? 反單調性 ? 當項集 S 違反規(guī)則約束時 , 它的任何超集合也違反約束 ? sum() ? v 是 反單調的 ? sum() ? v 不是 反單調的 ? 例 . C: range() ? 15是 反單調的 ? 項集 ab 違反約束 C ? ab的每個超集也違反約束 C TID Transaction 10 a, b, c, d, f 20 b, c, d, f, g, h 30 a, c, d, e, f 40 c, e, f, g TDB (min_sup=2) Item Profit a 40 b 0 c 20 d 10 e 30 f 30 g 20 h 10 70 規(guī)則約束 單調性 ? 單調性 ? 當項集 S 滿足 約束 時 , 它的任何超集合也滿足約束 ? sum() ? v 是 單調的 ? min() ? v 是 單調的 ? 例 . C: range() ? 15 ? 項集 ab 滿足 C ? ab的每個超集合也滿足 C TID Transaction 10 a, b, c, d, f 20 b, c, d, f, g, h 30 a, c, d, e, f 40 c, e, f, g TDB (min_sup=2) Item Profit a 40 b 0 c 20 d 10 e 30 f 30 g 20 h 10 71 簡潔性 ? 簡潔性 : ? 給定滿足約束 C 的項的集合 A1, 則滿足 C 的任意集合 S 都基于 A1 , 即 , S 包含一個屬于 A1 的子集 ? 思想 : 不查看事務數據庫 , 項集 S 是否滿足約束 C可以根據選取的項確定 ? min() ? v 是簡潔的 ? sum() ? v 不是簡潔的 ? 優(yōu)化 : 如果 C 是簡潔的 , C 是預計數可推進的 (precounting pushable) 72 Apriori 算法 — 一個例子 TID Items100 1 3 4200 2 3 5300 1 2 3 5400 2 5Database D itemset sup.{1} 2{2} 3{3} 3{4} 1{5} 3itemset sup.{1} 2{2} 3{3} 3{5} 3Scan D C1 L1 itemset{1 2}{1 3}{1 5}{2 3}{2 5}{3 5}itemset sup{1 2} 1{1 3} 2{1 5} 1{2 3} 2{2 5} 3{3 5} 2itemset sup{1 3} 2{2 3} 2{2 5} 3{3 5} 2L2 C2 C2 Scan D C3 L3 itemset{2 3 5} Scan D itemset sup{2 3 5} 273 樸素算法 : Apriori + 約束 TID Items100 1 3 4200 2 3 5300 1 2 3 5400 2 5Database D itemset sup.{1} 2{2} 3{3} 3{4} 1{5} 3itemset sup.{1} 2{2} 3{3} 3{5} 3Scan D C1 L1 itemset{1 2}{1 3}{1 5}{2 3}{2 5}{3 5}itemset sup{1 2} 1{1 3} 2{1 5} 1{2 3} 2{2 5} 3{3 5} 2itemset sup{1 3} 2{2 3} 2{2 5} 3{3 5} 2L2 C2 C2 Scan D C3 L3 itemset{2 3 5} Scan D itemset sup{2 3 5} 2約束 : Sum{ 5} 74 受約束的 Apriori 算法 : 推進反單調約束 TID Items100 1 3 4200 2 3 5300 1 2 3 5400 2 5Database D itemset sup.{1} 2{2} 3{3} 3{4} 1{5} 3itemset sup.{1} 2{2} 3{3} 3{5} 3Scan D C1 L1 itemset{1 2}{1 3}{1 5}{2 3}{2 5}{3 5}itemset sup{1 2} 1{1 3} 2{1 5} 1{2 3} 2{2 5} 3{3 5} 2itemset sup{1 3} 2{2 3} 2{2 5} 3{3 5} 2L2 C2 C2 Scan D C3 L3 itemset{2 3 5} Scan D itemset sup{2 3 5} 2約束 : Sum{ 5} 75 轉換 “強硬的” 約束 ? 通過將項適當地排序 , 將強硬的約束轉換成反單調的或單調的 ? 例 C: avg() ? 25 ? 將項按 profit值的遞減序排序 ? a, f, g, d, b, h, c, e ? 如果項集 afb 違反 C ? afbh, afb*也違反 C ?約束 C成為 反單調的 ! TID Transaction 10 a, b, c, d, f 20 b, c, d, f, g, h 30 a, c, d, e, f 40 c, e, f, g TDB (min_sup=2) Item Profit a 40 b 0 c 20 d 10 e 30 f 30 g 20 h 10 76 可轉變的約束 ? 設 R 項集的項以特定次序安排， ? 可轉變反單調 ? 如果項集 S 違反約束 C, 每個關于 R以 S 為前綴的項集也違反約束 C ? 例 . avg(S) ? v ，如果 項值遞減序排列 ? 可轉變單調 ? 如果項集 S 滿足約束 C, 每個關于 R以 S 為前綴的項集也滿足約束 C. ? 例 . avg(S) ? v ，如果 項值遞增序排列 77 強可轉變約束 ? avg(X) ? 25 關于項值的遞減序 R: a, f, g, d, b, h, c, e是可轉變反單調的 ? 如果項集 af 違反約束 C, 每個以 af 為前綴的項集也違反 C, 如 afd ? avg(X) ? 25關于項值的遞增序 R1: e, c, h, b, d, g, f, a是可轉變單調的 ? 如果項集 d 滿足約束 C, df 和 dfa 也滿足 , 它們具有前綴 d ? 這樣 , avg(X) ? 25 是 強可轉變的 Item Profit a 40 b 0 c 20 d 10 e 30 f 30 g 20 h 10 78 約束的性質匯總 約束 反單調 單調 簡潔 v ? S no yes yes S ? V no yes yes S ? V yes no yes min(S) ? v no yes yes min(S) ? v yes no yes max(S) ? v yes no yes max(S) ? v no yes yes count(S) ? v yes no weakly count(S) ? v no yes weakly sum(S) ? v ( a ? S, a ? 0 ) yes no no sum(S) ? v ( a ? S, a ? 0 ) no yes no range(S) ? v yes no no range(S) ? v no yes no avg(S) ? v, ? ? { ?, ?, ? } convertible convertible no support(S) ? ? yes no no support(S) ? ? no yes no 79 約束的分類 可轉變反單調 可轉變單調 強可轉變 不可轉變的 簡潔 反單調 單調 80 Apriori 能夠處理可轉變的約束嗎 ? ? 可轉變的 , 但既不是單調 , 反單調 , 也不是簡潔的約束不能推進到 Apriori 挖掘算法的挖掘過程中 ? 在逐級的框架下 , 不能做直接基于該約束的剪枝 ? 項集 df 違反 約束 C: avg(X)=25 ? 由于 adf 滿足 C, Apriori 需要 df 來組裝 adf, 因此不能將 df 剪去 ? 但是 , 在模式增長框架下該約束可以推進到挖掘過程中 ! Item Value a 40 b 0 c 20 d 10 e 30 f 30 g 20 h 10 81 具有可轉變約束的挖掘 ? C: avg(X)=25, min_sup=2 ? 以值的遞減序 R: a, f, g, d, b, h, c, e 列出事務中的每一個項 ? 關于 R, C是可轉變反單調的 ? 掃描 TDB 一次 ? 刪除非頻繁項 ? 項 h 被刪