Apriori

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

История

Алгоритм Apriori был впервые представлен в 1994 году в статье «Fast Algorithms for Mining Association Rules» (Быстрые алгоритмы для поиска ассоциативных правил), опубликованной на конференции VLDB. Авторы, Рамеш Агравал и Рамакришнан Шрикант, работали в исследовательском центре IBM Almaden Research Center. Разработка алгоритма была мотивирована необходимостью анализа больших объёмов транзакционных данных, генерируемых розничной торговлей, в частности, для выявления закономерностей в покупках клиентов.

В последующие годы алгоритм Apriori стал основой для множества последующих исследований и модификаций. Он был включён в стандартные библиотеки анализа данных многих языков программирования, включая Python (библиотека mlxtend), R (пакет arules) и Apache Spark (MLlib). Несмотря на появление более эффективных алгоритмов (например, FP-Growth, Eclat), Apriori остаётся популярным учебным и практическим инструментом благодаря своей простоте и наглядности.

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

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

• Транзакция — это запись о наборе предметов (товаров, услуг, действий), совершённых в рамках одного события (например, покупка в магазине, посещение веб-страницы).
• Набор предметов (itemset) — это множество из одного или нескольких предметов, встречающихся в транзакциях. Например, {молоко, хлеб}.
• Поддержка (support) — мера, показывающая, как часто данный набор предметов встречается в базе данных транзакций. Вычисляется как отношение количества транзакций, содержащих данный набор, к общему количеству транзакций.
• Достоверность (confidence) — мера, показывающая, насколько часто правило является истинным. Для правила X → Y достоверность вычисляется как отношение поддержки набора {X, Y} к поддержке набора {X}.
• Лифт (lift) — мера, показывающая, насколько вероятнее появление предмета Y при условии появления предмета X, чем без этого условия. Значение лифта больше 1 указывает на положительную корреляцию, меньше 1 — на отрицательную.
• Минимальная поддержка (min_support) — пороговое значение, задаваемое пользователем. Наборы предметов, поддержка которых ниже этого порога, считаются нечастыми и отбрасываются.
• Минимальная достоверность (min_confidence) — пороговое значение для фильтрации сгенерированных ассоциативных правил.

Принцип работы

Алгоритм Apriori основан на априорном свойстве (apriori property): любое подмножество частого набора предметов также является частым. И наоборот, если набор предметов является нечастым (его поддержка ниже минимальной), то все его надмножества также будут нечастыми. Это свойство позволяет алгоритму значительно сократить пространство поиска, отбрасывая заведомо неперспективные комбинации.

Работа алгоритма состоит из двух основных этапов:

Этап 1: Поиск частых наборов предметов

1. Генерация кандидатов (C1): Алгоритм сканирует базу данных и подсчитывает поддержку для каждого отдельного предмета. Все предметы, чья поддержка ниже минимальной, отбрасываются. Оставшиеся предметы образуют множество частых наборов первого уровня (L1).
2. Итеративный процесс: Для k = 2, 3, ... до тех пор, пока не будет пустого множества:

• Генерация кандидатов (Ck): Из множества частых наборов предыдущего уровня (L_{k-1}) генерируются потенциальные кандидаты размера k. Для этого используются комбинации, в которых первые (k-2) элемента совпадают.
• Подсчёт поддержки: Алгоритм снова сканирует базу данных и подсчитывает поддержку для каждого кандидата из Ck.
• Отсев: Кандидаты, чья поддержка ниже минимальной, удаляются. Оставшиеся образуют множество частых наборов Lk.

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

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

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

Рассмотрим простую базу данных транзакций из 5 записей:

• Минимальная поддержка: 0.4 (то есть набор должен встречаться как минимум в 2 из 5 транзакций).

Этап 1:

• C1: {A} (3), {B} (4), {C} (4), {D} (1), {E} (1). Отбрасываем D и E. L1: {A}, {B}, {C}.
• C2: {A, B} (2), {A, C} (2), {B, C} (3). Все имеют поддержку >= 2. L2: {A, B}, {A, C}, {B, C}.
• C3: {A, B, C} (1). Поддержка = 1, что ниже 2. L3: пусто. Поиск завершён.

Этап 2: Из частых наборов (например, {A, B}) генерируются правила:

• A → B: поддержка {A, B} = 2/5 = 0.4, поддержка {A} = 3/5 = 0.6. Достоверность = 0.4 / 0.6 = 0.67.
• B → A: поддержка {A, B} = 0.4, поддержка {B} = 4/5 = 0.8. Достоверность = 0.4 / 0.8 = 0.5.

Преимущества и недостатки

Преимущества

• Простота и понятность: Алгоритм легко реализовать и интерпретировать.
• Надёжность: Гарантирует нахождение всех частых наборов предметов, удовлетворяющих заданному порогу поддержки.
• Широкая применимость: Используется в различных областях, от розничной торговли до биоинформатики.

Недостатки

• Высокая вычислительная сложность: Алгоритм требует многократного сканирования базы данных, что делает его медленным на больших наборах данных.
• Проблема с большим количеством кандидатов: На ранних итерациях может генерироваться огромное количество кандидатов, особенно если минимальная поддержка установлена низко.
• Чувствительность к порогам: Результат сильно зависит от выбора минимальной поддержки и достоверности. Неправильный выбор может привести к большому количеству тривиальных или ложных правил.

Применение

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

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

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

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

• FP-Growth (Frequent Pattern Growth): Этот алгоритм строит сжатое представление базы данных в виде дерева (FP-tree) и не требует многократного сканирования. Он значительно быстрее Apriori на больших наборах данных.
• Eclat (Equivalence Class Clustering and bottom-up Lattice Traversal): Использует вертикальный формат данных (список идентификаторов транзакций для каждого предмета) и пересечение множеств для поиска частых наборов.
• AprioriTID: Модификация Apriori, которая на поздних итерациях использует не исходную базу данных, а сжатое представление транзакций.

Интересные факты

• Название алгоритма происходит от латинского слова «a priori» (априори), что отражает использование априорного знания о том, что подмножества частых наборов также являются частыми.
• Классический пример из учебников — правило «пиво → подгузники», которое, по легенде, было обнаружено при анализе покупок в американских супермаркетах. Однако достоверных подтверждений этого факта не существует; скорее всего, это вымышленный пример, иллюстрирующий принцип работы алгоритма.
• Алгоритм Apriori является одним из первых и наиболее цитируемых алгоритмов в области Data Mining. Его описание включено практически во все учебники по анализу данных.

Источники

1. Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th VLDB Conference, 487-499.
2. Han, J., Kamber, M., & Pei, J. (2011). Data Mining: Concepts and Techniques (3rd ed.). Morgan Kaufmann.
3. Tan, P. N., Steinbach, M., & Kumar, V. (2005). Introduction to Data Mining. Addison-Wesley.
4. Witten, I. H., Frank, E., & Hall, M. A. (2011). Data Mining: Practical Machine Learning Tools and Techniques (3rd ed.). Morgan Kaufmann.