小伙伴們汽煮，繼續(xù)一起學(xué)習(xí)機(jī)器學(xué)習(xí)算法啦，今天學(xué)習(xí)關(guān)聯(lián)分析、Apriori算法啦逗物！大家肯定很熟悉一個故事-沃爾瑪超市數(shù)據(jù)總結(jié)出的啤酒與尿布的相關(guān)性（知乎上也有牛人們在討論這個故事的真假）
來自《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》這本書里提到的一個例子搬卒，展示了如下的一個購物清單：
在上述購物交易單中發(fā)現(xiàn)，{尿布翎卓，葡萄酒}出現(xiàn)的次數(shù)較多契邀，辣么，他們之間真的有木有關(guān)系呢失暴？這就需要關(guān)聯(lián)分析坯门。
關(guān)聯(lián)分析：在大規(guī)模數(shù)據(jù)集中尋找有趣關(guān)系的任務(wù)。這些關(guān)系可以有兩種形式：頻繁項(xiàng)集或者關(guān)聯(lián)規(guī)則逗扒。頻繁項(xiàng)集(frequent item sets)是指經(jīng)常出現(xiàn)在一起的物品的集合古戴，關(guān)聯(lián)關(guān)系(association rules)暗示兩種物品之間可能存在很強(qiáng)的關(guān)系。比如上面的{尿布矩肩，葡萄酒}就頻繁出現(xiàn)现恼，他們之間可能存在一些關(guān)系，辣么黍檩，如何來確定是否是頻繁項(xiàng)集呢叉袍？主要是依靠支持度和可信度。
一個項(xiàng)集的支持度(support)被定義為數(shù)據(jù)集中包含該項(xiàng)集的記錄所占的比例刽酱。比如喳逛，圖2中{豆奶}的支持度為4/5。支持度是針對項(xiàng)集來說的棵里，因此可以定義一個最小支持度润文，而只保留滿足最小支持度的項(xiàng)集。可信度或置信度(confidence)是針對一條諸如{尿布}->{葡萄酒}的關(guān)聯(lián)關(guān)系來定義的殿怜。這條規(guī)則的可信度被定義為“支持度({尿布典蝌，葡萄酒})/支持度({尿布})”
可是，如何計算一個集合中的頻繁項(xiàng)集的支持度稳捆，首先需要遍歷全部可能的項(xiàng)集赠法，比如針對一個包含了4個產(chǎn)品的集合麦轰，那么購買該集合產(chǎn)品的可能集合數(shù)目為2^4-1=15乔夯，而針對包含N項(xiàng)的集合，就需要遍歷2^N-1款侵。顯然末荐，這樣的計算量很大。因此新锈，出現(xiàn)了Apriori原理甲脏。
Apriori原理：如果某個項(xiàng)集是頻繁的，那么它的所有子集也是頻繁的。該定理的逆反定理為：如果某一個項(xiàng)集是非頻繁的块请，那么它的所有超集（包含該集合的集合）也是非頻繁的娜氏。Apriori原理的出現(xiàn)，可以在得知某些項(xiàng)集是非頻繁之后墩新，不需要計算該集合的超集贸弥，有效地避免項(xiàng)集數(shù)目的指數(shù)增長，從而在合理時間內(nèi)計算出頻繁項(xiàng)集海渊。
Apriori算法實(shí)現(xiàn)：Apriori算法是發(fā)現(xiàn)頻繁項(xiàng)集的一種方法绵疲。Apriori算法的兩個輸入?yún)?shù)分別是最小支持度和數(shù)據(jù)集。該算法首先會生成所有單個物品的項(xiàng)集列表->接著掃描交易記錄來查看哪些項(xiàng)集滿足最小支持度要求臣疑，其中不滿足最小支持度的集合會被去掉->然后對剩下的集合進(jìn)行組合以生成包含兩個數(shù)據(jù)集的項(xiàng)集->接著重新掃描交易記錄盔憨，去掉不滿足最小支持度的項(xiàng)集->該過程重復(fù)進(jìn)行直到所有項(xiàng)集都被濾掉。
Apriori算法Python編程
1）準(zhǔn)備數(shù)據(jù)
在圖2中提到的createC1()函數(shù)中的C1指的是最原始的待選項(xiàng)集讯沈，也就是所有單個物品的項(xiàng)集列表郁岩；為什么這里將C1轉(zhuǎn)換為frozenset，而不是一般額set呢缺狠，簡單解釋：
set無序排序且不重復(fù)驯用，是可變的，有add()儒老，remove()等方法蝴乔。既然是可變的，所以它不存在哈希值驮樊∞闭基本功能包括關(guān)系測試和消除重復(fù)元素. 集合對象還支持union(聯(lián)合), intersection(交集), difference(差集)和sysmmetric difference(對稱差集)等數(shù)學(xué)運(yùn)算。sets 支持 x in set, len(set),和 for x in set 囚衔。作為一個無序的集合挖腰，sets不記錄元素位置或者插入點(diǎn)。因此练湿，sets不支持 indexing, 或其它類序列的操作猴仑。
frozenset是凍結(jié)的集合，它是不可變的肥哎，存在哈希值辽俗，好處是它可以作為字典的key，也可以作為其它集合的元素篡诽。缺點(diǎn)是一旦創(chuàng)建便不能更改崖飘，沒有add，remove方法杈女。詳情見set與frozenset
2)過濾函數(shù)：根據(jù)待選項(xiàng)集Ck的情況朱浴，判斷數(shù)據(jù)集D中Ck元素的出現(xiàn)頻率吊圾，過濾掉低于最低支持度的項(xiàng)集。
3）當(dāng)待選項(xiàng)集不是單個元素時翰蠢，比如K>=2的情況下项乒，合并元素時容易出現(xiàn)出現(xiàn)重復(fù)，因此針對包含K個元素的頻繁項(xiàng)集梁沧，對比每個頻繁項(xiàng)集第K-2位是否一致板丽。詳情如下：
4）Apriori算法核心
基于上述算法，仿真得到趁尼，不同的最小支持度得到的頻繁項(xiàng)集是不同的埃碱。
當(dāng)minSupport=0.5時，得到的頻繁項(xiàng)集是：[[frozenset([1]), frozenset([3]), frozenset([2]), frozenset([5])], [frozenset([1, 3]), frozenset([2, 5]), frozenset([2, 3]), frozenset([3, 5])], [frozenset([2, 3, 5])], []]
當(dāng)minSupport=0.7時酥泞，得到的頻繁項(xiàng)集是：[[frozenset([3]), frozenset([2]), frozenset([5])], [frozenset([2, 5])], []]砚殿；
實(shí)際每個項(xiàng)集的支持度為：{frozenset([5]): 0.75, frozenset([3]): 0.75, frozenset([3, 5]): 0.5, frozenset([4]): 0.25, frozenset([2, 3]): 0.5, frozenset([2, 5]): 0.75, frozenset([1]): 0.5, frozenset([2]): 0.75}
基于Apriori算法，從頻繁項(xiàng)集挖掘關(guān)聯(lián)規(guī)則
基于Apriori算法可以獲得頻繁項(xiàng)芝囤，基于這些頻繁項(xiàng)集可以產(chǎn)生很多關(guān)聯(lián)規(guī)則似炎。如果能夠減少規(guī)則數(shù)目來確保問題的可解性，可以較大的減少計算復(fù)雜度悯姊。易知羡藐，如果某條規(guī)則不滿足最小可信度要求，那么該規(guī)則的所有子集也不會滿足最小可信度要求悯许。利用關(guān)聯(lián)規(guī)則的上述性質(zhì)仆嗦，基于Apriori算法，首先從一個頻繁項(xiàng)集開始先壕，接著創(chuàng)建一個規(guī)則列表瘩扼，其中規(guī)則右部只包含一個元素，垃僚，然后對這些規(guī)則進(jìn)行測試集绰。接下來合并所有的剩余規(guī)則列表來創(chuàng)建一個新的規(guī)則列表，其中規(guī)則右部包含兩個元素谆棺。這種方法稱作分級法栽燕。
好噠，關(guān)于Apriori算法的初步學(xué)習(xí)基本到這里改淑，希望對大家有用碍岔，歡迎大牛不吝賜教哈，各位朋友溅固，晚安付秕、早安啦~~
