“机器学习实战”刻意练习——相关问题：Apriori

拼搏现实的明天。 2023-06-24 06:25 52阅读 0赞

# 一、概述 #

忠诚度计划是指顾客使用会员卡可以获得一定的折扣，利用这种计划，商店可以了解顾客所购买的商品。即使顾客不使用会员卡，商店也会查看顾客购买商品所使用的信用卡记录。如果顾客不使用信用卡而使用现金付账，商店则可以查看顾客一起购买的商品。通过查看哪些商品经常在一起购买，可以帮助商店了解用户的购买行为。

这种从数据海洋中抽取的知识可以用于商品定价、市场促销、存货管理等环节。从大规模数据集中寻找物品间的隐含关系被称作**关联分析（association analysis**）或者关联规则学习（association rule learning）。

这里的主要问题在于，寻找物品的不同组合是一项十分耗时的任务，所需的计算代价很高，蛮力搜索方法并不能解决这个问题，所以需要用更智能的方法在合理的时间范围内找到**频繁项集**。

所以我们将学习如何使用**Apriori算法**来解决上述问题。

*  Apriori算法优缺点  
    优点：**易编码**实现。  
    缺点：**在大数据集上可能较慢**。
 *  适用数据类型：  
    **数值型**  
    **标称型**
 *  Apriori算法的一般过程  
    (1) 收集数据：使用任意方法。  
    (2) 准备数据：任何数据类型都可以，因为我们**只保存集合**。  
    (3) 分析数据：使用任意方法。  
    (4) 训练算法：使用Apriori算法来找到**频繁项集**。  
    (5) 测试算法：不需要测试过程。  
    (6) 使用算法：用于发现频繁项集以及物品之间的**关联规则**。

# 二、基本原理 #

## 1.关联分析 ##

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

1.  **频繁项集（frequent item sets**）是经常出现在一块的物品的集合
2.  **关联规则（association rules**）暗示两种物品之间可能存在很强的关系。

下面用一个杂货店的例子来说明这两个概念：  
![在这里插入图片描述][format_png]

*  \{葡萄酒, 尿布, 豆奶\} 就是一个频繁项集的例子。
 *  尿布 -> 葡萄酒 就是一个关联规则。  
    这意味着如果顾客买了尿布，那么他很可能会买葡萄酒。

那么**频繁**的定义是什么呢？怎么样才算频繁呢？  
度量它们的方法有很多种，这里我们来简单的介绍下支持度和可信度。

**支持度**: 数据集中包含该项集的记录所占的比例。例如上图中，\{豆奶\} 的支持度为 4/5。\{豆奶, 尿布\} 的支持度为 3/5。

**可信度**: 针对一条诸如 \{尿布\} -> \{葡萄酒\} 这样具体的关联规则来定义的。  
这条规则的可信度被定义为支持度(\{尿布, 葡萄酒\})/支持度(\{尿布\})，从图中可以看出 支持度(\{尿布, 葡萄酒\}) = 3/5，支持度(\{尿布\}) = 4/5，所以 \{尿布\} -> \{葡萄酒\} 的可信度 = 3/5 / 4/5 = 3/4 = 0.75。

假设想找到支持度大于 0.8 的所有项集，应该如何去做呢？  
一个办法是生成一个物品所有可能组合的清单，然后对每一种组合统计它出现的频繁程度，但是当物品成千上万时，上述做法就非常非常慢了。  
我们需要详细分析下这种情况并讨论下 Apriori 原理，该原理会减少关联规则学习时所需的计算量。

## 2.Apriori 原理 ##

假设我们在经营一家商品种类并不多的杂货店，我们对那些经常在一起被购买的商品非常感兴趣。我们只有4种商品：商品0，商品1，商品2和商品3。

这些商品组合可能只有一种商品，比如商品0，也可能包括两种、三种或者所有四种商品。我们并不关心某人买了两件商品0以及四件商品2的情况，我们只关心他购买了一种或多种商品。下图显示了物品之间所有可能的组合。图中从上往下的第一个集合是 ϕ \\phi ϕ ，表示空集或不包含任何物品的集合。物品集合之间的连线表明两个或者更多集合可以组合形成一个更大的集合。  
![在这里插入图片描述][20191222100638347.png]  
我们可以数一下图的集合数目，会发现即使对于仅有4种物品的集合，也需要遍历数据15次。而随着物品数目的增加遍历次数会急剧增长。对于包含N种物品的数据集共有 2 N − 1 2^\{N\}-1 2N−1种项集组合。

为了降低所需的计算时间，研究人员发现一种所谓的Apriori原理，可以帮我们减少可能感兴趣的项集。

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

上图给出的例子，这意味着如果\{0,1\}是频繁的，那么\{0\}、\{1\}也一定是频繁的。这个原理直观上并没有什么帮助，但是如果反过来看就有用了，也就是说如果一个项集是非频繁集，那么它的所有超集也是非频繁的。 如下图：  
![format_png 1][]  
已知阴影项集\{2,3\}是非频繁的。利用这个知识，我们就知道项集\{0,2,3\}，\{1,2,3\}以及\{0,1,2,3\}也是非频繁的。这也就是说，一旦计算出了\{2,3\}的支持度，知道它是非频繁的之后，就不需要再计算\{0,2,3\}、\{1,2,3\}和\{0,1,2,3\}的支持度，因为我们知道这些集合不会满足我们的要求。使用该原理就可以避免项集数目的指数增长，从而在合理时间内计算出频繁项集。

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

## 3.从频繁项集中挖掘关联规则 ##

我们已经学习了用于发现频繁项集的 Apriori 算法，现在要解决的问题是如何找出其中的关联规则。

要找到关联规则，我们首先从一个频繁项集开始。 我们知道集合中的元素是不重复的，但我们想知道**基于这些元素能否获得其它内容**。

还是那个杂货店的例子，如果有一个频繁项集 \{豆奶,莴苣\}，那么就可能有一条关联规则 “豆奶 -> 莴苣”。 这意味着如果有人买了豆奶，那么在统计上他会购买莴苣的概率比较大。 但是，这一条件**反过来并不总是成立**。 也就是说 “豆奶 -> 莴苣” 统计上显著，那么 “莴苣 -> 豆奶” 也不一定成立。

前面我们给出了频繁项集的量化定义，即它满足最小支持度要求。  
对于 关联规则，我们也有类似的量化方法，这种量化指标称之为 可信度。  
一条规则 A -> B 的**可信度定义为 support(A | B) / support(A)**。  
（注意: 在 python 中 | 表示集合的并操作，而数学书集合并的符号是 U）。

类似于上一节的频繁项集生成，我们可以为每个频繁项集产生许多关联规则。如果能够减少规则数目来确保问题的可解性，那么计算起来就会好很多。可以观察到，**如果某条规则并不满足最小可信度要求，那么该规则的所有子集也不会满足最小可信度要求**。  
举个例子，假设 123 -> 3 并不满足最小可信度要求，那么就知道任何左部为 \{0,1,2\} 子集的规则也不会满足 最小可信度 的要求。 即 12 -> 03 , 02 -> 13 , 01 -> 23 , 2 -> 013, 1 -> 023, 0 -> 123 都不满足 最小可信度 要求。

# 三、代码实现 #

## 1.生成候选项集 ##

先创建一个用于构建初始集合的函数，再创建一个通过扫描数据集以寻找交易记录子集的函数。

*  数据扫描的伪代码如下:

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

具体代码如下：

def loadDataSet():
        """ 加载数据集 """
        return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
    
    def createC1(dataSet):
        """ 创建大小为1的所有候选项集的集合C1 - - - - dataSet - 原始数据集 """
        C1 = []
        # 元素去重
        for transaction in dataSet:
            for item in transaction:
                if not [item] in C1:
                    C1.append([item])
        # 对数组进行从小到大的排序
        print ('sort 前=', C1)
        C1.sort()
        # frozenset表示冻结的set集合，用户不能修改
        print ('sort 后=', C1)
        print ('frozenset=', map(frozenset, C1))
        return list(map(frozenset, C1))
    
    def scanD(D, Ck, minSupport):
        """ 计算候选数据集 CK 在数据集 D 中的支持度 - - - - D - 数据集 Ck - 候选项集列表 minSupport — 最小支持度 """
        # 存放选数据集Ck的频率
        ssCnt = { }
        for tid in D:
            for can in Ck:
                # 测试s中的每一个元素是否都在t中
                if can.issubset(tid):
                    if can in ssCnt:
                        ssCnt[can] += 1
                    else:
                        ssCnt[can] = 1
        numItems = float(len(D))
        retList = []
        supportData = { }
        for key in ssCnt:
            # 支持度 = 候选项（key）出现的次数 / 所有数据集的数量
            support = ssCnt[key]/numItems
            # 只存储支持度满足频繁项集的值
            if support >= minSupport:            
                retList.insert(0, key)
            # 存储所有的候选项（key）和对应的支持度（support）
            supportData[key] = support
        return retList, supportData

## 2.完整的Apriori 算法 ##

*  整个Apriori算法的伪代码如下：

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

剩下部分代码如下：

def aprioriGen(Lk, k):
        """ 输出候选项集 - - - - Lk - 频繁项集列表 k - 返回的项集元素个数 """
        retList = []
        lenLk = len(Lk)
        for i in range(lenLk):
            for j in range(i+1, lenLk):
                #只对k-2前的元素进行比较，可确保遍历列表的次数最少，最后不需要遍历列表来寻找非重复值
                L1 = list(Lk[i])[: k-2]
                L2 = list(Lk[j])[: k-2]
                L1.sort()
                L2.sort()
                # 第一次 L1,L2 为空，元素直接进行合并，返回元素两两合并的数据集
                if L1 == L2:
                    retList.append(Lk[i]|Lk[j])
        return retList
    
    def apriori(dataSet, minSupport=0.5):
        """ apriori算法找出所有频繁项集的支持度 - - - - dataSet - 原始数据集 minSupport - 支持度的阈值 """
        C1 = createC1(dataSet)
        D = list(map(set, dataSet))
        L1, supportData = scanD(D, C1, minSupport)
    
        # 第二层运算
        L = [L1]
        k = 2
        # 判断 L 的第 k-2 项的数据长度是否 > 0
        while (len(L[k-2]) > 0):
            Ck = aprioriGen(L[k-2], k) 
            Lk, supK = scanD(D, Ck, minSupport) 
            supportData.update(supK)
            if len(Lk) == 0:
                break
            L.append(Lk)
            k += 1
        return L, supportData
    
    def testApriori():
        """ 测试Apriori算法 """
        dataSet = loadDataSet()
        print('dataSet: ', dataSet)
        # Apriori 算法生成频繁项集以及它们的支持度
        L1, supportData1 = apriori(dataSet, minSupport=0.7)
        print('L(0.7): ', L1)
        print('supportData(0.7): ', supportData1)
    
    if __name__ == "__main__":
        testApriori()

结果：

dataSet:  [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
    L(0.7):  [[frozenset({5}), frozenset({2}), frozenset({3})], [frozenset({2, 5})]]
    supportData(0.7):  {frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25, frozenset({2}): 0.75, frozenset({5}): 0.75, frozenset({2, 5}): 0.75, frozenset({3, 5}): 0.5, frozenset({2, 3}): 0.5}

## 3.从频繁项集中挖掘关联规则 ##

由于我们先前已经计算出所有频繁项集的支持度了，现在我们要做的只不过是提取这些数据做一次除法运算即可。  
函数generateRules()是主函数，它调用其他两个函数。如果频繁项集的元素数目超过2，那么会考虑通过函数rulesFromConseq()对它做进一步的合并。如果项集中只有两个元素，那么使用函数calcConf()来计算可信度值。

def calcConf(freqSet, H, supportData, brl, minConf=0.7):
        """ 计算可信度,并记录可信度大于最小可信度的集合 - - - - freqSet - 频繁项集中的元素 H - 频繁项集中的元素的集合 supportData - 所有元素的支持度的字典 brl - 关联规则列表的空数组 minConf - 最小可信度 """
        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):
        """ 递归计算频繁项集的规则 - - - - freqSet - 频繁项集中的元素 H - 频繁项集中的元素的集合 supportData - 所有元素的支持度的字典 brl - 关联规则列表的数组 minConf - 最小可信度 """
        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):
                print ('----------------------', Hmp1)
                rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
    
    def generateRules(L, supportData, minConf=0.7):
        """ 生成关联规则 - - - - L - 频繁项集列表 supportData - 频繁项集支持度的字典 minConf - 最小置信度 """
        # 包含可信度的规则列表
        bigRuleList = []
        # 获取频繁项集中每个元素数量大于1的组合的所有元素
        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 testGenerateRules():
        """ 测试关联规则的生成 """
        dataSet = loadDataSet()
        L1, supportData1 = apriori(dataSet, minSupport=0.5)
        rules = generateRules(L1, supportData1, minConf=0.5)
        print('rules: ', rules)
    
    if __name__ == "__main__":
        #1.测试Apriori算法
        #testApriori()
        #2.测试关联规则的生成
        testGenerateRules()

结果：

frozenset({3}) --> frozenset({2}) conf: 0.6666666666666666
    frozenset({2}) --> frozenset({3}) conf: 0.6666666666666666
    frozenset({5}) --> frozenset({3}) conf: 0.6666666666666666
    frozenset({3}) --> frozenset({5}) conf: 0.6666666666666666
    frozenset({5}) --> frozenset({2}) conf: 1.0
    frozenset({2}) --> frozenset({5}) conf: 1.0
    frozenset({3}) --> frozenset({1}) conf: 0.6666666666666666
    frozenset({1}) --> frozenset({3}) conf: 1.0
    frozenset({5}) --> frozenset({2, 3}) conf: 0.6666666666666666
    frozenset({3}) --> frozenset({2, 5}) conf: 0.6666666666666666
    frozenset({2}) --> frozenset({3, 5}) conf: 0.6666666666666666
    ---------------------- [frozenset({2, 3}), frozenset({2, 5}), frozenset({3, 5})]
    rules:  [(frozenset({3}), frozenset({2}), 0.6666666666666666), (frozenset({2}), frozenset({3}), 0.6666666666666666), (frozenset({5}), frozenset({3}), 0.6666666666666666), (frozenset({3}), frozenset({5}), 0.6666666666666666), (frozenset({5}), frozenset({2}), 1.0), (frozenset({2}), frozenset({5}), 1.0), (frozenset({3}), frozenset({1}), 0.6666666666666666), (frozenset({1}), frozenset({3}), 1.0), (frozenset({5}), frozenset({2, 3}), 0.6666666666666666), (frozenset({3}), frozenset({2, 5}), 0.6666666666666666), (frozenset({2}), frozenset({3, 5}), 0.6666666666666666)]

# 四、小结 #

1.  关联分析是用于发现大数据集中元素间有趣关系的一个工具，可以用在许多不同物品上。商店中的商品以及网站的访问页面是其中比较常见的例子。关联分析也曾用于查看选举人及法官的投票历史。
2.  可以采用两种方式来量化关系：  
    第一种方式是使用**频繁项集**，它会给出经常在一起出现的元素项；  
    第二种方式是**关联规则**，每条关联规则意味着元素项之间的“如果……那么”关系。
3.  发现元素项间不同的组合是个耗时耗资源的任务，而**Apriori算法**可以在合理的时间范围内找到频繁项集。能够实现这一目标的一个方法是，它使用Apriori原理来减少在数据库上进行检查的集合的数目。  
    **Apriori原理是说如果一个元素项是不频繁的，那么那些包含该元素的超集也是不频繁的。** Apriori算法从单元素项集开始，通过组合满足最小支持度要求的项集来形成更大的集合。
4.  **支持度**用来度量一个集合在原始数据中出现的频率。
5.  Apriori算法缺点：每次增加频繁项集的大小，Apriori算法都会重新扫描整个数据集。当**数据集很大时，这会显著降低频繁项集发现的速度**。

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jYW1vLmdpdGh1YnVzZXJjb250ZW50LmNvbS9hNjdiM2YyNGEwZDA2ZmZhMTdmMDVkOGYzYWVjMjcyYjliMDc1ZWQ0LzY4NzQ3NDcwM2EyZjJmNjQ2MTc0NjEyZTYxNzA2MTYzNjg2NTYzNmUyZTZmNzI2NzJmNjk2ZDY3MmY0MTY5NGM2NTYxNzI2ZTY5NmU2NzJmNmQ2YzJmMzEzMTJlNDE3MDcyNjk2ZjcyNjkyZjYxNzA2MTYzNjg2NTYzNmU1ZjYxNzA3MjY5NmY3MjY5NWY2MTczNzM2ZjYzNjk2MTc0Njk2ZjZlNWY2NDY1NmQ2ZjVmMzEyZTZhNzA2Nw?x-oss-process=image/format,png
[20191222100638347.png]: https://img-blog.csdnimg.cn/20191222100638347.png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jYW1vLmdpdGh1YnVzZXJjb250ZW50LmNvbS8xMzZlZmY5NzgyZTFkOWEwYWEwY2E0MzFlNjhmZDFlZjFjMWQ4MjMxLzY4NzQ3NDcwM2EyZjJmNjQ2MTc0NjEyZTYxNzA2MTYzNjg2NTYzNmUyZTZmNzI2NzJmNjk2ZDY3MmY0MTY5NGM2NTYxNzI2ZTY5NmU2NzJmNmQ2YzJmMzEzMTJlNDE3MDcyNjk2ZjcyNjkyZjI1NDUzOTI1Mzk0NDI1Mzk0NTI1NDUzOTI1NDEzMjI1MzkzMTI1NDUzNzI1NDIzOTI1MzgzMTI1NDUzOTI1NDEzMTI1NDIzOTI1NDUzOTI1Mzk0MjI1MzgzNjJlNzA2ZTY3?x-oss-process=image/format,png