Вивчайте Побудова Дерев Частих Шаблонів за Допомогою Алгоритму FP-Growth | Високопродуктивний пошук правил та оптимізація масштабування

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

Огляд FP-Growth

FP-Growth — високопродуктивний алгоритм, розроблений для пошуку частих наборів елементів у великих транзакційних наборах даних. На відміну від Apriori, який генерує кандидатні набори елементів і багаторазово сканує базу даних, FP-Growth будує компактну структуру даних під назвою FP-Tree (дерево частих шаблонів), що дозволяє знаходити часті шаблони без генерації кандидатів. Це забезпечує значне підвищення швидкості та економію пам'яті, особливо для наборів даних із великою кількістю частих шаблонів.

Структура дерева

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

Зв'язування вузлів

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

Пошук шаблонів

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

Приклад: Покрокове побудування FP-дерева

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

Припустимо, у вас є такі транзакції:

- Транзакція 1: A, B, D;
- Транзакція 2: B, C, E;
- Транзакція 3: A, B, C, E;
- Транзакція 4: B, E.

Крок 1: Сканування бази даних і сортування за частотою

Спочатку алгоритм читає весь набір даних, щоб підрахувати, скільки разів кожен окремий елемент зустрічається. Будь-який елемент, що не досягає мінімального порогу підтримки, відкидається. Далі встановлюється глобальний порядок сортування від найвищої до найнижчої частоти.

Глобальна кількість елементів:

B зустрічається 4 рази

E зустрічається 3 рази

A зустрічається 2 рази

C зустрічається 2 рази

D зустрічається 1 раз (Відкидається, оскільки менше мінімальної підтримки 2)

Фінальне правило впорядкування: Тепер кожна транзакція буде відфільтрована та впорядкована відповідно до цього порядку спадання частоти:

$\mathbf{B} \longrightarrow \mathbf{E} \longrightarrow \mathbf{A} \longrightarrow \mathbf{C}$

Крок 2: Перевпорядкування кожної транзакції

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

- Транзакція 1: A, B, D стає B, A
- Транзакція 2: B, C, E стає B, E, C
- Транзакція 3: A, B, C, E стає B, E, A, C
- Транзакція 4: B, E стає B, E

Крок 3: Вставка шляхів у FP-дерево

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

Вставка транзакції 1 {B, A}: дерево створює нову гілку прямо вниз від кореня.

Вставка транзакції 2 {B, E, C}: алгоритм починає з кореня і перевіряє перший елемент, B. Оскільки B вже існує як нащадок кореня, шлях перетинається! Алгоритм переходить до B і збільшує його лічильник до 2. Наступний елемент — E. Оскільки у B ще немає нащадка з ім’ям E, тут дерево розгалужується і створює нову підгілку для E, а потім для C.

Вставка транзакції 3 {B, E, A, C}: починаючи з кореня, шлях проходить через B (лічильник збільшується до 3), потім переходить до існуючого вузла E (лічильник збільшується до 2). Наступний елемент — A. Оскільки у E немає нащадка з ім’ям A, дерево створює нову гілку під E для (A:1) -> (C:1).

Вставка транзакції 4 {B, E}: алгоритм рухається найпопулярнішим префіксним шляхом: B збільшується до 4, E збільшується до 3. Транзакція закінчується тут, тому нові вузли не додаються.

(Null Root) | (B: 4) / \ (A: 1) (E: 3) / \ (C: 1) (A: 1) | (C: 1)


              12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
            
transactions = [
    ['A', 'B', 'D'],
    ['B', 'C', 'E'],
    ['A', 'B', 'C', 'E'],
    ['B', 'E']
]

# Step 1: Counting item frequency
from collections import defaultdict, Counter

item_counts = Counter()
for transaction in transactions:
    item_counts.update(transaction)

# Step 2: Removing infrequent items
min_support = 2
freq_items = {item for item, count in item_counts.items() if count >= min_support}

# Step 3: Sorting items in each transaction by frequency
def sort_transaction(transaction):
    return sorted([item for item in transaction if item in freq_items],
                  key=lambda item: (-item_counts[item], item))

sorted_transactions = [sort_transaction(t) for t in transactions]

# Step 4: Defining FP-Tree node class
class FPTreeNode:
    def __init__(self, item, count, parent):
        self.item = item
        self.count = count
        self.parent = parent
        self.children = {}
        self.link = None  # Node link for header table

# Step 5: Building the FP-Tree and header table
def build_fp_tree(transactions):
    root = FPTreeNode(None, 1, None)
    header_table = defaultdict(list)

    for transaction in transactions:
        current = root
        for item in transaction:
            if item not in current.children:
                current.children[item] = FPTreeNode(item, 1, current)
                header_table[item].append(current.children[item])
            else:
                current.children[item].count += 1
            current = current.children[item]
    # Linking nodes in header table
    for item, nodes in header_table.items():
        for i in range(len(nodes) - 1):
            nodes[i].link = nodes[i + 1]
    return root, header_table

fp_root, header_table = build_fp_tree(sorted_transactions)

# Step 6: Printing the FP-Tree
def print_tree(node, indent=0):
    if node.item is not None:
        print('  ' * indent + f"{node.item}:{node.count}")
    for child in node.children.values():
        print_tree(child, indent + 1)

print_tree(fp_root)

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

Підрахунок частот елементів:
- Код використовує клас Counter з модуля collections для підрахунку, скільки разів кожен елемент зустрічається у всіх транзакціях;
- Це допомагає визначити, які елементи є достатньо частими, щоб бути включеними у дерево.
Видалення нечастих елементів:
- Елементи, які не відповідають мінімальному порогу підтримки, відфільтровуються;
- Множина freq_items містить лише ті елементи, які зустрічаються не менше разів, ніж визначено у min_support.
Сортування транзакцій за частотою:
- Кожна транзакція фільтрується, щоб залишити лише часті елементи;
- Елементи потім впорядковуються у спадному порядку їх глобальної частоти (та за алфавітом для розв'язання однакових частот);
- Сортування максимізує спільне використання префіксів у FP-дереві, роблячи дерево компактнішим.
Опис класу вузла FP-дерева:
- Клас FPTreeNode представляє кожен вузол у дереві;
- Кожен вузол зберігає назву елемента, лічильник, вказівник на батьківський вузол, словник нащадків та посилання на наступний вузол з тим самим ім’ям елемента (для обходу через заголовкову таблицю).
Побудова FP-дерева та заголовкової таблиці:
- Функція build_fp_tree створює дерево шляхом вставки кожної впорядкованої транзакції;
- Починаючи з кореня, для кожного елемента у транзакції функція перевіряє, чи існує дочірній вузол — якщо ні, створює його і додає у заголовкову таблицю;
- Якщо вузол вже існує, його лічильник збільшується;
- Після побудови дерева код з’єднує всі вузли з однаковим ім’ям елемента через атрибут link, що дозволяє швидко обходити дерево через заголовкову таблицю.
Виведення структури FP-дерева:
- Функція print_tree відображає дерево, рекурсивно виводячи кожен вузол та його лічильник з відступами для візуалізації структури дерева;
- Такий вивід допомагає побачити, як транзакції стискаються у спільні шляхи всередині FP-дерева.

1. Яка з наведених переваг є ключовою для FP-Growth порівняно з алгоритмом Apriori?

2. Яка структура вузла FP-Tree?

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

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

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

Запитати АІ

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

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