Алгоритм Apriori

Алгоритм Apriori — это классический алгоритм машинного обучения, предназначенный для поиска ассоциативных правил в больших наборах транзакционных данных. Он относится к методам анализа рыночной корзины (market basket analysis) и позволяет выявлять устойчивые закономерности, такие как «если покупатель приобрёл товар A, то с высокой вероятностью он купит и товар B». Алгоритм был предложен Ракешем Агравалом и Рамакришнаном Шрикантом в 1994 году и основан на принципе антимонотонности (или свойстве Apriori): если подмножество элементов является частым, то все его подмножества также являются частыми, и наоборот — если подмножество нечастое, то его надмножества не могут быть частыми.

История

Разработка алгоритма Apriori связана с ростом объёмов данных в розничной торговле и необходимостью автоматизированного выявления скрытых закономерностей. В 1993 году Ракеш Агравал, Томаш Имелинский и Арун Свами опубликовали работу «Mining Association Rules between Sets of Items in Large Databases», в которой впервые формализовали задачу поиска ассоциативных правил. В 1994 году Агравал и Шрикант представили сам алгоритм Apriori в статье «Fast Algorithms for Mining Association Rules in Large Databases».

Алгоритм быстро стал стандартом де-факто в области анализа данных благодаря своей простоте и эффективности для небольших и средних наборов данных. Впоследствии были разработаны его многочисленные модификации, направленные на повышение производительности: AprioriTID, AprioriHybrid, а также более современные алгоритмы, такие как FP-Growth и Eclat, которые обходят некоторые ограничения Apriori.

Основные понятия

Для понимания работы алгоритма необходимо определить несколько ключевых терминов:

• Транзакция — это набор элементов (items), приобретённых или совершённых вместе. Например, чек в магазине, содержащий хлеб, молоко и масло.
• Набор элементов (itemset) — множество элементов, рассматриваемое как единое целое. Набор, состоящий из k элементов, называется k-элементным набором.
• Поддержка (support) — доля транзакций, содержащих данный набор элементов, от общего числа транзакций. Формально: Support(X) = (количество транзакций, содержащих X) / (общее количество транзакций).
• Достоверность (confidence) — условная вероятность того, что транзакция, содержащая набор X, также содержит набор Y. Вычисляется как Confidence(X → Y) = Support(X ∪ Y) / Support(X).
• Лифт (lift) — мера, показывающая, насколько вероятность появления Y в транзакциях с X выше, чем вероятность появления Y в целом. Lift(X → Y) = Confidence(X → Y) / Support(Y). Если лифт больше 1, правило положительно коррелирует; если меньше 1 — отрицательно.
• Частый набор элементов — набор, чья поддержка не ниже заданного пользователем порога минимальной поддержки (min_sup).
• Ассоциативное правило — импликация вида X → Y, где X и Y — непересекающиеся наборы элементов. Правило считается интересным, если его достоверность не ниже порога минимальной достоверности (min_conf).

Принцип работы алгоритма

Алгоритм Apriori состоит из двух основных этапов: генерация частых наборов элементов и построение ассоциативных правил.

Этап 1: Генерация частых наборов элементов

Алгоритм использует итеративный подход, начиная с одноэлементных наборов (1-элементных) и постепенно увеличивая размерность.

1. Инициализация: Сканируется база данных транзакций, подсчитывается поддержка каждого отдельного элемента. Элементы, чья поддержка ниже min_sup, отбрасываются. Оставшиеся образуют множество частых 1-элементных наборов L1.
2. Генерация кандидатов: На основе L1 генерируются кандидаты в 2-элементные наборы C2. Для этого используется операция соединения: каждый элемент из L1 соединяется с каждым другим элементом, образуя пары.
3. Подсчёт поддержки: Сканируется база данных, для каждого кандидата из C2 подсчитывается его поддержка. Кандидаты с поддержкой ниже min_sup удаляются. Оставшиеся образуют L2.
4. Повторение: Для генерации Ck (k ≥ 3) используется свойство Apriori: из Lk-1 берутся все наборы, которые можно соединить так, чтобы их первые k-2 элементов совпадали. Затем применяется шаг отсечения (pruning): из Ck удаляются все кандидаты, у которых хотя бы одно (k-1)-элементное подмножество не входит в Lk-1. Это резко сокращает количество кандидатов.
5. Остановка: Процесс повторяется, пока не будет получено пустое множество Lk+1.

Этап 2: Построение ассоциативных правил

Из каждого частого набора элементов X генерируются все возможные правила вида Y → (X \ Y), где Y — непустое подмножество X. Для каждого правила вычисляется достоверность. Правила, чья достоверность ниже min_conf, отбрасываются. Оставшиеся правила считаются значимыми ассоциативными правилами.

Пример работы

Рассмотрим простой пример с четырьмя транзакциями:

Пусть min_sup = 50% (то есть 2 транзакции).

Шаг 1: Подсчёт поддержки 1-элементных наборов:

• A: 3 (75%) — частый
• B: 2 (50%) — частый
• C: 2 (50%) — частый
• D: 1 (25%) — нечастый
• E: 1 (25%) — нечастый

L1 = {A, B, C}

Шаг 2: Генерация C2 = {AB, AC, BC}. Подсчёт поддержки:

• AB: 1 (25%) — нечастый
• AC: 2 (50%) — частый
• BC: 1 (25%) — нечастый

L2 = {AC}

Шаг 3: Генерация C3 = {ABC} (из L2). Проверка подмножеств: AB, AC, BC. AB и BC не входят в L2, поэтому кандидат отбрасывается на этапе отсечения. L3 = ∅. Алгоритм завершается.

Построение правил: Из частого набора {A, C} можно получить правило A → C. Его достоверность: Support(AC)/Support(A) = 2/3 ≈ 66.7%. Если min_conf = 60%, правило принимается.

Достоинства и недостатки

Достоинства

• Простота реализации: Алгоритм легко понять и запрограммировать.
• Интуитивная интерпретация: Результаты (ассоциативные правила) легко интерпретируются человеком.
• Гарантия полноты: При правильном выборе порогов алгоритм находит все правила, удовлетворяющие заданным условиям.

Недостатки

• Высокая вычислительная сложность: Для больших наборов данных количество кандидатов может быть огромным, особенно на ранних итерациях. Сложность составляет O(2^n), где n — число уникальных элементов.
• Многократное сканирование базы данных: На каждой итерации требуется полное сканирование транзакций, что замедляет работу при больших объёмах данных.
• Чувствительность к порогам: Слишком низкий min_sup приводит к генерации огромного числа правил, многие из которых могут быть ложными или неинтересными. Слишком высокий — к потере значимых закономерностей.
• Проблема редких элементов: Алгоритм плохо работает с редкими, но ценными элементами (например, покупка дорогих товаров).

Применение

Алгоритм Apriori и его модификации находят широкое применение в различных областях:

• Розничная торговля: Анализ покупательских корзин для оптимизации выкладки товаров, формирования рекомендаций и планирования акций (например, правило «пиво и подгузники»).
• Медицина: Выявление сочетаний симптомов, лекарств или диагнозов, которые часто встречаются вместе.
• Биоинформатика: Поиск закономерностей в последовательностях ДНК или белков.
• Веб-аналитика: Анализ последовательностей посещения страниц для улучшения навигации сайта.
• Телекоммуникации: Обнаружение аномальных паттернов использования услуг (например, для борьбы с мошенничеством).

Модификации и альтернативы

Из-за недостатков Apriori были разработаны более эффективные алгоритмы:

• FP-Growth (Frequent Pattern Growth): Строит сжатое представление базы данных в виде FP-дерева, что позволяет избежать генерации кандидатов и многократного сканирования.
• Eclat: Использует вертикальный формат данных (списки идентификаторов транзакций для каждого элемента) и операции пересечения множеств.
• AprioriTID: Модификация, при которой на каждой итерации вместо исходной базы данных используется уменьшенное представление транзакций.
• AprioriHybrid: Комбинирует Apriori и AprioriTID для оптимизации производительности.

Критика

Основная критика алгоритма Apriori связана с его масштабируемостью. При работе с большими наборами данных (миллионы транзакций, тысячи уникальных элементов) время выполнения становится неприемлемо большим. Кроме того, алгоритм не учитывает порядок элементов в транзакции (например, последовательность покупок во времени). Также существует проблема «ложных корреляций»: правила с высокой достоверностью могут быть статистически незначимыми, если не учитывать объём выборки. Для решения этой проблемы используются дополнительные метрики, такие как лифт, левередж или убеждённость (conviction).

Источники

1. Agrawal, R., Imieliński, T., & Swami, A. (1993). Mining Association Rules between Sets of Items in Large Databases. Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data.
2. Agrawal, R., & Srikant, R. (1994). Fast Algorithms for Mining Association Rules in Large Databases. Proceedings of the 20th International Conference on Very Large Data Bases (VLDB).
3. Han, J., Pei, J., & Kamber, M. (2011). Data Mining: Concepts and Techniques (3rd ed.). Morgan Kaufmann.
4. Tan, P.-N., Steinbach, M., & Kumar, V. (2005). Introduction to Data Mining. Addison-Wesley.
5. Witten, I. H., Frank, E., & Hall, M. A. (2011). Data Mining: Practical Machine Learning Tools and Techniques (3rd ed.). Morgan Kaufmann.