精华内容
下载资源
问答
  • Apriori 关联规则算法

    2013-11-12 19:45:41
    Python版本的Apriori关联规则算法
  • Apriori关联规则算法

    2012-05-24 19:21:05
    Apriori关联规则算法源代码目前已提出了许多挖掘关联规则的算法,其中最 为经典的是Ap riori算法[ 123 ] ,算法思想是使用逐层搜索的迭代方法。算法主要包括三个步骤:连接步、剪枝步和扫描数据库。而本文通过对剪枝步...
  • C语言实现的Apriori关联规则算法 先通过扫描数据库D得到那些支持度不小于用户给定的最小支持度minsup的频繁项集L1。然后同样通过多次循环扫描数据库D,分别得到频繁项集L2,L3, . . . ,Lk。
  • Apriori关联规则算法(AR算法)理解笔记 1、有关的几个概念 事务和项集 项目 可以是一种商品,一个网页链接或一个险种 项集 是若干个 项目 的 集合 ,若项集包含k个项目,则称该项集为k-项集 事务 由 序号 和 项集 ...

    Apriori关联规则算法(AR算法)理解笔记

    1、有关的几个概念

    事务和项集

    项目 可以是一种商品,一个网页链接或一个险种

    项集 是若干个 项目集合 ,若项集包含k个项目,则称该项集为k-项集

    事务 由 序号 和 项集 组成

    序号 是确定一个 事务 的唯一标志

    关联规则

    频繁项集:经常同时出现的一些项目的集合

    关联规则:项集A与项集B的相互依存性和关联性。如果存在A->B的蕴含式,则说明两种项目之间存在很强的某种联系

    2、重要的三个核心概念

    支持度

    支持度用于衡量规则在数据库中出现的频率

    例如:项目X和项目Y同时出现的概率
    在这里插入图片描述

    置信度

    置信度用于衡量规则的强弱程度

    例如:包含项目X的事务中同时也包含项目Y的概率,反映X出现条件下Y出现的可能性。
    在这里插入图片描述
    最小支持度是用户定义衡量支持度的一个阈值,表示项目集在统计意义上的最低重要性
    最小置信度是用户定义的衡量置信度的一个阈值,表示关联规则的最低可靠性
    同时满足最小支持度和最小置信度的规则称为强规则

    项目集格空间理论

    主要包括两条定理:
    1、频繁项目集的所有子集仍是频繁项目集
    2、非频繁项目集的所有超集是非频繁项目集

    3、代码部分

    首先是主模块,python执行的地方

    if __name__ == '__main__':   
        myDat = loadDataSet()    
        L, suppData = apriori(myDat, 0.22)
        print("所有规则的置信度信息:")
        rules = generateRules(L,suppData,0.1)
    

    loadDataSet这个函数是用来构建一个数据集的,主模块调用这个函数赋值给了myDat

    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]]
    

    createC1这个函数在apriori函数中被调用,传入参数myDat,这个函数的目的在提取出所有的单项,并用frozenset把它们冻结,在for循环遍历的第一次中,transaction是[1,2,5],item是1,把item变为[[1]]加入C中。遍历完成后,C经过sort排序的结果是[ [1],[2],[3],[4],[5] ]。

    map(function,iterable)函数会把iterable中的每一个元素通过function生成的返回值构建新列表,因为map是一个迭代器,所以需要list(map())把它变为个列表才能返回,不然返回的是内存地址。

    结果是这样:[frozenset({1}), frozenset({2}), frozenset({3}), frozenset({4}), frozenset({5})]

    def createC1(dataSet):
        C = []
        for transaction in dataSet:
            for item in transaction:
                if [ item ] not in C:
                    C.append([item])
        C.sort()
        return list(map(frozenset, C))
    

    scanD这个函数apriori函数中被调用了4次,在外面1次,在while循环中3次,D中传入的参数是myDat,Ck依次传入的参数是:

    1. [frozenset({1}), frozenset({2}), frozenset({3}), frozenset({4}), frozenset({5})]
    2. [frozenset({3, 4}), frozenset({3, 5}), frozenset({2, 3}), frozenset({1, 3}), frozenset({4, 5}), frozenset({2, 4}), frozenset({1, 4}), frozenset({2, 5}), frozenset({1, 5}), frozenset({1, 2})]
    3. [frozenset({1, 2, 3}), frozenset({1, 3, 5}), frozenset({2, 3, 4}), frozenset({2, 3, 5}), frozenset({1, 2, 4}), frozenset({2, 4, 5}), frozenset({1, 2, 5})]
    4. [frozenset({1, 2, 3, 5})]

    minSupport传入最小支持度阈值0.22,scanD这个函数的目的是通过计算传入的Ck中的每个元素在D的每个元素中出现的次数:
    ssCnt[can] = ssCnt.get(can, 0) + 1
    再除以匹配的次数一共9次,从而得到Ck中每个元素的支持度:
    support = ssCnt[key] / numItems
    并用 if 语句比对minSupport,将满足最小支持度的项集放入retList集合中,将所有项集的支持度放入supportData字典中

    def scanD(D, Ck, minSupport):
        ssCnt = {}
        for tid in D:
            for can in Ck:     
                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       
            if support >= minSupport:
                retList.insert(0, key)
            supportData[key] = support
        return retList, supportData
    

    aprioriGen这个函数在apriori函数中被调用了3次,Ck和 k 依次传入参数为:

    1. k = 2 [frozenset({3}), frozenset({4}), frozenset({5}), frozenset({2}), frozenset({1})]
    2. k=3 [frozenset({1, 3}), frozenset({2, 3}), frozenset({2, 4}), frozenset({1, 2}), frozenset({1, 5}), frozenset({2, 5})]
    3. k=4 [frozenset({1, 2, 3}), frozenset({1, 2, 5})]

    aprioriGen这个函数的目的是通过排列组合从k-1-项集中生成候选k-项集,即从1-项集中生成候选2-项集,从2-项集中生成候选3-项集

    def aprioriGen(Ck, k):
        retList = []
        lenCk = len(Ck)
        for i in range( lenCk ):
            for j in range( i + 1, lenCk ):
                L1 = Ck[ i ] |Ck[ j ]
                if(len(L1)==k):
                    if L1 not in retList:
                        retList.append( L1 ) 
    
        return retList
    

    apriori函数是在AR算法中计算符合最小支持度的项集的集成函数,它分别调用了aprioriGen函数和scanD函数来生成项集和筛选项集,最终返回:
    列表L:所有满足最小支持度要求的项集
    字典supportData:所有项集对应的支持度(除支持度为0的项集外)

    def apriori(D, minSupport):
        C1=createC1(D)
        L1, suppData = scanD(D, C1, minSupport)
        L = [L1]
    #   这里是一个[[]],所以后面的L[0]是指[3,4,5,2,1],循环就为[[单项集],[双项集],[三项集]]
        k = 2    
        while (len(L[k-2]) > 0):
            Ck = aprioriGen(L[k-2], k)
            Lk, supK = scanD(D, Ck, minSupport)        
            suppData.update(supK)        
            L.append(Lk)        
            k += 1
        return L, suppData
    

    generateRules这个函数是在满足最小置信度条件下,筛选出元素与频繁项集中的关联规则和计算其置信度的集成函数。传入的参数L为所有满足最小支持度要求的项集,supportData为所有项集对应的支持度,minConf最小置信度为0.1(默认0.7)。

    len(L)=4,i=1,2,3。L=[ [1-项集],[2-项集],[3项集],[ ] ],H1把2-项集和3-项集拆回成1-项集。

    它分别调用了rulesFromConseq函数把3-项集重组为2-项集便于生成1-项集与2项集的关联规则和calcConf函数用于计算置信度。

    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 = []
        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:
        #检查频繁项集是否大到移除大小为m的子集
            Hmp1 = aprioriGen(H, m+1)
            Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
            #calcConf函数中的prunedH赋给了Hmp1
            #如果不止一条规则满足要求,进一步递归合并
            if len(Hmp1) > 1:
                rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
    
    展开全文
  • 本章使用Apriori关联规则算法实现购物篮分析,发现超市不同商品之间的关联关系,并根据商品之间的关联规则制定销售策略。 1背景与挖掘目标 现代商品种类繁多,顾客往往会由于需要购买的商品众多而变得疲于选择,且...

    购物篮分析是商业领域最前沿、最具挑战性的问题之一,也是许多企业研究的重点问题。购物篮分析是通过发现顾客在一次购买行为中放入购物篮中不同商品之间的关联,研究客户的购买行为,从而辅助零售企业制定营销策略的一种数据分析方法。

    本章使用Apriori关联规则算法实现购物篮分析,发现超市不同商品之间的关联关系,并根据商品之间的关联规则制定销售策略。

    1背景与挖掘目标

    现代商品种类繁多,顾客往往会由于需要购买的商品众多而变得疲于选择,且顾客并不会因为商品选择丰富而选择购买更多的商品。繁杂的选购过程往往会给顾客疲惫的购物体验。对于某些商品,顾客会选择同时购买,如面包与牛奶、薯片与可乐等,当面包与牛奶或者薯片与可乐分布在商场的两侧,且距离十分遥远时,顾客购买的欲望就会减少,在时间紧迫的情况下顾客甚至会放弃购买某些计划购买的商品。相反,把牛奶与面包摆放在相邻的位置,既给顾客提供便利,提升购物体验,又提高顾客购买的概率,达到了促销的目的。许多商场以打折方式作为主要促销手段,以更少的利润为代价获得更高的销量。打折往往会使顾客增加原计划购买商品的数量,对于原计划不打算购买且不必要的商品,打折的吸引力远远不足。而正确的商品摆放却能提醒顾客购买某些必需品,甚至吸引他们购买感兴趣的商品。

    因此,为了获得最大的销售利润,销售什么样的商品,采用什么样的促销策略,商品在货架上如何摆放,了解顾客的购买习惯和偏好对销售商尤其重要。通过对商场销售数据进行分析,从而得到顾客的购买行为特征,并根据发现的规律而采取有效的行动,制定商品摆放、商品定价、新商品采购计划,对商场增加销量并获取最大利润有重要意义。

    请根据提供的数据实现以下目标。

    1)构建零售商品的Apriori关联规则模型,分析商品之间的关联性。

    2)根据模型结果给出销售策略。

    2分析方法与过程

    本次数据挖掘建模的总体流程如图 1所示。
    在这里插入图片描述
    图1 购物篮分析流程图

    购物篮关联规则挖掘主要步骤如下。

    1)对原始数据进行数据探索性分析,分析商品的热销情况与商品结构。

    2)对原始数据进行数据预处理,转换数据形式,使之符合Apriori关联规则算法要求。

    3)在步骤(2)得到的建模数据基础上,采用Apriori关联规则算法,调整模型输入参数,完成商品关联性分析。

    4)结合实际业务,对模型结果进行分析,根据分析结果给出销售建议,最后输出关联规则结果。

    2.1数据探索分析

    本案例的探索性分析是查看数据特征,以及对商品热销情况和商品结构分析。

    探索数据特征是了解数据的第一步。分析商品热销情况和商品结构,是为了更好地实现企业的经营目标。商品管理应坚持商品齐全和商品优选的原则,产品销售基本满足“二八定律”即80%的销售额是由20%的商品创造的,这些商品是企业主要盈利商品,要作为商品管理的重中之重。商品热销情况分析和商品结构分析也是商品管理不可或缺的一部分,其中商品结构分析能够帮助保证商品的齐全性,热销情况分析可以助力于商品优选。

    某商品零售企业共收集了9835个购物篮的数据,购物篮数据主要包括3个属性:id、Goods和Types。属性的具体说明如表 1所示。
    表1 购物篮属性说明
    在这里插入图片描述
    微信关注泰迪学院,回复购物篮领取数据和代码

    1.数据特征

    探索数据的特征,查看每列属性、最大值、最小值,是了解数据的第一步。查看数据特征,如代码清单 81所示。
    代码清单1 查看数据特征

    import numpy as np
    import pandas as pd
    
    inputfile = '../data/GoodsOrder.csv'   # 输入的数据文件
    data = pd.read_csv(inputfile,encoding='gbk')  # 读取数据
    data.info()  # 查看数据属性
    
    data = data['id']
    description = [data.count(),data.min(), data.max()]  # 依次计算总数、最小值、最大值
    description = pd.DataFrame(description, index=['Count','Min', 'Max']).T  # 将结果存入数据框
    print('描述性统计结果:\n',np.round(description))  # 输出结果
    

    微信关注泰迪学院,回复购物篮领取数据和代码

    根据代码清单1可得,每列属性共有43367个观测值,并不存在缺失值。查看“id”属性的大值和最小值,可知某商品零售企业共收集了9835个购物篮的数据,其中包含169个不同的商品类别,售出商品总数为43367件。

    2.分析热销商品

    商品热销情况分析是商品管理不可或缺的一部分,热销情况分析可以助力于商品优选。计算销量排行前10商品的销量及占比,并绘制条形图显示销量前10商品的销量情况,如代码清单2所示。
    代码清单2 分析热销商品

    # 销量排行前10商品的销量及其占比
    import pandas as pd
    inputfile = '../data/GoodsOrder.csv'  # 输入的数据文件
    data = pd.read_csv(inputfile,encoding='gbk')  # 读取数据
    group = data.groupby(['Goods']).count().reset_index()  # 对商品进行分类汇总
    sorted=group.sort_values('id',ascending=False)
    print('销量排行前10商品的销量:\n', sorted[:10])  # 排序并查看前10位热销商品
    
    # 画条形图展示出销量排行前10商品的销量
    import matplotlib.pyplot as plt
    x = sorted[:10]['Goods']
    y = sorted[:10]['id']
    plt.figure(figsize=(8, 4))  # 设置画布大小 
    plt.barh(x,y)
    plt.rcParams['font.sans-serif'] = 'SimHei'
    plt.xlabel('销量')  # 设置x轴标题
    plt.ylabel('商品类别')  # 设置y轴标题
    plt.title('商品的销量TOP10')  # 设置标题
    plt.savefig('../tmp/top10.png')  # 把图片以.png格式保存
    plt.show()  # 展示图片
    
    # 销量排行前10商品的销量占比
    data_nums = data.shape[0]
    for idnex, row in sorted[:10].iterrows():
        print(row['Goods'],row['id'],row['id']/data_nums)
    

    微信关注泰迪学院,回复购物篮领取数据和代码

    根据代码清单2可得到销量排行前10商品的销量及其占比情况,如表2和图2所示。

    表2 销量排行前10商品的销量及其占比
    在这里插入图片描述
    在这里插入图片描述
    图2 销量排行前10的商品销量情况

    通过分析热销商品的结果可知,全脂牛奶销售量最高,销量为2513件,占比5.795%;其次是其他蔬菜、面包卷和苏打,占比分别为4.388%、4.171%、3.955%。

    3.分析商品结构

    对每一类商品的热销程度进行分析,有利于商家制定商品在货架的摆放策略和位置,若是某类商品较为热销,商场可以把此类商品摆放到商场的中心位置,方便顾客选购。或者放在商场深处位置,使顾客在购买热销商品前经过非热销商品,增加在非热销商品处的停留时间,促进非热销产品的销量。

    原始数据中的商品本身已经过归类处理,但是部分商品还是存在一定的重叠,故再次对其进行归类处理。分析归类后各类别商品的销量及其占比,并绘制饼图显示各类商品的销量占比情况,如代码清单3所示。

    代码清单3 各类别商品的销量及其占比

    import pandas as pd
    inputfile1 = '../data/GoodsOrder.csv'
    inputfile2 = '../data/GoodsTypes.csv'
    data = pd.read_csv(inputfile1,encoding='gbk')
    types = pd.read_csv(inputfile2,encoding='gbk')  # 读入数据
    
    group = data.groupby(['Goods']).count().reset_index()
    sort = group.sort_values('id',ascending=False).reset_index()
    data_nums = data.shape[0]  # 总量
    del sort['index']
    
    sort_links = pd.merge(sort,types)  # 合并两个datafreame 根据type
    # 根据类别求和,每个商品类别的总量,并排序
    sort_link = sort_links.groupby(['Types']).sum().reset_index()
    sort_link = sort_link.sort_values('id',ascending=False).reset_index()
    del sort_link['index']  # 删除“index”列
    
    # 求百分比,然后更换列名,最后输出到文件
    sort_link['count'] = sort_link.apply(lambda line: line['id']/data_nums,axis=1)
    sort_link.rename(columns={'count':'percent'},inplace=True)
    print('各类别商品的销量及其占比:\n',sort_link)
    outfile1 = '../tmp/percent.csv'
    sort_link.to_csv(outfile1,index=False,header=True,encoding='gbk')  # 保存结果
    
    # 画饼图展示每类商品销量占比
    import matplotlib.pyplot as plt
    data = sort_link['percent']
    labels = sort_link['Types']
    plt.figure(figsize=(8, 6))  # 设置画布大小   
    plt.pie(data,labels=labels,autopct='%1.2f%%')
    plt.rcParams['font.sans-serif'] = 'SimHei'
    plt.title('每类商品销量占比')  # 设置标题
    plt.savefig('../tmp/persent.png')  # 把图片以.png格式保存
    plt.show()
    

    微信关注泰迪学院,回复购物篮领取数据和代码

    根据代码清单3可得各类别商品的销量及其占比情况,结果如表4、图3所示。

    表4 各类别商品的销量及其占比
    在这里插入图片描述
    在这里插入图片描述
    图3 各类别商品的销量占比情况

    通过分析各类别商品的销量及其占比情况可知,非酒精饮料、西点、果蔬三类商品销量差距不大,占总销量的50%左右,同时,根据大类划分发现和食品相关的类的销量总和接近90%,说明了顾客倾向于购买此类产品,而其余商品仅为商场满足顾客的其余需求而设定,并非销售的主力军。

    进一步查看销量第一的非酒精饮料类商品的内部商品结构,并绘制饼图显示其销量占比情况,如代码清单4所示。
    代码清单4 非酒精饮料内部商品的销量及其占比

    # 先筛选“非酒精饮料”类型的商品,然后求百分比,然后输出结果到文件。
    selected = sort_links.loc[sort_links['Types'] == '非酒精饮料']  # 挑选商品类别为“非酒精饮料”并排序
    child_nums = selected['id'].sum()  # 对所有的“非酒精饮料”求和
    selected['child_percent'] = selected.apply(lambda line: line['id']/child_nums,axis=1)  # 求百分比
    selected.rename(columns={'id':'count'},inplace=True)
    print('非酒精饮料内部商品的销量及其占比:\n',selected)
    outfile2 = '../tmp/child_percent.csv'
    sort_link.to_csv(outfile2,index=False,header=True,encoding='gbk')  # 输出结果
    
    # 画饼图展示非酒精饮品内部各商品的销量占比
    import matplotlib.pyplot as plt
    data = selected['child_percent']
    labels = selected['Goods']
    plt.figure(figsize=(8,6))  # 设置画布大小 
    explode = (0.02,0.03,0.04,0.05,0.06,0.07,0.08,0.08,0.3,0.1,0.3)  # 设置每一块分割出的间隙大小
    plt.pie(data,explode=explode,labels=labels,autopct='%1.2f%%',
          pctdistance=1.1,labeldistance=1.2)
    plt.rcParams['font.sans-serif'] = 'SimHei'
    plt.title("非酒精饮料内部各商品的销量占比")  # 设置标题
    plt.axis('equal')
    plt.savefig('../tmp/child_persent.png')  # 保存图形
    plt.show()  # 展示图形
    

    微信关注泰迪学院,回复购物篮领取数据和代码

    根据代码清单4可得非酒精饮料内部商品的销量及其占比情况,如表5、图4所示。
    表5 非酒精饮料内部商品的销量及其占比
    在这里插入图片描述
    在这里插入图片描述
    图4 非酒精饮料内部商品的销量占比情况

    通过分析非酒精饮料内部商品的销量及其占情况可知,全脂牛奶的销量在非酒精饮料的总销量中占比超过33%,前3种非酒精饮料的销量在非酒精饮料的总销量中占比接近70%,说明了大部分顾客到店购买的饮料为这三种,需要时常注意货物的库存,定期补货必不可少。

    2.2数据预处理

    通过对数据探索分析,发现数据数据完整,并不存在缺失值。建模之前需要建模之前需要转变数据的格式,才能使用apriori函数进行关联分析。对数据进行转换,如代码清单 5所示。
    代码清单5 数据转换

    import pandas as pd
    inputfile='../data/GoodsOrder.csv'
    data = pd.read_csv(inputfile,encoding='gbk')
    
    # 根据id对“Goods”列合并,并使用“,”将各商品隔开
    data['Goods'] = data['Goods'].apply(lambda x:','+x)
    data = data.groupby('id').sum().reset_index()
    
    # 对合并的商品列转换数据格式
    data['Goods'] = data['Goods'].apply(lambda x :[x[1:]])
    data_list = list(data['Goods'])
    
    # 分割商品名为每个元素
    data_translation = []
    for i in data_list:
        p = i[0].split(',')
        data_translation.append(p)
    print('数据转换结果的前5个元素:\n', data_translation[0:5])
    

    微信关注泰迪学院,回复购物篮领取数据和代码

    2.3模型构建

    本案例的目标是探索商品之间的关联关系,因此采用关联规则算法,挖掘它们之间的关联关系。关联规则算法主要用于寻找数据中项集之间的关联关系。它揭示了数据项间的未知关系,基于样本的统计规律,进行关联规则分析。根据所分析的关联关系,可从一个属性的信息来推断另一个属性的信息。当置信度达到某一阈值时,就可以认为规则成立。Apriori算法是常用的关联规则算法之一,也是最为经典的分析频繁项集的算法,第一次实现在大数据集上可行的关联规则提取的算法。除此之外,还有FP-Tree算法,Eclat算法和灰色关联算法等。本案例主要使用Apriori算法进行分析。

    1.商品购物篮关联规则模型构建

    本次商品购物篮关联规则建模的流程如图5所示。
    在这里插入图片描述
    图5 商品购物篮关联规则模型建模流程图

    由图5可知,模型主要由输入、算法处理、输出3个部分组成。输入部分包括:建模样本数据的输入;建模参数的输入。算法处理部分是采用Apriori关联规则算法进行处理。输出部分为采用Apriori关联规则算法进行处理后的结果。

    模型具体实现步骤为:首先设置建模参数最小支持度、最小置信度,输入建模样本数据;然后采用Apriori关联规则算法对建模的样本数据进行分析,以模型参数设置的最小支持度、最小置信度以及分析目标作为条件,如果所有的规则都不满足条件,则需要重新调整模型参数,否则输出关联规则结果。

    目前,如何设置最小支持度与最小置信度,并没有统一的标准。大部分都是根据业务经验设置初始值,然后经过多次调整,获取与业务相符的关联规则结果。本案例经过多次调整并结合实际业务分析,选取模型的输入参数为:最小支持度0.02、最小置信度0.35。其关联规则代码如代码清单6所示。
    代码清单6 构建关联规则模型

    from numpy import *
     
    def loadDataSet():
        return [['a', 'c', 'e'], ['b', 'd'], ['b', 'c'], ['a', 'b', 'c', 'd'], ['a', 'b'], ['b', 'c'], ['a', 'b'],
                ['a', 'b', 'c', 'e'], ['a', 'b', 'c'], ['a', 'c', 'e']]
     
    def createC1(dataSet):
        C1 = []
        for transaction in dataSet:
            for item in transaction:
                if not [item] in C1:
                    C1.append([item])
        C1.sort()
        # 映射为frozenset唯一性的,可使用其构造字典
        return list(map(frozenset, C1))     
        
    # 从候选K项集到频繁K项集(支持度计算)
    def scanD(D, Ck, minSupport):
        ssCnt = {}
        for tid in D:   # 遍历数据集
            for can in Ck:  # 遍历候选项
                if can.issubset(tid):  # 判断候选项中是否含数据集的各项
                    if not can in ssCnt:
                        ssCnt[can] = 1  # 不含设为1
                    else:
                        ssCnt[can] += 1  # 有则计数加1
        numItems = float(len(D))  # 数据集大小
        retList = []  # L1初始化
        supportData = {}  # 记录候选项中各个数据的支持度
        for key in ssCnt:
            support = ssCnt[key] / numItems  # 计算支持度
            if support >= minSupport:
                retList.insert(0, key)  # 满足条件加入L1中
                supportData[key] = support  
        return retList, supportData
     
    def calSupport(D, Ck, min_support):
        dict_sup = {}
        for i in D:
            for j in Ck:
                if j.issubset(i):
                    if not j in dict_sup:
                        dict_sup[j] = 1
                    else:
                        dict_sup[j] += 1
        sumCount = float(len(D))
        supportData = {}
        relist = []
        for i in dict_sup:
            temp_sup = dict_sup[i] / sumCount
            if temp_sup >= min_support:
                relist.append(i)
    # 此处可设置返回全部的支持度数据(或者频繁项集的支持度数据)
                supportData[i] = temp_sup
        return relist, supportData
     
    # 改进剪枝算法
    def aprioriGen(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:  # 前k-1项相等,则可相乘,这样可防止重复项出现
                    # 进行剪枝(a1为k项集中的一个元素,b为它的所有k-1项子集)
                    a = Lk[i] | Lk[j]  # a为frozenset()集合
                    a1 = list(a)
                    b = []
                    # 遍历取出每一个元素,转换为set,依次从a1中剔除该元素,并加入到b中
                    for q in range(len(a1)):
                        t = [a1[q]]
                        tt = frozenset(set(a1) - set(t))
                        b.append(tt)
                    t = 0
                    for w in b:
                        # 当b(即所有k-1项子集)都是Lk(频繁的)的子集,则保留,否则删除
                        if w in Lk:
                            t += 1
                    if t == len(b):
                        retList.append(b[0] | b[1])
        return retList
    
    def apriori(dataSet, minSupport=0.2):
    # 前3条语句是对计算查找单个元素中的频繁项集
        C1 = createC1(dataSet)
        D = list(map(set, dataSet))  # 使用list()转换为列表
        L1, supportData = calSupport(D, C1, minSupport)
        L = [L1]  # 加列表框,使得1项集为一个单独元素
        k = 2
        while (len(L[k - 2]) > 0):  # 是否还有候选集
            Ck = aprioriGen(L[k - 2], k)
            Lk, supK = scanD(D, Ck, minSupport)  # scan DB to get Lk
            supportData.update(supK)  # 把supk的键值对添加到supportData里
            L.append(Lk)  # L最后一个值为空集
            k += 1
        del L[-1]  # 删除最后一个空集
        return L, supportData  # L为频繁项集,为一个列表,1,2,3项集分别为一个元素
    
    # 生成集合的所有子集
    def getSubset(fromList, toList):
        for i in range(len(fromList)):
            t = [fromList[i]]
            tt = frozenset(set(fromList) - set(t))
            if not tt in toList:
                toList.append(tt)
                tt = list(tt)
                if len(tt) > 1:
                    getSubset(tt, toList)
     
    def calcConf(freqSet, H, supportData, ruleList, minConf=0.7):
        for conseq in H:  #遍历H中的所有项集并计算它们的可信度值
            conf = supportData[freqSet] / supportData[freqSet - conseq]  # 可信度计算,结合支持度数据
            # 提升度lift计算lift = p(a & b) / p(a)*p(b)
            lift = supportData[freqSet] / (supportData[conseq] * supportData[freqSet - conseq])
     
            if conf >= minConf and lift > 1:
                print(freqSet - conseq, '-->', conseq, '支持度', round(supportData[freqSet], 6), '置信度:', round(conf, 6),
                      'lift值为:', round(lift, 6))
                ruleList.append((freqSet - conseq, conseq, conf))
     
    # 生成规则
    def gen_rule(L, supportData, minConf0.7):
        bigRuleList = []
        for i in range(1, len(L)):  # 从二项集开始计算
            for freqSet in L[i]:  # freqSet为所有的k项集
                # 求该三项集的所有非空子集,1项集,2项集,直到k-1项集,用H1表示,为list类型,里面为frozenset类型,
                H1 = list(freqSet)
                all_subset = []
                getSubset(H1, all_subset)  # 生成所有的子集
                calcConf(freqSet, all_subset, supportData, bigRuleList, minConf)
        return bigRuleList
     
    if __name__ == '__main__':
        dataSet = data_translation
        L, supportData = apriori(dataSet, minSupport0.02)
        rule = gen_rule(L, supportData, minConf0.35)
    

    微信关注泰迪学院,回复购物篮领取数据和代码

    运行代码清单6得到的结果如下。

    frozenset({'水果/蔬菜汁'}) --> frozenset({'全脂牛奶'}) 支持度 0.02664 置信度: 0.368495 lift值为: 1.44216
    frozenset({'人造黄油'}) --> frozenset({'全脂牛奶'}) 支持度 0.024199 置信度: 0.413194 lift值为: 1.617098
    ...      ...      ...      ...
    frozenset({'根茎类蔬菜', '其他蔬菜'}) --> frozenset({'全脂牛奶'}) 支持度 0.023183 置信度: 0.48927 lift值为: 1.914833
    

    2.模型分析

    根据代码清单6运行结果,我们得出了26个关联规则。根据规则结果,可整理出购物篮关联规则模型结果,如表6所示。

    表6 购物篮关联规则模型结果

    在这里插入图片描述
    根据表6中的输出结果,对其中4条进行解释分析如下。

    (1){‘其他蔬菜’, ‘酸奶’}=>{‘全脂牛奶’}支持度为2.23%,置信度最大为51,29%。说明同时购买酸奶,其他蔬菜和全脂牛奶这3种商品的概率达51,29%,而这种情况发生的可能性为2.23%。

    (2){‘其他蔬菜’}=>{‘全脂牛奶’}支持度最大为7.48%,置信度为38.68%。说明同时购买其他蔬菜和全脂牛奶这2种商品的概率达38.68%,而这种情况发生的可能性为7.48%。

    (3){‘根茎类蔬菜’}=>{‘全脂牛奶’}支持度为4.89%,置信度为44.87%。说明同时购买根茎类蔬菜和全脂牛奶这三种商品的概率达44.87%,而这种情况发生的可能性为4.89%。

    (4){‘根茎类蔬菜’}=>{‘其他蔬菜’}支持度为4.74%,置信度为43.47%。说明同时根茎类蔬菜和其他蔬菜这2种商品的概率达43.47%,而这种情况发生的可能性为4.74%。

    综合表6以及输出结果分析,顾客购买酸奶和其他蔬菜的时候会同时购买全脂牛奶,其置信度最大达到51,29%。其他蔬菜、根茎类蔬菜和全脂牛奶同时购买的概率较高。

    对于模型结果,从购物者角度进行分析:现代生活中,大多数购物者为家庭煮妇,购买的商品大部分是食品,随着生活质量和健康意识的增加,其他蔬菜、根茎类蔬菜和全脂牛奶均为现代家庭每日饮食所需品,因此,其他蔬菜、根茎类蔬菜和全脂牛奶同时购买的概率较高符合现代人们的生活健康意识。

    3.模型应用

    模型结果表明顾客购买商品的时候会同时购买全脂牛奶。因此,商场应该根据实际情况将全脂牛奶放在顾客购买商品的必经之路,或者商场显眼位置,方便顾客拿取。其他蔬菜、根茎类蔬菜、酸奶油、猪肉、黄油、本地蛋类和多种水果同时购买的概率较高,可以考虑捆绑销售,或者适当调整商场布置,将这些商品的距离尽量拉近,提升购物体验。

    小结

    本案例主要结合商品零售购物篮的项目,重点介绍了关联规则算法中的Apriori算法在商品零售购物篮分析案例中的应用。过程中详细的分析了商品零售的现状与问题,同时给出某商场的商品零售数据,分析了商品的热销程度,最后通过Apriori算法构建相应模型,并根据模型结果制定销售策略。

    展开全文
  • 数据挖掘(一)——Apriori关联规则算法及评估 1、Apriori算法概述 直接上算法的手推图: 左上角是原数据,下半部分是步骤,用于挖掘最大频繁项集。 2、频繁项集评估参数 3、Python代码实现

    数据挖掘(一)——Apriori关联规则算法及评估

    1、Apriori算法概述

      大家不要害怕,在《数据挖掘概念与技术》一书中,Apriori算法是作为第一个数据挖掘算法来讲的,没有大公式,而且很容易理解, 直接上算法的手推图:


      图片左上角是原数据,图片下半部分是步骤。

      首先查找频繁一项集,项集就是项的集合(项,如:面包、牛奶等等),频繁项集可以理解为出现频度高或出现次数多的项集,如频繁{,面包,牛奶}表示买面包就很可能买牛奶或买牛奶就很可能买面包。怎么查找频繁一项集呢?先把所有的一项集列出来,{面包}{牛奶}{啤酒}{尿尿布},然后统计每个一项集的支持度计数,比如对于{面包},小明、小红、小赵三个人买了,那{面包}的支持度计数就是3,以此类推。然后我们设定支持度阈值为2,也就是说买面包的人少于两个我们就懒得考虑这一项了,因为买面包的人很少那挖掘它的意义也不大,据此找到支持度计数大于等于2的项集,作为频繁一项集。如图中1、2步。

      第二步是由频繁一项集产生二项集再选出频繁二项集(这里我们先不考虑先验性质),直接将频繁一项集按照不重复的原则组合成二项集,可以理解为排列组合,四个里面挑两个,C42=6C^2_4=6,一共有6个二项集{,面包,牛奶}{,面包,啤酒}{,尿面包,尿布}{,牛奶,啤酒}{,尿牛奶,尿布}{,尿啤酒,尿布}。然后计算每个二项集的支持度计数,比如{,面包,牛奶},同时买面包牛奶的是小红、小赵两人,所以的支持度计数是2,以此类推。之后再将支持度计数和阈值比较,选出频繁二项集{,面包,牛奶}{,尿啤酒,尿布}。如图中3、4步。

      第三步是构造三项集并选出频繁三项集,直接将频繁一项集和频繁二项集进行组合(后续构造n项集也是频繁n-1项集与频繁一项集组合),仍按照不重复原则,构造出三项集,然后计算支持度计数,并与阈值比较得到频繁三项集。这里我们发现所有三项集都不满足支持度阈值的要求,所以算法结束,给出结果,最终频繁项集为{,面包,牛奶}{,尿啤酒,尿布}。如图中第5步。

      没错,你就是呼唤胜利的男神!通过上述分析,你已经基本掌握了Apriori算法!

      那我们再来说一下先验性质是什么东西,有助于我们进一步学习Apriori算法。

      先验性质:频繁项集的所有非空子集也一定是频繁的。简单讲,{,,面包,牛奶,啤酒}是频繁三项集,则{,面包,牛奶}{,面包,啤酒}{,牛奶,啤酒}{牛奶}{啤酒}都是频繁项集。为什么是这样呢?因为我们的n项集都是由频繁n-1项集产生的呀!当你了解了先验性质,那么不难想到,只要我找到最高频繁项集,那所有的频繁项集就都有了,完美!

    2、频繁项集评估参数(进阶)

      当你找到了频繁项集,下一步就是对频繁项集进行评估了,也就是看看这个频繁项集有多么频繁。给出新的参数:置信度,公式如下:

    confidence(>)=count({,})count({})confidence(面包—>牛奶) = \frac {count(\{面包,牛奶\})}{count(\{面包\})}

      不要一看公式就跑哦!上面公式很简单,count就是我们之前算的支持度计数,confidence就是置信度。我们算一下之前例子中频繁二项集{,面包,牛奶}的置信度:confidence=2/32/2=0.661confidence=2/3或2/2=0.66或1,为什么多出来一个“或”?可以这样理解confidence(面包—>牛奶)表示买面包的同时还买牛奶的概率(0.66),confidence(牛奶—>面包)表示买牛奶的同时还买面包的概率(1)。那么我到底按0.66还是1?没错,按均值0.83!这个0.83有一个很高级的名字叫“Kulczynski”,简称“Kulc”。此时,你得到了衡量频繁程度的利器!Kulc越接近1代表频繁程度越高。(有兴趣的同学可自行查看其它评估方法,如提升度、全置信度、最大置信度、余弦度量,不过Kulc是被书中推荐的,因其不受零事务的影响,至于什么是关联规则中的零事务影响也可以自己查。)

      只有Kulc还不行,我们还得衡量一下confidence(面包—>牛奶)和confidence(牛奶—>面包)有多大的差距,引入不平衡比

    IR({,})=count({}count({})count({})+count({})count({,})IR(\{面包,牛奶\}) =\frac {|count(\{面包\}-count(\{牛奶\})|}{count(\{面包\})+count(\{牛奶\})-count(\{面包,牛奶\})}

      不平衡比反映了买面包的人和买牛奶的人之间的差距(比如10000个人买了面包而只有100个人买了牛奶),不平衡比越接近1,表示两者差距越大,其频繁的可靠性就越差。

    3、Python代码实现

      十几行代码就能实现??!!

    import numpy as np
    from Apriori_category import Apriori
    
    item = 5#项的个数(面包、牛奶、火腿、咖啡)
    TID = 10#事务个数(A,B,C,D,E,F,G)
    Confidence = 3#最小支持度
    data = np.random.randint(0,2,(10,5))#10行5列的 0、1 随机数组
    print("原数据:\n" + str(data) + "\n")
    my_Apriori = Apriori(data, item, TID, Confidence)
    my_Apriori.Frequent_item_one()
    my_Apriori.Frequent_item_two()#分开封装为了发掘频繁二项集的置信度
    my_Apriori.Frequent_item_many()
    

      别做梦了,还有个自己定义的类,相当于自定义函数。(别怕,基本上复制粘贴就能运行,末尾说明怎么让它顺利运行):

    import numpy as np
        
    class Apriori():
    #挖掘最大频繁项集,并给出频繁两项集的Kulc和不平衡比
        def __init__ (self, data, item, TID, Confidence):
            #给出数据集、项数、事务数、支持度阈值
            self.data = data
            self.item = item
            self.TID = TID
            self.Confidence = Confidence
            
        def Frequent_item_one (self):
            #计算频繁一项集,结果保存至lin
            count = np.zeros([1, self.item],int)#频繁一项集支持度计数
            flag = np.zeros([1, self.item],int)#辅助旗
            a = np.zeros([1, self.item],int)#辅助
            self.o = np.zeros([1],int)#辅助
            for i in range(0, self.item):
                count[0, i] = int(sum(self.data[:,[i]]))#计算支持度
                if count[0, i] >= self.Confidence:
                    flag[0, i] = 1
                    a[0, i] = i#如果flag中记录该项为频繁项则将其索引放入a             
            lin = a[np.nonzero(a)]#去掉a中的0元素
            if flag[0, 0] == 1:#如果第0列也是频繁项则把0放进lin中
                lin = np.hstack((self.o, lin))#满足频繁项的索引
            self.lin = lin#保存频繁一项索引和支持度集用于后续计算
            self.count = count[0, self.lin]
            
        def Frequent_item_two (self):
            #计算频繁二项集的索引和支持度 
            count_2_value = np.array([0])#记录频繁项集支持度
            count_2_index = np.array([0,0])#记录频繁项集索引
            flag_2 = 0#辅助旗
            self.cols = self.lin.shape[0]#读取lin的规格
    
            for i in range(0, self.cols-1):
                for j in range(i+1, self.cols):
                    k = self.lin[i]
                    L = self.lin[j]
                    for M in range(0, self.TID):
                        if self.data[M, k]==1 and self.data[M, L]==1:
                        #两个事务都为1
                            flag_2 = flag_2 + 1
                    count_time_index = np.array([L, k])
                    #记录二项集索引
                    count_time_value = np.array([flag_2])
                    #记录二项集索引对应值
                    count_2_index = np.r_[count_2_index, count_time_index]
                    #结果并入
                    count_2_value = np.r_[count_2_value, count_time_value]
                    flag_2 = 0#重置旗
                #修改索引和支持度矩阵的格式
            count_2_index =count_2_index.reshape(int((count_2_index.shape[0])/2),2)
            count_2_index = np.delete(count_2_index, 0, 0)
            count_2_value = count_2_value.reshape(int(count_2_value.shape[0]),1)
            count_2_value = np.delete(count_2_value, 0, 0)
            
            #根据支持度阈值,计算频繁二项集
            reverse = np.zeros([int(count_2_value.shape[0]), 1],int)
            #满足阈值索引
            for i in range(0, int(count_2_value.shape[0])):
                if int(count_2_value[i,:]) >= self.Confidence:
                    reverse[i, 0] = i#如果满足阈值则记录进reverse
            reverse = reverse[np.nonzero(reverse)]#删除0元素
            reverse = np.hstack((reverse, self.o))
            #假定第0行是频繁项集,加一个0
            if count_2_value[0] < self.Confidence:
                reverse = reverse[np.nonzero(reverse)]
                #第0行不满足支持度阈值,删除0
            count_2_index = count_2_index[reverse,:]
            #根据reverse索引得到频繁二项集
            count_2_value = count_2_value[reverse,:]
            self.count_3_index = count_2_index#保存结果
            self.count_3_value = count_2_value
            print("2<-->0表示第3项与第1项间的关联,")
            print("后续第一个框为Kulc, 第二个框为不平衡比.")
            print("Kulc越接近1越可靠, 不平衡比越接近0越可靠.\n")
            for j in range(0, count_2_value.shape[0]):
                v1_1 = self.count[list(self.lin).index(count_2_index[j, 0])]
                v1_2 = self.count[list(self.lin).index(count_2_index[j, 1])]
                v2 = count_2_value[j]
                xin_1 = v2/v1_1
                xin_2 = v2/v1_2
                Kulc = (xin_1 + xin_2)/2.0
                IR = abs(v1_1-v1_2)/(v1_1 + v1_2 - v2)
                print(str(count_2_index[j, 0]) + "-->" + \
                      str(count_2_index[j, 1]) + str(Kulc) + str(IR))
        
        def Frequent_item_many(self):
            #计算三项以上频繁项集的索引和支持度
            count_3_index = self.count_3_index
            count_3_value = self.count_3_value
            flag_2 = 0#辅助旗
            flag_3 = 0
            lin_col = self.lin.reshape(self.cols, 1)
            #设定频繁一项集,用于每次合并项
            lin_col_2 = lin_col
            pp = 2#频繁项集标号(表示目前为频繁几项集)
            tip = 1#循环内部的指针,用于满足条件后跳出循环
            
            while (int(tip)):
                out_index = count_3_index#记录结果
                out_value = count_3_value
                for i in range(0, count_3_index.shape[0]-1):
                    #合并频繁一项集用于填补频繁项集索引,
                    #有几组频繁项集就重复几组
                    lin_col_2 = np.r_[lin_col_2,lin_col]
                count_3_index = np.repeat(count_3_index, self.cols, axis=0)
                count_3_value = np.repeat(count_3_value, self.cols, axis=0)
                if len(count_3_index):
                    count_3_index = np.c_[count_3_index, lin_col_2]
                    #合并,增加项集数
                    pp = pp+1#上述运行完后,项集的项数+1
                    
                    MM = np.zeros([count_3_index.shape[0], 1],int)
                    #将合并得到的项集,删除重复项
                    for M in range(0, count_3_index.shape[0]):
                        for i in range(0, pp-1):
                            for j in range(i+1, pp):
                                if count_3_index[M, i] == count_3_index[M, j]:
                                    #如果某项集有重复数,则记录索引,等待删除
                                    MM[M] = M
                    MM = MM[np.nonzero(MM)]#删除0元素
                    MM = np.hstack((MM, self.o))#假定第一行有重复数据,加一个0
                    for i in range(0, pp-1):
                        for j in range(i+1, pp):
                            if count_3_index[0, i] == count_3_index[0, j]:
                                flag_2 = 1
                    if flag_2 != 1:
                        MM = MM[np.nonzero(MM)]
                    flag_2 = 0
                    count_3_index = np.delete(count_3_index, MM, axis=0)
                    #删除重复项集
                else:
                #count_3_index为空集则将指示符设置为0,下一次运行while就跳出
                    tip = 0
                if len(count_3_index):#count_3_index不为空集再运行
                    for i in range(0, count_3_index.shape[0]):
                        #项集排序后若两个项集间重复,则也删除
                        count_3_index[i,:].sort()
                    count_3_index = np.unique(count_3_index,axis=0)
                    
                    count_row, count_col = count_3_index.shape
                    count_3_value = np.zeros([count_row, 1],int)
                    
                    for i in range(0, count_row):
                        #计算支持度
                        for M in range(0, self.TID):
                            for j in range(0, pp):
                                index = count_3_index[i, j]
                                if self.data[M, index] == 1:
                                    flag_2 = flag_2 + 1
                            if flag_2 >= pp:
                                flag_3 = flag_3 + 1
                            flag_2 = 0
                        count_3_value[i, 0] = flag_3
                        flag_3 = 0
                    #记录支持度大于阈值的索引和支持度
                    reverse = np.zeros([int(count_3_value.shape[0]), 1],int)
                    for i in range(0, int(count_3_value.shape[0])):
                        if int(count_3_value[i,:]) >= self.Confidence:
                            reverse[i, 0] = i
                    reverse = reverse[np.nonzero(reverse)]#删除0元素
                    reverse = np.hstack((reverse, self.o))
                    #假定第一行是频繁项集,加一个0
                    if count_3_value[0] < self.Confidence:
                        reverse = reverse[np.nonzero(reverse)]
                    if len(reverse):
                        count_3_index = count_3_index[reverse,:]
                        count_3_value = count_3_value[reverse,:]
                    else:
                        tip = 0
                    lin_col_2 = lin_col#重置该项
                else:
                #count_3_index为空集则将指示符设置为0,下一次运行while就跳出
                    tip = 0
            print("\n最大频繁项集(Py索引对应原数据时记得加1):\n" + str(out_index))
            print("支持度:\n" + str(out_value))
    

      首先将第二部分代码粘贴到.py文件中,保存名为“Apriori_category”,(就是我们第一部分代码中的“from Apriori_category import Apriori”,如果你想给.py文件换个名字,那么把那句中的“Apriori_category”改成你想要的就行)地址为桌面,(其它地址也可,不过要保证这个.py文件与我们之后的.py文件在同一文件夹下)(后面用不用加“.py”要各位小伙伴自己注意一下哦)然后运行一下代码。再把第一部分代码粘贴到另外一个.py文件中,运行第一部分代码即可。(如遇到代码无法运行的问题可在留言区回复,看到后,无特殊情况会第一时间回复)

      平时用的时候直接用第一部分十几行代码就行,也就是只需要设置原数据(0代表没买,1代表买了,用数组或矩阵表示)、项数(在例子中是商品种类数)、事务数(在例子中是人数)、最小支持度(支持度计数阈值)。代码的结果是原数据、频繁二项集以及对应的Kulc、不平衡比,还有最大频繁项集。结果示意如下:
    在这里插入图片描述
      最上方是原数据,下边紧跟着一小段说明,然后是频繁二项集与Kulc、不平衡比,最下面是频繁项集及其支持度计数。大家在对比原数据的时候一定要注意频繁项集里面的索引数是按照Python习惯的第一个数为0给出的。

    展开全文
  • Apriori关联规则算法的目的就是找出所有的频繁项集,所以需要定义一个评估标准找出频繁项集,即最小支持度。 首先从原始数据集中找出出现的所有项,对应数据集确定候选1项集,根据候选一项集每项在原始项集中的出现...
    1. 算法原理

    Apriori关联规则算法的目的就是找出所有的频繁项集,所以需要定义一个评估标准找出频繁项集,即最小支持度。 首先从原始数据集中找出出现的所有项,对应数据集确定候选1项集,根据候选一项集每项在原始项集中的出现次数计算每一项的sup值。比较sup值 / 原始数据集数 的值与最小支持度,小于则舍去,计算出频繁一项集,然后对频繁一项集两项之间求补集,并按照一项集中求sup的方法求取候选二项集及频繁二项集。之后递归求取频繁n项集,当频繁项集项数只有一项时递归结束。得到最后的频繁项集。

    2. 代码实现
    import java.util.ArrayList;
    
    /**
     * @Description 项集item
     * @Author Clxk
     * @Date 2019/4/15 10:57
     * @Version 1.0
     */
    public class Data {
    
        private ArrayList<String> data = new ArrayList<>();
    
        private int cnt;
    
        public ArrayList<String> getData() {
            return data;
        }
    
        public void setData(ArrayList<String> data) {
            this.data = data;
        }
    
        public int getCnt() {
            return cnt;
        }
    
        public void setCnt(int cnt) {
            this.cnt = cnt;
        }
    
        @Override
        public boolean equals(Object obj) {
            Data rhs = (Data) obj;
            boolean eq = this.cnt == rhs.cnt;
    
            if(this.cnt == rhs.cnt) {
                for(int i = 0; i < data.size(); i++) {
                    if(!data.get(i).equals(rhs.data.get(i))) {
                        eq = false;
                        break;
                    }
                }
            }
            return eq;
        }
    }
    
    
    import java.util.*;
    
    /**
     * @Description Apriori
     * @Author Clxk
     * @Date 2019/4/15 10:43
     * @Version 1.0
     */
    public class Main {
    
        /**
         * 初始数据集最大值
         */
        private static final int MAXN = 1000;
        /**
         * 数据集长度、最小支持度
         */
        private static int datacnt = 0;
        private static double minsupport = 0;
        /**
         * 初始数据集
         */
        private static ArrayList<String> []data = new ArrayList[500];
        /**
         * 项集结构
         */
        private static ArrayList<Data> items = new ArrayList<>();
    
    
        public static void main(String[] args) {
    
            /**
             * 原始数据集读取
             */
            Scanner scanner = new Scanner(System.in);
            System.out.println("请输入数据集的大小: ");
            datacnt = scanner.nextInt();
            System.out.println("请输入最小支持度: ");
            minsupport = scanner.nextDouble();
            System.out.println("请输入原始数据集: ");
            String str;
            scanner.nextLine();
            for (int i = 0; i < datacnt; i++) {
                data[i] = new ArrayList<>();
                str = scanner.nextLine();
                String[] split = str.split("\\s");
                for (int j = 0; j < split.length; j++) {
                    data[i].add(split[j]);
                }
            }
    
            /**
             * 数据集处理
             */
            solve(data);
    
    
        }
    
        /**
         * 数据集处理
         * @param data
         */
        public static void solve(ArrayList<String>[] data) {
    
            getFrequent(data, 1);
        }
    
        /**
         * 获取到频繁1项集
         * @param data
         */
        public static void getFrequentOne(ArrayList<String>[] data) {
    
            /**
             * 获取不重复集合
             */
            for(ArrayList<String> list : data) {
                if(list == null) break;
                for(String s: list) {
                    Data dt = new Data();
                    List<String> ls = new ArrayList<>();
                    ls.add(s);
                    dt.setData((ArrayList<String>) ls);
                    int is_have = 0;
                    for(int i = 0; i < items.size(); i++) {
                        Data d = items.get(i);
                        if(d.getData().equals(ls)) {
                            is_have = 1;
                            break;
                        }
                    }
                    if(is_have == 0) {
                        items.add(dt);
                    }
                }
            }
        }
    
        /**
         * 输出候选n项集
         * @param n
         */
        public static void getCandidate(int n) {
    
            System.out.println("候选" + n + "项集为: ");
            outList();
        }
    
        /**
         * 输出频繁n项集
         * @param n
         */
        public static void getItems(int n) {
            for(int i = 0; i < items.size(); i++) {
                if((double)items.get(i).getCnt() / datacnt < minsupport) {
                    items.remove(i);
                    i--;
                }
            }
            System.out.println("频繁"+ n +"项集为: ");
            outList();
        }
    
        /**
         * 获取频繁n项集
         * @param data
         * @param n
         */
        public static void getFrequent(ArrayList<String>[] data, int n) {
    
            if(n == 1) {
                getFrequentOne(data);
            } else {
                ArrayList<Data> array = new ArrayList<>();
                for(int i = 0; i < items.size(); i++) {
                    Set<String> set = new HashSet<>();
                    ArrayList<String> data1 = items.get(i).getData();
                    for(int j = i+1; j < items.size(); j++) {
                        set.clear();
                        ArrayList<String> data2 = items.get(j).getData();
                        for(int u = 0; u < Math.max(data1.size(), data2.size()); u++) {
                            if(data1.size() > u) set.add(data1.get(u));
                            if(data2.size() > u) set.add(data2.get(u));
                        }
                        if(set == null || set.size() !=  n) continue;
                        put2Items(array,set);
                    }
                }
                items = (ArrayList<Data>) array.clone();
            }
    
            /**
             * 获取sup值
             */
            addSup(n);
    
            /**
             * 输出候选n项集
             */
            getCandidate(n);
            /**
             * 输出频繁n项集
             */
            getItems(n);
    
            if(items.size() > 1) {
                getFrequent(data, n+1);
            }
    
        }
    
        /**
         * 获取Sup值
         * @param n
         */
        public static void addSup(int n) {
            for(int i = 0; i < items.size(); i++) {
                ArrayList<String> list = items.get(i).getData();
                int cnt = 0;
                for(int j = 0; j < datacnt; j++) {
                    int have = 1;
                    ArrayList<String> cur = data[j];
                    for(int u = 0; u < list.size(); u++) {
                        if(!cur.contains(list.get(u))) {
                            have = 0;
                            break;
                        }
                    }
                    if(have == 1) cnt++;
                }
                Data d = new Data();
                d.setData(list);
                d.setCnt(cnt);
                items.set(i, d);
            }
        }
    
        /**
         * 整理候选频繁项集,同项相加
         * @param array,set
         */
        public static void put2Items(ArrayList<Data> array, Set<String> set) {
            Data data = new Data();
            for(String s:set) {
                data.getData().add(s);
            }
            int is_have = 0;
            for(int i = 0; i < array.size(); i++) {
                if(array.get(i) == null) break;
                if(array.get(i).equals(data)) {
                    is_have = 1;
                    array.set(i, data);
                    break;
                }
            }
            if(is_have == 0) {
                array.add(data);
            }
        }
    
    
        /**
         * 输出项集
         */
        public static void outList() {
    
            for(Data data : items) {
                System.out.println(Arrays.toString(data.getData().toArray()) + "   " + data.getCnt());
            }
    
        }
    }
    
    
    展开全文
  • Apriori算法是第一个关联规则挖掘算法,也是最经典的算法。它利用逐层搜索的迭代方法找出数据库中项集的关系,以形成规则,其过程由连接(类矩阵运算)与剪枝(去掉那些没必要的中间结果)组成。该算法中项集的概念...
  • Python Implementation of Apriori Algorithm The code attempts to implement the following paper: Agrawal, Rakesh, and Ramakrishnan Srikant. "Fast algorithms for mining association rules." Proc. 20th ...
  • 关联规则算法最出名的例子就是啤酒和尿布放一起卖。 假如我们去超市买东西,付款后,会拿到一张购物清单。这个清单就是一个Transaction。对关联规则算法来说,每个产品的购买数量是无意义的,不参与计算。 许...
  • 通过建立事务二维数组和事务量缩减等方法对 Apriori算法进行改进,并利用 C + +语言予以实现.结果表明,建立二维数组减少了数据库的扫描次数,同时在项目和事务两个维度上进行减枝,大幅度降低了计算的时间复杂度.
  • Apriori关联规则算法整个思路

    千次阅读 2018-08-21 14:18:44
    1.设定最小支持度和置信度,支持度确定规则可以用于给定数据集的频繁程度,置信度确定YY在包含XX的交易中出现的频繁程度。 support是支持度,confidence是置信度。 2.通过读取获取的数据:去除重复元素,得到...
  • weka实现的apriori算法是在weka.associations包的Apriror类。...在这个类,挖掘关联规则的入口函数是public void buildAssociations(Instances instances),而instances就是数据集,检查数据,设置参数,初始...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,070
精华内容 828
关键字:

apriori关联规则算法