Apriori Algorithm 是關(guān)聯(lián)規則領(lǐng)域里最具影響力的基礎算法。它是由
Rakesh Agrawal 在 1994 年提出的，詳細的介紹在這里《
Fast Algorithms for Mining Association Rules》。十幾年過(guò)去了，不少學(xué)者圍繞著(zhù) Apriori 進(jìn)行了諸多改良。但與 1994 年相比，目前基于互聯(lián)網(wǎng)的應用，數據量大了幾十倍甚至是幾百倍，因此，基于 Apriori 的算法逐漸暴露出其運算成本過(guò)高的問(wèn)題。但不管怎樣，對于大師及其做出的貢獻，我們也只有高山仰止的份兒。
Apriori 是一種廣度優(yōu)先算法，通過(guò)多次掃描數據庫來(lái)獲取支持度大于最小支持度的頻繁項集。它的理論基礎是頻繁項集的兩個(gè)單調性原則：頻繁項集的任一子集一定是頻繁的；非頻繁項集的任一超集一定是非頻繁的?；逎睦碚撐疫@里就不多寫(xiě)了，有興趣的可以去看論文。我把里面的例子給翻譯一下，圖文并茂，簡(jiǎn)明易懂。
某數據庫 DB 里有 4 條事務(wù)記錄，取最小支持度（min support）為 0.5，則計算頻繁項集的過(guò)程如下：
TID
| Items
| 100
| A, C, D
| 200
| B, C, E
| 300
| A, B, C, E
| 400
| B, E
|
| 掃描DB
| Itemset
| Support
| {A}
| 2 (0.5)
| {B}
| 3 (0.75)
| {C}
| 3 (0.75)
| {D}
| 1 (0.25)
| {E}
| 3 (0.75)
|
| 取滿(mǎn)足
最小支持度
項集
| Itemset
| Support
| {A}
| 2
| {B}
| 3
| {C}
| 3
| {E}
| 3
|
|
Itemset
| {A, B}
| {A, C}
| {A, E}
| {B, C}
| {B, E}
| {C, E}
|
| 掃描DB
| Itemset
| Support
| {A, B}
| 1 (0.25)
| {A, C}
| 2 (0.5)
| {A, E}
| 1 (0.25)
| {B, C}
| 2 (0.5)
| {B, E}
| 3 (0.75)
| {C, E}
| 2 (0.5)
|
| 取滿(mǎn)足
最小支持度
項集
| Itemset
| Support
| {A, C}
| 2
| {B, C}
| 2
| {B, E}
| 3
| {C, E}
| 2
|
|
Itemset
| {A, B, C}
| {A, B, E}
| {A, C, E}
| {B, C, E}
|
| 掃描DB
| Itemset
| Support
| {A, B, C}
| 1 (0.25)
| {A, B, E}
| 1 (0.25)
| {A, C, E}
| 1 (0.35)
| {B, C, E}
| 2 (0.5)
|
| 取滿(mǎn)足
最小支持度
項集
| Itemset
| Support
| {B, C, E}
| 2 (0.5)
|
|
如上可以看出，在海量數據的情況下，Apriori 算法的運算過(guò)程有 2 個(gè)問(wèn)題：
- 需要多次掃描數據庫，時(shí)間成本很高；
- 運算過(guò)程中需要產(chǎn)生大量的候選集，空間成本也非常高。
針對 Apriori 算法所做的
改進(jìn)也基本上是圍繞著(zhù)解決這兩個(gè)問(wèn)題進(jìn)行的，如在掃描DB前首先進(jìn)行以便事務(wù)合并和壓縮，數據分區或抽樣等。
Weka 里有 Apriori 算法的 Java 實(shí)現，非常值得一看。
貌似
wikipedia 已經(jīng)解封了，呵呵！
預報：關(guān)聯(lián)規則(3)，關(guān)于 FP-Growth 算法。
