Apriori算法

• 前言

  • 關聯分析是一種無監督的機器學習方法，主要用于發現大規模數據集中事物之間的依存性和關聯性。挖掘數據中隱藏的有價值的關系（如頻繁項集、關聯規則），有利于對相關事物進行預測，也能幫助系統制定合理決策。

  • 關聯分析的典型例子就是購物籃分析，通過發現顧客放入購物籃中不同商品之間的聯系，分析顧客的購買習慣。通過了解哪些商品頻繁地被顧客同時購買可以幫助零售商制定營銷策略。另外，關聯分析還能應用于餐飲企業的菜品搭配、搜索引擎的內容推薦、新聞流行趨勢分析、發現毒蘑菇的相似特征等應用中。

  • 為了解釋關聯分析的一些名詞，我使用了一個案例。

    號碼商品列表

    001	cola,egg,ham
    002	cola,diaper,beer
    003	cola,diaper,beer,ham
    004	diaper,beer

  • 名詞說明

    • 事物：每一條交易為一個事物，上表數據集包含三個事物。
    • 項：交易的每一個物品稱為一個項，如cola、ham等。
    • 項集：包含零個或多個項的集合稱為項集，如{cola,ham,beer}。
    • 規則：從項集中找出各項之間的關系。例如，關聯規則{diaper}—>{beer}。
    • 支持度計數：整個數據集中包含該項集的事物數。如{diaper,beer}出現在事物002、003和004中，所以它的支持度計數是3。
    • 支持度：支持度計數除以總的事物數。{diaper,beer}支持度為75%，說明有75%的人同時買了diaper和beer。
    • 頻繁項集：支持度大于或等于某個閾值的項集為頻繁項集。例如，閾值設為50%時，{diaper,beer}支持度為75%，所以是頻繁項集。
    • 前件和后件：對于規則{diaper}—>{beer}，{diaper}稱為前件，{beer}稱為后件。
    • 置信度：數據集中同時包含兩項的百分比。對于規則{diaper}—>{beer}，{diaper,beer}的支持度計數除以{diaper}的支持度計數，即為這個規則的置信度。
    • 強關聯規則：大于或等于最小支持度閾值和最小置信度閾值的規則稱為強關聯規則，關聯分析的最終目的就是找出強關聯規則。

  • 基本方法

    • 關聯分析的目標包括兩項：發現頻繁項集和關聯規則。首先需要找到頻繁項集，然后才能獲得關聯規則。關聯分析的主要目的就是尋找頻繁項集，如果暴力搜索，運算量會幾何性增長。為了減少頻繁項集的計算量，可以使用Apriori算法和FP-Growth算法。
• 原理
  • 如果某個項集是頻繁的，那么它的所有自己也是頻繁的。這個原理反過來看更有用，即如果一個項集是非頻繁項集，那么它的所有超集也是非頻繁的。
  • 算法步驟
    • (1)根據數據集生成候選項，首先生成單物品候選項集。
    • (2)設定最小支持度和最小置信度。
    • (3)過濾掉數據項集占比低于最小支持度的項，形成頻繁項。
    • (4)根據步驟3形成的頻繁項集結果，進行項集之間的組合形成新的項集集合。
    • (5)重復步驟3、4，直到沒有新的項集滿足最小支持度。
      -（6)根據步驟5形成的最終頻繁集合，計算頻繁集合所含物品之間的置信度，過濾掉小于最小置信度的項集。
    • (7)根據步驟6的結果生成關聯規則，并計算其置信度。
  • 上述步驟體現了Apriori算法的兩個重要過程：連接步和剪枝步。連接步的目的是找到K項集，從滿足約束條件1項候選項集，逐步連接并檢測約束條件產生高一級候選項集，知道得到最大的頻繁項集。剪枝步是在產生候選項Ck的過程中起到減小搜索空間的目的。根據Apriori原理，頻繁項集的所有非空子集也是頻繁的，反之，不滿足該性質的項集不會存在于Ck中，因此這個過程稱為剪枝。
  • Apriori算法從單元素項集開始，通過組合滿足最小支持度要求的項集來形成更大的集合。每次增加頻繁項集的大小，Apriori算法都會重新掃描整個數據集。當數據集很大時，會顯著降低頻繁項集發現的速度。比較來說，FP-Growth算法只要對數據集進行兩次遍歷，就能夠顯著加快發現頻繁項集的速度。
• 實戰
  • 用Apriori進行關聯分析
  • 發現商品購買的關聯規則
  • 可以看到，購買商品1的一定購買商品2和3；商品2與5我的關聯可以互換前后件。這些結果都是很有效的。
  • 代碼
    • # -*-coding:utf-8-*-def loadDataSet():"""生成數據集:return:"""return [[1, 2, 3], [2, 3, 5], [1, 2, 3, 5], [2, 5]]def createC1(dataSet):"""生成長度為1的所有候選項:param dataSet::return:"""C1 = []for transaction in dataSet:for item in transaction:if not [item] in C1:C1.append([item])C1.sort()return list(map(frozenset, C1))def scanD(D, Ck, minSupport):"""從候選項集中生成頻繁項集，同時輸出一個包含支持度值的字典:param D::param Ck::param minSupport::return:"""ssCnt = {}for tid in D:for can in Ck:if can.issubset(tid):if can not in (ssCnt.keys()):ssCnt[can] = 1else:ssCnt[can] += 1numItems = float(len(D))retList = []supportData = {}for key in ssCnt:support = ssCnt[key] / numItemsif support >= minSupport:retList.insert(0, key)supportData[key] = supportreturn retList, supportDatadef aprioriGen(Lk, k):retList = []lenLk = len(Lk)for i in range(lenLk):for j in range(i + 1, lenLk):L1 = list(Lk[i])[:k - 2]L2 = list(Lk[j])[:k - 2]L1.sort()L2.sort()if L1 == L2:retList.append(Lk[i] | Lk[j])return retListdef apriori(dataSet, minSupport=0.5):"""得到頻繁項的基礎上，進一步將頻繁項組合并計算支持度返回一個包含整個頻繁項集的列表和頻繁項集列表中每個元素對應的支持度值的字典:return:"""C1 = createC1(dataSet)D = list(map(set, dataSet))L1, supportData = scanD(D, C1, minSupport)L = [L1]k = 2while (len(L[k - 2]) > 0):Ck = aprioriGen(L[k - 2], k)Lk, supK = scanD(D, Ck, minSupport)supportData.update(supK)L.append(Lk)k += 1return L, supportDatadef generateRules(L, supportData, minConf=0.7):"""由于小于最小支持度的項集已經剔除，剩余項集形成的規則中如果大于設定的最小置信度閾值，則認為它們是強關聯規則:param L::param supportData::param minConf::return:"""bigRuleList = []for i in range(1, len(L)):for freqSet in L[i]:H1 = [frozenset([item]) for item in freqSet]if i > 1:rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)else:calcConf(freqSet, H1, supportData, bigRuleList, minConf)return bigRuleListdef calcConf(freqSet, H, supportData, brl, minConf=0.7):prunedH = []for conseq in H:conf = supportData[freqSet] / supportData[freqSet - conseq]if conf >= minConf:print(freqSet - conseq, '-->', conseq, 'conf:', conf)brl.append((freqSet - conseq, conseq, conf))prunedH.append(conseq)return prunedHdef rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):m = len(H[0])if len(freqSet) > (m + 1):Hmp1 = aprioriGen(H, m + 1)Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)if len(Hmp1) > 1:rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)if __name__ == '__main__':dataSet_1 = loadDataSet()L, suppData = apriori(dataSet_1)print(L)print('\n--------------------\n')print(suppData)rules = generateRules(L, suppData, minConf=0.7)print(rules)
• 補充說明
  • 參考書《Python3數據分析與機器學習實戰》
  • 具體數據集和代碼可以查看我的GitHub,歡迎star或者fork
  • 幾個著名的機器學習包內均沒有實現Apriori算法

總結

以上是生活随笔為你收集整理的机器学习-关联之Apriori算法原理及实战的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。