Python數據分析與挖掘第9章關聯規則挖掘

關聯規則挖掘關聯規則分析用于在一個數據集中找出各數據項之間的關聯關系，廣泛用于購物籃數據、生物信息學、醫療診斷、網頁挖掘和科學數據分析中。關聯規則分析又稱購物籃分析，最早是為了發現超市銷售數據庫中不同商品之間的關聯關系。采用關聯模型比較典型的案例：“尿布與啤酒”的故事颶風與蛋撻2ARealExample

關聯規則挖掘4關聯規則分析通過量化的數字描述某物品的出現對其他物品的影響程度，是數據挖掘中較活躍的研究方法之一。目前，常用的關聯規則分析算法如下表。頻繁項集、閉項集和關聯規則關聯規則分析最早是為了發現超市銷售數據庫中不同商品間的關聯關系。頻繁模式（FrequentPattern）是指頻繁出現在數據集中的模式（如項集，子序列或子結構）。挖掘頻繁模式可以揭示數據集的內在的、重要的特性，可以作為很多重要數據挖掘任務的基礎，比如：5關聯、相關和因果分析序列、結構（如子圖）模式分析時空、多媒體、時序和流數據中的模式分析分類：關聯分類聚類分析：基于頻繁模式的聚類數據倉庫：冰山方體計算頻繁項集、閉項集和關聯規則1.關聯規則的表示形式模式可以用關聯規則（AssociationRule）的形式表示。例如購買計算機也趨向于同時購買打印機，可以用如下關聯規則表示。規則的支持度（Support）和置信度（Confidence）是規則興趣度的兩種度量，分別反映規則的有用性和確定性。6頻繁項集、閉項集和關聯規則2.頻繁項集和閉項集同時滿足最小支持度閾值（min_sup）和最小置信度閾值（min_conf）的規則稱為強關聯規則。7頻繁項集、閉項集和關聯規則一般來說，關聯規則的挖掘可以看作兩步的過程：（1）找出所有頻繁項集，該項集的每一個出現的支持度計數≥min_sup；（2）由頻繁項集產生強關聯規則，即滿足最小支持度和最小置信度的規則。8頻繁項集、閉項集和關聯規則由于第2步的開銷遠小于第1步，因此挖掘關聯規則的總體性能由第1步決定。第1步主要是找到所有的頻繁k項集，而在找頻繁項集的過程中，需要對每個k項集，計算支持度計數以發現頻繁項集，k項集的產生過程如圖：9k項集的產生過程頻繁項集、閉項集和關聯規則因此，項集的個數太大嚴重影響算法的效率。為了克服這一困難，引入閉頻繁項集和極大頻繁項集的概念。項集X在數據集D中是閉的（Closed），如果不存在X的真超項集Y使得Y與X在D中具有相同的支持度計數。10頻繁項集挖掘方法發現頻繁項集是挖掘關聯規則的基礎。Apriori算法通過限制候選產生發現頻繁項集，FP-growth算法發現頻繁模式而不產生候選。11Apriori算法12Apriori算法是Agrawal和Srikant于1994年提出，是布爾關聯規則挖掘頻繁項集的原創性算法，通過限制候選產生發現頻繁項集。Apriori算法使用一種稱為逐層搜索的迭代方法，其中k項集用于探索（k+1）項集。具體過程描述如下：首先掃描數據庫，累計每個項的計數，并收集滿足最小支持度的項找出頻繁1項集記為L1。然后使用L1找出頻繁2項集的集合L2，使用L2找出L3，迭代直到無法再找到頻繁k項集為止。找出每個Lk需要一次完整的數據庫掃描。Apriori算法使用一種稱為先驗性質的特性進行搜索空間的壓縮，即頻繁項集的所有非空子集也一定是頻繁的。Apriori算法Apriori算法產生k項頻繁集的過程主要包括連接和剪枝兩步。13Apriori算法Apriori算法產生k項頻繁集的過程主要包括連接和剪枝兩步。（2）剪枝Ck是Lk的超集，Ck的成員不一定全部是頻繁的，但所有頻繁的k項集都包含在Ck中。為了減少計算量，可以使用Apriori性質，即如果一個k項集的（k-1）子集不在Lk-1中，則該候選不可能是頻繁的，可以直接從Ck刪除。這種子集測試可以使用所有頻繁項集的散列樹快速完成。14Apriori算法15由頻繁項集產生關聯規則16由頻繁項集產生關聯規則17提高Apriori算法的效率Apriori算法使用逐層搜索的迭代方法，隨著k的遞增不斷尋找滿足最小支持度閾值的“k項集”，第k次迭代從k-1次迭代的結果中查找頻繁k項集，每一次迭代都要掃描一次數據庫。而且，對候選項集的支持度計算非常繁瑣。為了進一步提高Apriori算法的效率，一般采用減少對數據的掃描次數、縮小產生的候選項集以及改進對候選項集的支持度計算方法等策略。1.基于hash表的項集計數2.事務壓縮（壓縮進一步迭代的事務數）3.抽樣（在給定數據的一個子集挖掘）4.動態項集計數18頻繁模式增長算法Apriori算法的候選產生-檢查方法顯著壓縮了候選集的規模，但還是可能要產生大量的候選項集。而且，要重復掃描數據庫，通過模式匹配檢查一個很大的候選集合。頻繁模式增長（FP-growth）是一種不產生候選頻繁項集的算法，它采用分治策略（DivideandConquer），在經過第一遍掃描之后，把代表頻繁項集的數據庫壓縮進一棵頻繁模式樹（FP-tree），同時依然保留其中的關聯信息；然后將FP-tree分化成一些條件庫，每個庫和一個長度為1的頻集相關，再對這些條件庫分別進行挖掘（降低了I/O開銷）。19頻繁模式增長算法2.FP樹構建過程示例（1）從數據庫構建一個FP樹第一次掃描數據庫，導出頻繁項的集合（1-項集），并將頻繁項按支持度計數降序排列20頻繁模式增長算法根據上述生成的項集，構造FP樹，如圖所示。21頻繁模式增長算法根據上述生成的項集，構造FP樹，如圖所示。22頻繁模式增長算法為了方便樹的遍歷，創建一個項頭表，使每項通過一個結點鏈指向它在樹中的位置。掃描所有的事務，得到的FP樹如圖所示。23頻繁模式增長算法FP樹挖掘（1）從FP樹到條件模式基從項頭表開始挖掘，由頻率低的結點開始。在圖6.5的FP樹中，首先依據結點o在該路徑上的支持度更新前綴路徑上結點的支持度計數。在此基礎上，得到o點的條件模式基{f,c,a,b,m,l:1}，{f,b:1}。構建條件FP樹。利用o點的條件模式基得到o點的條件FP樹。如果該條件FP樹有多條路徑，則繼續迭代，構造條件FP樹。否則，如果該FP樹只有一條路徑，則直接求以該結點結尾的頻繁項集。24頻繁模式增長算法圖中節點m的條件模式基為{f,c,a:2}，{f,c,a,b:1}，m的條件FP樹如圖下示，可以直接獲得關于m的頻繁項為m,fm,cm,am,fcm,fam,cam,fcam。

節點m的條件FP樹頻繁模式增長算法FP-growth方法將發現長頻繁模式的問題轉換化為在較小的條件數據庫中遞歸地搜索一些較短模式，然后連接后綴。它使用最不頻繁的項做后綴，提供了較好的選擇性，顯著降低了搜索開銷。當數據庫很大時，構造基于主存的FP樹是不現實的，一種有趣的選擇是將數據庫劃分成投影數據庫集合，然后在每個投影數據庫上構造FP樹并進行挖掘。26使用垂直數據格式挖掘頻繁項集Apriori算法和FP-growth算法都從TID項集格式（即{TID：itemset}）的事務集中挖掘頻繁模式。其中TID是事務標識符，而itemset是事務TID中購買的商品。這種數據格式稱為水平數據格式（HorizontalDataFormat）。使用垂直數據格式有效地挖掘頻繁項集，它是等價類變換(EquivalencCLAssTransformation，Eclat)算法的要點。27使用垂直數據格式挖掘頻繁項集28使用垂直數據格式挖掘頻繁項集。使用垂直數據格式挖掘頻繁項集29例中解釋了通過探查垂直數據格式挖掘頻繁項集的過程。首先，通過掃描一次數據集，把水平格式的數據轉換成垂直格式。項集的支持度計數簡單地等于項集的TID集的長度。從k=1開始，可以根據先驗性質，使用頻繁k項集來構造候選（k+1）項集。通過取頻繁k項集的TID集的交，計算對應的（k+1）項集的TID集。重復該過程，

每次k增加1，直到不能再找到頻繁項集或候選項集。

關聯模式評估方法大部分關聯規則挖掘算法都使用支持度-置信度框架。盡管最小支持度和置信度閾值可以排除大量無趣規則的探查，但仍然會有一些用戶不感興趣的規則存在。當使用低支持度閾值挖掘或挖掘長模式時，這種情況尤為嚴重。強關聯規則不一定是有趣的：例：30從關聯分析到相關分析由于支持度和置信度還不足以過濾掉無趣的關聯規則，因此，可以使用相關性度量來擴展關聯規則的支持度-置信度框架。相關規則框架為：31從關聯分析到相關分析32從關聯分析到相關分析33Apriori算法應用1在Pyhton中進行關聯規則挖掘時需要用到apyori包，apyori包的安裝方式為：pipinstallapyori返回結果result中的屬性說明：items–項集，frozenset對象，可迭代取出子集；support–支持度，float類型；confidence–置信度或可信度，float類型；ordered_statistics–存在的關聯規則，可迭代，迭代后，其元素的屬性：items_base–關聯規則中的分母項集；confidence–上面的分母規則所對應的關聯規則的可信度。34Apriori算法應用2關聯規則目前在scikit-learn中并沒有實現。機器學習擴展庫mlxtend：是一款高級的機器學習擴展庫,可用于日常機器學習任務的主要工具,也可以作為sklearn的一個補充和輔助工具。

mlxtend提供了多種分類和回歸算法api，包括多層感知機、stacking分類器、邏輯回歸等。Apriori算法應用2安裝pipinstallmlxtend數據：importpandasaspditem_list=[['牛奶','面包'],['面包','尿布','啤酒','土豆'],['牛奶','尿布','啤酒','可樂'],['面包','牛奶','尿布','啤酒'],['面包','牛奶','尿布','可樂']]item_df=pd.DataFrame(item_list)#frommlxtend.preprocessingimportTransactionEncodeimportmlxtendte=mlxtend.preprocessing.TransactionEncoder()df_tf=te.fit_transform(item_list)df=pd.DataFrame(df_tf,columns=te.columns_)display(df)Apriori算法應用2計算頻繁項集frommlxtend.frequent_patternsimportapriori#use_colnames=True表示使用元素名字，默認的False使用列名代表元素frequent_itemsets=apriori(df,min_support=0.05,use_colnames=True)frequent_itemsets.sort_values(by='support',ascending=False,inplace=True)#選擇2頻繁項集print(frequent_itemsets[frequent_itemsets.itemsets.apply(lambdax:len(x))==2])Apriori算法應用2計算關聯規則frommlxtend.frequent_patternsimportassociation_rules#metric可以有很多的度量選項，返回的表列名都可以作為參數association_rule=association_rules(frequent_itemsets,metric='confidence',min_threshold