挖掘關聯(lián)規(guī)則

1、1挖掘關聯(lián)規(guī)則挖掘關聯(lián)規(guī)則n關聯(lián)規(guī)則挖掘關聯(lián)規(guī)則挖掘n事務數(shù)據(jù)庫中關聯(lián)規(guī)則挖掘算法事務數(shù)據(jù)庫中關聯(lián)規(guī)則挖掘算法n基于限制的關聯(lián)挖掘基于限制的關聯(lián)挖掘2關聯(lián)規(guī)則關聯(lián)規(guī)則n關聯(lián)規(guī)則反映一個事物與其他事物之間的關聯(lián)規(guī)則反映一個事物與其他事物之間的相互依相互依存性和關聯(lián)性存性和關聯(lián)性。如果兩個或者多個事物之間存在。如果兩個或者多個事物之間存在一定的關聯(lián)關系，那么，其中一個事物就能夠通一定的關聯(lián)關系，那么，其中一個事物就能夠通過其他事物過其他事物預測預測到。到。 n典型的關聯(lián)規(guī)則發(fā)現(xiàn)問題是對超市中的貨籃數(shù)據(jù)典型的關聯(lián)規(guī)則發(fā)現(xiàn)問題是對超市中的貨籃數(shù)據(jù)進行分析。通過發(fā)現(xiàn)顧客放入貨籃中的不同商品進行分析。通過

2、發(fā)現(xiàn)顧客放入貨籃中的不同商品之間的關系來分析顧客的購買習慣。之間的關系來分析顧客的購買習慣。 3什么是關聯(lián)規(guī)則挖掘什么是關聯(lián)規(guī)則挖掘n關聯(lián)規(guī)則挖掘關聯(lián)規(guī)則挖掘(1993)n在事務、關系數(shù)據(jù)庫中的項集和對象中發(fā)現(xiàn)在事務、關系數(shù)據(jù)庫中的項集和對象中發(fā)現(xiàn)頻繁模式頻繁模式、關聯(lián)規(guī)則關聯(lián)規(guī)則、相關性或者因果結構相關性或者因果結構n頻繁模式頻繁模式: 數(shù)據(jù)庫中頻繁出現(xiàn)的數(shù)據(jù)庫中頻繁出現(xiàn)的項集項集 n目的目的: 發(fā)現(xiàn)數(shù)據(jù)中的規(guī)律發(fā)現(xiàn)數(shù)據(jù)中的規(guī)律n超市數(shù)據(jù)中的什么產(chǎn)品會一起購買？超市數(shù)據(jù)中的什么產(chǎn)品會一起購買？ 啤酒和尿布啤酒和尿布n在買了一臺在買了一臺PC之后下一步會購買之后下一步會購買?n我們如何自動對我

3、們如何自動對Web文檔進行分類文檔進行分類?n交叉銷售、直銷等交叉銷售、直銷等4關聯(lián)規(guī)則基本模型關聯(lián)規(guī)則基本模型 nAprioriApriori是關聯(lián)規(guī)則模型中的經(jīng)典算法。是關聯(lián)規(guī)則模型中的經(jīng)典算法。n給定一組事務給定一組事務n產(chǎn)生所有的關聯(lián)規(guī)則產(chǎn)生所有的關聯(lián)規(guī)則n滿足最小支持度和最小可信度滿足最小支持度和最小可信度5關聯(lián)規(guī)則基本模型關聯(lián)規(guī)則基本模型n設設I=i1, im為所有項目的集合，為所有項目的集合，D為事務數(shù)據(jù)庫，事務為事務數(shù)據(jù)庫，事務T是是一個項目子集（一個項目子集（T I）。每一個事務具有唯一的事務標識）。每一個事務具有唯一的事務標識TID。n設設A是一個由項目構成的集合，稱為是一

4、個由項目構成的集合，稱為項集項集。事務。事務T包含項集包含項集A，當且僅當當且僅當A T。n如果項集如果項集A中包含中包含k個項目，則稱其為個項目，則稱其為k項集項集。n項集項集A在事務數(shù)據(jù)庫在事務數(shù)據(jù)庫D中出現(xiàn)的次數(shù)占中出現(xiàn)的次數(shù)占D中總事務的百分比叫中總事務的百分比叫做項集的做項集的支持度支持度。n如果項集的支持度超過用戶給定的如果項集的支持度超過用戶給定的最小支持度最小支持度(閾值閾值)，就稱，就稱該項集是該項集是頻繁項集頻繁項集。 交易ID購買的商品2000A,B,C1000A,C4000A,D5000B,E,F6關聯(lián)規(guī)則基本模型關聯(lián)規(guī)則基本模型n關聯(lián)規(guī)則是形如關聯(lián)規(guī)則是形如XY的邏輯

5、蘊含式，其中的邏輯蘊含式，其中X I，Y I，且且X Y=。n如果事務數(shù)據(jù)庫如果事務數(shù)據(jù)庫D中有中有s%的事務包含的事務包含X Y，則稱關聯(lián)，則稱關聯(lián)規(guī)則規(guī)則XY的的支持度為支持度為s%nsupport (XY)=P (X Y)n項集的項集的支持度計數(shù)支持度計數(shù)support_countn包含項集的事務數(shù)包含項集的事務數(shù)n若項集若項集X的的支持度支持度記為記為support (X)，規(guī)則的，規(guī)則的置信度置信度為為support (X Y)support (X)。n是一個條件概率是一個條件概率P (Y | X)。confidence (XY)=P (Y | X)n=support _count(

6、X Y)support_count (X)7頻繁模式和關聯(lián)規(guī)則頻繁模式和關聯(lián)規(guī)則nItemset X=x1, , xkn找出滿足最小支持度和置信度找出滿足最小支持度和置信度的所有規(guī)則的所有規(guī)則 XY n支持度支持度, s, 事務包含事務包含 X Y 的的概率概率 n置信度置信度, c, 事務含事務含 X 也包含也包含 Y 的的條件概率條件概率.顧客購買顧客購買尿布尿布顧客購顧客購買二者買二者顧客購買顧客購買啤酒啤酒Transaction-idItems bought10A, B, D20A, C, D30A, D, E40B, E, F50B, C, D, E, F令令supmin = 50%

7、, confmin = 50%A:3, B:3, D:4, E:3, F:3,AD:3關聯(lián)規(guī)則關聯(lián)規(guī)則Association rules:A D (60%, 100%)D A (60%, 75%)8挖掘關聯(lián)規(guī)則挖掘關聯(lián)規(guī)則一個例子一個例子規(guī)則規(guī)則 A C支持度支持度 = support(A C) = 50%置信度置信度 = support(A C)/support(A) = 66.6%最小支持度最小支持度 50%最小置信度最小置信度 50%Transaction-idItems bought10A, B, C20A, C30A, D40B, E, FFrequent patternSuppor

8、tA75%B50%C50%A, C50%9第第5講：挖掘關聯(lián)規(guī)則講：挖掘關聯(lián)規(guī)則n關聯(lián)規(guī)則挖掘關聯(lián)規(guī)則挖掘n事務數(shù)據(jù)庫中關聯(lián)規(guī)則挖掘算法事務數(shù)據(jù)庫中關聯(lián)規(guī)則挖掘算法n基于限制的關聯(lián)挖掘基于限制的關聯(lián)挖掘10Apriori算法的步驟算法的步驟nApriori算法將發(fā)現(xiàn)關聯(lián)規(guī)則的過程分為兩個步驟：算法將發(fā)現(xiàn)關聯(lián)規(guī)則的過程分為兩個步驟：n通過通過迭代迭代、檢索檢索出事務數(shù)據(jù)庫中的所有頻繁項集，即支出事務數(shù)據(jù)庫中的所有頻繁項集，即支持度不低于用戶設定的閾值的項集；持度不低于用戶設定的閾值的項集；n利用頻繁項集構造出滿足用戶最小信任度的規(guī)則。利用頻繁項集構造出滿足用戶最小信任度的規(guī)則。n挖掘或識別出挖掘

9、或識別出所有頻繁項集所有頻繁項集是該算法的是該算法的核心核心，占整，占整個計算量的大部分。個計算量的大部分。 11頻繁項集頻繁項集n為了避免計算所有項集的支持度（實際上頻為了避免計算所有項集的支持度（實際上頻繁項集只占很少一部分），繁項集只占很少一部分），Apriori算法引算法引入入潛在頻繁項集潛在頻繁項集的概念。的概念。n若若潛在頻繁潛在頻繁k項集項集的集合記為的集合記為Ck ，頻繁，頻繁k項集項集的集合記為的集合記為Lk ，m個項構成的個項構成的k項集的集合項集的集合為為 ，則三者之間滿足關系，則三者之間滿足關系Lk Ck 。kmCkmC12關聯(lián)規(guī)則的性質關聯(lián)規(guī)則的性質 n性質性質1：頻

10、繁項集的子集必為頻繁項集。：頻繁項集的子集必為頻繁項集。 n性質性質2：非頻繁項集的超集一定是非頻繁的：非頻繁項集的超集一定是非頻繁的。 nApriori算法運用性質算法運用性質1，通過已知的頻繁項集，通過已知的頻繁項集構成長度更大的項集，并將其稱為潛在頻繁項構成長度更大的項集，并將其稱為潛在頻繁項集。集。n潛在頻繁潛在頻繁k項集項集的集合的集合Ck 是指由有可能成為頻繁是指由有可能成為頻繁k項項集的項集組成的集合。集的項集組成的集合。n以后只需計算潛在頻繁項集的支持度，而不必以后只需計算潛在頻繁項集的支持度，而不必計算所有不同項集的支持度，計算所有不同項集的支持度，因此在一定程度因此在一定程

11、度上減少了計算量。上減少了計算量。 13Apriori: 一種候選產(chǎn)生一種候選產(chǎn)生-測試方法測試方法n頻繁項集的任何子集必須是頻繁的頻繁項集的任何子集必須是頻繁的n如果如果 beer, diaper, nuts 是頻繁的是頻繁的, beer, diaper也是也是n每個包含每個包含 beer, diaper, nuts的事務的事務 也包含也包含 beer, diaper nApriori 剪枝原則剪枝原則: （性質（性質2）n如果一個項集不是如果一個項集不是頻繁的頻繁的, 將不產(chǎn)生將不產(chǎn)生/測試它的超集測試它的超集!n方法方法: n由長度為由長度為k的的頻繁頻繁項集項集產(chǎn)生長度為產(chǎn)生長度為 (

12、k+1) 的候選項集的候選項集n并且根據(jù)并且根據(jù) D測試這些候選（測試這些候選（.）14Apriori 算法算法 一個例子一個例子數(shù)據(jù)庫數(shù)據(jù)庫 TDB第第1次掃描次掃描C1L1L2C2C2第第2次掃描次掃描C3L3第第3次掃描次掃描TidItems10A, C, D20B, C, E30A, B, C, E40B, EItemsetsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA, BA, CA, EB, CB, EC, EItemsetsupA, B1A, C2A, E1B, C2B, E3C, E2ItemsetsupA, C2B, C2B, E3C, E2I

13、temsetB, C, EItemsetsupB, C, E215Apriori算法算法n(1) L1=頻繁頻繁1項集項集; n(2) for(k=2;Lk-1;k+) do begin n(3) Ck=apriori_gen(Lk-1); /新的潛在頻繁項集新的潛在頻繁項集 n(4) for all transactions t D do begin n(5) Ct=subset(Ck,t); /找出找出t中包含的潛在的頻繁項中包含的潛在的頻繁項 n(6) for all candidates c Ct do n(7) c.count+; n(8) end; n(9) Lk=c Ck|c.c

14、ount minsup n(10) end; n(11) Answer= kkL16Apriori的重要細節(jié)的重要細節(jié)n如何產(chǎn)生候選如何產(chǎn)生候選?n步驟步驟 1: Lk的自連接的自連接 n步驟步驟 2: 剪枝剪枝n候選產(chǎn)生的例子候選產(chǎn)生的例子nL3=abc, abd, acd, ace, bcdn自連接自連接: L3*L3nAbcd：由由 abc 和和 abdnAcde：由由 acd 和和 acen剪枝剪枝:nacde 被刪除被刪除, 因為因為 ade 不在不在 L3nC4=abcd17如何產(chǎn)生候選如何產(chǎn)生候選?n假定假定 Lk-1 中的項集已排序中的項集已排序(按字典序排序按字典序排序)n步

15、驟步驟 1: Lk-1自連接自連接 insert into Ckselect p.item1, p.item2, , p.itemk-1, q.itemk-1from Lk-1 p, Lk-1 qwhere p.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 q.itemk-1nStep 2: 剪枝剪枝forall itemsets c in Ck doforall (k-1)-subsets s of c doif (s is not in Lk-1) then delete c from Ck18例子例子-支持計數(shù)支持計數(shù)=219例子例子20

16、由頻繁項集產(chǎn)生關聯(lián)規(guī)則由頻繁項集產(chǎn)生關聯(lián)規(guī)則n根據(jù)公式產(chǎn)生關聯(lián)規(guī)則根據(jù)公式產(chǎn)生關聯(lián)規(guī)則n對于每個頻繁項集對于每個頻繁項集l，產(chǎn)生所有的非空子集，產(chǎn)生所有的非空子集n對于對于l的每個非空子集的每個非空子集s，如果，如果則輸出規(guī)則則輸出規(guī)則”s (l-s)”21頻繁模式挖掘的挑戰(zhàn)頻繁模式挖掘的挑戰(zhàn)n挑戰(zhàn)挑戰(zhàn)n事務數(shù)據(jù)庫的多遍掃描n數(shù)量巨大的候選n候選支持度計數(shù)繁重的工作量n改進改進 Apriori: 基本思想基本思想n減少事務數(shù)據(jù)庫的掃描遍數(shù)n壓縮候選數(shù)量n便于候選計數(shù)n提高提高Apriori算法的方法算法的方法（劃分和采樣）（劃分和采樣）22n劃分劃分: 只掃描數(shù)據(jù)庫兩次只掃描數(shù)據(jù)庫兩次n項集在

17、項集在D中是頻繁的中是頻繁的, 它必須至少在它必須至少在D的一個劃分中是頻繁的的一個劃分中是頻繁的n掃描掃描 1: 劃分數(shù)據(jù)庫劃分數(shù)據(jù)庫, 并找出局部頻繁模式并找出局部頻繁模式 n掃描掃描 2: 求出全局頻繁模式求出全局頻繁模式n采樣：頻繁模式采樣：頻繁模式n選取原數(shù)據(jù)庫的一個樣本選取原數(shù)據(jù)庫的一個樣本, 使用使用Apriori 算法在樣本中挖掘算法在樣本中挖掘頻繁模式頻繁模式n掃描一次數(shù)據(jù)庫掃描一次數(shù)據(jù)庫, 驗證在樣本中發(fā)現(xiàn)的頻繁模式驗證在樣本中發(fā)現(xiàn)的頻繁模式.n再次掃描數(shù)據(jù)庫再次掃描數(shù)據(jù)庫, 找出遺漏的頻繁模式找出遺漏的頻繁模式n犧牲一些精度換取有效性。犧牲一些精度換取有效性。23頻繁模式

18、挖掘的瓶頸頻繁模式挖掘的瓶頸n多遍數(shù)據(jù)庫掃描是多遍數(shù)據(jù)庫掃描是 昂貴的昂貴的n挖掘長模式需要很多遍掃描挖掘長模式需要很多遍掃描, 并產(chǎn)生大量候選并產(chǎn)生大量候選n挖掘頻繁模式挖掘頻繁模式 i1i2i100n掃描次數(shù)掃描次數(shù): 100n候選個數(shù)候選個數(shù): (1001) + (1002) + + (100100) = 2100-1 = 1.27*1030 !n瓶頸瓶頸: 候選產(chǎn)生候選產(chǎn)生-測試測試n能夠避免候選產(chǎn)生嗎能夠避免候選產(chǎn)生嗎?（FP-樹）樹）24挖掘關聯(lián)規(guī)則挖掘關聯(lián)規(guī)則n關聯(lián)規(guī)則挖掘關聯(lián)規(guī)則挖掘n事務數(shù)據(jù)庫中關聯(lián)規(guī)則挖掘的算法事務數(shù)據(jù)庫中關聯(lián)規(guī)則挖掘的算法n基于限制的關聯(lián)挖掘基于限制的關聯(lián)

19、挖掘25基于約束的數(shù)據(jù)挖掘基于約束的數(shù)據(jù)挖掘n自動地自動地找出數(shù)據(jù)庫中的找出數(shù)據(jù)庫中的所有所有模式模式? 不現(xiàn)實不現(xiàn)實(模式太多模式太多)!n基于約束的挖掘基于約束的挖掘n用戶靈活性用戶靈活性: 提供挖掘的提供挖掘的 約束約束 n系統(tǒng)優(yōu)化系統(tǒng)優(yōu)化: 考察限制考察限制, 尋找有效的挖掘尋找有效的挖掘基于約束的挖掘基于約束的挖掘n知識類型約束知識類型約束:分類分類, 關聯(lián)關聯(lián), 等等n數(shù)據(jù)約束數(shù)據(jù)約束 （指定任務相關的數(shù)據(jù)集）（指定任務相關的數(shù)據(jù)集）n找出找出 Vancouver 2000年年12月份一起銷售的產(chǎn)品對月份一起銷售的產(chǎn)品對n興趣度約束興趣度約束強規(guī)則強規(guī)則 : min_support

20、 3%, min_confidence 60%n規(guī)則規(guī)則 (或模式或模式) 約束約束-指定規(guī)則形式指定規(guī)則形式n小額銷售小額銷售 (價格價格 $200)26規(guī)則約束規(guī)則約束- -剪枝搜索空間剪枝搜索空間n規(guī)則約束的分類規(guī)則約束的分類n反單調性反單調性Anti-monotonicn單調性單調性Monotonicn簡潔性簡潔性 Succinct:27規(guī)則約束規(guī)則約束n反單調性反單調性n當項集當項集 S S 違反規(guī)則約束時違反規(guī)則約束時, , 它的任何超集它的任何超集合也違反約束合也違反約束nsum(S.Price) sum(S.Price) v v 是是反單調的反單調的nsum(S.Price)

21、sum(S.Price) v v 不是不是反單調的反單調的n單調性單調性n當項集當項集 S S 滿足滿足約束約束時時, , 它的任何超集合也它的任何超集合也滿足約束滿足約束nsum(S.Price) sum(S.Price) v v 是是單調的單調的nmin(S.Price) min(S.Price) v v 是是單調的單調的n簡潔性簡潔性:不查看事務數(shù)據(jù)庫不查看事務數(shù)據(jù)庫, 項集項集S 是否滿足約束是否滿足約束C可以可以根據(jù)選取的項確定根據(jù)選取的項確定 nmin(S.Price) v 是簡潔的是簡潔的nsum(S.Price) v 不是簡潔的不是簡潔的TIDTransaction10a, b

22、, c, d, f20b, c, d, f, g, h30a, c, d, e, f40c, e, f, gTDB (min_sup=2)ItemProfita40b0c-20d10e-30f30g20h-1028Apriori 算法算法 一個例子一個例子TID Items100 1 3 4200 2 3 5300 1 2 3 5400 2 5Database Ditemset sup.1223334153itemset sup.12233353Scan DC1L1itemset1 21 31 52 32 53 5itemset sup1 211 321 512 322 533 52items

23、et sup1 322 322 533 52L2C2C2Scan DC3L3itemset2 3 5Scan Ditemset sup2 3 5229樸素算法樸素算法: Apriori + 約束約束TID Items100 1 3 4200 2 3 5300 1 2 3 5400 2 5Database Ditemset sup.1223334153itemset sup.12233353Scan DC1L1itemset1 21 31 52 32 53 5itemset sup1 211 321 512 322 533 52itemset sup1 322 322 533 52L2C2C2Scan DC3L3itemset2 3 5Scan Ditemset sup2 3 52約束約束: SumS.price 530受約束的受約束的A