關聯規則（Apriori、FP-grpwth）

什麼是關聯規則

關聯規則（Association Rules）是反映一個事物與其他事物之間的互相依存性和關聯性，是資料挖掘的一個重要技術，用于從大量資料中挖掘出有價值的資料項之間的相關關系。

所謂資料挖掘就是以某種方式分析源資料，從中發現一些潛在的有用的資訊。即資料挖掘又可以稱作知識發現，而機器學習算法則是這種“某種方式”。

舉個簡單的例子（尿布和啤酒太經典）：通過調研超市顧客購買的東西，可以發現30%的顧客會同時購買床單和枕套，而在購買床單的顧客中有80%的人購買了枕套，這就存在一種隐含的關系：床單→枕套，也就是說購買床單的顧客會有很大可能購買枕套，是以商場可以将床單和枕套放在同一個購物區，友善顧客購買。

關聯規則中的概念
- 項目：交易資料庫中的一個字段，對超市的交易來說一般是指一次交易中的一個物品，如：牛奶
- 事務：某個客戶在一次交易中，發生的所有項目的集合，如（牛奶，面包，啤酒）
- 項集：包含若幹個項目的集合（一次事務中的），一般會大于0個
- 支援度（Support）：項集（X，Y）在總項集中出現的機率
- 頻繁項集（Frequent item Sets）：某個項集的支援度大于設定門檻值（人為設定或者根據資料分布或者經驗來設定），即稱這個項集為頻繁項集
- 置信度（Confidence）：在先決條件X發生的條件下，由關聯規則（X->Y）推出Y的機率
- 提升度：表示含有X的條件下同僚含有Y的機率，與無論含不含有Y的

支援度與置信度的例子：

假如有一條規則：牛肉—>雞肉，那麼同時購買牛肉和雞肉的顧客比例是3/7，而購買牛肉的顧客當中也購買了雞肉的顧客比例是3/4。這兩個比例參數是很重要的衡量名額，它們在關聯規則中稱作支援度（support）和置信度（confidence）。對于規則：牛肉—>雞肉，它的支援度為3/7，表示在所有顧客當中有3/7同時購買牛肉和雞肉，其反應了同時購買牛肉和雞肉的顧客在所有顧客當中的覆寫範圍；它的置信度為3/4，表示在買了牛肉的顧客當中有3/4的人買了雞肉，其反應了可預測的程度，即顧客買了牛肉的話有多大可能性買雞肉。

支援度：P（AUB），即A和B這兩個項集在事務集D中同時出現的機率。

support（A=>B） = P（AUB）

置信度：P（B|A），即在出現項集A的事務集D中，項集B也同時的機率。

關聯規則（Apriori、FP-grpwth）

設定合理的支援度和置信度

對于某條規則：（A = a）−>（B = b）（support=30%,confident=60%）；其中support=30%表示在所有的資料記錄中，同時出現A=a和B=b的機率為30%；confident=60%表示在所有的資料記錄中，在出現A=a的情況下出現B=b的機率為60%，也就是條件機率。支援度揭示了A=a和B=b同時出現的機率，置信度揭示了當A=a出現時，B=b是否會一定出現的機率。

（1）如果支援度和置信度閉值設定的過高，雖然可以減少挖掘時間，但是容易造成一些隐含在資料中非頻繁特征項被忽略掉，難以發現足夠有用的規則；

（2）如果支援度和置信度閉值設定的過低，又有可能産生過多的規則，甚至産生大量備援和無效的規則，同時由于算法存在的固有問題，會導緻高負荷的計算量，大大增加挖掘時間。

Apriori算法簡介

Apriori算法：使用候選項集找頻發項集

Apriori算法是一種罪有影響的挖掘布爾關聯規則頻繁項集的算法。其核心是基于兩階段頻集思想的遞推算法。該關聯規則在分類上屬于單維、單層、布爾關聯規則。在這裡，所有支援度大于最小支援度的項集稱為頻繁項集，簡稱頻集。

Apriori原理：如果某個項集是頻繁的，那麼它的所有子集也是頻繁的。該定理的逆反定理為：如果某一個項集是非頻繁的，那麼它的所有超集（包含該集合的集合）也是非頻繁的。Apriori原理的出現，可以在得知某些項集是非頻繁之後，不需要計算該集合的超集，有效地避免項集數目的指數增長，進而在合理時間内計算出頻繁項集。

在圖中，已知陰影項集{2,3}是非頻繁的。利用這個知識，我們就知道項集{0,2,3}，{1,2,3}以及{0,1,2,3}也是非頻繁的。也就是說，一旦計算出了{2,3}的支援度，知道它是非頻繁的後，就可以緊接着排除{0,2,3}、{1,2,3}和{0,1,2,3}。

關聯規則（Apriori、FP-grpwth）

算法思想

①找出所有的頻集，這些項集出現的頻繁性至少和預定義的最小支援度一樣。

②由頻集産生強關聯規則，這些規則必須滿足最小支援度和最小可信度。

③使用第1步找到的頻集産生期望的規則，産生隻包含集合的項的所有規則，其中每一條規則的右部隻有一項，這裡采用的是中規則的定義。

④一旦這些規則被生成，那麼隻有那些大于使用者給定的最小可信度的規則才被留下來。為了生成所有頻集，使用了遞推的方法。

關聯規則（Apriori、FP-grpwth）

算法步驟

關聯規則（Apriori、FP-grpwth）

代碼實作

#Apriori算法實作
from numpy import *

def loadDataSet():
    return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]

# 擷取候選1項集，dataSet為事務集。傳回一個list，每個元素都是set集合
def createC1(dataSet):
    C1 = []   # 元素個數為1的項集（非頻繁項集，因為還沒有同最小支援度比較）
    for transaction in dataSet:
        for item in transaction:
            if not [item] in C1:
                C1.append([item])
    C1.sort()  # 這裡排序是為了，生成新的候選集時可以直接認為兩個n項候選集前面的部分相同
    # 因為除了候選1項集外其他的候選n項集都是以二維清單的形式存在，是以要将候選1項集的每一個元素都轉化為一個單獨的集合。
    return list(map(frozenset, C1))   #map(frozenset, C1)的語義是将C1由Python清單轉換為不變集合（frozenset，Python中的資料結構）

# 找出候選集中的頻繁項集
# dataSet為全部資料集，Ck為大小為k（包含k個元素）的候選項集，minSupport為設定的最小支援度
def scanD(dataSet, Ck, minSupport):
    ssCnt = {}   # 記錄每個候選項的個數
    for tid in dataSet:
        for can in Ck:
            if can.issubset(tid):
                ssCnt[can] = ssCnt.get(can, 0) + 1   # 計算每一個項集出現的頻率
    numItems = float(len(dataSet))
    retList = []
    supportData = {}
    for key in ssCnt:
        support = ssCnt[key] / numItems
        if support >= minSupport:
            retList.insert(0, key)  #将頻繁項集插入傳回清單的首部
        supportData[key] = support
    return retList, supportData   #retList為在Ck中找出的頻繁項集（支援度大于minSupport的），supportData記錄各頻繁項集的支援度

# 通過頻繁項集清單Lk和項集個數k生成候選項集C(k+1)。
def aprioriGen(Lk, k):
    retList = []
    lenLk = len(Lk)
    for i in range(lenLk):
        for j in range(i + 1, lenLk):
            # 前k-1項相同時，才将兩個集合合并，合并後才能生成k+1項
            L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2]   # 取出兩個集合的前k-1個元素
            L1.sort(); L2.sort()
            if L1 == L2:
                retList.append(Lk[i] | Lk[j])
    return retList

# 擷取事務集中的所有的頻繁項集
# Ck表示項數為k的候選項集，最初的C1通過createC1()函數生成。Lk表示項數為k的頻繁項集，supK為其支援度，Lk和supK由scanD()函數通過Ck計算而來。
def apriori(dataSet, minSupport=0.5):
    C1 = createC1(dataSet)  # 從事務集中擷取候選1項集
    D = list(map(set, dataSet))  # 将事務集的每個元素轉化為集合
    L1, supportData = scanD(D, C1, minSupport)  # 擷取頻繁1項集和對應的支援度
    L = [L1]  # L用來存儲所有的頻繁項集
    k = 2
    while (len(L[k-2]) > 0): # 一直疊代到項集數目過大而在事務集中不存在這種n項集
        Ck = aprioriGen(L[k-2], k)   # 根據頻繁項集生成新的候選項集。Ck表示項數為k的候選項集
        Lk, supK = scanD(D, Ck, minSupport)  # Lk表示項數為k的頻繁項集，supK為其支援度
        L.append(Lk);supportData.update(supK)  # 添加新頻繁項集和他們的支援度
        k += 1
    return L, supportData

if __name__=='__main__':
    dataSet = loadDataSet()  # 擷取事務集。每個元素都是清單
    # C1 = createC1(dataSet)  # 擷取候選1項集。每個元素都是集合
    # D = list(map(set, dataSet))  # 轉化事務集的形式，每個元素都轉化為集合。
    # L1, suppDat = scanD(D, C1, 0.5)
    # print(L1,suppDat)

    L, suppData = apriori(dataSet,minSupport=0.7)
    print(L,suppData)

FP-growth算法

Apriori算法是關聯規則的基本算法，很多用于發現關聯規則的算法都是基于Apriori算法，但Apriori算法需要多次通路資料庫，具有嚴重的性能問題。FP-Growth算法隻需要兩次掃描資料庫，相比于Apriori減少了I/O操作，克服了Apriori算法需要多次掃描資料庫的問題。

算法步驟：

建構FP樹
從FP樹中挖掘頻繁項集

實作流程：

關聯規則（Apriori、FP-grpwth）

第一步：建立FP樹

關聯規則（Apriori、FP-grpwth）

第二步：挖掘頻繁項集

關聯規則（Apriori、FP-grpwth）

代碼實作：

# FP樹類
class treeNode:
    def __init__(self, nameValue, numOccur, parentNode):
        self.name = nameValue  #節點元素名稱，在構造時初始化為給定值
        self.count = numOccur   # 出現次數，在構造時初始化為給定值
        self.nodeLink = None   # 指向下一個相似節點的指針，預設為None
        self.parent = parentNode   # 指向父節點的指針，在構造時初始化為給定值
        self.children = {}  # 指向子節點的字典，以子節點的元素名稱為鍵，指向子節點的指針為值，初始化為空字典

    # 增加節點的出現次數值
    def inc(self, numOccur):
        self.count += numOccur

    # 輸出節點和子節點的FP樹結構
    def disp(self, ind=1):
        print(' ' * ind, self.name, ' ', self.count)
        for child in self.children.values():
            child.disp(ind + 1)

# =======================================================建構FP樹==================================================

# 對不是第一個出現的節點，更新頭指針塊。就是添加到相似元素連結清單的尾部
def updateHeader(nodeToTest, targetNode):
    while (nodeToTest.nodeLink != None):
        nodeToTest = nodeToTest.nodeLink
    nodeToTest.nodeLink = targetNode

# 根據一個排序過濾後的頻繁項更新FP樹
def updateTree(items, inTree, headerTable, count):
    if items[0] in inTree.children:
        # 有該元素項時計數值+1
        inTree.children[items[0]].inc(count)
    else:
        # 沒有這個元素項時建立一個新節點
        inTree.children[items[0]] = treeNode(items[0], count, inTree)
        # 更新頭指針表或前一個相似元素項節點的指針指向新節點
        if headerTable[items[0]][1] == None:  # 如果是第一次出現，則在頭指針表中增加對該節點的指向
            headerTable[items[0]][1] = inTree.children[items[0]]
        else:
            updateHeader(headerTable[items[0]][1], inTree.children[items[0]])

    if len(items) > 1:
        # 對剩下的元素項疊代調用updateTree函數
        updateTree(items[1::], inTree.children[items[0]], headerTable, count)

# 主程式。建立FP樹。dataSet為事務集，為一個字典，鍵為每個事物，值為該事物出現的次數。minSup為最低支援度
def createTree(dataSet, minSup=1):
    # 第一次周遊資料集，建立頭指針表
    headerTable = {}
    for trans in dataSet:
        for item in trans:
            headerTable[item] = headerTable.get(item, 0) + dataSet[trans]
    # 移除不滿足最小支援度的元素項
    keys = list(headerTable.keys()) # 因為字典要求在疊代中不能修改，是以轉化為清單
    for k in keys:
        if headerTable[k] < minSup:
            del(headerTable[k])
    # 空元素集，傳回空
    freqItemSet = set(headerTable.keys())
    if len(freqItemSet) == 0:
        return None, None
    # 增加一個資料項，用于存放指向相似元素項指針
    for k in headerTable:
        headerTable[k] = [headerTable[k], None]  # 每個鍵的值，第一個為個數，第二個為下一個節點的位置
    retTree = treeNode('Null Set', 1, None) # 根節點
    # 第二次周遊資料集，建立FP樹
    for tranSet, count in dataSet.items():
        localD = {} # 記錄頻繁1項集的全局頻率，用于排序
        for item in tranSet:
            if item in freqItemSet:   # 隻考慮頻繁項
                localD[item] = headerTable[item][0] # 注意這個[0]，因為之前加過一個資料項
        if len(localD) > 0:
            orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)] # 排序
            updateTree(orderedItems, retTree, headerTable, count) # 更新FP樹
    return retTree, headerTable

# =================================================查找元素條件模式基===============================================

# 直接修改prefixPath的值，将目前節點leafNode添加到prefixPath的末尾，然後遞歸添加其父節點。
# prefixPath就是一條從treeNode（包括treeNode）到根節點（不包括根節點）的路徑
def ascendTree(leafNode, prefixPath):
    if leafNode.parent != None:
        prefixPath.append(leafNode.name)
        ascendTree(leafNode.parent, prefixPath)

# 為給定元素項生成一個條件模式基（字首路徑）。basePet表示輸入的頻繁項，treeNode為目前FP樹中對應的第一個節點
# 函數傳回值即為條件模式基condPats，用一個字典表示，鍵為字首路徑，值為計數值。
def findPrefixPath(basePat, treeNode):
    condPats = {}  # 存儲條件模式基
    while treeNode != None:
        prefixPath = []  # 用于存儲字首路徑
        ascendTree(treeNode, prefixPath)  # 生成字首路徑
        if len(prefixPath) > 1:
            condPats[frozenset(prefixPath[1:])] = treeNode.count  # 出現的數量就是目前葉子節點的數量
        treeNode = treeNode.nodeLink  # 周遊下一個相同元素
    return condPats

# =================================================遞歸查找頻繁項集===============================================
# 根據事務集擷取FP樹和頻繁項。
# 周遊頻繁項，生成每個頻繁項的條件FP樹和條件FP樹的頻繁項
# 這樣每個頻繁項與他條件FP樹的頻繁項都構成了頻繁項集

# inTree和headerTable是由createTree()函數生成的事務集的FP樹。
# minSup表示最小支援度。
# preFix請傳入一個空集合（set([])），将在函數中用于儲存目前字首。
# freqItemList請傳入一個空清單（[]），将用來儲存生成的頻繁項集。
def mineTree(inTree, headerTable, minSup, preFix, freqItemList):
    # 對頻繁項按出現的數量進行排序進行排序
    sorted_headerTable = sorted(headerTable.items(), key=lambda p: p[1][0])  #傳回重新排序的清單。每個元素是一個元組，[（key,[num,treeNode],()）
    bigL = [v[0] for v in sorted_headerTable]  # 擷取頻繁項
    for basePat in bigL:
        newFreqSet = preFix.copy()  # 新的頻繁項集
        newFreqSet.add(basePat)     # 目前字首添加一個新元素
        freqItemList.append(newFreqSet)  # 所有的頻繁項集清單
        condPattBases = findPrefixPath(basePat, headerTable[basePat][1])  # 擷取條件模式基。就是basePat元素的所有字首路徑。它像一個新的事務集
        myCondTree, myHead = createTree(condPattBases, minSup)  # 建立條件FP樹

        if myHead != None:
            # 用于測試
            print('conditional tree for:', newFreqSet)
            myCondTree.disp()
            mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)  # 遞歸直到不再有元素

# 生成資料集
def loadSimpDat():
    simpDat = [['r', 'z', 'h', 'j', 'p'],
               ['z', 'y', 'x', 'w', 'v', 'u', 't', 's'],
               ['z'],
               ['r', 'x', 'n', 'o', 's'],
               ['y', 'r', 'x', 'z', 'q', 't', 'p'],
               ['y', 'z', 'x', 'e', 'q', 's', 't', 'm']]
    return simpDat

# 将資料集轉化為目标格式
def createInitSet(dataSet):
    retDict = {}
    for trans in dataSet:
        retDict[frozenset(trans)] = 1
    return retDict

if __name__=='__main__':
    minSup =3
    simpDat = loadSimpDat()  # 加載資料集
    initSet = createInitSet(simpDat)  # 轉化為符合格式的事務集
    myFPtree, myHeaderTab = createTree(initSet, minSup)  # 形成FP樹
    # myFPtree.disp()  # 列印樹

    freqItems = []  # 用于存儲頻繁項集
    mineTree(myFPtree, myHeaderTab, minSup, set([]), freqItems)  # 擷取頻繁項集
    print(freqItems)  # 列印頻繁項集

關聯規則（Apriori、FP-grpwth）

什麼是關聯規則

關聯規則中的概念

支援度與置信度的例子：

設定合理的支援度和置信度

繼續閱讀

libsvm for python 安裝

學習軟體測試基礎測試第七天

Zeppelin 配置通路 REST APIApache Zeppelin Configuration REST API

【Torch】最簡潔logging使用指南

筆試面試題目：滑動視窗(二)

27. Remove Element(清單)題目代碼

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Cloud Studio初體驗

使用 ctypes 進行 Python 和 C 的混合程式設計

【python】【資料處理】畫多元資料分布圖

【python】netconf協定對接管理裝置

「Python 網絡自動化」NETCONF —— Python 使用 NETCONF 管理配置 H3C 網絡裝置

在python中建立excel并寫入

hdu7108哈希