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

Правила ассоциаций

Автор метода
Agrawal, R., Imielinski, T., & Swami, A.
Год
1993
Тип
Unsupervised pattern discovery
Семейство
Machine learning

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

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

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

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

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

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

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

История

Обучение правилам ассоциаций было формально представлено Агравалом, Имелински и Свами на конференции ACM SIGMOD в 1993 году, мотивированное задачей анализа баз данных транзакций супермаркетов. Их последующая статья 1994 года представила алгоритм Apriori, предоставив эффективный вычислительный метод. Область быстро развивалась в 1990-х и 2000-х годах, а алгоритм FP-growth (Han et al., 2000) позже предложил дальнейшие улучшения скорости. Правила ассоциаций остаются фундаментальной техникой в учебных программах по добыче данных и регулярно применяются в розничной торговле, здравоохранении и веб-аналитике.

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

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

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

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

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

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

  • Полностью неконтролируемый: не требуется метка зависимой переменной, что обеспечивает открытое обнаружение закономерностей.
  • Интерпретируемый вывод: каждое правило представляет собой читаемое человеком утверждение «ЕСЛИ–ТО» с количественно определенными поддержкой, достоверностью и подъемом.
  • Масштабируется до очень больших транзакционных баз данных с помощью эвристик отсечения (Apriori, FP-growth).
  • Применим в различных областях, где совместная встречаемость в бинарно-кодированных записях имеет значение.
  • Генерация гипотез: выявляет неожиданные совместные встречаемости, которые могут направлять последующий подтверждающий анализ.

Применение

  • Анализ рыночной корзины: выявление продуктов, которые часто покупаются вместе, для оптимизации размещения товаров и рекламных акций.
  • Рекомендации в электронной коммерции: генерация предложений «клиенты, которые купили X, также купили Y».
  • Обнаружение клинических коморбидностей: поиск наборов диагнозов, лекарств или симптомов, которые совместно встречаются в записях пациентов.
  • Биоинформатика: обнаружение совместно экспрессируемых генов или совместно встречающихся генетических вариантов в образцах.
  • Анализ веб-использования: выявление общих закономерностей кликстрима и последовательностей навигации на веб-сайтах.
  • Исследования в области опросов и поведения: поиск наборов вопросов в анкетах или поведенческих паттернов, которые совместно встречаются у респондентов.

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

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

1

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

2

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

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

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

Формула
X \Rightarrow Y, \quad X \cap Y = \emptyset
4

Каждое кандидатное правило оценивается по его достоверности: условной вероятности того, что Y присутствует при условии присутствия X. Сохраняются только правила, превышающие минимальный порог достоверности, отфильтровывая антецеденты, которые предсказывают консеквент лишь незначительно лучше, чем базовая частота.

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

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

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

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

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

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

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

Универсального правила нет. Начните с изучения распределения поддержки отдельных элементов, затем установите минимальную поддержку достаточно низкой, чтобы охватить интересующие закономерности, но достаточно высокой, чтобы гарантировать, что наборы элементов появляются хотя бы в осмысленном абсолютном количестве транзакций. Минимальная достоверность от 0,6 до 0,8 является распространенным начальным диапазоном, но знание предметной области и ранжирование по подъему должны направлять окончательный выбор.

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

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

Можно ли использовать правила ассоциаций для прогнозирования?

Они в первую очередь описательные и исследовательские, а не предсказательные. Хотя возможно использовать правила с фиксированным консеквентом (один целевой элемент) для классификации — метод, называемый ассоциативной классификацией — стандартная добыча правил ассоциаций не оптимизирует функцию потерь для прогнозирования и не должна заменять контролируемые модели при наличии размеченной зависимой переменной.

В моем наборе данных есть непрерывные переменные. Могу ли я все еще использовать правила ассоциаций?

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

Чем правила ассоциаций отличаются от корреляционного анализа?

Корреляция (например, r Пирсона) измеряет линейную связь между двумя непрерывными переменными. Правила ассоциаций обнаруживают закономерности совместной встречаемости среди наборов бинарных элементов — любого размера комбинации — в транзакционных данных. Метрики (поддержка, достоверность, подъем) основаны на частоте, а не на моментах, а вывод представляет собой набор читаемых человеком правил «ЕСЛИ–ТО», а не один числовой коэффициент.

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

Источники

  1. Agrawal, R., Imielinski, 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, 207–216.

    Открыть ссылку DOI
    Скопировано.
  2. Tan, P.-N., Steinbach, M., Karpatne, A., & Kumar, V. (2018). Introduction to Data Mining (2nd ed., Ch. 5). Pearson.

    ISBN: 978-0-13-312890-1
    Скопировано.