聯(lián)規(guī)則實戰(zhàn)：從Apriori到FP-樹頻集算法的選型與落地)
有沒有遇到過這種情況業(yè)務(wù)方丟給你一份幾十萬行的訂單流水開口就問“哪些商品經(jīng)常被一起買能不能挖出點搭配銷售的規(guī)律”你如果用Excel透視表硬扛可能折騰一整天只得到一堆沒什么解釋力的數(shù)字。這時候關(guān)聯(lián)規(guī)則就該上場了。關(guān)聯(lián)規(guī)則算是機器學習里相當經(jīng)典的一類無監(jiān)督學習方法核心任務(wù)是從交易數(shù)據(jù)、行為日志這類“事件集合”中找出高頻共現(xiàn)的模式。而提到關(guān)聯(lián)規(guī)則繞不開的兩個算法就是Apriori算法和FP-樹頻集算法FP-Growth。這篇文章不打算做教科書式的理論復(fù)述我就從實際項目里怎么用、這兩個算法各自好在哪里、坑在哪里的角度把關(guān)聯(lián)規(guī)則這件事講透。1. 關(guān)聯(lián)規(guī)則到底在解決什么問題從購物籃到用戶行為1.1 一個被反復(fù)說起的案例購物籃分析的本質(zhì)絕大多數(shù)講關(guān)聯(lián)規(guī)則的文章都會從“啤酒和尿布”的故事開始。這個故事的真實性其實一直被爭論但它能流傳這么多年確實精準說明了關(guān)聯(lián)規(guī)則的應(yīng)用場景在一個購物籃中出現(xiàn)了商品A那么商品B同時出現(xiàn)的概率是不是顯著變高了如果是那就可以據(jù)此做出商品陳列、捆綁銷售、促銷策略等業(yè)務(wù)決策。我在實際項目中接觸到的場景比“啤酒尿布”要寬泛得多。比如一個在線教育平臺用戶在一個月內(nèi)點擊了“Python入門”“數(shù)據(jù)分析實戰(zhàn)”“SQL基礎(chǔ)”三門課程這三門課之間構(gòu)成什么關(guān)系再比如一個內(nèi)容社區(qū)用戶讀了一篇“裝修避坑指南”之后會不會更大概率去讀“全屋定制選購攻略”這些都可以建模為關(guān)聯(lián)規(guī)則問題。所謂購物籃分析本質(zhì)上就是把“一個用戶的一次行為集合”看成一個“籃子”把籃子里的每一項看成“商品”。這個籃子可以是訂單也可以是會話甚至是一個時間段內(nèi)的行為序列。把數(shù)據(jù)抽象成這樣的結(jié)構(gòu)之后我們就不再被具體業(yè)務(wù)形態(tài)干擾可以用同一套算法去處理非常多的場景。1.2 三個核心指標支持度、置信度、提升度學習關(guān)聯(lián)規(guī)則第一關(guān)就是理解三個指標支持度Support、置信度Confidence、提升度Lift。很多人會背公式但真的拿到業(yè)務(wù)數(shù)據(jù)時還是搞不清楚該怎么用。我建議從業(yè)務(wù)含義去理解它們。支持度衡量一個項集比如“牛奶和面包同時出現(xiàn)”在所有訂單中的出現(xiàn)頻率。計算公式是包含該項集的訂單數(shù)除以總訂單數(shù)。支持度解決的是“這個規(guī)律到底覆蓋了多少人”的問題。如果一條規(guī)則只有5個訂單支持哪怕置信度100%也不值得投入資源。置信度表示在已經(jīng)包含前件比如牛奶的訂單中同時包含后件面包的比例。計算公式是“牛奶和面包同時出現(xiàn)的支持度”除以“牛奶出現(xiàn)的支持度”。置信度解決的是“有A時出現(xiàn)B的概率有多大”的問題它是衡量規(guī)則強度的指標。提升度這是很多人最容易忽略但最重要的指標。提升度的計算公式是規(guī)則置信度除以后件的支持度它衡量的是“A出現(xiàn)后B的概率”和“B本來就出現(xiàn)的概率”之間的比值。如果提升度大于1說明A對B有正向促進作用小于1則說明更傾向于抑制等于1則代表A和B是獨立的所謂的規(guī)則只是巧合。舉個具體的例子來說明。假設(shè)一個超市有10000條訂單其中600條包含牛奶400條包含面包同時包含兩者的有200條。那么“牛奶→面包”的支持度是2%置信度是200/600約等于33.3%而提升度是33.3%除以4%等于8.33。這個提升度意味著買了牛奶的顧客買面包的概率是普通顧客的8倍多這顯然是條強規(guī)則。1.3 為什么“相關(guān)性”不等于“因果性”這個提醒必須放在最前面。關(guān)聯(lián)規(guī)則挖掘出來的只是“共現(xiàn)關(guān)系”它描述的是“這兩個東西傾向于一起出現(xiàn)”但它完全不能證明“一個導(dǎo)致另一個”。在業(yè)務(wù)實踐中我見過很多團隊的誤用——把關(guān)聯(lián)規(guī)則的結(jié)果直接解釋成因果然后做出了錯誤的策略。舉例來說數(shù)據(jù)分析發(fā)現(xiàn)“購買嬰兒紙尿褲的用戶會在同一周內(nèi)購買啤酒”真正的解釋很可能是“購買紙尿褲的大概率是有夜間照顧嬰兒需求的中青年男性他們在采購日常用品的同時順便給自己囤了啤酒”而不是“紙尿褲導(dǎo)致啤酒購買”。這就是基于人群特征的共同驅(qū)動而不是商品間的因果鏈條。所以在向業(yè)務(wù)方輸出結(jié)果時一定要把規(guī)則描述成“在某種人群或場景下存在強共現(xiàn)關(guān)系”而不是“A導(dǎo)致B”。關(guān)聯(lián)規(guī)則是用來發(fā)現(xiàn)組合機會的不是用來做因果推斷的。2. Apriori算法先找頻繁項集再生成規(guī)則的經(jīng)典路線2.1 算法的兩步走邏輯Apriori算法的思想其實非常直白整個過程可以拆成兩大步第一步是找出所有頻繁項集第二步是從頻繁項集中生成關(guān)聯(lián)規(guī)則?！邦l繁”的定義就是支持度大于等于我們設(shè)定的最小支持度閾值。比如設(shè)定最小支持度0.02那么在所有訂單中出現(xiàn)次數(shù)至少達到總數(shù)2%的商品集合就是頻繁項集。Apriori算法的核心操作是一個逐層遞推的過程先生成所有單商品項集1項集篩選出滿足最小支持度的然后基于頻繁1項集兩兩組合生成2項集再篩選生成3項集再篩選……直到無法生成新的頻繁項集為止。這里的“生成候選集”是一個組合爆炸的過程如果商品種類有1000種那2項集就有約50萬種3項集更是上億量級。如果沒有優(yōu)化機制普通機器根本跑不動。Apriori的聰明之處就在于它有一條非常重要的性質(zhì)——Apriori性質(zhì)。2.2 剪枝策略Apriori性質(zhì)與其推導(dǎo)Apriori性質(zhì)用一句話概括就是如果一個項集是頻繁的那么它的所有子集都是頻繁的反過來如果一個項集是非頻繁的那么它的所有超集都是非頻繁的。這個性質(zhì)看起來像廢話但它提供了一把極強的剪枝剪刀。假設(shè)“牛奶”本身不是頻繁項出現(xiàn)次數(shù)太少那么在生成2項集時所有包含“牛奶”的組合比如“牛奶面包”“牛奶蘋果”都可以直接扔掉根本不需要去統(tǒng)計它們的支持度。這就砍掉了大量的無效計算。在候選集生成的過程中還有一個可以優(yōu)化的點生成k1項集的候選項時只從“前k-1項相同”的頻繁k項集中做合并這樣能保證不會生成重復(fù)的組合同時確保新候選集的所有k-1項子集都已經(jīng)是頻繁的。正是這個“先剪枝再計數(shù)”的思路讓Apriori成為那個年代最有效的關(guān)聯(lián)規(guī)則挖掘算法。我在實現(xiàn)的時候會特別強調(diào)這個性質(zhì)因為很多初學者會忽略它直接做全量組合結(jié)果就是內(nèi)存爆炸、跑半天出不來根本沒有理解算法的精髓。2.3 一個可以跑起來的最小實現(xiàn)mlxtend在Python里我并不推薦從零手寫Apriori的底層代碼除非你是為了學習或者研究目的。工業(yè)場景下直接使用mlxtend庫就夠了它封裝了一套非常干凈的關(guān)聯(lián)規(guī)則挖掘接口。首先準備數(shù)據(jù)。關(guān)聯(lián)規(guī)則的標準輸入是一個“事務(wù)”列表每行代表一個訂單每行的內(nèi)容是商品集合。import pandas as pd from mlxtend.preprocessing import TransactionEncoder from mlxtend.frequent_patterns import apriori from mlxtend.frequent_patterns import association_rules # 模擬一組訂單數(shù)據(jù) dataset [ [牛奶, 面包, 黃油], [牛奶, 面包], [啤酒, 尿布], [牛奶, 尿布, 啤酒], [面包, 黃油], [牛奶, 面包, 尿布], [啤酒, 尿布], ] # 將事務(wù)數(shù)據(jù)轉(zhuǎn)換為one-hot編碼的DataFrame te TransactionEncoder() te_ary te.fit(dataset).transform(dataset) df pd.DataFrame(te_ary, columnste.columns_) # 跑Apriori最小支持度設(shè)為0.2 frequent_itemsets apriori(df, min_support0.2, use_colnamesTrue) print(frequent_itemsets)接下來從頻繁項集生成規(guī)則并按照提升度排序rules association_rules(frequent_itemsets, metriclift, min_threshold1.0) rules.sort_values(lift, ascendingFalse, inplaceTrue) print(rules[[antecedents, consequents, support, confidence, lift]])這段代碼就能完成一次完整的Apriori挖掘。輸出結(jié)果里有幾個要注意的地方use_colnamesTrue是為了讓項集顯示為商品名稱而不是數(shù)字編號association_rules里的metriclift是篩選規(guī)則的最常用方式實際項目中我一般至少把提升度閾值設(shè)在1.5以上否則噪聲太多。2.4 Apriori的瓶頸為什么數(shù)據(jù)稍大就變慢Apriori算法夠經(jīng)典但它的弱點也非常明顯。它需要多次掃描全量數(shù)據(jù)集每生成一層的候選項集就要掃一次數(shù)據(jù)庫。假設(shè)最長的頻繁項集長度為L那就要掃描L次。在數(shù)據(jù)量幾十萬上百萬條交易時I/O開銷就很可觀了。另一個問題是候選項集的數(shù)量依然可能很大。剪枝能去掉一部分但組合的基數(shù)擺在那里特別是商品種類多、數(shù)據(jù)稀疏的時候候選集的生成和計數(shù)仍然非常耗時。我在一個幾十萬訂單的數(shù)據(jù)集上實測過商品種類約5000種時Apriori跑完的耗時要幾十秒到幾分鐘這還算可以接受。但如果商品種類上到幾萬、訂單量上到幾百萬Apriori就有點扛不住了。這時候就該把目光轉(zhuǎn)向FP-樹頻集算法。3. FP-樹頻集算法從“多次掃描”到“一次構(gòu)建”的優(yōu)化思路3.1 FP樹的構(gòu)建過程拆解FP-樹頻集算法通常直接叫FP-Growth它的核心思路和Apriori完全不同。Apriori是“生成候選集掃描驗證”FP-Growth則是“壓縮數(shù)據(jù)到內(nèi)存中的樹結(jié)構(gòu)遞歸挖掘”。FP-Growth只需要掃描數(shù)據(jù)庫兩次這是它性能碾壓Apriori的關(guān)鍵。第一次掃描統(tǒng)計每個商品的支持度過濾掉不滿足最小支持度的商品然后按照支持度從高到低排序。第二次掃描逐行處理每條交易把交易中出現(xiàn)且頻繁的商品按照全局頻率降序插入到一棵FP樹中同時在節(jié)點上累加計數(shù)。把事務(wù)壓縮進樹后每個項集的所有必要信息都保存在了樹和頭指針表中不需要再反復(fù)回到原始數(shù)據(jù)里去數(shù)次數(shù)。用一個小例子說明。假設(shè)有三條交易(魚, 牛奶, 面包)、(面包, 牛奶)、(魚, 面包)最小支持度為1。第一次統(tǒng)計得到魚出現(xiàn)2次、面包3次、牛奶2次都是頻繁的排序順序為面包、魚、牛奶按頻次降序。第二條交易插入了面包和牛奶第三條插入面包和魚。最終樹的結(jié)構(gòu)是根節(jié)點下有面包計數(shù)3面包節(jié)點下有兩個分支牛奶計數(shù)2和魚計數(shù)1牛奶下還有魚計數(shù)1。路徑面包→魚和面包→牛奶→魚共享了節(jié)點“面包”這就壓縮了數(shù)據(jù)量。整個樹的結(jié)構(gòu)記錄了所有頻繁模式的關(guān)鍵信息。3.2 從FP樹挖掘頻繁項集條件模式基與遞歸生長構(gòu)建完FP樹接下來就是遞歸挖掘的過程。FP-Growth的挖掘策略不像Apriori那樣顯式枚舉候選集而是通過構(gòu)造條件模式基Conditional Pattern Base來逐步生長頻繁項集。以經(jīng)常被一起買的“牛奶魚”為例。要找到所有包含“牛奶”的頻繁項集需要先找到FP樹中所有包含“牛奶”的路徑即牛奶的前綴路徑。每條路徑上都帶著計數(shù)信息——路徑中每個節(jié)點恰好出現(xiàn)了多少次。把相同前綴路徑的計數(shù)累加就得到了“牛奶的條件模式基”?；跅l件模式基可以構(gòu)建一棵“牛奶的條件FP樹”。在條件FP樹上繼續(xù)遞歸挖掘把新挖掘到的節(jié)點和原模式合并就得到了更長的頻繁項集。整個過程沒有任何重復(fù)掃描原數(shù)據(jù)全部在樹結(jié)構(gòu)上完成。理解FP-Growth的難點在于“遞歸生長”的抽象感。我個人的學習經(jīng)驗是先手工跑一遍小規(guī)模數(shù)據(jù)的挖掘過程把每一層的條件模式基畫出來然后再回來看代碼會順暢很多。這類算法的遞歸邏輯用空想來理解很容易繞暈。3.3 用同一份數(shù)據(jù)實測FP-Growthmlxtend同樣封裝了FP-Growth的實現(xiàn)接口和Apriori幾乎一致替換起來非常方便。from mlxtend.frequent_patterns import fpgrowth # 使用相同的數(shù)據(jù)格式 frequent_itemsets_fp fpgrowth(df, min_support0.2, use_colnamesTrue) print(frequent_itemsets_fp) # 生成規(guī)則 rules_fp association_rules(frequent_itemsets_fp, metriclift, min_threshold1.0) rules_fp.sort_values(lift, ascendingFalse, inplaceTrue) print(rules_fp[[antecedents, consequents, support, confidence, lift]])在數(shù)據(jù)規(guī)模較小時兩者的結(jié)果幾乎一致。但到幾十萬條交易、商品上萬的數(shù)據(jù)集上FP-Growth通常比Apriori快一到兩個數(shù)量級。我跑過的最典型的一個對比是Apriori需要40秒才能完成的挖掘任務(wù)FP-Growth大概3秒就出來了差別非常直觀。值得注意的是有少數(shù)的數(shù)據(jù)分布場景下兩者差距沒有這么明顯比如頻繁項集非常短所有項集長度都在2以內(nèi)的時候Apriori的多次掃描開銷并不大差距就不顯著。但從實際經(jīng)驗看大多數(shù)業(yè)務(wù)數(shù)據(jù)都是長尾分布FP-Growth的優(yōu)勢是壓倒性的。3.4 結(jié)構(gòu)設(shè)計背后的工程考量FP-Growth真正聰明的地方是它構(gòu)建了一棵高度壓縮的前綴樹。這棵樹能把共享前綴的交易合并存儲從而大幅減少內(nèi)存占用。比如有一萬條交易都包含面包但后面的搭配各不相同在FP樹里面包節(jié)點只出現(xiàn)一次后面的分支再分別延伸。這種做法非常契合真實業(yè)務(wù)數(shù)據(jù)的特點頭部商品高度集中長尾商品稀疏分散。FP樹利用的就是這個分布特征。另外FP-Growth在挖掘過程中也展現(xiàn)出良好的模塊化特性。每一個條件FP樹的構(gòu)建和挖掘都是獨立的天然適合并行化處理。在大數(shù)據(jù)場景下可以先對不同商品的條件模式基做分區(qū)再用分布式計算來加速。這一點在單機版的Apriori中是很難做到的。4. 兩個算法怎么選業(yè)務(wù)場景、數(shù)據(jù)規(guī)模和工程成本的權(quán)衡4.1 兩個算法的對比表格很多人在學習階段糾結(jié)“到底用哪個”實際上工程上的答案很明確默認用FP-Growth。但搞清楚兩者的區(qū)別依然非常重要因為在某些特定條件下Apriori反而更有優(yōu)勢。維度AprioriFP-Growth核心思想候選集生成 逐層篩選前綴樹壓縮 遞歸挖掘掃描次數(shù)多次頻繁項集層數(shù)兩次內(nèi)存占用候選集常駐內(nèi)存開銷較大FP樹結(jié)構(gòu)較為緊湊但條件庫也占內(nèi)存適用數(shù)據(jù)量中小數(shù)據(jù)集幾千到幾十萬中到大規(guī)模數(shù)據(jù)集百萬級實現(xiàn)復(fù)雜度邏輯簡單易理解樹構(gòu)建和遞歸較復(fù)雜算法效果結(jié)果一致結(jié)果一致有一點要特別說明兩個算法挖掘的頻繁項集在相同支持度閾值下是完全一致的差異只體現(xiàn)在效率和資源開銷上。所以選型時不需要擔心結(jié)果質(zhì)量不同只需要考慮計算資源。4.2 不同數(shù)據(jù)規(guī)模下的實測感受我個人的選型經(jīng)驗大致是這樣的。數(shù)據(jù)量在1萬條訂單以內(nèi)商品種類不超過幾百個Apriori和FP-Growth的耗時幾乎都是毫秒到秒級。這時候想用哪個就用哪個我通常會選擇Apriori做快速驗證因為代碼邏輯更直白出了問題好查。數(shù)據(jù)量到了10萬到100萬條交易、商品種類幾千的時候我會毫不猶豫地選擇FP-Growth。內(nèi)存方面也要心里有數(shù)如果商品種類特別多、交易特別長FP樹的條件模式基可能會占用大量內(nèi)存必要的時候得調(diào)大JVM或Python進程的可用內(nèi)存。數(shù)據(jù)量上到千萬級甚至更大單機已經(jīng)很難支撐此時要考慮分布式方案。業(yè)界成熟的工具比如Spark的FP-Growth實現(xiàn)也是基于同樣的樹結(jié)構(gòu)思路去分布式化的。這種情況下Apriori基本沒有登場機會。4.3 規(guī)則篩選與業(yè)務(wù)落地的常見坑算法跑完只是第一步真正的難點在于從一大堆規(guī)則中淘出有價值的那幾條。我在實踐中總結(jié)下來規(guī)則篩選至少要過三道關(guān)。第一道關(guān)是統(tǒng)計顯著性。提升度大于1只是說正面關(guān)聯(lián)比隨機共現(xiàn)高但樣本量過小時這個“高”可能完全來自波動。所以要額外關(guān)注支持度絕對值——一條規(guī)則至少要有幾十個以上的訂單做支撐否則不可信。比如支持度0.001看起來很合理但如果總共10000個訂單那只有10個訂單在支撐噪聲風險極高。第二道關(guān)是業(yè)務(wù)合理性。很多挖掘出的強規(guī)則其實是冗余的。比如“牛奶→乳制品”這種規(guī)則完全沒有指導(dǎo)意義因為后件是前件的超集。更麻煩的是“交叉持單”規(guī)則比如“A平臺優(yōu)惠券→B平臺使用”這可能是同一用戶在兩個平臺之間的自然流轉(zhuǎn)而并非主導(dǎo)關(guān)系。規(guī)則落地前需要業(yè)務(wù)方一起判斷信息的可執(zhí)行性。第三道關(guān)是動作閉環(huán)。一條規(guī)則要能變成業(yè)務(wù)策略必須能轉(zhuǎn)化成具體的觸發(fā)動作。比如“買了嬰兒車的用戶有較高概率購買嬰兒座椅”那么動作就是在購物車結(jié)算頁對購買嬰兒車的用戶彈嬰兒座椅的推薦。如果規(guī)則本身沒法映射到一個清晰的觸點上挖掘得再準也是廢的。4.4 一個完整的簡單分析流程示例最后用一個完整的流程把這些串起來。假設(shè)手頭有一個電商訂單表字段是order_id和product_name任務(wù)是想找出“搭配購買”的機會。第一步是數(shù)據(jù)預(yù)處理把明細表聚合成事務(wù)列表每一行為一個訂單包含的商品集合。這里有兩點要注意一是確認是否需要做類別合并比如“牛奶”和“脫脂牛奶”是放在一起分析還是分開分析二是決定要不要對高銷量商品做降采樣否則它們會“霸屏”。第二步是調(diào)參跑模型。先用一個相對寬松的最小支持度比如0.005跑一輪看看項集分布再根據(jù)結(jié)果調(diào)。我一般會從支持度0.01、置信度0.5、提升度1.5起步然后根據(jù)規(guī)則數(shù)量調(diào)整。規(guī)則過多就收緊支持度過少就放寬。第三步是寫一個簡單的挑選函數(shù)按業(yè)務(wù)邏輯過濾掉同質(zhì)規(guī)則。比如計算前后件是否有包含關(guān)系或者是否屬于同一個品類。第四步是把通過篩選的規(guī)則輸出成一張報告表格配兩三個典型的商品組合案例一起提交給業(yè)務(wù)方讓業(yè)務(wù)方判斷是否有進一步做捆綁促銷或商品推薦的價值。這套流程我反復(fù)用過很多次從技術(shù)實現(xiàn)上并不復(fù)雜難點全在數(shù)據(jù)理解和業(yè)務(wù)判斷上。建議初次接觸關(guān)聯(lián)規(guī)則的朋友先拿一份真實的訂單流水完整跑一遍不要用太干凈的演示數(shù)據(jù)。數(shù)據(jù)一臟你就能深刻理解為什么要花那么多時間做預(yù)處理了。5. 寫在最后的幾條實際經(jīng)驗回頭再看關(guān)聯(lián)規(guī)則這件事它之所以到現(xiàn)在還沒被深度學習那套東西沖擊掉原因其實很簡單它是一種自帶解釋性的方法。輸出的是“前提→結(jié)論”形式的規(guī)則業(yè)務(wù)方一看就懂不像神經(jīng)網(wǎng)絡(luò)給出一堆特征權(quán)重讓人摸不著頭腦。我個人在實戰(zhàn)中還有幾條小經(jīng)驗值得分享。第一最小支持度的選擇不要拍腦袋可以先統(tǒng)計一下單商品的支持度分布取中位數(shù)附近的值作為起調(diào)點。第二FP-Growth跑出來的結(jié)果如果條數(shù)太多優(yōu)先去檢查數(shù)據(jù)質(zhì)量而不是繼續(xù)壓縮閾值很多“強規(guī)則”其實是重復(fù)錄入、別名亂造或者刷單造成的假象。第三年度大促期間的數(shù)據(jù)和日常運營數(shù)據(jù)混在一起時最好按活動周期分開挖掘因為大促期間的用戶行為模式和非大促期間差異極大混在一起容易得到不符合日常規(guī)律的規(guī)則。如果非要在Apriori和FP-樹頻集算法里選一個入門我會建議新手先把Apriori弄懂因為它幫你建立“項集—支持度—置信度—提升度”這個基本框架實際干活的時候再用FP-Growth去跑大數(shù)據(jù)。這個組合是最穩(wěn)妥的路徑既能理解原理又能解決問題。 關(guān)聯(lián)規(guī)則實戰(zhàn)：從Apriori到FP-樹頻集算法的選型與落地
有沒有遇到過這種情況業(yè)務(wù)方丟給你一份幾十萬行的訂單流水開口就問“哪些商品經(jīng)常被一起買能不能挖出點搭配銷售的規(guī)律”你如果用Excel透視表硬扛可能折騰一整天只得到一堆沒什么解釋力的數(shù)字。這時候關(guān)聯(lián)規(guī)則就該上場了。關(guān)聯(lián)規(guī)則算是機器學習里相當經(jīng)典的一類無監(jiān)督學習方法核心任務(wù)是從交易數(shù)據(jù)、行為日志這類“事件集合”中找出高頻共現(xiàn)的模式。而提到關(guān)聯(lián)規(guī)則繞不開的兩個算法就是Apriori算法和FP-樹頻集算法FP-Growth。這篇文章不打算做教科書式的理論復(fù)述我就從實際項目里怎么用、這兩個算法各自好在哪里、坑在哪里的角度把關(guān)聯(lián)規(guī)則這件事講透。1. 關(guān)聯(lián)規(guī)則到底在解決什么問題從購物籃到用戶行為1.1 一個被反復(fù)說起的案例購物籃分析的本質(zhì)絕大多數(shù)講關(guān)聯(lián)規(guī)則的文章都會從“啤酒和尿布”的故事開始。這個故事的真實性其實一直被爭論但它能流傳這么多年確實精準說明了關(guān)聯(lián)規(guī)則的應(yīng)用場景在一個購物籃中出現(xiàn)了商品A那么商品B同時出現(xiàn)的概率是不是顯著變高了如果是那就可以據(jù)此做出商品陳列、捆綁銷售、促銷策略等業(yè)務(wù)決策。我在實際項目中接觸到的場景比“啤酒尿布”要寬泛得多。比如一個在線教育平臺用戶在一個月內(nèi)點擊了“Python入門”“數(shù)據(jù)分析實戰(zhàn)”“SQL基礎(chǔ)”三門課程這三門課之間構(gòu)成什么關(guān)系再比如一個內(nèi)容社區(qū)用戶讀了一篇“裝修避坑指南”之后會不會更大概率去讀“全屋定制選購攻略”這些都可以建模為關(guān)聯(lián)規(guī)則問題。所謂購物籃分析本質(zhì)上就是把“一個用戶的一次行為集合”看成一個“籃子”把籃子里的每一項看成“商品”。這個籃子可以是訂單也可以是會話甚至是一個時間段內(nèi)的行為序列。把數(shù)據(jù)抽象成這樣的結(jié)構(gòu)之后我們就不再被具體業(yè)務(wù)形態(tài)干擾可以用同一套算法去處理非常多的場景。1.2 三個核心指標支持度、置信度、提升度學習關(guān)聯(lián)規(guī)則第一關(guān)就是理解三個指標支持度Support、置信度Confidence、提升度Lift。很多人會背公式但真的拿到業(yè)務(wù)數(shù)據(jù)時還是搞不清楚該怎么用。我建議從業(yè)務(wù)含義去理解它們。支持度衡量一個項集比如“牛奶和面包同時出現(xiàn)”在所有訂單中的出現(xiàn)頻率。計算公式是包含該項集的訂單數(shù)除以總訂單數(shù)。支持度解決的是“這個規(guī)律到底覆蓋了多少人”的問題。如果一條規(guī)則只有5個訂單支持哪怕置信度100%也不值得投入資源。置信度表示在已經(jīng)包含前件比如牛奶的訂單中同時包含后件面包的比例。計算公式是“牛奶和面包同時出現(xiàn)的支持度”除以“牛奶出現(xiàn)的支持度”。置信度解決的是“有A時出現(xiàn)B的概率有多大”的問題它是衡量規(guī)則強度的指標。提升度這是很多人最容易忽略但最重要的指標。提升度的計算公式是規(guī)則置信度除以后件的支持度它衡量的是“A出現(xiàn)后B的概率”和“B本來就出現(xiàn)的概率”之間的比值。如果提升度大于1說明A對B有正向促進作用小于1則說明更傾向于抑制等于1則代表A和B是獨立的所謂的規(guī)則只是巧合。舉個具體的例子來說明。假設(shè)一個超市有10000條訂單其中600條包含牛奶400條包含面包同時包含兩者的有200條。那么“牛奶→面包”的支持度是2%置信度是200/600約等于33.3%而提升度是33.3%除以4%等于8.33。這個提升度意味著買了牛奶的顧客買面包的概率是普通顧客的8倍多這顯然是條強規(guī)則。1.3 為什么“相關(guān)性”不等于“因果性”這個提醒必須放在最前面。關(guān)聯(lián)規(guī)則挖掘出來的只是“共現(xiàn)關(guān)系”它描述的是“這兩個東西傾向于一起出現(xiàn)”但它完全不能證明“一個導(dǎo)致另一個”。在業(yè)務(wù)實踐中我見過很多團隊的誤用——把關(guān)聯(lián)規(guī)則的結(jié)果直接解釋成因果然后做出了錯誤的策略。舉例來說數(shù)據(jù)分析發(fā)現(xiàn)“購買嬰兒紙尿褲的用戶會在同一周內(nèi)購買啤酒”真正的解釋很可能是“購買紙尿褲的大概率是有夜間照顧嬰兒需求的中青年男性他們在采購日常用品的同時順便給自己囤了啤酒”而不是“紙尿褲導(dǎo)致啤酒購買”。這就是基于人群特征的共同驅(qū)動而不是商品間的因果鏈條。所以在向業(yè)務(wù)方輸出結(jié)果時一定要把規(guī)則描述成“在某種人群或場景下存在強共現(xiàn)關(guān)系”而不是“A導(dǎo)致B”。關(guān)聯(lián)規(guī)則是用來發(fā)現(xiàn)組合機會的不是用來做因果推斷的。2. Apriori算法先找頻繁項集再生成規(guī)則的經(jīng)典路線2.1 算法的兩步走邏輯Apriori算法的思想其實非常直白整個過程可以拆成兩大步第一步是找出所有頻繁項集第二步是從頻繁項集中生成關(guān)聯(lián)規(guī)則?！邦l繁”的定義就是支持度大于等于我們設(shè)定的最小支持度閾值。比如設(shè)定最小支持度0.02那么在所有訂單中出現(xiàn)次數(shù)至少達到總數(shù)2%的商品集合就是頻繁項集。Apriori算法的核心操作是一個逐層遞推的過程先生成所有單商品項集1項集篩選出滿足最小支持度的然后基于頻繁1項集兩兩組合生成2項集再篩選生成3項集再篩選……直到無法生成新的頻繁項集為止。這里的“生成候選集”是一個組合爆炸的過程如果商品種類有1000種那2項集就有約50萬種3項集更是上億量級。如果沒有優(yōu)化機制普通機器根本跑不動。Apriori的聰明之處就在于它有一條非常重要的性質(zhì)——Apriori性質(zhì)。2.2 剪枝策略Apriori性質(zhì)與其推導(dǎo)Apriori性質(zhì)用一句話概括就是如果一個項集是頻繁的那么它的所有子集都是頻繁的反過來如果一個項集是非頻繁的那么它的所有超集都是非頻繁的。這個性質(zhì)看起來像廢話但它提供了一把極強的剪枝剪刀。假設(shè)“牛奶”本身不是頻繁項出現(xiàn)次數(shù)太少那么在生成2項集時所有包含“牛奶”的組合比如“牛奶面包”“牛奶蘋果”都可以直接扔掉根本不需要去統(tǒng)計它們的支持度。這就砍掉了大量的無效計算。在候選集生成的過程中還有一個可以優(yōu)化的點生成k1項集的候選項時只從“前k-1項相同”的頻繁k項集中做合并這樣能保證不會生成重復(fù)的組合同時確保新候選集的所有k-1項子集都已經(jīng)是頻繁的。正是這個“先剪枝再計數(shù)”的思路讓Apriori成為那個年代最有效的關(guān)聯(lián)規(guī)則挖掘算法。我在實現(xiàn)的時候會特別強調(diào)這個性質(zhì)因為很多初學者會忽略它直接做全量組合結(jié)果就是內(nèi)存爆炸、跑半天出不來根本沒有理解算法的精髓。2.3 一個可以跑起來的最小實現(xiàn)mlxtend在Python里我并不推薦從零手寫Apriori的底層代碼除非你是為了學習或者研究目的。工業(yè)場景下直接使用mlxtend庫就夠了它封裝了一套非常干凈的關(guān)聯(lián)規(guī)則挖掘接口。首先準備數(shù)據(jù)。關(guān)聯(lián)規(guī)則的標準輸入是一個“事務(wù)”列表每行代表一個訂單每行的內(nèi)容是商品集合。import pandas as pd from mlxtend.preprocessing import TransactionEncoder from mlxtend.frequent_patterns import apriori from mlxtend.frequent_patterns import association_rules # 模擬一組訂單數(shù)據(jù) dataset [ [牛奶, 面包, 黃油], [牛奶, 面包], [啤酒, 尿布], [牛奶, 尿布, 啤酒], [面包, 黃油], [牛奶, 面包, 尿布], [啤酒, 尿布], ] # 將事務(wù)數(shù)據(jù)轉(zhuǎn)換為one-hot編碼的DataFrame te TransactionEncoder() te_ary te.fit(dataset).transform(dataset) df pd.DataFrame(te_ary, columnste.columns_) # 跑Apriori最小支持度設(shè)為0.2 frequent_itemsets apriori(df, min_support0.2, use_colnamesTrue) print(frequent_itemsets)接下來從頻繁項集生成規(guī)則并按照提升度排序rules association_rules(frequent_itemsets, metriclift, min_threshold1.0) rules.sort_values(lift, ascendingFalse, inplaceTrue) print(rules[[antecedents, consequents, support, confidence, lift]])這段代碼就能完成一次完整的Apriori挖掘。輸出結(jié)果里有幾個要注意的地方use_colnamesTrue是為了讓項集顯示為商品名稱而不是數(shù)字編號association_rules里的metriclift是篩選規(guī)則的最常用方式實際項目中我一般至少把提升度閾值設(shè)在1.5以上否則噪聲太多。2.4 Apriori的瓶頸為什么數(shù)據(jù)稍大就變慢Apriori算法夠經(jīng)典但它的弱點也非常明顯。它需要多次掃描全量數(shù)據(jù)集每生成一層的候選項集就要掃一次數(shù)據(jù)庫。假設(shè)最長的頻繁項集長度為L那就要掃描L次。在數(shù)據(jù)量幾十萬上百萬條交易時I/O開銷就很可觀了。另一個問題是候選項集的數(shù)量依然可能很大。剪枝能去掉一部分但組合的基數(shù)擺在那里特別是商品種類多、數(shù)據(jù)稀疏的時候候選集的生成和計數(shù)仍然非常耗時。我在一個幾十萬訂單的數(shù)據(jù)集上實測過商品種類約5000種時Apriori跑完的耗時要幾十秒到幾分鐘這還算可以接受。但如果商品種類上到幾萬、訂單量上到幾百萬Apriori就有點扛不住了。這時候就該把目光轉(zhuǎn)向FP-樹頻集算法。3. FP-樹頻集算法從“多次掃描”到“一次構(gòu)建”的優(yōu)化思路3.1 FP樹的構(gòu)建過程拆解FP-樹頻集算法通常直接叫FP-Growth它的核心思路和Apriori完全不同。Apriori是“生成候選集掃描驗證”FP-Growth則是“壓縮數(shù)據(jù)到內(nèi)存中的樹結(jié)構(gòu)遞歸挖掘”。FP-Growth只需要掃描數(shù)據(jù)庫兩次這是它性能碾壓Apriori的關(guān)鍵。第一次掃描統(tǒng)計每個商品的支持度過濾掉不滿足最小支持度的商品然后按照支持度從高到低排序。第二次掃描逐行處理每條交易把交易中出現(xiàn)且頻繁的商品按照全局頻率降序插入到一棵FP樹中同時在節(jié)點上累加計數(shù)。把事務(wù)壓縮進樹后每個項集的所有必要信息都保存在了樹和頭指針表中不需要再反復(fù)回到原始數(shù)據(jù)里去數(shù)次數(shù)。用一個小例子說明。假設(shè)有三條交易(魚, 牛奶, 面包)、(面包, 牛奶)、(魚, 面包)最小支持度為1。第一次統(tǒng)計得到魚出現(xiàn)2次、面包3次、牛奶2次都是頻繁的排序順序為面包、魚、牛奶按頻次降序。第二條交易插入了面包和牛奶第三條插入面包和魚。最終樹的結(jié)構(gòu)是根節(jié)點下有面包計數(shù)3面包節(jié)點下有兩個分支牛奶計數(shù)2和魚計數(shù)1牛奶下還有魚計數(shù)1。路徑面包→魚和面包→牛奶→魚共享了節(jié)點“面包”這就壓縮了數(shù)據(jù)量。整個樹的結(jié)構(gòu)記錄了所有頻繁模式的關(guān)鍵信息。3.2 從FP樹挖掘頻繁項集條件模式基與遞歸生長構(gòu)建完FP樹接下來就是遞歸挖掘的過程。FP-Growth的挖掘策略不像Apriori那樣顯式枚舉候選集而是通過構(gòu)造條件模式基Conditional Pattern Base來逐步生長頻繁項集。以經(jīng)常被一起買的“牛奶魚”為例。要找到所有包含“牛奶”的頻繁項集需要先找到FP樹中所有包含“牛奶”的路徑即牛奶的前綴路徑。每條路徑上都帶著計數(shù)信息——路徑中每個節(jié)點恰好出現(xiàn)了多少次。把相同前綴路徑的計數(shù)累加就得到了“牛奶的條件模式基”?；跅l件模式基可以構(gòu)建一棵“牛奶的條件FP樹”。在條件FP樹上繼續(xù)遞歸挖掘把新挖掘到的節(jié)點和原模式合并就得到了更長的頻繁項集。整個過程沒有任何重復(fù)掃描原數(shù)據(jù)全部在樹結(jié)構(gòu)上完成。理解FP-Growth的難點在于“遞歸生長”的抽象感。我個人的學習經(jīng)驗是先手工跑一遍小規(guī)模數(shù)據(jù)的挖掘過程把每一層的條件模式基畫出來然后再回來看代碼會順暢很多。這類算法的遞歸邏輯用空想來理解很容易繞暈。3.3 用同一份數(shù)據(jù)實測FP-Growthmlxtend同樣封裝了FP-Growth的實現(xiàn)接口和Apriori幾乎一致替換起來非常方便。from mlxtend.frequent_patterns import fpgrowth # 使用相同的數(shù)據(jù)格式 frequent_itemsets_fp fpgrowth(df, min_support0.2, use_colnamesTrue) print(frequent_itemsets_fp) # 生成規(guī)則 rules_fp association_rules(frequent_itemsets_fp, metriclift, min_threshold1.0) rules_fp.sort_values(lift, ascendingFalse, inplaceTrue) print(rules_fp[[antecedents, consequents, support, confidence, lift]])在數(shù)據(jù)規(guī)模較小時兩者的結(jié)果幾乎一致。但到幾十萬條交易、商品上萬的數(shù)據(jù)集上FP-Growth通常比Apriori快一到兩個數(shù)量級。我跑過的最典型的一個對比是Apriori需要40秒才能完成的挖掘任務(wù)FP-Growth大概3秒就出來了差別非常直觀。值得注意的是有少數(shù)的數(shù)據(jù)分布場景下兩者差距沒有這么明顯比如頻繁項集非常短所有項集長度都在2以內(nèi)的時候Apriori的多次掃描開銷并不大差距就不顯著。但從實際經(jīng)驗看大多數(shù)業(yè)務(wù)數(shù)據(jù)都是長尾分布FP-Growth的優(yōu)勢是壓倒性的。3.4 結(jié)構(gòu)設(shè)計背后的工程考量FP-Growth真正聰明的地方是它構(gòu)建了一棵高度壓縮的前綴樹。這棵樹能把共享前綴的交易合并存儲從而大幅減少內(nèi)存占用。比如有一萬條交易都包含面包但后面的搭配各不相同在FP樹里面包節(jié)點只出現(xiàn)一次后面的分支再分別延伸。這種做法非常契合真實業(yè)務(wù)數(shù)據(jù)的特點頭部商品高度集中長尾商品稀疏分散。FP樹利用的就是這個分布特征。另外FP-Growth在挖掘過程中也展現(xiàn)出良好的模塊化特性。每一個條件FP樹的構(gòu)建和挖掘都是獨立的天然適合并行化處理。在大數(shù)據(jù)場景下可以先對不同商品的條件模式基做分區(qū)再用分布式計算來加速。這一點在單機版的Apriori中是很難做到的。4. 兩個算法怎么選業(yè)務(wù)場景、數(shù)據(jù)規(guī)模和工程成本的權(quán)衡4.1 兩個算法的對比表格很多人在學習階段糾結(jié)“到底用哪個”實際上工程上的答案很明確默認用FP-Growth。但搞清楚兩者的區(qū)別依然非常重要因為在某些特定條件下Apriori反而更有優(yōu)勢。維度AprioriFP-Growth核心思想候選集生成 逐層篩選前綴樹壓縮 遞歸挖掘掃描次數(shù)多次頻繁項集層數(shù)兩次內(nèi)存占用候選集常駐內(nèi)存開銷較大FP樹結(jié)構(gòu)較為緊湊但條件庫也占內(nèi)存適用數(shù)據(jù)量中小數(shù)據(jù)集幾千到幾十萬中到大規(guī)模數(shù)據(jù)集百萬級實現(xiàn)復(fù)雜度邏輯簡單易理解樹構(gòu)建和遞歸較復(fù)雜算法效果結(jié)果一致結(jié)果一致有一點要特別說明兩個算法挖掘的頻繁項集在相同支持度閾值下是完全一致的差異只體現(xiàn)在效率和資源開銷上。所以選型時不需要擔心結(jié)果質(zhì)量不同只需要考慮計算資源。4.2 不同數(shù)據(jù)規(guī)模下的實測感受我個人的選型經(jīng)驗大致是這樣的。數(shù)據(jù)量在1萬條訂單以內(nèi)商品種類不超過幾百個Apriori和FP-Growth的耗時幾乎都是毫秒到秒級。這時候想用哪個就用哪個我通常會選擇Apriori做快速驗證因為代碼邏輯更直白出了問題好查。數(shù)據(jù)量到了10萬到100萬條交易、商品種類幾千的時候我會毫不猶豫地選擇FP-Growth。內(nèi)存方面也要心里有數(shù)如果商品種類特別多、交易特別長FP樹的條件模式基可能會占用大量內(nèi)存必要的時候得調(diào)大JVM或Python進程的可用內(nèi)存。數(shù)據(jù)量上到千萬級甚至更大單機已經(jīng)很難支撐此時要考慮分布式方案。業(yè)界成熟的工具比如Spark的FP-Growth實現(xiàn)也是基于同樣的樹結(jié)構(gòu)思路去分布式化的。這種情況下Apriori基本沒有登場機會。4.3 規(guī)則篩選與業(yè)務(wù)落地的常見坑算法跑完只是第一步真正的難點在于從一大堆規(guī)則中淘出有價值的那幾條。我在實踐中總結(jié)下來規(guī)則篩選至少要過三道關(guān)。第一道關(guān)是統(tǒng)計顯著性。提升度大于1只是說正面關(guān)聯(lián)比隨機共現(xiàn)高但樣本量過小時這個“高”可能完全來自波動。所以要額外關(guān)注支持度絕對值——一條規(guī)則至少要有幾十個以上的訂單做支撐否則不可信。比如支持度0.001看起來很合理但如果總共10000個訂單那只有10個訂單在支撐噪聲風險極高。第二道關(guān)是業(yè)務(wù)合理性。很多挖掘出的強規(guī)則其實是冗余的。比如“牛奶→乳制品”這種規(guī)則完全沒有指導(dǎo)意義因為后件是前件的超集。更麻煩的是“交叉持單”規(guī)則比如“A平臺優(yōu)惠券→B平臺使用”這可能是同一用戶在兩個平臺之間的自然流轉(zhuǎn)而并非主導(dǎo)關(guān)系。規(guī)則落地前需要業(yè)務(wù)方一起判斷信息的可執(zhí)行性。第三道關(guān)是動作閉環(huán)。一條規(guī)則要能變成業(yè)務(wù)策略必須能轉(zhuǎn)化成具體的觸發(fā)動作。比如“買了嬰兒車的用戶有較高概率購買嬰兒座椅”那么動作就是在購物車結(jié)算頁對購買嬰兒車的用戶彈嬰兒座椅的推薦。如果規(guī)則本身沒法映射到一個清晰的觸點上挖掘得再準也是廢的。4.4 一個完整的簡單分析流程示例最后用一個完整的流程把這些串起來。假設(shè)手頭有一個電商訂單表字段是order_id和product_name任務(wù)是想找出“搭配購買”的機會。第一步是數(shù)據(jù)預(yù)處理把明細表聚合成事務(wù)列表每一行為一個訂單包含的商品集合。這里有兩點要注意一是確認是否需要做類別合并比如“牛奶”和“脫脂牛奶”是放在一起分析還是分開分析二是決定要不要對高銷量商品做降采樣否則它們會“霸屏”。第二步是調(diào)參跑模型。先用一個相對寬松的最小支持度比如0.005跑一輪看看項集分布再根據(jù)結(jié)果調(diào)。我一般會從支持度0.01、置信度0.5、提升度1.5起步然后根據(jù)規(guī)則數(shù)量調(diào)整。規(guī)則過多就收緊支持度過少就放寬。第三步是寫一個簡單的挑選函數(shù)按業(yè)務(wù)邏輯過濾掉同質(zhì)規(guī)則。比如計算前后件是否有包含關(guān)系或者是否屬于同一個品類。第四步是把通過篩選的規(guī)則輸出成一張報告表格配兩三個典型的商品組合案例一起提交給業(yè)務(wù)方讓業(yè)務(wù)方判斷是否有進一步做捆綁促銷或商品推薦的價值。這套流程我反復(fù)用過很多次從技術(shù)實現(xiàn)上并不復(fù)雜難點全在數(shù)據(jù)理解和業(yè)務(wù)判斷上。建議初次接觸關(guān)聯(lián)規(guī)則的朋友先拿一份真實的訂單流水完整跑一遍不要用太干凈的演示數(shù)據(jù)。數(shù)據(jù)一臟你就能深刻理解為什么要花那么多時間做預(yù)處理了。5. 寫在最后的幾條實際經(jīng)驗回頭再看關(guān)聯(lián)規(guī)則這件事它之所以到現(xiàn)在還沒被深度學習那套東西沖擊掉原因其實很簡單它是一種自帶解釋性的方法。輸出的是“前提→結(jié)論”形式的規(guī)則業(yè)務(wù)方一看就懂不像神經(jīng)網(wǎng)絡(luò)給出一堆特征權(quán)重讓人摸不著頭腦。我個人在實戰(zhàn)中還有幾條小經(jīng)驗值得分享。第一最小支持度的選擇不要拍腦袋可以先統(tǒng)計一下單商品的支持度分布取中位數(shù)附近的值作為起調(diào)點。第二FP-Growth跑出來的結(jié)果如果條數(shù)太多優(yōu)先去檢查數(shù)據(jù)質(zhì)量而不是繼續(xù)壓縮閾值很多“強規(guī)則”其實是重復(fù)錄入、別名亂造或者刷單造成的假象。第三年度大促期間的數(shù)據(jù)和日常運營數(shù)據(jù)混在一起時最好按活動周期分開挖掘因為大促期間的用戶行為模式和非大促期間差異極大混在一起容易得到不符合日常規(guī)律的規(guī)則。如果非要在Apriori和FP-樹頻集算法里選一個入門我會建議新手先把Apriori弄懂因為它幫你建立“項集—支持度—置信度—提升度”這個基本框架實際干活的時候再用FP-Growth去跑大數(shù)據(jù)。這個組合是最穩(wěn)妥的路徑既能理解原理又能解決問題。