機(jī)器學(xué)習(xí)無疑是當(dāng)前數(shù)據(jù)分析領(lǐng)域的一個(gè)熱點(diǎn)內(nèi)容驻仅。很多人在平時(shí)的工作中都或多或少會(huì)用到機(jī)器學(xué)習(xí)的算法原茅。機(jī)器學(xué)習(xí)在學(xué)習(xí)方式上可分為監(jiān)督式學(xué)習(xí)揣非、半監(jiān)督式學(xué)習(xí)她渴、非監(jiān)督式學(xué)習(xí)和強(qiáng)化學(xué)習(xí)等
在非監(jiān)督式學(xué)習(xí)中达址，數(shù)據(jù)并不被特別標(biāo)識(shí)，學(xué)習(xí)模型是為了推斷出數(shù)據(jù)的一些內(nèi)在結(jié)構(gòu)趁耗。常見的應(yīng)用場(chǎng)景包括關(guān)聯(lián)規(guī)則的學(xué)習(xí)以及聚類等沉唠。常見算法包括Apriori算法以及k-Means算法。
關(guān)聯(lián)規(guī)則挖掘
關(guān)聯(lián)規(guī)則挖掘（Association rule mining）是數(shù)據(jù)挖掘中最活躍的研究方法之一苛败，可以用來發(fā)現(xiàn)事情之間的聯(lián)系满葛，最早是為了發(fā)現(xiàn)超市交易數(shù)據(jù)庫中不同的商品之間的關(guān)系。
這里有一則沃爾瑪超市的趣聞罢屈。沃爾瑪曾今對(duì)數(shù)據(jù)倉庫中
一年多的原始交易數(shù)據(jù)進(jìn)行了詳細(xì)的分析嘀韧，發(fā)現(xiàn)與尿布一起被購買最多的商品竟然是啤酒。借助數(shù)據(jù)倉庫和關(guān)聯(lián)規(guī)則缠捌，發(fā)現(xiàn)了這個(gè)隱藏在背后的事實(shí)：美國的婦女經(jīng)常會(huì)囑咐丈夫下班后為孩子買尿布锄贷，而30%~40%的丈夫在買完尿布之后又要順便購買自己愛喝的啤酒译蒂。根據(jù)這個(gè)發(fā)現(xiàn)，沃爾瑪調(diào)整了貨架的位置谊却，把尿布和啤酒放在一起銷售柔昼，大大增加了銷量。
這里借用一個(gè)引例來介紹關(guān)聯(lián)規(guī)則挖掘[1]炎辨。
定義一：項(xiàng)集
設(shè)I={i1,i2,…,im}捕透，是m個(gè)不同的項(xiàng)目的集合，每個(gè)ik稱為一個(gè)項(xiàng)目碴萧。項(xiàng)目的集合I稱為項(xiàng)集乙嘀。其元素的個(gè)數(shù)稱為項(xiàng)集的長度，長度為k的項(xiàng)集稱為k-項(xiàng)集破喻。引例中每個(gè)商品就是一個(gè)項(xiàng)目虎谢，項(xiàng)集為I={bread, beer, cake,cream, milk, tea}，I的長度為6低缩。
定義二
每筆交易T是項(xiàng)集I的一個(gè)子集嘉冒。對(duì)應(yīng)每一個(gè)交易有一個(gè)唯一標(biāo)識(shí)交易號(hào)，記作TID咆繁。交易全體構(gòu)成了交易數(shù)據(jù)庫D讳推，|D|等于D中交易的個(gè)數(shù)。引例中包含10筆交易玩般，因此|D|=10银觅。
定義三：支持度
對(duì)于項(xiàng)集X，設(shè)定count(X?T)為交易集D中包含X的交易的數(shù)量坏为，則項(xiàng)集X的支持度為：
support(X)=count(X?T)/|D|
引例中X={bread, milk}出現(xiàn)在T1究驴，T2，T5匀伏，T9和T10中洒忧，所以支持度為0.5。
定義四：最小支持度
最小支持度是項(xiàng)集的最小支持閥值够颠，記為SUPmin熙侍，代表了用戶關(guān)心的關(guān)聯(lián)規(guī)則的最低重要性。支持度不小于SUPmin 的項(xiàng)集稱為頻繁集履磨，長度為k的頻繁集稱為k-頻繁集蛉抓。如果設(shè)定SUPmin為0.3，引例中{bread, milk}的支持度是0.5剃诅，所以是2-頻繁集巷送。
定義五：
關(guān)聯(lián)規(guī)則是一個(gè)蘊(yùn)含式：
R：X?Y
其中X?I，Y?I矛辕，并且X∩Y=?笑跛。表示項(xiàng)集X在某一交易中出現(xiàn)付魔，則導(dǎo)致Y以某一概率也會(huì)出現(xiàn)。用戶關(guān)心的關(guān)聯(lián)規(guī)則堡牡，可以用兩個(gè)標(biāo)準(zhǔn)來衡量：支持度和可信度抒抬。
定義六
關(guān)聯(lián)規(guī)則R的支持度是交易集同時(shí)包含X和Y的交易數(shù)與|D|之比。即：
support(X?Y)=count(X?Y)/|D|
支持度反映了X晤柄、Y同時(shí)出現(xiàn)的概率。關(guān)聯(lián)規(guī)則的支持度等于頻繁集的支持度妖胀。
定義七：可信度
對(duì)于關(guān)聯(lián)規(guī)則R芥颈，可信度是指包含X和Y的交易數(shù)與包含X的交易數(shù)之比。即：
confidence(X?Y)=support(X?Y)/support(X)
可信度反映了如果交易中包含X赚抡，則交易包含Y的概率爬坑。一般來說，只有支持度和可信度較高的關(guān)聯(lián)規(guī)則才是用戶感興趣的涂臣。
定義八：強(qiáng)關(guān)聯(lián)規(guī)則
設(shè)定關(guān)聯(lián)規(guī)則的最小支持度和最小可信度為SUPmin和CONFmin盾计。規(guī)則R的支持度和可信度均不小于SUPmin和CONFmin ，則稱為強(qiáng)關(guān)聯(lián)規(guī)則赁遗。關(guān)聯(lián)規(guī)則挖掘的目的就是找出強(qiáng)關(guān)聯(lián)規(guī)則署辉，從而指導(dǎo)商家的決策。
這八個(gè)定義包含了關(guān)聯(lián)規(guī)則相關(guān)的幾個(gè)重要基本概念岩四，關(guān)聯(lián)規(guī)則挖掘主要有兩個(gè)問題：
1哭尝、找出交易數(shù)據(jù)庫中所有大于或等于用戶指定的最小支持度的頻繁項(xiàng)集。
2剖煌、利用頻繁項(xiàng)集生成所需要的關(guān)聯(lián)規(guī)則材鹦，根據(jù)用戶設(shè)定的最小可信度篩選出強(qiáng)關(guān)聯(lián)規(guī)則。
目前研究人員主要針對(duì)第一個(gè)問題進(jìn)行研究耕姊，找出頻繁集是比較困難的桶唐，而有了頻繁集再生成強(qiáng)關(guān)聯(lián)規(guī)則就相對(duì)容易了。
Apriori算法介紹
Apriori算法使用頻繁項(xiàng)集的先驗(yàn)知識(shí)茉兰，使用一種稱作逐層搜索的迭代方法尤泽，k項(xiàng)集用于探索(k+1)項(xiàng)集。首先邦邦，通過掃描事務(wù)（交易）記錄安吁，找出所有的頻繁1項(xiàng)集，該集合記做L1燃辖，然后利用L1找頻繁2項(xiàng)集的集合L2鬼店，L2找L3，如此下去黔龟，直到不能再找到任何頻繁k項(xiàng)集妇智。最后再在所有的頻繁集中找出強(qiáng)規(guī)則滥玷，即產(chǎn)生用戶感興趣的關(guān)聯(lián)規(guī)則。
其中巍棱，Apriori算法具有這樣一條性質(zhì)：任一頻繁項(xiàng)集的所有非空子集也必須是頻繁的惑畴。因?yàn)榧偃鏟(I)<最小支持度閾值，當(dāng)有元素A添加到I中時(shí)航徙，結(jié)果項(xiàng)集（A∩I）不可能比I出現(xiàn)次數(shù)更多如贷。因此A∩I也不是頻繁的。
連接步和剪枝步
在上述的關(guān)聯(lián)規(guī)則挖掘過程的兩個(gè)步驟中到踏，第一步往往是總體性能的瓶頸杠袱。Apriori算法采用連接步和剪枝步兩種方式來找出所有的頻繁項(xiàng)集。
