1. Johngo学长首页
  2. 技术点详细复盘专题
  3. 人工智能

数据挖掘学习笔记：Apriori算法介绍和使用Python的两种实现(原始版和改进版)

• 人工智能 • 阅读 79

博文目录

简述

数据挖掘课程的作业，要求研究一个算法并写一篇实验报告。本次报告使用Overleaf编写，模板使用的IEEE期刊，后续将展示本次报告源码。以下正文内容是该报告的中文翻译，内容有删改。
2022-5-27: 增加代码注释中
2022-6-03: 代码注释完成, 编写笔记中
2022-6-17: 笔记编写完成, 添加报告源码

本次报告使用Overleaf编写，模板使用的IEEE期刊。点击这里获取报告源代码

正文

摘要

数据挖掘的关联规则算法有很多种。关联规则算法是在数据库中发现条目之间特殊关系的一种方法。关联规则从可以定量分析关系的角度来判断项目之间是否存在关联。Apriroi算法是目前最流行的关联规则算法之一，具有简单易学的特点。本文主要介绍了Apriori的基本知识，以及它的Python实现。Python是一种流行的脚本语言，用于人工智能、数据分析等。此外，我将展示一个基于数学集合理论改进的Apriori。

介绍

关联规则的概念由Rakesh Agrawal、Tomasz Imielinski和Arun Swami引入，用于发现超市大规模交易数据中产品之间的规律性。如摘要所述，关联规则挖掘使用以下定义定量描述商品之间的关系:

  1. 令I = { i 1 , i 2 , i 3 . . . i n } \rm I= \left {i_1,i_2,i_3…i_n \right }I ={i 1 ​,i 2 ​,i 3 ​…i n ​}是一个含有n个条目的集合，令T = { t 1 , t 2 , t 3 . . . t m } \rm T= \left {t_1,t_2,t_3…t_m \right }T ={t 1 ​,t 2 ​,t 3 ​…t m ​}是一组事务，每个事务都有一个ID号，是集合I \rm I I的一个子集。
  2. ;如果A ⊆ B \rm A \subseteq B A ⊆B, 则称B \rm B B 满足A \rm A A。
  3. 如果X ⊆ I \rm X \subseteq I X ⊆I, 则称X X X为 项集。
  4. 形式如:X ⟹ Y \rm X \Longrightarrow Y X ⟹Y,X \rm X X 和Y \rm Y Y 都是项集, 且X ∩ Y = ∅ \rm X \cap Y=\emptyset X ∩Y =∅ 被称作 关联规则
  5. 令X \rm X X为项集, 支持度是T中满足X的事务的比例。它的计算公式如下:
    S u p p o r t ( X ) = S i z e ( { t i ∣ t i ∈ T , X ⊆ t i } ) S i z e ( { t i ∣ t i ∈ T } ) Support(X)=\frac{Size(\left { t_i \mid ti\in T, X\subseteq ti\right })}{Size(\left { ti \mid ti \in T \right })}S u pp or t (X )=S i ze ({t i ∣t i ∈T })S i ze ({t i ​∣t i ∈T ,X ⊆t i })​
  6. 置信度用于计算满足X同时满足Y的所有交易的百分比，计算公式如下:
    C o n f i d e n c e ( X ⟹ Y ) = S u p p o r t ( X ∪ Y ) S u p p o r t ( X ) Confidence\left ( X\Longrightarrow Y \right ) = \frac{Support(X\cup Y)}{Support(X)}C o n f i d e n ce (X ⟹Y )=S u pp or t (X )S u pp or t (X ∪Y )​
  7. 支持度大于或等于最小支持度阈值的项集被定义为 频繁项集

根据关联规则处理的的对象类型，可以将关联规则分为两种类型:

  1. 数量关联规则(quantitative association rules)
  2. 布尔关联规则(Boolean association rules)

Apriori是布尔关联规则的著名算法之一，由R. Agrawal和R. Srikant在1994年给出了利用BFS和剪枝寻找频繁项集的算法，该算法的诞生还基于以下两个重要定理和一个定义:

  1. 如果一个项目集是频繁的，那么它的所有子集也必须是频繁的.

  2. 如果一个项集是非频繁集，那么它的所有超集也是非频繁集.

  3. 如果一个包含k个项目的项目集被定义为k-项目集。

这两个定理是集合定理的结论。我将用维恩图来证明它们。图1显示了项集X和项集Y之间的关联。红色圆圈包含所有满足项集X的事务，而那些包含项集Y的事务位于白色圆圈中。任何满足X和Y的交易都位于粉色区域。换句话说，粉色部分是红色和白色的交集。根据数学集合的属性，粉色区域包含的事务数小于或等于红色和白色区域包含的最小事务数。给定相同的事务总数，一个集合的支持度与该集合包含的事务数量之间存在线性正相关。因此，粉色的支持度小于或等于红色和白色的最小支持度。假设有一个项集X ∪ Y \rm X \cup Y X ∪Y，其中项集X为非频繁集，那么支持度S u p p o r t ( X ∪ Y ) {Support(X\cup Y)}S u pp or t (X ∪Y )将小于或等于对X的支持度，因此新的项集X ∪ Y \rm X \cup Y X ∪Y将是非频繁集。因为每个项集都可由两个项集的并集产生，定理2是正确的，反之亦然。因此这两个重要的定理都是正确的。

论文的剩余部分组织如下：第二节介绍了算法的核心及其改进。第三节简要介绍了如何用Python实现它。第四节我将使用含有9835个事务的数据集来简单地评估这个算法，并比较两个版本。最后第五节给出结论。

; 算法

在这一节中，我将首先介绍原始的Apriori算法，然后介绍它的改进。

原始版

如第一节所述，Apriori算法通过BFS和剪枝来寻找频繁项集。它主要有两个步骤：

  1. 生成新项目集：图2说明了生成新项集的过程。当k大于1时，所有的k+1项集，也称为候选项集，可以通过合并两个k项集来生成，其中两个k项集 必须前k个项相同，前提是这两个项集中的项顺序相同。这可以用 归纳法证明，证明过程略。注意k不大于集合I的元素个数。稍后将展示此过程的伪代码。
  2. 剪枝:利用定理1和定理2，我们可以在每一层中剪去非频繁项集。图3中，项集{2,3}很少出现，项集{2,3}、{1,2,3}、{0,2,3}和项集{0,1,2,3}也很少出现。总共有五个项集(红色圈)是不常见的。我们将它们(如果它们存在的话)在相应的层次上剔除。

现在，让我们用一个例子来解释这些算法。表1显示了一组6个事务，每个事务都包含来自集合I = { i 1 , i 2 , i 3 … i n } \rm I = {i_1, i_2, i_3…i_n}I ={i 1 ​,i 2 ​,i 3 ​…i n ​}，最小支持度为0.33。Apriori的详细过程如下(四舍五入到小数点后两位):

  1. k = 1：最初k是1，所以所有k项集(候选)都是集合i的元素。通过遍历总事务5次计算出5个元素的支持度，支持度如表2所示。

由于项集 i 5 \rm i_5 i 5 ​的支持计数小于0.33，我们将{ i 5 } \rm {i_5}{i 5 ​}切掉后，有4个频繁集。
2. k = 2：我们使用步骤1中的频繁项集，通过有条件地连接两个1-项集来生成2-项集。表3显示了每个2-项集的支持度。

所有2-频繁集如表4所示:
3. k = 3：因为没有频繁的3项集，所以算法结束。表5显示了所有频繁项目集：

; 改进版

该算法(原始版)的主要缺点是浪费大量时间变量总事务集筛选候选集。本节接下来将通过大幅度减少事务访问的次数来改进Apriori。

回想一下用于证明两个重要定理的图1，粉色的部分是红色的交集。如果我们记录分别包含X和Y的事务，那么我们很快就会知道哪些事务满足项集X ∪ Y \rm X \cup Y X ∪Y。我们使用前面的例子来说明，表6和表2基本一样，除了表6distributions一列记录哪些事务包含相应的项目集。首先，我们需要对总事务集进行n次循环，以获得一个包含n条记录的列表。

下一步是从1-频繁集生成的2-候选集中生成2-频繁集。因为我们记录了哪些事务包含相应的1-频繁集，所以我们不需要再次访问事务。例如，我们直接计算{ t 1 , t 4 , t 5 } \rm {t_1,t_4,t_5}{t 1 ​,t 4 ​,t 5 ​}和{ t 1 , t 2 , t 3 , t 4 , t 6 } \rm {t_1,t_2,t_3,t_4,t_6}{t 1 ​,t 2 ​,t 3 ​,t 4 ​,t 6 ​}的交集的大小，以获得项目集{ i 1 , i 2 } \rm {i_1, i_2}{i 1 ​,i 2 ​}的支持度。

同样，根据表7生成3个候选项，如表8所示。

此处我们做一个新的定义:

  1. 包含满足相应项目集的所有事务ID的集合被定义为 分布(distribution)。

; 实现

本节简要介绍如何使用Python实现该算法。完整的代码可以在实现代码中找到。

尽管frozenset是内置的Python类型，类似于数学集合，但元素无序的特性使其在产生频繁集中的比较过程不方便，并增大了运行时间。假设我们有两个frozenset({1,2})和frozenset({3,2})，如果我们要比较它们的第一个元素，我们应该在比较之前对它们进行排序，因为元素在set中是无序的。Python Tuple类似于list，但不可变且可哈希，同时tuple元素有序。所以我使用它来表示项集。为了方便起见，我将产生关联规则的函数集成进Apriori函数。

这里简单讲解一下产生关联规则的函数，例如：我们从项集{1,2,3}中产生关联规则，如果我们知道规则{1}->{2,3}，反过来我们可以快速知道规则{2,3}->{1}，所以我们不需要专门生成项集{2,3}，具体过程见实现代码。

实验分析

我使用9835个事务的数据集试验了这两种实现。该数据集共有169个产品。我在PC上完成了所有的实验，实验环境的简要描述如下:

数据挖掘学习笔记：Apriori算法介绍和使用Python的两种实现(原始版和改进版)
我做了两种实验。首先，评估了Apriori算法效率。其次，我使用不同的最小支持度来比较原始Apriori和改进的Apriori的性能。这些实验的结果将在后面给出。
  1. 算法效率
    为了评估该算法，我将修剪率定义为该算法减去的候选数占总候选数的比例。给定相同的最小支持，候选人的数量可以随您定义的顺序而变化(即:这两个项目集{a,b}和{a,c}可以生成{a,b,c}，而如果我们分别编号a,b,c为 3,2,1，则它们不能生成{3,2,1})。图4验证了这一现象。

在实验过程中。我将项目集中的项目按其ASCII递增排序，因为此时候选集的总数最低。在我使用了一个最小支持度列表[0.0005,0.001,0.005,0.01,0.02,0.05]后，修剪比率如下所示。从图5中我们可以看到超过一半的候选集是非频繁集。
2. 性能对比
我使用最小支持度列表[0.001,0.005,0.01,0.02,0.05]来比较原始Apriori和改进的Apriori所消耗的时间，我们通过原始版运行时间与改进版运行时间的比值来分析改进版的效果。各最小支持度的候选集总和如表9所示，结果如图6所示。数据集部分截图如图7所示。

原始算法很容易理解和实现。然而，许多事务扫描将导致运行时间急剧增加。改进的Apriori算法大大减少了事务扫描的次数。它们都将花费大量时间来筛选候选集。

; 实现代码

原始版

from decimal import Decimal
from itertools import count
import time
from typing import Set
from numpy import sort
import pandas._libs.lib as lib
import pandas as pd
from scipy.special import comb, perm
from bidict import bidict

'''
    targetEachlen: k的值
    frequentTuples: (k-1)-频繁集列表
    返回所有k-候选集列表
'''
def generateCandidates(targetEachlen, frequentTuples=[]):
    candidates = []
    lenOfArr = len(frequentTuples)

    for i in range(lenOfArr):
        for j in range(i+1, lenOfArr):
            tupleA = frequentTuples[i]
            tupleB = frequentTuples[j]

            if tupleA[:targetEachlen-2] == tupleB[:targetEachlen-2]:
                tupleC = tupleA + tuple([tupleB[-1]])
                candidates.append( tupleC )

            else:
                break

    return candidates

'''
    dataSetList: 由set组成的list, 每个set代表一次交易情况
    elementTupleList: 所有商品列表
    返回所有频繁集列表frequentTuplesList和每个频繁集的支持度字典supportDict
'''
def genearateFrequentSets(dataSetList, elementTupleList, minSupport=0.5):
    supportDict = {}

    frequentTuples,tempSupportDict= filterSetCandidates(transactions=dataSetList, tupleCandidates=elementTupleList,
    minSupport=minSupport)

    k = 2

    supportDict.update(tempSupportDict)
    frequentTuplesList = [frequentTuples]

    while (k-2)<len(frequentTuplesList) and len(frequentTuplesList[k-2]) > 1:

        tupleCandidates = generateCandidates(k, frequentTuplesList[k-2])

        frequentTuples, tempSupportDict = filterSetCandidates(transactions=dataSetList, tupleCandidates=tupleCandidates,
        minSupport=minSupport)

        supportDict.update(tempSupportDict)

        if len(frequentTuples) > 0:
            frequentTuplesList.append(frequentTuples)

        k += 1

    return frequentTuplesList,supportDict

'''
    transactions: 所有交易情况
    tupleCandidates: 所有k-候选集
    返回所有k-候选集和k-候选集的支持度字典
'''
def filterSetCandidates(transactions, tupleCandidates, minSupport):
    freqItemSets = []
    supportDict = {}
    lenOfTransactions = float(len(transactions))

    for itemSetTuple in tupleCandidates:
        existCount = 0
        for transaction in transactions:
            itemSet = set(itemSetTuple)
            if itemSet.issubset(transaction):
                existCount += 1
        support = float(existCount)/lenOfTransactions
        if support >= minSupport:
            supportDict[itemSetTuple] = support
            freqItemSets.append(itemSetTuple)

    return freqItemSets,supportDict

'''
    frequentTuplesList: 所有频繁集
    supportDict: 所有频繁集支持度字典
    minConfidence: 最小置信度
    返回所有关联规则
'''
def generateAllRules(frequentTuplesList, supportDict, minConfidence):
    ruleList = []

    for i in range(1, len(frequentTuplesList)):

        for frequentTuple in frequentTuplesList[i]:

            itemsOfTuple = [tuple({item}) for item in frequentTuple]

            if i > 1:
                ruleList.extend(generateRulesOfFrequentSet(frequentTuple, itemsOfTuple, supportDict, minConfidence))

            else:
                ruleList.extend(calcConfidenceOnSubSetList(frequentTuple, itemsOfTuple, supportDict, minConfidence))

    return ruleList

'''
    frequentTuple: 一个频繁集
    itemsOfTuple: frequentTuple的所有1-项集
    minConfidence: 最小置信度
    返回该项集的所有关联规则
'''
def generateRulesOfFrequentSet(frequentTuple, itemsOfTuple, supportDict, minConfidence):
    confidenceList = []
    k = 1
    tupleCandidates = itemsOfTuple
    lenOfTuple = len(itemsOfTuple)

    while len(tupleCandidates) >= 2:

        confidenceList.extend(calcConfidenceOnSubSetList(frequentTuple, tupleCandidates, supportDict, minConfidence))
        k += 1

        if k>int(lenOfTuple/2):
            break
        tupleCandidates = generateCandidates(k, tupleCandidates)

    return confidenceList

'''
    wholeTuple: 一个完整的频繁集
    subTuples: 所有k-频繁集
    minConfidence: 最小置信度
    返回大于minConfidence的关联规则
'''
def calcConfidenceOnSubSetList(wholeTuple, subTuples, supportDict={}, minConfidence=1):
    confidenceList = []

    for leftSubTuple in subTuples:

        tempSet = set(leftSubTuple)

        rightSubTuple = tuple([v for v in wholeTuple if v not in tempSet])
        conf1 = supportDict[wholeTuple] / supportDict[leftSubTuple]
        rule1 = [leftSubTuple, rightSubTuple, conf1]

        if(rule1[2] >= minConfidence):
            confidenceList.append(rule1)

        if len(wholeTuple)/2 == len(leftSubTuple):
            continue

        conf2 = supportDict[wholeTuple] / supportDict[rightSubTuple]
        rule2 = [rightSubTuple, leftSubTuple, conf2]
        if(rule2[2] >= minConfidence):
            confidenceList.append(rule2)

    return confidenceList

'''
    data: 交易数据
    minSupport: 最小支持度
    minConfidence: 最小置信度
    返回符合条件的关联规则list: [itemsetX, itemsetY, confidence]
'''
def apriori(data=[[]], minSupport=1, minConfidence=1):

    dataSetList = list(map(set, data))

    tempSet = sorted(set([ele for arr in data for ele in arr]))

    elementTupleList = [tuple([ele]) for ele in tempSet]

    frequentTuplesList, supportDict = genearateFrequentSets(dataSetList=dataSetList,
    elementTupleList=elementTupleList, minSupport=minSupport)
    ruleList = []

    ruleList = generateAllRules(frequentTuplesList=frequentTuplesList, supportDict=supportDict, minConfidence=minConfidence)
    return ruleList

if __name__ == '__main__':
    begin = time.perf_counter()

    dataFrame = pd.read_csv(filepath_or_buffer=r'mydata.csv')

    transactions = [x.strip('{}').split(',') for x in dataFrame['items']]
    ruleList =  apriori(data=transactions, minSupport=0.02, minConfidence=0.4)
    end = time.perf_counter()
    print(end-begin)
    print(len(ruleList))

优化版

import datetime
import sys
import time
from typing import Set
from numpy import sort
import pandas._libs.lib as lib
import pandas as pd
from scipy.special import comb, perm
from bidict import bidict

'''
    改进版与原始版相似, 故只在核心部分注释
'''

def generateCandidates(targetEachlen, frequentTuples=[]):
    candidates = []
    lenOfArr = len(frequentTuples)

    for i in range(lenOfArr):
        for j in range(i+1, lenOfArr):
            tupleA = frequentTuples[i]
            tupleB = frequentTuples[j]

            if tupleA[:targetEachlen-2] == tupleB[:targetEachlen-2]:
                tupleC = tupleA + tuple([tupleB[-1]])
                candidates.append( tupleC )
            else:
                break

    return candidates

def generateAllFrequent(data=[[]], minSupport=1):
    lenOfTransactions = float(len(data))
    dataSetList = list(map(set, data))
    tempSet = sorted(set([ele for arr in data for ele in arr]))
    tempDistributions = []
    nextDistributions = []
    frequentTuples = []
    supportDict = {}

    for ele in tempSet:
        temp = set()
        for i in range(len(dataSetList)):
            if ele in dataSetList[i]:
                temp.add(i)
        support = float(len(temp))/lenOfTransactions
        tempDistributions.append(temp)

        if support >= minSupport:
            nextDistributions.append(temp)
            tupleEle = tuple({ele})
            frequentTuples.append(tupleEle)

            supportDict[tupleEle] = support

    k = 2

    frequentTuplesList = [frequentTuples]
    while (k-2)<len(frequentTuplesList) and len(frequentTuplesList[k-2]) > 1:
        frequentTuples, tempSupportDict, nextDistributions = generatefrequentTuples(frequentTuples=frequentTuples,
        targetEachlen=k,
        lastDistributions=nextDistributions,
        lenOfTransactions=lenOfTransactions,
        minSupport=minSupport)
        supportDict.update(tempSupportDict)
        if len(frequentTuples) > 0:
            frequentTuplesList.append(frequentTuples)
        k += 1

    return frequentTuplesList,supportDict

'''
    lastDistributions: (k-1)-项集的分布情况
'''
def generatefrequentTuples(frequentTuples, targetEachlen, lastDistributions=[], lenOfTransactions=1.0, minSupport=1.0):
    nextFrequentTuples = []
    nextDistributions = []

    lenOfArr = len(frequentTuples)
    supportDict = {}
    candidateCount = 0

    for i in range(lenOfArr):
        for j in range(i+1, lenOfArr):
            tupleA = frequentTuples[i]
            tupleB = frequentTuples[j]

            if tupleA[:targetEachlen-2] == tupleB[:targetEachlen-2]:

                setC = lastDistributions[i] & lastDistributions[j]
                support = float(len(setC))/lenOfTransactions
                if support >= minSupport:
                    tupleC = tupleA + tuple([tupleB[-1]])
                    nextFrequentTuples.append( tupleC )
                    nextDistributions.append(setC)
                    supportDict[tupleC] = support
            else:
                break

    return nextFrequentTuples, supportDict, nextDistributions

def generateAllRules(frequentTuplesList, supportDict, minConfidence):
    ruleList = []

    for i in range(1, len(frequentTuplesList)):
        for frequentTuple in frequentTuplesList[i]:
            itemsOfTuple = [tuple({item}) for item in frequentTuple]
            if i > 1:
                ruleList.extend(generateRulesOfFrequentSet(frequentTuple, itemsOfTuple, supportDict, minConfidence))
            else:
                ruleList.extend(calcConfidenceOnSubSetList(frequentTuple, itemsOfTuple, supportDict, minConfidence))

    return ruleList

def generateRulesOfFrequentSet(frequentTuple, itemsOfTuple, supportDict, minConfidence):
    confidenceList = []
    k = 1
    tupleCandidates = itemsOfTuple
    lenOfTuple = len(itemsOfTuple)
    while len(tupleCandidates) >= 2:
        confidenceList.extend(calcConfidenceOnSubSetList(frequentTuple, tupleCandidates, supportDict, minConfidence))
        k += 1
        if k>int(lenOfTuple/2):
            break
        tupleCandidates = generateCandidates(k, tupleCandidates)

    return confidenceList

def calcConfidenceOnSubSetList(wholeTuple, subTuples, supportDict={}, minConfidence=1):
    confidenceList = []

    for leftSubTuple in subTuples:
        tempSet = set(leftSubTuple)
        rightSubTuple = tuple([v for v in wholeTuple if v not in tempSet])

        conf1 = supportDict[wholeTuple] / supportDict[leftSubTuple]
        rule1 = [leftSubTuple, rightSubTuple, conf1]
        if(rule1[2] >= minConfidence):
            confidenceList.append(rule1)
        if len(wholeTuple)/2 == len(leftSubTuple):
            continue
        conf2 = supportDict[wholeTuple] / supportDict[rightSubTuple]
        rule2 = [rightSubTuple, leftSubTuple, conf2]
        if(rule2[2] >= minConfidence):
            confidenceList.append(rule2)

    return confidenceList

def apriori(data=[[]], minSupport=1, minConfidence=1):
    frequentTuplesList, supportDict = generateAllFrequent(data=data, minSupport=minSupport)
    ruleList = []

    ruleList = generateAllRules(frequentTuplesList=frequentTuplesList, supportDict=supportDict, minConfidence=minConfidence)
    return ruleList

if __name__ == '__main__':
    begin = datetime.datetime.now()
    dataFrame = pd.read_csv(filepath_or_buffer=r'mydata.csv')
    data = [x.strip('{}').split(',') for x in dataFrame['items']]
    ruleList =  apriori(data=data, minSupport=0.001, minConfidence=0.4)

    end = datetime.datetime.now()
    print((end-begin).total_seconds())
    print(len(ruleList))

Original: https://blog.csdn.net/strcpy_s/article/details/124696796
Author: strcpy_s
Title: 数据挖掘学习笔记：Apriori算法介绍和使用Python的两种实现(原始版和改进版)

原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/640048/

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
0

【自取】最近整理的，有需要可以领取学习：



Linux核心资料大放送~

全栈面试题汇总（持续更新&可下载）

一个提高学习100%效率的工具！

【超详细】深度学习面试题目！

LeetCode Python刷题答案下载！

LeetCode Java版刷题答案下载！

LeetCode C++ 版本，抓紧保存！

LeetCode GO语言 刷题答案下载！

大家都在看

亲爱的 Coder【最近整理，可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球