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

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

2、發(fā)現(xiàn)顧客放入貨籃中的不同商品之間的關(guān)系來(lái)分析顧客的購(gòu)買(mǎi)習(xí)慣。之間的關(guān)系來(lái)分析顧客的購(gòu)買(mǎi)習(xí)慣。 3什么是關(guān)聯(lián)規(guī)則挖掘什么是關(guān)聯(lián)規(guī)則挖掘n關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則挖掘(1993)n在事務(wù)、關(guān)系數(shù)據(jù)庫(kù)中的項(xiàng)集和對(duì)象中發(fā)現(xiàn)在事務(wù)、關(guān)系數(shù)據(jù)庫(kù)中的項(xiàng)集和對(duì)象中發(fā)現(xiàn)頻繁模式頻繁模式、關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則、相關(guān)性或者因果結(jié)構(gòu)相關(guān)性或者因果結(jié)構(gòu)n頻繁模式頻繁模式: 數(shù)據(jù)庫(kù)中頻繁出現(xiàn)的數(shù)據(jù)庫(kù)中頻繁出現(xiàn)的項(xiàng)集項(xiàng)集 n目的目的: 發(fā)現(xiàn)數(shù)據(jù)中的規(guī)律發(fā)現(xiàn)數(shù)據(jù)中的規(guī)律n超市數(shù)據(jù)中的什么產(chǎn)品會(huì)一起購(gòu)買(mǎi)？超市數(shù)據(jù)中的什么產(chǎn)品會(huì)一起購(gòu)買(mǎi)？ 啤酒和尿布啤酒和尿布n在買(mǎi)了一臺(tái)在買(mǎi)了一臺(tái)PC之后下一步會(huì)購(gòu)買(mǎi)之后下一步會(huì)購(gòu)買(mǎi)?n我們?nèi)绾巫詣?dòng)對(duì)我

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

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

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

6、X Y)support_count (X)7頻繁模式和關(guān)聯(lián)規(guī)則頻繁模式和關(guān)聯(lián)規(guī)則nItemset X=x1, , xkn找出滿足最小支持度和置信度找出滿足最小支持度和置信度的所有規(guī)則的所有規(guī)則 XY n支持度支持度, s, 事務(wù)包含事務(wù)包含 X Y 的的概率概率 n置信度置信度, c, 事務(wù)含事務(wù)含 X 也包含也包含 Y 的的條件概率條件概率.顧客購(gòu)買(mǎi)顧客購(gòu)買(mǎi)尿布尿布顧客購(gòu)顧客購(gòu)買(mǎi)二者買(mǎi)二者顧客購(gòu)買(mǎi)顧客購(gòu)買(mǎi)啤酒啤酒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關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則Association rules:A D (60%, 100%)D A (60%, 75%)8挖掘關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則一個(gè)例子一個(gè)例子規(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講：挖掘關(guān)聯(lián)規(guī)則講：挖掘關(guān)聯(lián)規(guī)則n關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則挖掘n事務(wù)數(shù)據(jù)庫(kù)中關(guān)聯(lián)規(guī)則挖掘算法事務(wù)數(shù)據(jù)庫(kù)中關(guān)聯(lián)規(guī)則挖掘算法n基于限制的關(guān)聯(lián)挖掘基于限制的關(guān)聯(lián)挖掘10Apriori算法的步驟算法的步驟nApriori算法將發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的過(guò)程分為兩個(gè)步驟：算法將發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的過(guò)程分為兩個(gè)步驟：n通過(guò)通過(guò)迭代迭代、檢索檢索出事務(wù)數(shù)據(jù)庫(kù)中的所有頻繁項(xiàng)集，即支出事務(wù)數(shù)據(jù)庫(kù)中的所有頻繁項(xiàng)集，即支持度不低于用戶設(shè)定的閾值的項(xiàng)集；持度不低于用戶設(shè)定的閾值的項(xiàng)集；n利用頻繁項(xiàng)集構(gòu)造出滿足用戶最小信任度的規(guī)則。利用頻繁項(xiàng)集構(gòu)造出滿足用戶最小信任度的規(guī)則。n挖掘或識(shí)別出挖掘

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

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

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

12、k+1) 的候選項(xiàng)集的候選項(xiàng)集n并且根據(jù)并且根據(jù) D測(cè)試這些候選（測(cè)試這些候選（.）14Apriori 算法算法 一個(gè)例子一個(gè)例子數(shù)據(jù)庫(kù)數(shù)據(jù)庫(kù) 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項(xiàng)集項(xiàng)集; n(2) for(k=2;Lk-1;k+) do begin n(3) Ck=apriori_gen(Lk-1); /新的潛在頻繁項(xiàng)集新的潛在頻繁項(xiàng)集 n(4) for all transactions t D do begin n(5) Ct=subset(Ck,t); /找出找出t中包含的潛在的頻繁項(xiàng)中包含的潛在的頻繁項(xiàng) 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的重要細(xì)節(jié)的重要細(xì)節(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 被刪除被刪除, 因?yàn)橐驗(yàn)?ade 不在不在 L3nC4=abcd17如何產(chǎn)生候選如何產(chǎn)生候選?n假定假定 Lk-1 中的項(xiàng)集已排序中的項(xiàng)集已排序(按字典序排序按字典序排序)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例子例子-支持計(jì)數(shù)支持計(jì)數(shù)=219例子例子20

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

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

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

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

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

21、m(S.Price) ) v v 不是不是反單調(diào)的反單調(diào)的n單調(diào)性單調(diào)性n當(dāng)項(xiàng)集當(dāng)項(xiàng)集 S S 滿足滿足約束約束時(shí)時(shí), , 它的任何超集合也它的任何超集合也滿足約束滿足約束nsum(S.Pricesum(S.Price) ) v v 是是單調(diào)的單調(diào)的nmin(S.Pricemin(S.Price) ) v v 是是單調(diào)的單調(diào)的n簡(jiǎn)潔性簡(jiǎn)潔性:不查看事務(wù)數(shù)據(jù)庫(kù)不查看事務(wù)數(shù)據(jù)庫(kù), 項(xiàng)集項(xiàng)集S 是否滿足約束是否滿足約束C可以可以根據(jù)選取的項(xiàng)確定根據(jù)選取的項(xiàng)確定 nmin(S.Price) v 是簡(jiǎn)潔的是簡(jiǎn)潔的nsum(S.Price) v 不是簡(jiǎn)潔的不是簡(jiǎn)潔的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 算法算法 一個(gè)例子一個(gè)例子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