精华内容
下载资源
问答
  • 数据挖掘中改进的Apriori关联规则算法分析.pdf
  • 实验目的:在掌握关联规则算法的原理的基础上,能够应用关联规则算法解决实际问题。 实验内容:根据实验数据,采用Apriori等关联规则发现算法,给出相关关联规则。 实验要求:给出数据预处理过程、关联规则发现算法...

    实验目的:在掌握关联规则算法的原理的基础上,能够应用关联规则算法解决实际问题。
    实验内容:根据实验数据,采用Apriori等关联规则发现算法,给出相关关联规则。
    实验要求:给出数据预处理过程、关联规则发现算法及发现关联规则,并对关联规则结果进行分析说明。
    实验题目:蔬菜价格相关性分析
    蔬菜的价格会受季节、天气等多方面因素的影响,但许多会出现同涨或者同跌等现象,请根据给出的蔬菜价格数据,采用关联规则发现算法,发现哪些蔬菜之间具有同涨、同跌或者涨跌不同步的现象。
    数据格式如下:
    在这里插入图片描述

    一、背景知识介绍

    Apriori算法这里就不详细介绍了,毕竟这篇博客的重点是记录解决实验的过程。

    象征性地推荐一些链接:
    Apriori算法详解之【一、相关概念和核心步骤】

    数据挖掘十大算法(四):Apriori(关联分析算法)

    二、数据处理

    做机器学习的实验,很大一部分或者说主要的工作,就是对数据的处理。

    同时,对数据处理的方法也是多种多样的,路漫漫呀~~

    这里采用了xlrd/xlwt 和 pandas 包进行数据的处理(这两种包单独使用当然可以处理好数据,这里主要是为了展现知识的丰富性),阅读下面代码前建议应先了解这两个包的基本用法。

    1、数据处理第一部分:采用xlrd/xlwt将数据变得规整

    思路点播博客链接:使用Apriori实现蔬菜价格涨跌关联分析
    简单了解博客链接:python使用xlrd和xlwt读写Excel文件学习笔记(解决xlwt写入日期格式错误的问题)

    知识点参考链接之一:

    import xlrd; #导入读取excel表格数据包(第三方模块)
    import xlwt; #导入写入excel表格数据包(第三方模块)
    
    #一、准备部分
    #1、Excel表格读的部分:
    excel=xlrd.open_workbook('蔬菜价格3.xls') #读入本地名为‘蔬菜价格3.xls’的Excel表格
    excelsheet=excel.sheets()[0]#获取excel表格中的第一个sheet工作表
    
    #2、Excel表格写的部分:
    newexcel = xlwt.Workbook(encoding = 'utf-8') #创建一个Excel对象,编码格式采用utf-8
    #创建一个表名为“蔬菜价格关联分析”的工作表,cell_overwrite_ok=True表示可覆盖之前已操作的单元格
    newsheet=newexcel.add_sheet('蔬菜价格关联分析',cell_overwrite_ok=True)
    
    #3、设置表格样式,这里主要用于设置日期的格式
    datastyle = xlwt.XFStyle() # 创建一个样式对象,初始化样式
    datastyle.num_format_str = 'M/D/YY' #设置日期格式
    
    #4、表格中有的空的位置不是真的为空,这里获取一个这样的值,待会用于特判
    tmp=excelsheet.cell_value(5,2)
    
    #二、正式开始处理数据,主要思路:从旧表中读出写入新表
    ri=2 #用于读原始第ri行
    rj=0#用于读原始第rj列
    wi=0#用于写入表格的第wi行
    wj=1#用于写入表格的第wj列
    #创建新表的第一行,包括日期和各个菜的菜名
    newsheet.write(0,0,excelsheet.cell_value(0,0))#将旧表的(0,0)位置的日期写到新表的(0,0)位置
    
    #1、先读取蔬菜列和禽肉类的列名,暂时先不处理禽肉类的一个K位置为空值的特殊情况
    while ri<42:
        rj=1#蔬菜在第1列,有40种,肉类在第3列,有23种
        newsheet.write(0,wj,excelsheet.cell_value(ri,rj))
        newsheet.write(0,wj+40,excelsheet.cell_value(ri,rj+2))
        ri=ri+1
        wj=wj+1
    
    #2、先整理蔬菜的价格
    ri=42 #遍历原始第ri行
    rj=2#遍历原始第rj列
    wi=0#写入表格的第wi行
    wj=1#写入表格的第wj行
    while ri<22320:
        if ri%47>=42:
            ri=ri+6
            wi=wi+1
            newsheet.write(wi,0,excelsheet.cell_value(ri,0),datastyle)
        else:
            if excelsheet.cell_value(ri,rj)!=tmp:
                newsheet.write(wi,wj,excelsheet.cell_value(ri,rj))              
            wj=wj%40+1
        ri=ri+1
    
    #3、再整理禽肉类的价格
    ri=26 #遍历原始第ri行
    rj=4#遍历原始第4列
    wi=0#写入表格的第wi行
    wj=41#写入表格的第wj行,从第41列开始
    while ri<22320:
        if ri%47>=26:
            ri=ri+22
            wi=wi+1
            wj=41
        else:
            if excelsheet.cell_value(ri,rj)!=tmp:      
                newsheet.write(wi,wj,excelsheet.cell_value(ri,rj))              
            wj=wj%(41+24)+1
        ri=ri+1
      
    newexcel.save('蔬菜数据处理过渡版.xls')#生成处理后的表格
    

    处理后数据示意图:
    在这里插入图片描述
    (小提示:要是看到部分日期显示为“XXXX”,把单元格拉宽就好了)

    2、数据处理第二部分:采用pandas相关函数将表格变得更好操作:

    import pandas as pd
    
    #header = None用于不让蔬菜名那一行作为“表头”,便于之后步骤的数据获取
    data=pd.read_excel('蔬菜数据处理过渡版.xls',header = None)
    
    #删除第60列空值列,axis=1表示纵向,inplace=True表示删除操作对原数据生效
    data.drop(labels=[60],axis=1,inplace=True)
    
    ri=1
    while ri<data.shape[0]-1:
        rj=1
        while rj<data.shape[1]:
            if (len(str(data.values[ri,rj]))==0 or len(str(data.values[ri+1,rj]))==0):
                data.iloc[ri,rj]=0
            else:
                d=float(data.values[ri,rj])-float(data.values[ri+1,rj]) #上-下 今天-昨天  正为涨,负为跌
                if d>0:
                    data.iloc[ri,rj]='up'
                elif d<0:
                    data.iloc[ri,rj]='down'
                else:
                    data.iloc[ri,rj]=0
            rj=rj+1
        ri=ri+1
    
    data.drop(labels=[data.shape[0]-1],axis=0,inplace=True)#删除最后一行
       
    data.to_excel("蔬菜数据处理完成版.xlsx")
    

    处理后数据示意图:
    在这里插入图片描述

    三、采用Apriori算法对蔬菜价格数据进行关联分析

    1、完整代码
    代码参考于:数据挖掘十大算法(四):Apriori(关联分析算法)

    我自己简略分析代码的过程:【机器学习】Apriori(关联分析算法)经典代码理解与学习笔记(Python)

    import pandas as pd
    
    #获取数据
    def vegetable():
        excel=pd.read_excel('蔬菜数据处理完成版.xlsx',header = None)
        data=[]
        ri=2 #结合表格,确定需要获取数据的位置
        while ri<excel.shape[0]:
            rj=1
            temp=[]
            while rj<excel.shape[1]:
                if excel.values[ri,rj]=='up':
                    temp.append(excel.values[1,rj]+'up')
                elif excel.values[ri,rj]=='down':
                    temp.append(excel.values[1,rj]+'down')
                rj=rj+1
            data.append(temp)
            ri=ri+1
        return excel.shape[0]-2,data
     
    # 将所有元素转换为frozenset型字典,存放到列表中
    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))  # frozenset一种不可变的集合,set可变集合
     
    # 过滤掉不符合支持度的集合
    # 返回 频繁项集列表retList 所有元素的支持度字典
    def scanD(D, Ck, minSupport):
        ssCnt = {}
        for tid in D:
            for can in Ck:
                if can.issubset(tid):   # 判断can是否是tid的《子集》 (这里使用子集的方式来判断两者的关系)
                    if can not in ssCnt:    # 统计该值在整个记录中满足子集的次数(以字典的形式记录,frozenset为键)
                        ssCnt[can] = 1
                    else:
                        ssCnt[can] += 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 # 排除不符合支持度元素后的元素 每个元素支持度
     
    # 生成所有可以组合的集合
    # 频繁项集列表Lk 项集元素个数k  [frozenset({2, 3}), frozenset({3, 5})] -> [frozenset({2, 3, 5})]
    def aprioriGen(Lk, k):
        retList = []
        lenLk = len(Lk)
        for i in range(lenLk): # 两层循环比较Lk中的每个元素与其它元素
            for j in range(i+1, lenLk):
                L1 = list(Lk[i])[:k-2]  # 将集合转为list后取值
                L2 = list(Lk[j])[:k-2]
                L1.sort(); L2.sort()        # 这里说明一下:该函数每次比较两个list的前k-2个元素,如果相同则求并集得到k个元素的集合
                if L1==L2:
                    retList.append(Lk[i] | Lk[j]) # 求并集
        return retList  # 返回频繁项集列表Ck
     
    # 封装所有步骤的函数
    # 返回 所有满足大于阈值的组合 集合支持度列表
    def apriori(dataSet, minSupport = 0.5):
        D = list(map(set, dataSet)) # 转换列表记录为字典 
        C1 = createC1(dataSet)      # 将每个元素转会为frozenset字典    [frozenset({1}), frozenset({2}), frozenset({3}), frozenset({4}), frozenset({5})]
        L1, supportData = scanD(D, C1, minSupport)  # 过滤数据
        L = [L1]
        k = 2
        while (len(L[k-2]) > 0):    # 若仍有满足支持度的集合则继续做关联分析
            Ck = aprioriGen(L[k-2], k)  # Ck候选频繁项集
            Lk, supK = scanD(D, Ck, minSupport) # Lk频繁项集
            supportData.update(supK)    # 更新字典(把新出现的集合:支持度加入到supportData中)
            L.append(Lk)
            k += 1  # 每次新组合的元素都只增加了一个,所以k也+1(k表示元素个数)
        return L, supportData
    
    
    # 获取关联规则的封装函数
    def generateRules(L, supportData, minConf=0.7):  # supportData 是一个字典
        bigRuleList = []
        for i in range(1, len(L)):  # 从为2个元素的集合开始
            for freqSet in L[i]:
                # 只包含单个元素的集合列表
                H1 = [frozenset([item]) for item in freqSet]    # frozenset({2, 3}) 转换为 [frozenset({2}), frozenset({3})]
                # 如果集合元素大于2个,则需要处理才能获得规则
                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(set(freqSet-conseq),'-->',set(conseq),'conf(置信度):',conf,',',set(freqSet),'的支持度supportData:',supportData[freqSet])
                print("{}——>{}的置信度为:{:.6f},支持度为:{:.6f}".format(set(freqSet-conseq),set(conseq),conf,supportData[freqSet]))
                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) # 将单个集合元素两两合并
            Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
            if (len(Hmp1) > 1):    #need at least two sets to merge
                rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
     
    N,dataSet = vegetable()
    #在这里控设置最小支持度
    L,suppData = apriori(dataSet,minSupport=float(40)/float(N))
    #在这里设置最小置信度
    rules = generateRules(L,suppData,minConf=0.3)
    #print("具有强关联规则的项集为:",rules)
    

    2、结果稍微分析
    ①上面的代码输出结果:
    在这里插入图片描述
    ②可通过设置支持度和置信度的不同,使显示结果数量不同!
    例如,将要求都设置低一些:
    在这里插入图片描述
    这样就有机会看到“多推多”的情况了(部分显示结构截取):
    在这里插入图片描述
    在这里插入图片描述

    ③值得注意的是:“up”和“down”是可以互推的
    在这里插入图片描述
    (frozenset({‘茭瓜up’}), frozenset({‘韭菜down’}), 0.22988505747126436), (frozenset({‘韭菜down’}), frozenset({‘茭瓜up’}), 0.273972602739726)

    后记

    事情太多,随便改改,草草写完,莫得办法。
    日后再补?

    历史的经验告诉我,写完一篇博客之后再去完善补充一般是小概率事件,人生每个阶段都有每个阶段该去完成的任务,学会安排时间分配时间非常重要!

    时光匆匆,且惜时光吧,少年ㄟ( ▔, ▔ )ㄏ

    展开全文
  • Apriori关联规则挖掘算法分析与改进
  • 关联规则算法论文

    2018-07-07 20:21:28
    绍了关联规则挖掘的研究性况,提出了关联规则的分类方法,对一些典型算法进行了分析和秤价,指出传统关系规则衡量标准的 不足,归纳出关联规则的价值衡量方,展望了关联规则挖掘的未来研究方向
  • 关联规则算法

    2014-10-14 16:51:48
    做的一份算法的讲义,关联规则方面的。对想学习本算法的同学有一点建议,
  • 目录 关联规则挖掘介绍 Apriori算法介绍 FP-growth算法介绍 强规则关联与相关分析 什么是关联规则挖掘? 关联规则挖掘: 从事务数据库,关系数据库和其他信息存储中的大 量数据的项集之间发现有趣的频繁出现的模式 关联...
  • Mahout关联规则算法源码分析(1)

    千次阅读 2013-02-02 00:49:27
    首先说明一点,前面的文章中的mahout关联规则源码分析part2 很多地方都理解错误了,现重新把理解的写下: 在命令行直接运行下面的命令就可以获得mahout关联规则FPGrowthDriver的用法: bin/hadoop jar $mahout_...

    首先说明一点,前面的文章中的mahout关联规则源码分析part2  很多地方都理解错误了,现重新把理解的写下:

    在命令行直接运行下面的命令就可以获得mahout关联规则FPGrowthDriver的用法:

     bin/hadoop jar $mahout_home/core/target/mahout-core-0.7-job.jar org.apache.mahout.fpm.pfpgrowth.FPGrowthDriver -h
    1. 打开FPGrowthDriver的源文件,可以看到主要的操作是调用PFPGrowth的runPFPGrowth方法,因为这里只考虑并行的情况,所以使用-method 参数使用mapreduce变量:

    else if ("mapreduce".equalsIgnoreCase(classificationMethod)) {
          Configuration conf = new Configuration();
          HadoopUtil.delete(conf, outputDir);
          PFPGrowth.runPFPGrowth(params);
        }
    这样操作就转移了,即 FPGrowthDriver--> PFPGrowth

    2. 打开PFPGrowth源文件,查看runPFPGrowth方法,可以看到该类主要有下面四个操作:

        2.1 startParallelCounting(params, conf);
    
        2.2// save feature list to dcache
        List<Pair<String,Long>> fList = readFList(params);
        saveFList(fList, params, conf);
    
        2.3 startParallelFPGrowth(params, conf);
        2.4 startAggregating(params, conf);
    其中2.1和2.2的操作在 mahout关联规则源码分析 Part 1里面已经说明的很清楚了,这里不再说明;

    2.3 这一步开启了一个Job,他的Mapper、Combiner、Reducer分别是:ParallelFPGrowthMapper、ParallelFPGrowthCombiner、ParallelFPGrowthReducer;

        job.setMapperClass(ParallelFPGrowthMapper.class);
        job.setCombinerClass(ParallelFPGrowthCombiner.class);
        job.setReducerClass(ParallelFPGrowthReducer.class);

    在说明具体步骤之前,先贴上原始数据,设置FPGrowthDriver的-g参数为2,即为2组:

    表1

    牛奶,鸡蛋,面包,薯片
    鸡蛋,爆米花,薯片,啤酒
    鸡蛋,面包,薯片
    牛奶,鸡蛋,面包,爆米花,薯片,啤酒
    牛奶,面包,啤酒
    鸡蛋,面包,啤酒
    牛奶,面包,薯片
    牛奶,鸡蛋,面包,黄油,薯片
    牛奶,鸡蛋,黄油,薯片
    牛奶1,鸡蛋1,面包1,薯片1
    鸡蛋1,爆米花1,薯片1,啤酒1
    鸡蛋1,面包1,薯片1
    牛奶1,鸡蛋1,面包1,爆米花1,薯片1,啤酒1
    牛奶1,面包1,啤酒1
    鸡蛋1,面包1,啤酒1
    牛奶1,面包1,薯片1
    牛奶1,鸡蛋1,面包1,黄油1,薯片1
    牛奶1,鸡蛋1,黄油1,薯片1

    2.3.1 ParallelFPGrowthMapper的主要操作:

    2.3.1.1 ParallelFPGrowthMapper的setup函数,此函数主要是读取全局的fList(参考:mahout关联规则之FP树:Parallel FP-Growth for Query Recommendation),把其存入一个Map中:

    int i = 0;
        for (Pair<String,Long> e : PFPGrowth.readFList(context.getConfiguration())) {
          fMap.put(e.getFirst(), i++);
        }
    针对原始数据,那么存储后的fMap为(项目名,编码,出现的次数),其中编码是根据项目出现的次数按降序从0开始向上编码,每次递增1:

    表 2

    薯片       0              7
    薯片1      1              7
    面包       2              7
    面包1      3              7
    鸡蛋       4              7
    鸡蛋1      5              7
    牛奶       6              6
    牛奶1      7              6
    啤酒       8              4
    啤酒1      9              4
    2.3.1.2 ParallelFPGrowthMapper的map函数:这个函数主要有两部分:第一部分:针对原始数据的一个事务,按照fMap中出现的顺序进行输出,并删除没有在fMap中出现的项目:比如针对
    鸡蛋,面包,薯片

    输出应为:[0,2,4];针对

    牛奶1,鸡蛋1,面包1,爆米花1,薯片1,啤酒1
    输出应为:[1,3,5,7,9];

    第二部分:针对上面的输出如何进行map的输出呢?上面设置的numGroups为2,即为两组(numGroups的参数设置主要是针对fList的,即把fList分为多组,这样可以达到并行的目的),那么0~4(编码后的项目名)为第一组,其相应的id为0,5~9为第二组,相应的id为1。若第一部分的所有项目都没有超过第一组的最后一个编码(本例中即为4)则此记录只输出一条记录,即本身;比如[0,2,4],那么map输出的记录的key为组的id,即0,value是[0,2,4];否则输出两条记录比如[1,3,5,7,9],其中一条为本身,即map输出key为id,1,value为[1,3,5,7,9];另一条记录为key为0,value为[1,3],即把第一部分的输出拆分为两部分,只取相应组的输出即可。又比如[0,2,4,6]的输出应为: 0   [0,2,4];  1    [0,2,4,6]  ;

    那么针对原始数据map的全部输出为:

    表3


    这里输出TransactionTree,其中的构造方法,其中transactionSet为TransactionTree的一个属性(这里初始TransactionTree,下面详细介绍):

    public TransactionTree(IntArrayList items, Long support) {
        representedAsList = true;
        transactionSet = Lists.newArrayList();
        transactionSet.add(new Pair<IntArrayList,Long>(items, support));
      }
    2.3.2 ParallelFPGrowthCombiner的reduce函数:
    TransactionTree cTree =new TransactionTree();
    for (TransactionTree tr : values) {
          for (Pair<IntArrayList,Long> p : tr) {
            cTree.addPattern(p.getFirst(), p.getSecond());
          }
        }
    context.write(key, cTree.getCompressedTree());
    这里可以看到新建了一个TransactionTree,然后把同一组(groupid)的记录通过addPattern方法放入到一棵TransactionTree上,最后通过getCompressedTree方法返回一个压缩了的TransactionTree并输出此TransactionTree;

    TransactionTree的属性有:

    int[] attribute;
    int[] childCount;
    int[][] nodeChildren;
    long[] nodeCount;
    int nodes;
    boolean representedAsList;
    List<Pair<IntArrayList,Long>> transactioniSet;
    比如[0,2,4,6],[0,2,4],[2,4,8]下面三条记录通过addPattern加入数中的效果如下(attr:attribute,nC:nodeCount,nCd:nodeChildren,cC:childCount;圆圈里的数字代表节点号,attribute代表其值,childCount代表子节点数,nodeChildren代表子节点号,nodeCount代表attribute出现的次数;加入一条记录的规则:针对一条新纪录,查看其值是否和节点0的子节点的attribute相同,是则把相应的子节点的nodeCount加1,否则新开一条路径):

    第一、二条记录:


    第三条记录:


    通过addPattern方法加入记录,TransactionTree的representedAsList属性为false,transactionSet为null,其他属性则存储相应的值;

    通过上面的方法即可以把每个id都建立一个TransactionTree,所以针对表3的数据建立了2棵TransactionTree,然后每棵TransactionTree又通过getCompressedTree把得到的两棵TrasactionTree进行压缩。压缩的方法就是把用数组表示的值用list表示,这时的representedAsList 属性为true,且transactionSet,不为null,而是下面的值:id:0,value:{([1],2)([1, 3],5)([2],1)([2, 4],1)([0, 2],1)([0, 2, 4],4)([0, 4],2)([3],2)};id:1,value:{([0, 2, 4, 6],2)([0, 2, 4, 6, 8],1)([0, 2, 6],1)([0, 4, 8],1)([0, 4, 6],1)([2, 6, 8],1)([2, 4, 8],1)([1, 5, 9],1)([1, 5, 7],1)([1, 3, 5],1)([1, 3, 5, 7],2)([1, 3, 5, 7, 9],1)([1, 3, 7],1)([3, 7, 9],1)([3, 5, 9],1)},其实上面的结果也就是表3中每个事务出现的次数而已;

    2.3.3 ParalleFPGrowthReducer:

    2.3.3.1 setup函数,这个函数和Mapper的setup函数的作用是一样的,都是读fList文件,但是这里是把项目读入List<String> featureReverseMap,把相应的频度读入LongArrayList freqList;

    2.3.3.2 reduce函数:首先产生一个localFList即gList,使用TransactionTree的generateFList方法,此方生成一棵TransactionTree中含有的所有项目的一个list即其相应的在这棵TransactionTree上面的频数;比如上面的两棵TransactionTree生成的gList及其相应的频数分别为: [(0,7), (1,7), (2,7), (3,7), (4,7)] 和[(1,7), (3,7), (5,7), (0,6), (2,6), (4,6), (6,6), (7,6), (8,4), (9,4)];接着调用FPGrowth的generateTopKFrequentPatterns方法;

     FPGrowth<Integer> fpGrowth = new FPGrowth<Integer>();
          fpGrowth.generateTopKFrequentPatterns()
    打开FPGrowth的源码,找到下面的方法:

    public final void generateTopKFrequentPatterns(Iterator<Pair<List<A>,Long>> transactionStream,
                                                     Collection<Pair<A, Long>> frequencyList,
                                                     long minSupport,
                                                     int k,
                                                     Collection<A> returnableFeatures,
                                                     OutputCollector<A,List<Pair<List<A>,Long>>> output,
                                                     StatusUpdater updater)
    这个方法首先就是把相应的fList转为gList,比如对于第二棵TransactionTree的gList:[(1,7), (3,7), (5,7), (0,6), (2,6), (4,6), (6,6), (7,6), (8,4), (9,4)],其项目按频度降序排序如下:1,3,5,0,2,4,6,7,8,9;那么本地的gList对其进行重新编码:{0=3, 1=0, 2=4, 3=1, 4=5, 5=2, 6=6, 7=7, 8=8, 9=9},所以1,3,5,0,2,4,6,7,8,9在本地就应该为:0,1,2,3,4,5,6,7,8,9;对于原来的记录:{[2,3,4,6],2}就会变为{[3,4,5,6]2};接着,该函数调用了generateTopKFrequentPatterns这个函数,第一次我以为它又调用了自身(就是上面说的理解错误的地方),往下看,有一个同名的方法,但是输入参数不一样;并且引入了FPTree,下次再分析。



    分享,快乐,成长


    转载请注明出处:http://blog.csdn.net/fansy1990 

    展开全文
  • 关联规则算法总结

    千次阅读 2020-05-01 12:15:27
    关联规则A->B的支持度:1000个顾客购物,100个购买了面包和黄油。则面包->黄油 10% 可信度 关联规则A->B的可信度:1000个顾客购物,200个购买了面包和黄油,140个购买了黄油,则可信度为70%(140/200) ...

    目的:两个属性是否相关联的研究

    物品集I里面是物品,事务集

    事务T支持物品集A:这个事务中包含此物品

    支持度

    物品A的支持度:1000个顾客购物,200个买了面包,支持度20%(200/1000)

    关联规则A->B的支持度(联合概率):1000个顾客购物,100个购买了面包和黄油。则面包->黄油 10%

    可信度

    关联规则A->B的可信度(条件概率):1000个顾客购物,200个购买了面包,140个购买了面包和黄油,则可信度为70%(140/200)

    A->B的支持度和B->A的支持度一样,可信度不同。

    规则度量

    最小支持度minsup关联规则必须满足的最小支持度

    最小可信度minconf关联规则必须满足的最小可信度

    大项集

    频繁项集:支持度不小于minsup的物品集

    最大频繁项目集:频繁集中挑选出所有不被其他元素包含的平凡项目集。

    关联规则发现任务

    事务数据库D,满足最小支持度和最小可信度的关联规则

    1)求D中满足最小支持度的所有频繁集(Apriori算法和FP树都是找频繁集的算法)。大于支持度

    2)利用频繁集生成满足最小可信度的所有关联规则。大于可信度

    高效求出频繁集:生成长度为1的L[1];L[k]的基础上生成候选物品集C[k+1],候选物品集必须保证包括所有的频繁项集。

    频繁集向下封闭性,频繁集子集必是频繁集;非频繁集的超集必是非频繁集

    Apriori算法(生成测试法)——构造候选集->组合频繁集

    思想:找单项候选集,去掉小于事先设定最小支持度的项,得单项频繁集;组合为两项候选集,再去掉小于事先设定最小支持度的项,得两项频繁集。以此类推!

    注意:组合时及时修剪。k项到k+1项时,可以将它排序,前k-1项都一样,然后将两个集合的第k项加入(此方法选的只多不少,需要再筛选一次)

    伪代码:

    优化:基于划分方法/Hash/采样/减小交易个数

    瓶颈:候选集的生成(1、组成更长频繁集太多。2、最长模式n,则需n+1次扫描数据库)

    注意的问题:充分理解数据、目标明确、数据工作做好、最小的支持度和可信度、理解关联规则

    使用步骤:连接数据,做数据准备;给定最小支持度和可信度,发现关联规则;可视化与评估

    FP-树算法——构造FP-树->挖掘频繁集

    原理:

    1.两次数据库搜索。一次对所有1-项目进行频度排序,一次将数据库信息转化为紧致内存(即FP-tree)

    2.根据FP-tree生成频繁集。为树上每个节点生成条件模型库;用条件模型库构造对应的条件FP树;递归挖掘条件FP树,并增长频繁集。

    步骤:

    1.找单项集的频次,并将大于等于minsup的项目进行排序,形成项头表。构建一个Null结点的FP树

    2.将数据库中的每一条记录进行过滤排序(过滤即删去频次<minsup的结点,排序即按照项头表的顺序)

    3.将排序后的数据插入FP树中,记录路过一次结点,结点频次加一。

    4.不断进行2-3步,直到每一条记录都插入FP树,FP树即构造完成

    5.FP-growth,按项头表的逆序(即从下往上),依次选定结点,并在FPtree中找到能到达该结点的路径(条件模式基)

    6.根据条件模式基找到频繁集

    具体算法和例子在这篇博客中讲的很清楚https://www.cnblogs.com/pinard/p/6307064.html

    缺点:需要递归,所以内存开销大。只适用于单维的布尔关联规则。

     

    上面观察的是用户单次购物买这些东西和买另一些东西的关系;

    下面观察的是用户的上次购物买的东西和下次购物买的东西的关系。

    序列模式(sequential pattern)——交易有先后关系

    如图,有五个用户A,B,C,D,E分别有3,2,3,3,2次购买记录,A用户第一次买了物品{1,2,4},第二次买了物品{2,3},第三次买了物品{5}

    <{1,2}>代表某用户某次购买时同时买了物品1和2;<{1}{2}>代表某用户某次购买了物品1,之后在另一次购买时又购买了物品2

    支持度的分母代表记录几个人,这里就是5。分子代表有几个人买过(不论是哪次购物)

    候选集生成

    两个长度为k(有k个数,不关注几个大括号)的序列,一个去头,一个去尾,若中间相同,则将两个集合合并

    a的生成:1去首{1}==4去尾{4},则a=1+4

    b的生成:2去首{1}==5去尾{3},则b=2+5

    c的生成:3去首{1}==7去尾{3,4}中的4,则c=3+7

    d的生成:4去首{2}==6去尾{5},则d=4+6

    e的生成:5去首{2,5}中的2==7去尾{3,4}中的4,则e=5+7

    上面生成的之多不少,再进行pruning最终只有b.

     

     

     

    展开全文
  • 基于关联规则算法的数据挖掘技术分析与研究.pdf
  • 关联规则挖掘可以发现大量数据中项集之间相关联系的知识,隐私保护是当前数据挖掘领域中一个十分重要的研究问题,其目标是要在不精确访问真实原始数据的条件下,得到准确的模型和分析结果。提出了关联规则挖掘形式化...
  • 基于关联规则的数据挖掘算法分析.pdf
  • 调用apriori进行关联规则分析,具体代码如下,其中数据集选取本博客 “机器学习算法——关联规则” 中的例子,可进行参考,设置最小支持度(min_support)为0.4,最小置信度(min_threshold)为0.1, 最小提升度...
  • MS关联规则分析算法

    2017-07-08 17:12:13
    MS关联规则分析算法 属于建议引擎算法,可根据已购买的...关联规则算法是Apriori算法的简单实现,下面是原理分析 3.1. 支持度:P(A∩B),既有A又有B的概率 3.2. 置信度:P(B|A),在A发生的事件中同时发生B的概率p

    MS关联规则分析算法

    1. 属于建议引擎算法,可根据已购买的商品推测出可能要购买的商品。

    2. 关联规则是在大量数据事例中挖掘项集之间的关联或相关联系。典型如购物篮分析,就是购买了某一商品的用户是否会去购买另一商品。

    3. 关联规则算法是Apriori算法的简单实现,下面是原理分析
      3.1. 支持度:P(A∩B),既有A又有B的概率
      3.2. 置信度:P(B|A),在A发生的事件中同时发生B的概率p(AB)/P(A),例如购物篮分析:牛奶 ⇒ 面包,即购买牛奶的用户同时购买面包的概率
      3.3. 例子:[支持度:3%,置信度:40%]
      支持度3%:意味着3%顾客同时购买牛奶和面包
      置信度40%:意味着购买牛奶的顾客40%也购买面包

    4. 一个或多个项(项的意思是单项,比如,一个商品就是一个项),组成的集合称为项集。算法就是分析各项集的支持度与置信度,为了控制计算量,需要控制项集的数量,可以通过配置参数来控制。

    5. 关联规则分析算法重要配置参数
      5.1. Minimum_Support:指定包含项集的最小事例数,也就是说项集的事项数必须超过该设定才进行挖掘
      5.2. Minimum_Probability:定义关联有效性的最小值,也就是说当关联的有效性小于该值时不会被展示
      5.3. 算法就是对各个项进行排列组合,并计算项集的支持度和置信度,且满足参数的限定,最后得出分析结果

    6. 关联模型所需输入
      6.1. 单键列:输入表的主键,且是单一键列
      6.2. 单个可预测列:一个关联模型只能有一个可预测列,通常它是嵌套表的键列
      6.3. 输入列:输入列必须为离散列。关联模型通常包含两个表,一个主表一个嵌套表,如主表是会员的订单信息,嵌套表是会员的订单的明细。

    7. 数据准备
      7.1. 创建一个主数据视图,主要是生成了会员号与日期的联合的会员按日消费单号
      create view [dbo].[v_DM_Association_vipDate]
      as
      –会员信息及会员号与日期组成的消费单号
      select v.vipKey, v.vipAkey, v.vipName, v.vipAkey+’-‘+cast(d.fullDate as varchar) saleKey
      from [dbo].[DimVip] v
      join [dbo].[FactVipSaleAndBonus] vs on vs.vipKey=v.vipKey
      join [dbo].[DimStore] s on s.storeKey=vs.storeKey
      join [dbo].[DimDate] d on d.dateKey=vs.dateKey
      group by v.vipKey, v.vipAkey, v.vipName, d.fullDate

    7.2. 创建一个嵌套视图,主要生成了会员各日的店铺消费明细和店铺对应的消费顺序号
    create view [dbo].[v_DM_Association_vipDateDetail]
    as
    –会员号与日期组成的消费单号,与消费的店铺信息及消费顺序号
    select s.storeAkey, s.storeName, v.vipAkey+’-‘+cast(d.fullDate as varchar) saleKey
    ,row_number() over(partition by v.vipAkey+’-‘+cast(d.fullDate as varchar) order by vs.hourKey) sequence
    from [dbo].[DimVip] v
    join [dbo].[FactVipSaleAndBonus] vs on vs.vipKey=v.vipKey
    join [dbo].[DimStore] s on s.storeKey=vs.storeKey
    join [dbo].[DimDate] d on d.dateKey=vs.dateKey
    group by v.vipAkey, d.fullDate, s.storeAkey, s.storeName, vs.hourKey

    7.3. 在挖掘项目中,将两个视图引入数据源视图,并增加逻辑主键和表关联如下
    这里写图片描述

    1. 创建关联规则挖掘模型
      8.1. 参考决策树的创建方式,直到指定表类型
      8.2. 指定表类型-》事例勾选“v_DM_Association_vipDate”,也就是主表-》嵌套表勾选“v_DM_Association_vipDateDetail”,也就是明细表
      8.3. 指定定型数据-》主表键是saleKey默认已勾选-》我们要预测的是会员可能要去哪些店铺购物,所以可预测列勾选“storeName”-》并且我们要分析的数据为会员已经去了哪些店铺购物,所以输入列勾选“storeName”-》还要为嵌套表指定键列,我们这里就直接勾选“storeName”了
      8.4. 勾选“可钻取”,完成挖掘模型向导

    2. 挖掘模型查看器
      9.1. 规则
      9.1.1. 概率:意思是产品间会产生关联的概率
      9.1.2. 重要性:衡量该规则重要性程度的指标
      9.1.3. 规则:挖掘出来的关联规则,“->”符号前的为已有商品,其后的为推测出来的关联商品
      9.2. 项集
      9.2.1. 支持:频率,表示包含目标项目的事例的数目(如项集A,支持100,意思是输入表中项集A有100个事例,A出现了100次)
      9.2.2. 大小:表示项集中项的个数
      9.2.3. 项集:显示了项集中具体的各个项(如,商品)的信息
      9.3. 依赖关系网络:是各项间关系的直观映射,每个椭圆代表了一个项,箭头表示预测方向,左侧可调节依赖关系的强弱

    3. 挖掘模型预测
      10.1. 选择挖掘模型
      10.2. 选择输入表主表-》选择嵌套表-》修改联接,将挖掘模型与输入键列进行映射
      10.3. 预测参数配置
      10.3.1. 配置输入表的输出字段,这样就能预测输入表对应的预测结果输出-》这里将会员名和会员号输出
      10.3.2. 源:“预测函数”-》字段:“PredictAssociation”(预测关联)-》条件/参数:拖入挖掘模型的嵌套表-》后面加上“,include_statistics,3”,意思是预测关联性最强的前三个项
      10.3.3. 点击查看结果-》保存结果

    4. 截图说明
      11.1. 店铺间的依赖关系
      这里写图片描述

    11.2. 模型预测参数配置
    这里写图片描述

    11.3. 模型预测结果
    11.3.1. 其中support是支持的事例数
    11.3.2. Probability是可能性
    11.3.3. adjustedProbability是准确度
    这里写图片描述

    展开全文
  • 关联规则下的数据挖掘算法分析.pdf
  • 数据挖掘关联规则算法改进.pdf
  • 数据挖掘关联规则算法研究.pdf
  • 关联规则算法java实现代码

    热门讨论 2011-07-28 13:16:16
    关联规则算法java实现代码,以完成关联规则提取、预测及归纳
  • 使用Apriori关联规则算法实现购物篮分析

    千次阅读 多人点赞 2020-11-19 15:19:26
    本章使用Apriori关联规则算法实现购物篮分析,发现超市不同商品之间的关联关系,并根据商品之间的关联规则制定销售策略。 1背景与挖掘目标 现代商品种类繁多,顾客往往会由于需要购买的商品众多而变得疲于选择,且...
  • Mahout关联规则算法源码分析(2)

    千次阅读 2013-02-07 15:44:46
    这里先分析下FPTree的各个属性: int[] attribute; int[] childCount; int[] conditional; long[] headerTableAttributeCount; int[] headerTableAttributes; int headerTableCount; int[] headerTableLookup...
  • 基于关联规则算法的推荐方法研究综述.pdf
  • apriori和关联规则算法

    千次阅读 2016-02-21 10:32:48
    从大规模数据集中寻找物品间的隐含关系被称为关联规则分析(association analysis)或关联规则学习(association rule learning)。举个例子说就是发现用户购买了一件商品(如帽子)后,会购买另一件商品(如围巾)...
  • 讨论了并行关联规则算法在地震预报中的应用,提出了分区、画圆数据预处理方法和相应的并行关联规则算法,给出实验结果并进行了解释分析
  • 数据挖掘中关联规则算法的研究.pdf
  • 数据挖掘中的关联规则算法研究.pdf
  • 基于关联规则算法的数据挖掘研究.pdf
  • 数据关联规则分析算法

    千次阅读 2018-01-29 18:33:14
    数据关联规则(Associaton Rules,AR)是数据挖掘算法的重要目的之一,用于...Apriori算法关联规则分析中较为典型的频繁项集算法。 原理步骤: (1)对数据中每一项数据进行频率次数统计; (2)构成候选项集C1,计
  • 10.2 关联规则算法原理 10.3 分层搜索经典算法-Apriori算法 10.4 并行挖掘算法 10.5 增量更新挖掘算法 10.6 多层关联规则挖掘 10.7 多维关联规则挖掘 10.8 约束性关联规则挖掘 10.9 数量关联规则挖掘 10.10 负关联...
  • 这是一篇2008年1月的硕士毕业论文,介绍了关联规则算法在金融数据中的应用。详细介绍了Apriori算法的改进,引入hecker确信因子过滤无效规则。采用了一种新的股票数据预处理算法进行预处理。最后对上交所的部分股票...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 88,494
精华内容 35,397
关键字:

关联规则算法分析结果