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

,Apriori Algorithm,小組成員 吳國(guó)泉、唐思遠(yuǎn)、趙清偉、張波,2,購(gòu)物籃分析：引發(fā)性例子,Questions 關(guān)聯(lián) 分析 Solutions,1：經(jīng)常同時(shí)購(gòu)買(mǎi)的商品可以擺近一點(diǎn)，以便進(jìn)一步刺激這些商品一起銷(xiāo)售。 2：規(guī)劃哪些附屬商品可以降價(jià)銷(xiāo)售，以便刺激主體商品的捆綁銷(xiāo)售。,哪組商品顧客可能會(huì)在一次購(gòu)物時(shí)同時(shí)購(gòu)買(mǎi)？,關(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的百分比。 Confidence（ ）= P（ ）/P（A） （k項(xiàng)集）包含k個(gè)項(xiàng)的項(xiàng)集稱(chēng)為k項(xiàng)集，頻繁k項(xiàng)集的集合記作 ，候選k項(xiàng)集的集合記作 。,由頻繁項(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)集。 （4）同時(shí)滿足最小支持度閥值和最小置信度閥值的規(guī)則稱(chēng)為強(qiáng)規(guī)則。,Apriori算法說(shuō)明,在Apriori算法中,尋找最大項(xiàng)目集的基本思想是: 算法需要對(duì)數(shù)據(jù)集進(jìn)行多步處理.第一步,簡(jiǎn)單統(tǒng)計(jì)所有含一個(gè)元素項(xiàng)目集出現(xiàn)的頻率,并找出那些不小于最小支持度的項(xiàng)目集, 即一維最大項(xiàng)目集L1. 從第二步開(kāi)始循環(huán)處理直到再?zèng)]有最大項(xiàng)目集生成. 循環(huán)過(guò)程是: 第k步中, 根據(jù)第k-1步生成的(k-1)維最大項(xiàng)目集產(chǎn)生k維侯選項(xiàng)目集CK, 然后對(duì)數(shù)據(jù)庫(kù)進(jìn)行搜索, 得到侯選項(xiàng)目集的項(xiàng)集支持度, 與最小支持度比較, 從而找到k維頻繁項(xiàng)目集LK.,連接步,為找出Lk，通過(guò)將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的超集，也就是說(shuō)，CK的成員可能是也可能不是頻繁的。通過(guò)掃描所有的事務(wù)（交易），確定CK中每個(gè)候選的計(jì)數(shù)，判斷是否小于最小支持度計(jì)數(shù)，如果不是，則認(rèn)為該候選是頻繁的。為了壓縮Ck,可以利用Apriori性質(zhì)：任一頻繁項(xiàng)集的所有非空子集也必須是頻繁的，如果某個(gè)候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的，從而可以將其從CK中刪除。,Apriori算法實(shí)例,頻繁項(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)集遺漏。,Apriori算法,假設(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。 通過(guò)I1，I2，I3和I1，I2，I4的組合，就可以得到I1，I2，I3，I4.所以不會(huì)遺漏。,Apriori算法的缺陷,（1）在每一步產(chǎn)生侯選項(xiàng)目集時(shí)循環(huán)產(chǎn)生的組合過(guò)多，沒(méi)有排除不應(yīng)該參與組合的元素; （2）每次計(jì)算項(xiàng)集的支持度時(shí)，都對(duì)數(shù)據(jù)庫(kù)D中的全部記錄進(jìn)行了一遍掃描比較，如果是一個(gè)大型的數(shù)據(jù)庫(kù)的話，這種掃描比較會(huì)大大增加計(jì)算機(jī)系統(tǒng)的I/O開(kāi)銷(xiāo)。而這種代價(jià)是隨著數(shù)據(jù)庫(kù)的記錄的增加呈現(xiàn)出幾何級(jí)數(shù)的增加。 因此人們開(kāi)始尋求一種能減少這種系統(tǒng)1/O開(kāi)銷(xiāo)的更為快捷的算法。,Apriori算法的優(yōu)化思路,在逐層搜索循環(huán)過(guò)程的第k步中，根據(jù)k-1步生成的k-1維頻繁項(xiàng)目集來(lái)產(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ì)某元素而言，若它的計(jì)數(shù)個(gè)數(shù)不到k-1的話，可以事先刪除該元素，從而排除由該元素將引起的大規(guī)格所有組合。 這是因?yàn)閷?duì)某一個(gè)元素要成為K維項(xiàng)目集的一元素的話，該元素在k-1階頻繁項(xiàng)目集中的計(jì)數(shù)次數(shù)必須達(dá)到K-1個(gè)，否則不可能生成K維項(xiàng)目集(性質(zhì)3)。,根據(jù)以上思路得到了這個(gè)候選項(xiàng)目集后，可以對(duì)數(shù)據(jù)庫(kù)D的每一個(gè)事務(wù)進(jìn)行掃描，若該事務(wù)中至少含有候選項(xiàng)目集CK中的一員則保留該項(xiàng)事務(wù)，否則把該事物記錄與數(shù)據(jù)庫(kù)末端沒(méi)有作刪除標(biāo)記的事務(wù)記錄對(duì)換，并對(duì)移到數(shù)據(jù)庫(kù)末端的事務(wù)記錄作刪除標(biāo)一記，整個(gè)數(shù)據(jù)庫(kù)掃描完畢后為新的事務(wù)數(shù)據(jù)庫(kù)D 中。 因此隨著K 的增大，D中事務(wù)記錄量大大地減少，對(duì)于下一次事務(wù)掃描可以大大節(jié)約I/0 開(kāi)銷(xiāo)。由于顧客一般可能一次只購(gòu)買(mǎi)幾件商品，因此這種虛擬刪除的方法可以實(shí)現(xiàn)大量的交易記錄在以后的挖掘中被剔除出來(lái)，在所剩余的不多的記錄中再作更高維的數(shù)據(jù)挖掘是可以大大地節(jié)約時(shí)間的。,Apriori算法的優(yōu)化實(shí)例,Apriori算法的優(yōu)化效果,（1）優(yōu)化算法在考慮組合CK前，對(duì)將參與組合的元素進(jìn)行計(jì)數(shù)處理，根據(jù)計(jì)數(shù)結(jié)果決定排除一些不符合組合條件的元素而降低循環(huán)判斷的次數(shù)。如果對(duì)大型的數(shù)據(jù)庫(kù)而言，這種時(shí)間開(kāi)銷(xiāo)的降低對(duì)數(shù)據(jù)挖掘效率來(lái)說(shuō)是顯而易見(jiàn)的，這是Apriori方法中沒(méi)有涉及的; （2） 優(yōu)化算法對(duì)數(shù)據(jù)庫(kù)進(jìn)行掃描后重新生成(刪除一些不能支持頻繁集的記錄，這里所謂的刪除實(shí)際上是把不符合再次掃描比較條件的記錄通過(guò)交換記錄內(nèi)容的方式移到數(shù)據(jù)庫(kù)的末端