Вопрос TL; DR
Это длинный вопрос, так что вот версия TL; DR: я реализую априорный алгоритм, и он медленный. медленная часть - это когда я пытаюсь сгенерировать Lk форму Ck, и ему приходится сканировать весь набор данных (более или менее), чтобы узнать, часто ли кандидат или нет. Как я могу сделать эту часть быстрее? Есть ли какая-либо структура данных, которая ускоряет этот повторный поиск по набору данных?
Длинный вопрос
У меня есть задание написать алгоритм априори с python. Ограничения не в том, чтобы использовать pandas и не использовать какой-либо модуль, реализующий апериори, например apyori. Так что создание C1 и L1 вообще не проблема. Генерация Ck из Lk-1 тоже в порядке. узкое место всего этого генерирует Lk из Ck. в этом разделе будет сравниваться каждый кандидат со всем набором данных, который требует времени для небольших минимальных_поддержек.
Я потратил некоторое время на поиск улучшенных версий apriori, и среди тех, которые я мог понять, эта была лучшей (IMO): https://arxiv.org/pdf/1403.3948.pdf
В этом документе предлагается вести список транзакций для каждого элемента, в котором указано, в каких транзакциях этот элемент / набор элементов появился (назовем его found_in). Имея это под рукой, мы можем сократить количество поисков при генерации Lk из Ck, поскольку мы можем сканировать только элементы, упомянутые в этом списке (found_in).
Я реализовал это и это сократило время примерно в 4 раза, что удивительно. Тем не менее, этого недостаточно для выполнения задания, так как я должен извлекать 40 000 частых шаблонов.
Так что я думаю, что, возможно, алгоритм хорош, но используемые мной структуры данных python слишком медленные. догнать. Итак, вот мои вопросы:
- Могу ли я сделать этот алгоритм быстрее, используя лучшую структуру данных? Возможно, что-то в
ctype? - Есть ли проблема с моим кодом, из-за которой он зависает? Результаты этого алгоритма кажутся мне звуковыми (по сравнению с выводом
apyori) - Есть какие-нибудь советы, чтобы улучшить его или склонить к некоторым условиям?
Я знаю, что этот вопрос требует огромного время тщательно исследовать, и я этого не жду. Поэтому приветствуются любые маленькие подсказки.
медленная часть кода:
def gen_Lk(Ck: dict, dataset: list, min_support_count: int) -> dict:
subset_time = 0
Lk = {}
for candidate, TIDs in Ck.items():
if len(TIDs) < min_support_count:
continue
new_TIDs = set()
tt = time()
for TID in TIDs:
comp_transaction = dataset[TID]
# equivalent to: if candidate.issubset(dataset[TID])
# this is the slowest part of the code and this is how to make it a
# bit faster
if not any(item not in comp_transaction for item in candidate):
new_TIDs.add(TID)
if len(new_TIDs) < min_support_count:
continue
Lk[candidate] = new_TIDs
return Lk
весь код (извините за плохие комментарии):
from itertools import combinations
import pickle
from time import time
def has_infrequent_subset(candidate: set, previous_L: list) -> bool:
"""
A function to prone some of candidates
Parameters
----------
candidate -- a set to check whether all of its subsets are frequent or not.
if any subset is not frequent, the function will returns True,
otherwise returns False.
previous_L -- a list of tuples to check candidate's subsets against it.
an instance of previous_L could be found in 'Examples' part.
Returns
-------
a boolean value. True means there are some subsets in the candidate that
are not frequent with respect to previous_L and this value should no be
included in the final Ck result. False means all subsets are frequent and
we shall include this candidate in our Ck result.
Examples
--------
>>> previous_L = [(1,2,4),(2,3,6),(2,3,8),(2,6,7),(2,6,8),(3,4,5),(3,6,8)]
>>> has_infrequent_subset((2,3,6,8), previous_L)
False
>>> has_infrequent_subset((2,3,6,7), previous_L)
True
"""
subsets = combinations(candidate, len(candidate)-1)
for subset in subsets: # subset is a tuple
if subset not in previous_L:
return True
return False
def apriori_gen(previous_L: dict) -> dict:
"""
A function generate candidates with respect to Lk-1 (previous_L). tries
prone the results with the help of has_infrequent_subset(). for every new
candidate found, if all of its subsets with the length of k-1 are not
frequent in Lk-1 (previous_L), it will not be added to the result.
"""
Ck = {}
for item_1, TIDs1 in previous_L.items():
for item_2, TIDs2 in previous_L.items():
if item_1[:-1] == item_2[:-1] and item_1[-1] < item_2[-1]:
new_item = tuple([*item_1, item_2[-1]])
if has_infrequent_subset(new_item, previous_L):
continue
new_TIDs = TIDs1 if len(TIDs1) < len(TIDs2) else TIDs2
Ck[new_item] = new_TIDs
return Ck
def generate_L1(dataset: list, min_support_count: int) -> dict:
"""
Generates L1 itemset from given dataset with respect to min_support_count
Parameters
----------
dataset -- a list of lists. each inner list represent a transaction which
its content are items bought in that transacton. the outer list is the
dataset which contain all transactions.
min_support_count -- an integer which is used to check whether one item is
frequent or not.
Returns
-------
a dictionary with keys representing L1 frequent items fount and values
representing what transactions that item appeared in. the values are sets.
the values will be useful later as this paper demonstrates:
https://arxiv.org/pdf/1403.3948.pdf
Examples
--------
>>> generate_L1([[1,2,3], [3,4,1], [3,4,5]], 3)
{(3,): {0, 1, 2}}
>>> generate_L1([[1,2,3], [3,4,1], [3,4,5]], 2)
{(1,): {0, 1}, (3,): {0, 1, 2}, (4,): {1, 2}}
"""
L1 = {}
for TID, transaction in enumerate(dataset):
for item in transaction:
if (item,) not in L1:
L1[(item,)] = set()
L1[(item,)].add(TID)
return {item: TIDs for item, TIDs in L1.items()
if len(TIDs) >= min_support_count}
def gen_Lk(Ck: dict, dataset: list, min_support_count: int) -> dict:
st = time()
Lk = {}
for candidate, TIDs in Ck.items():
if len(TIDs) < min_support_count:
continue
new_TIDs = set()
tt = time()
for TID in TIDs:
comp_transaction = dataset[TID]
# equivalent to: if candidate.issubset(dataset[TID])
# this is the slowest part of the code and this is how to make it a
# bit faster
if not any(item not in comp_transaction for item in candidate):
new_TIDs.add(TID)
if len(new_TIDs) < min_support_count:
continue
Lk[candidate] = new_TIDs
return Lk
def apriori(min_support_count: int, dataset: list):
st = time()
L1 = generate_L1(dataset, min_support_count)
L = {1: L1}
for k in range(2, 1000):
if len(L[k-1]) < 2:
break
Ck = apriori_gen(L[k-1])
L[k] = gen_Lk(Ck, dataset, min_support_count)
return L
if __name__ == '__main__':
with open(paths.q1.listed_ds, 'rb') as f:
dataset = pickle.load(f)
L = apriori(len(dataset)*0.03, dataset)
result = []
for _, Lk in L.items():
result.extend(Lk.keys())
print(result, len(result))