精华内容
下载资源
问答
  • 资源中包含apriori关联分析算法的Python代码,python的版本为3.6,使用pycharm平台运行即可。
  • 一个实例带你搞懂Apriori关联分析算法

    千次阅读 多人点赞 2020-05-31 16:13:01
    关联分析算法 关联分析是一种在大规模数据集中寻找有趣关系的任务。这些关系可以有两种形式:频繁项集或者关联规则。 附算法分析以及详细代码示例

    关联分析

    Apriori算法
    优点:易编码实现。
    缺点:在大数据集上可能较慢。
    适用数据类型:数值型或者标称型数据。

    关联分析是一种在大规模数据集中寻找有趣关系的任务。这些关系可以有两种形式:频繁项集或者关联规则。

    频繁项集是经常出现在一块的物品的集合
    关联规则(association rules)暗示两种物品之间可能存在很强的关系。下面会用一个例子来说明这两种概念。
    在这里插入图片描述
    频繁项集是指那些经常出现在一起的物品集合,图中的集合{葡萄酒,尿布, 豆奶}就是频繁项集的一个例子

    如尿布 ➞葡萄酒的一起出现的频率较高就是一个关联规则。这意味着如果有人买了尿布,那么他很可能也会买葡萄酒。

    数据集中包含该项集的记录所占的比例就是项集的支持度

    可以得到,{豆奶}的支持度为4/5。而在5条交易记录中有3条包含{豆奶,尿布},因此{豆奶,尿布}的支持度为3/5。支持度是针对项集来说的,因此可以定义一个最小支持度,而只保留满足最小支持度的项集。
    可信度或置信度(confidence)是针对一条诸如{尿布} ➞ {葡萄酒}的关联规则来定义的。这条规则的可信度被定义为“支持度({尿布, 葡萄酒})/支持度({尿布})”。

    由{尿布, 葡萄酒}的支持度为3/5,尿布的支持度为4/5,所以“尿布 ➞ 葡萄酒”的可信度为3/4=0.75。这意味着对于包含“尿布”的所有记录,我们的规则对其中75%的记录都适用。

    支持度和可信度是用来量化关联分析是否成功的方法。假设想找到支持度大于0.8的所有项集,应该如何去做?一个办法是生成一个物品所有可能组合的清单,然后对每一种组合统计它出现的频繁程度,但当物品成千上万时,上述做法非常非常慢。

    Apriori原理会减少关联规则学习时所需的计算量。

    Apriori 原理

    先验原理:如果一个项集是频繁的,那么他的子集也是频繁的;反过来,如果一个子集是非频繁的,该项集也是非频繁

    Apriori算法的一般过程

    1. 收集数据:使用任意方法。
    2. 准备数据:任何数据类型都可以,因为我们只保存集合。
    3. 分析数据:使用任意方法。
    4. 训练算法:使用Apriori算法来找到频繁项集。
    5. 测试算法:不需要测试过程。
    6. 使用算法:用于发现频繁项集以及物品之间的关联规则。

    在这里插入图片描述
    上图就是扫描数据的过程,在扫描完所有数据之后,使用统计得到的总数除以总的交易记录数,就可以得到支持度。
    对于包含n种物品的数据集共有 2 n − 1 2^n -1 2n1种项集组合。即使只出售100种商品的商店也会有1.26×1030种可能的项集组合。
    在这里插入图片描述
    若已知123是频繁项集,则他上面的那几个子集都是频繁的

    在这里插入图片描述
    上图中,假设已知阴影项集{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 算法来发现频繁集

    首先需要找到频繁项集,然后才能获得关联规则。
    在这里插入图片描述
    C1,C2,… Ck分别表示1-项集,2-项集,…k-项集,是候选项集
    L1, L2, …Lk分别表示有k个数据项的频繁项集。
    create是根据数据集创建候选项集
    Scan表示数据集扫描函数。该函数起到的作用是支持度过滤,满足最小支持度的项集才留下,不满足最小支持度的项集直接舍掉。

    Apriori算法是发现频繁项集的一种方法。两个输入参数分别是最小支持度和数据集。该算法首先会生成所有单个物品的项集列表。接着扫描交易记录来查看哪些项集满足最小支持度要求,那些不满足最小支持度的集合会被去掉。然后,对剩下来的集合进行组合以生成包含两个元素的项集。接下来,再重新扫描交易记录,去掉不满足最小支持度的项集。该过程重复进行直到所有项集都被去掉。

    生成候选项集

    对数据集中的每条交易记录transaction
    对每个候选项集c:
    检查一下c是否是transaction的子集:
    如果是,则增加ca的计数值
    对每个候选项集:
    如果其支持度不低于最小值,则保留该项集
    返回所有频繁项集列表

    #创建一组数据
    def loadDataSet():
        dataset=[[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
        return dataset
    
    def createC1(dataSet):
        C1 = []
        for transaction in dataSet:
            #print(transaction)
            for item in transaction:
                #print(item)
                if not {item} in C1:
                    #print([item])
                    C1.append({item})
            #print(C1)
        C1.sort()
        #就是对c1用frozenset的方法,frozenset就是把这个数集合冰冻起来不能进行修改
        return list(map(frozenset, C1))# use frozen set so we can use it as a key in a dict
    
    c1=createC1(dataset)
    #三个参数 分别是数据集、候选项集列表Ck以及最小支持度minSupport
    def scanD(D, Ck, minSupport):
        ssCnt = { }
        for tid in D:
            for can in Ck:
                #issubset方法用于判断集合的所有元素是否都包含在指定集合中,如果是则返回 True,否则返回 False。
                if can.issubset(tid):
                    #判断can是否是tid的子集,has_key() 函数用于判断键key是否存在于字典中,如果键在字典dict里返回true,否则返回false。
                    if can not in ssCnt:
                        ssCnt[can]=1
                    else:
                        ssCnt[can] += 1
    
        numItems = float(len(D))
        retList = [ ]
        supportData = { }
        for key in ssCnt:
            support = ssCnt[key] /numItems
            supportData[key] = support
            if support >= minSupport:
                retList.append(key)
        return retList, supportData
    dataset=loadDataSet()
    c1=createC1(dataset)
    l1,suppordata=scanD(dataset,c1,0.5)
    print(l1)
    print(suppordata)
    
    
    [frozenset({1}), frozenset({3}), frozenset({2}), frozenset({5})]
    
    {frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25, frozenset({2}): 0.75, frozenset({5}): 0.75}
    

    代码实现原理如下图:
    在这里插入图片描述
    这里有详细解释
    或者这里

    关联规则就是A–>B有关联,而B–>A则不一定有关联,这个下篇再讲。

    展开全文
  • Apriori算法--关联分析算法(一)

    万次阅读 多人点赞 2017-10-16 15:49:49
    在实际生产生活我们经常会遇到一些“关联分析”(Association Analyse)的任务。举几个实际例子。1.人们的购物清单里面的各个商品有没有什么关联呢?就像下面这个购物清单写的那样子,右边是各个顾客所买的东西。 有...

    在实际生产生活我们经常会遇到一些“关联分析”(Association Analyse)的任务。举几个实际例子。

    1.人们的购物清单里面的各个商品有没有什么关联呢?就像下面这个购物清单写的那样子,右边是各个顾客所买的东西。

    这里写图片描述

    有的时候我们想问,顾客购买商品的时候会不会多个商品组合起来买呢?顾客会不会倾向于豆奶和尿布这两样商品一起买?我们怎么从一份购物清单里面发现这种往往会一起出现的商品组合呢?


    2.现在几乎人人都有自己的PC,都会在自己的电脑上安装自己喜欢的软件。现在给出不同工作领域的用户的软件列表,我们能不能发现同种身份的人一般都会按照那些共性的软件呢?这样或许我们就可以给用户推荐他所在领域的受欢迎的软件。
    这里写图片描述

    能不能通过计算得到学生群体的共性软件呢?


    3.总结疾病的特征。给我们一些疾病的特征,我们如何从这些数据总结出某种疾病的普遍特征呢?比如,给一些患流行性感冒的病人的生理特征数据,我们如何从这些数据发现患流行性感冒的普遍症状呢?

    以上这些问题都是关系分析的问题,这些问题希望在数据集中发现其中蕴含的关系,企图发现里面存在的频繁出现的组合(比如学生会经常按照那些软件)或者项与项之间的关系(比如一般安装微信的人也会顺带安装QQ)。发现频繁出现的组合叫做发现频繁项集(frequent item set),而找出项与项之间的相关关系叫做关联规则学习(association rule analyse)

    这里写图片描述


    #如何量化?
    我们如何衡量一个组合是不是频繁出现的呢?频繁是中文含义就是出现的次数多,那么频繁的衡量标准肯定和出现的频数有关。如何计算某个组合的频数?例如:

    这里写图片描述

    那么{豆奶,尿布}的频数就是3,因为这个组合出现在第2,3,4条样本出现过。

    但是,我们也知道频数这个指标是和样本数量的有关的。假如我们规定频数大于5的组合就是频繁的。那这样子假如某个组合在10条随机数据集中的频数为1,这个组合是不频繁的;但是在100条随机数据集中频数为10,该组合变的频繁了。这就会导致频繁性的判断不稳定。因此实际上我们使用频率这个指标。

    实际上一个组合A的频率又叫组合A在这个数据集T上的支持度(support degree),意思就是组合A在数据集T上出现的概率。

    那么我们如何定义关联规则可信呢?已知一个人已经买了豆奶,那么他有多大概率也买尿布嘞?这个就要使用到条件概率了。

    这里写图片描述

    这个条件概率的直观解释就是:在所有出现豆奶的样本里,有多少个还出现了尿布。如果这个条件概率特别大,那么我们可以认为**“买了 豆奶 一般也会买 尿布 ”**这条规则是可信任的。规则 “买了 豆奶 一般也会买 尿布” 记作:豆奶——>尿布。但是这条关联规则不具备自反性。也就是说 豆奶——>尿布,并不能推出 尿布——>豆奶,本质上是因为他们的条件概率都不同:
    这里写图片描述

    直观上的理解也是一样的。比如 人们一般上完厕所就会洗手,规则:上厕所——>洗手 是可信的;但是并不意味着 洗了手就一定是在上厕所,因为也可能是吃了饭再洗手。

    同样的,在关联分析中,与某条规则相对应的条件概率也有另外一个名称:置信度

    规则A->B的置信度计算公式为:
    这里写图片描述

    有了这两个量化指标,那我们就可以在一个数据集上寻找频繁项集和关联规则啦。
    最原始的做法就是,生成所有可能的组合方式,然后我们枚举计算这些所有的组合方式的支持度(频率),那些达到支持度指标的就是我们想到找到的频繁项集啦。这种枚举法当然可以解决问题,但是我们想也想的到这个复杂度特别高!

    比如上面购物的例子中基础元素共有6个,这6个元素可以一个一个组合,也可以两个两个组合,也可以三个三个来•••那么这6个基本元素组合起来就一共有:
    这里写图片描述种可能的组合方式。如此,我们需要计算63种组合出现的频率,每次计算需要遍历整个数据集。emmmmm…这个时间复杂度O(2^N)要GG。那么一个自然的思路就是剪枝。

    #使用Apriori 原理进行剪枝

    Apriori原理特别简单!有一些公理化概率论基础都会轻松理解

    设A,B是两个事件,则

    这里写图片描述

    积事件的概率小于等于各个因子的概率。直观的解释就是A和B同时发生的概率当然要小于等于他们单独分别发生的概率。

    这里写图片描述

    ok.我们来使用这个性质对上面寻找频繁项集的过程进行剪枝。

    这里写图片描述

    上图显示了基础元素集为{0,1,2,3}时,所有可能的组合。这实际显示了一种生成所有组合的层次化的方法:先一一组合,然后再二二组合,再三三组合•••每一层的组合都可以在上一层的基础上进行。具体方法为:

    设第i层是所有含i个元素的组合,每个组合都有i+1个不同的元素。现在需要生成所有含i+1个元素的组合。

    i+1个元素的组合就是每个组合含有i+1个不同的元素;那么只要在原来第i层的基础上进行两两合并,生成含且只含i+1个元素的组合。

    为了让第i层两个组合CA,CB组合后生成只含i+1个元素,需要CA,CB有且只有一个元素不同。否则合并后的组合将不只i个元素。

    所以我们可以让所有组合按基础元素升序的方式排列,比较CA,CB前i-1个元素.如果CA和CB的前i-1个元素相同的话,CA和CB就只有第i个元素不同了(如01和02),这样合并后才能只含有i+1个元素。如果CA和CB的前i-1个元素不等,那至少CA与CB会有两个元素不一致(如01 和23 组合生成0123 就包含4个基本元素)。 (此方法存在问题,感谢@weixin_39799208指正)
    正确的做法应该是对CA和CB内的各元素做交集,看交集内的元素个数是否为i-1。

    现在 我们假设{23}组合的支持度为P({23}),它小于容许的最小支持度p’,即P(23) < p’,此时{23}这种组合就是不频繁的了。

    由图可知,{23}参与了组合{023}和{123}的生成,那么:

    这里写图片描述
    这里写图片描述

    #Apriori的实现代码:

    __author__ = 'jmh081701'
    import  numpy as np
    
    def loadDataset():
        return [{1,3,4},{2,3,5},{1,2,3,5},{2,5}]
    def createC1(dataset,minsupport=0.6):
        C1=[]
        for t in dataset:
            for s in t:
                if({s} in C1):
                    continue
                else:
                    C1.append({s})
        C1.sort()
        return map(frozenset,C1)
    
    def scan(dataset,minisupport=0.6,Ck=None):
        rst=[]
        cutset=[]
        supportData={}
        for c in Ck:
            for t in dataset:
                if c.issubset(t):
                    if c in supportData:
                        supportData[c]+=1
                    else:
                        supportData[c]=1
        lenD=float(len(dataset))
    
        for key in supportData:
            supportData[key]=supportData[key]/lenD
            if(supportData[key]>=minisupport):
                rst.append(key)
            else:
                cutset.append(key)
        return rst,supportData,cutset
    
    def genCj(Ck,k,Cutset={}):
    	#2019年04.10 此实现有问题,应该是取l1,l2交集然后判断交集元素个数是否符合要求。
        lenCk=len(Ck)
        Cj=set()
        for i in  range(lenCk):
            for j in range(i+1,lenCk):
                l1=list(Ck[i])[:k-1]
                l2=list(Ck[j])[:k-1]
                l1.sort()
                l2.sort()
                if(l1==l2):
                    t=Ck[i]|Ck[j]
                    f=0
                    for each in Cutset:
                        if set(each).issubset(t):
                            f=1
                            break
                    if(f==0):
                        Cj.add(t)
        return Cj
        
    def apriori(dataset,minisupport=0.6):
        #from number i layer frequent item set generate i+1 th frequent item set.
        C1=createC1(dataset)
        Ck=C1
        k=1
        supportData={}
        CutSet=[]
        rstC=[]
        while Ck!=set():
            rst,support,cutset=scan(dataset,minisupport,Ck)
            rstC.append([rst])
            supportData.update(support)
            CutSet.append(cutset)
            Cj=genCj(rst,k,CutSet)
            k+=1
            Ck=Cj
    
        return rstC,supportData
    data=loadDataset()
    rstC,supportData=apriori(data)
    print(rstC)
    print(supportData)
    

    运行结果:

    [[[frozenset({3}), frozenset({2}), frozenset({5})]], [[frozenset({2, 5})]]]
    {frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25, frozenset({2}): 0.75, frozenset({5}): 0.75, frozenset({2, 3}): 0.5, frozenset({3, 5}): 0.5, frozenset({2, 5}): 0.75}
    

    #代码解释

    def loadDataset():
        return [{1,3,4},{2,3,5},{1,2,3,5},{2,5}]
    

    该函数用于生成数据集。输入数据集是一个list of set.列表里面的每一个元素都是集合。在关联分析中,需要将原始数据转化为这种数据形式。尤其是每个样本的特征向量其实是一个无序的集合。

    def createC1(dataset,minsupport=0.6):
        C1=[]
        for t in dataset:
            for s in t:
                if({s} in C1):
                    continue
                else:
                    C1.append({s})
        C1.sort()
        return map(frozenset,C1)
    

    该函数遍历整个数据集,将各个基础元素抽离出来。注意最后的map{frozenset,C1}

    map(func, seq1[, seq2,…]) 
    第一个参数接受一个函数名,后面的参数接受一个或多个可迭代的序列,返回的是一个集合。 Python函数编程中的map()函数是将func作用于seq中的每一个元素,并将所有的调用的结果作为一个list返回。
    

    map(frozenset,C1)其实就是将C1的每一个元素都转化为frozenset类型。这么做是为了让元素组合能够做字典的key.

    def scan(dataset,minisupport=0.6,Ck=None):
        rst=[]
        cutset=[]
        supportData={}
        for c in Ck:
            for t in dataset:
                if c.issubset(t):
                    if c in supportData:
                        supportData[c]+=1
                    else:
                        supportData[c]=1
        lenD=float(len(dataset))
    
        for key in supportData:
            supportData[key]=supportData[key]/lenD
            if(supportData[key]>=minisupport):
                rst.append(key)
            else:
                cutset.append(key)
        return rst,supportData,cutset
    

    上述代码在计算各个组合的频率。
    对于Ck里面的每一个组合c,遍历整个数据集,看这个c在数据集中出现了多少次。按照定义,c是t的子集说明 c在t出现了。

    rst是满足Ck内所有满足最小支持度要求的组合;同时supportData返回了Ck内所有组合的支持度,supportData是一个字典,key是基本元素的组合,而value是这个组合出现的频率。cutset用于返回Ck内那些被剪枝的组合。

    def genCj(Ck,k,Cutset={}):
        lenCk=len(Ck)
        Cj=set()
        for i in  range(lenCk):
            for j in range(i+1,lenCk):
                l1=list(Ck[i])[:k-1]
                l2=list(Ck[j])[:k-1]
                l1.sort()
                l2.sort()
                if(l1==l2):
                    t=Ck[i]|Ck[j]
                    f=0
                    for each in Cutset:
                        if set(each).issubset(t):
                            f=1
                            break
                    if(f==0):
                        Cj.add(t)
        return Cj
    

    genCj用于输入只含k个元素的若干组合Ck,以及已确定被剪枝的组合列表Cutset,输出含k+1个元素的所有可能的组合Cj。注意要先把前k-1个元素提取出来,然后排序,比较、如果相等后t不含有cutset的元素 再把合并后的加入。

    def apriori(dataset,minisupport=0.6):
        #from number i layer frequent item set generate i+1 th frequent item set.
        C1=createC1(dataset)
        Ck=C1
        k=1
        supportData={}
        CutSet=[]
        rstC=[]
        while Ck!=set():
            rst,support,cutset=scan(dataset,minisupport,Ck)
            rstC.append([rst])
            supportData.update(support)
            CutSet.append(cutset)
            Cj=genCj(rst,k,CutSet)
            k+=1
            Ck=Cj
    
        return rstC,supportData
    

    当第k层一直不空的时候,不断寻找新的组合。

    注意:关联分析的输入数据集中,每个样本的特征向量是一个集合,是无序的、确定的、互斥的。

    展开全文
  • 在美国有这样一家奇怪的超市,它将啤酒与尿布这样两个奇怪的东西放在一起进行销售,并且最终让啤酒与尿布这两个看起来没有...但这毕竟是事后分析,我们更应该关注的,是在这样的场景下,如何找出物品之间的关联规...

    在美国有这样一家奇怪的超市,它将啤酒与尿布这样两个奇怪的东西放在一起进行销售,并且最终让啤酒与尿布这两个看起来没有关联的东西的销量双双增加。这家超市的名字叫做沃尔玛。

    你会不会觉得有些不可思议?虽然事后证明这个案例确实有根据,美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布,而丈夫们在买尿布后又随手带回了他们喜欢的啤酒。但这毕竟是事后分析,我们更应该关注的,是在这样的场景下,如何找出物品之间的关联规则。接下来就来介绍下如何使用Apriori算法,来找到物品之间的关联规则吧。

    一. 关联分析概述

    选择物品间的关联规则也就是要寻找物品之间的潜在关系。要寻找这种关系,有两步,以超市为例

    1. 找出频繁一起出现的物品集的集合,我们称之为频繁项集。比如一个超市的频繁项集可能有{{啤酒,尿布},{鸡蛋,牛奶},{香蕉,苹果}}
    2. 频繁项集的基础上,使用关联规则算法找出其中物品的关联结果

    简单点说,就是先找频繁项集,再根据关联规则找关联物品。

    为什么要先找频繁项集呢?还是以超市为例,你想想啊,我们找物品关联规则的目的是什么,是为了提高物品的销售额。如果一个物品本身购买的人就不多,那么你再怎么提升,它也不会高到哪去。所以从效率和价值的角度来说,肯定是优先找出那些人们频繁购买的物品的关联物品。

    既然要找出物品的关联规则有两步,那我们也一步一步来。我们会先介绍如何用Apriori找出物品的频繁项集,然后下一篇会在Apriori处理后的频繁项集的基础上,进行物品的关联分析。

    二. Apriori算法基础概念

    在介绍Apriori算法之前,我们需要先了解几个概念,别担心,我们会结合下面的例子来进行说明的。

    这些是一个超市里面的一部分购买商品记录:

    交易编号购买商品
    0牛奶,洋葱,肉豆蔻,芸豆,鸡蛋,酸奶
    1莳萝,洋葱,肉豆蔻,芸豆,鸡蛋,酸奶
    2牛奶,苹果,芸豆,鸡蛋
    3牛奶,独角兽,玉米,芸豆,酸奶
    4玉米,洋葱,洋葱,芸豆,冰淇淋,鸡蛋

    2.1 关联分析的几个概念

    支持度(Support):支持度可以理解为物品当前流行程度。计算方式是:

    支持度 = (包含物品A的记录数量) / (总的记录数量)

    用上面的超市记录举例,一共有五个交易,牛奶出现在三个交易中,故而{牛奶}的支持度为3/5。{鸡蛋}的支持度是4/5。牛奶和鸡蛋同时出现的次数是2,故而{牛奶,鸡蛋}的支持度为2/5。

    置信度(Confidence):置信度是指如果购买物品A,有较大可能购买物品B。计算方式是这样:

    置信度( A -> B) = (包含物品A和B的记录数量) / (包含 A 的记录数量)

    举例:我们已经知道,(牛奶,鸡蛋)一起购买的次数是两次,鸡蛋的购买次数是4次。那么Confidence(牛奶->鸡蛋)的计算方式是Confidence(牛奶->鸡蛋)=2 / 4。

    提升度(Lift):提升度指当销售一个物品时,另一个物品销售率会增加多少。计算方式是:

    提升度( A -> B) = 置信度( A -> B) / (支持度 A)

    举例:上面我们计算了牛奶和鸡蛋的置信度Confidence(牛奶->鸡蛋)=2 / 4。牛奶的支持度Support(牛奶)=3 / 5,那么我们就能计算牛奶和鸡蛋的支持度Lift(牛奶->鸡蛋)=0.83
    当提升度(A->B)的值大于1的时候,说明物品A卖得越多,B也会卖得越多。而提升度等于1则意味着产品A和B之间没有关联。最后,提升度小于1那么意味着购买A反而会减少B的销量。

    其中支持度和Apriori相关,而置信度和提升度是下一篇寻找物品关联规则的时候会用到。

    2.2 Apriori 算法介绍

    Apriori的作用是根据物品间的支持度找出物品中的频繁项集。通过上面我们知道,支持度越高,说明物品越受欢迎。那么支持度怎么决定呢?这个是我们主观决定的,我们会给Apriori提供一个最小支持度参数,然后Apriori会返回比这个最小支持度高的那些频繁项集。

    说到这里,有人可能会发现,既然都知道了支持度的计算公式,那直接遍历所有组合计算它们的支持度不就可以了吗

    是的,没错。确实可以通过遍历所有组合就能找出所有频繁项集。但问题是遍历所有组合花的时间太多,效率太低,假设有N个物品,那么一共需要计算2^N-1次。每增加一个物品,数量级是成指数增长。而Apriori就是一种找出频繁项集的高效算法。它的核心就是下面这句话:

    某个项集是频繁的,那么它的所有子集也是频繁的

    这句话看起来是没什么用,但是反过来就很有用了。

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

    Apriori算法中的非频繁项集

    如图所示,我们发现{A,B}这个项集是非频繁的,那么{A,B}这个项集的超集,{A,B,C},{A,B,D}等等也都是非频繁的,这些就都可以忽略不去计算。

    运用Apriori算法的思想,我们就能去掉很多非频繁的项集,大大简化计算量。

    2.3 Apriori算法流程

    要使用Apriori算法,我们需要提供两个参数,数据集和最小支持度。我们从前面已经知道了Apriori会遍历所有的物品组合,怎么遍历呢?答案就是递归。先遍历1个物品组合的情况,剔除掉支持度低于最小支持度的数据项,然后用剩下的物品进行组合。遍历2个物品组合的情况,再剔除不满足条件的组合。不断递归下去,直到不再有物品可以组合。

    下面我们来用Apriori算法实战一下吧。

    三. Apriori算法实战

    我们用一个简单的例子来用一下Apriori吧,这里用到的库是mlxtend。

    在放代码之前,先介绍下Apriori算法的参数吧。

    def apriori(df, min_support=0.5,  
                use_colnames=False, 
                max_len=None)
    参数如下:
    df:这个不用说,就是我们的数据集。
    min_support:给定的最小支持度。
    use_colnames:默认False,则返回的物品组合用编号显示,为True的话直接显示物品名称。
    max_len:最大物品组合数,默认是None,不做限制。如果只需要计算两个物品组合的话,便将这个值设置为2。
    
    

    OK,接下来就来用一个简单的例子来看看怎么使用Apriori算法找到频繁项集吧。

    import pandas as pd
    from mlxtend.preprocessing import TransactionEncoder
    from mlxtend.frequent_patterns import apriori
    
    #设置数据集
    dataset = [['牛奶','洋葱','肉豆蔻','芸豆','鸡蛋','酸奶'],
            ['莳萝','洋葱','肉豆蔻','芸豆','鸡蛋','酸奶'],
            ['牛奶','苹果','芸豆','鸡蛋'],
            ['牛奶','独角兽','玉米','芸豆','酸奶'],
            ['玉米','洋葱','洋葱','芸豆','冰淇淋','鸡蛋']]
    		
    te = TransactionEncoder()
    #进行 one-hot 编码
    te_ary = te.fit(records).transform(records)
    df = pd.DataFrame(te_ary, columns=te.columns_)
    #利用 Apriori 找出频繁项集
    freq = apriori(df, min_support=0.05, use_colnames=True)
    
    

    首先,需要先将商品进行one-hot编码,编码后用boolean值表示。所谓ont-hot编码呢,直观来说就是有多少个状态就有多少比特,而且只有一个比特为1,其他全为0的一种码制。比如冰淇淋只存在最后一共交易单中,其他交易中都没出现。那冰淇淋就可以用[0,0,0,0,1]来表示

    这里编码后的数据如下:

         冰淇淋     洋葱     牛奶    独角兽     玉米    肉豆蔻    芸豆     苹果     莳萝     酸奶     鸡蛋
    0  False        True   True 	  False      False    True     True    False    False   True     True
    1  False        True  False 	  False      False    True     True    False     True   True     True
    2  False       False   True 	  False      False   False     True     True    False  False     True
    3  False       False   True 	   True       True   False     True    False    False   True    False
    4   True        True  False 	  False       True   False     True    False    False  False     True
    

    我们设定的最小支持度是0.6,那么只有支持度大于0.6的物品集合才是频繁项集,最终结果如下:

        support      itemsets
    0       0.6          (洋葱)
    1       0.6          (牛奶)
    2       1.0          (芸豆)
    3       0.6          (酸奶)
    4       0.8          (鸡蛋)
    5       0.6      (芸豆, 洋葱)
    6       0.6      (洋葱, 鸡蛋)
    7       0.6      (牛奶, 芸豆)
    8       0.6      (酸奶, 芸豆)
    9       0.8      (芸豆, 鸡蛋)
    10      0.6  (芸豆, 洋葱, 鸡蛋)
    

    四. 小结

    今天我们介绍了关联分析中会用到的几个概念,支持度,置信度,提升度。然后讲述了Apriori算法的作用,以及Apriori算法如何高效得找出物品的频繁项集。

    最后使用Apriori算法找出例子中的频繁项集。

    以上~

    展开全文
  • 你也能看懂的:灰色关联分析算法

    千次阅读 2020-02-11 16:54:09
    灰色关联分析是指对一个系统发展变化态势的定量描述和比较的方法,其基本思想是通过确定参考数据列和若干个比较数据列的几何形状相似程度来判断其联系是否紧密,它反映了曲线间的关联程度。 通常可以运用此方法来...

    灰色关联分析是指对一个系统发展变化态势的定量描述和比较的方法,其基本思想是通过确定参考数据列和若干个比较数据列的几何形状相似程度来判断其联系是否紧密,它反映了曲线间的关联程度。
    通常可以运用此方法来分析各个因素对于结果的影响程度,也可以运用此方法解决随时间变化的综合评价类问题,其核心是按照一定规则确立随时间变化的母序列,把各个评估对象随时间的变化作为子序列,求各个子序列与母序列的相关程度,依照相关性大小得出结论


    灰色关联分析的流程

    1. 根据分析目的确定分析指标体系,收集分析数据

    比如水果店里面每天卖苹果的总金额与哪些因素相关,定价、数量、大小、人流量等

    这 n 种数据构成矩阵:
    ( X 1 ′ , X 2 ′ , ⋯   , X n ′ ) = ( x 1 ′ ( 1 ) x 2 ′ ( 1 ) ⋯ x n ′ ( 1 ) x 1 ′ ( 2 ) x 2 ′ ( 2 ) ⋯ x n ′ ( 2 ) ⋮ ⋮ ⋮ ⋮ x 1 ′ ( m ) x 2 ′ ( m ) ⋯ x n ′ ( m ) ) (X_1',X_2',\cdots,X_n')=\begin{pmatrix} x_1^{'(1)} & x_2^{'(1)} & \cdots & x_n^{'(1)} \\ x_1^{'(2)} & x_2^{'(2)} & \cdots & x_n^{'(2)} \\ \vdots & \vdots & \vdots & \vdots \\ x_1^{'(m)} & x_2^{'(m)} & \cdots & x_n^{'(m)} \\ \end{pmatrix} (X1,X2,,Xn)=x1(1)x1(2)x1(m)x2(1)x2(2)x2(m)xn(1)xn(2)xn(m)

    1. 确定参考数据列

    上面的水果例子中,每天的总金额就是参考数据列,其它数据与其进行比较,得出相关度,这样就知道每种因素对其的影响

    参考数据列应该是一个理想的比较标准,可以以各指标的最优值(或最劣值)构成参考数据列,也可根据评价目的选择其它参照值

    记作:
    X 0 ′ = ( x 0 ′ ( 1 ) , x 0 ′ ( 1 ) , ⋯   , x 0 ′ ( 1 ) ) X_0'=(x_0^{'(1)},x_0^{'(1)}, \cdots,x_0^{'(1)}) X0=(x0(1),x0(1),,x0(1))

    1. 针对数据进行无量纲化处理(通常情况下需要)

    不同量纲造成不同指标的数据有大有小,为了消除不同变量不同量纲的影响因此在分析前需要先对数据进行处理,常见的处理方法可分为:标准化初值化。两者并没有什么固定的使用标准,初值化对数据格式要求更严格,建议使用均值法

    无量纲化后的数据序列形成如下矩阵:
    ( X 0 , X 1 , ⋯   , X n ) = ( x 1 ( 1 ) x 2 ( 1 ) ⋯ x n ( 1 ) x 1 ( 2 ) x 2 ( 2 ) ⋯ x n ( 2 ) ⋮ ⋮ ⋮ ⋮ x 1 ( m ) x 2 ( m ) ⋯ x n ( m ) ) (X_0,X_1,\cdots,X_n)=\begin{pmatrix} x_1^{(1)} & x_2^{(1)} & \cdots & x_n^{(1)} \\ x_1^{(2)} & x_2^{(2)} & \cdots & x_n^{(2)} \\ \vdots & \vdots & \vdots & \vdots \\ x_1^{(m)} & x_2^{(m)} & \cdots & x_n^{(m)} \\ \end{pmatrix} (X0,X1,,Xn)=x1(1)x1(2)x1(m)x2(1)x2(2)x2(m)xn(1)xn(2)xn(m)

    1. 计算关联系数
      ζ i ( k ) = min ⁡ i min ⁡ k ∣ x 0 ( k ) − x i ( k ) ∣ + ρ max ⁡ i max ⁡ k ∣ x 0 ( k ) − x i ( k ) ∣ ∣ x 0 ( k ) − x i ( k ) ∣ + ρ max ⁡ i max ⁡ k ∣ x 0 ( k ) − x i ( k ) ∣ \zeta_i(k) =\frac {\min_i \min_k|x_0(k)-x_i(k)|+\rho \max_i \max_k|x_0(k)-x_i(k)|}{|x_0(k)-x_i(k)|+\rho \max_i \max_k|x_0(k)-x_i(k)|} ζi(k)=x0(k)xi(k)+ρmaximaxkx0(k)xi(k)miniminkx0(k)xi(k)+ρmaximaxkx0(k)xi(k)

    ρ \rho ρ 为分辨系数, 0 < ρ < 1 0<ρ<1 0<ρ<1,若 ρ \rho ρ 越小,关联系数间差异越大,区分能力越强。通常 ρ \rho ρ 取 0.5

    看不懂没关系,可以直接套公式

    更为简便的计算方法:
    ζ i ( k ) = min ⁡ i ∣ x 0 ′ ( k ) − x i ′ ( k ) ∣ + ρ max ⁡ i ∣ x 0 ′ ( k ) − x i ′ ( k ) ∣ ∣ x 0 ′ ( k ) − x i ′ ( k ) ∣ + ρ max ⁡ i ∣ x 0 ′ ( k ) − x i ′ ( k ) ∣ \zeta_i(k) =\frac {\min_i |x_0'(k)-x_i'(k)|+\rho \max_i |x_0'(k)-x_i'(k)|}{|x_0'(k)-x_i'(k)|+\rho \max_i |x_0'(k)-x_i'(k)|} ζi(k)=x0(k)xi(k)+ρmaxix0(k)xi(k)minix0(k)xi(k)+ρmaxix0(k)xi(k)

    1. 计算关联度

    上一步计算的只是某一对象在某一因素下与标准的关联程度。然后就是用之前算的权作一个加权平均,就可以得到每个对象与标准的关联度 r i r_i ri
    r i = 1 n ∑ k = 1 n ζ i ( k ) r_i=\frac 1n \sum_{k=1}^n \zeta_i(k) ri=n1k=1nζi(k)

    1. 排序,得到关联度顺序了

    案例解读

    使用 MatLab 语言

    x1 = [1.14 1.49 1.69 2.12 2.43 4.32 5.92 6.07 7.85;3.30 3.47 3.61 3.80 4.00 4.19 4.42 4.61 4.80;6.00 6.00 6.00 7.50 7.50 7.50 9.00 9.00 9.00;1.20 1.20 1.80 1.80 1.80 2.40 2.70 3.60 4.00;4.87 5.89 6.76 7.97 8.84 10.05 11.31 12.25 11.64];
    %原始数据59列
    x = x1;
    %以第一行数据为参考数据
    %按照公式一步步计算
    for i=1:5
        for j=1:9
            x(i,j) = x(i,j)/x1(1,j);
        end
    end
    x1 = x;
    for i = 1:5
        for j = 1:9
            x(i,j) = abs(x(i,j)-x1(i,1));
        end
    end
    max = x(1,1);
    min = x(1,1);
    for i = 1:5
        for j = 1:9
            if x(i,j) >= max
                max = x(i,j);
            end
        end
    end
    for i = 1:5
        for j = 1:9
            if x(i,j) <= min
                min = x(i,j);
            end
        end
    end
    k = 0.5; %分辨系数取值
    l = (min+k*max)./(x+k*max); %求关联系数矩阵
    guanliandu = sum(l')/9;
    [rs,rind] = sort(guanliandu,'descend') %对关联度进行排序
    

    得出的结论:
    在这里插入图片描述

    展开全文
  • 1.什么是关联分析? 从大规模数据集中寻找物品间的隐含关系被称作关联分析(association analysis)或者关联规则学习(association rule learning)。 2.关联分析中的关系 频繁项集(frequent item sets)是经常...
  • 关联分析及常用的apriori算法和fp-growth算法做了较为详细的分析和改进。是本人自己结合资料整理而来
  • 关联规则算法是在大量数据事例中挖掘项集之间的关联或相关联系,它典型的应用就是购物篮分析,通过关联规则分析帮助我们发现交易数据库中不同的商品(项)之间的联系,找到顾客购买行为模式,如购买某一个商品对其它...
  • 关系数据库和其他信息存储中的大 量数据的项集之间发现有趣的频繁出现的模式 关联和相关性 应用: 购物篮分析分类设计捆绑销售和亏本销售分析 Web日志(点击流)分析,和DNA序列分析 尿布与啤酒典型关联分析案例 ...
  • 关联规则按照不同的标准,能用各种不同的方法分成不同类型。将关联规则分为挖掘频繁项集、闭频繁项集、被约束频繁项集、极大频繁项集,是根据挖掘模式的完全性分类的;将关联规则分为多层和单层关联规则,以及单位和...
  • 关联分析算法介绍以及案例实现

    千次阅读 2020-05-10 14:31:19
    关联分析又称关联挖掘:发现存在于大量数据集中的关联性或相关性,进行智能推荐。 事务 相当于用户的篮子,篮子里面可能是1项集,也可能是4项集。 项集 篮子里所有的物品构成一个集合。在关联分析中,包含0个或者多...
  • 01 项集 :在关联分析中,包括0个或多个项的集合被称为项集。如{啤酒,尿布,牛奶,花生}是一个4项集。 02支持度: 一个项集或者规则在所有事物中出现的频率,确定规则可以用于给定数据集的频繁程度。 03置信度: ...
  • 机器学习补充系列国际权威的学术组织the IEEE International Conference on Data Mining (ICDM,国际数据哇局会议) 2006年12月评选出了数据挖掘领域的十大经典算法:C4.5, k-Means, SVM, Apriori, EM, PageRank, ...
  • 首先导入包含apriori算法的mlxtend库,pip install mlxtend调用apriori进行关联规则分析,具体代码如下,其中数据集选取本博客 “机器学习算法——关联规则” 中的例子,可进行参考,设置最小支持度(min_support)...
  • 大数据时代:基于微软案例数据库数据挖掘知识点总结(Microsoft 关联规则分析算法) 原文:(原创)大数据时代:基于微软案例数据库数据挖掘知识点总结(Microsoft 关联规则分析算法)前言 本篇继续...
  • 用以前爬的知乎用户行为数据,跑了一下Apriori算法,发现了一些有意思的关联规则。以下是简略的分析过程。 数据采集 数据怎么来的?当然不是知乎给的,是爬虫来的。怎么爬的?这篇文章就不说了。 数据处理 之前...
  • 关联规则挖掘发现大量数据中项集之间有趣的关联或相关关系随着大量数据不停...分析关联规则的一个典型例子是购物篮分析该过程通过发现顾客放入其购物篮中不同商品之间的联系分析顾客的购买习惯通过了解哪些商品频繁地被...
  • Apriori算法对购物篮进行关联分析-Apriori算法进行购物篮关联分析.rar 大家好,出来乍到,看到好多高手分享自己的程序,我也想分享一下,做出自己的贡献。 虽然学MATLAB已经一年有余,但是一直忙着数学建模,对...
  • 关联分析——Apriori算法

    千次阅读 2018-06-13 11:50:15
    关联分析的目的就是要寻找事物之间的联系规律,发现它们之间的关联关系。关联分析是一种简单、实用的分析技术,就是发现存在于大量数据集中的关联性或相关性,从而描述了一个事物中某些属性同时出现的规律和模式。...
  • 光环大数据 --大数据培训 &人工智能培训 Apriori 算法实例 322 万知乎用户的关注话题关联分析 _光环大数据 用以前爬的知乎用户行为数据 跑了一下 Apriori 算法发现了一些有意思 的关联规则以下是简略的分析过程 数据...
  • 本篇继续我们的微软挖掘算法系列总结,前几篇我们分别介绍了:Microsoft决策树分析算法、Microsoft聚类分析算法、Microsoft Naive Bayes 算法、Microsoft 时序算法,后续还补充了二篇结果预测篇、Microsoft 时序...
  • Python关联分析之——Apriori算法

    万次阅读 2017-12-01 09:18:19
    使用Apriori算法进行关联分析Apriori原理 如果某个项集是频繁的,那么它的所有子集也是频繁的。即如果{0,1}是频繁的,则{0},{1}也是频繁的。 这个原理直观上并没有什么帮助,但如果反过来看,就有用了。 ...
  • 关联规则(Association Rules)是反映一个事物与其他事物之间的相互依存性和关联性,如果两个或多个事物之间存在一定的关联关系,那么,其中一个事物就能通过其他事物预测到。关联规则是数据挖掘的一个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 99,618
精华内容 39,847
关键字:

关联分析算法案例