Читать книгу Нейросети. Основы онлайн

1. Создание начальных наборов: На первом этапе алгоритм находит все частые одиночные элементы, которые удовлетворяют заданному порогу поддержки (минимальное количество раз, которое элемент должен появиться в базе данных, чтобы считаться частым).

2. Генерация кандидатов: На каждом последующем этапе алгоритм генерирует наборы кандидатов, увеличивая размер наборов на один элемент. Это делается путем объединения частых наборов элементов из предыдущего шага.

3. Фильтрация: Каждый набор кандидатов проверяется на частоту в базе данных. Наборы, удовлетворяющие порогу поддержки, считаются частыми и проходят на следующий этап.

4. Повторение: Процесс продолжается до тех пор, пока не будут найдены все частые наборы элементов.

5. Создание ассоциативных правил: После нахождения всех частых наборов элементов алгоритм генерирует ассоциативные правила, которые представляют собой зависимости между элементами.

Основным недостатком алгоритма Apriori является необходимость многократного прохода по базе данных для генерации и проверки кандидатов, что делает его менее эффективным для больших наборов данных.

FP-Growth (Frequent Pattern Growth)

FP-Growth (Frequent Pattern Growth) – это более эффективный алгоритм для выявления частых наборов элементов и создания ассоциативных правил по сравнению с Apriori. Основная идея FP-Growth заключается в использовании структуры дерева (FP-дерево) для компактного представления набора частых элементов и быстрого обнаружения ассоциативных правил без необходимости генерировать кандидатов.

FP-Growth работает следующим образом:

1. Построение FP-дерева: На первом этапе алгоритм строит FP-дерево. Для этого сначала проводится один проход по базе данных для определения частоты всех элементов. Затем база данных повторно проходит для построения дерева, где каждая транзакция добавляется в дерево, обновляя счетчики частоты.

2. Разделение дерева: FP-дерево делится на поддеревья для каждого частого элемента. Этот процесс продолжается рекурсивно, пока не будут найдены все частые наборы элементов.