Machine Learning in Action 读书笔记---第11章使用Apriori算法进行关联分析

你的名字 2022-09-07 15:57 134阅读 0赞

# Machine Learning in Action 读书笔记 #

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

--------------------

### 文章目录 ###

*  Machine Learning in Action 读书笔记
 *  一、关联分析
 *  二、Apriori算法
 *   *  1.Apriori原理
     *  2.Apriori算法的一般过程
     *  3.使用Apriori算法来发现频繁集
 *  三、从频繁项集中挖掘关联规则
 *  四、全部代码

--------------------

# 一、关联分析 #

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

1.  **发现频繁项集**：利用**支持度**
2.  **发现关联规则**：利用**可信度**

（1）**频繁项集（frequent item sets）**：是经常出现在一块的物品的集合  
（2）**关联规则（assocation rules）**：暗示两种物品之间可能存在很强的关系  
（3）**支持度（support）**：被定义为数据集中包含该项集的记录所占的比例  
（4）**可信度或置信度（confidence）**：是针对一条诸如\{A\}–>\{B\}的关联规则来定义的，这条规则的可信度被定义为“支持度(\{A，B\}) / 支持度(\{A\})”

> 支持度和可信度是用来量化关联分析是否成功的方法。

# 二、Apriori算法 #

## 1.Apriori原理 ##

Apriori原理：如果某个项集是频繁的，那么它的所有子集也是频繁的，也就是说，**如果一个项集是非频繁集，那么它的所有超集也是非频繁的**。通过Apriori原理可以帮助减少感兴趣的项集，减少计算量。

## 2.Apriori算法的一般过程 ##

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

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

1.  首先生成所有单个物品的项集列表
2.  接着扫描交易记录来查看哪些项集满足最小支持度要求
3.  对剩下的集合进行组合以生成包含两个元素的项集
4.  再重新扫描交易记录，去掉不满足最小支持度的项集
5.  该过程重复进行直到所有项集都被去掉

生成候选项集伪代码：

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

代码：

'''Apriori算法中的辅助函数'''
    def loadDataSet():
        return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
    
    # 构建第一个候选集的列表C1
    def createC1(dataSet):
        C1 = [] # 创建空列表，用于存储所有不重复的项值
        for transaction in dataSet: # 遍历数据集中的所有交易记录
            for item in transaction: # 遍历记录中的每个一项
                if not [item] in C1: # 如果某个物品项没有出现在C1中，则将只包含该物品项的列表添加到C1中，这样做的目的是：为每个物品项构建一个集合
                    C1.append([item]) # python不能创建只有一个整数的集合，因此这里实现必须使用列表
        C1.sort() # 由单物品列表组成大列表后，对大列表进行排序
        return list(map(frozenset, C1))  # frozenset() 返回一个冻结的集合，冻结后集合不能再添加或删除任何元素。这里不能使用set()，因为后面要将这些集合作为字典键值使用
    
    # 该函数用于从C1生成L1，最终返回一个包含支持度值的字典
    def scanD(D, Ck, minSupport): # 参数：数据集、候选项集列表（单列表集合）、感兴趣项集的最小支持度
        ssCnt = {
        }
        for tid in D: # 遍历数据集中的所有交易记录
            # print(tid)
            for can in Ck: # 遍历C1中的所有候选集
                # print(can)
                if can.issubset(tid): # issubset() 方法用于判断集合的所有元素是否都包含在指定集合中，如果是则返回 True，否则返回 False。
                    if can not in ssCnt.keys(): # 如果C1中的集合是记录中的一部分，增加字典中对应的计数值
                        ssCnt[can] = 1
                    else:
                        ssCnt[can] += 1
        # print(ssCnt) #{frozenset({1}): 2, frozenset({3}): 3, frozenset({4}): 1, frozenset({2}): 3, frozenset({5}): 3}
        numItems = float(len(D))
        retList = []
        supportData = {
        }
        for key in ssCnt:
            # print(key) # frozenset({1})
            support = ssCnt[key] / numItems # 计算所有项集的支持度
            if support >= minSupport:
                retList.insert(0, key) # 在列表的首部插入任意新的集合,也可以在任意位置插入，修改第一个参数值就可以
            # print(retList) #[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})]
            supportData[key] = support
        return retList, supportData # 返回 大于等于最小支持度的候选集 和 最频繁项集的支持度

'''Apriori算法'''
    #创建 Ck，例如输入{0},{1},{2}，会生成{0, 1},{0, 2},{1, 2}
    def aprioriGen(Lk, k):  # 参数：频繁项集列表Lk、项集元素个数k
        retList = []
        lenLk = len(Lk) # 计算LK中的元素数目
        for i in range(lenLk):
            for j in range(i+1, lenLk): # 比较LK中的每一个元素与其他元素
                L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2] # 取两个集合,只取前k-2项
                L1.sort(); L2.sort()
                if L1==L2: # 如果两个集合的前面k-2个元素都相等，那么就将这两个集合合成一个大小为k的集合（只对前k-2个元素相同的集合求并操作，可以简化操作数目）
                    retList.append(Lk[i] | Lk[j]) #合并集合
        return retList
    # apriori函数通过调用aprioriGen函数来创建候选项集Ck
    def apriori(dataSet, minSupport = 0.5):
        C1 = createC1(dataSet)
        D = list(map(set, dataSet))
        L1, supportData = scanD(D, C1, minSupport)
        L = [L1]
        k = 2
        while (len(L[k-2]) > 0): # 直到下一个大项集为空时，停止
            # print(L[k-2]) #[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})]
            Ck = aprioriGen(L[k-2], k)
            # print(Ck) # [frozenset({2, 5}), frozenset({3, 5}), frozenset({1, 5}), frozenset({2, 3}), frozenset({1, 2}), frozenset({1, 3})]
            Lk, supK = scanD(D, Ck, minSupport)#扫描数据集，从CK得到Lk（从所有组合中得到大于等于最小支持率的组合）
            supportData.update(supK)
            L.append(Lk)
            k += 1
        return L, supportData

# 三、从频繁项集中挖掘关联规则 #

如关联规则\{A\}–>\{B\}，从逻辑研究上来讲，箭头左边的集合称为**前件**，箭头右边的集合称为**后件**。  
对于关联规则，使用可信度来量化方法。P–>H的**可信度定义**为： s u p p o r t ( P ∣ H ) / s u p p o r t ( P ) support(P|H)/support(P) support(P∣H)/support(P)  
关联规则生成函数：

'''关联规则生成函数'''
    # 主函数，调用其他两个函数
    def generateRules(L, supportData, minConf=0.7):  #参数：频繁项集列表、包含那些频繁项集支持数据的字典、最小可信度阈值
        bigRuleList = []
        # L：[[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})], [frozenset({2, 3}), frozenset({3, 5}), frozenset({2, 5}), frozenset({1, 3})], [frozenset({2, 3, 5})], []]
        for i in range(1, len(L)):#只获得集合条目两个或两个以上的集合，因为无法从单元素项集中构建关联规则
            for freqSet in L[i]: # [frozenset({2, 3})
                H1 = [frozenset([item]) for item in freqSet] # 遍历L中的每一个频繁项集，创建只包含单个元素集合的列表H1
                if (i > 1):
                    rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf) # 如果频繁项集的元素数目超多2，使用rulesFromConseq函数进行合并
                else:
                    calcConf(freqSet, H1, supportData, bigRuleList, minConf)     # 如果项集中只有两个元素，那么使用函数calcConf来计算可信度
        return bigRuleList # 返回一个包含可信度的规则列表
    # 生成候选规则集合：计算规则的可信度，以及找到满足最小可信度要求的规则
    def calcConf(freqSet, H, supportData, brl, minConf=0.7):# 频繁项集、可以出现在规则右部的元素列表H、包含那些频繁项集支持数据的字典、包含可信度的规则列表、最小可信度阈值
        prunedH = [] #用于存储 满足最小可信度的规则列表
        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):# 频繁项集、可以出现在规则右部的元素列表H、包含那些频繁项集支持数据的字典、包含可信度的规则列表、最小可信度阈值
        m = len(H[0]) # 计算H中的频繁集大小
        if (len(freqSet) > (m + 1)): #尝试进一步合并：查看该频繁项集是否大到可以移除大小为m的子集
            Hmp1 = aprioriGen(H, m+1)#创建新的候选集Hm+1，生成H中的无重复组合，作为下一次迭代的H列表
            Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
            if (len(Hmp1) > 1):    #如果不止一条规则满足要求，使用Hmp1调用函数rulesFromConseq来判断是否可以进一步组合这些规则
                rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)

# 四、全部代码 #

from numpy import *
    
    '''Apriori算法中的辅助函数'''
    def loadDataSet():
        return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
    
    # 构建第一个候选集的列表C1
    def createC1(dataSet):
        C1 = [] # 创建空列表，用于存储所有不重复的项值
        for transaction in dataSet: # 遍历数据集中的所有交易记录
            for item in transaction: # 遍历记录中的每个一项
                if not [item] in C1: # 如果某个物品项没有出现在C1中，则将只包含该物品项的列表添加到C1中，这样做的目的是：为每个物品项构建一个集合
                    C1.append([item]) # python不能创建只有一个整数的集合，因此这里实现必须使用列表
        C1.sort() # 由单物品列表组成大列表后，对大列表进行排序
        return list(map(frozenset, C1))  # frozenset() 返回一个冻结的集合，冻结后集合不能再添加或删除任何元素。这里不能使用set()，因为后面要将这些集合作为字典键值使用
    
    # 该函数用于从C1生成L1，最终返回一个包含支持度值的字典
    def scanD(D, Ck, minSupport): # 参数：数据集、候选项集列表（单列表集合）、感兴趣项集的最小支持度
        ssCnt = {
        }
        for tid in D: # 遍历数据集中的所有交易记录
            # print(tid)
            for can in Ck: # 遍历C1中的所有候选集
                # print(can)
                if can.issubset(tid): # issubset() 方法用于判断集合的所有元素是否都包含在指定集合中，如果是则返回 True，否则返回 False。
                    if can not in ssCnt.keys(): # 如果C1中的集合是记录中的一部分，增加字典中对应的计数值
                        ssCnt[can] = 1
                    else:
                        ssCnt[can] += 1
        # print(ssCnt) #{frozenset({1}): 2, frozenset({3}): 3, frozenset({4}): 1, frozenset({2}): 3, frozenset({5}): 3}
        numItems = float(len(D))
        retList = []
        supportData = {
        }
        for key in ssCnt:
            # print(key) # frozenset({1})
            support = ssCnt[key] / numItems # 计算所有项集的支持度
            if support >= minSupport:
                retList.insert(0, key) # 在列表的首部插入任意新的集合,也可以在任意位置插入，修改第一个参数值就可以
            # print(retList) #[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})]
            supportData[key] = support
        return retList, supportData # 返回 大于等于最小支持度的候选集 和 最频繁项集的支持度
    
    '''Apriori算法'''
    #创建 Ck，例如输入{0},{1},{2}，会生成{0, 1},{0, 2},{1, 2}
    def aprioriGen(Lk, k):  # 参数：频繁项集列表Lk、项集元素个数k
        retList = []
        lenLk = len(Lk) # 计算LK中的元素数目
        for i in range(lenLk):
            for j in range(i+1, lenLk): # 比较LK中的每一个元素与其他元素
                L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2] # 取两个集合,只取前k-2项
                L1.sort(); L2.sort()
                if L1==L2: # 如果两个集合的前面k-2个元素都相等，那么就将这两个集合合成一个大小为k的集合（只对前k-2个元素相同的集合求并操作，可以简化操作数目）
                    retList.append(Lk[i] | Lk[j]) #合并集合
        return retList
    # apriori函数通过调用aprioriGen函数来创建候选项集Ck
    def apriori(dataSet, minSupport = 0.5):
        C1 = createC1(dataSet)
        D = list(map(set, dataSet))
        L1, supportData = scanD(D, C1, minSupport)
        L = [L1]
        k = 2
        while (len(L[k-2]) > 0): # 直到下一个大项集为空时，停止
            # print(L[k-2]) #[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})]
            Ck = aprioriGen(L[k-2], k)
            # print(Ck) # [frozenset({2, 5}), frozenset({3, 5}), frozenset({1, 5}), frozenset({2, 3}), frozenset({1, 2}), frozenset({1, 3})]
            Lk, supK = scanD(D, Ck, minSupport)#扫描数据集，从CK得到Lk（从所有组合中得到大于等于最小支持率的组合）
            supportData.update(supK)
            L.append(Lk)
            k += 1
        return L, supportData
    
    '''关联规则生成函数'''
    # 主函数，调用其他两个函数
    def generateRules(L, supportData, minConf=0.7):  #参数：频繁项集列表、包含那些频繁项集支持数据的字典、最小可信度阈值
        bigRuleList = []
        # L：[[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})], [frozenset({2, 3}), frozenset({3, 5}), frozenset({2, 5}), frozenset({1, 3})], [frozenset({2, 3, 5})], []]
        for i in range(1, len(L)):#只获得集合条目两个或两个以上的集合，因为无法从单元素项集中构建关联规则
            for freqSet in L[i]: # [frozenset({2, 3})
                H1 = [frozenset([item]) for item in freqSet] # 遍历L中的每一个频繁项集，创建只包含单个元素集合的列表H1
                if (i > 1):
                    rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf) # 如果频繁项集的元素数目超多2，使用rulesFromConseq函数进行合并
                else:
                    calcConf(freqSet, H1, supportData, bigRuleList, minConf)     # 如果项集中只有两个元素，那么使用函数calcConf来计算可信度
        return bigRuleList # 返回一个包含可信度的规则列表
    # 生成候选规则集合：计算规则的可信度，以及找到满足最小可信度要求的规则
    def calcConf(freqSet, H, supportData, brl, minConf=0.7):# 频繁项集、可以出现在规则右部的元素列表H、包含那些频繁项集支持数据的字典、包含可信度的规则列表、最小可信度阈值
        prunedH = [] #用于存储 满足最小可信度的规则列表
        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):# 频繁项集、可以出现在规则右部的元素列表H、包含那些频繁项集支持数据的字典、包含可信度的规则列表、最小可信度阈值
        m = len(H[0]) # 计算H中的频繁集大小
        if (len(freqSet) > (m + 1)): #尝试进一步合并：查看该频繁项集是否大到可以移除大小为m的子集
            Hmp1 = aprioriGen(H, m+1)#创建新的候选集Hm+1，生成H中的无重复组合，作为下一次迭代的H列表
            Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
            if (len(Hmp1) > 1):    #如果不止一条规则满足要求，使用Hmp1调用函数rulesFromConseq来判断是否可以进一步组合这些规则
                rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
    
    if __name__ == '__main__':
        dataSet = loadDataSet() # 导入数据集
        # print(dataSet) # [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
        C1 = createC1(dataSet) # 构建第一个候选项集合C1
        # print(C1) #[frozenset({1}), frozenset({2}), frozenset({3}), frozenset({4}), frozenset({5})]
        D = list(map(set, dataSet)) # 构建集合表示的数据集D
        # print(D) # [{1, 3, 4}, {2, 3, 5}, {1, 2, 3, 5}, {2, 5}]
        L1, suppData0 = scanD(D, C1, 0.5) # 有了集合形式的数据，就可以去掉那些不满足最小支持度的项集
        # L1由四个项集构成，该列表中的每个单物品项集至少出现在50%以上的记录里，物品四并没有达到最小支持度，所以没有包含在L1中，通过去掉该物品减少了查找两物品项集的工作量
        # print(L1) # [frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})]
        # print(suppData0) # {frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25, frozenset({2}): 0.75, frozenset({5}): 0.75}
    
        L, suppData = apriori(dataSet)
        # print(L) # [[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})], [frozenset({2, 3}), frozenset({3, 5}), frozenset({2, 5}), frozenset({1, 3})], [frozenset({2, 3, 5})], []]
        # print(suppData) #{frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25, frozenset({2}): 0.75, ...
        CK = aprioriGen(L[0], 2)
        # print(L[0])  # [frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})]
        # print(CK) # [frozenset({2, 5}), frozenset({3, 5}), frozenset({1, 5}), frozenset({2, 3}), frozenset({1, 2}), frozenset({1, 3})]
    
        '''关联规则生成'''
        #生成一个最小支持度是0.5的频繁项集的集合
        L, suppData = apriori(dataSet, minSupport=0.5)
        rules = generateRules(L, suppData, minConf=0.7)
        # print(rules)
        '''
        frozenset({5}) --> frozenset({2}) conf: 1.0
        frozenset({2}) --> frozenset({5}) conf: 1.0
        frozenset({1}) --> frozenset({3}) conf: 1.0
        [(frozenset({5}), frozenset({2}), 1.0), (frozenset({2}), frozenset({5}), 1.0), (frozenset({1}), frozenset({3}), 1.0)]
        '''
        # 降低可信度阈值
        rules = generateRules(L, suppData, minConf=0.5)
        # print(rules) # 降低阈值会得到更多规则