机器学习实战--Apriori算法挖掘频繁项集

Posted on | In | 阅读

Apriori算法是最著名的关联规则的挖掘方法，可以使用它挖掘频繁项集发现数据中的规律。著名的“啤酒与尿布”案例就是在分析大量超市的事务之后发现了“啤酒”与“尿布”这一频繁项集。这篇笔记主要是记录Apriori的Python3代码实现的，会就算法来讲解Apriori挖掘频繁项集的步骤，算法的详细内容在《数据挖掘-概念与技术》一书中有非常详细的讲解，这里不再赘述

完整代码在这里

  1. 数据格式

    类似下方的二维数组，每一个list代表一个transaction，里面的每个数都是item的编号

    1
    [[1,2,5], [2,4], [2,3], [1,2,4],[1,3], [2,3], [1,3], [1,2,3,5], [1,2,3]]

  2. 读取数据

    1
    2
    3
    4
    5
    6
    7
    8
    def loadDataSet():
        thing_arr = []

        with open('data/Groceries.txt', 'r') as f:
            X = f.read()
            thing_arr = json.loads(X)
            f.close()
        return thing_arr

    ​

  3. 首先生成C1集合，将所有出现过的item编号都加入到C1中

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    def createC1(dataSet):
        '''
        生成C1
        :param dataSet:
        :return:
        '''
        C1 = []
        for transaction in dataSet:
            for item in transaction:
                if not [item] in C1:
                    C1.append([item])
        C1.sort()
        #将项集列表转换为不可变集和
        return [frozenset(item) for item in C1]

    ​

  4. 扫描数据集计数，去除Ck中的非频繁项集，生成L1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    def scanD(D, Ck, minSupport = 50):
        '''
        扫描事务集D过滤Ck
        :param D:
        :param Ck:
        :param minSupport:
        :return:
        '''
        ssCnt = {}
        for tid in D:
            for can in Ck:
                if can.issubset(tid):
                    if can not in ssCnt.keys() : ssCnt[can] = 1
                    else: ssCnt[can] += 1

        retList = []
        supportData = {}
        for key in ssCnt:
            support = ssCnt[key]
            if support >= minSupport:
                retList.insert(0, key)
            supportData[key] = support
        return retList, supportData

    ​

  5. 从Lk-1集中生成Ck集合，需要将Lk-1项集进行排序，然后将前k-2项相同的集合进行合并

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    def aprioriGen(Lk, k):
        '''
        生成Ck
        :param Lk:
        :param k:
        :return:
        '''
        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

    ​

  6. 将上述步骤结合起来，就可以生成所有的频繁项集，直到为空终止算法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    def apriori(dataSet, minSupport = 50):
        C1 = createC1(dataSet=dataSet)
        D = [set(item) for item in 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)
            L.append(Lk)
            k += 1
        return L, supportData

  7. 到此使用Apriori挖掘频繁项集就编写完了，后面还有关联规则的挖掘，未完。。

​