????????????????????????????????????????Apriori算法
?Apriori算法將發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的過(guò)程分為兩個(gè)步驟：
????? 1楼咳、通過(guò)迭代偿洁，檢索出事務(wù)數(shù)據(jù)庫(kù)中的所有頻繁項(xiàng)集，即支持度不低于用戶設(shè)定的閾值的項(xiàng)集
????? 2、利用頻繁項(xiàng)集構(gòu)造出滿足用戶最小置信度的規(guī)則促绵。
?? 其中，檢索所有頻繁項(xiàng)集是該算法的核心迂曲，占整個(gè)計(jì)算量的大部分
?Apriori算法的重要性質(zhì)
性質(zhì)1：頻繁項(xiàng)集的子集必為頻繁項(xiàng)集禀忆。如果{B，C}是頻繁的狸页，那么{B}锨能，{C}也一定是頻繁的
性質(zhì)2：非頻繁項(xiàng)集的超集一定是非頻繁的。例如{A,B}是非頻繁的芍耘，那么{A,B, C}址遇，{A,B, C, D}也一定是頻繁的
運(yùn)用Apriori算法的性質(zhì)，我們就能去掉很多非頻繁的項(xiàng)集斋竞，大大簡(jiǎn)化計(jì)算量：
我們發(fā)現(xiàn){A,B}這個(gè)項(xiàng)集是非頻繁的倔约，那么{A,B}這個(gè)項(xiàng)集的超集{A,B,C},{A,B,D}等也都是非頻繁的，這些就都可以忽略不去計(jì)算坝初。
?使用Apriori算法構(gòu)造出滿足用戶最小置信度的規(guī)則：
現(xiàn)有頻繁項(xiàng)集l浸剩，生成每個(gè)非空子集S，若S滿足最小置信度:
則輸出關(guān)聯(lián)規(guī)則(l-s)->s
Example:
最小支持度計(jì)數(shù)為2鳄袍，minconf=80%
? ??Step1:生成頻繁項(xiàng)集：
? ??Step2:生成關(guān)聯(lián)規(guī)則：
?對(duì)于step1得到的頻繁集{B,C,E},有子集{B},{C},{E},{B,E},{B,C},{C,E}绢要，分別計(jì)算置信度：
confidence(BE->C)=2/3<80%
confidence(BC->E)=2/2>80%
confidence(CE->B)=2/2>80%
confidence(B->CE)=2/3<80%
confidence(C->BE)=2/3<80%
confidence(E->BC)=2/3<80%
則滿足條件的為BC->E和CE->B兩條規(guī)則
Apriori的優(yōu)點(diǎn)：
?適合稀疏數(shù)據(jù)集。
?算法原理簡(jiǎn)單拗小，易實(shí)現(xiàn)袖扛。
?適合事務(wù)數(shù)據(jù)庫(kù)的關(guān)聯(lián)規(guī)則挖掘。
?易編碼實(shí)現(xiàn)
Apriori的缺點(diǎn)：
?可能產(chǎn)生龐大的候選集十籍。
?算法需多次遍歷數(shù)據(jù)集蛆封，算法效率低，耗時(shí)勾栗。
?在大數(shù)據(jù)集上可能較慢
? ? ? ? ? ? ? ? ? ? ? ????????????FP-Growth算法? ? ? ? ?
??FpGrowth算法通過(guò)構(gòu)造一個(gè)樹(shù)結(jié)構(gòu)來(lái)壓縮數(shù)據(jù)記錄惨篱，使得挖掘頻繁項(xiàng)集只需要掃描兩次數(shù)據(jù)記錄，而且該算法不需要生成候選集合围俘，效率高砸讳。 而Apriori算法對(duì)于每個(gè)潛在的頻繁項(xiàng)集都會(huì)掃描數(shù)據(jù)集判定給定模式是否頻繁。
?FpTree的數(shù)據(jù)結(jié)構(gòu)：
FpTree是一種樹(shù)結(jié)構(gòu)界牡，樹(shù)結(jié)構(gòu)定義如下：
Example:
假設(shè)最小支持度為3
Step 1：掃描數(shù)據(jù)記錄簿寂，生成一級(jí)頻繁項(xiàng)集，并按出現(xiàn)次數(shù)由多到少排序：
Step 2：再次掃描數(shù)據(jù)記錄宿亡，對(duì)每條記錄中出現(xiàn)在Step1產(chǎn)生的表中的項(xiàng)常遂，按表中的順序排序。
Step 3：遍歷每一條記錄挽荠，生成fpTree克胳。初始時(shí)平绩，新建一個(gè)根結(jié)點(diǎn)，標(biāo)記為null:
Step 4：根據(jù)step1得到的一級(jí)頻繁項(xiàng)集建立項(xiàng)頭表：
Step5:利用FpTree挖掘頻繁項(xiàng)集漠另。從表頭header的最后一個(gè)項(xiàng)開(kāi)始挖掘,得到每一項(xiàng)的條件模式基捏雌。
此處即從{啤酒}開(kāi)始，根據(jù){啤酒}的線索鏈找到所有{啤酒}結(jié)點(diǎn)笆搓，然后找出每個(gè){啤酒}結(jié)點(diǎn)的前綴路徑{牛奶性湿，面包，尿布：1}满败，{牛奶窘奏，尿布:1}，{面包葫录，尿布:1}着裹。其中的“1”表示出現(xiàn)頻次，由后綴結(jié)點(diǎn){啤酒}的次數(shù)決定米同。
根據(jù)前綴路徑我們可以生成條件FpTree骇扇，構(gòu)造方式跟之前一樣，此處的數(shù)據(jù)記錄變?yōu)椋?/p>
Step6：使用條件模式基構(gòu)造條件fpTree:
構(gòu)造好條件樹(shù)后面粮，對(duì)條件樹(shù)進(jìn)行遞歸挖掘少孝，當(dāng)條件樹(shù)只有一條路徑時(shí)，路徑的所有組合即為條件頻繁集熬苍。此處的條件頻繁集為：{{}稍走，{尿布}}，于是得到以{啤酒}為后綴的頻繁集為{啤酒}柴底、{尿布婿脸，啤酒}。
接下來(lái)重復(fù)step5,step6找header表頭的倒數(shù)第二個(gè)項(xiàng){尿布}的頻繁集,直到header表頭每個(gè)項(xiàng)挖掘完成柄驻。
?{尿布}的前綴路徑為：{面包：1}狐树，{牛奶：1}，{牛奶鸿脓，面包：2}
得到一組頻繁項(xiàng)集{尿布}抑钟，{牛奶，尿布}野哭，{面包在塔，尿布}，{牛奶拨黔，面包蛔溃，尿布}
重復(fù)以上步驟，對(duì)header表頭的每個(gè)項(xiàng)進(jìn)行挖掘，即可得到整個(gè)頻繁項(xiàng)集
FP-Growth算法總結(jié)：
?兩次掃描數(shù)據(jù)庫(kù)：
? 第一次掃描得出單個(gè)頻率
? 第二次掃描構(gòu)建FP-Tree樹(shù)
?步驟：
? 掃描(計(jì)數(shù)城榛、去除不滿足最小支持度的項(xiàng)集）
? 重排
? 構(gòu)建FPTree
? 從下往上掃描項(xiàng)頭表揪利，構(gòu)建每一項(xiàng)的條件模式基并構(gòu)造條件FPTree
? 遞歸條件FPTree得到頻繁項(xiàng)
?優(yōu)點(diǎn)：
? 只需兩次掃描數(shù)據(jù)庫(kù)
?缺點(diǎn)：
? 內(nèi)存開(kāi)銷大
? 單維布爾關(guān)聯(lián)規(guī)則
