
數(shù)據(jù)挖掘系列關(guān)聯(lián)規(guī)則挖掘基本概念與Aprior算法
關(guān)聯(lián)規(guī)則挖掘在電商、零售、大氣物理、生物醫(yī)學(xué)已經(jīng)有了廣泛的應(yīng)用,本篇文章將介紹一些基本知識和Aprori算法。
啤酒與尿布的故事已經(jīng)成為了關(guān)聯(lián)規(guī)則挖掘的經(jīng)典案例,還有人專門出了一本書《啤酒與尿布》,雖然說這個故事是哈弗商學(xué)院杜撰出來的,但確實能很好的解釋關(guān)聯(lián)規(guī)則挖掘的原理。我們這里以一個超市購物籃迷你數(shù)據(jù)集來解釋關(guān)聯(lián)規(guī)則挖掘的基本概念:
TID | Items |
T1 | {牛奶,面包} |
T2 | {面包,尿布,啤酒,雞蛋} |
T3 | {牛奶,尿布,啤酒,可樂} |
T4 | {面包,牛奶,尿布,啤酒} |
T5 | {面包,牛奶,尿布,可樂} |
表中的每一行代表一次購買清單(注意你購買十盒牛奶也只計一次,即只記錄某個商品的出現(xiàn)與否)。數(shù)據(jù)記錄的所有項的集合稱為總項集,上表中的總項集S={牛奶,面包,尿布,啤酒,雞蛋,可樂}。
一、關(guān)聯(lián)規(guī)則、自信度、自持度的定義
關(guān)聯(lián)規(guī)則就是有關(guān)聯(lián)的規(guī)則,形式是這樣定義的:兩個不相交的非空集合X、Y,如果有X-->Y,就說X-->Y是一條關(guān)聯(lián)規(guī)則。舉個例子,在上面的表中,我們發(fā)現(xiàn)購買啤酒就一定會購買尿布,{啤酒}-->{尿布}就是一條關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則的強度用支持度(support)和自信度(confidence)來描述,
支持度的定義:support(X-->Y) = |X交Y|/N=集合X與集合Y中的項在一條記錄中同時出現(xiàn)的次數(shù)/數(shù)據(jù)記錄的個數(shù)。例如:support({啤酒}-->{尿布}) = 啤酒和尿布同時出現(xiàn)的次數(shù)/數(shù)據(jù)記錄數(shù) = 3/5=60%。
自信度的定義:confidence(X-->Y) = |X交Y|/|X| = 集合X與集合Y中的項在一條記錄中同時出現(xiàn)的次數(shù)/集合X出現(xiàn)的個數(shù) 。例如:confidence({啤酒}-->{尿布}) = 啤酒和尿布同時出現(xiàn)的次數(shù)/啤酒出現(xiàn)的次數(shù)=3/3=100%;confidence({尿布}-->{啤酒}) = 啤酒和尿布同時出現(xiàn)的次數(shù)/尿布出現(xiàn)的次數(shù) = 3/4 = 75%。
這里定義的支持度和自信度都是相對的支持度和自信度,不是絕對支持度,絕對支持度abs_support = 數(shù)據(jù)記錄數(shù)N*support。
支持度和自信度越高,說明規(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ī)則。
有一個簡單而粗魯?shù)姆椒梢哉页鏊枰囊?guī)則,那就是窮舉項集的所有組合,并測試每個組合是否滿足條件,一個元素個數(shù)為n的項集的組合個數(shù)為2^n-1(除去空集),所需要的時間復(fù)雜度明顯為O(2^N),對于普通的超市,其商品的項集數(shù)也在1萬以上,用指數(shù)時間復(fù)雜度的算法不能在可接受的時間內(nèi)解決問題。怎樣快速挖出滿足條件的關(guān)聯(lián)規(guī)則是關(guān)聯(lián)挖掘的需要解決的主要問題。
仔細想一下,我們會發(fā)現(xiàn)對于{啤酒-->尿布},{尿布-->啤酒}這兩個規(guī)則的支持度實際上只需要計算{尿布,啤酒}的支持度,即它們交集的支持度。于是我們把關(guān)聯(lián)規(guī)則挖掘分兩步進行:
1)生成頻繁項集
這一階段找出所有滿足最小支持度的項集,找出的這些項集稱為頻繁項集。
2)生成規(guī)則
在上一步產(chǎn)生的頻繁項集的基礎(chǔ)上生成滿足最小自信度的規(guī)則,產(chǎn)生的規(guī)則稱為強規(guī)則。
關(guān)聯(lián)規(guī)則挖掘所花費的時間主要是在生成頻繁項集上,因為找出的頻繁項集往往不會很多,利用頻繁項集生成規(guī)則也就不會花太多的時間,而生成頻繁項集需要測試很多的備選項集,如果不加優(yōu)化,所需的時間是O(2^N)。
三、Apriori定律
為了減少頻繁項集的生成時間,我們應(yīng)該盡早的消除一些完全不可能是頻繁項集的集合,Apriori的兩條定律就是干這事的。
Apriori定律1):如果一個集合是頻繁項集,則它的所有子集都是頻繁項集。舉例:假設(shè)一個集合{A,B}是頻繁項集,即A、B同時出現(xiàn)在一條記錄的次數(shù)大于等于最小支持度min_support,則它的子集{A},{B}出現(xiàn)次數(shù)必定大于等于min_support,即它的子集都是頻繁項集。
Apriori定律2):如果一個集合不是頻繁項集,則它的所有超集都不是頻繁項集。舉例:假設(shè)集合{A}不是頻繁項集,即A出現(xiàn)的次數(shù)小于min_support,則它的任何超集如{A,B}出現(xiàn)的次數(shù)必定小于min_support,因此其超集必定也不是頻繁項集。
利用這兩條定律,我們拋掉很多的候選項集,Apriori算法就是利用這兩個定理來實現(xiàn)快速挖掘頻繁項集的。
四、Apriori算法
Apriori是由a priori合并而來的,它的意思是后面的是在前面的基礎(chǔ)上推出來的,即先驗推導(dǎo),怎么個先驗法,其實就是二級頻繁項集是在一級頻繁項集的基礎(chǔ)上產(chǎn)生的,三級頻繁項集是在二級頻繁項集的基礎(chǔ)上產(chǎn)生的,以此類推。
Apriori算法屬于候選消除算法,是一個生成候選集、消除不滿足條件的候選集、并不斷循環(huán)直到不再產(chǎn)生候選集的過程。
上面的圖演示了Apriori算法的過程,注意看由二級頻繁項集生成三級候選項集時,沒有{牛奶,面包,啤酒},那是因為{面包,啤酒}不是二級頻繁項集,這里利用了Apriori定理。最后生成三級頻繁項集后,沒有更高一級的候選項集,因此整個算法結(jié)束,{牛奶,面包,尿布}是最大頻繁子集。
算法的思想知道了,這里也就不上偽代碼了,我認(rèn)為理解了算法的思想后,子集去構(gòu)思實現(xiàn)才能理解更深刻,這里貼一下我的關(guān)鍵代碼:
如果想看完整的代碼,可以查看我的github,數(shù)據(jù)集的格式跟本文所述的略有不通,但不影響對算法的理解。
數(shù)據(jù)分析咨詢請掃描二維碼
若不方便掃碼,搜微信號:CDAshujufenxi
LSTM 模型輸入長度選擇技巧:提升序列建模效能的關(guān)鍵? 在循環(huán)神經(jīng)網(wǎng)絡(luò)(RNN)家族中,長短期記憶網(wǎng)絡(luò)(LSTM)憑借其解決長序列 ...
2025-07-11CDA 數(shù)據(jù)分析師報考條件詳解與準(zhǔn)備指南? ? 在數(shù)據(jù)驅(qū)動決策的時代浪潮下,CDA 數(shù)據(jù)分析師認(rèn)證愈發(fā)受到矚目,成為眾多有志投身數(shù) ...
2025-07-11數(shù)據(jù)透視表中兩列相乘合計的實用指南? 在數(shù)據(jù)分析的日常工作中,數(shù)據(jù)透視表憑借其強大的數(shù)據(jù)匯總和分析功能,成為了 Excel 用戶 ...
2025-07-11尊敬的考生: 您好! 我們誠摯通知您,CDA Level I和 Level II考試大綱將于 2025年7月25日 實施重大更新。 此次更新旨在確保認(rèn) ...
2025-07-10BI 大數(shù)據(jù)分析師:連接數(shù)據(jù)與業(yè)務(wù)的價值轉(zhuǎn)化者? ? 在大數(shù)據(jù)與商業(yè)智能(Business Intelligence,簡稱 BI)深度融合的時代,BI ...
2025-07-10SQL 在預(yù)測分析中的應(yīng)用:從數(shù)據(jù)查詢到趨勢預(yù)判? ? 在數(shù)據(jù)驅(qū)動決策的時代,預(yù)測分析作為挖掘數(shù)據(jù)潛在價值的核心手段,正被廣泛 ...
2025-07-10數(shù)據(jù)查詢結(jié)束后:分析師的收尾工作與價值深化? ? 在數(shù)據(jù)分析的全流程中,“query end”(查詢結(jié)束)并非工作的終點,而是將數(shù) ...
2025-07-10CDA 數(shù)據(jù)分析師考試:從報考到取證的全攻略? 在數(shù)字經(jīng)濟蓬勃發(fā)展的今天,數(shù)據(jù)分析師已成為各行業(yè)爭搶的核心人才,而 CDA(Certi ...
2025-07-09【CDA干貨】單樣本趨勢性檢驗:捕捉數(shù)據(jù)背后的時間軌跡? 在數(shù)據(jù)分析的版圖中,單樣本趨勢性檢驗如同一位耐心的偵探,專注于從單 ...
2025-07-09year_month數(shù)據(jù)類型:時間維度的精準(zhǔn)切片? ? 在數(shù)據(jù)的世界里,時間是最不可或缺的維度之一,而year_month數(shù)據(jù)類型就像一把精準(zhǔn) ...
2025-07-09CDA 備考干貨:Python 在數(shù)據(jù)分析中的核心應(yīng)用與實戰(zhàn)技巧? ? 在 CDA 數(shù)據(jù)分析師認(rèn)證考試中,Python 作為數(shù)據(jù)處理與分析的核心 ...
2025-07-08SPSS 中的 Mann-Kendall 檢驗:數(shù)據(jù)趨勢與突變分析的有力工具? ? ? 在數(shù)據(jù)分析的廣袤領(lǐng)域中,準(zhǔn)確捕捉數(shù)據(jù)的趨勢變化以及識別 ...
2025-07-08備戰(zhàn) CDA 數(shù)據(jù)分析師考試:需要多久?如何規(guī)劃? CDA(Certified Data Analyst)數(shù)據(jù)分析師認(rèn)證作為國內(nèi)權(quán)威的數(shù)據(jù)分析能力認(rèn)證 ...
2025-07-08LSTM 輸出不確定的成因、影響與應(yīng)對策略? 長短期記憶網(wǎng)絡(luò)(LSTM)作為循環(huán)神經(jīng)網(wǎng)絡(luò)(RNN)的一種變體,憑借獨特的門控機制,在 ...
2025-07-07統(tǒng)計學(xué)方法在市場調(diào)研數(shù)據(jù)中的深度應(yīng)用? 市場調(diào)研是企業(yè)洞察市場動態(tài)、了解消費者需求的重要途徑,而統(tǒng)計學(xué)方法則是市場調(diào)研數(shù) ...
2025-07-07CDA數(shù)據(jù)分析師證書考試全攻略? 在數(shù)字化浪潮席卷全球的當(dāng)下,數(shù)據(jù)已成為企業(yè)決策、行業(yè)發(fā)展的核心驅(qū)動力,數(shù)據(jù)分析師也因此成為 ...
2025-07-07剖析 CDA 數(shù)據(jù)分析師考試題型:解鎖高效備考與答題策略? CDA(Certified Data Analyst)數(shù)據(jù)分析師考試作為衡量數(shù)據(jù)專業(yè)能力的 ...
2025-07-04SQL Server 字符串截取轉(zhuǎn)日期:解鎖數(shù)據(jù)處理的關(guān)鍵技能? 在數(shù)據(jù)處理與分析工作中,數(shù)據(jù)格式的規(guī)范性是保證后續(xù)分析準(zhǔn)確性的基礎(chǔ) ...
2025-07-04CDA 數(shù)據(jù)分析師視角:從數(shù)據(jù)迷霧中探尋商業(yè)真相? 在數(shù)字化浪潮席卷全球的今天,數(shù)據(jù)已成為企業(yè)決策的核心驅(qū)動力,CDA(Certifie ...
2025-07-04CDA 數(shù)據(jù)分析師:開啟數(shù)據(jù)職業(yè)發(fā)展新征程? ? 在數(shù)據(jù)成為核心生產(chǎn)要素的今天,數(shù)據(jù)分析師的職業(yè)價值愈發(fā)凸顯。CDA(Certified D ...
2025-07-03