Вивчайте Порівняння Продуктивності Алгоритмів | Високопродуктивний пошук правил та оптимізація масштабування

Свайпніть щоб показати меню

Розуміння обчислювальних відмінностей між Apriori та FP-Growth є ключовим при масштабному видобутку асоціативних правил. Нижче наведено структурований огляд для ефективного порівняння цих двох алгоритмів:

Використання пам'яті

Apriori

Генерує всі можливі набори елементів і зберігає їх у пам'яті, що може призвести до експоненційного зростання використання пам'яті зі збільшенням кількості унікальних елементів;

FP-Growth

Створює компактну структуру FP-дерева, яка зберігає транзакції ефективніше шляхом об'єднання спільних префіксів, що значно зменшує обсяг пам'яті для щільних наборів даних.

Швидкість

Apriori

Багаторазове сканування набору даних для підрахунку частотності наборів елементів, що призводить до високого часу виконання, особливо зі збільшенням розміру набору елементів;

FP-Growth

Потребує лише двох повних проходів по даних — один для визначення частих елементів і ще один для побудови FP-дерева, що робить його значно швидшим для великих наборів даних.

Масштабованість

Apriori

Має труднощі з масштабованістю через комбінаційний вибух кандидатних наборів елементів, що робить його непрактичним для дуже великих або щільних наборів даних;

FP-Growth

Краще масштабується, уникаючи генерації кандидатів і використовуючи стиснення дерева, що дозволяє ефективно виконувати пошук навіть зі зростанням розміру даних і складності наборів елементів.

Практичні сценарії

Використання Apriori

Коли набори даних невеликі або розріджені, важлива інтерпретованість і простота, або коли потрібно легко налаштовувати пороги мінімальної підтримки;

Використання FP-Growth

Коли набори даних великі, щільні, або пріоритетними є ефективність використання пам'яті та швидкість.

Наступний приклад коду демонструє створення синтетичного набору даних транзакцій кошика покупок і порівняння часу виконання алгоритмів Apriori та FP-Growth за допомогою бібліотеки mlxtend у Python. Ви побачите, як кожен алгоритм обробляє одні й ті самі дані та як відрізняється час їх виконання, що підкреслює їхню ефективність у практичних сценаріях.


              123456789101112131415161718192021222324252627
            
import pandas as pd
from mlxtend.frequent_patterns import apriori, fpgrowth
import numpy as np
import time

# Create a medium-sized synthetic dataset
np.random.seed(42)
items = ['apple', 'banana', 'milk', 'bread', 'butter', 'cheese', 'eggs', 'juice']
n_transactions = 3000
data = []
for _ in range(n_transactions):
    basket = np.random.choice(items, size=np.random.randint(2, 6), replace=False)
    data.append({item: (item in basket) for item in items})
df = pd.DataFrame(data)

# Timing Apriori
start_apriori = time.time()
apriori(df, min_support=0.05, use_colnames=True)
end_apriori = time.time()

# Timing FP-Growth
start_fpgrowth = time.time()
fpgrowth(df, min_support=0.05, use_colnames=True)
end_fpgrowth = time.time()

print(f"Apriori runtime: {end_apriori - start_apriori:.3f} seconds")
print(f"FP-Growth runtime: {end_fpgrowth - start_fpgrowth:.3f} seconds")

1. Коли слід віддавати перевагу FP-Growth над Apriori для пошуку асоціативних правил?

2. Яке твердження найкраще описує різницю в обчислювальній складності між Apriori та FP-Growth?

Все було зрозуміло?

Дякуємо за ваш відгук!

Секція 2. Розділ 2

Запитати АІ

Запитайте про що завгодно або спробуйте одне із запропонованих запитань, щоб почати наш чат

Секція 2. Розділ 2