Apriori算法中的辅助函数（一）

机器学习小白学习心得：

Apriori算法是发现频繁项集的一种方法。Apriori算法的两个输人参数分别是最小支持度和数据集。该算法首先

会生成所有单个物品的项集列表。接着扫描交易记录来查看哪些项集满足最小支持度要求，那些不满足最小支

持度的集合会被去掉。然后,对剩下来的集合进行组合以生成包含两个元素的项集。接下来，再重新扫描交易记

录，去掉不满足最小支持度的项集。该过程重复进行直到所有项集都被去掉。

伪算法：

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

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

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

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

机器学习实战中的python实现的算法有一点的缺陷，可能达不到想要的结果，这里稍微改进一点，借助

copy包中的deepcopy()函数来弥补这一缺陷，大家有更好的方法，欢迎评论区留言。

#!/usr/bin/env python
# _*_ coding: utf-8 _*_
# @Time : 2020/10/5 14:54
# @Author : 沐蓉
# @Version：V 0.1
# @File : apriori.py
# @desc : apriori算法

import copy

# 创建初始数据集
def loadDataSet():
    return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]

# 创建大小为1的所有候选项集的集合
def creatC1(dataSet):
    C1 = []
    for transaction in dataSet:
        for item in transaction:
            if not [item] in C1:
                C1.append([item])
    C1.sort()
    # print(*map(frozenset, C1))
    return map(frozenset, C1)

# creatC1(loadDataSet())

# 重复扫描每条记录，计算所有项集的支持度
"""
    D: 数据集
    Ck: 候选项目集
    minSupport: 最小支持度
"""
def scanD(D, Ck, minSupport):
    # print("D:", D)
    # print("Ck:", Ck)
    # print("minSupport:", minSupport)
    # # numItems = len(list(D))
    ssCnt = {}
    tmpD = copy.deepcopy(D)         # 不要直接操作D，需要深拷贝
    for tid in tmpD:                # tid为数据集中的一条交易记录
        # print("tid:", tid)
        ListCk = copy.deepcopy(Ck)  # 借助深拷贝
        for can in ListCk:          # can为每次从候选集中拿出的一个项集
            if can.issubset(tid):
                if can in ssCnt:
                    ssCnt[can] += 1
                else:
                    ssCnt[can] = 1
    numItems = len(list(D))
    print("numItems:", numItems)
    retList = []
    supportData = {}
    for key in ssCnt:
        support = ssCnt[key] / numItems     #计算每个项集的支持度
        if support >= minSupport:
            retList.insert(0, key)          #列表前插法插入每个满足支持度的项集：retList = [2, 3, 5]
        supportData[key] = support          # supportData = {'2':0.75, '3':0.75, '5':0.75}
    return retList, supportData

if __name__ == '__main__':

    dataSet = loadDataSet()
    C1 = creatC1(dataSet)
    D = map(set, dataSet)

    L1, suppData0 = scanD(D, C1, 0.5)
    print("L1: {} \nsuppData0: {}".format(L1, suppData0))

Apriori算法中的辅助函数（一）

推荐阅读