版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
Python數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)第6章關(guān)聯(lián)規(guī)則挖掘OverviewFrequentItemsetsAssociationRulesSequentialPatterns2ARealExample第6章關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則分析用于在一個(gè)數(shù)據(jù)集中找出各數(shù)據(jù)項(xiàng)之間的關(guān)聯(lián)關(guān)系,廣泛用于購(gòu)物籃數(shù)據(jù)、生物信息學(xué)、醫(yī)療診斷、網(wǎng)頁(yè)挖掘和科學(xué)數(shù)據(jù)分析中。關(guān)聯(lián)規(guī)則分析又稱購(gòu)物籃分析,最早是為了發(fā)現(xiàn)超市銷售數(shù)據(jù)庫(kù)中不同商品之間的關(guān)聯(lián)關(guān)系。采用關(guān)聯(lián)模型比較典型的案例:“尿布與啤酒”的故事颶風(fēng)與蛋撻10十一月20244第6章關(guān)聯(lián)規(guī)則挖掘5關(guān)聯(lián)規(guī)則分析通過(guò)量化的數(shù)字描述某物品的出現(xiàn)對(duì)其他物品的影響程度,是數(shù)據(jù)挖掘中較活躍的研究方法之一。目前,常用的關(guān)聯(lián)規(guī)則分析算法如表6-1所示。頻繁項(xiàng)集、閉項(xiàng)集和關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則分析最早是為了發(fā)現(xiàn)超市銷售數(shù)據(jù)庫(kù)中不同商品間的關(guān)聯(lián)關(guān)系。頻繁模式(FrequentPattern)是指頻繁出現(xiàn)在數(shù)據(jù)集中的模式(如項(xiàng)集,子序列或子結(jié)構(gòu))。挖掘頻繁模式可以揭示數(shù)據(jù)集的內(nèi)在的、重要的特性,可以作為很多重要數(shù)據(jù)挖掘任務(wù)的基礎(chǔ),比如:10十一月20246頻繁項(xiàng)集、閉項(xiàng)集和關(guān)聯(lián)規(guī)則1.關(guān)聯(lián)規(guī)則的表示形式模式可以用關(guān)聯(lián)規(guī)則(AssociationRule)的形式表示。例如購(gòu)買(mǎi)計(jì)算機(jī)也趨向于同時(shí)購(gòu)買(mǎi)打印機(jī),可以用如下關(guān)聯(lián)規(guī)則表示。規(guī)則的支持度(Support)和置信度(Confidence)是規(guī)則興趣度的兩種度量,分別反映規(guī)則的有用性和確定性。10十一月20247頻繁項(xiàng)集、閉項(xiàng)集和關(guān)聯(lián)規(guī)則2.頻繁項(xiàng)集和閉項(xiàng)集同時(shí)滿足最小支持度閾值(min_sup)和最小置信度閾值(min_conf)的規(guī)則稱為強(qiáng)關(guān)聯(lián)規(guī)則。10十一月20248頻繁項(xiàng)集、閉項(xiàng)集和關(guān)聯(lián)規(guī)則一般來(lái)說(shuō),關(guān)聯(lián)規(guī)則的挖掘可以看作兩步的過(guò)程:(1)找出所有頻繁項(xiàng)集,該項(xiàng)集的每一個(gè)出現(xiàn)的支持度計(jì)數(shù)≥min_sup;(2)由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則,即滿足最小支持度和最小置信度的規(guī)則。10十一月20249頻繁項(xiàng)集、閉項(xiàng)集和關(guān)聯(lián)規(guī)則由于第2步的開(kāi)銷遠(yuǎn)小于第1步,因此挖掘關(guān)聯(lián)規(guī)則的總體性能由第1步?jīng)Q定。第1步主要是找到所有的頻繁k項(xiàng)集,而在找頻繁項(xiàng)集的過(guò)程中,需要對(duì)每個(gè)k項(xiàng)集,計(jì)算支持度計(jì)數(shù)以發(fā)現(xiàn)頻繁項(xiàng)集,k項(xiàng)集的產(chǎn)生過(guò)程如圖6.110十一月202410頻繁項(xiàng)集、閉項(xiàng)集和關(guān)聯(lián)規(guī)則因此,項(xiàng)集的個(gè)數(shù)太大嚴(yán)重影響算法的效率。為了克服這一困難,引入閉頻繁項(xiàng)集和極大頻繁項(xiàng)集的概念。項(xiàng)集X在數(shù)據(jù)集D中是閉的(Closed),如果不存在X的真超項(xiàng)集Y使得Y與X在D中具有相同的支持度計(jì)數(shù)。10十一月202411頻繁項(xiàng)集挖掘方法發(fā)現(xiàn)頻繁項(xiàng)集是挖掘關(guān)聯(lián)規(guī)則的基礎(chǔ)。Apriori算法通過(guò)限制候選產(chǎn)生發(fā)現(xiàn)頻繁項(xiàng)集,F(xiàn)P-growth算法發(fā)現(xiàn)頻繁模式而不產(chǎn)生候選。10十一月202412Apriori算法10十一月202413Apriori算法是Agrawal和Srikant于1994年提出,是布爾關(guān)聯(lián)規(guī)則挖掘頻繁項(xiàng)集的原創(chuàng)性算法,通過(guò)限制候選產(chǎn)生發(fā)現(xiàn)頻繁項(xiàng)集。Apriori算法使用一種稱為逐層搜索的迭代方法,其中k項(xiàng)集用于探索(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,迭代直到無(wú)法再找到頻繁k項(xiàng)集為止。找出每個(gè)Lk需要一次完整的數(shù)據(jù)庫(kù)掃描。Apriori算法使用一種稱為先驗(yàn)性質(zhì)的特性進(jìn)行搜索空間的壓縮,即頻繁項(xiàng)集的所有非空子集也一定是頻繁的。Apriori算法Apriori算法產(chǎn)生k項(xiàng)頻繁集的過(guò)程主要包括連接和剪枝兩步。10十一月202414Apriori算法Apriori算法產(chǎn)生k項(xiàng)頻繁集的過(guò)程主要包括連接和剪枝兩步。(2)剪枝Ck是Lk的超集,Ck的成員不一定全部是頻繁的,但所有頻繁的k項(xiàng)集都包含在Ck中。為了減少計(jì)算量,可以使用Apriori性質(zhì),即如果一個(gè)k項(xiàng)集的(k-1)子集不在Lk-1中,則該候選不可能是頻繁的,可以直接從Ck刪除。這種子集測(cè)試可以使用所有頻繁項(xiàng)集的散列樹(shù)快速完成。10十一月202415Apriori算法10十一月202416由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則10十一月202417由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則10十一月202418提高Apriori算法的效率Apriori算法使用逐層搜索的迭代方法,隨著k的遞增不斷尋找滿足最小支持度閾值的“k項(xiàng)集”,第k次迭代從k-1次迭代的結(jié)果中查找頻繁k項(xiàng)集,每一次迭代都要掃描一次數(shù)據(jù)庫(kù)。而且,對(duì)候選項(xiàng)集的支持度計(jì)算非常繁瑣。為了進(jìn)一步提高Apriori算法的效率,一般采用減少對(duì)數(shù)據(jù)的掃描次數(shù)、縮小產(chǎn)生的候選項(xiàng)集以及改進(jìn)對(duì)候選項(xiàng)集的支持度計(jì)算方法等策略。1.基于hash表的項(xiàng)集計(jì)數(shù)2.事務(wù)壓縮(壓縮進(jìn)一步迭代的事務(wù)數(shù))3.抽樣(在給定數(shù)據(jù)的一個(gè)子集挖掘)4.動(dòng)態(tài)項(xiàng)集計(jì)數(shù)10十一月202419頻繁模式增長(zhǎng)算法Apriori算法的候選產(chǎn)生-檢查方法顯著壓縮了候選集的規(guī)模,但還是可能要產(chǎn)生大量的候選項(xiàng)集。而且,要重復(fù)掃描數(shù)據(jù)庫(kù),通過(guò)模式匹配檢查一個(gè)很大的候選集合。頻繁模式增長(zhǎng)(FP-growth)是一種不產(chǎn)生候選頻繁項(xiàng)集的算法,它采用分治策略(DivideandConquer),在經(jīng)過(guò)第一遍掃描之后,把代表頻繁項(xiàng)集的數(shù)據(jù)庫(kù)壓縮進(jìn)一棵頻繁模式樹(shù)(FP-tree),同時(shí)依然保留其中的關(guān)聯(lián)信息;然后將FP-tree分化成一些條件庫(kù),每個(gè)庫(kù)和一個(gè)長(zhǎng)度為1的頻集相關(guān),再對(duì)這些條件庫(kù)分別進(jìn)行挖掘(降低了I/O開(kāi)銷)。10十一月202420頻繁模式增長(zhǎng)算法1.FP樹(shù)原理FP樹(shù)采用分治策略的方法,在經(jīng)過(guò)第一遍掃描之后,把代表頻繁項(xiàng)集的數(shù)據(jù)庫(kù)壓縮進(jìn)一棵頻繁模式樹(shù)(FP-tree),同時(shí)依然保留其中的關(guān)聯(lián)信息;然后將FP-tree分化成一些條件庫(kù),每個(gè)庫(kù)和一個(gè)長(zhǎng)度為1的頻集相關(guān),然后再對(duì)這些條件庫(kù)分別進(jìn)行挖掘(降低了I/O開(kāi)銷)。10十一月202421頻繁模式增長(zhǎng)算法2.FP樹(shù)構(gòu)建過(guò)程示例(1)從數(shù)據(jù)庫(kù)構(gòu)建一個(gè)FP樹(shù)第一次掃描數(shù)據(jù)庫(kù),導(dǎo)出頻繁項(xiàng)的集合(1-項(xiàng)集),并將頻繁項(xiàng)按支持度計(jì)數(shù)降序排列10十一月202422頻繁模式增長(zhǎng)算法根據(jù)上述生成的項(xiàng)集,構(gòu)造FP樹(shù),如圖6-4所示。10十一月202423頻繁模式增長(zhǎng)算法根據(jù)上述生成的項(xiàng)集,構(gòu)造FP樹(shù),如圖6-4所示。10十一月202424頻繁模式增長(zhǎng)算法為了方便樹(shù)的遍歷,創(chuàng)建一個(gè)項(xiàng)頭表,使每項(xiàng)通過(guò)一個(gè)結(jié)點(diǎn)鏈指向它在樹(shù)中的位置。掃描所有的事務(wù),得到的FP樹(shù)如圖6-5所示。10十一月202425頻繁模式增長(zhǎng)算法FP樹(shù)挖掘(1)從FP樹(shù)到條件模式基從項(xiàng)頭表開(kāi)始挖掘,由頻率低的結(jié)點(diǎn)開(kāi)始。在圖6.5的FP樹(shù)中,首先依據(jù)結(jié)點(diǎn)o在該路徑上的支持度更新前綴路徑上結(jié)點(diǎn)的支持度計(jì)數(shù)。在此基礎(chǔ)上,得到o點(diǎn)的條件模式基{f,c,a,b,m,l:1},{f,b:1}。構(gòu)建條件FP樹(shù)。利用o點(diǎn)的條件模式基得到o點(diǎn)的條件FP樹(shù)。如果該條件FP樹(shù)有多條路徑,則繼續(xù)迭代,構(gòu)造條件FP樹(shù)。否則,如果該FP樹(shù)只有一條路徑,則直接求以該結(jié)點(diǎn)結(jié)尾的頻繁項(xiàng)集。10十一月202426頻繁模式增長(zhǎng)算法圖6-5中節(jié)點(diǎn)m的條件模式基為{f,c,a:2},{f,c,a,b:1},m的條件FP樹(shù)如圖6-6所示,可以直接獲得關(guān)于m的頻繁項(xiàng)為m,fm,cm,am,fcm,fam,cam,fcam。11/10/2024圖6-6節(jié)點(diǎn)m的條件FP樹(shù)頻繁模式增長(zhǎng)算法FP-growth方法將發(fā)現(xiàn)長(zhǎng)頻繁模式的問(wèn)題轉(zhuǎn)換化為在較小的條件數(shù)據(jù)庫(kù)中遞歸地搜索一些較短模式,然后連接后綴。它使用最不頻繁的項(xiàng)做后綴,提供了較好的選擇性,顯著降低了搜索開(kāi)銷。當(dāng)數(shù)據(jù)庫(kù)很大時(shí),構(gòu)造基于主存的FP樹(shù)是不現(xiàn)實(shí)的,一種有趣的選擇是將數(shù)據(jù)庫(kù)劃分成投影數(shù)據(jù)庫(kù)集合,然后在每個(gè)投影數(shù)據(jù)庫(kù)上構(gòu)造FP樹(shù)并進(jìn)行挖掘。10十一月202428使用垂直數(shù)據(jù)格式挖掘頻繁項(xiàng)集Apriori算法和FP-growth算法都從TID項(xiàng)集格式(即{TID:itemset})的事務(wù)集中挖掘頻繁模式。其中TID是事務(wù)標(biāo)識(shí)符,而itemset是事務(wù)TID中購(gòu)買(mǎi)的商品。這種數(shù)據(jù)格式稱為水平數(shù)據(jù)格式(HorizontalDataFormat)。使用垂直數(shù)據(jù)格式有效地挖掘頻繁項(xiàng)集,它是等價(jià)類變換(EquivalencCLAssTransformation,Eclat)算法的要點(diǎn)。10十一月202429使用垂直數(shù)據(jù)格式挖掘頻繁項(xiàng)集10十一月202430使用垂直數(shù)據(jù)格式挖掘頻繁項(xiàng)集10十一月202431例6.3解釋了通過(guò)探查垂直數(shù)據(jù)格式挖掘頻繁項(xiàng)集的過(guò)程。首先,通過(guò)掃描一次數(shù)據(jù)集,把水平格式的數(shù)據(jù)轉(zhuǎn)換成垂直格式。項(xiàng)集的支持度計(jì)數(shù)簡(jiǎn)單地等于項(xiàng)集的TID集的長(zhǎng)度。從k=1開(kāi)始,可以根據(jù)先驗(yàn)性質(zhì),使用頻繁k項(xiàng)集來(lái)構(gòu)造候選(k+1)項(xiàng)集。通過(guò)取頻繁k項(xiàng)集的TID集的交,計(jì)算對(duì)應(yīng)的(k+1)項(xiàng)集的TID集。重復(fù)該過(guò)程,
每次k增加1,直到不能再找到頻繁項(xiàng)集或候選項(xiàng)集。
關(guān)聯(lián)模式評(píng)估方法大部分關(guān)聯(lián)規(guī)則挖掘算法都使用支持度-置信度框架。盡管最小支持度和置信度閾值可以排除大量無(wú)趣規(guī)則的探查,但仍然會(huì)有一些用戶不感興趣的規(guī)則存在。當(dāng)使用低支持度閾值挖掘或挖掘長(zhǎng)模式時(shí),這種情況尤為嚴(yán)重。強(qiáng)關(guān)聯(lián)規(guī)則不一定是有趣的:例:10十一月202432從關(guān)聯(lián)分析到相關(guān)分析由于支持度和置信度還不足以過(guò)濾掉無(wú)趣的關(guān)聯(lián)規(guī)則,因此,可以使用相關(guān)性度量來(lái)擴(kuò)展關(guān)聯(lián)規(guī)則的支持度-置信度框架。相關(guān)規(guī)則框架為:10十一月202433從關(guān)聯(lián)分析到相關(guān)分析10十一月202434從關(guān)聯(lián)分析到相關(guān)分析10十一月202435Apriori算法應(yīng)用1在Pyhton中進(jìn)行關(guān)聯(lián)規(guī)則挖掘時(shí)需要用到apyori包,apyori包的安裝方式為:pipinstallapyori返回結(jié)果result中的屬性說(shuō)明:items–項(xiàng)集,frozenset對(duì)象,可迭代取出子集;support–支持度,float類型;confidence–置信度或可信度,float類型;ordered_statistics–存在的關(guān)聯(lián)規(guī)則,可迭代,迭代后,其元素的屬性:items_base–關(guān)聯(lián)規(guī)則中的分母項(xiàng)集;confidence–上面的分母規(guī)則所對(duì)應(yīng)的關(guān)聯(lián)規(guī)則的可信度。10十一月202436Apriori算法應(yīng)用2關(guān)聯(lián)規(guī)則目前在scikit-learn中并沒(méi)有實(shí)現(xiàn)。機(jī)器學(xué)習(xí)擴(kuò)展庫(kù)mlxtend:是一款高級(jí)的機(jī)器學(xué)習(xí)擴(kuò)展庫(kù),可用于日常機(jī)器學(xué)習(xí)任務(wù)的主要工具,也可以作為sklearn的一個(gè)補(bǔ)充和輔助工具。
mlxtend提供了多種分類和回歸算法api,包括多層感知機(jī)、stacking分類器、邏輯回歸等。11/10/2024Apriori算法應(yīng)用2安裝pipinstallmlxtend數(shù)據(jù):importpandasaspditem_list=[['牛奶','面包'],['面包','尿布','啤酒','土豆'],['牛奶','尿布','啤酒','可樂(lè)'],['面包','牛奶','尿布','啤酒'],['面包','牛奶','尿布','可樂(lè)']]item_df=pd.DataFrame(item_list)11/10/2024#frommlxtend.preprocessingimportTransactionEncodeimportmlxtendte=mlxtend.preprocessing.TransactionEncoder()df_tf=te.fit_transform(item_list)df=pd.DataFrame(df_tf,columns=te.columns_)display(df)Apriori算法應(yīng)用2計(jì)算頻繁項(xiàng)集frommlxtend.frequent_patternsimportapriori#use_colnames=True表示使用元素名字,默認(rèn)的False使用列名代表元素frequent_itemsets=apriori(df,min_support=0.05,use_colnames=True)frequent_itemsets.sort_values(by='support',ascending=False,inplace=True)#選擇2頻繁項(xiàng)集print(frequent_itemsets[frequent_itemsets.itemsets.apply(lambdax:len(x))==2])11/10/2024Apriori算法應(yīng)用2計(jì)算關(guān)聯(lián)規(guī)則frommlxtend.frequent_patternsimportassociation_rules#metric可以有很多的度量選項(xiàng),返回的表列名都可以作為參數(shù)association_rule=association_rules(frequent_itemsets,metric='confidence',min_t
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 鄭州美術(shù)學(xué)院《嵌入式系統(tǒng)與接口技術(shù)》2023-2024學(xué)年第一學(xué)期期末試卷
- 浙江大學(xué)《工程圖學(xué)》2023-2024學(xué)年第一學(xué)期期末試卷
- 漳州理工職業(yè)學(xué)院《中學(xué)政治學(xué)科教學(xué)技能訓(xùn)練》2023-2024學(xué)年第一學(xué)期期末試卷
- 深度學(xué)習(xí)中特征表征優(yōu)化策略
- 保險(xiǎn)業(yè)務(wù)創(chuàng)新培訓(xùn)模板
- AI技術(shù)保險(xiǎn)創(chuàng)新模板
- 雙十二營(yíng)銷優(yōu)化
- 專業(yè)基礎(chǔ)-房地產(chǎn)經(jīng)紀(jì)人《專業(yè)基礎(chǔ)》名師預(yù)測(cè)卷1
- 房地產(chǎn)經(jīng)紀(jì)綜合能力-2019年房地產(chǎn)經(jīng)紀(jì)人協(xié)理《房地產(chǎn)經(jīng)紀(jì)綜合能力》真題匯編
- 2024-2025學(xué)年陜西省西安八十三中八年級(jí)(上)期末數(shù)學(xué)試卷
- 汽機(jī)油管道安裝方案指導(dǎo)
- 2022年中國(guó)城市英文名稱
- 語(yǔ)言規(guī)劃課件
- 下肢皮牽引護(hù)理PPT課件(19頁(yè)P(yáng)PT)
- 臺(tái)資企業(yè)A股上市相關(guān)資料
- 電 梯 工 程 預(yù) 算 書(shū)
- 參會(huì)嘉賓簽到表
- 形式發(fā)票格式2 INVOICE
- 2.48低危胸痛患者后繼治療評(píng)估流程圖
- 人力資源管理之績(jī)效考核 一、什么是績(jī)效 所謂績(jī)效簡(jiǎn)單的講就是對(duì)
- 山東省醫(yī)院目錄
評(píng)論
0/150
提交評(píng)論