实验目的：在掌握关联规则算法的原理的基础上，能够应用关联规则算法解决实际问题。
 实验内容：根据实验数据，采用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)
 
后记
 
事情太多，随便改改，草草写完，莫得办法。
 日后再补？
 
历史的经验告诉我，写完一篇博客之后再去完善补充一般是小概率事件，人生每个阶段都有每个阶段该去完成的任务，学会安排时间分配时间非常重要！
 
时光匆匆，且惜时光吧，少年ㄟ( ▔, ▔ )ㄏ

首先说明一点，前面的文章中的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 

目的：两个属性是否相关联的研究
 
物品集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.
 
 
 
 
 
 

MS关联规则分析算法
 
属于建议引擎算法，可根据已购买的商品推测出可能要购买的商品。
关联规则是在大量数据事例中挖掘项集之间的关联或相关联系。典型如购物篮分析，就是购买了某一商品的用户是否会去购买另一商品。
关联规则算法是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%也购买面包
一个或多个项（项的意思是单项，比如，一个商品就是一个项），组成的集合称为项集。算法就是分析各项集的支持度与置信度，为了控制计算量，需要控制项集的数量，可以通过配置参数来控制。
关联规则分析算法重要配置参数 
 5.1. Minimum_Support：指定包含项集的最小事例数，也就是说项集的事项数必须超过该设定才进行挖掘 
 5.2. Minimum_Probability：定义关联有效性的最小值，也就是说当关联的有效性小于该值时不会被展示 
 5.3. 算法就是对各个项进行排列组合，并计算项集的支持度和置信度，且满足参数的限定，最后得出分析结果
关联模型所需输入 
 6.1. 单键列：输入表的主键，且是单一键列 
 6.2. 单个可预测列：一个关联模型只能有一个可预测列，通常它是嵌套表的键列 
 6.3. 输入列：输入列必须为离散列。关联模型通常包含两个表，一个主表一个嵌套表，如主表是会员的订单信息，嵌套表是会员的订单的明细。
数据准备 
 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. 在挖掘项目中，将两个视图引入数据源视图，并增加逻辑主键和表关联如下 
 
 
创建关联规则挖掘模型 
 8.1. 参考决策树的创建方式，直到指定表类型 
 8.2. 指定表类型-》事例勾选“v_DM_Association_vipDate”，也就是主表-》嵌套表勾选“v_DM_Association_vipDateDetail”，也就是明细表 
 8.3. 指定定型数据-》主表键是saleKey默认已勾选-》我们要预测的是会员可能要去哪些店铺购物，所以可预测列勾选“storeName”-》并且我们要分析的数据为会员已经去了哪些店铺购物，所以输入列勾选“storeName”-》还要为嵌套表指定键列，我们这里就直接勾选“storeName”了 
 8.4. 勾选“可钻取”，完成挖掘模型向导
挖掘模型查看器 
 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. 依赖关系网络：是各项间关系的直观映射，每个椭圆代表了一个项，箭头表示预测方向，左侧可调节依赖关系的强弱
挖掘模型预测 
 10.1. 选择挖掘模型 
 10.2. 选择输入表主表-》选择嵌套表-》修改联接，将挖掘模型与输入键列进行映射 
 10.3. 预测参数配置 
 10.3.1. 配置输入表的输出字段，这样就能预测输入表对应的预测结果输出-》这里将会员名和会员号输出 
 10.3.2. 源：“预测函数”-》字段：“PredictAssociation”（预测关联）-》条件/参数：拖入挖掘模型的嵌套表-》后面加上“,include_statistics,3”，意思是预测关联性最强的前三个项 
 10.3.3. 点击查看结果-》保存结果
截图说明 
 11.1. 店铺间的依赖关系 
 
 
11.2. 模型预测参数配置 
 
 
11.3. 模型预测结果 
 11.3.1. 其中support是支持的事例数 
 11.3.2. Probability是可能性 
 11.3.3. adjustedProbability是准确度