Apriori算法介紹PPT

1、Apriori算法最新研究進(jìn)展Apriori 算法背景1Apriori 算法基本思想2Apriori 算法的缺陷3Apriori 算法的改進(jìn)4關(guān)聯(lián)規(guī)則算法的發(fā)展5Apriori 算法代碼實(shí)現(xiàn)6目錄目錄CONTENTS改進(jìn)Apriori 算法在股票分析中的應(yīng)用研究7Apriori 算法背景01Apriori 算法背景自然界中的普遍性的形式就是規(guī)律 -馬克思”“Apriori 算法背景當(dāng)我們從普遍發(fā)生的事件中，找到其中的關(guān)聯(lián)和規(guī)律，那我們就能得到一些突破。在1993年， Agrawal 等人針對(duì)購(gòu)物籃問(wèn)題進(jìn)行分析提出了第一個(gè)關(guān)聯(lián)規(guī)則挖掘算法-Apriori算法，其目的是為了發(fā)現(xiàn)交易數(shù)據(jù)庫(kù)中不同商品

2、之間的聯(lián)系規(guī)則。這些規(guī)則刻畫(huà)了顧客購(gòu)買(mǎi)行為模式，可以用來(lái)指導(dǎo)商家科學(xué)地安排進(jìn)貨，庫(kù)存以及貨架設(shè)計(jì)等?！啊彼惴ǖ膽?yīng)用場(chǎng)景01Apriori 算法背景算法背景Apriori 算法背景算法背景舉一個(gè)例子02Apriori 算法背景算法背景下面這個(gè)表格是代表一個(gè)事務(wù)數(shù)據(jù)庫(kù)D，其中最小支持度為50%，最小置信度為70%，求事務(wù)數(shù)據(jù)庫(kù)中的頻繁關(guān)聯(lián)規(guī)則。Apriori 算法背景算法背景（1）生成候選項(xiàng)目集C1=面包，牛奶，啤酒，花生，尿布。 求解步驟如下：Apriori 算法背景算法背景C1=面包，牛奶，啤酒，花生，尿布(2)掃描事務(wù)數(shù)據(jù)庫(kù)D，計(jì)算C1中每個(gè)項(xiàng)目集在D中的支持度。從事務(wù)數(shù)據(jù)庫(kù)D中可以得出每個(gè)

3、項(xiàng)目集的支持?jǐn)?shù)分別為3,3,3,1,2，事務(wù)數(shù)據(jù)庫(kù)D的項(xiàng)目集總數(shù)為4，因此可得出C1中每個(gè)項(xiàng)目集的支持度分別為75%，75%，75%，25%，50%。根據(jù)最小支持度為50%，可以得出頻繁項(xiàng)目集L1=面包，牛奶，啤酒，尿布。Apriori 算法背景算法背景L1=面包，牛奶，啤酒，尿布(3)根據(jù)L1自連接L1 L1生成候選項(xiàng)目集C2=面包，牛奶，面包，啤酒，面包，尿布，牛奶，啤酒，牛奶，尿布，啤酒，尿布。Apriori 算法背景算法背景 C2=面包，牛奶，面包，啤酒，面包，尿布，牛奶，啤酒，牛奶，尿布，啤酒，尿布(4)掃描事務(wù)數(shù)據(jù)庫(kù)D，計(jì)算C2中每個(gè)項(xiàng)目集在D中的支持度。從事務(wù)數(shù)據(jù)庫(kù)D中可以得出每

4、個(gè)項(xiàng)目集的支持?jǐn)?shù)分別為3,2,1,2,1,2，事務(wù)數(shù)據(jù)庫(kù)D的項(xiàng)目集總數(shù)為4，因此可得出C2中每個(gè)項(xiàng)目集的支持度分別為75%，50%，25%，50%，25%，50%。根據(jù)最小支持度為50%，可以得出頻繁項(xiàng)目集L2=面包，牛奶，面包，啤酒，牛奶，啤酒，啤酒，尿布。Apriori 算法背景算法背景 L2=面包，牛奶，面包，啤酒，牛奶，啤酒，啤酒，尿布(5)根據(jù)L2 L2生成候選項(xiàng)目集C3=面包，牛奶，啤酒，面包，啤酒，尿布，牛奶，啤酒，尿布，由于C3中項(xiàng)目集面包，啤酒，尿布中的一個(gè)子集面包，尿布是L2中不存在的，因此可以去除。同理項(xiàng)目集牛奶，啤酒，尿布也可去除。因此C3=面包，牛奶，啤酒。Aprio

5、ri 算法背景算法背景 C3=面包，牛奶，啤酒(6)掃描事務(wù)數(shù)據(jù)庫(kù)D，計(jì)算C3中每個(gè)項(xiàng)目集在D中的支持度。從事務(wù)數(shù)據(jù)庫(kù)D中可以得出每個(gè)項(xiàng)目集的支持?jǐn)?shù)分別為2，事務(wù)數(shù)據(jù)庫(kù)D的項(xiàng)目集總數(shù)為4，因此可得出C2中每個(gè)項(xiàng)目集的支持度分別為50%。根據(jù)最小支持度為50%，可以得出頻繁項(xiàng)目集L3=面包，牛奶，啤酒。Apriori 算法背景算法背景 (7)L=L1UL2UL3=面包，牛奶，啤酒，尿布，面包，牛奶，面包，啤酒，牛奶，啤酒，啤酒，尿布，面包，牛奶，啤酒。Apriori 算法背景算法背景 (8)我們只考慮項(xiàng)目集長(zhǎng)度大于1的項(xiàng)目集，例如面包，牛奶，啤酒，它的所有非真子集面包，牛奶，啤酒，面包，牛奶，面

6、包，啤酒，牛奶，啤酒，分別計(jì)算關(guān)聯(lián)規(guī)則面包牛奶，啤酒，牛奶面包，啤酒，啤酒面包，牛奶，面包，牛奶啤酒，面包，啤酒牛奶，牛奶，啤酒面包的置信度，其值分別為67%，67%，67%，67%，100%，100%。由于最小置信度為70%，可得，面包，啤酒牛奶，牛奶，啤酒面包為頻繁關(guān)聯(lián)規(guī)則。也就是說(shuō)買(mǎi)面包和啤酒的同時(shí)肯定會(huì)買(mǎi)牛奶，買(mǎi)牛奶和啤酒的同時(shí)也是會(huì)買(mǎi)面包。關(guān)聯(lián)規(guī)則定義：給定一組事務(wù)，尋找預(yù)測(cè)“某些項(xiàng)將會(huì)隨其他項(xiàng)的出現(xiàn)而出現(xiàn)”的規(guī)則。例如： 面包，啤酒牛奶注：蘊(yùn)含符號(hào)“”表現(xiàn)共現(xiàn)關(guān)系，而不是因果關(guān)系算法的基本概念03Apriori 算法背景算法背景 項(xiàng) 集K-項(xiàng)集 一個(gè)或多個(gè)項(xiàng)的集合例如：面包、面包、

7、啤酒 包含K個(gè)項(xiàng)的項(xiàng)集例如： C1=面包，牛奶，啤酒，花生，尿布就是一個(gè)5-項(xiàng)集Apriori 算法背景算法背景候選項(xiàng)集頻繁項(xiàng)集用來(lái)獲取頻繁項(xiàng)集的候選項(xiàng)集，候選項(xiàng)集中滿足支持度條件的項(xiàng)集保留，不滿足條件的舍棄。在所有訓(xùn)練元組中同時(shí)出現(xiàn)的次數(shù)超過(guò)人工定義的閾值的項(xiàng)集（支持度=最小支持度的集合）。Apriori 算法背景算法背景候選項(xiàng)集： 例如：C1=面包，牛奶，啤酒，花生，尿布頻繁項(xiàng)集： 例如：根據(jù)最小支持度為50%，從C1可以得出頻繁項(xiàng)目集L1=面包，牛奶，啤酒，尿布。Apriori 算法背景算法背景頻繁項(xiàng)集基本原則1.任意一個(gè)頻繁項(xiàng)集，它所有的非空子集都必須是頻繁的。2.如果一個(gè)項(xiàng)集是不頻繁

8、的，那他的超集一定是不頻繁的。Apriori 算法背景算法背景規(guī)則評(píng)估標(biāo)準(zhǔn)規(guī)則評(píng)估標(biāo)準(zhǔn)支持度、置信度支持度、置信度支持度（support）：關(guān)聯(lián)數(shù)據(jù)在數(shù)據(jù)集中出現(xiàn)的次數(shù)或所占的比重。置信度（confidence）：置信度表示Y數(shù)據(jù)出現(xiàn)后，X數(shù)據(jù)出現(xiàn)的可能性，也可以說(shuō)是數(shù)據(jù)的條件概率。Apriori 算法背景算法背景 強(qiáng)關(guān)聯(lián)規(guī)則強(qiáng)關(guān)聯(lián)規(guī)則：滿足最小支持度和最小置信度的關(guān)聯(lián)規(guī)則。舉例舉例Apriori 算法背景算法背景Apriori 算法背景算法背景買(mǎi) 咖 啡不 買(mǎi) 咖 啡合 計(jì)買(mǎi)牛奶20525不買(mǎi)牛奶70575合計(jì)9010100設(shè)定minsup = 0.2，minconf = 0.6，按照現(xiàn)有的

9、挖掘算法可得到關(guān)聯(lián)規(guī)則：規(guī)則一：買(mǎi)牛奶 買(mǎi)咖啡 s = 20/100 = 0.2 c = 20/25 = 0.8 80%的人買(mǎi)了牛奶就會(huì)買(mǎi)咖啡，但是90%的人肯定會(huì)買(mǎi)咖啡，即買(mǎi)牛奶對(duì)買(mǎi)咖啡這件事的刺激作用并沒(méi)有想象中的大規(guī)則二：買(mǎi)咖啡 不買(mǎi)牛奶 s = 70/100 = 0.7 c = 70/90 = 0.78 可以看出規(guī)則二更具有商業(yè)銷(xiāo)售的指導(dǎo)意義關(guān)聯(lián)規(guī)則的興趣度04Apriori 算法背景算法背景從上例可知，之前的挖掘算法只能挖掘出類(lèi)似于規(guī)則一的規(guī)則，而對(duì)于類(lèi)似規(guī)則二的帶有類(lèi)似于“不買(mǎi)牛奶”之類(lèi)的負(fù)屬性項(xiàng)的規(guī)則卻無(wú)能為力，而這種知識(shí)往往具有更重要的價(jià)值。所以對(duì)于不購(gòu)買(mǎi)商品的事務(wù)與購(gòu)買(mǎi)商品的

10、事務(wù)的關(guān)系的研究，引入興趣度：興趣度的使用：一條規(guī)則的興趣度越大于1，則其實(shí)際利用價(jià)值越大 一條規(guī)則的興趣度越小于1，則其反面規(guī)則的實(shí)際利用價(jià)值越大Apriori 算法背景算法背景RulesSCI1買(mǎi)牛奶買(mǎi)咖啡0.20.80.892買(mǎi)咖啡買(mǎi)牛奶0.20.220.893買(mǎi)牛奶不買(mǎi)咖啡0.050.224不買(mǎi)咖啡買(mǎi)牛奶0.050.525不買(mǎi)牛奶買(mǎi)咖啡0.70.931.0376買(mǎi)咖啡不買(mǎi)牛奶0.70.781.0377不買(mǎi)牛奶不買(mǎi)咖啡0.050.0670.678不買(mǎi)咖啡不買(mǎi)牛奶0.050.20.87基于咖啡和牛奶的例子，列出所有可能的規(guī)則描述及其對(duì)應(yīng)的支持度、可信度和興趣度：在此只考慮第1、2、3、6四

11、條規(guī)則，由于I1， I21，因此在實(shí)際中它的價(jià)值不大， I3， I61都可以列入進(jìn)一步考慮的范圍Apriori 算法背景算法背景上述興趣度的公式可以等價(jià)于：有人也稱(chēng)上述公式為作用度（Lift），表示關(guān)聯(lián)規(guī)則AB的“提升”，所以I（AB）也被稱(chēng)為提升度。如果作用度不大于1，則此關(guān)聯(lián)規(guī)則就沒(méi)有意義可信度：是對(duì)關(guān)聯(lián)規(guī)則準(zhǔn)確度的衡量 興趣度：是項(xiàng)集A對(duì)項(xiàng)集B的影響力的大小的衡量 支持度：是對(duì)關(guān)聯(lián)規(guī)則重要性的衡量 興趣度越大，說(shuō)明項(xiàng)集B 受項(xiàng)集A的影響越大Apriori 算法基本思想02關(guān)于Apriori算法1，Apriori算法是Agrawal和R.Snikant于1994年提出的，為布爾關(guān)聯(lián)規(guī)則挖掘

12、頻繁項(xiàng)集的原創(chuàng)性算法。2，Apriori算法的思想正如其名字那樣，使用頻繁項(xiàng)集的先驗(yàn)知識(shí)，使用的是一種稱(chēng)為逐層搜索的迭代方法，運(yùn)用k-項(xiàng)集來(lái)生成k+1項(xiàng)集?！薄八惴ǖ幕舅枷胪ㄟ^(guò)掃描數(shù)據(jù)庫(kù)，累計(jì)每個(gè)項(xiàng)的計(jì)數(shù)，并收集滿足最小支持度的項(xiàng)，找出頻繁1項(xiàng)集的集合。記該集合為L(zhǎng)1.然后，使用L1找出頻繁2項(xiàng)集的集合L2，使用L2找出L3，如此類(lèi)推，直到不能再找到頻繁k項(xiàng)集為止。為了提高頻繁項(xiàng)集逐層產(chǎn)生的效率，一種稱(chēng)為先驗(yàn)性質(zhì)的重要性質(zhì)用于壓縮搜素空間。”“”“先驗(yàn)性質(zhì)先驗(yàn)性質(zhì)1，先驗(yàn)性質(zhì)：頻繁項(xiàng)集的所有非空子集也一定是頻繁的。2，該性質(zhì)表明，如果項(xiàng)集B不滿足最小閾值min-sup，則B不是頻繁的，即P(

13、B)min-sup。如果項(xiàng)A添加到B，則結(jié)果項(xiàng)集（即BA）不可能比B更頻繁的出現(xiàn)。因此BA也不是頻繁的，即P（BA）min-sup連接步01剪枝步02如何進(jìn)行迭代如何進(jìn)行迭代連接步連接步連接步 為找出Lk，通過(guò)將Lk-1 與自身連接產(chǎn)生候選k項(xiàng)集的集合。該候選項(xiàng)集的集合記為Ck。設(shè)l1和l2是Lk-1中的項(xiàng)集。記號(hào)l1j表示l1的第j項(xiàng)(例如，l1k-2表示l1的倒數(shù)第2項(xiàng))。為了有效地實(shí)現(xiàn)，Apriori算法假定事務(wù)或項(xiàng)集中的項(xiàng)按字典序排序。對(duì)于(k-1)項(xiàng)集li，這意味把項(xiàng)排序，使得li1li2 lik-1。執(zhí)行連接Lk-1XLk-1;其中Lk-1的元素是可連接的，如果它們前(k-2)個(gè)項(xiàng)

14、相同。即，Lk-1的元素l1和l2是可連接的，如果(I11=l21)(l12 =l22) (l1k-2=l2k-2)(l1k-1l2k-1)。條件(I1k-1l2k-1)是簡(jiǎn)單地確保不產(chǎn)生重復(fù)。連接l1 和l2產(chǎn)生的結(jié)果項(xiàng)集是l11， l22， ，l1k-1，l2k-1。剪枝步剪枝步剪枝步 Ck是Lk的超集，也就是說(shuō)，Ck的成員可以是也可以不是頻繁的，但所有的頻繁k項(xiàng)集都包含在Ck中。掃描數(shù)據(jù)庫(kù)，確定Ck中每個(gè)候選的計(jì)數(shù)，從而確定Lk (即根據(jù)定義，計(jì)數(shù)值不小于最小支持度計(jì)數(shù)的所有候選都是頻繁的，從而屬于Lk)。然而，Ck可能很大，因此所涉及的計(jì)算量就很大。為了壓縮Ck，可以用以下辦法使用先驗(yàn)

15、性質(zhì)。任何非頻繁的(k-1)項(xiàng)集都不是頻繁k項(xiàng)集的子集。因此，如果一個(gè)候選k項(xiàng)集的(k-1)項(xiàng)子集不在Lk-1中，則該候選也不可能是頻繁的，從而可以從Ck中刪除。這種子集測(cè)試可以使用所有頻繁項(xiàng)集的散列樹(shù)快速完成。Apriori算法實(shí)例算法實(shí)例TID商品商品ID列表列表T1I1I2I5T2I2I4T3I2I3T4I1I2I4T5I1I3T6I2I3T7I1I3T8I1I2I3I5T9I1I2I3該例子基于某超市的事物數(shù)據(jù)庫(kù)，該數(shù)據(jù)庫(kù)共有9個(gè)事物項(xiàng)集第一次迭代第一次迭代第一次迭代，生成備選項(xiàng)集C1，并計(jì)算支持?jǐn)?shù) ，滿足最小支持度的項(xiàng)生成項(xiàng)集L1，設(shè)最小支持度計(jì)數(shù)=2，即min-sup = 2。項(xiàng)集

16、項(xiàng)集支持度計(jì)數(shù)支持度計(jì)數(shù)I16I27I36I42I53項(xiàng)集項(xiàng)集支持度計(jì)數(shù)支持度計(jì)數(shù)I16I27I36I42I53篩選滿足min-sup的項(xiàng)C1L1第二次迭代第二次迭代項(xiàng)集項(xiàng)集支持度計(jì)數(shù)支持度計(jì)數(shù)I1，I24I1，I34I1，I41I1，I52I2，I34I2，I42I2，I52I3，I40I3，I51I4，I50項(xiàng)集項(xiàng)集支持度計(jì)數(shù)支持度計(jì)數(shù)I1，I24I1，I34I1，I52I2，I34I2，I42I2，I52第二次迭代，鏈接L1和L1，生成備選集合C2，并篩選出L2篩選符合最小支持度的項(xiàng)C2L2第三次迭代第三次迭代第三次迭代項(xiàng)集項(xiàng)集支持度計(jì)數(shù)支持度計(jì)數(shù)I1，I24I1，I34I1，I52I2

17、，I34I2，I42I2，I52項(xiàng)集項(xiàng)集支持度計(jì)數(shù)支持度計(jì)數(shù)I1，I2，I32I1，I2，I52由L2生成C3，篩選發(fā)現(xiàn)C3即L3L2C3L3第四次迭代第四次迭代連接L3，L3，盡管可以生成集合C4I1，I2，I3，I5，但是這個(gè)項(xiàng)集的子集I2,I3,I5不是頻繁的，所以C4為空集，算法終止。項(xiàng)集項(xiàng)集支持度計(jì)數(shù)支持度計(jì)數(shù)I1，I2，I32I1，I2，I52項(xiàng)集項(xiàng)集支持度支持度I1，I2，I3，I51L3C3C4連接篩選總的流程總的流程Apriori 算法代碼實(shí)現(xiàn)(一)03算法代碼實(shí)現(xiàn)流程算法代碼實(shí)現(xiàn)流程1 根據(jù)輸入數(shù)據(jù)生成一項(xiàng)集2 計(jì)算一項(xiàng)集中項(xiàng)的支持度（ScanD()函數(shù)），去除支持度不滿足

18、要求的項(xiàng)3 將一項(xiàng)集中滿足支持度的項(xiàng)進(jìn)行組合（apriori()函數(shù)），生成二項(xiàng)集4 計(jì)算二項(xiàng)集中項(xiàng)的支持度（ScanD()函數(shù)），去除支持度不滿足要求的項(xiàng)5 將二項(xiàng)集中滿足支持度的項(xiàng)進(jìn)行組合（apriori()函數(shù)），生成三項(xiàng)集按照以上流程遞歸操作生成項(xiàng)集, 當(dāng)某一項(xiàng)集為空時(shí)結(jié)束主體函數(shù)主體函數(shù)該函數(shù)接收兩個(gè)參數(shù)：原始數(shù)據(jù)原始，最小支持度該函數(shù)作用如下：將原始數(shù)據(jù)輸入createC1()函數(shù)，生成一項(xiàng)集C1，將一項(xiàng)集輸入scanD()函數(shù)，生成最初的支持度字典supportData，頻繁項(xiàng)集的集合L；在遞歸循環(huán)中，不斷生成新的頻繁項(xiàng)集和支持度數(shù)據(jù)，進(jìn)行L和supportData數(shù)據(jù)的更新，最

19、終當(dāng)某一項(xiàng)集為空則跳出循環(huán)；最終返回所有的頻繁項(xiàng)集和支持度support處理輸入數(shù)據(jù)處理輸入數(shù)據(jù)規(guī)定初始數(shù)據(jù)中，每一個(gè)事務(wù)由一個(gè)List結(jié)構(gòu)表示，事務(wù)中的項(xiàng)目為L(zhǎng)ist中元素，所有事務(wù)List構(gòu)成整體數(shù)據(jù)的LIst（二維）該函數(shù)接收一個(gè)參數(shù)：原始數(shù)據(jù)，該函數(shù)作用如下：進(jìn)行遍歷，使用Python編程技巧進(jìn)行去重和排序，最后生成一項(xiàng)集，防止后期因?yàn)槟承┰蛐薷牡綌?shù)據(jù)，將數(shù)據(jù)進(jìn)行frozenset操作，將每個(gè)元素生成一個(gè)Set結(jié)構(gòu)。返回的List就是數(shù)據(jù)的一項(xiàng)集生成頻繁項(xiàng)集生成頻繁項(xiàng)集該函數(shù)接收三個(gè)參數(shù)：原始數(shù)據(jù)，項(xiàng)集List，最小支持度該函數(shù)作用如下：定義一個(gè)空dict用于存放項(xiàng)集頻數(shù)，對(duì)于原始數(shù)

20、據(jù)和傳入項(xiàng)集List進(jìn)行遍歷，得到每個(gè)項(xiàng)集在原始數(shù)據(jù)中出現(xiàn)的頻數(shù)，以dict的形式進(jìn)行存儲(chǔ)遍歷頻數(shù)dict，計(jì)算支持度，supportData記錄每項(xiàng)的支持度，在滿足支持度的項(xiàng)插入retList返回最終的頻繁項(xiàng)集reList，和支持度字典supportData生成新項(xiàng)集生成新項(xiàng)集該函數(shù)接收兩個(gè)參數(shù)：上一項(xiàng)集的頻繁項(xiàng)集，項(xiàng)集index該函數(shù)作用如下：當(dāng)一項(xiàng)集的頻繁項(xiàng)集生成后，利用該頻繁項(xiàng)集生成二項(xiàng)集；當(dāng)二項(xiàng)集的頻繁項(xiàng)集生成后，利用該頻繁項(xiàng)集生成三項(xiàng)集，以此類(lèi)推能夠生成所有項(xiàng)集測(cè)試結(jié)果測(cè)試結(jié)果Apriori 算法代碼實(shí)現(xiàn)03Apriori中的輔助函數(shù)Apriori算法首先構(gòu)建集合 C1 ,然后掃描

21、數(shù)據(jù)集判斷這些只有一個(gè)元素的項(xiàng)集是否滿足最小支持度的要求。那些滿足最低要求的項(xiàng)集構(gòu)成集合 L1 。而 L1 中的元素相互組合構(gòu)成 C2 , C2 再進(jìn)一步過(guò)濾變?yōu)?L2 。組織完整的Apriori算法舉例來(lái)說(shuō),aprioriGen函數(shù)以0、1、2作為輸入,會(huì)生成0,1、0,2以及1,2。要完成這一點(diǎn),首先創(chuàng)建一個(gè)空列表,然后計(jì)算 Lk 中的元素?cái)?shù)目。通過(guò)循環(huán)來(lái)比較 Lk 中的每一個(gè)元素與其他元素，緊接著,取列表中 apriori函數(shù)首先創(chuàng)建 C1 然后讀入數(shù)據(jù)集將其轉(zhuǎn)化為 D (集合列表)來(lái)完成。scanD() 函數(shù)來(lái)創(chuàng)建 L1 ,并將 L1 放入列表 L 中。后面會(huì)繼續(xù)找 L2 , L3 測(cè)

22、試測(cè)試上述4個(gè)項(xiàng)集構(gòu)成了 L1 列表,該列表中的每個(gè)單項(xiàng)集至少出現(xiàn)在50%以上的記錄中。由于4并沒(méi)有達(dá)到最小支持度,所以沒(méi)有包含在 L1 中。通過(guò)去掉該數(shù),減少了查找兩個(gè)元素項(xiàng)集的工作量。測(cè)試測(cè)試L包含滿足最小支持度為0.5的頻繁項(xiàng)集列表L0,L1,L2是其中元素個(gè)數(shù)分別為1，2，3的頻繁項(xiàng)集從頻繁項(xiàng)集中挖掘關(guān)聯(lián)規(guī)則從頻繁項(xiàng)集中挖掘關(guān)聯(lián)規(guī)則函數(shù)generateRules()是主函數(shù)，它調(diào)用rulesFromConseq()函數(shù)和calcConf()函數(shù)，分別用于生成候選規(guī)則集合以及對(duì)規(guī)則進(jìn)行評(píng)估。rulesFromConseq()函數(shù)可以從最初的項(xiàng)集中生成更多的關(guān)聯(lián)規(guī)則，它的參數(shù)一個(gè)是頻繁項(xiàng)集

23、,另一個(gè)是可以出現(xiàn)在規(guī)則右部的元素列表 H。測(cè)試測(cè)試分別對(duì)0.7和0.5的可信度閾值進(jìn)行了測(cè)試。在數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)在數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)毒蘑菇數(shù)據(jù)集，包括8124個(gè)數(shù)據(jù)，每個(gè)數(shù)據(jù)有23個(gè)特征，包括毒性，顏色，形狀等。測(cè)試測(cè)試發(fā)現(xiàn)數(shù)據(jù)集中的頻繁項(xiàng)集及關(guān)聯(lián)規(guī)則，可以找出哪種蘑菇更可能具有毒性首先測(cè)試得出了數(shù)據(jù)集中所有滿足最小支持度為0.3的頻繁項(xiàng)集測(cè)試測(cè)試之后需要從頻繁項(xiàng)集中找出包含毒性特征為2的集合，并且找出其中的關(guān)聯(lián)規(guī)則Apriori 算法的缺陷04AprioriApriori主要有兩個(gè)缺陷：主要有兩個(gè)缺陷：(1) 在每一步產(chǎn)生侯選項(xiàng)目集時(shí)循環(huán)產(chǎn)生的組合過(guò)多，沒(méi)有排除不應(yīng)該參與組合的元素;(2)每

24、次計(jì)算項(xiàng)集的支持度時(shí)，都對(duì)數(shù)據(jù)庫(kù)中的全部記錄進(jìn)行了一遍掃描比較，如果是一個(gè)大型的數(shù)據(jù)庫(kù)的話，這種掃描比較會(huì)大大增加計(jì)算機(jī)系統(tǒng)的I/O開(kāi)銷(xiāo)。而這種代價(jià)是隨著數(shù)據(jù)庫(kù)的記錄的增加呈現(xiàn)出幾何級(jí)數(shù)的增加。因此人們開(kāi)始尋求更好性能的算法。Apriori 算法的改進(jìn)05基于hash表的項(xiàng)集計(jì)數(shù)1改進(jìn)改進(jìn)Apriori 算法的方法算法的方法將每個(gè)項(xiàng)集通過(guò)相應(yīng)的hash函數(shù)映射到hash表中的不同的桶中這樣可以通過(guò)將桶中的項(xiàng)集計(jì)數(shù)跟最小支持計(jì)數(shù)相比較先淘汰一部分項(xiàng)集事物壓縮2改進(jìn)改進(jìn)Apriori 算法的方法算法的方法壓縮進(jìn)一步迭代的事物數(shù)不包含任何k-項(xiàng)集的事物不可能包含任何（k+1）-項(xiàng)集，這種食物在下一步

25、的計(jì)算中可以加上標(biāo)記或刪除劃分3改進(jìn)改進(jìn)Apriori 算法的方法算法的方法挖掘頻繁項(xiàng)集只需要兩次數(shù)據(jù)掃描第一次掃描：將數(shù)據(jù)劃分為多個(gè)部分并找到局部頻繁項(xiàng)集第二次掃描：評(píng)估每個(gè)候選項(xiàng)集的實(shí)際支持度，以確定全局頻繁項(xiàng)集選樣4改進(jìn)改進(jìn)Apriori 算法的方法算法的方法在給定數(shù)據(jù)的一個(gè)子集挖掘基本思想：選擇原始數(shù)據(jù)的一個(gè)樣本，在這個(gè)樣本上用Apriori算法來(lái)挖掘頻繁模式通過(guò)犧牲精確度來(lái)減少算法開(kāi)銷(xiāo)，為了提高效率，樣本大小應(yīng)該以可以放在內(nèi)存中為宜，可以適當(dāng)降低最小支持度來(lái)減少遺漏的頻繁模式可以通過(guò)一次全局掃描來(lái)驗(yàn)證從樣本中發(fā)現(xiàn)的模式可以通過(guò)第二次全局掃描來(lái)找到遺漏的模式動(dòng)態(tài)項(xiàng)集計(jì)數(shù)5改進(jìn)改進(jìn)Apr

26、iori 算法的方法算法的方法在掃描的不同點(diǎn)添加候選項(xiàng)集如果一個(gè)候選項(xiàng)集已經(jīng)滿足最少支持度，則在可以直接將它添加到頻繁項(xiàng)集，而不必在這次掃描的以后對(duì)比中繼續(xù)計(jì)算一種一種Apriori的改進(jìn)算法的改進(jìn)算法第一步：簡(jiǎn)單統(tǒng)計(jì)所有含一個(gè)元素的項(xiàng)目出現(xiàn)的頻率，并找出那些大于或等于最小支持度的項(xiàng)目集，產(chǎn)生一維頻繁項(xiàng)目集Lt第二步：循環(huán)處理直到未能再產(chǎn)生維數(shù)更高的頻繁項(xiàng)目集循環(huán)過(guò)程是：在第k步中，根據(jù)k-1步生成的k-1維頻繁項(xiàng)目集來(lái)產(chǎn)生k維候選項(xiàng)目集，由于在產(chǎn)生k-1維頻繁項(xiàng)目集時(shí)，我們可以實(shí)現(xiàn)對(duì)該集中出現(xiàn)元素的個(gè)數(shù)進(jìn)行計(jì)數(shù)處理，因此對(duì)某元素而言，若它的計(jì)數(shù)個(gè)數(shù)不到k-1的話，可以實(shí)現(xiàn)刪除該元素，從而排除

27、由該元素將引起的大規(guī)模的所有組合。第三步：按Apriori算法再檢驗(yàn)新的K維頻繁項(xiàng)目集的所有k-1維項(xiàng)目集是否己經(jīng)包含在己經(jīng)求出的K一1維頻繁項(xiàng)目集。若其中有一個(gè)沒(méi)有包含，則也可刪去該組合，這樣得到一個(gè)真正有用的K維頻繁項(xiàng)目集選項(xiàng)目集。第四步：得到了這個(gè)候選項(xiàng)目集后，可以對(duì)數(shù)據(jù)庫(kù)D的每一個(gè)事務(wù)tid進(jìn)行掃描，若該事務(wù)中至少含有候選項(xiàng)目集CK中的一員，則保留該項(xiàng)事務(wù)，否則把該事物記錄與數(shù)據(jù)庫(kù)末端沒(méi)有作刪除標(biāo)記的事務(wù)記錄對(duì)換，并對(duì)移到數(shù)據(jù)庫(kù)末端的事務(wù)記錄作刪除標(biāo)一記，整個(gè)數(shù)據(jù)庫(kù)掃描完畢后為新的事務(wù)數(shù)據(jù)庫(kù)D中。改進(jìn)改進(jìn)算法的評(píng)價(jià)算法的評(píng)價(jià)我們可以看到本算法的思路基本上與Apriori算法保持一致，但

28、是又有不同之處。第一，改進(jìn)的算法在考慮組合Ck前，對(duì)將參與組合的元素進(jìn)行計(jì)數(shù)處理，根據(jù)計(jì)數(shù)結(jié)果決定排除一些不符合組合條件的元素，這就降低了組合的可能性，即降低循環(huán)判斷的次數(shù)。第二，改進(jìn)的算法對(duì)數(shù)據(jù)庫(kù)進(jìn)行了掃描后的重新生成，雖然會(huì)在記錄重寫(xiě)中浪費(fèi)時(shí)間和I/O的開(kāi)銷(xiāo)，但是隨著循環(huán)次數(shù)的增加，本算法對(duì)以后在新生成的數(shù)據(jù)庫(kù)中的掃描比較次數(shù)很快減少將逐漸體現(xiàn)出來(lái)。關(guān)聯(lián)規(guī)則算法的發(fā)展06FP-growth的使用背景1FP-growth算法的基本原理2FP-growth算法的具體代碼實(shí)現(xiàn)3生活中常見(jiàn)的頻繁項(xiàng)集合頻繁項(xiàng)集對(duì)搜索引擎通過(guò)分析經(jīng)常出現(xiàn)的詞對(duì)自動(dòng)補(bǔ)全查詢?cè)~項(xiàng)FP-growth算法在數(shù)據(jù)量很大時(shí)發(fā)現(xiàn)頻

29、繁項(xiàng)集更為高效AprioriFP-growth數(shù)據(jù)量較大時(shí)FP-growth算法的特征算法的特征FP-growth算法中FP表示(frequent pattern)頻繁模式1.基于Aprior構(gòu)建但在完成相同任務(wù)時(shí)使用了一些不同的技術(shù)，利用了一種FP樹(shù)的數(shù)據(jù)結(jié)構(gòu)將數(shù)據(jù)存放在其中然后再發(fā)現(xiàn)頻繁項(xiàng)集或者頻繁項(xiàng)對(duì)2.FP-growth算法的執(zhí)行速度要快于Apriori，通常性能要好兩個(gè)數(shù)量級(jí)以上（FP-growth只用對(duì)數(shù)據(jù)庫(kù)進(jìn)行兩次掃描）3.發(fā)現(xiàn)頻繁的基本過(guò)程如下：構(gòu)建FP樹(shù)從FP樹(shù)中挖掘頻繁項(xiàng)集FP樹(shù)樹(shù)二叉搜索樹(shù)FP樹(shù)2.每個(gè)項(xiàng)集會(huì)以路徑的形式存儲(chǔ)在樹(shù)中3.一個(gè)元素項(xiàng)可以在一棵FP樹(shù)中出現(xiàn)多次4

30、.相似項(xiàng)之間還有節(jié)點(diǎn)鏈接創(chuàng)建創(chuàng)建FP樹(shù)的數(shù)據(jù)結(jié)構(gòu)樹(shù)的數(shù)據(jù)結(jié)構(gòu)構(gòu)建構(gòu)建FP樹(shù)樹(shù)數(shù)據(jù)集樣例除了FP樹(shù)以外還需要構(gòu)建一個(gè)頭指針表來(lái)指向給定類(lèi)型的第一個(gè)實(shí)例構(gòu)建構(gòu)建FP樹(shù)的第一次遍歷樹(shù)的第一次遍歷給定一個(gè)最小閾值（和Apriori的支持度類(lèi)似）這里為出現(xiàn)的次數(shù)，同樣Apriori的原理也是成立的即如果某一個(gè)元素是不頻繁的，那么包含該元素的集合也是不頻繁的。第一次遍歷會(huì)獲得每個(gè)元素項(xiàng)的出現(xiàn)頻率，去掉不滿足最小支持度的元素項(xiàng)再進(jìn)行排序（為了使相同項(xiàng)只出現(xiàn)一次）最小閾值為3過(guò)濾排序后的結(jié)果FP樹(shù)的構(gòu)建樹(shù)的構(gòu)建FP樹(shù)的代碼實(shí)現(xiàn)樹(shù)的代碼實(shí)現(xiàn)樹(shù)構(gòu)建的過(guò)程中會(huì)遍歷數(shù)據(jù)集兩次，第一次遍歷掃描數(shù)據(jù)集并統(tǒng)計(jì)每個(gè)元素出現(xiàn)的

31、頻度并把這些信息存儲(chǔ)在頭指針表中。掃描頭指針表刪掉那些出現(xiàn)次數(shù)少于minsup的項(xiàng)接著對(duì)頭指針表進(jìn)行擴(kuò)展以便保存計(jì)數(shù)值及指向每種類(lèi)型第一個(gè)元素項(xiàng)的指針。創(chuàng)建只包含空集合的根節(jié)點(diǎn)最后再次遍歷數(shù)據(jù)集生成FP樹(shù)和頭指針表從一棵FP樹(shù)中挖掘頻繁項(xiàng)集這里的思路與Apriori算法大致類(lèi)似，首先從單元素項(xiàng)集合開(kāi)始，然后在此基礎(chǔ)上逐步構(gòu)成更大的集合。這里將利用FP樹(shù)來(lái)實(shí)現(xiàn)上述過(guò)程，不在需要原始數(shù)據(jù)集了。從FP樹(shù)中抽取頻繁項(xiàng)集的三個(gè)基本步驟（1）從FP樹(shù)中獲得條件模式基；（2）利用條件模式基，構(gòu)建一個(gè)條件FP樹(shù)；（3）迭代重復(fù)（1）、（2）步驟，直到樹(shù)包含一個(gè)元素項(xiàng)為止示例說(shuō)明如下表所示數(shù)據(jù)清單（第一列為購(gòu)買(mǎi)

32、id,第二列為物品項(xiàng)目）：第一步：構(gòu)建FP樹(shù)1.掃描數(shù)據(jù)集，對(duì)每個(gè)物品進(jìn)行計(jì)數(shù)：2. 設(shè)定最小支持度（即物品最少出現(xiàn)的次數(shù)）為23. 按降序重新排列物品集（如果出現(xiàn)計(jì)數(shù)小于2的物品則需刪除）4. 根據(jù)項(xiàng)目（物品）出現(xiàn)的次數(shù)重新調(diào)整物品清單5構(gòu)建FP樹(shù)第二步：挖掘頻繁項(xiàng)集對(duì)于每一個(gè)元素項(xiàng)，獲取其對(duì)應(yīng)的條件模式基（conditional pattern base）。條件模式基是以所查找元素項(xiàng)為結(jié)尾的路徑集合。每一條路徑其實(shí)都是一條前綴路徑。簡(jiǎn)而言之，一條前綴路勁是介于所查找元素項(xiàng)與樹(shù)根節(jié)點(diǎn)之間的所有內(nèi)容。所以尋找條件模式基的時(shí)候從下往上看，從指定元素開(kāi)始一直尋找到跟節(jié)點(diǎn)所以尋找條件模式基的時(shí)候從下

33、往上看，從指定元素開(kāi)始一直尋找到跟節(jié)點(diǎn)以I5為例： 考慮I5，得到條件模式基I2,I1:1；I2,I1,I3:1, 構(gòu)造（元素元素I5項(xiàng)項(xiàng)）條件FP樹(shù)如下。 每條單路徑上的條件模式基取并集每條單路徑上的條件模式基取并集，相同元素項(xiàng)合并，頻數(shù)+1，刪除自由度小于給定最小自由度的項(xiàng)（此示例為2）。之后和模式后綴I5取并集得到支持度大于2的所有模式： I2 I5:2, I1 I5:2, I2 I1 I5:2。I5的情況是比較簡(jiǎn)單的，因?yàn)镮5對(duì)應(yīng)的條件FP-樹(shù)是單路徑的。下面考慮I3，I3的條件模式基是I2,I1:2 I2:2 I1:2，生成的條件FP-樹(shù)如下圖，然后遞歸調(diào)用FP-growth，模式前

34、綴為I3。I3的條件FP-樹(shù)仍然是一個(gè)多路徑樹(shù)，首先把模式后綴I3和條件FP樹(shù)中的項(xiàng)頭表中的每一項(xiàng)取并集，得到一組模式I2 I3:4, I1 I3:4，但是這一組模式不是后綴為I3的所有模式。還需要遞歸調(diào)用FP-growth，模式后綴為I1，I3，I1，I3的條件模式基為I2：2。這是一個(gè)單路徑的條件FP-樹(shù)，在FP-growth中把I2和模式后綴I1，I3取并得到模式I2 I1 I3：2。最終模式后綴I3的支持度大于2的所有模式為： I2 I3:4, I1 I3:4, I1 I2 I3:2根據(jù)FP-growth算法得到此示例的所有頻繁項(xiàng)集發(fā)現(xiàn)一給定元素項(xiàng)結(jié)尾的所有路徑的函數(shù)遞歸查找頻繁項(xiàng)集的

35、函數(shù)示例執(zhí)行執(zhí)行結(jié)果改進(jìn)Apriori 算法在股票分析中的應(yīng)用研究07Apriori算法的改進(jìn)01實(shí)驗(yàn)及結(jié)果分析02改進(jìn)的Apriori算法在股票分析中的應(yīng)用研究改進(jìn)的Apriori算法在股票分析中的應(yīng)用研究 針對(duì)經(jīng)典Apriori 算法效率上的不足，提出了一種改進(jìn)的Apriori 算法。通過(guò)改進(jìn)的Apriori 挖掘算法對(duì)股票交易數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行分析，找出各種股票之間的隱藏關(guān)系，挖掘出一些可靠的、合理的股票關(guān)聯(lián)規(guī)則，為投資者對(duì)股票是買(mǎi)入還是賣(mài)出提供決策支持?！薄案倪M(jìn)的apriori算法在股票分析中的應(yīng)用研究 在許多情況下，Apriori 性質(zhì)大幅度壓縮了候選項(xiàng)集的大小，并產(chǎn)生很好的性能。然

36、而，它有兩種開(kāi)銷(xiāo)可能是十分巨大的： 數(shù)據(jù)庫(kù)掃描的次數(shù)過(guò)多，尋找每個(gè)k-頻繁項(xiàng)集(k =1,2, ,k )都需要掃描數(shù)據(jù)庫(kù)一次，共需要掃描k 次。因此當(dāng)數(shù)據(jù)庫(kù)或者k 太大時(shí)，算法的耗時(shí)將太大甚至無(wú)法完成。算法的剪枝步，VcCk，判斷c 的k 個(gè)(k-1)-子集是否都在Lk-1中，若找到一個(gè)(k-1)-子集不在Lk-1 中就淘汰C。因?yàn)檫@個(gè)過(guò)程會(huì)多次掃描Lk-1，特別是當(dāng)生成的Ck 很大時(shí)，算法的效率并不理想。Apriori算法的改進(jìn)01改進(jìn)的apriori算法在股票分析中的應(yīng)用研究 針對(duì)Apriori 算法的缺點(diǎn)，給出了一種改進(jìn)的算法：NApriori算法，其產(chǎn)生頻繁項(xiàng)集及其支持?jǐn)?shù)的具體步驟如下：(1)掃描事務(wù)數(shù)據(jù)庫(kù)DB一次，得到1-項(xiàng)的支持?jǐn)?shù)，并根據(jù)最小支持?jǐn)?shù)得到頻繁1-項(xiàng)集F 和它們的支持?jǐn)?shù)；(2