Apriori算法介紹PPT

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、終當某一項集為空則跳出循環(huán)；最終返回所有的頻繁項集和支持度support處理輸入數(shù)據(jù)處理輸入數(shù)據(jù)規(guī)定初始數(shù)據(jù)中，每一個事務由一個List結構表示，事務中的項目為List中元素，所有事務List構成整體數(shù)據(jù)的LIst（二維）該函數(shù)接收一個參數(shù)：原始數(shù)據(jù)，該函數(shù)作用如下：進行遍歷，使用Python編程技巧進行去重和排序，最后生成一項集，防止后期因為某些原因修改到數(shù)據(jù)，將數(shù)據(jù)進行frozenset操作，將每個元素生成一個Set結構。返回的List就是數(shù)據(jù)的一項集生成頻繁項集生成頻繁項集該函數(shù)接收三個參數(shù)：原始數(shù)據(jù)，項集List，最小支持度該函數(shù)作用如下：定義一個空dict用于存放項集頻數(shù)，對于原始數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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