關(guān)聯(lián)規(guī)則Apriori算法的示例分析

關(guān)聯(lián)規(guī)則Apriori算法的示例分析，針對這個問題，這篇文章詳細介紹了相對應(yīng)的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

關(guān)聯(lián)規(guī)則挖掘背景和基本概念

如下所示的數(shù)據(jù)集，表中的每一行代表一次購買清單，注意我們只關(guān)心記錄出現(xiàn)與否，不關(guān)心某條記錄購買了幾次，如購買十盒牛奶也只計一次。

數(shù)據(jù)記錄的所有項的集合稱為總項集，上表中的總項集：

S={牛奶,面包,尿布,啤酒,雞蛋,可樂}

關(guān)聯(lián)規(guī)則

就是有關(guān)聯(lián)的規(guī)則，形式是這樣定義的：兩個不相交的非空集合X、Y，如果有

X->Y，就說X-->Y是一條關(guān)聯(lián)規(guī)則，例如，{啤酒}-->{尿布}就是一條關(guān)聯(lián)規(guī)則。

關(guān)聯(lián)規(guī)則的強度用支持度(support)和自信度(confidence)來描述。

支持度

support(X-->Y) = 集合X與集合Y中的項在一條記錄中同時出現(xiàn)的次數(shù)  /   數(shù)據(jù)記錄的個數(shù)。例如：support({啤酒}-->{尿布}) = 啤酒和尿布同時出現(xiàn)的次數(shù) / 數(shù)據(jù)記錄數(shù) = 3/5=60%

自信度

confidence(X-->Y) =  集合X與集合Y中的項在一條記錄中同時出現(xiàn)的次數(shù)  /   集合X出現(xiàn)的個數(shù) 。例如：confidence({尿布}-->{啤酒}) = 啤酒和尿布同時出現(xiàn)的次數(shù) / 尿布出現(xiàn)的次數(shù) = 3/4 = 75%。

支持度和自信度越高，說明規(guī)則越強，關(guān)聯(lián)規(guī)則挖掘就是挖掘出滿足一定強度的規(guī)則。

關(guān)聯(lián)規(guī)則挖掘的之窮舉算法

關(guān)聯(lián)規(guī)則挖掘

給定一個交易數(shù)據(jù)集T，找出其中所有支持度 support >= min_support、自信度confidence >= min_confidence的關(guān)聯(lián)規(guī)則。

窮舉算法

找出所需要的規(guī)則就是窮舉項集的所有組合，并測試每個組合是否滿足條件，一個元素個數(shù)為n的項集所需要的時間復(fù)雜度為O(2^N)。上表的總項集 S={牛奶,面包,尿布,啤酒,雞蛋,可樂}，元素的個數(shù)為6，所有的組合個數(shù)為63 。

為了簡單起見，已知一個商品編號的總項集為：{1, 2, 3}，那么所有可能的組合為：

{1},{2}

{1},{3}

{2},{3}

{1},{2,3}

{2},{1,3}

{3},{1,2}

{1,2,3}

共有7項（2^3  - 1），分別檢查以上各種組合，在每一種組合上找出滿足支持度和自信度要求的關(guān)聯(lián)規(guī)則。

對于普通的超市，其商品的項集數(shù)也在1萬以上，用指數(shù)時間復(fù)雜度的算法不能在可接受的時間內(nèi)解決問題。

怎樣快速挖出滿足條件的關(guān)聯(lián)規(guī)則是關(guān)聯(lián)挖掘的需要解決的主要問題。

關(guān)聯(lián)規(guī)則挖掘優(yōu)化算法之Apriori算法

關(guān)聯(lián)規(guī)則挖掘分兩步進行：

　　1）生成頻繁項集

　　這一階段找出所有滿足最小支持度的項集，找出的這些項集稱為頻繁項集。

　　2）生成規(guī)則

　　在上一步產(chǎn)生的頻繁項集的基礎(chǔ)上生成滿足最小自信度的規(guī)則，產(chǎn)生的規(guī)則稱為強規(guī)則。

關(guān)聯(lián)規(guī)則挖掘所花費的時間主要是在第一步：生成頻繁項集上。因為找出的頻繁項集往往不會很多，所以2）相對1）耗時少。

為了減少 1）：頻繁項集的生成時間，應(yīng)該盡早的消除一些完全不可能是頻繁項集的集合，Apriori算法主要通過兩個規(guī)律減少頻繁項集。

兩個定律

1. 高級到低級。如果一個集合是頻繁項集，則它的所有子集都是頻繁項集。假設(shè)一個集合{A,B}是頻繁項集，則它的子集{A}, {B} 都是頻繁項集。

2. 低級到高級。如果一個集合不是頻繁項集，則它的所有超集都不是頻繁項集。假設(shè)集合{A}不是頻繁項集，則它的任何超集如{A,B}，{A,B,C}必定也不是頻繁項集。

具有實際應(yīng)用價值的還是第2條，從低級的頻繁項集到高級的頻繁項集的演化，試想，如果二級項集 {A,B}支持度都沒有大于閾值，即不是頻繁項集，三級{A,C,B}或更高級怎么可能是頻繁項集呢？如果是的話，{A,B}就一定是頻繁項集了，這不和原來的條件矛盾了嗎？

首先統(tǒng)計一級候選項集，清除不滿足條件的候選集，得到滿足條件的一級項集，在生成一級項集的基礎(chǔ)上，生成二級項集，得到滿足條件的二級項集，在生成三級項集時，再次根據(jù)定律2的思想，如，{牛奶,啤酒}不是頻繁項集，所以{牛奶，啤酒，尿布}，{牛奶，啤酒，面包}都不是頻繁項集。

Apriori算法

屬于候選消除算法，是一個根據(jù)定律2生成候選集、根據(jù)支持度和可信度的預(yù)置消除不滿足條件的候選集，并不斷循環(huán)直到不再產(chǎn)生候選集的過程。

算法的偽代碼：

public void Apriori() {

        // 獲取原始數(shù)據(jù)記錄

        record = getRecord(); 

         // 獲取第一次的候選集

        List<List<String>> candidateItemset = findFirstCandidate();

        // 獲取候選集candidateItemset 滿足支持的集合

        List<List<String>> lItemset = getSupportedItemset(candidateItemset ); 

         // 只要能繼續(xù)挖掘

        while (endTag != true) {

            // 獲取下一次的候選集

            List<List<String>> ckItemset = getNextCandidate(lItemset); 

            // 獲取候選集ckItemset 滿足支持的集合

            List<List<String>> lkItemset = getSupportedItemset(ckItemset); 

            //得到這一級別的頻繁項集

             save(IkItemset)

            // 保存數(shù)據(jù)，為下次迭代準(zhǔn)備

            lItemset = lkItemset;          

        }

總結(jié)了關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法Apriori算法，這個算法利用了一個定律：如果一個集合不是頻繁項集，則它的所有超集都不是頻繁項集，自下而上，挖掘出滿足支持度和可信度閾值的所有級別的頻繁項集。

關(guān)于關(guān)聯(lián)規(guī)則Apriori算法的示例分析問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識。