机器学习实战-Apriori算法进行关联分析

商场的销售过程，涉及很多机器学习的应用，商品的陈列，购物卷的提供，用户忠诚度等等，通过对这些大量数据的分析，可以帮组商店了解用户的购物行为，进而对商品的定价、市场促销、存货管理等进行决策帮组。从大规模数据集中寻找物品间的隐含关系被称作关联分析（association analysis）或关联学习(association rule learning).

关联分析也可用于网站流量分析以及医药行业

关联分析：在大规模数据集中寻找有趣关系的任务。

有趣关系：

　　　　频繁项集：经常出现在一起的物品集合

　　　　关联规则：暗示两种物品之间可能存在很强的关系。

例子分析杂货店交易清单

商店交易清单1-1
交易编码	商品
1	豆奶，莴苣
2	莴苣，尿布，葡萄酒，甜菜
3	豆奶，尿布，葡萄酒，橙汁
4	莴苣，豆奶，尿布，葡萄酒
5	莴苣，豆奶，尿布，橙汁

由频繁项集的定义：经常出现在一起的物品集合，集合{尿布，葡萄酒，豆奶}是一个频繁项集。可以从表中看出{尿布----》葡萄酒}当用户购买了尿布后，购买葡萄酒的几率很大，即找到了尿布---》葡萄酒的关联规则。

如何寻找频繁项集----根据支持度和可信度（或置信度）

支持度：数据集中包含该项集记录所占的比例，用于量化频繁项集。事件A与事件B同时出现的概率：P(A∩B).

　　　　P(A∩B)=AB同时出现的次数 / A出现的次数支持度越高，事件{A，B}越频繁。

　　从表1-1中可以看出豆奶的支持度为4/5.5条交易中，包含{豆奶，尿布}的有3条，所以{豆奶，尿布}的支持度为3/5

可信度（置信度）：事件A发生时，事件B发生的概率。

　　P(B|A)=P(A∩B)/P(A)=support(AB)/support(A)

比如，{尿布}--->{葡萄酒}，这条规则的可信度被定义为：支持度（{尿布，葡萄酒}/支持度{尿布}）。从表中可以看出{尿布，葡萄酒}的支持度3/5，{尿布}的支持度4/5，所以{尿布}--->葡萄酒的置信度：（3/5）/（4/5）=3/4

Apriori原理

一杂货店有四种商品 0，1，2，3.这些商品的组合可能有一种，二种，三种，四种。我们的关注点：用户购买一种或者多种商品，不关心具体买的商品的数量。

集合{0，1，2，3}中所有可能的项集组合如下图1-1：

机器学习实战----Apriori算法进行关联分析

图1-1

四种商品要遍历15次，随着物品数目的增加遍历次数会急剧增加。对于包含N种商品的数据集一共有2^N-1种项集组合。

Apriori原理

如果一个集合是频繁子集，则它的所有子集都是频繁项集。

如果一个集合不是频繁项集，则它的所有超集都不是频繁项集。

根据Apriori原理，假设集合{2，3}是非频繁项集，则{0，2，3}，{1，2，3}，{0，1，2，3}也是非频繁的，它们的支持度就不需要计算了。

机器学习实战----Apriori算法进行关联分析

使用Apriori算法发现频繁项集

apriori算法两个输入参数：数据集和最小支持度。

该算法首先生成所有单个物品的频繁项集列表，接着扫描交易记录查看哪些项集满足最小支持度要求，不满足的被踢掉；对剩下的集合进行组合生成包含两个元素的项集，重新扫描交易记录，去掉不满足最小支持度的项集。重复，直到所有项集都被去掉。

生成候选项集

 1 import numpy as np
 2 
 3 
 4 #加载数据
 5 def loadDataSet():
 6     return [[1,3,4],[2,3,5],[1,2,3,5],[2,5]]
 7 
 8 #构建c1：大小为1的所有候选项集的集合
 9 def createC1(dataSet):
10     C1=[]#空列表
11     for transaction in dataSet:
12         for item in transaction:
13             if not [item] in C1:
14                 C1.append([item]) #只添加包含该物品项的一个列表   为每个物品构建一个集合
15                # print([item],"item")
16     C1.sort()
17     print(len(C1))
18     return map(frozenset,C1) #对C1中每个项构建一个不变集合
19     
20 
21 def scanD(Data,Ck,minSupport): #数据集，候选项集列表，感兴趣项集的最小支持度
22     D = map(set, Data)
23     #print(list(Ck))
24     ssCnt={} #空字典
25     # for tid in D:#遍历数据集的所有交易记录
26     #     #print(tid,"------tid")
27     #     for can in Ck:#遍历c1中的所有候选集
28     #         #print(can,"-----can")
29     #        #if can.issubSet(tid):#c1中的集合是记录的一部分，增加字典中对应的计数值
30     #         if tid.issuperset(can):
31     #             #if not ssCnt.keys():ssCnt[can]=1 #字典的键就是集合
32     #             if  can in ssCnt.keys():scanD[can]+=1
33     #             else:ssCnt[can]=1
34 
35     for tid in D:
36          #print(tid, "------tid")
37         for can in Ck:
38            # print(can, "-----can")
39             if can <=tid:
40             #if tid.issuperset(can):
41                 if can in ssCnt.keys():
42                     ssCnt[can]+=1
43                 else:
44                     ssCnt[can]=1
45     numItem=len(list(Data))
46     #print(list(Data))
47     #print("numItem:",numItem)
48     retList=[]#空列表，用于包含最小支持度要求的集合
49     supportData={}#空字典
50     for key in ssCnt:#遍历字典中的每个元素并计算支持度
51         suport=ssCnt[key]/numItem#计算所有项集的支持度s
52         #print(suport,"support",key)
53         if suport>=minSupport:#满足支持度要求，则将字典元素添加到retList
54             retList.insert(0,key)#在列表的首部插入任意新的集合
55         supportData[key]=suport
56         #print("reList:",retList)
57     return retList,supportData#返回频繁项集的支持度