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

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

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

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

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

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

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

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

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