大數(shù)據(jù)經(jīng)典算法Apriori講解11704

1、Apriori Algorithm小組成員小組成員吳國泉、唐思遠、趙清偉、張波吳國泉、唐思遠、趙清偉、張波2購物籃分析：引發(fā)性例子購物籃分析：引發(fā)性例子Questions 關(guān)聯(lián) 分析Solutions1：經(jīng)常同時購買的商品可以擺近一點，以便進一步刺激這些商品一起銷售。2：規(guī)劃哪些附屬商品可以降價銷售，以便刺激主體商品的捆綁銷售。 哪組商品顧客可能會在一次購物時同時購買？關(guān)聯(lián)分析的基本概念關(guān)聯(lián)分析的基本概念關(guān)聯(lián)規(guī)則是形如 的蘊含式， （支持度支持度）規(guī)則 在事務(wù)集D中成立，支持度S是事務(wù)包含 的百分比。Support（ ）= P（ ） （置信度置信度）置信度C是D中同時包含A的事務(wù)同時也包含B的

2、百分比。Confidence（ ）= P（ ）/P（A） （k項集項集）包含k個項的項集稱為k項集，頻繁k項集的集合記作 ，候選k項集的集合記作 。BA ，且BA,AIBIBA BABA BABA kLkCBA由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則（1）K維數(shù)據(jù)項集LK是頻繁項集的必要條件是它所有K-1維子項集也為頻繁項集，記為LK-1（2）如果K維數(shù)據(jù)項集LK的任意一個K-1維子集LK-1，不是頻繁項集，則K維數(shù)據(jù)項集LK本身也不是最大數(shù)據(jù)項集。（3）LK是K維頻繁項集，如果所有K-1維頻繁項集集合LK-1中包含LK的K-1維子項集的個數(shù)小于K，則LK不可能是K維最大頻繁數(shù)據(jù)項集。

3、（4）同時滿足最小支持度閥值和最小置信度閥值的規(guī)則稱為強規(guī)則強規(guī)則。Apriori算法說明算法說明 在Apriori算法中,尋找最大項目集的基本思想是: 算法需要對數(shù)據(jù)集進行多步處理.第一步,簡單統(tǒng)計所有含一個元素項目集出現(xiàn)的頻率,并找出那些不小于最小支持度的項目集, 即一一維最大項目集維最大項目集L L1 1. 從第二步開始循環(huán)處理直到再沒有最大項目集生成. 循環(huán)過程是: 第k步中, 根據(jù)第k-1步生成的(k-1)維最大項目集產(chǎn)生k維侯選項目集維侯選項目集C CK K, 然后對數(shù)據(jù)庫進行搜索, 得到侯選項目集的項集支持度, 與最小支持度比較, 從而找到k維頻繁項維頻繁項目集目集L LK K.

4、連接步連接步 為找出Lk，通過將Lk-1與自身連接產(chǎn)生候選k項集的集合Ck。設(shè)l1和l2是Lk-1中的成員。記lij表示li中的第j項。假設(shè)Apriori算法對事務(wù)集中的項按字典次序排序，即對于(k-1)項集li，li1li2lik-1 。將Lk-1與自身連接，如果(l11=l21)&( l12=l22)&. & (l1k-2=l2k-2)&(l1k-1l2k-1)，那認為l1和l2是可連接。連接l1和l2 產(chǎn)生的結(jié)果是l11,l12,l1k-1,l2k-1。剪枝步剪枝步 CK是LK的超集，也就是說，CK的成員可能是也可能不是頻繁的。通過掃描所有的事務(wù)（交易），

5、確定CK中每個候選的計數(shù)，判斷是否小于最小支持度計數(shù)，如果不是，則認為該候選是頻繁的。為了壓縮Ck,可以利用Apriori性質(zhì)：任一頻繁項集的所有非任一頻繁項集的所有非空子集也必須是頻繁的空子集也必須是頻繁的，如果某個候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的，從而可以將其從CK中刪除。Apriori算法實例頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則Apriori算法 如果存在I1，I2，I4. 和 I1，I3，I4兩組的時候，我們要不要連接？我認為是不用的。首先，不用連接的后果，唯一可能造成的后果就是將I1，I2，I3，I4項集遺漏。我們觀察是否會將I1，I2，I3，I4項集遺漏。Ap

6、riori算法 假設(shè)I1，I2，I3，I4項集滿足條件，是存在的。那么候選集中必然存在I1，I2，I3;和I1，,I2，I4 和 I1，I3, I4，和 I2，I3，I4.而不會僅僅是I1，I2，I4. 和 I1，I3，I4。通過I1，I2，I3和I1，I2，I4的組合，就可以得到I1，I2，I3，I4.所以不會遺漏。Apriori算法的缺陷（1）在每一步產(chǎn)生侯選項目集時循環(huán)產(chǎn)生的組合過多，沒有排除不應(yīng)該參與組合的元素;（2）每次計算項集的支持度時，都對數(shù)據(jù)庫D中的全部記錄進行了一遍掃描比較，如果是一個大型的數(shù)據(jù)庫的話，這種掃描比較會大大增加計算機系統(tǒng)的I/O開銷。而這種代價是隨著數(shù)據(jù)庫的記錄

7、的增加呈現(xiàn)出幾何級數(shù)的增加。因此人們開始尋求一種能減少這種系統(tǒng)1/O開銷的更為快捷的算法。Apriori算法的優(yōu)化思路 在逐層搜索循環(huán)過程的第k步中，根據(jù)k-1步生成的k-1維頻繁項目集來產(chǎn)生k維候選項目集，由于在產(chǎn)生k-1維頻繁項目集時，我們可以實現(xiàn)對該集中出現(xiàn)元素的個數(shù)進行計數(shù)處理，因此對某元素而對某元素而言，若它的計數(shù)個數(shù)不到言，若它的計數(shù)個數(shù)不到k-1的話，可以事先刪除的話，可以事先刪除該元素，從而排除由該元素將引起的大規(guī)格所有組該元素，從而排除由該元素將引起的大規(guī)格所有組合合。 這是因為對某一個元素要成為K維項目集的一元素的話，該元素在k-1階頻繁項目集中的計數(shù)次數(shù)必須達到K-1個，

8、否則不可能生成K維項目集(性質(zhì)3)。 根據(jù)以上思路得到了這個候選項目集后，可以對數(shù)據(jù)庫D的每一個事務(wù)進行掃描，若該事務(wù)中至少含有候選項目集C CK K中的一員則保留該項事務(wù)，否則把該事物記錄與數(shù)據(jù)庫末端沒有作刪除標記的事務(wù)記錄對換，并對移到數(shù)據(jù)庫末端的事務(wù)記錄作刪除標一記，整個數(shù)據(jù)庫掃描完畢后為新的事務(wù)數(shù)據(jù)庫D 中。 因此隨著K 的增大，D中事務(wù)記錄量大大地減少，對于下一次事務(wù)掃描可以大大節(jié)約I/0 開銷。由于顧客一般可能一次只購買幾件商品，因此這種虛虛擬刪除擬刪除的方法可以實現(xiàn)大量的交易記錄在以后的挖掘中被剔除出來，在所剩余的不多的記錄中再作更高維的數(shù)據(jù)挖掘是可以大大地節(jié)約時間的。Apriori算法的優(yōu)化實例Apriori算法的優(yōu)化效果（1）優(yōu)化算法在考慮組合C CK K前，對將參與組合的元素進行計數(shù)處理，根據(jù)計數(shù)結(jié)果決定排除一些不符合組合條件的元素而降低循環(huán)判斷的次數(shù)。如果對大型的數(shù)據(jù)庫而言，這種時間開銷的降低對數(shù)據(jù)挖掘效率來說是顯而易見的，這是Apriori方法中沒有涉及的; （2） 優(yōu)化算法對數(shù)據(jù)庫進行掃描后重新生成(刪除一些不能支持頻繁集的記錄，這里所謂的刪除實際上是把不符合再次掃描比較條件的記錄通過交換記錄