Skip to content
Назад к результатам поиска

Алгоритм Apriori

Автор метода
Agrawal, R. & Srikant, R.
Год
1994
Тип
Frequent itemset and association rule mining algorithm
Семейство
Machine learning

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Алгоритм Apriori, представленный Агравалом и Шрикантом в 1994 году, является основополагающим методом для обнаружения частых наборов элементов и правил ассоциации в транзакционных базах данных.

Он использует поиск в ширину, по уровням, управляемый антимонотонным свойством поддержки, для эффективного перечисления всех комбинаций элементов, которые совместно встречаются выше установленного пользователем минимального порога, а затем извлекает интерпретируемые правила «если-то» из этих закономерностей.

Интуиция метода

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

История

Ракеш Агравал и Рамакришнан Шрикант представили алгоритм Apriori на конференции VLDB в 1994 году, развивая формулировку проблемы поиска правил ассоциации Агравала и др. 1993 года. Название отражает его ключевую идею: использование предварительных знаний о частых (k)-наборах элементов для отсечения кандидатов на уровне k+1. Он стал каноническим эталоном, по отношению к которому измеряются все последующие алгоритмы поиска частых наборов элементов — включая FP-Growth (2000) и Eclat — и остается стандартной главой в учебниках по интеллектуальному анализу данных и машинному обучению.

Когда применять

Используйте Apriori, когда цель состоит в обнаружении закономерностей совместного появления или правил «если-то» в транзакционных данных или данных о наличии бинарных элементов — анализ рыночной корзины, совместное подтверждение элементов опроса, совместное появление симптомов при медицинских диагнозах или ассоциация терминов в тексте. Он подходит для наборов данных умеренного размера, где приоритетом является прозрачность и интерпретируемость выходных правил. Не используйте Apriori, когда база данных транзакций очень велика (миллионы строк с широким каталогом элементов), поскольку повторные полные сканирования базы данных делают его медленным по сравнению с FP-Growth; в таких случаях предпочтительнее FP-Growth. Он также неприменим для непрерывных числовых данных без предварительной дискретизации и не моделирует направленность или причинно-следственную связь.

Ограничения и замечания

  • Повторные полные сканирования базы данных делают его медленным на больших наборах данных — FP-Growth часто предпочтительнее при масштабировании.
  • Снижение порога поддержки может привести к экспоненциальному количеству кандидатских наборов элементов и правил, затрудняя интерпретацию.
  • Не улавливает временной порядок, направленность или причинно-следственные связи между элементами.
  • Результаты чувствительны к выбору порогов поддержки и достоверности, которые требуют знаний предметной области или систематической настройки.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Генерирует полностью интерпретируемые правила «если-то» с количественно определенными поддержкой, достоверностью и подъемом.
  • Свойство антимонотонного отсечения делает иначе экспоненциальный поиск управляемым.
  • Не требует предварительной разметки данных; полностью неконтролируемый.
  • Параметры порогов (поддержка, достоверность) дают аналитику прямой контроль над гранулярностью правил.
  • Выходные правила действенны и могут быть доведены до сведения нетехнических заинтересованных сторон без алгоритмического бэкграунда.
  • Фундаментальный, широко цитируемый и реализованный практически во всех основных библиотеках интеллектуального анализа данных.

Применение

  • Анализ рыночной корзины: обнаружение того, какие продукты часто покупаются вместе, для определения расположения на полках и проведения рекламных акций.
  • Медицинская информатика: выявление совместно встречающихся симптомов, диагнозов или назначений лекарств в записях пациентов.
  • Анализ веб-использования: поиск страниц или функций, которые пользователи склонны посещать или активировать вместе.
  • Анализ опросов и анкет: выявление того, какие пункты или ответы по шкале систематически совместно подтверждаются.
  • Начальная загрузка рекомендательных систем: генерация кандидатских ассоциаций элементов перед развертыванием коллаборативной фильтрации.
  • Обнаружение мошенничества: выявление необычных закономерностей совместного появления в журналах транзакций, которые отклоняются от нормальных корзин.

Как это работает

Как это работает

1

Аналитик выбирает два порога перед запуском алгоритма: минимальная поддержка (доля транзакций, которые должны содержать данный набор элементов, чтобы он считался частым) и минимальная достоверность (условная вероятность, необходимая для сохранения правила «если-то»). Эти два значения контролируют объем и специфичность вывода и должны быть откалиброваны на основе знаний о предметной области или разведочных запусков.

2

Алгоритм выполняет один полный проход по базе данных транзакций для подсчета частоты появления каждого отдельного элемента. Сохраняются только те элементы, поддержка которых соответствует минимальному порогу поддержки или превышает его; остальные отбрасываются. Этот набор частых одиночных элементов формирует первый уровень кандидатов.

Формула
\text{support}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|}
3

Частые наборы элементов, найденные на уровне k, объединяются попарно для формирования кандидатских наборов элементов размера k+1. Объединяются только пары, имеющие одинаковые первые k-1 элементов — это правило сохраняет компактность набора кандидатов. Новый проход по базе данных подсчитывает поддержку каждого кандидата.

4

Перед подсчетом каждый кандидат размера k+1 проверяется на соответствие всем его (k)-подмножествам. Если какое-либо подмножество было нечастым на предыдущем уровне, кандидат немедленно отбрасывается без чтения данных, используя антимонотонное свойство для снижения вычислительной нагрузки. Выжившие после этого этапа отсечения формируют следующий уровень частых наборов элементов.

5

Из каждого частого набора элементов размером два или более генерируются все возможные правила «если-то» путем разбиения элементов на антецедент и консеквент. Каждое правило оценивается по достоверности — доле транзакций с антецедентом, которые также содержат консеквент. Правила ниже минимальной достоверности отбрасываются.

Формула
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)}
6

Выжившие правила ранжируются по подъему (lift), который сравнивает наблюдаемую достоверность с базовой частотой консеквента. Подъем выше 1 указывает на то, что антецедент и консеквент совместно встречаются чаще, чем случайно; подъем, близкий к 1, указывает на независимость; подъем ниже 1 указывает на отрицательную ассоциацию. Правила с наибольшим подъемом являются наиболее действенными открытиями.

Формула
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)}

Частые ошибки

  • Установка минимальной поддержки слишком низкой приводит к получению тысяч низкокачественных правил без фильтрации по подъему.
  • Интерпретация высокой достоверности как причинно-следственной связи, а не совместного появления — правило с высокой достоверностью, но подъемом, близким к 1, тривиально.
  • Применение Apriori к непрерывным признакам без предварительной дискретизации, что раздувает пространство элементов и ухудшает результаты.
  • Предоставление правил без проверки того, достаточно ли вели выборки наборов элементов для доверия оценкам поддержки.
  • Пренебрежение удалением неинформативных правил (например, правил, включающих универсально приобретаемые товары, такие как карта лояльности магазина).

Часто задаваемые вопросы

В чем разница между поддержкой, достоверностью и подъемом?

Поддержка — это доля всех транзакций, содержащих набор элементов; она измеряет распространенность. Достоверность — это условная вероятность появления консеквента при наличии антецедента; она измеряет надежность правила. Подъем — это отношение наблюдаемой достоверности к базовой частоте консеквента; подъем выше 1 показывает истинную положительную ассоциацию, а не совпадение, обусловленное популярностью элемента.

Когда следует выбирать FP-Growth вместо Apriori?

FP-Growth сжимает базу данных в древовидную структуру и анализирует ее без повторных полных сканирований, что делает его значительно быстрее на больших наборах данных или когда минимальная поддержка низкая. Apriori проще для понимания и реализации и хорошо работает на малых и средних наборах данных, где время выполнения не является узким местом.

Как выбрать минимальную поддержку и достоверность?

Универсального правила нет. Общепринятая практика — запускать алгоритм при нескольких уровнях поддержки, строить график количества частых наборов элементов в зависимости от поддержки и выбирать значение в точке изгиба кривой. Затем достоверность устанавливается на основе бизнес-задачи или исследовательского вопроса — более высокая достоверность для критически важных правил, более низкая для разведочного поиска. Всегда проверяйте лучшие правила с помощью экспертных знаний в предметной области.

Может ли Apriori обрабатывать числовые или непрерывные данные?

Apriori требует бинарных данных о наличии элементов. Непрерывные переменные должны быть дискретизированы на интервалы (например, возраст на низкий/средний/высокий) перед кодированием в качестве элементов. Плохая дискретизация может серьезно исказить обнаруженные правила, поэтому стратегия разбиения на интервалы заслуживает тщательного рассмотрения.

Подразумевает ли Apriori причинно-следственную связь между элементами?

Нет. Правила ассоциации отражают совместное появление, а не причинно-следственную связь или направленность. Правило «хлеб → масло» означает, что они часто появляются в одной корзине; это не означает, что покупка хлеба вызывает покупку масла, и не означает, что связь асимметрична в каком-либо причинном смысле.

Похожие методы

Источники

  1. Agrawal, R. & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), 487–499.

    Открыть ссылку на публикацию
    Скопировано.
  2. Apriori algorithm. Wikipedia.

    Открыть ссылку на публикацию
    Скопировано.