Apriori算法與關聯分析

概述

關聯分析是一種在大規模資料集中尋找有趣關系的任務。這些關系可以有兩種形式：頻繁項集（frequent item sets）或者關聯規則。頻繁項集是經常出現在一起的物品的集合，關聯規則（association rules）暗示兩種物品之間可能存在很強的關系。

一個項集的支援度（support）度被定義為在資料集中包含該項集的記錄所占的比例。支援度是針對項集來說的，是以可以定義一個最小支援度，隻保留滿足最小支援度的項集。

置信度（confidence）是針對一條關聯規則來說的，假設由Apriori算法得到一個高支援度項集 k ，這個項集産生一組關聯規則， k 被分為兩個不相交的子集， A，B ，并記為

A−>B

第一個子項內建為“前件”，第二個子項內建為“後件”。規則的置信度是規則的支援度除以其前件的支援度，即

C(A−>B)=T(k)/T(A)

尋找頻繁項集

Apriori算法用一種比起暴力搜尋更快速的方法尋找頻繁項集，具體來說，如果一個項集是頻繁的，那麼它的所有子集也是頻繁的。第一遍掃描資料，計算所有1項集的支援度，删除那些支援度小于門檻值的項，第二次掃描對可以通過第一次掃描而保留下來的項生成的所有2項集計算支援度。也就是說，要生成所有m項集，我們隻需考慮這樣的m項集候選，他們的m個規模為m-1的項集都是頻繁的。删除那些支援度小于門檻值的2項集。每一遍後繼資料掃描隻考慮能由前一邊掃描保留項集和第一遍掃描留下的項組合所生成的項集。繼續掃描資料，直到由上一步得到的所有候選項集的支援度都小于指定的門檻值。這是至關重要的，因為我們假定所有資料不能全部裝入計算機記憶體。

從頻繁項集挖掘關聯規則

對于每一個頻繁項集，我們可以生成許多關聯規則。如果能夠減少規則數目來確定問題的可解性，那麼計算起來就會好很多。可以觀察到，如果某條規則并不滿足最小可信度要求，那麼該規則的所有子集也不會滿足最小可信度要求。舉例來說，對于頻繁項集{0，1，2，3}，如果{0，1，2}->{3}不滿足最小可信度要求，那麼任何左部為{0,1,2}的子集的規則也不會滿足最小可信度要求。這和頻繁項集的特性類似，對于一個頻繁項集，我們可以從後件隻有一個元素開始尋找規則，後件有兩個元素的規則其中的每一個元素作為後件對應的規則置信度都大于門檻值。

Python實作

吐槽…《機器學習實戰》上的代碼全是錯誤，而且例子也是錯的。。。

自己修改的代碼，在測試資料上輸出正确

這裡簡要說幾個重要的函數，首先是生成候選項集aprioriGen，比如要生成大小為k的候選項集Ck，如果将所有的長度為k-1的頻繁項集和長度為1的頻繁項集結合，那麼會生成大量重複的集合，需要判重，為了降低計算複雜度，考慮将所有長度為k-1的頻繁項集排序，然後對于兩層循環，對于前k-2項相同的頻繁項集合并，這樣可以保證沒有重複元素。

然後是遞歸生成規則的函數generateRules，每次從目前候選後件中尋找置信度大于門檻值的規則然後遞歸下去。

from numpy import *


# Apriori算法


def loadData():
    return [[, , ], [, , ], [, , , ], [, ]]

def createC1(dataSet):
    C1 = []
    for transaction in dataSet:
        for term in transaction:
            if [term] not in C1:
                C1.append([term])
    C1.sort()
    return list(map(frozenset, C1))

# 由候選項集生成頻繁項集，并計算支援度
def scanD(D, Ck, minSupport):
    ssCnt = {}
    for transaction in D:
        for can in Ck:
            if can.issubset(transaction):
                if can not in ssCnt: ssCnt[can] = 
                else: ssCnt[can] += 
    numItems = float(len(D))
    retList = []
    supportData = {}
    for key in ssCnt:
        # print(key, ssCnt[key])
        support = ssCnt[key]/numItems
        if support >= minSupport:
            retList.append(key)
        supportData[key] = support
    return retList, supportData

# 生成候選項集
def aprioriGen(Lk, k):
    retList = []
    sortL = []
    for i in range(len(Lk)):
        tmpL = sorted(list(Lk[i]))
        sortL.append(tmpL[:k-])
    for i in range(len(Lk)):
        for j in range(i+, len(Lk)):
            if sortL[i] == sortL[j]:
                retList.append(Lk[i]|Lk[j])
    return retList


def apriori(dataSet, minSupport=):
    C1 = createC1(dataSet)
    D = list(map(set, dataSet))
    L1, supportData = scanD(D, C1, minSupport)
    L = [L1]
    k = 
    while(len(L[k-]) > ):
        Ck = aprioriGen(L[k-], k)
        print(Ck)
        Lk, supK = scanD(D, Ck, minSupport)
        L.append(Lk)
        # update方法将一個字典添加到另一個字典中
        supportData.update(supK)
        k += 
    return L, supportData

def generateRules(L, supportData, minConf=):
    bigRuleList = []
    for i in range(, len(L)):
        for freqSet in L[i]:
            H1 = [frozenset([item]) for item in freqSet]
            rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
    return bigRuleList

def calConf(freqSet, H, supportData, brl, minConf):
    prunedH = []
    for conseq in H:
        conf = supportData[freqSet]/supportData[freqSet-conseq]
        if conf >= minConf:
            prunedH.append(conseq)
            brl.append((freqSet-conseq, conseq, conf))
            print(freqSet-conseq, '-->', conseq, 'conf', conf)
    return prunedH

def rulesFromConseq(freqSet, H, supportData, brl, minConf):
    prunedH = calConf(freqSet, H, supportData, brl, minConf)
    m = len(H[])
    if (len(freqSet) > m+):
        newH = aprioriGen(H, m+)
        if (len(newH) > ):
            rulesFromConseq(freqSet, newH, supportData, brl, minConf)

dataSet = loadData()
L, supportData = apriori(dataSet)
print(supportData)
rules = generateRules(L, supportData)