Python教程

Apriori 算法原理以及python实现详解

本文主要是介绍Apriori 算法原理以及python实现详解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Apriori 算法原理以及python实现

​ Apriori算法是第一个关联规则挖掘算法,也是最经典的算法。它利用逐层搜索的迭代方法找出数据库中项集的关系,以形成规则,其过程由连接(类
矩阵运算)与剪枝(去掉那些没必要的中间结果)组成。该算法中项集的概念即为项的集合。包含K个项的集合为k项集。项集出现的频率是包含项集的事务数,称为项集的频率。如果某项集满足最小支持度,则称它为频繁项集。(节选自百科)

1. Apriori 算法原理介绍

​ 设想场景如下:有一商场,记录对比每位顾客每次购买商品的清单,会发现购买了某类商品的顾客很大概率还会购买另外一类商品,为了更好的布局商品货架和进行捆绑促销的活动,需要统计分析不同种类商品的关联性。
进一步假定商场仅有四类商品0、1、2、3,为了统计分析商品的关联性,会自然去逐个计算不同商品组合出现的概率,1、2、3、4、01、02、03、12、13、23、012、013、023、123、1234 ,这些组合在Apriori中称为项集。

在这里插入图片描述

引入具体概念如下

  • 项与项集:设itemset={item1, item_2, …, item_m}是所有项的集合,其中,item_k(k=1,2,…,m)成为项。项的集合称为项集(itemset),包含k个项的项集称为k项集(k-itemset)。

  • 关联规则:关联规则是形如A=>B的蕴涵式,其中A、B均为itemset的子集且均不为空集,而A交B为空。

  • 支持度(support):关联规则的支持度定义如下:

在这里插入图片描述

即项集A、B同时发生的概率。

  • 置信度(confidence):关联规则的置信度定义如下:

在这里插入图片描述

​ 即项集A发生的情况下,则项集B发生的概率为关联规则的置信度。

  • 项集的出现频度(support count):相应项集的出现次数,简称为项集的频度、支持度计数或计数。
  • 频繁项集(frequent itemset):满足最小支持度的所有项集。
  • 强关联规则:满足最小支持度和最小置信度的关联规则,即待挖掘的关联规则。

​ 为了便于理解,假定有有5份购物清单,总计5类商品,1表示购买,0表示未买。

iditem0item1item2item3item4
111000
210111
301110
411110
511100

其中,项包含item0、item1、item2、item3、item4,项集为每个id对应的item。

​ 现在想研究{item1、item2}与item3的关联性。

支持度:{item1、item2、item3}同时发生概率为2/5。

置信度:{item1、item2}发生情况下,item3发生概率,即计算{item1、item2、item3}出现的次数所占{item1、item2}发生次数的比重,为2/3 。

​ 若最小支持度为1/5而最小置信度为1/2,则此关联规则为强规则,其为频繁项集中的一个子集。

​ 针对这些商品,我们的目标是:从大量购买数据中找到经常一起被购买的
商品。在寻找频繁项集(即经常出现的商品组合)的过程,我们采用支持度
和置信度来过滤商品组合来获得频繁项集。针对四钟商品,我们要在整体数
据集上进行15次轮询,才可以统计出每个频繁项集的支持度和置信度。试想,如果数据量较大,且商品种类不止四种的情况下,依旧采用逐个轮询的方式进行统计,带来的运算量是巨大的,并且随着商品种类的增加,频繁项集的组合种类也将变为2^N - 1种,随着种类的增加,那么带来的运算代价呈现指数型增加。为了解决这个问题,研究人员便在Apriori原理的基础上设计了Apriori算法。具体原理如下:如果某个项集是频繁的,那么它的所有子集也是频繁的。毫无疑问是正确的,则其逆否命题,如果一个项集是非频繁集,那么它的所有超集(包含该非频繁集的父集)也是非频繁的也是正确的。
在这里插入图片描述

假定阴影项集{2,3}是非频繁的,那么它的所有超集,也都是非频繁的,如上图灰色所示。在实际计算过程中,一旦计算出{2,3}的支持度不满足最小支持度,那么就不需要再计算{0,2,3}、{1,2,3}和{0,1,2,3}的支持度,因为它们也都是非频繁集。

2. Apriori 算法实现

设定最小支持度与置信度

MIN_Support = 0.5
MIN_Conf = 0.7

2.1项集构造及频繁项集获取

首先载入数据集

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

createOneitmeset(...)函数生成对应数据集内所有一项集

def createOneitmeset(dataSet):
    one_itmeset = []				
    for transaction in dataSet:			 	#循环遍历dataset中所有元素,未在列表中则添加
        for item in transaction:
            if not [item] in one_itmeset:
                one_itmeset.append([item])
    one_itmeset.sort()
    return list(map(frozenset, one_itmeset))

filter_itmeset(...)函数依据Apriori算法(一个项集是非频繁集,那么它的所有超集(包含该非频繁集的父集)也是非频繁的)来进

行滤除

def filter_itmeset(Data, itmeset):
    item_frequency = {}
    for item in Data:				#循环遍历项集中元素,并记录出现次数至item_frequency字典中
        for element in itmeset:
            if element.issubset(item):                   #issubset方法:若item包含element中所有元素则返回True
                if not element in item_frequency: item_frequency[element] = 1
                else:item_frequency[element] += 1

    numItems = float(len(Data))		#数据集中总的项集个数

    item_filtered = [] 				#频繁项集
    itemSupprotData={}				#项集中各项支持度
    for key in item_frequency:
        support = item_frequency[key]/numItems	#支持度计算:元素出现次数 / 总项集数
        if support>=MIN_Support:				#满足最小支持度添加到频繁项集列表中
            item_filtered.insert(0, key)
        itemSupprotData[key] = support
    return item_filtered, itemSupprotData

接着依照一项集构造未滤除的二项集,滤除之后得到二项集,再依据二项集构造三项集,循环往复得到直到K项集。具体函数实现为K_itemsetGenerator(...)函数,二项集及其之后的项集构造函数,滤除函数仍使用 filter_itmeset(Data, itmeset)

def K_itemsetGenerator(K_itemset_prev, K):
    K_itemset = []				#K-项集
    len_prev = len(K_itemset_prev)		#前一项集项数
    for i in range(len_prev):			#二重循环两两组合生成生成新项集
        for j in range(i+1, len_prev):
            L1=list(K_itemset_prev[i])[:K-2];L2=list(K_itemset_prev[j])[:K-2]
            L1.sort();L2.sort()
            if L1==L2:
                K_itemset.append(K_itemset_prev[i]|K_itemset_prev[j])            
    return K_itemset

​ 这里用了一个简单的优化来减少遍历次数和确保项集合成不超K,即输入的两个项集有k-2项相同才合并。以二项集生成三项集举例,只有{0、1}和{0、2}才会合并成为三项集,而{0、1}和{1、2}并不会合并。

2.2 获取关联信息

关联信息获取的主函数如下:

def findRelatedItemGroup(K_itemset_freq,itemSupprotData):
    RelatedItemGroup = []
    K = len(K_itemset_freq)
    for i in range(1, K):
        for itemset in K_itemset_freq[i]:
            itemWaitjudge = [frozenset([element]) for element in itemset]
            if(i > 1):
                reunionAcalcConf(itemset,itemWaitjudge,itemSupprotData,RelatedItemGroup)
            else:
                calcConf(itemset,itemWaitjudge,itemSupprotData,RelatedItemGroup)
    return RelatedItemGroup

findRelatedItemGroup(...)函数具体流程如下,获取二项集{A、B},对其进行分割,获得两个一项集A、B,由于是一项集不需要进行再组合,可以直接计算(A⇒B)以及(B⇒A)的置信度通过calcConf(...)是否达到需求,达到要求则会添加到RelatedItemGroup列表变量中,不满足则舍去,遍历完二项集之后,如若存在三项集,开始遍历三项集{A、B、C},首先进行分割,获得三个一项集A、B、C,此时需要在组合以便计算{(AUB)⇒C}、{(AUC)⇒B}等等组合的置信度。如此逐层循环获取频繁项集中所包含的强关联规则。三项集及以上的再组合与置信度计算均包含在reunionAcalcConf(...)函数中。

​ 以下是两个函数的具体实现,首先来看reunionAcalcConf(...)函数:

def reunionAcalcConf(itemset, itemWaitjudge, itemSupprotData, RelatedItemGroup):
    K = len(itemWaitjudge[0])               #K:当前项集的项数
    if (len(itemset) > (K + 1)):            #当当前项集项数已经组合到(父项集项数 - 1)时无需再次递归组合,否则继续在组合
        itemset_reunion = K_itemsetGenerator(itemWaitjudge, K + 1)      #项集包含项再组合,项数为当前项数 + 1
        itemset_reunion_filtered = calcConf(itemset, itemset_reunion, itemSupprotData, RelatedItemGroup)  #计算置信度并进行滤除
        if(len(itemset_reunion_filtered) > 1):               #如果没有强关联规则存在,后续的也无须递归再组合计算置信度
            reunionAcalcConf(itemset, itemset_reunion_filtered, itemSupprotData, RelatedItemGroup)   #存在强关联规则,递归在组合计算置信度


reunionAcalcConf(...)为递归函数,第一次进入时,此时 itemWaitjudge 为一项集,故K = 1 , 必定小于父项集项数, 满足len(itemset) > (K + 1),可以进行再组合、计算置信度,此时如果再组和计算后发现了多组强规则的存在,即满足len(itemset_reunion) > 1,那么对这些强规则进行再组和判断是否有进一步的强规则情况存在。如此递归,边界条件为 len(itemset) > (K + 1) ,即当当前项集项数已经组合到 (父项集项数 - 1) 时。

​ 接下来看 calcConf(...)的具体细节

def calcConf(itemset, itemWaitjudge, itemSupprotData, RelatedItemGroup):
    item_realted = []                   #存储itemWaitjudge中项间强关联规则
    for item in itemWaitjudge:
        conf = itemSupprotData[itemset] / itemSupprotData[itemset - item]   #计算置信度
        if conf >= MIN_Conf:            #满足条件 存储并输出
            print (itemset-item,'--->',item,'conf:',conf)
            RelatedItemGroup.append((itemset - item, item, conf))
            item_realted.append(item)
    return item_realted

​ 其中 itemSupprotData[itemset]为事件(AUB)发生概率,itemSupprotData[itemset - item]为事件A发生概率,两者相除即为支持度,如果所得支持度满足最小支持度存储并输出,最后返回该项集内强关联规则。

3.完整实验代码

MIN_Support = 0.5
MIN_Conf = 0.6

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

def createOneitmeset(dataSet):
    one_itmeset = []
    for transaction in dataSet:             #循环遍历dataset中所有元素,未在列表中则添加
        for item in transaction:
            if not [item] in one_itmeset:
                one_itmeset.append([item])
    one_itmeset.sort()
    return list(map(frozenset, one_itmeset))

def K_itemsetGenerator(K_itemset_prev, K):
    K_itemset = []				#K-项集
    len_prev = len(K_itemset_prev)		#前一项集项数
    for i in range(len_prev):			#二重循环两两组合生成生成新项集
        for j in range(i+1, len_prev):
            L1=list(K_itemset_prev[i])[:K-2];L2=list(K_itemset_prev[j])[:K-2]
            L1.sort();L2.sort()
            if L1==L2:
                K_itemset.append(K_itemset_prev[i]|K_itemset_prev[j])            
    return K_itemset

def filter_itmeset(Data, itmeset):
    item_frequency = {}
    for item in Data:				#循环遍历项集中元素,并记录出现次数至item_frequency字典中
        for element in itmeset:
            if element.issubset(item):                   #issubset方法:若item包含element中所有元素则返回True
                if not element in item_frequency: item_frequency[element] = 1
                else:item_frequency[element] += 1

    numItems = float(len(Data))		#数据集中总的项集个数

    item_filtered = [] 				#频繁项集
    itemSupprotData={}				#项集中各项支持度
    for key in item_frequency:
        support = item_frequency[key]/numItems	#支持度计算:元素出现次数 / 总项集数
        if support>=MIN_Support:				#满足最小支持度添加到频繁项集列表中
            item_filtered.insert(0, key)
        itemSupprotData[key] = support
    return item_filtered, itemSupprotData

def itemset_exhaustion(dataSet):
    one_itmeset = createOneitmeset(dataSet)
    Data = list(map(set, dataSet))
    one_itmeset_filtered, itemSupprotData_union = filter_itmeset(Data, one_itmeset)
    itemset_union = [one_itmeset_filtered]
    K = 2
    while(len(itemset_union[K - 2]) > 0):
        K_itemset = K_itemsetGenerator(itemset_union[K-2], K)
        K_itemset_filtered, K_itemSupprotData = filter_itmeset(Data, K_itemset)
        itemSupprotData_union.update(K_itemSupprotData)
        itemset_union.append(K_itemset_filtered)
        K += 1
    return itemset_union, itemSupprotData_union

def findRelatedItemGroup(K_itemset_freq,itemSupprotData):
    RelatedItemGroup = []
    K = len(K_itemset_freq)
    for i in range(1, K):
        for itemset in K_itemset_freq[i]:
            itemWaitjudge = [frozenset([element]) for element in itemset]
            if(i > 1):
                reunionAcalcConf(itemset,itemWaitjudge,itemSupprotData,RelatedItemGroup)
            else:
                calcConf(itemset,itemWaitjudge,itemSupprotData,RelatedItemGroup)
    return RelatedItemGroup

def calcConf(itemset, itemWaitjudge, itemSupprotData, RelatedItemGroup):
    item_realted = []                   #存储itemWaitjudge项中强关联规则
    for item in itemWaitjudge:
        conf = itemSupprotData[itemset] / itemSupprotData[itemset - item]   #计算置信度
        if conf >= MIN_Conf:            #满足条件 存储并输出
            print (itemset-item,'--->',item,'conf:',conf)
            RelatedItemGroup.append((itemset - item, item, conf))
            item_realted.append(item)
    return item_realted

def reunionAcalcConf(itemset, itemWaitjudge, itemSupprotData, RelatedItemGroup):
    K = len(itemWaitjudge[0])               #K:当前项集的项数
    if (len(itemset) > (K + 1)):            #当当前项集项数已经组合到(父项集项数 - 1)时无需再次递归组合,否则继续在组合
        itemset_reunion = K_itemsetGenerator(itemWaitjudge, K + 1)      #项集包含项再组合,项数为当前项数 + 1
        itemset_reunion_filtered = calcConf(itemset, itemset_reunion, itemSupprotData, RelatedItemGroup)  #计算置信度并进行滤除
        if(len(itemset_reunion_filtered) > 1):               #如果没有强关联规则存在,后续的也无须递归再组合计算置信度
            reunionAcalcConf(itemset, itemset_reunion_filtered, itemSupprotData, RelatedItemGroup)   #存在强关联规则,递归在组合计算置信度

if __name__=='__main__':
    dataSet=loadDataSet()
    L,supportData=itemset_exhaustion(dataSet)
    rules = findRelatedItemGroup(L,supportData)

实验输出如下

MIN_Support = 0.5
MIN_Conf = 0.7

在这里插入图片描述

MIN_Support = 0.5
MIN_Conf = 0.6

在这里插入图片描述 (部分图片来源网络)
参考文章:
【机器学习】Apriori算法——原理及代码实现(Python版)

这篇关于Apriori 算法原理以及python实现详解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!