Вивчайте Обробка Потоків Транзакційних Даних за Допомогою Алгоритму Apriori | Основи асоціативних правил та транзакційного аналізу

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

Алгоритм Apriori є базовим інструментом для виявлення частих наборів товарів у транзакційних даних, що є ключовим для аналізу кошика покупця. В основі Apriori лежить Принцип Apriori, також відомий як властивість спадної замкненості.

Визначення

Принцип Apriori – якщо набір товарів є частим, то всі його підмножини також повинні бути частими.

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

Генерація кандидатів — це етап підбору алгоритму. На кожному кроці алгоритм розглядає виграшні часті набори товарів з попереднього раунду та об'єднує їх для створення нових, більших груп, які називаються кандидатами. Для ефективності алгоритм об'єднує лише ті набори, які майже ідентичні, тобто мають усі однакові товари, крім останнього.

Як це працює: Якщо алгоритм виявляє, що {Bread, Milk} та {Bread, Diapers} обидва є популярними окремо, він об'єднує їх, щоб створити новий кандидат з трьох товарів для наступного раунду: {Bread, Milk, Diapers}.

Одразу після створення нових кандидатів алгоритм переходить до фази Обрізання для усунення зайвих комбінацій до виконання складних обчислень у базі даних. Цей крок повністю ґрунтується на Принципі Apriori, який стверджує, що великий набір товарів може бути частим лише тоді, коли всі його менші підмножини також є частими. Під час обрізання алгоритм ретельно перевіряє кожного нового кандидата та його менші підмножини. Якщо хоча б одна підмножина не пройшла відбір у попередньому раунді, весь кандидат одразу видаляється.

Як це працює: Уявіть, що створено кандидата {Bread, Milk, Eggs}. Алгоритм перевіряє його підкомбінації: {Bread, Milk}, {Bread, Eggs} та {Milk, Eggs}. Якщо у ваших історичних транзакціях {Milk, Eggs} — рідкісна комбінація, яка не пройшла попередній раунд, алгоритм повністю відкидає {Bread, Milk, Eggs}. Це дозволяє уникнути витрат обчислювальних ресурсів на комбінацію, яка математично приречена на невдачу.

Після того, як список кандидатів скорочено до найбільш перспективних, алгоритм переходить до етапу Ідентифікація частих наборів товарів. Система сканує ваші сирі транзакційні бази даних, щоб підрахувати, скільки разів ці залишені групи кандидатів зустрічаються разом у реальних покупках. Кількість кожного кандидата перетворюється у відсоток. Якщо цей показник досягає або перевищує встановлений вами Мінімальний поріг підтримки, кандидат офіційно визнається Частим набором товарів.

Визначення

Мінімальний поріг підтримки — це визначене користувачем обмеження, яке встановлює найнижчу частоту, з якою набір елементів має з’являтися, щоб вважатися значущим в алгоритмі Apriori. Встановлюючи цей поріг, ви відсіюєте набори елементів, які зустрічаються занадто рідко у наборі даних. Високий поріг призведе до меншої кількості, але більш поширених наборів елементів, що може призвести до пропуску цікавих, але рідкісних комбінацій. Занадто низький поріг може перевантажити вас надто великою кількістю наборів елементів, включаючи ті, що мають малу практичну цінність. Обраний поріг безпосередньо впливає на глибину та фокус вашого аналізу, тому він має відповідати цілям і масштабу вашого дослідження даних.

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

Щоб зробити ці ідеї конкретними, розглянемо простий приклад з невеликим набором даних. Припустимо, у вас є такі транзакції:

Транзакція 1: {Milk, Bread};
Транзакція 2: {Milk, Diaper, Beer, Bread};
Транзакція 3: {Milk, Diaper, Beer, Cola};
Транзакція 4: {Diaper, Beer};
Транзакція 5: {Milk, Diaper, Bread, Beer}.

Алгоритм спочатку визначає всі окремі елементи, які часто зустрічаються, потім генерує кандидатні пари з них, відсіює ті, що містять рідкісні елементи, і продовжує цей процес для знаходження більших частих груп, таких як {Milk, Diaper, Beer}.


              1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
            
import pandas as pd
from itertools import combinations

# Example transaction dataset
transactions = [
    ['Milk', 'Bread'],
    ['Milk', 'Diaper', 'Beer', 'Bread'],
    ['Milk', 'Diaper', 'Beer', 'Cola'],
    ['Diaper', 'Beer'],
    ['Milk', 'Diaper', 'Bread', 'Beer']
]

# Convert transactions to a DataFrame of one-hot encoded items
all_items = sorted(set(item for transaction in transactions for item in transaction))
df = pd.DataFrame([{item: (item in transaction) for item in all_items} for transaction in transactions])

def apriori(df, min_support=0.6):

    def get_support(itemset):
        return (df[list(itemset)].all(axis=1).sum()) / len(df)

    # Step 1: Finding frequent 1-itemsets
    frequent_itemsets = []
    current_level = []
    for item in all_items:
        support = get_support([item])
        if support >= min_support:
            current_level.append(frozenset([item]))
            frequent_itemsets.append((frozenset([item]), support))

    k = 2
    while current_level:
        # Step 2: Candidate generation
        candidates = []
        level_list = list(current_level)
        for i in range(len(level_list)):
            for j in range(i+1, len(level_list)):
                union = level_list[i] | level_list[j]
                if len(union) == k and union not in candidates:
                    # Step 3: Pruning
                    subsets = list(combinations(union, k-1))
                    if all(frozenset(subset) in current_level for subset in subsets):
                        candidates.append(union)

        # Step 4: Support counting
        next_level = []
        for candidate in candidates:
            support = get_support(candidate)
            if support >= min_support:
                next_level.append(candidate)
                frequent_itemsets.append((candidate, support))

        current_level = next_level
        k += 1

    # Format output
    return [(set(itemset), round(support, 2)) for itemset, support in frequent_itemsets]

# Running Apriori and displaying frequent itemsets
frequent_itemsets = apriori(df, min_support=0.6)
for itemset, support in frequent_itemsets:
    print(f"Frequent Itemset: {itemset}, Support: {support}")

Цей код на Python демонструє просту реалізацію алгоритму Apriori для виявлення частих наборів елементів у транзакційних даних. Ось як виконується кожен крок:

Підготовка даних

Транзакції представлені у вигляді списку списків, де кожен підсписок містить товари, придбані разом.
Визначаються всі унікальні товари та сортуються.
Створюється DataFrame з one-hot кодуванням: кожен рядок відповідає транзакції, а кожен стовпець — товару, з True або False, що вказує на наявність чи відсутність.

Кроки алгоритму Apriori

1. Визначення частих 1-елементних наборів

Алгоритм обчислює підтримку для кожного окремого товару (частка транзакцій, що містять цей товар).
Якщо підтримка товару дорівнює або перевищує поріг min_support (тут 0.6), він вважається частим і включається до першого списку частих наборів.

2. Генерація кандидатів

Для наборів довжини k (починаючи з 2) алгоритм генерує нові кандидатні набори шляхом об'єднання частих наборів з попереднього раунду, які мають всі, крім одного, спільні елементи.
Розглядаються лише унікальні комбінації, щоб уникнути дублювання.

3. Обрізання

Перевіряються всі піднабори довжини k-1 для кожного нового кандидата.
Якщо будь-який піднабір не входить до списку частих наборів з попередньої ітерації, кандидат відкидається (обрізається) згідно з принципом Apriori.

4. Підрахунок підтримки

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

5. Ітерація

Кроки 2–4 повторюються, щоразу збільшуючи розмір наборів, доки не буде знайдено нових частих наборів.

Вивід

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

1. Яке з наведеного найкраще описує етап генерації кандидатів в алгоритмі Apriori?

2. Яка основна причина обрізання кандидатних наборів під час роботи алгоритму Apriori?

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

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

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

Запитати АІ

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

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