【文章內(nèi)容簡(jiǎn)介】 可視化 : 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) : 冗余過濾 ? 由于項(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ù)的屬性可分為兩類 ? 分類屬性 ? 有限個(gè)不同值 , 值之間無(wú)序 ? 量化屬性 ? 數(shù)值的 , 值之間隱含次序 57 挖掘多維關(guān)聯(lián)規(guī)則的技術(shù) ? 搜索頻繁 k謂詞集 :包含 k個(gè)合取謂詞的集合 ? 例 : {age, occupation, buys} 是一個(gè) 3謂詞集 . ? 可以按如何處理 age 對(duì)技術(shù)分類 . 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)的離散化過程 , 它考慮數(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（分類屬性） ? ARCS方法：使用 2D柵格 , ? 1)對(duì)屬性進(jìn)行（等寬）分箱 ? 2)找頻繁謂詞集 ? 3)規(guī)則聚類：對(duì)“相鄰的” 關(guān)聯(lián)規(guī)則 聚類 形成一般關(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) ? 吃谷類食品的學(xué)生所占的百分比為 75%, 比 %還高 . ? play basketball ? not eat cereal [20%, %] 更準(zhǔn)確 , 其支持度和置信度都較低 ? 依賴 /相關(guān)事件的度量 : Basketball Not basketball Sum (row) Cereal谷類 2022 1750 3750 Not cereal 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 不是好的相關(guān)度量，對(duì)于大的交易數(shù)據(jù)庫(kù) ? allconf or coherence could be good measures (Omiecinski@TKDE’03) ? Over 20 interestingness measures have been proposed (see Tan, Kumar, Sritastava @KDD’02) ? Which are good ones? 64 第 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)挖掘 ? 順序模式挖掘 ? 頻繁模式挖掘的應(yīng)用 /擴(kuò)展 ? 小結(jié) 65 基于約束的數(shù)據(jù)挖掘 ? 自動(dòng)地 找出數(shù)據(jù)庫(kù)中的 所有 模式 ? — 不現(xiàn)實(shí) ! ? 模式可能太多 , 并不聚焦 ! ? 數(shù)據(jù)挖掘應(yīng)當(dāng)是一個(gè) 交互的 過程 ? 用戶使用 數(shù)據(jù)挖掘查詢語(yǔ)言 (或圖形用戶界面 ) 指導(dǎo)需要挖掘什么 ? 基于約束的挖掘 ? 用戶靈活性 : 提供挖掘的 約束 ? 系統(tǒng)優(yōu)化 : 考察限制 , 尋找有效的挖掘 —基于約束的挖掘 66 數(shù)據(jù)挖掘的約束 ? 知識(shí)類型約束 : ? 分類 , 關(guān)聯(lián) , 等 . ? 數(shù)據(jù)約束 （指定任務(wù)相關(guān)的數(shù)據(jù)集） — 使用類 SQL查詢 ? 找出 Vancouver 2022年 12月份一起銷售的產(chǎn)品對(duì) ? 維 /層約束 指定數(shù)據(jù)屬性 /概念分層結(jié)構(gòu)的層次 ? 關(guān)于 region, price, brand, customer category ? 興趣度約束 ? 強(qiáng)規(guī)則 : min_support ? 3%, min_confidence ? 60% ? 規(guī)則 (或模式 ) 約束 指定規(guī)則形式 ? 小額銷售 (價(jià)格 $10) 觸發(fā)大額銷售 (sum $200) 67 元規(guī)則制導(dǎo)挖掘 MetaRule Guided Mining ? 元規(guī)則是帶有部分約束謂詞和常量的規(guī)則 P1(X, Y) ^ P2(X, W) = buys(X, ―iPad‖) ? 一個(gè)導(dǎo)致的規(guī)則 age(X, ―1525‖) ^ profession(X, ―student‖) = buys(X, ―iPad‖) ? 通常情況 , 元規(guī)則如下形式的規(guī)則模板 P1 ^ P2 ^ … ^ P l = Q1 ^ Q2 ^ … ^ Q r ? 挖掘過程 ? 找出所有的頻繁 (l+r) 謂詞集 (基于最小支持度閾值 ) ?比須保留 l子集的支持度 /計(jì)數(shù)（計(jì)算規(guī)則的置信度） ? （挖掘過程中）盡可能推進(jìn)約束 (見約束推進(jìn)技術(shù) ) ? 盡可能地應(yīng)用置信度 , 相關(guān)和其他度量 68 規(guī)則約束 剪枝搜索空間 ? 規(guī)則約束的分類 ? 反單調(diào)性 Antimonotonic ? 單調(diào)性 Monotonic ? 簡(jiǎn)潔性 Succinct: ? 可轉(zhuǎn)變的 Convertible: ? 不可轉(zhuǎn)變的 69 規(guī)則約束 反單調(diào)性 ? 反單調(diào)性 ? 當(dāng)項(xiàng)集 S 違反規(guī)則約束時(shí) , 它的任何超集合也違反約束 ? sum() ? v 是 反單調(diào)的 ? sum() ? v 不是 反單調(diào)的 ? 例 . C: range() ? 15是 反單調(diào)的 ? 項(xiàng)集 ab 違反約束 C ? ab的每個(gè)超集也違反約束 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ī)則約束 單調(diào)性 ? 單調(diào)性 ? 當(dāng)項(xiàng)集 S 滿足 約束 時(shí) , 它的任何超集合也滿足約束 ? sum() ? v 是 單調(diào)的 ? min() ? v 是 單調(diào)的 ? 例 . C: range() ? 15 ? 項(xiàng)集 ab 滿足 C ? ab的每個(gè)超集合也滿足 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 簡(jiǎn)潔性 ? 簡(jiǎn)潔性 : ? 給定滿足約束 C 的項(xiàng)的集合 A1, 則滿足 C 的任意集合 S 都基于 A1 , 即 , S 包含一個(gè)屬于 A1 的子集 ? 思想 : 不查看事務(wù)數(shù)據(jù)庫(kù) , 項(xiàng)集 S 是否滿足約束 C可以根據(jù)選取的項(xiàng)確定 ? min() ? v 是簡(jiǎn)潔的 ? sum() ? v 不是簡(jiǎn)潔的 ? 優(yōu)化 : 如果 C 是簡(jiǎn)潔的 , C 是預(yù)計(jì)數(shù)可推進(jìn)的 (precounting pushable) 72 Apriori 算法 — 一個(gè)例子 TID Items100 1 3 4200 2 3 5300 1 2 3 5400 2 5Database D items