Python: 优化函数以找到给定候选项集的大小为 k 的频繁项集
Python: Optimise the function to find frequent itemsets of size k given candidate itemsets
我编写了一个函数来查找给定候选项集的大小为 k 的项集的频率。数据集包含超过 16000 笔交易。有人可以帮我优化这个功能吗,因为当前形式使用 minSupport=1 执行大约需要 45 分钟。
示例数据集
算法 0(参见下面的其他算法)
使用 Numba. Numba is a 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 dataframe,这意味着你已经安装了 pandas,如果你安装了 pandas 那么你肯定有 Numpy,所以我决定使用它。如果你正在处理 pandas 数据帧,你就不能没有 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 的排序部分可能不是瓶颈,事务 while 循环可能是瓶颈。
所以为了改善这种情况,我决定实施并使用更快的算法和 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}
我已经改变了你代码的执行顺序。但是,由于我无法访问您的实际输入数据,因此很难检查优化后的代码是否产生了预期的输出以及您获得了多少速度。
算法 0
import pandas as pd
import numpy as np
from collections import defaultdict
def selectLk(dataSet,Ck,minSupport):
dict_data = defaultdict(int)
for _, row in dataSet.iterrows():
for items in Ck:
dict_data[items] += all(item in row.values for item in items)
Lk = { k : v for k,v in dict_data.items() if v > minSupport}
return Lk
if __name__ == '__main__':
data = list(range(0, 1000, 10))
df_data = {}
for i in range(26):
sample = np.random.choice(data, size=16000, replace=True)
df_data[f"d{i}"] = sample
dataset = pd.DataFrame(df_data)
C1 = set()
C1.add((100, 160))
C1.add((170, 180))
C1.add((190, 200))
Lk1 = selectLk(dataset, C1, 1)
dataset = pd.DataFrame([[100,160,100,160],[170,180,190,200],[100,160,190,200]])
Lk2 = selectLk(dataset, C1, 1)
print(Lk1)
print(Lk2)
算法 1
算法 1 利用 numpy.equal.outer
,它创建 Ck 元组中任何匹配元素的布尔掩码。然后,应用.all()
操作。
def selectLk(dataSet, Ck, minSupport):
dict_data = defaultdict(int)
dataSet_np = dataSet.to_numpy(copy=False)
for items in Ck:
dict_data[items] = dataSet[np.equal.outer(dataSet_np, items).any(axis=1).all(axis=1)].shape[0]
Lk = { k : v for k, v in dict_data.items() if v > minSupport}
return Lk
结果:
{(190, 200): 811, (170, 180): 797, (100, 160): 798}
{(190, 200): 2, (100, 160): 2}
我编写了一个函数来查找给定候选项集的大小为 k 的项集的频率。数据集包含超过 16000 笔交易。有人可以帮我优化这个功能吗,因为当前形式使用 minSupport=1 执行大约需要 45 分钟。
示例数据集
算法 0(参见下面的其他算法)
使用 Numba. Numba is a 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 dataframe,这意味着你已经安装了 pandas,如果你安装了 pandas 那么你肯定有 Numpy,所以我决定使用它。如果你正在处理 pandas 数据帧,你就不能没有 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 的排序部分可能不是瓶颈,事务 while 循环可能是瓶颈。
所以为了改善这种情况,我决定实施并使用更快的算法和 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}
我已经改变了你代码的执行顺序。但是,由于我无法访问您的实际输入数据,因此很难检查优化后的代码是否产生了预期的输出以及您获得了多少速度。
算法 0
import pandas as pd
import numpy as np
from collections import defaultdict
def selectLk(dataSet,Ck,minSupport):
dict_data = defaultdict(int)
for _, row in dataSet.iterrows():
for items in Ck:
dict_data[items] += all(item in row.values for item in items)
Lk = { k : v for k,v in dict_data.items() if v > minSupport}
return Lk
if __name__ == '__main__':
data = list(range(0, 1000, 10))
df_data = {}
for i in range(26):
sample = np.random.choice(data, size=16000, replace=True)
df_data[f"d{i}"] = sample
dataset = pd.DataFrame(df_data)
C1 = set()
C1.add((100, 160))
C1.add((170, 180))
C1.add((190, 200))
Lk1 = selectLk(dataset, C1, 1)
dataset = pd.DataFrame([[100,160,100,160],[170,180,190,200],[100,160,190,200]])
Lk2 = selectLk(dataset, C1, 1)
print(Lk1)
print(Lk2)
算法 1
算法 1 利用 numpy.equal.outer
,它创建 Ck 元组中任何匹配元素的布尔掩码。然后,应用.all()
操作。
def selectLk(dataSet, Ck, minSupport):
dict_data = defaultdict(int)
dataSet_np = dataSet.to_numpy(copy=False)
for items in Ck:
dict_data[items] = dataSet[np.equal.outer(dataSet_np, items).any(axis=1).all(axis=1)].shape[0]
Lk = { k : v for k, v in dict_data.items() if v > minSupport}
return Lk
结果:
{(190, 200): 811, (170, 180): 797, (100, 160): 798}
{(190, 200): 2, (100, 160): 2}