Блог

Я написал функцию для определения частоты наборов элементов размера k с учетом наборов элементов-кандидатов. Набор данных содержит более 16000 транзакций. Может кто-нибудь, пожалуйста, помочь мне в оптимизации этой функции, поскольку в текущей форме выполнение с minSupport = 1 занимает около 45 минут.

Образец набора данных

Алгоритм 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 dataframe, это означает, что вы установили pandas, и если вы установили pandas, то у вас определенно есть Numpy, поэтому я решил использовать его. У вас не может быть Numpy, если вы имеете дело с фреймом данных pandas.

Попробуйте онлайн!

 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 version (встроенной 2D-версии нет, поэтому ее пришлось реализовывать отдельно), в котором нет длинных циклов чистого python, большая часть времени тратится на функции Numpy.

Пожалуйста, попробуйте, если этот алгоритм 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}