Правила ассоциаций
- Автор метода
- 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 указывает на присутствие товара. Это разреженное, широкое представление является основным входным форматом; небинарные или количественные элементы должны быть дискретизированы перед этим шагом.
Идентифицируются все комбинации товаров (наборы элементов), частота которых в базе данных транзакций соответствует заданной пользователем минимальной пороговой поддержке. Принцип Apriori — любой поднабор частого набора элементов также является частым — значительно сокращает пространство комбинаторного поиска, делая перечисление осуществимым даже на больших каталогах.
Формула
\text{support}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|} \geq \text{min\_sup}Для каждого частого набора элементов генерируются все возможные разделения на антецедент и консеквент (X → Y, где X и Y — непересекающиеся непустые подмножества) в качестве кандидатных правил. Количество кандидатов может быть большим, поэтому последующий этап фильтрации имеет решающее значение.
Формула
X \Rightarrow Y, \quad X \cap Y = \emptyset
Каждое кандидатное правило оценивается по его достоверности: условной вероятности того, что Y присутствует при условии присутствия X. Сохраняются только правила, превышающие минимальный порог достоверности, отфильтровывая антецеденты, которые предсказывают консеквент лишь незначительно лучше, чем базовая частота.
Формула
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \text{min\_conf}Сохраненные правила ранжируются по подъему — отношению наблюдаемой совместной поддержки к поддержке, ожидаемой при независимости. Подъем, превышающий 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 Пирсона) измеряет линейную связь между двумя непрерывными переменными. Правила ассоциаций обнаруживают закономерности совместной встречаемости среди наборов бинарных элементов — любого размера комбинации — в транзакционных данных. Метрики (поддержка, достоверность, подъем) основаны на частоте, а не на моментах, а вывод представляет собой набор читаемых человеком правил «ЕСЛИ–ТО», а не один числовой коэффициент.
Похожие методы
Источники
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Скопировано.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Скопировано.