Python:优化函数以找到给定候选项集的大小为k的频繁项集

Question

我编写了一个函数来查找给定候选项集的大小为 k 的项集的频率。数据集包含超过 16000 笔交易。有人可以帮助我优化此功能，因为使用当前形式执行 minSupport=1 大约需要 45 分钟。
样本数据集

Answer 1

算法 0 (请参阅下面的其他算法)
使用 Numba 实现算法的提升. Numba 是 JIT将 Python 代码转换为高度优化的 C++ 代码，然后编译为机器代码的编译器。对于许多算法，Numba 实现了 50-200 倍的速度提升。
要使用 numba，您必须通过 pip install numba 安装它，请注意 Numba 仅支持 Python <= 3.8，3.9 尚未发布!
我已经稍微重写了您的代码以满足 Numba 编译要求，我的代码在行为上应该与您的相同，请进行一些测试。
我的 numba 优化代码应该会给你很好的加速!
我也创建了一些人工的简短示例输入数据，以进行测试。
Try it online!

import numba, numpy as np, pandas as pd

@numba.njit(cache = True)
def selectLkNm(dataSet,Ck,minSupport):
    dict_data = {}
    transactions = dataSet.shape[0]
    for items in Ck:
        count = 0
        while count < transactions:
            if items not in dict_data:
                dict_data[items] = 0
            for item in items:
                for e in dataSet[count, :]:
                    if item == e:
                        break
                else:
                    break
            else:
                dict_data[items] += 1
            count += 1
    Lk = {}
    for k, v in dict_data.items():
        if v >= minSupport:
            Lk[k] = v
    return Lk
    
def selectLk(dataSet, Ck, minSupport):
    tCk = numba.typed.List()
    for e in Ck:
        tCk.append(e)
    return selectLkNm(dataSet.values, tCk, minSupport)

dataset = pd.DataFrame([[100,160,100,160],[170,180,190,200],[100,160,190,200]])
C1 = set()
C1.add((100, 160))
C1.add((170, 180))
C1.add((190, 200))
Lk = selectLk(dataset, C1, 2)
print(Lk)

输出:

{(100, 160): 2, (190, 200): 2}

算法 1 (请参阅下面的其他算法)
我通过对数据进行排序来改进算法 0(以上)，如果您的 Ck 中有很多值或者 Ck 中的每个元组都很长，它会提供很好的加速。
Try it online!

import numba, numpy as np, pandas as pd

@numba.njit(cache = True)
def selectLkNm(dataSet,Ck,minSupport):
    assert dataSet.ndim == 2
    dataSet2 = np.empty_like(dataSet)
    for i in range(dataSet.shape[0]):
        dataSet2[i] = np.sort(dataSet[i])
    dataSet = dataSet2
    dict_data = {}
    transactions = dataSet.shape[0]
    for items in Ck:
        count = 0
        while count < transactions:
            if items not in dict_data:
                dict_data[items] = 0
            for item in items:
                ix = np.searchsorted(dataSet[count, :], item)
                if not (ix < dataSet.shape[1] and dataSet[count, ix] == item):
                    break
            else:
                dict_data[items] += 1
            count += 1
    Lk = {}
    for k, v in dict_data.items():
        if v >= minSupport:
            Lk[k] = v
    return Lk
    
def selectLk(dataSet, Ck, minSupport):
    tCk = numba.typed.List()
    for e in Ck:
        tCk.append(e)
    return selectLkNm(dataSet.values, tCk, minSupport)

dataset = pd.DataFrame([[100,160,100,160],[170,180,190,200],[100,160,190,200]])
C1 = set()
C1.add((100, 160))
C1.add((170, 180))
C1.add((190, 200))
Lk = selectLk(dataset, C1, 2)
print(Lk)

输出:

{(100, 160): 2, (190, 200): 2}

算法2 (请参阅下面的其他算法)
如果您不被允许使用 Numba，那么我建议您对算法进行下一步改进。我对您的数据集进行了预排序以搜索不在 O(N) 中的每个项目时间但在 O(Log(N))时间要快得多。
我在你的代码中看到你使用了 Pandas 数据框，这意味着你已经安装了 Pandas ，如果你安装了 Pandas ，那么你肯定有 Numpy，所以我决定使用它。如果您正在处理 Pandas 数据框，则不能没有 Numpy。
Try it online!

import numpy as np, pandas as pd, collections

def selectLk(dataSet,Ck,minSupport):
    dataSet = np.sort(dataSet.values, axis = 1)
    dict_data = collections.defaultdict(int)
    transactions = dataSet.shape[0]
    for items in Ck:
        count = 0
        while count < transactions:
            for item in items:
                ix = np.searchsorted(dataSet[count, :], item)
                if not (ix < dataSet.shape[1] and dataSet[count, ix] == item):
                    break
            else:
                dict_data[items] += 1
            count += 1
    Lk = {k : v for k, v in dict_data.items() if v >= minSupport}
    return Lk
    
dataset = pd.DataFrame([[100,160,100,160],[170,180,190,200],[100,160,190,200]])
C1 = set()
C1.add((100, 160))
C1.add((170, 180))
C1.add((190, 200))
Lk = selectLk(dataset, C1, 2)
print(Lk)

输出:

{(100, 160): 2, (190, 200): 2}

算法3
我只是有一个想法，算法 2 的排序部分可能不是瓶颈，可能事务 while 循环可能是瓶颈。
因此，为了改善情况，我决定实现并使用具有 2D 搜索排序版本的更快算法(没有内置的 2D 版本，因此必须单独实现)，大多数情况下它没有任何长的纯 python 循环用在 Numpy 函数中。
请尝试此 Algo 3 是否会更快，如果排序不是瓶颈而是内部 while 循环，它应该只会更快。
Try it online!

import numpy as np, pandas as pd, collections

def selectLk(dataSet, Ck, minSupport):
    def searchsorted2d(a, bs):
        s = np.r_[0, (np.maximum(a.max(1) - a.min(1) + 1, bs.ravel().max(0)) + 1).cumsum()[:-1]]
        a_scaled = (a + s[:, None]).ravel()
        def sub(b):
            b_scaled = b + s
            return np.searchsorted(a_scaled, b_scaled) - np.arange(len(s)) * a.shape[1]
        return sub

    assert dataSet.values.ndim == 2, dataSet.values.ndim
    dataSet = np.sort(dataSet.values, axis = 1)
    dict_data = collections.defaultdict(int)
    transactions = dataSet.shape[0]
    Ck = np.array(list(Ck))
    assert Ck.ndim == 2, Ck.ndim
    ss = searchsorted2d(dataSet, Ck)
    for items in Ck:
        cnts = np.zeros((dataSet.shape[0],), dtype = np.int64)
        for item in items:
            bs = item.repeat(dataSet.shape[0])
            ixs = np.minimum(ss(bs), dataSet.shape[1] - 1)
            cnts[...] += (dataSet[(np.arange(dataSet.shape[0]), ixs)] == bs).astype(np.uint8)
        dict_data[tuple(items)] += int((cnts == len(items)).sum())
    return {k : v for k, v in dict_data.items() if v >= minSupport}
    
dataset = pd.DataFrame([[100,160,100,160],[170,180,190,200],[100,160,190,200]])
C1 = set()
C1.add((100, 160))
C1.add((170, 180))
C1.add((190, 200))
Lk = selectLk(dataset, C1, 2)
print(Lk)

输出:

{(100, 160): 2, (190, 200): 2}