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

算法0（请参阅下面的其他算法）

使用Numba实现了算法的增强。Numba是一个JIT编译器，可将Python代码转换为高度优化的C ++代码，然后编译为机器代码。对于许多算法，Numba的速度提高了50-200倍。

要使用numba，您必须通过安装它pip install numba，请注意，仅Numba仅支持python <= 3.8，而3.9尚未发布！

我已经重新编写了一些代码以满足Numba的编译要求，我的代码在行为上应该与您的代码相同，请进行一些测试。

我的numba优化代码应该为您带来非常好的加速！

我也创建了一些人为的简短示例输入数据来进行测试。

在线尝试！

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中的每个元组都相当长，它将大大提高速度。

在线尝试！

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，所以我决定使用它。如果要处理熊猫数据框，则不能没有Numpy。

在线尝试！

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的排序部分可能不是瓶颈，而循环中的事务可能是瓶颈。

因此，为了改善情况，我决定在2D searchsorted版本（没有内置2D版本，因此必须单独实现）中实施并使用更快的算法，大多数情况下，它没有任何长的纯Python循环用于Numpy函数。

请尝试一下该Algo 3是否会更快，如果不是排序瓶颈，而是内部while循环，那么它应该只会更快。

在线尝试！

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}