《机器学习实战》11.Apriori算法进行关联分析

目录

使用Apriori算法进行关联分析

1 关联分析

2 Apriori原理

3 使用Apriori算法来发现频繁集

3.1 生成候选项集

3.2 组织完整的Apriori算法

4 从频繁项集中挖掘关联规则

5 示例：发现国会投票中的模式

6 示例：发现毒蘑菇的相似特征

7 本章小结

---

本章涉及到的相关代码和数据

使用Apriori算法进行关联分析

本章内容：

①Apriori算法

②频繁项集生成

③关联规则生成

④投票中的关联规则发现

从大规模数据集中寻找物品间的隐含关系被称为关联分析或是关联规则学习。

1 关联分析

Apriori算法：

优点：易编码实现

缺点：在大数据集上可能较慢

使用数据类型：数值型或标称型数据

关联分析是一种在大规模数据集中寻找有趣关系的任务，这些关系可以有两种形式：频繁项集或关联规则

频繁项集是经常出现在一块的物品的集合，关联规则暗示两种物品之间可能存在很强的关系。

支持度和可信度可以来说明频繁的定义是啥，支持度是指数据集中包含该数据像的记录所占比例，可信度是针对一个关联规则所定义的，关联的物品的支持度/其中一个物品的支持度

2 Apriori原理

Apriori算法的一般过程

①收集数据：使用任意方法

②准备数据：任意数据类型都可以，因为我们只保存集合

③分析数据：任意方法

④训练算法：使用Apriori算法来找到频繁项集

⑤测试算法：不需要测试过程

⑥使用算法：用于发现频繁项集以及物品之间的关联规则

Apriori算法原理：如果某个项集是频繁的，那么他的所有子集也是频繁的

3 使用Apriori算法来发现频繁集

Apriori算法的两个输入参数分别是最小支持度和数据集。该算法首先会生成所有单个物品的项集列表。接着扫描交易记录来查看那些项集满足最小支持度要求，那些不满足最小支持度的集合会被去掉。然后，对剩下来的几何进行组合以生成包含两个元素的项集。接下来，再重新扫描交易记录没去掉不满足最小支持度的项集。该过程重复到所有项集都被去掉。

3.1 生成候选项集

数据集扫描的伪代码：

对数据集中的每条交易记录tran：

对每个候选项集can：

    检查一下can是否是tran的子集

    如果是，则增加can的计数值

对每个候选项集：

    如果其支持度不低于最小值，则保留该项集

返回所有频繁项集列表

# 创建一个用于测试的简单数据集
def loadDataSet():
    return [[1,3,4],[2,3,5],[1,2,3,5],[2,5]]
 
# 构建集合C1
            #  数据集
def createC1(dataSet):
    # C1是大小为1的所有候选项集的集合
    C1=[]
    # 遍历所有交易记录
    for transaction in dataSet:
        # 遍历所有交易记录中的每一个项
        for item in transaction:
            if not [item] in C1:
                # 添加一个列表，为每个物品构建一个集合
                C1.append([item])
    C1.sort()
    # frozenset时不可变集合，将C1中的每一个物品变程不可变集合
    return list(map(frozenset,C1))
 
 
def scanD(D,Ck,minSupport):
    ssCnt={}
     #统计项集在数据中的出现次数
    for tid in D:
        for can in Ck:
            # issubset函数用于判断集合的所有元素是否都包含在指定集合中
            if can.issubset(tid):
                ssCnt[can] = ssCnt.get(can,0) + 1
                # if can not in ssCnt:
                # if not ssCnt.has_key(can):   python3中已经废除了has_key函数
                    # ssCnt[can]=1
                # else:
                    # ssCnt[can]+=1
    # print(list(D))
    numItems=float(len(D))
    # print(numItems)
    retList=[]
    supportData={}
    for key in ssCnt:
        support=ssCnt[key]/numItems
        if support>=minSupport:
            retList.insert(0,key)
        supportData[key]=support
    return retList,supportData

3.2 组织完整的Apriori算法

伪代码如下：

当集合中项的个数大于0时：

    构建一个k个项组成的候选项集的列表

    检查数据已确认每个项集都是频繁的

    保留频繁项集并构建k+1项组成的候选项集的列表

 

# 创建候选集Ck
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:
                # 集合的合并操作：|
                retList.append(Lk[i]|Lk[j])
    return retList
 
# 主函数
def apriori(dataSet,minSupport=0.5):
    C1=createC1(dataSet)
    D=list(map(set,dataSet))
    # print(list(D))
    L1,supportData=scanD(D,C1,minSupport)
    L=[L1]
    k=2
    while len(L[k-2])>0:
        Ck=aprioriGen(L[k-2],k)
        Lk,supK=scanD(D,Ck,minSupport)
        supportData.update(supK)
        L.append(Lk)
        k+=1
    return L,supportData

我们来测试一下这个算法：

# 测试函数
dataSet=loadDataSet()
print(dataSet)
C1=createC1(dataSet)
# print(C1)
L,suppData=apriori(dataSet)
L,suppData

得到的输出结果为：

4 从频繁项集中挖掘关联规则

对于关联规则，我们也有类似的量化方法，这种量化指标称为可信度。

关联规则的性质：如果某条规则并不满足最小可信度要求，那马尔该规则的所有自己也不会满足最小可信度要求

减少测试的规则数目：首先从一个频繁项集开始，接着创建一个规则列表，其中规则右部只包含一个规则元素，然后对这些规则进行测试。接下来合并所有剩余规则来创建一个新的规则列表，其中规则右部包含两个元素。这种方法也叫做分级法。

# 主函数：
# 频繁项集列表 包含那些频繁项集支持数据的字典 最小可信度阙值
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,br1,minConf=0.7):
    prunedH=[]
    for conseq in H:
        conf=supportData[freqSet]/supportData[freqSet-conseq]
        if conf>=minConf:
            print(freqSet-conseq,'-->',conseq,'conf:',conf)
            br1.append((freqSet-conseq,conseq,conf))
            prunedH.append(conseq)
    return prunedH
 
# 对规则进行评估
def rulesFromConseq(freqSet,H,supportData,br1,minConf=0.7):
    m=len(H[0])
    if(len(freqSet)>(m+1)):
        Hmp1=aprioriGen(H,m+1)
        Hmp1=calcConf(freqSet,Hmp1,supportData,br1,minConf)
        if(len(Hmp1)>1):
            rulesFromConseq(freqSet,Hmp1,supportData,br1,minConf)

测试一下算法

rules=generateRules(L,suppData)
rules

得到的输出结果为：

 

5 示例：发现国会投票中的模式

①收集数据：使用votesmart模块来访问投票纪录

②准备数据：构造一个函数来将投票转化为遗传交易记录

③分析数据：再python提示符下查看准备的数据以确保数据的准确性

④训练算法：使用之前写的apriori函数和generateRules函数来发现投票纪录中的有趣信息

⑤测试算法：没有测试过程

⑥使用算法：这里知识出于娱乐的目的，不过也可以使用分析结果来为政治竞选活动服务，或者预测官员会如何投票

该部分API已经不再进行使用，因此跳过

6 示例：发现毒蘑菇的相似特征

mushDatSet=[line.split() for line in open('mushroom.dat').readlines()]
L,suppData=apriori(mushDatSet,minSupport=0.3)
# print(L)
for item in L[1]:
    if item.intersection('2'):
        print (item)

得到的输出结果为：

7 本章小结

关联分析是用于发大数据集中元素间有趣关系的一个工具集，可以采用两种方式来量化这种有趣的关系。频繁项集和关联规则