Apriori算法：使用候選項(xiàng)找頻繁項(xiàng)集

Apriori算法是關(guān)聯(lián)分析中一種基本算法，用于挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集。原理：利用頻繁項(xiàng)集的先驗(yàn)知識(shí)，使用逐層搜索的迭代方法，使用k項(xiàng)集探索(k+1)項(xiàng)集。這里先看哈二維Apriori算法。（一般數(shù)據(jù)庫(kù)都是二維的嘛。。hehe）

Apriori性質(zhì)：頻繁項(xiàng)集的所有非空子集都必須也是頻繁的。（一種反單調(diào)性質(zhì)）

算法描述：
1、鏈接步：通過(guò)L<k-1>自連接產(chǎn)生候選k項(xiàng)集C<k>。
2、剪枝步：C<k>是L<k>的超集。利用Apriori性質(zhì)，如果一個(gè)k項(xiàng)集的(k-1)項(xiàng)集不在L<k-1>中，則該k項(xiàng)集從C<k>中刪除。（這種子集測(cè)試可以使用所有頻繁項(xiàng)集的散列樹(shù)快速完成）

上Pseudo Code：

Apriori
輸入：事務(wù)數(shù)據(jù)D；最小支持度閥值min_sup。
輸出：D中的頻繁項(xiàng)集L。

L<1>?=?find_frequent_1-itemset(D);
For?(k?=?2;?L<k-1>?!=?empty;?k++)?{
????C<k>?=?apriori_gen(L<k-1>,?min_sup);
????For?each?transaction?t?in?D?{
????????C<t>?=?subset(C<k>,?t);????//找出t中是候選集的所有C<k>的子集
????????For?each?candidate?c?in?C<t>
????????????c.count++;
????}
????L<k>?=?{c?in?C<k>?|?c.count?>=?min_sup}
}
Return?L?=?set?of?L<k>

Procedure?apriori_gen(L<k-1>,?min_sup)
????For?each?itemset?l1?in?L<k-1>
????????For?each?itemset?l2?in?L<k-1>
????????????If?(l1[i]?=?l2[1])?&&?(l1[2]?=?l2[2])?&&?…?&&?(l1[k-2]?=?l2[k-2])?&&?(l1[k-1]?<?l2[k-1])?then?{
????????????????c?=?l1?*?l2;????//union
????????????????if?has_infrequent_subset(c,?L<k-1>)?then
????????????????????delete?c;
????????????????else
????????????????????add?c?to?C<k>;
????????????}
????Return?C<k>;

Procedure?has_infrequent_subset(c,?L<k-1>)
????For?each?(k-1)-subset?s?of?c
????????If?s?not?in?L<k-1>?then
Return?TRUE;
????Return?FALSE;

---

由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則：??

Confidence(A => B) = P(A | B)
??? = support(AB) / support(B) = support_count(AB) / support_count(B)

對(duì)于前面Apriori找出的每個(gè)頻繁項(xiàng)集l，產(chǎn)生l的非空子集；（記得Apriori性質(zhì)哦)
對(duì)于每個(gè)非空子集s，如果 support_count(l) / support_count(s) >= min_conf，則輸出“s => (l – s)”（為什么用support_count(l)不用(l-s)？）

---

提高Apriori的有效性？數(shù)據(jù)結(jié)構(gòu)的改進(jìn)，掃描次數(shù)的降低等。??

1、散列項(xiàng)集計(jì)數(shù)，增加效率。
一個(gè)土一點(diǎn)的比喻：在Java里面用HashMap<Key, Val>來(lái)存。。還有種用trie樹(shù)的，等我補(bǔ)習(xí)過(guò)Algorithms in C++再說(shuō)。。

2、事務(wù)壓縮：不包含k項(xiàng)集的事務(wù)不可能包含(k+1)項(xiàng)集。這樣，可以給事務(wù)加刪除標(biāo)記，下次迭代不考慮之。

3、劃分（Er。。不是等價(jià)類(lèi)，是看程序設(shè)計(jì)的方便亂劃，比如一次能裝入內(nèi)存多少就劃多少）
兩次掃描。第一次，將D中事務(wù)劃分為n個(gè)非重疊部分，如果D中事務(wù)最小支持閥值為min_sup，則每個(gè)部分最小支持計(jì)數(shù)為(min_sup * 該部分事務(wù)數(shù))。對(duì)每一部分，找出局部頻繁項(xiàng)集。
局部頻繁項(xiàng)集可能不是整個(gè)數(shù)據(jù)庫(kù)D的頻繁項(xiàng)集，但D的任何頻繁項(xiàng)集必是局部頻繁項(xiàng)集（WHY？）。所有局部頻繁項(xiàng)集合并為全局候選項(xiàng)集。第二次掃描D，評(píng)估每個(gè)候選的實(shí)際支持度。

4、選樣：就是抽樣+檢測(cè)手段，以精度換速度。

5、動(dòng)態(tài)項(xiàng)集計(jì)數(shù)：不像Apriori僅在每次完整掃描前確定新的候選，現(xiàn)在在任何開(kāi)始點(diǎn)添加候選集。（編程怎么實(shí)現(xiàn)比較好？）

轉(zhuǎn)載于:https://www.cnblogs.com/dxz/archive/2007/04/05/dm_apriori_basics.html

總結(jié)

以上是生活随笔為你收集整理的DM入门之Apriori小结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。