Анализ рыночной корзины в Python для большого набора данных транзакций

Question

При применении функций apriori (support >= 0.01) и association_rules с использованием пакета python mlxtend для данных транзакций строк 4.2L+ (в виде разреженной матрицы) генерация наборов частых элементов и правил связывания занимает слишком много времени.

Пример матрицы разреженных транзакций (фрейм данных pandas), входные данные для MBA:

Счет №./ Продукция Рубашка Футболка Джинсовая обувь

    1                  1        1         0        0
    2                  0        0         1        0  
    3                  0        1         0        1

а) Есть ли способ оптимизировать представление разреженной матрицы данных транзакций перед применением MBA?

б) какие-либо альтернативные эффективные представления данных транзакций?

Answer 1

Априорный алгоритм получает список списков, где каждый список является транзакцией. Вы передаете список транзакций? Например:

transactions = [['milk', 'bread', 'water'],['coffe', 'sugar' ],['burgers', 'eggs']]

здесь у вас есть список транзакций (списки). Тогда вы можете передать его априори.

from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import apriori
from mlxtend.frequent_patterns import association_rules
import time

support_threshold = 0.004

te = TransactionEncoder()
te_ary = te.fit(transactions).transform(transactions)
df = pd.DataFrame(te_ary, columns=te.columns_)
logging.debug("Calculating itemset according to support...")
# time 
start_time = time.clock()
# apriori
frequent_itemsets = apriori(df, min_support=support_threshold, use_colnames=True)
# end time to calculation
end_time = time.clock()
time_apriori = (end_time-start_time)/60
apriori_decimals = "%.2f" % round(time_apriori,2)
print("\n\nCompleted in %s minutes\n" % apriori_decimals)

print(frequent_itemsets) #dataframe with the itemsets

lift = association_rules(frequent_itemsets, metric="lift", min_threshold=1)
print(lift) #dataframe with confidence, lift, conviction and leverage metrics calculated

Что касается минимального порога поддержки и времени, которое потребовался алгоритму apriori для получения результата, с небольшими значениями min_support у нас будет много правил ассоциации. Таким образом, для их вычисления алгоритму требуется время. Это одно из известных ограничений алгоритма.

Здесь вы можете найти общее объяснение того, как работает алгоритм apriori. Вот некоторые основные моменты:

Apriori использует подход "снизу вверх", при котором частые подмножества расширяются по одному элементу за один раз (известный как генерация кандидатов). Затем группы кандидатов проверяются по данным. Алгоритм завершается, когда дальнейшие успешные расширения не найдены.

Apriori использует поиск в ширину и хэш-структуру дерева для эффективного подсчета наборов элементов-кандидатов. Он генерирует подходящие наборы элементов длины k из наборов элементов длины k-1. Тогда это сокращает кандидатов, у которых есть нечастый подшаблон. Согласно лемме о нисходящем замыкании, набор кандидатов содержит все часто встречающиеся наборы элементов длины k. После этого он сканирует базу данных транзакций, чтобы определить частые наборы элементов среди кандидатов.

Как мы видим, для набора данных с большим количеством частых элементов или с низким значением поддержки наборы-кандидаты всегда будут очень большими.

Эти большие наборы данных требуют много памяти для хранения. Кроме того, алгоритм apriori также просматривает все части базы данных несколько раз, чтобы вычислить частоту наборов элементов в k-itemset. Таким образом, алгоритм apriori может быть очень медленным и неэффективным, в основном, когда объем памяти ограничен, а количество транзакций велико.

Например, я попробовал алгоритм apriori со списком транзакций с 25900 транзакциями и значением min_support 0,004. Алгоритму потребовалось около двух с половиной часов, чтобы выдать результат.

Answer 2

Используйте алгоритм fpgrowth, который почти в 5 раз быстрее исходного apriori для больших наборов данных.

Я испробовал 1,4 миллиона транзакций и 200 уникальных предметов. Apriori потребовалось более 4 часов, в то время как fpgrowth потребовалось менее 5 минут для генерации частых наборов элементов, учитывая худшее минимальное значение поддержки.

Версия библиотеки mlxtend>= 0.17 обеспечивает реализацию fpgrowth и дает те же результаты, что и apriori, что экономит ваше время и пространство. Ваш ввод находится в горячем формате кодирования и является допустимым форматом ввода. Ссылка: http://rasbt.github.io/mlxtend/user_guide/frequent_patterns/fpgrowth/

from mlxtend.frequent_patterns import fpgrowth
from mlxtend.frequent_patterns import association_rules

frequent_itemsets = fpgrowth(df, min_support=0.6)
rules = association_rules(frequent_itemsets, metric="confidence", min_threshold=0.7)