【正文】 除 ? 項(xiàng) a 和 f 是好的 , … ? 基于投影的挖掘 ? 利用項(xiàng)投影的適當(dāng)次序 ? 許多強(qiáng)硬的約束可以轉(zhuǎn)變成 (反 )單調(diào)的 TID Transaction 10 a, f, d, b, c 20 f, g, d, b, c 30 a, f, d, c, e 40 f, g, h, c, e TDB (min_sup=2) tem Profit a 40 f 30 g 20 d 10 b 0 h 10 c 20 e 30 82 討論 —處理多個(gè)約束 ? 不同的約束需要不同的 , 甚至相互沖突的項(xiàng)序 ? 如果存在序 R, 使得約束 C1 和 C2 關(guān)于 R是可轉(zhuǎn)變的 , 則兩個(gè)可轉(zhuǎn)變的約束之間不存在沖突 ? 如果項(xiàng)序存在沖突 ? 試圖先滿足一個(gè)約束 ? 然后使用另一約束的序 , 在相應(yīng)的投影數(shù)據(jù)庫中挖掘頻繁項(xiàng)集 83 文獻(xiàn) : 頻繁模式挖掘方法 ? R. Agarwal, C. Aggarwal, and V. V. V. Prasad. A tree projection algorithm for generation of frequent itemsets. Journal of Parallel and Distributed Computing, 2022. ? R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases. SIGMOD39。 ? (11) Answer= ?k kL20 Apriori的重要細(xì)節(jié) ? 如何產(chǎn)生候選 ? ? 步驟 1: Lk的自連接 ? 步驟 2: 剪枝 ? 候選產(chǎn)生的例子 ? L3={abc, abd, acd, ace, bcd} ? 自連接 : L3*L3 ? Abcd： 由 abc 和 abd ? Acde： 由 acd 和 ace ? 剪枝 : ? acde 被刪除 , 因?yàn)? ade 不在 L3 ? C4={abcd} 21 如何產(chǎn)生候選 ? ? 假定 Lk1 中的項(xiàng)集已排序 (按字典序排序 ) ? 步驟 1: Lk1自連接 insert into Ck select , , …, k1, from Lk1 p, Lk1 q where =, …, k2=, ? Step 2: 剪枝 forall itemsets c in Ck do forall (k1)subsets s of c do if (s is not in Lk1) then delete c from Ck 22 例子 支持計(jì)數(shù) =2 23 例子 24 由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則 ? 根據(jù)公式產(chǎn)生關(guān)聯(lián)規(guī)則 ? 對(duì)于每個(gè)頻繁項(xiàng)集 l，產(chǎn)生所有的非空子集 ? 對(duì)于 l的每個(gè)非空子集 s，如果 則輸出規(guī)則 ‖s?(ls)‖ 25 頻繁模式挖掘的挑戰(zhàn) ? 挑戰(zhàn) ? 事務(wù)數(shù)據(jù)庫的多遍掃描 ? 數(shù)量巨大的候選 ? 候選支持度計(jì)數(shù)繁重的工作量 ? 改進(jìn) Apriori: 基本思想 ? 減少事務(wù)數(shù)據(jù)庫的掃描遍數(shù) ? 壓縮候選數(shù)量 ? 便于候選計(jì)數(shù) 26 提高 Apriori算法的方法 ? Hashbased itemset counting（散列項(xiàng)集計(jì)數(shù)） ? Transaction reduction（事務(wù)壓縮） ? Partitioning（劃分） ? Sampling（采樣） 27 劃分 : 只掃描數(shù)據(jù)庫兩次 ? 項(xiàng)集在 DB中是頻繁的 , 它必須至少在 DB的一個(gè)劃分中是頻繁的 ? 掃描 1: 劃分?jǐn)?shù)據(jù)庫 , 并找出局部頻繁模式 local frequent itemset ? 掃描 2: 求出全局頻繁模式 ? A. Savasere, E. Omiecinski, and S. Navathe. An efficient algorithm for mining association in large databases. In VLDB’95 DB1 DB2 DBk + = DB + + sup1(i) σDB1 sup2(i) σDB2 supk(i) σDBk sup(i) σDB 28 抽樣 頻繁模式 ? 選取原數(shù)據(jù)庫的一個(gè)樣本 , 使用 Apriori 算法在樣本中挖掘頻繁模式 ? 掃描一次數(shù)據(jù)庫 , 驗(yàn)證在樣本中發(fā)現(xiàn)的頻繁模式 . ? 再次掃描數(shù)據(jù)庫 , 找出遺漏的頻繁模式 ? 犧牲一些精度換取有效性。 ? (8) end。 //新的潛在頻繁項(xiàng)集 ? (4) for all transactions t?D do begin ? (5) Ct=subset(Ck,t)。Lk1??。 17 Apriori: 一種候選產(chǎn)生 測(cè)試方法 ? 頻繁項(xiàng)集的任何子集必須是頻繁的 ? 如果 {beer, diaper, nuts} 是頻繁的 , {beer, diaper}也是 ? 每個(gè)包含 {beer, diaper, nuts}的事務(wù) 也包含 {beer, diaper} ? Apriori 剪枝原則 : ? 如果一個(gè)項(xiàng)集不是 頻繁的 , 將不產(chǎn)生 /測(cè)試它的超集 ! ? 方法 : ? 由長(zhǎng)度為 k的 頻繁 項(xiàng)集產(chǎn)生長(zhǎng)度為 (k+1) 的候選項(xiàng)集 , 并且 ? 根據(jù) DB測(cè)試這些候選 ? 性能研究表明了它的有效性和可伸縮性 18 Apriori 算法 — 一個(gè)例子 數(shù)據(jù)庫 TDB 第 1次掃描 C1 L1 L2 C2 C2 第 2次掃描 C3 L3 第 3次掃描 Tid Items 10 A, C, D 20 B, C, E 30 A, B, C, E 40 B, E Itemset sup {A} 2 {B} 3 {C} 3 {D} 1 {E} 3 Itemset sup {A} 2 {B} 3 {C} 3 {E} 3 Itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E} Itemset sup {A, B} 1 {A, C} 2 {A, E} 1 {B, C} 2 {B, E} 3 {C, E} 2 Itemset sup {A, C} 2 {B, C} 2 {B, E} 3 {C, E} 2 Itemset {B, C, E} Itemset sup {B, C, E} 2 19 Apriori算法 ? (1) L1={頻繁 1項(xiàng)集 }。 ? 潛在頻繁 k項(xiàng)集 的集合 Ck 是指由有可能成為頻繁 k項(xiàng)集的項(xiàng)集組成的集合。 ? 性質(zhì) 2：非頻繁項(xiàng)集的超集一定是非頻繁的 。 ? 構(gòu)成潛在頻繁項(xiàng)集所遵循的原則是“頻繁項(xiàng)集的子集必為頻繁項(xiàng)集”。 15 頻繁項(xiàng)集 ? 為了避免計(jì)算所有項(xiàng)集的支持度（實(shí)際上頻繁項(xiàng)集只占很少一部分）， Apriori算法引入潛在頻繁項(xiàng)集的概念。 ? Apriori算法將發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的過程分為兩個(gè)步驟： ? 通過迭代，檢索出事務(wù)數(shù)據(jù)庫中的所有頻繁項(xiàng)集，即支持度不低于用戶設(shè)定的閾值的項(xiàng)集； ? 利用頻繁項(xiàng)集構(gòu)造出滿足用戶最小信任度的規(guī)則。 ? 由頻繁項(xiàng)集生成滿足最小信任度閾值的規(guī)則。 11 閉頻繁項(xiàng)集 and 極大頻繁項(xiàng)集 ? Exercise. DB = {a1, …, a 100, a1, …, a 50} ? Min_sup = 1. ? What is the set of closed itemset? ? a1, …, a 100: 1 ? a1, …, a 50: 2 ? What is the set of maxpattern? ? a1, …, a 100: 1 ? What is the set of all patterns? ? !! 12 關(guān)聯(lián)規(guī)則基本模型 ? 關(guān)聯(lián)規(guī)則就是支持度和信任度分別滿足用戶給定閾值的規(guī)則。 ? 是一個(gè)條件概率 P (Y | X)。是一個(gè)相對(duì)計(jì)數(shù)。 交易 ID 購買的商品2022 A ,B ,C1000 A ,C4000 A ,D5000 B ,E ,F7 關(guān)聯(lián)規(guī)則基本模型 ? 關(guān)聯(lián)規(guī)則是形如 X?Y的邏輯蘊(yùn)含式，其中 X?I， Y?I，且 X?Y=?。 ? 項(xiàng)集 A在事務(wù)數(shù)據(jù)庫 D中出現(xiàn)的次數(shù)占 D中總事務(wù)的百分比叫做項(xiàng)集的 支持度 。事務(wù) T包含項(xiàng)集 A，當(dāng)且僅當(dāng) A?T。每一個(gè)事務(wù)具有唯一的事務(wù)標(biāo)識(shí) TID。其中，Apriori是關(guān)聯(lián)規(guī)則模型中的經(jīng)典算法。 3 什么是關(guān)聯(lián)規(guī)則挖掘 ? 關(guān)聯(lián)規(guī)則挖掘 ? 首先被 Agrawal, Imielinski and Swami在 1993年的SIGMOD會(huì)議上提出 ? 在事務(wù)、關(guān)系數(shù)據(jù)庫中的項(xiàng)集和對(duì)象中發(fā)現(xiàn)頻繁模式、關(guān)聯(lián)規(guī)則、相關(guān)性或者因果結(jié)構(gòu) ? 頻繁模式 : 數(shù)據(jù)庫中頻繁出現(xiàn)的項(xiàng)集 ? 目的 : 發(fā)現(xiàn)數(shù)據(jù)中的規(guī)律 ? 超市數(shù)據(jù)中的什么產(chǎn)品會(huì)一起購買？ — 啤酒和尿布 ? 在買了一臺(tái) PC之后下一步會(huì)購買 ? ? 哪種 DNA對(duì)這種藥物敏感 ? ? 我們?nèi)绾巫詣?dòng)對(duì) Web文檔進(jìn)行分類 ? 4 頻繁模式挖掘的重要性 ? 許多重要數(shù)據(jù)挖掘任務(wù)的基礎(chǔ) ? 關(guān)聯(lián)、相關(guān)性、因果性 ? 序列模式、空間模式、時(shí)間模式、多維 ? 關(guān)聯(lián)分類、聚類分析 ? 更加廣泛的用處 ? 購物籃分析、交叉銷售、直銷 ? 點(diǎn)擊流分析、 DNA序列分析等等 5 關(guān)聯(lián)規(guī)則基本模型 ? IBM公司 Almaden研究中心的 提出 關(guān)聯(lián)規(guī)則模型 ，并給出求解算法 AIS。 ? 典型的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)問題是對(duì)超市中的貨籃數(shù)據(jù)（ Market Basket）進(jìn)行分析。1 第 5章：挖掘關(guān)聯(lián)規(guī)則 ? 關(guān)聯(lián)規(guī)則挖掘 ? 事務(wù)數(shù)據(jù)庫中 (單維布爾 )關(guān)聯(lián)規(guī)則挖掘的可伸縮算法 ? 挖掘各種關(guān)聯(lián) /相關(guān)規(guī)則 ? 基于限制的關(guān)聯(lián)挖掘 ? 順序模式挖掘 ? 小結(jié) 2 關(guān)聯(lián)規(guī)則 ? 關(guān)聯(lián)規(guī)則反映一個(gè)事物與其他事物之間的相互依存性和關(guān)聯(lián)性。如果兩個(gè)或者多個(gè)事物之間存在一定的關(guān)聯(lián)關(guān)系，那么，其中一個(gè)事物就能夠通過其他事物預(yù)測(cè)到。通過發(fā)現(xiàn)顧客放入貨籃中的不同商品之間的關(guān)系來分析顧客的購買習(xí)慣。隨后又出現(xiàn)了 SETM和 Apriori等算法。 ? 給定一組事務(wù) ? 產(chǎn)生所有的關(guān)聯(lián)規(guī)則 ? 滿足最小支持度和最小可信度 6 關(guān)聯(lián)規(guī)則基本模型 ? 設(shè) I={i1,…, im}為所有項(xiàng)目的集合， D為事務(wù)數(shù)據(jù)庫，事務(wù) T是一個(gè)項(xiàng)目子集（ T?I）。 ? 設(shè) A是一個(gè)由項(xiàng)目構(gòu)成的集合，稱為 項(xiàng)集 。 ? 如果項(xiàng)集 A中包含 k個(gè)項(xiàng)目，則稱其為 k項(xiàng)集 。 ? 如果項(xiàng)集的支持度超過用戶給定的 最小支持度閾值 ，就稱該項(xiàng)集是 頻繁項(xiàng)集 （或 大項(xiàng)集 ）。 ? 如果事務(wù)數(shù)據(jù)庫 D中有 s%的事務(wù)包含 X?Y，則稱關(guān)聯(lián)規(guī)則 X?Y的 支持度為 s% ? 實(shí)際上，支持度是一個(gè)概率值。 ? support (X?Y)=P (X ?Y) ? 項(xiàng)集的 支持度計(jì)數(shù) (頻率 ) support_count ? 包含項(xiàng)集的事務(wù)數(shù) ? 若項(xiàng)集 X的 支持度 記為 support (X)，規(guī)則的 信任度 為 support (X?Y)／ support (X)。 confidence (X?Y)=P (Y | X) ? =support _count(X?Y)／ support_count (X) 8 頻繁模式和關(guān)聯(lián)規(guī)則 ? Itemset X={x1, …, x k} ? 找出滿足最小支持度和置信度的所規(guī)則 X?Y ? 支持度 , s, 事務(wù)包含 X?Y 的概率 ? 置信度 , c, 事務(wù)含 X 也包含 Y 的 條件概率 . 顧客購買 尿布 顧客購買二者 顧客購買 啤酒 Transactionid Items bought 10 A, B, D 20 A, C, D 30 A, D, E 40 B, E, F 50 B, C, D, E, F 令 supmin = 50%, confmin = 50% Freq. Pat.: {A:3, B:3, D:4, E:3, AD:3} 關(guān)聯(lián)規(guī)則 Association rules: A ? D (60%, 100%) D ? A (60%, 75%) 9 挖掘關(guān)聯(lián)規(guī)則 —一個(gè)例子 規(guī)則 A ? C: 支持度 = support({A}?{C}) = 50% 置信度 = support({A}?{C})/support({A}) = %