• 《机器学习实战》学习笔记（十一）

    文章目录

    第11章 使用Apriori算法进行关联分析

    引言

    从大规模数据集中寻找物品间的隐含关系被称作关联分析(association analysis ) 或者关联规则学习（association rule learning)

    Apriori算法优缺点

    • 优 点 ：易编码实现。
    • 缺点：在大数据集上可能较慢。
    • 适用数据类型：数值型或者标称型数据。

    Apriori算法的一般过程

    1. 收集数据：使用任意方法。
    2. 准备数据：任何数据类型都可以，因为我们只保存集合。
    3. 分析数据：使用任意方法。
    4. 训练算法：使用人口Apriori算法来找到频繁项集。
    5. 测试算法：不需要测试过程。
    6. 使用算法：用于发现频繁项集以及物品之间的关联规则。

    11.1 关联分析

    频繁项集（frequent item sets)是经常出现在一块的物品的集合。

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

    一个项集的支持度(support)(支持度是针对项集来说的)被定义为数据集中包含该项集的记录所占的比例。

    可信度或置信度（confidence)是针对一条诸如{尿布} → \to → {葡萄酒}的关联规则来定义的。这条规则的可信度被定义为 “ 支持度({尿布，葡萄酒})/支持度({尿布}) ” 从图11-1中可以看到，由于 {尿布，葡萄酒}的支持度为3/5,尿布的支持度为4/5,所以“尿布 → \to →葡萄酒”的可信度为3/4=0.75。在这里插入图片描述

    11.2 Apriori 原理

    Apriori原理是说如果某个项集是频繁的，那么它的所有子集也是频繁的。

    对于图11-2给出的例子，这意味着如果{0，1}是频繁的，那么{0}、{1}也一定是频繁的。

    在这里插入图片描述
    这个原理直观上并没有什么帮助，但是如果反过来看就有用了，也就是说如果一个项集是非频繁集，那么它的所有超集也是非频繁的。
    在这里插入图片描述

    一旦计算出了{2,3}的支持度，知道它是非频繁的之后，就不需要再计算{0，2，3}、{1，2，3}和 {0，1，2，3}的支持度，因为我们知道这些集合不会满足我们的要求。使用该原理就可以避免项集数目的指数增长，从而在合理时间内计算出频繁项集。

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

    需要找到频繁项集，然后才能获得关联规则。

    11.3.1 生成候选项集

    数据集扫描的伪代码大致如下：

    对数据集中的每条交易记录tran
对每个候选项集can：
	检查一下can是否是tran的子集：
	如果是，则增加can的计数值
对每个候选项集：
如果其支持度不低于最小值，则保留该项集
返回所有频繁项集列表

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    APriori算法中的辅助函数实现如下：

    from numpy import *

#加载数据
def loadDataSet():
    return [[1,3,4],[2,3,5],[1,2,3,5],[2,5]]

#用于对数据集构建初始项集
def createC1(dataSet):
    # 用来存放初始项集
    C1 =[]  
    #遍历每一个交易记录
    for transaction in dataSet:  
        # 遍历记录中的每一个物品
        for item in transaction: 
            # 以列表作为元素，因为不能单独对一个int执行set
            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:  
            # can中的所有元素是否都在tid中
            if can.issubset(tid):  
                # python3废除了has_key方法，可以用get 方法代替
                ssCnt[can] = ssCnt.get(can,0) + 1
                
    numItems = float(len(list(D)))
    # 用来存放满足支持度的那些项集
    retList = []  
    # 用来存放所有项集与其对应的支持度
    supportData = {}  
    for key in ssCnt:
        support1 = ssCnt[key] / numItems
        # 如果满足最小支持度的要求
        if support1 >= minSupport: 
            # 将key插入到索引为0的位置 
            retList.insert(0,key)  
        supportData[key] = support1
    return retList,supportData

dataSet = loadDataSet()
C1 = createC1(dataSet)
D = list(map(set,dataSet ))
#支持度设为0.5
L1,suppData0 = scanD(D, C1, 0.5)

print("候选项集：",C1,end="\n")
print("满足最小支持度的项集：",L1,end="\n")


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58

    输出如下：
    在这里插入图片描述
    通过辅助函数我们可以得到设置的满足最小支持度要求的项集。

    整个Apriori算法的伪代码如下:

    当集合中项的个数大于0时
	构建一个K个项组成的候选项集的列表
	检查数据以确认每个项集都是频繁的
	保留频繁项集并构建k+1项组成的候选项集的列表

    • 1
    • 2
    • 3
    • 4

    Aprioria算法实现如下：

    #产生要求的项集元素个数的项集组合
def aprioriGen(Lk,k):
    # 用来存放新的项集
    retList = []  
    lenLk = len(Lk)
    # 构建新项集的思路是遍历每个元素，两两之间如果只有1个不相同就可以加在一起
    # 当前项集中每一个元素的长度为k
    for i in range(lenLk): 
        for j in range(i+1, lenLk):  
            # 取出前k-1个元素，就是索引到k-2，
            # 记得下标索引从0开始
            L1 = list(Lk[i])[:k-2]  
            L2 = list(Lk[j])[:k-2]
            L1.sort()
            L2.sort()
            # 如果相等，说明Lk[i]和Lk[j]只有第k个元素不等
            if L1 == L2:  
                # 采用集合的并方法将其添加到新集合中
                retList.append(Lk[i] | Lk[j])
                
    return retList

#apriori函数
def apriori(dataSet,minSupport=0.5):
    C1 = createC1(dataSet)
    # 这里set不是将dataSet中的重复交易记录去除掉
    # 而是将dataSet的每一个交易记录中重复购买的东西去除掉
    D = list(map(set,dataSet)) 
   
    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)  
        # 直到Lk为空，下一次循环的时候就退出了
        L.append(Lk)  
        k += 1
    return L,supportData


dataSet = loadDataSet()
L , suppData = apriori(dataSet)
print("满足最小支持度的频繁项集：",L,end="\n")

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    输出结果如下：
    在这里插入图片描述
    可以看到，现在将满足我们要求的所有的频繁集输出了。从单个项集到含有三个成员的项集。因为{4}不是频繁项集，所以输出都不包含{4}这项。

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

    对于关联规则的量化方法：

    量化指标称为可信度。

    一条规则P → \to →H 的可信度定义为:
    support(P|H) /support ( P)

    P | H是指所有出现在集合P或者集合H 中的元素。
    箭头左边的集合称作前件，箭头右边的集合称为后件。

    如果某条规则并不满足最小可信度要求，那么该规则的所有子集也不会满足最小可信度要求。

    关联规则生成函数：

    # 生成一个包含可信度的规则列表
def generateRules(L, supportData, minConf = 0.7):
    # 用来存储符合条件的规则
    bigRuleList = []  
    # 索引0中只有单个元素无法构建规则，从索引1有两个元素的开始
    for i in range(1,len(L)): 
        # 遍历当前的每一个频繁项集 
        for freqSet in L[i]:  
            # 拆成单个元素的集合构成的列表
            Hl = [frozenset([item]) for item in freqSet]  
            # i>1，则说明每个频繁项集大小大于2，那么可能有右端大于1的可能
            if i > 1:  
                rulesFromConseq(freqSet,Hl,supportData,bigRuleList,minConf)
            # i=1的话，频繁项集只有2的元素，只有右端为1的可能
            else: 
                calcConf(freqSet,Hl,supportData,bigRuleList,minConf)
    return bigRuleList

# 求满足最小可信度要求的规则列表
# freqset为当前的频繁项集，H存放其子集，不是全部的，长度不断增加的
def calcConf(freqSet,H,supportData,brl,minConf = 0.7): 
    # 用来存放那些规则的可信度满足要求的右端
    prunedH = []  
    # 遍历freqset当前H长度的子集
    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]) 
    # 如果大于说明还能移除大小为m+1的子集来构建规则
    if len(freqSet) > (m+1):  
        # 用H中的集合取拼凑成长度为m+1的子集
        Hmp1 = aprioriGen(H,m+1)  
        Hmp1 = calcConf(freqSet,Hmp1,supportData,brl,minConf)
        # 计算当前频繁项集与Hmp1这些子集的规则的可信度，返回的符合条件的规则的右端放入Hmp1中
        if len(Hmp1) > 1:
            rulesFromConseq(freqSet,Hmp1,supportData,brl,minConf)


dataSet = loadDataSet()
L , suppData = apriori(dataSet)
print("满足最小支持度的频繁项集：",L,end="\n")
rules=generateRules( L , suppData,minConf =.7)
print("关联规则：",rules,end="\n")

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55

    输出结果如下：
    在这里插入图片描述
    输出结果展示了三条规则，{1} → \to →{3}。{5} → \to →{2}、{2} → \to →{5}规则{5} → \to →{2}可以互换前件与后件。
    降低可信度阈值为0.6后输出结果如下：
    在这里插入图片描述
    可以看到输出的规则有11条。随着可信度下降，我们能得到的规则也越多。

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

    这个示例要数据集没下下来。程序没办法跑。简单过一下算法。

    def getActionIds():
    actionIdList = []; billTitleList = []
    fr = open('./Ch11/recent20bills.txt') 
    for line in fr.readlines():
        # 得到了议案的ID
        billNum = int(line.split('\t')[0])
        try:
            # 得到一个billDetail对象
            billDetail = votesmart.votes.getBill(billNum) 
            # 遍历议案中的所有行为
            for action in billDetail.actions:  
                if action.level == 'House' and \
                (action.stage == 'Passage' or action.stage == 'Amendment Vote'):
                    actionId = int(action.actionId) 
                    print ('bill: %d has actionId: %d' % (billNum, actionId))
                    actionIdList.append(actionId)
                    billTitleList.append(line.strip().split('\t')[1])
        # API调用时发生错误
        except:  
            print ("problem getting bill %d" % billNum)
        # 礼貌访问网站而做出些延迟，避免过度访问
        sleep(1) 
    return actionIdList, billTitleList


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    这部分代码是用来获取数据的，得到了ID号列表与投票信息列表。
    首先创建一个字典，字典中使用政客的名字作为键值，当某政客首次出现时，将他及其所属政党（民主党或者共和党）添加到字典中，这里使用0来代表民主党，1来代表共和党。然后对投票进行编码，其对每条议案使用两个条目：bill+’Yea’以及bill+’Nay’。

    使用actionId串作为输入并利用voteSmart的API来抓取投票记录的函数。然后将每个选举人的投票转化为一个项集 。每个选举人对应于一行或者说事务数据库中的一条记录。
    在这里插入图片描述

    
# 基于投票数据的事物列表填充函数 
def getTransList(actionIdList, billTitleList): 
    # 创建一个含义列表
    itemMeaning = ['Republican', 'Democratic'] 
    # 遍历所有的议案
    for billTitle in billTitleList: 
        # 在议案标题后面添加Nay(反对)
        itemMeaning.append('%s -- Nay' % billTitle) 
        # 在议案标题后添加Yea(同意)
        itemMeaning.append('%s -- Yea' % billTitle) 
    # 用于加入元素项
    transDict = {} 
    voteCount = 2
    # 遍历getActionIds()返回的每一个actionId
    for actionId in actionIdList: 
        # 延迟访问，防止过于频繁的API调用
        sleep(3)  
        print ('getting votes for actionId: %d' % actionId)
        try:
            # 获得某个特定的actionId的所有投票信息
            voteList = votesmart.votes.getBillActionVotes(actionId) 
            # 遍历投票信息
            for vote in voteList: 
                # 如果没有该政客的名字
                if not transDict.has_key(vote.candidateName):  
                    # 用该政客的名字作为键来填充transDict
                    transDict[vote.candidateName] = [] 
                    # 获取该政客的政党信息
                    if vote.officeParties == 'Democratic':  
                        transDict[vote.candidateName].append(1)
                    elif vote.officeParties == 'Republican':
                        transDict[vote.candidateName].append(0)
                if vote.action == 'Nay':
                    transDict[vote.candidateName].append(voteCount)
                elif vote.action == 'Yea':
                    transDict[vote.candidateName].append(voteCount + 1)
        except: 
            print ("problem getting actionId: %d" % actionId)
        voteCount += 2
    # 返回事物字典和元素项含义列表
    return transDict, itemMeaning  


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43

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

    实现代码如下：

    #输出蘑菇特征频繁集
def mushroomChara():
    
    fr = open("./Ch11/mushroom.dat")
    #按行读取并拆分数据
    mushDateSet = [line.split() for line in fr.readlines()]
    
    L,suppData = apriori(mushDateSet,minSupport=0.3)
    print(L[1])
    for item in L[1]:
        # 搜索包含有毒特征值2的频繁项集
        # 返回集合item和集合{“2”}的交集
        if(item.intersection('2')):
            print(item)

    return
    
mushroomChara()

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    输出结果如下：
    在这里插入图片描述
    实现很简单，导入数据集，根据数据集产生频繁项集。最后打印出频繁项集中所包含的所需特征的组合。

    11.7 小结

    本章主要是两部分，首先是创建频繁项集。之后是通过频繁项集根据我们设置的可信度，找到对应的关联规则。
    每次增加频繁项集的大小，apriori算法都会重新扫描整个数据集。当数据集很大时，这会显著降低频繁项集发现的速度。

  • 相关阅读:
    Modbus协议详解3：数据帧格式 - RTU帧 & ASCII帧的区别
    python学习框架
    Linear Model 线性模型
    HACK ME PLEASE: 1实战演练
    设置hadoop+安装java环境
    提升Java性能的优化细节
    16：状态模式
    关于聚合根，领域事件的那点事---深入浅出理解DDD
    python selenium如何带cookie访问网站
    唐山海德教育二级建造师报考-----考试科目
  • 原文地址：https://blog.csdn.net/qq_35021992/article/details/126582751