Поиск ассоциативных правил (Apriori)
- Автор метода
- Rakesh Agrawal & Ramakrishnan Srikant
- Год
- 1994
- Тип
- Unsupervised pattern discovery algorithm
- Семейство
- Pattern mining
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Поиск ассоциативных правил — это метод интеллектуального анализа данных без учителя, который обнаруживает закономерности совместной встречаемости элементов в транзакционных наборах данных.
Формально представленный Agrawal, Imieliński и Swami в 1993 году и усовершенствованный с помощью основополагающего алгоритма Apriori от Agrawal и Srikant в 1994 году, он идентифицирует правила вида X ⇒ Y — означающие, что транзакции, содержащие набор элементов X, также склонны содержать набор элементов Y — количественно определяемые с помощью поддержки, достоверности и подъема.
Интуиция метода
Представьте себе журнал чеков из супермаркета: если тысячи покупателей, покупающих хлеб и масло, также покупают молоко, эта закономерность заслуживает внимания. Поиск ассоциативных правил работает как дотошный библиотекарь, просматривающий каждый чек, подсчитывающий, как часто комбинации товаров появляются вместе, и выявляющий комбинации, превышающие минимальную частоту. Как только найдены частые группы, алгоритм задает вопрос: учитывая, что у вас уже есть эти товары, насколько надежно это предсказывает следующий товар? Эта двухэтапная логика «частота, затем достоверность» лежит в основе Apriori.
История
Фундаментальная работа Agrawal, Imieliński и Swami (1993) определила проблему ассоциативных правил в контексте данных о транзакциях супермаркетов. Работа Agrawal и Srikant 1994 года в VLDB представила алгоритм Apriori и его эффективную стратегию отсечения, сделав крупномасштабный поиск практичным. Последующие работы породили FP-Growth (Han et al., 2000), который полностью избегает генерации кандидатов, и ECLAT, который осуществляет поиск в вертикальном формате данных — создав богатое семейство алгоритмов, ныне центральное для учебных программ по интеллектуальному анализу данных.
Когда применять
Поиск ассоциативных правил подходит для больших транзакционных наборов данных, где цель состоит в обнаружении закономерностей совместной встречаемости без предопределенной целевой переменной. Он предполагает, что элементы являются бинарными (присутствуют/отсутствуют) в каждой транзакции. Он подходит для анализа рыночной корзины, рекомендательных систем, анализа веб-потоков кликов и обнаружения сопутствующих диагнозов в медицине. Он не подходит для непрерывных или порядковых данных, если они не были предварительно дискретизированы, для наборов данных с очень высокой размерностью (экспоненциальное пространство кандидатов) или когда требуется причинно-следственный, а не ассоциативный вывод. Альтернативы включают FP-Growth для более быстрого перечисления частых наборов элементов и поиск последовательностей, когда важен временной порядок.
Ограничения и замечания
- Экспоненциальное пространство кандидатов: количество правил растет комбинаторно с числом различных элементов.
- Структура поддержки-достоверности может давать вводящие в заблуждение правила, когда базовые частоты элементов сильно различаются (требуется корректировка подъемом).
- Бинарная модель транзакций требует дискретизации непрерывных переменных, что приводит к потере информации.
- Высокие минимальные пороги поддержки упускают редкие, но ценные правила; низкие пороги генерируют тысячи тривиальных правил.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Полностью без учителя: не требуется размеченных данных или предопределенной цели.
- Интерпретируемый вывод: правила представляют собой читаемые человеком утверждения «если-то» с количественно определенными поддержкой и достоверностью.
- Масштабируемость за счет отсечения Apriori; вариант FP-Growth полностью исключает повторные сканирования базы данных.
- Независимость от предметной области: применяется в розничной торговле, здравоохранении, веб-аналитике и биоинформатике.
Применение
- Розничная торговля: размещение товаров и рекомендации по перекрестным продажам на основе журналов транзакций точки продажи.
- Здравоохранение: анализ совместной встречаемости диагнозов, процедур или лекарств в электронных медицинских картах.
- Веб-аналитика: обнаружение закономерностей потоков кликов для рекомендаций страниц и оптимизации навигации.
- Биоинформатика: идентификация совместно экспрессируемых наборов генов и мотивов взаимодействия белков.
- Кибербезопасность: обнаружение коррелированных сетевых событий, указывающих на закономерности вторжений.
Как это работает
Как это работает
Алгоритм сканирует базу данных транзакций D, чтобы подсчитать, как часто встречается каждый набор элементов X. Набор элементов объявляется частым — и помещается в L_k — только тогда, когда его поддержка (доля транзакций, содержащих его) достигает или превышает заданный пользователем минимальный порог поддержки σ_min. Процесс начинается с отдельных элементов (k=1) и итеративно строит более крупные наборы кандидатов.
Формула
L_k = \{ X \subseteq I \mid |X| = k,\; \text{support}(X) = \frac{|\{t \in D : X \subseteq t\}|}{|D|} \geq \sigma_{\min} \}Свойство антимонотонности поддержки гласит, что любой поднабор частого набора элементов сам должен быть частым. Apriori использует это, отбрасывая каждый кандидатский k-элементный набор, поднаборы которого не все находятся в проверенном частом наборе L_{k-1}. Это значительно сокращает пространство поиска, избегая дорогостоящих сканирований базы данных для наборов элементов, которые заведомо не могут быть частыми.
Формула
\forall X \in C_k,\; \forall Y \subset X,\; |Y| = k-1 : Y \notin L_{k-1} \Rightarrow X \notin L_kИз каждого частого набора элементов X ∪ Y алгоритм генерирует правила X ⇒ Y, где X и Y являются непересекающимися поднаборами. Правило сохраняется только тогда, когда его достоверность — условная вероятность Y при условии X, вычисляемая как поддержка(X ∪ Y) / поддержка(X) — достигает или превышает минимальный порог достоверности γ_min. Этот шаг преобразует сырые совместные встречаемости в направленные предсказательные утверждения.
Формула
X \Rightarrow Y \text{ where } X \cap Y = \emptyset,\quad \text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \gamma_{\min}Сохраненные правила ранжируются и фильтруются по подъему, который измеряет, насколько более вероятно появление Y с X, чем случайно. Подъем > 1 указывает на положительную корреляцию сверх независимости; подъем = 1 указывает на независимость; подъем < 1 указывает на отрицательную корреляцию. Дополнительные меры интересности, такие как убедительность (conviction) и рычаг (leverage), могут далее уточнить набор правил для практического развертывания.
Формула
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)} = \frac{\text{support}(X \cup Y)}{\text{support}(X) \cdot \text{support}(Y)}Частые ошибки
- Установка слишком низкого минимального порога поддержки заваливает аналитика ложными правилами; выбор порога требует знания предметной области или перекрестной проверки.
- Смешение статистической ассоциации с причинно-следственной связью: высокий подъем не подразумевает, что X вызывает Y.
- Игнорирование распределения частот элементов: распространенные элементы доминируют в правилах и вытесняют значимые ассоциации редких элементов.
- Рассмотрение только достоверности как метрики качества; правило с высокой достоверностью, но низким подъемом, может работать не лучше, чем случайное угадывание.
Часто задаваемые вопросы
В чем разница между поддержкой, достоверностью и подъемом?
Поддержка измеряет, как часто набор элементов встречается в наборе данных в целом. Достоверность измеряет условную вероятность следствия при условии антецедента. Подъем нормализует достоверность по маргинальной частоте следствия, показывая, превышает ли совместная встречаемость то, что ожидалось бы при независимости. Все три метрики необходимы вместе для надежной оценки правил.
Как алгоритм Apriori снижает вычислительные затраты?
Apriori использует свойство антимонотонности: если набор элементов не является частым, то все его супернаборы также должны быть нечастыми. Отбрасывая любого кандидата, поднаборы которого не были проверены как частые, алгоритм отсекает огромные части пространства поиска перед подсчетом, значительно сокращая количество проходов по базе данных, необходимых по сравнению с полным перебором.
Когда следует использовать FP-Growth вместо Apriori?
FP-Growth предпочтительнее, когда набор данных велик, а минимальный порог поддержки низок, поскольку он сжимает базу данных транзакций в компактную структуру FP-дерева и ищет закономерности непосредственно, не генерируя явных кандидатов. Это исключает повторные полные сканирования базы данных, делая его значительно быстрее Apriori на плотных наборах данных с большим количеством частых наборов элементов.
Похожие методы
Источники
Agrawal, R., Imieliński, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. ACM SIGMOD, 207–216.
Открыть ссылку DOIСкопировано.Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th VLDB Conference, 487–499.
Открыть ссылку на публикациюСкопировано.