精华内容
下载资源
问答
  • 关联规则Apriori算法例子
    千次阅读
    2021-02-25 17:34:50

    前言

    什么是AI?
    The theory and development of computer systems able to perform tasks normally requiring human intelligence.(–Oxford Dictionary)
    Using data to solve problems.(–cy)

    支持度、置信度、提升度

    1.支持度:是个百分比,指的是某个商品组合出现的次数与总次数之间的比例,支持度越高,代表这个组合出现的频率越大;
    2.置信度:置信度(A→B)是个条件概念。指的是当你购买了商品A,会有多大的概率购买商品B;
    3.提升度:商品A的出现,对商品B的出现概率提升的程度。提升度(A→B)=置信度(A→B)/支持度(B);
    提升度的三种可能:提升度(A→B)>1:代表有提升;提升度(A→B)=1:代表有没有提升,也没有下降;提升度(A→B)<1:代表有下降。

    举例

    有下图这样一组订单:
    在这里插入图片描述

    from efficient_apriori import apriori
    
    # 设置数据集
    transactions = [('牛奶','面包','尿布'),
            ('可乐','面包', '尿布', '啤酒'),
            ('牛奶','尿布', '啤酒', '鸡蛋'),
            ('面包', '牛奶', '尿布', '啤酒'),
            ('面包', '牛奶', '尿布', '可乐')]
    # 挖掘频繁项集和频繁规则
    itemsets, rules = apriori(transactions, min_support=0.5,  min_confidence=1)
    print("频繁项集:\n", itemsets)
    print("关联规则:\n", rules)
    

    频繁项集:
    {1: {(‘牛奶’,): 4, (‘尿布’,): 5, (‘面包’,): 4, (‘啤酒’,): 3}, 2: {(‘尿布’, ‘牛奶’): 4, (‘尿布’, ‘面包’): 4, (‘牛奶’, ‘面包’): 3, (‘啤酒’, ‘尿布’): 3}, 3: {(‘尿布’, ‘牛奶’, ‘面包’): 3}}
    关联规则:
    [{牛奶} -> {尿布}, {面包} -> {尿布}, {啤酒} -> {尿布}, {牛奶, 面包} -> {尿布}]

     #看一下频繁项集
    print(itemsets)
    print(type(itemsets))
    

    {1: {(‘牛奶’,): 4, (‘尿布’,): 5, (‘面包’,): 4, (‘啤酒’,): 3}, 2: {(‘尿布’, ‘牛奶’): 4, (‘尿布’, ‘面包’): 4, (‘牛奶’, ‘面包’): 3, (‘啤酒’, ‘尿布’): 3}, 3: {(‘尿布’, ‘牛奶’, ‘面包’): 3}}
    <class ‘dict’>

    for k,value in itemsets.items():#最前面的数字123代表商品组合数   分别代表123件商品的组合
        print(k,value)#{}括号里面又是():数字,()代表商品组合名称,:后面的数字代表()商品组合出现的次数
        #支持度小于0.5的已经被pass了,因为设置的min_support=0.5
    

    1 {(‘牛奶’,): 4, (‘尿布’,): 5, (‘面包’,): 4, (‘啤酒’,): 3}
    2 {(‘尿布’, ‘牛奶’): 4, (‘尿布’, ‘面包’): 4, (‘牛奶’, ‘面包’): 3, (‘啤酒’, ‘尿布’): 3}
    3 {(‘尿布’, ‘牛奶’, ‘面包’): 3}

    #看一下关联规则
    print(rules)#关联规则是置信度和支持度都满足
    #这里的意思就是说  {}里面的组合支持度 大于0.5    并且 {}->{}  前面括号对后面括号的置信度等于1(因为设置的置信度最小值是1  本身置信度最大值也是1print(type(rules))
    

    [{牛奶} -> {尿布}, {面包} -> {尿布}, {啤酒} -> {尿布}, {牛奶, 面包} -> {尿布}]
    <class ‘list’>

    总结

    (如果您发现我写的有错误,欢迎在评论区批评指正)。

    更多相关内容
  • 关联规则Apriori算法实验,内内含代码和。word报告,包您满意。关联规则Apriori算法实验,内内含代码和。word报告,包您满意。关联规则Apriori算法实验,内内含代码和。word报告,包您满意。关联规则Apriori算法实验...
  • 有关apriori算法的PPT,用于关联规则分析,里面分析了apriori算法的优缺点以及如何进行改进
  • 关联规则apriori算法

    2018-06-18 18:59:38
    关联规则算法,txt文件是训练的数据,可以参考,m文件是算法的代码文件
  • python源码集锦-基于关联规则 Apriori 算法的智能推荐
  • 关联规则Apriori算法在煤矿生产数据上的应用研究,戴明军,程灿,本文以C#.NET开发煤矿生产调度子系统为背景,为挖掘出煤矿生产数据之间的关联规则,采用了关联规则的经典算法Apriori算法对该子系统�
  • 关联规则Apriori算法

    千次阅读 多人点赞 2020-10-20 09:13:30
    参考《【机器学习实战-python3】使用Apriori算法进行关联 分析》,《 使用Apriori进行关联...关联规则的目的在于分析出经常出现在一起的物品的集合之间的关系。Apriori算法本质由两部分组成,分别是 频繁项集(frequ.

    参考《【机器学习实战-python3】使用Apriori算法进行关联 分析》,《 使用Apriori进行关联分析(一)》,《使用Apriori进行关联分析(二)》,《关于apriori算法中置信度、支持度怎么理解的问题


    关联规则的目的在于分析出经常出现在一起的物品的集合之间的关系。Apriori算法本质由两部分组成,分别是

    1. 频繁项集(frequent item sets)。包括计算:频繁项集的支持度(support)
    2. 关联规则(association rules)。包括计算:关联规则的置信度(confidence)

    接下来分别对这几个名词进行讲解,同时串通整个Apriori算法。

    1. 频繁项集(frequent item sets)

    假设下表为一个超市的交易记录,其中交易ID可以看作每个前来购物的顾客商品列表就是每个顾客购买的商品。

    交易ID商品列表
    0P1, P2, P5
    1P2, P4
    2P2, P3
    3P1, P2, P4
    4P1, P3
    5P2, P3
    6P1, P3
    7P1, P2, P3, P5
    8P1, P2, P3

    单是肉眼去观察的话,似乎顾客经常购买P1, P2这样的组合。这种的购物中出现的经常的组合,就是我们要找的频繁项集了。项集可以由一个商品组成,也可以由多个商品组成。比如{P1}是一个项集,{P1, P2}也是一个项集。

    现实生活中的数据肯定比这更加庞大,因此需要使用算法来帮助我们筛选出来哪些是频繁项集。

    1.1 频繁项集的支持度(support)和阈值

    一个项集的支持度被定义为数据集中包含该项集的记录所占的比例,比如在上表中,9个顾客中有4个购买了P1商品和P2商品,项集{P1, P2}的支持度就是 4 / 9 = 0.44 4/9=0.44 4/9=0.44支持项就是4项.

    通常来说,我们会手动设置支持度的阈值。比如设置阈值为50%,这样支持度小于该阈值的时候,就认为该项集并不频繁,也就没有挖掘关联规则的意义,因此不会进行后续的计算。

    1.2 频繁项集的特点

    频繁项集拥有如下特点:**如果某个项集是频繁的,那么它的所有子集也是频繁的。**比如项集{P1, P2}是频繁的,那么项集{P1}和{P2}也是频繁的。该原理倒过来推并不成立,也就是说当我们 只发现{P1}和{P2}是频繁的的时候,是无法推出项集{P1, P2}是频繁的,因为有可能他们的频繁是依靠和别的商品一起购买组合而成的。该原理可以用下图表示
    在这里插入图片描述

    已知阴影项集{2,3}是非频繁的。利用这个知识,我们就知道项集{0,2,3} ,{1,2,3}以及{0,1,2,3}也是非频繁的。该特点的最大用处是帮助我们减少计算,一旦计算出了{2,3}的支持度,知道它是非频繁的之后,就不需要再计算{0,2,3}、{1,2,3}和{0,1,2,3}的支持度,因为我们知道这些集合不会满足我们的要求。使用该原理就可以避免项集数目的指数增长,从而在合理时间内计算出频繁项集。

    1.3 频繁项集支持度计算方法

    频繁项集的计算方法并不复杂,主要就是三步的不断循环。

    1. 计算当前频繁项的所有并集,得到新的频繁项候选集
    2. 对得到的所有频繁项候选集进行支持项/支持度的计算
    3. 使用阈值过滤掉不符合要求的频繁项,最终剩下的成为新的频繁项

    在这里插入图片描述

    具体代码如下

    def loadDataSet():
        return [[1,2,5],[2,4],[2,3],[1,2,4],[1,3],[2,3],[1,3],[1,2,3,5],[1,2,3]]
    #1.构建候选1项集C1
    def createC1(dataSet):
        C1 = []
        for transaction in dataSet:
            for item in transaction:
                if not [item] in C1:
                    C1.append([item])
    
        C1.sort()
        return list(map(frozenset, C1))
    
    #将候选集Ck转换为频繁项集Lk
    #D:原始数据集
    #Cn: 候选集项Ck
    #minSupport:支持度的最小值
    def scanD(D, Ck, minSupport):
        #候选集计数
        ssCnt = {}
        for tid in D:
            for can in Ck:
                if can.issubset(tid):
                    if can not in ssCnt.keys(): ssCnt[can] = 1
                    else: ssCnt[can] += 1
    
        numItems = float(len(D))
        Lk= []     # 候选集项Cn生成的频繁项集Lk
        supportData = {}    #候选集项Cn的支持度字典
        #计算候选项集的支持度, supportData key:候选项, value:支持度
        for key in ssCnt:
            support = ssCnt[key] / numItems
            if support >= minSupport:
                Lk.append(key)
            supportData[key] = support
        return Lk, supportData
    
    #连接操作,将频繁Lk-1项集通过拼接转换为候选k项集
    def aprioriGen(Lk_1, k):
        Ck = []
        lenLk = len(Lk_1)
        for i in range(lenLk):
            L1 = list(Lk_1[i])[:k - 2]
            L1.sort()
            for j in range(i + 1, lenLk):
                #前k-2个项相同时,将两个集合合并
                L2 = list(Lk_1[j])[:k - 2]
                L2.sort()
                if L1 == L2:
                    Ck.append(Lk_1[i] | Lk_1[j])
    
        return Ck
    
    def apriori(dataSet, minSupport = 0.5):
        C1 = createC1(dataSet)
        L1, supportData = scanD(dataSet, C1, minSupport)
        L = [L1]
        k = 2
        while (len(L[k-2]) > 0):
            Lk_1 = L[k-2]
            Ck = aprioriGen(Lk_1, k)
            print("ck:",Ck)
            Lk, supK = scanD(dataSet, Ck, minSupport)
            supportData.update(supK)
            print("lk:", Lk)
            L.append(Lk)
            k += 1
    
        return L, supportData
    
    dataset = loadDataSet()
    L, supportData = apriori(dataset, minSupport=0.2)
    

    最终输出如下,其中ck就是频繁项候选集lk就是经过阈值筛选后得到的新的频繁项候选集。该结果与上图一致。

    ck: [frozenset({1, 2}), frozenset({1, 5}), frozenset({1, 4}), frozenset({1, 3}), frozenset({2, 5}), frozenset({2, 4}), frozenset({2, 3}), frozenset({4, 5}), frozenset({3, 5}), frozenset({3, 4})]
    lk: [frozenset({1, 2}), frozenset({1, 5}), frozenset({2, 5}), frozenset({2, 4}), frozenset({2, 3}), frozenset({1, 3})]
    ck: [frozenset({1, 2, 5}), frozenset({1, 2, 3}), frozenset({1, 3, 5}), frozenset({2, 4, 5}), frozenset({2, 3, 5}), frozenset({2, 3, 4})]
    lk: [frozenset({1, 2, 5}), frozenset({1, 2, 3})]
    ck: [frozenset({1, 2, 3, 5})]
    lk: []
    

    需要注意的是,在上述代码的aprioriGen方法中,假定购买商品是有顺序的,可以通过频繁2项集{P1,P2},{P1,P3}推导出频繁项{P1,P2,P3},但是不能通过频繁2项集{P3,P4},{P1,P3}推导出频繁项{P1,P3,P4}。如果去掉假设,则需要修改aprioriGen的代码:

    #将频繁Lk-1项集转换为候选k项集
    def aprioriGen(Lk_1, k):
        Ck = []
        lenLk = len(Lk_1)
        for i in range(lenLk):
            L1 = Lk_1[i]
            for j in range(i + 1, lenLk):
                L2 = Lk_1[j]
                if len(L1 & L2) == k - 2:
                    L1_2 = L1 | L2
                    if L1_2 not in Ck:
                        Ck.append(L1 | L2)
        return Ck
    

    2. 关联规则挖掘(association rules)

    2.1 关联规则的置信度(confidence)

    我们的目的是根据频繁项集挖掘出关联规则。关联规则的意思就是通过某个项集可以推导出另一个项集。比如一个频繁项集{P1, P2, P3},就可以推导出六个可能的关联规则。其中置信度最高的就是最有可能的关联规则。

    • {P1} → {P2, P3}
    • {P2} → {P1, P3}
    • {P3} → {P1, P2}
    • {P1, P2} → {P3}
    • {P2, P3} → {P1}
    • {P1, P3} → {P2}

    箭头左边的集合称为“前件”,右边集合称为“后件”,根据前件会有较大概率推导出后件,这个概率就是之前提到的置信度(confidence)。需要注意的是,如果A→B成立,B→A不一定成立。

    一个具有N个元素的频繁项集,共有M个可能的关联规则:
    M = ∑ N − 1 i = 1 C N i M = \sum_{N-1}^{i=1}C_N^i M=N1i=1CNi
    下图是一个频繁4项集的所有关联规则网格示意图
    M = C 4 1 + C 4 2 + C 4 3 = 14 M = C_4^1+C_4^2+C_4^3=14 M=C41+C42+C43=14

    上图中深色区域表示低可信度规则,如果012→3是一条低可信度规则,则所有其它3为后件的规则都是低可信度。这需要从可信度的概念去理解

    • Confidence(012→3) = P(3|0,1,2)
    • Confidence(01→23) = P(2,3|0,1)
    • P(3|0,1,2) >= P(2,3|0,1)

    由此可以对关联规则做剪枝处理。

    在这里插入图片描述

    2.2 关联规则置信度的计算过程

    置信度的计算公式为
    置 信 度 = 频 繁 项 集 的 出 现 数 量 某 可 能 规 则 的 出 现 数 量 置信度 =\frac{频繁项集的出现数量}{某可能规则的出现数量} =
    还是以上篇的超市交易数据为例,我们发现了如下的频繁项集:
    在这里插入图片描述

    对于寻找关联规则来说,频繁1项集L1没有用处,因为L1中的每个集合仅有一个数据项,至少有两个数据项才能生成A→B这样的关联规则。

    当最小置信度取0.5时,L2最终能够挖掘出9条关联规则:在这里插入图片描述

    以P2->P1为例,在本文最上面的表格中,P2出现了7次,频繁项集{P1, P2}的出现次数为4次,因此P2->P1的支持度就是4/7。同理,P1出现了6次,那么P1->P2的支持度就是4/6.

    从频繁3项集开始,挖掘的过程就较为复杂,要计算如{P1, P2}这样的复合频繁项集后件,并分别计算置信度。
    在这里插入图片描述
    假设有一个频繁4项集(这是杜撰的,文中的数据不能生成L4),其挖掘过程如下:
    在这里插入图片描述
    发掘关联规则的代码如下

    #生成关联规则
    #L: 频繁项集列表
    #supportData: 包含频繁项集支持数据的字典
    #minConf 最小置信度
    def generateRules(L, supportData, minConf=0.7):
        #包含置信度的规则列表
        bigRuleList = []
        #从频繁二项集开始遍历
        for i in range(1, len(L)):
            for freqSet in L[i]:
                H1 = [frozenset([item]) for item in freqSet]
                if (i > 1):
                    rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
                else:
                    calcConf(freqSet, H1, supportData, bigRuleList, minConf)
        return bigRuleList
    
    
    # 计算是否满足最小可信度
    def calcConf(freqSet, H, supportData, brl, minConf=0.7):
        prunedH = []
        #用每个conseq作为后件
        for conseq in H:
            # 计算置信度
            conf = supportData[freqSet] / supportData[freqSet - conseq]
            if conf >= minConf:
                print(freqSet - conseq, '-->', conseq, 'conf:', conf)
                # 元组中的三个元素:前件、后件、置信度
                brl.append((freqSet - conseq, conseq, conf))
                prunedH.append(conseq)
    
        #返回后件列表
        return prunedH
    
    
    # 对规则进行评估
    def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
        m = len(H[0])
        if (len(freqSet) > (m + 1)):
            Hmp1 = aprioriGen(H, m + 1)
           # print(1,H, Hmp1)
            Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
            if (len(Hmp1) > 0):
                rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
    
    generateRules(L, supportData)
    

    得到的结果如下所示

    frozenset({5}) --> frozenset({1}) conf: 1.0
    frozenset({5}) --> frozenset({2}) conf: 1.0
    frozenset({4}) --> frozenset({2}) conf: 1.0
    frozenset({5}) --> frozenset({1, 2}) conf: 1.0
    [(frozenset({5}), frozenset({1}), 1.0),
     (frozenset({5}), frozenset({2}), 1.0),
     (frozenset({4}), frozenset({2}), 1.0),
     (frozenset({5}), frozenset({1, 2}), 1.0)]
    

    3. 为什么需要置信度和支持度同时确定关联规则

    以超市购物为例。

    TIDItems
    1Bread, Milk
    2Break, Diaper, Beer, Eggs
    3Milk, Diaper, Beer, Coke
    4Bread, Milk, Diaper, Beer
    5Bread, Milk, Diaper, Coke

    TID是transaction ID 即交易编号,也就是有五个人在超市买了这样的东西(Iteams),现在我们统计一下,大家买的东西之间有没有什么规律,比如买面包的是不是很可能同时买牛奶这样的规律。

    在这里,支持度的计算过程为
    s u p p o r t = σ ( M i l k , D i a p e r , B e e r ) ∣ T ∣ = 2 5 = 0.4 support =\frac{\sigma(Milk, Diaper, Beer)}{|T|} = \frac{2}{5}=0.4 support=Tσ(Milk,Diaper,Beer)=52=0.4

    支持度越大,说明同时买这三个东西的人多,说明这三者之间有关系.

    但是当交易量特别大的时候,假如有一万个人买东西,只有10个人同时买了Milk、Diaper、Beer,但其他9990个人没有买这三者中的任何一个,那么此时S=10/10000=0.001。如果仅从这个0.001看,这三者之间没有任何关系,但是事实却不是这样,因为只有十个人这样买,并且同时买了这三种东西,所以他们之间应该是由关系的,而不是偶然。

    引入置信度的概念后,比如我们想看{Milk, Diaper}→{Beer}的置信度,则计算过程为
    c o n f i d e n c e = σ ( M i l k , D i a p e r , B e e r ) σ ( M i l k , D i a p e r ) = 2 3 = 0.67 confidence=\frac{\sigma(Milk, Diaper, Beer)}{\sigma(Milk, Diaper)} = \frac{2}{3}=0.67 confidence=σ(Milk,Diaper)σ(Milk,Diaper,Beer)=32=0.67
    和S支持度比较只有分母变了,变成了买了Milk和Diaper两种东西的人,这个式子是说买了Milk和Diaper两种东西的人里面又有多少人买了Beer这个东西!

    在上面支持度为0.001的情况下,此时置信度=10/10=100%!足以说明两者之间的关联性。

    但是只有置信度也是不可行的,比如10000个订单中,只有一个人同时购买了Milk,Diaper和Bear,那么此时的置信度为1/1=100%!可是支持度只有0.0001,非常的小。

    所以正确的有关联的判定是:置信度和支持度都应该比较大才可以认为这些东西之间有关联!

    展开全文
  • c++实现关联规则Apriori算法

    热门讨论 2014-10-30 12:18:35
    Apriori算法的c++实现vs2010也适用
  • 理解关联规则apriori算法:Apriori算法是第一个关联规则挖掘算法,也是最经典的算法,它利用逐层搜索的迭代方法找出数据库中项集的关系,以形成规则,其过程由连接【类矩阵运算】与剪枝【去掉那些没必要的中间结果】...

    理解关联规则apriori算法:Apriori算法是第一个关联规则挖掘算法,也是最经典的算法,它利用逐层搜索的迭代方法找出数据库中项集的关系,以形成规则,其过程由连接【类矩阵运算】与剪枝【去掉那些没必要的中间结果】组成。

    a6fad5b30952d956de3fe86297fcbe03.png

    理解关联规则apriori算法:

    一、概念

    表1 某超市的交易数据库交易号TID顾客购买的商品交易号TID顾客购买的商品

    T1bread, cream, milk, teaT6bread, tea

    T2bread, cream, milkT7beer, milk, tea

    T3cake, milkT8bread, tea

    T4milk, teaT9bread, cream, milk, tea

    T5bread, cake, milkT10bread, milk, tea

    定义一:设I={i1,i2,…,im},是m个不同的项目的集合,每个ik称为一个项目。项目的集合I称为项集。其元素的个数称为项集的长度,长度为k的项集称为k-项集。引例中每个商品就是一个项目,项集为I={bread, beer, cake,cream, milk, tea},I的长度为6。

    定义二:每笔交易T是项集I的一个子集。对应每一个交易有一个唯一标识交易号,记作TID。交易全体构成了交易数据库D,|D|等于D中交易的个数。引例中包含10笔交易,因此|D|=10。

    定义三:对于项集X,设定count(X⊆T)为交易集D中包含X的交易的数量,则项集X的支持度为:

    support(X)=count(X⊆T)/|D|

    引例中X={bread, milk}出现在T1,T2,T5,T9和T10中,所以支持度为0.5。

    定义四:最小支持度是项集的最小支持阀值,记为SUPmin,代表了用户关心的关联规则的最低重要性。支持度不小于SUPmin 的项集称为频繁集,长度为k的频繁集称为k-频繁集。如果设定SUPmin为0.3,引例中{bread, milk}的支持度是0.5,所以是2-频繁集。

    定义五:关联规则是一个蕴含式:

    R:X⇒Y

    其中X⊂I,Y⊂I,并且X∩Y=⌀。表示项集X在某一交易中出现,则导致Y以某一概率也会出现。用户关心的关联规则,可以用两个标准来衡量:支持度和可信度。

    定义六:关联规则R的支持度是交易集同时包含X和Y的交易数与|D|之比。即:

    support(X⇒Y)=count(X⋃Y)/|D|

    支持度反映了X、Y同时出现的概率。关联规则的支持度等于频繁集的支持度。

    定义七:对于关联规则R,可信度是指包含X和Y的交易数与包含X的交易数之比。即:

    confidence(X⇒Y)=support(X⇒Y)/support(X)

    可信度反映了如果交易中包含X,则交易包含Y的概率。一般来说,只有支持度和可信度较高的关联规则才是用户感兴趣的。

    定义八:设定关联规则的最小支持度和最小可信度为SUPmin和CONFmin。规则R的支持度和可信度均不小于SUPmin和CONFmin ,则称为强关联规则。关联规则挖掘的目的就是找出强关联规则,从而指导商家的决策。

    这八个定义包含了关联规则相关的几个重要基本概念,关联规则挖掘主要有两个问题:找出交易数据库中所有大于或等于用户指定的最小支持度的频繁项集。

    利用频繁项集生成所需要的关联规则,根据用户设定的最小可信度筛选出强关联规则。

    目前研究人员主要针对第一个问题进行研究,找出频繁集是比较困难的,而有了频繁集再生成强关联规则就相对容易了。

    二、理论基础

    首先来看一个频繁集的性质。

    定理:如果项目集X是频繁集,那么它的非空子集都是频繁集。

    根据定理,已知一个k-频繁集的项集X,X的所有k-1阶子集都肯定是频繁集,也就肯定可以找到两个k-1频繁集的项集,它们只有一项不同,且连接后等于X。这证明了通过连接k-1频繁集产生的k-候选集覆盖了k-频繁集。同时,如果k-候选集中的项集Y,包含有某个k-1阶子集不属于k-1频繁集,那么Y就不可能是频繁集,应该从候选集中裁剪掉。Apriori算法就是利用了频繁集的这个性质。

    三、算法步骤:

    首先是测试数据:交易ID商品ID列表

    T100I1,I2,I5

    T200I2,I4

    T300I2,I3

    T400I1,I2,I4

    T500I1,I3

    T600I2,I3

    T700I1,I3

    T800I1,I2,I3,I5

    T900I1,I2,I3

    算法的步骤图:

    ee5d4025b4515349f02d1d2241f49b6e.png

    可以看到,第三轮的候选集发生了明显的缩小,这是为什么呢?

    请注意取候选集的两个条件:

    1.两个K项集能够连接的两个条件是,它们有K-1项是相同的。所以,(I2,I4)和(I3,I5)这种是不能够进行连接的。缩小了候选集。

    2.如果一个项集是频繁集,那么它不存在不是子集的频繁集。比如(I1,I2)和(I1,I4)得到(I1,I2,I4),而(I1,I2,I4)存在子集(I1,I4)不是频繁集。缩小了候选集。

    第三轮得到的2个候选集,正好支持度等于最小支持度。所以,都算入频繁集。

    这时再看第四轮的候选集与频繁集结果为空

    可以看到,候选集和频繁集居然为空了!因为通过第三轮得到的频繁集自连接得到{I1,I2,I3,I5},它拥有子集{I2,I3,I5},而{I2,I3,I5}不是频繁集,不满足:频繁集的子集也是频繁集这一条件,所以被剪枝剪掉了。所以整个算法终止,取最后一次计算得到的频繁集作为最终的频繁集结果:

    也就是:['I1,I2,I3', 'I1,I2,I5']

    四、代码:

    编写Python代码实现Apriori算法。代码需要注意如下两点:由于Apriori算法假定项集中的项是按字典序排序的,而集合本身是无序的,所以我们在必要时需要进行set和list的转换;

    由于要使用字典(support_data)记录项集的支持度,需要用项集作为key,而可变集合无法作为字典的key,因此在合适时机应将项集转为固定集合frozenset。def local_data(file_path): import pandas as pd

    dt = pd.read_excel(file_path)

    data = dt['con']

    locdata = [] for i in data:

    locdata.append(str(i).split(",")) # print(locdata) # change to [[1,2,3],[1,2,3]]

    length = [] for i in locdata:

    length.append(len(i)) # 计算长度并存储

    # print(length)

    ki = length[length.index(max(length))] # print(length[length.index(max(length))]) # length.index(max(length)读取最大值的位置,然后再定位取出最大值

    return locdata,kidef create_C1(data_set): """

    Create frequent candidate 1-itemset C1 by scaning data set.

    Args:

    data_set: A list of transactions. Each transaction contains several items.

    Returns:

    C1: A set which contains all frequent candidate 1-itemsets """

    C1 = set() for t in data_set: for item in t:

    item_set = frozenset([item])

    C1.add(item_set) return C1def is_apriori(Ck_item, Lksub1): """

    Judge whether a frequent candidate k-itemset satisfy Apriori property.

    Args:

    Ck_item: a frequent candidate k-itemset in Ck which contains all frequent

    candidate k-itemsets.

    Lksub1: Lk-1, a set which contains all frequent candidate (k-1)-itemsets.

    Returns:

    True: satisfying Apriori property.

    False: Not satisfying Apriori property. """

    for item in Ck_item:

    sub_Ck = Ck_item - frozenset([item]) if sub_Ck not in Lksub1: return False return Truedef create_Ck(Lksub1, k): """

    Create Ck, a set which contains all all frequent candidate k-itemsets

    by Lk-1's own connection operation.

    Args:

    Lksub1: Lk-1, a set which contains all frequent candidate (k-1)-itemsets.

    k: the item number of a frequent itemset.

    Return:

    Ck: a set which contains all all frequent candidate k-itemsets. """

    Ck = set()

    len_Lksub1 = len(Lksub1)

    list_Lksub1 = list(Lksub1) for i in range(len_Lksub1): for j in range(1, len_Lksub1):

    l1 = list(list_Lksub1[i])

    l2 = list(list_Lksub1[j])

    l1.sort()

    l2.sort() if l1[0:k-2] == l2[0:k-2]:

    Ck_item = list_Lksub1[i] | list_Lksub1[j] # pruning

    if is_apriori(Ck_item, Lksub1):

    Ck.add(Ck_item) return Ckdef generate_Lk_by_Ck(data_set, Ck, min_support, support_data): """

    Generate Lk by executing a delete policy from Ck.

    Args:

    data_set: A list of transactions. Each transaction contains several items.

    Ck: A set which contains all all frequent candidate k-itemsets.

    min_support: The minimum support.

    support_data: A dictionary. The key is frequent itemset and the value is support.

    Returns:

    Lk: A set which contains all all frequent k-itemsets. """

    Lk = set()

    item_count = {} for t in data_set: for item in Ck: if item.issubset(t): if item not in item_count:

    item_count[item] = 1 else:

    item_count[item] += 1

    t_num = float(len(data_set)) for item in item_count: if (item_count[item] / t_num) >= min_support:

    Lk.add(item)

    support_data[item] = item_count[item] / t_num return Lkdef generate_L(data_set, k, min_support): """

    Generate all frequent itemsets.

    Args:

    data_set: A list of transactions. Each transaction contains several items.

    k: Maximum number of items for all frequent itemsets.

    min_support: The minimum support.

    Returns:

    L: The list of Lk.

    support_data: A dictionary. The key is frequent itemset and the value is support. """

    support_data = {}

    C1 = create_C1(data_set)

    L1 = generate_Lk_by_Ck(data_set, C1, min_support, support_data)

    Lksub1 = L1.copy()

    L = []

    L.append(Lksub1) for i in range(2, k+1):

    Ci = create_Ck(Lksub1, i)

    Li = generate_Lk_by_Ck(data_set, Ci, min_support, support_data)

    Lksub1 = Li.copy()

    L.append(Lksub1) return L, support_datadef generate_big_rules(L, support_data, min_conf): """

    Generate big rules from frequent itemsets.

    Args:

    L: The list of Lk.

    support_data: A dictionary. The key is frequent itemset and the value is support.

    min_conf: Minimal confidence.

    Returns:

    big_rule_list: A list which contains all big rules. Each big rule is represented

    as a 3-tuple. """

    big_rule_list = []

    sub_set_list = [] for i in range(0, len(L)): for freq_set in L[i]: for sub_set in sub_set_list: if sub_set.issubset(freq_set):

    conf = support_data[freq_set] / support_data[freq_set - sub_set]

    big_rule = (freq_set - sub_set, sub_set, conf) if conf >= min_conf and big_rule not in big_rule_list: # print freq_set-sub_set, " => ", sub_set, "conf: ", conf big_rule_list.append(big_rule)

    sub_set_list.append(freq_set) return big_rule_listif __name__ == "__main__": """

    Test """

    file_path = "test_aa.xlsx"

    data_set,k = local_data(file_path)

    L, support_data = generate_L(data_set, k, min_support=0.2)

    big_rules_list = generate_big_rules(L, support_data, min_conf=0.4) print(L) for Lk in L: if len(list(Lk)) == 0: break

    print("="*50) print("frequent " + str(len(list(Lk)[0])) + "-itemsets\t\tsupport") print("="*50) for freq_set in Lk: print(freq_set, support_data[freq_set]) print() print("Big Rules") for item in big_rules_list: print(item[0], "=>", item[1], "conf: ", item[2])

    文件格式:

    test_aa.xlsxname con

    T1 2,3,5T2 1,2,4T3 3,5T5 2,3,4T6 2,3,5T7 1,2,4T8 3,5T9 2,3,4T10 1,2,3,4,5

    展开全文
  • 自己写的数据挖掘 关联规则 Apriori算法 matlab实现 分了许多个文件 结构清晰
  • 关联规则挖掘算法apriori算法的实现
  • 电子科技大学数据挖掘课程 第二次实验 关联规则挖掘 实验报告及代码实现 包括频繁项集获取过程 关联规则获取过程 自认为理解&写得还是很透彻的哈哈哈 没看懂可以来找我~
  • 环境python版本:3.5数据来源数据来自51CTO网站的分享,点此下载关联规则所谓关联规则,就是指现实中同时发生两种不同事情之间的相关联程度,具体分析可以参考这篇博客,讲的很清晰数据分析这是数据文件数据文件其中...

    环境

    python版本:3.5

    数据来源

    数据来自51CTO网站的分享,点此下载

    关联规则

    所谓关联规则,就是指现实中同时发生两种不同事情之间的相关联程度,具体分析可以参考这篇博客,讲的很清晰

    数据分析

    这是数据文件

    43b3761f1433?from=message&isappinstalled=0

    数据文件

    其中movies中电影信息的内容如图所示

    43b3761f1433?from=message&isappinstalled=0

    movies.dat

    每行分别为电影id,电影名字,电影类型,每项之间用::分隔,rating.dat为收集的用户打分记录,users.dat为用户id对应的用户信息,personalRating.txt为个人打分,用来找到规律后为个人推荐电影,ratings.dat文件内容如图所示

    43b3761f1433?from=message&isappinstalled=0

    ratings.dat

    其中分别为用户id,电影id,评分(1-5分),评分时间,总共一百万行多点的数据。我设置评分3分以上算是喜欢,最小支持度为0.2,最小置信度为0.5,下面是代码实现

    # -*- coding: utf-8 -*-

    """

    Apriori exercise.

    Created on Sun Oct 26 11:09:03 2017

    @author: FWW

    """

    import time

    def createC1( dataSet ):

    '''

    构建初始候选项集的列表,即所有候选项集只包含一个元素,

    C1是大小为1的所有候选项集的集合

    '''

    C1 = []

    for transaction in dataSet:

    for item in transaction:

    if [ item ] not in C1:

    C1.append( [ item ] )

    C1.sort()

    return list(map( frozenset, C1 ))

    def scanD( D, Ck, minSupport ):

    '''

    计算Ck中的项集在事务集合D的每个transactions中的支持度,

    返回满足最小支持度的项集的集合,和所有项集支持度信息的字典。

    '''

    ssCnt = {}

    for tid in D:

    # 对于每一条transaction

    for can in Ck:

    # 对于每一个候选项集can,检查是否是transaction的一部分

    # 即该候选can是否得到transaction的支持

    if can.issubset( tid ):

    ssCnt[ can ] = ssCnt.get( can, 0) + 1

    numItems = float( len( D ) )

    retList = []

    supportData = {}

    for key in ssCnt:

    # 每个项集的支持度

    support = ssCnt[ key ] / numItems

    # 将满足最小支持度的项集,加入retList

    if support >= minSupport:

    retList.insert( 0, key )

    # 汇总支持度数据

    supportData[ key ] = support

    return retList, supportData

    # Aprior算法

    def aprioriGen( Lk, k ):

    '''

    由初始候选项集的集合Lk生成新的生成候选项集,

    k表示生成的新项集中所含有的元素个数

    '''

    retList = []

    lenLk = len( Lk )

    for i in range( lenLk ):

    for j in range( i + 1, lenLk ):

    L1 = list( Lk[ i ] )[ : k - 2 ];

    L2 = list( Lk[ j ] )[ : k - 2 ];

    L1.sort();L2.sort()

    if L1 == L2:

    retList.append( Lk[ i ] | Lk[ j ] )

    return retList

    def apriori( dataSet, minSupport = 0.5 ):

    # 构建初始候选项集C1

    C1 = createC1( dataSet )

    # 将dataSet集合化,以满足scanD的格式要求

    D = list(map( set, dataSet ))

    # 构建初始的频繁项集,即所有项集只有一个元素

    L1, suppData = scanD( D, C1, minSupport )

    L = [ L1 ]

    # 最初的L1中的每个项集含有一个元素,新生成的

    # 项集应该含有2个元素,所以 k=2

    k = 2

    while ( len( L[ k - 2 ] ) > 0 ):

    Ck = aprioriGen( L[ k - 2 ], k )

    Lk, supK = scanD( D, Ck, minSupport )

    # 将新的项集的支持度数据加入原来的总支持度字典中

    suppData.update( supK )

    # 将符合最小支持度要求的项集加入L

    L.append( Lk )

    # 新生成的项集中的元素个数应不断增加

    k += 1

    # 返回所有满足条件的频繁项集的列表,和所有候选项集的支持度信息

    return L, suppData

    def calcConf( freqSet, H, supportData, brl, minConf=0.5 ):

    '''

    计算规则的可信度,返回满足最小可信度的规则。

    freqSet(frozenset):频繁项集

    H(frozenset):频繁项集中所有的元素

    supportData(dic):频繁项集中所有元素的支持度

    brl(tuple):满足可信度条件的关联规则

    minConf(float):最小可信度

    '''

    prunedH = []

    for conseq in H:

    conf = supportData[ freqSet ] / supportData[ freqSet - conseq ]

    if conf >= minConf:

    #print (freqSet - conseq, '-->', conseq, 'conf:', conf)

    brl.append( ( freqSet - conseq, conseq, conf ) )

    prunedH.append( conseq )

    return prunedH

    def rulesFromConseq( freqSet, H, supportData, brl, minConf=0.5 ):

    '''

    对频繁项集中元素超过2的项集进行合并。

    freqSet(frozenset):频繁项集

    H(frozenset):频繁项集中的所有元素,即可以出现在规则右部的元素

    supportData(dict):所有项集的支持度信息

    brl(tuple):生成的规则

    '''

    m = len( H[ 0 ] )

    if m == 1:

    calcConf( freqSet, H , supportData, brl, minConf )

    # 查看频繁项集是否大到移除大小为 m 的子集

    if len( freqSet ) > m + 1:

    Hmp1 = aprioriGen( H, m + 1 )

    Hmp1 = calcConf( freqSet, Hmp1, supportData, brl, minConf )

    # 如果不止一条规则满足要求,进一步递归合并

    if len( Hmp1 ) > 1:

    rulesFromConseq( freqSet, Hmp1, supportData, brl, minConf )

    def recommendMovies(rules,personal_list,movie_list):

    recommend_list = []

    sup_list = []

    for rule in rules:

    if rule[0] <= personal_list:

    for movie in rule[1]:

    if movie_list[movie-1] not in recommend_list:

    recommend_list.append(movie_list[movie-1])

    sup_list.append(rule[2])

    for recommend in recommend_list:

    i = recommend_list.index(recommend)

    print('Recommend you to watch',recommend,',',round(sup_list[i]*100,2),'% people who is similar to you like it!')

    def generateRules( L, supportData, minConf=0.5 ):

    '''

    根据频繁项集和最小可信度生成规则。

    L(list):存储频繁项集

    supportData(dict):存储着所有项集(不仅仅是频繁项集)的支持度

    minConf(float):最小可信度

    '''

    bigRuleList = []

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

    for freqSet in L[ i ]:

    # 对于每一个频繁项集的集合freqSet

    H1 = [ frozenset( [ item ] ) for item in freqSet ]

    # 如果频繁项集中的元素个数大于2,需要进一步合并

    if i > 1:

    rulesFromConseq( freqSet, H1, supportData, bigRuleList, minConf )

    else:

    calcConf( freqSet, H1, supportData, bigRuleList, minConf )

    return bigRuleList

    if __name__ == '__main__':

    # 导入数据集

    start_time = time.time()

    file_object = open('ratings.dat')

    movies_object = open('movies.dat')

    personal_object = open('personalRatings.txt')

    file_list = []

    try:

    all_the_text = file_object.read()

    origin_list = (line.split('::') for line in all_the_text.split('\n'))

    tem_list = []

    for line in origin_list:

    if len(file_list)

    file_list.append(tem_list)

    tem_list = []

    else:

    if int(line[2])>3:

    tem_list.append(int(line[1]))

    movies_text = movies_object.read()

    movies_list = []

    for item in (line.split('::') for line in movies_text.split('\n')):

    if item[1] not in movies_list:

    movies_list.append(item[1])

    personal_text = personal_object.read()

    personal_list = []

    for item in (line.split('::') for line in personal_text.split('\n')):

    if int(item[2])>3:

    personal_list.append(int(item[1]))

    finally:

    file_object.close()

    movies_object.close()

    personal_object.close()

    print('Read file sucess in',time.time()-start_time,'s')

    # 选择频繁项集

    L, suppData = apriori( file_list, 0.2 )

    rules = generateRules( L, suppData, minConf=0.5 )

    #print ('rules:\n', rules)

    print ('Caculate rules success in',time.time()-start_time,'s')

    recommendMovies(rules,frozenset(personal_list),movies_list)

    print ('The program completes in',time.time()-start_time,'s')

    运行结果

    43b3761f1433?from=message&isappinstalled=0

    2017-11-05 14-53-20屏幕截图.png

    读文件用了1.3秒,运行花了14秒,相信之后用numpy数组改进一下运行速度会更快

    展开全文
  • 关联规则Apriori算法实例

    千次阅读 2019-10-18 11:02:55
    Apriori算法关联规则计算结果Apriori算法 关联规则 以下数据使用关联规则计算 import pandas as pd #import Apriori from apriori import * inputfile ='../menu_orders.xls' outputfile = 'tmp/apriori_rules.xls...
  • 1.R语言 2.关联规则 3.apriori算法
  • 数据挖掘关联规则Apriori算法的一种新改进,白东玲,郭庆平,关联规则算法的研究在数据挖掘算法的研究中占有相当重要的地位。关联规则算法的核心是Apriori 算法,但随着对关联规则研究的深入,�
  • 关联规则Apriori算法及实现(python)

    千次阅读 2018-08-12 17:39:53
    Apriori算法就是利用了频繁集的这个性质。 三、算法步骤 假如有项目集合T={1,2,3,4,5},有事务集T: 事务集T 集合内容 事务集T 集合内容 T1 1,2,3 T5 1,3,5 T2 1,...
  • 提出了采用关联规则Apriori算法对煤矿生产调度子系统进行频繁模式数据挖掘的方案,详细描述了对煤矿生产数据进行预处理以及运用Apriori算法对预处理后的数据挖掘频繁项集的过程,分析了频繁项集中关联规则的含义,并...
  • 关联规则算法是在一堆数据集中寻找数据之间的某种关联,通过该算法我们可以对数据集做关联分析——在大规模的数据中寻找有趣关系的任务。这些关系可以有两种形式:频繁项集、关联规则。 频繁项集:经常出现在一块的...
  • 数据挖掘中关联规则Apriori算法.pdf
  • 关联规则Apriori算法导语mlxtend实现Apriori算法 导语 关联规则: 是反映一个事物与其他事物之间的相互依存性和关联性 常用于实体商店或在线电商的推荐系统:通过对顾客的购买记录数据库进行关联规则挖掘,最终目的...
  • 关联规则 Apriori算法应用于试卷成绩分析中.首先对数据进行预处理,然后使用 Apriori算法挖掘学生各科目试卷成绩的优良影响关系,最终产生关联规则.用所获得的知识指导学生的学习及今后的工作.
  • java实现apriori算法进行关联规则挖掘
  • 针对Apriori算法存在多次扫描数据库及产生大量候选项集的缺陷,提出了一种改进算法。该算法只需扫描数据库一次,并将事务变换成二进制存储到数据库,可节省存储空间、提高速度。实验结果表明,改进算法挖掘关联规则的...
  • 本文简单介绍传统数据挖掘关联规则算法中的Apriori算法,以及在挖掘中医医案辨证规律中的应用。并简单分析传统算法缺点,提出简要的改进思路。 文章目录一、关联规则简介二、Apriori算法简介三、Apriori步骤Step1 找...
  • 基于数据挖掘关联规则Apriori算法的优化对策分析.pdf
  • 基于关联规则Apriori算法的物联网海量数据挖掘系统研究.pdf
  • 数据挖掘关联规则Apriori算法的一种新改进:一、概述本篇博文主要阐述数据挖掘相关的关联规则挖掘的算法(Apriori算法)。主要介绍关联规则的基|下载前务必先预览,自己验证一下是不是你要下载的文档!

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,812
精华内容 3,924
关键字:

关联规则apriori算法