Frequent pattern: a pattern (a set of items, subsequences, substructures, etc.) that occurs frequently in a data set
First proposed by Agrawal, Imielinski, and Swami [AIS93] in the context of frequent itemsets and association rule mining
Motivation: Finding inherent regularities in data
What products were often purchased together?— Beer and diapers?!
What are the subsequent purchases after buying a PC?
What kinds of DNA are sensitive to this new drug?
Can we automatically classify web documents?
Applications
Basket data analysis,cross-marketing, catalog design, sale campaign analysis, Web log (click stream)
analysis, and DNA sequence analysis.
Apriori 及其改進算法
規(guī)則:? {x1，x2，…,xn} =>Y ?
如果顧客把商品x1，x2纱兑，…, xn放入購物籃中的話，則很可能也會把商品Y放入其中翅阵。這個可能性（購買x1姚建，x2止状，…,xn的前提下購買Y）稱作規(guī)則的可信度，人們通常只對那些可信度大于某個值的規(guī)則感興趣阳仔，希望把這些規(guī)則找出來忧陪。當然，有可能出現(xiàn)這樣的情況近范，某些商品是被隨機放入購物籃中的嘶摊，例如：類似這樣的規(guī)則，{牛奶顺又，黃油}—〉面包更卒，它的可信度非常大，可能是因為很多人都購買面包稚照，象這樣的規(guī)則是無用的蹂空。
可信度和最小可信度
購買x1俯萌，x2，…, xn 的情況下購買Y的可能性, 條件概率
支持度和最小支持度
同時購買x1上枕，x2咐熙，…,xn??? 和Y的可能性?
頻繁項目集
滿足最小支持度的項目集
支持度：
support(A => B ) = P(A ∪ B)??????????
可信度：????????????????????????????????????????????????????
confidence(A => B) =? P(B|A)
兩個子問題：
1.根據用戶輸入的最小支持度，尋找頻繁項目集
2. 根據用戶輸入的最小可信度辨萍，產生關聯(lián)規(guī)則
第二個問題比較簡單棋恼，關鍵是解決第一個問題
Boolean AR：算法設計的重要前提
以“市場-購物籃”為數據模型，把數據看作一個布爾矩陣锈玉，其中行=購物籃爪飘，列=商品項目：
1.矩陣很稀疏，幾乎全是0
2.列的數目（項目數）要足夠小拉背，每列存點東西的話可以把所有的列放入內存师崎，同時列的數目又要足夠大，每個項目對存點東西的話不能全部放入內存椅棺。
3.行的數目很多犁罩，不可能把整個矩陣放入內存，即使利用稀疏采用壓縮也不行两疚。
主要考慮：
?它對數據的掃描次數?數據挖掘的主要代價是從硬盤讀數據床估，因此估算一個數據挖掘算法運行時間的最好手段是看它對同一個數據讀了幾次。
重要公理：
如果一個項目集S是頻繁的（項目集S的出現(xiàn)頻度大于最小支持度s）诱渤，那么S的任意子集也是頻繁的丐巫。
要找出頻繁項目集，主要有兩類算法：
1.分層挖掘 （每一層需要對數據做一次掃描）
先找出大小為1的頻繁項目集源哩，再找出大小為2的頻繁項目集鞋吉，再找出大小為3的頻繁項目集鸦做，等等励烦。
我們只需要把精力放在大小為2的頻繁項目集上，因為：
通常泼诱，大小為2的頻繁項目集就足夠了坛掠。
在很多數據集合里，查找大小為2的頻繁項目集比較困難治筒，進行高層挖掘比查找大小為2的頻繁項目集用的時間要少屉栓。
2.?? 數據做一次（最多兩次）掃描，找出最大頻繁集?? （任何超集都不是頻繁集的集合S）耸袜。
Apriori 算法
步驟1：分層尋找頻繁項目集
1.給出minisupp友多，第一次掃描數據的時候，找出頻度大于minisupp的項目堤框，稱這集合為L1域滥。一般來說纵柿，一個商店賣的商品品種不會超過10萬個，所以我們假定有足夠的內存來計算每個項目的出現(xiàn)頻度启绰。
2.第二次掃描數據時昂儒，L1中的項目對成為大小為2的候選項目集C2，我們希望C2不要太大委可，這樣的話就可以有足夠的空間為每個候選對分配一個計數器來計算它的出現(xiàn)頻度渊跋，計數值大于minisupp的候選對構成大小為2的頻繁項目集L2。
3.第三次掃描數據時着倾，由L2生成大小為3的候選項目集C3拾酝，C3是這樣的集合{A，B卡者，C}微宝，并且{A，B}虎眨，{B蟋软，C}，{A嗽桩，C}都在L2中岳守。計算C3中每個三元組的出現(xiàn)頻度，大于minisupp構成L3碌冶。
4.一直進行到集合為空時為止湿痢。Li是大小為i的頻繁項目集，Ci+1是大小為i+1的集合扑庞，這些集合的每個大小為i 的子集都在Li中譬重。?
步驟2:產生關聯(lián)規(guī)則
對于每個頻繁項目集L，產生它的所有非空子集S
對L的每個非空子集S罐氨，如果滿足如下條件：
? 則輸出關聯(lián)規(guī)則S→(L – S)
The Apriori Algorithm? ? ? An Example：
對A-priori算法的改進：
1.當>=2時,減小候選集Ci的大小.這一點非常重要,因為即使對于找頻繁的對(大小為2的頻繁項目集),候選集的大小必須足夠小,給每個對加一個計數器之后還可以在內存中放得下.（基于hash的算法以及Iceberg 查詢對hash算法的改進）
2.? 把找L1,L2,…,Ln的過程合并成一次(最多兩次)掃描,而不是每層掃描一次.（Sample算法臀规，Partition算法，Dynamic算法）?
3.? 減小數據庫的大小任何一個事務（一個購物藍）栅隐，如果它不包含k-itemset塔嬉，則不包含k+1-itemset，可以去掉租悄。（基于hash的算法采用了該技術）
基于hash的算法
利用了內存通常比項目數要大的事實,在第一次掃描數據決定L1的時候谨究，建立一個哈希表（P237），根據該表的數據來提前去掉那些不可能是頻繁的2-itemset. 在第一次開始掃描數據決定L1時泣棋，內存中的情況如圖：
pass1：
1.計算所有項目的頻度
2.對每一個記錄胶哲，將所有的 2-Itemset 哈希到哈希表的某個桶中,桶的計數增加1
3.掃描結束時，將頻度大于s的項目放入L1.
4.掃描結束時潭辈，找出哈希表中計數值大于s的桶（在結果位圖中，相應位設為1）。
在第二次掃描數據決定L2時盼砍，內存中的情況如圖：
pass2：
1.內存中存放有大小為1的頻繁項目集L1。
2.內存中存放有位圖
3.最后棚辽，內存中還放了一個表，存放所有的候選對和它們的計數值冰肴，候選對集合C2中的每一個對（i屈藐，j），必須滿足下列條件：
?i? 在L1中熙尉，j 在L1中
對（i联逻，j）必須哈希到一個頻繁桶中
第二點正是PCY算法和直接a-priori算法之間的不同之處。PCY算法減小了第二次掃描數據時的內存需求检痰。
4.??? 最后包归，在第二次掃描數據時，考察每一個2-Itemset铅歼，如果滿足上面列出的兩個條件公壤，則在內存中增加它的計數值，如果第一次出現(xiàn)的話創(chuàng)建一個入口點椎椰。
example:
什么時候Hash算法比Apriori算法優(yōu)越厦幅？
?當C2很大（C2和他們的計數器在內存中放不下），而Hash算法產生的頻繁桶卻很少（大大地減小了C2的大小慨飘，使之能全部裝入內存,從而不需要再掃描數據）時确憨，Hash算法比Apriori算法優(yōu)越。
partition算法(two passes)
將數據劃分成多個子集, 分別讀入內存瓤的，找出局部候選集(pass 1)
再次掃描數據休弃，找出所有的頻繁集.(pass 2)
關鍵點: 一個集合如果在任一個子集中都不頻繁，則它在全局數據中也不頻繁
Sample算法(one or two passes)
隨機取內存大小的一個數據的樣本圈膏，在內存中運行一個層次算法（不用負擔I/O）塔猾，希望從這個樣本數據能求出真正的頻繁集
按比例伸縮最小支持率，如果樣本數據是整個數據的1%本辐，則應該用s%作為新的最小支持率
完整地掃描數據一次桥帆，對由樣本數據得出的頻繁項目集進行驗證，但是那些在全局數據中頻繁但在樣本數據中不頻繁的集合被丟掉了
為了減小false negative慎皱，可以將樣本數據的最小支持率降低一點，這樣在全面掃描數據的時候就可以找到更多的候選集叶骨。但注意：這樣做的后果可能會產生太多的候選集而使內存裝不下茫多。
------------------------------------------------------
References
[AgSr94] R. Agrawal, R. Srikant, “Fast?Algorithms for Mining Association Rules”, Proc. of the 20th Int'l Conference on Very Large Databases, Santiago, Chile, Sept. 1994.
[AgSr96] R. Srikant, R. Agrawal: "Mining?Sequential Patterns: Generalizations and Performance Improvements", to appear in Proc. of the Fifth Int'l Conference on Extending Database Technulogy (EDBT), Avignon, France, March 1996.
[BeRa99] Kevin S. Beyer and Raghu Ramakrishnan.? “Bottom-Up Computation of?Sparse and Iceberg CUBEs”. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 359-370, June 1999.
[HPDW01] J. Han, J. Pei, G.Dong, and K. Wang, “Efficient Computation?of Iceberg Cubes with Complex Measures”, Proc. 2001 ACM-SIGMOD Int. Conf. on Management of Data (SIGMOD'01), Santa Barbara, CA, May 2001.
[HPY00] J. Han, J. Pei, and Y.Yin, `` Mining Frequent?Patterns without Candidate Generation'',, Proc. 2000 ACM-SIGMOD Int. Conf. on Management of Data (SIGMOD'00), Dallas, TX, May 2000.
[HaPe00] J. Han and J. Pei ``Mining Frequent?Patterns by Pattern-Growth: Methodology and Implications'', ACM SIGKDD Explorations (Special Issue on Scaleble Data Mining Algorithms), 2(2),December 2000.
[PHPC01] J. Pei, J. Han, H.Pinto, Q. Chen, U. Dayal, and M.-C. Hsu, “ PrefixSpan: Mining Sequential?Patterns Efficiently by Prefix-Projected Pattern Growth'', Proc. 2001 Int. Conf. on Data Engineering (ICDE'01), Heidelberg, Germany, April 2001.
