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

Полуавтоматическое извлечение правил ассоциаций

Автор метода
Liu, B.; Hsu, W.; Ma, Y. (and subsequent researchers)
Год
2003–2010s
Тип
Pattern mining with partial supervision
Семейство
Machine learning

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

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

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

Полуавтоматическое извлечение правил ассоциаций расширяет классическое обучение правил ассоциаций за счет использования небольшого количества размеченных данных наряду с большим неразмеченным набором данных.

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

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

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

История

Извлечение правил ассоциаций было формализовано Агравалом, Имелински и Свами в 1993 году с введением алгоритма Apriori, нацеленного на неконтролируемое обнаружение частых наборов элементов в данных рыночной корзины. Интеграция меток классов и ограничений в извлечение правил ассоциаций получила развитие в начале 2000-х годов, в частности, благодаря фреймворкам CMAR и CBA Лю и коллег, которые рассматривали метки классов как следствия правил. Полуавтоматические расширения появились по мере того, как исследователи осознали, что частичный надзор может уменьшить комбинаторный взрыв кандидатов в правила, сохраняя при этом статистический вклад неразмеченных данных. Этот подход теперь встречается в биоинформатике, анализе образовательных данных и рекомендательных системах.

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

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

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

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

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

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

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

Применение

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

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

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

1

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

2

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

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

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

4

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

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

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

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

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

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

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

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

Сколько размеченных данных необходимо?

Даже небольшой размеченный набор может предоставить полезные ограничения, но качество затравки важнее количества. На практике рекомендуется иметь по крайней мере несколько десятков размеченных примеров на класс, чтобы избежать сильно предвзятых ограничений. Если метки чрезвычайно редки, результаты следует тщательно проверять на отложенном размеченном поднаборе.

Какие пороги следует установить для поддержки и достоверности?

Универсального ответа нет: пороги зависят от размера набора данных, предметной области и того, сколько правил вы можете реально оценить. Начните с умеренных порогов (например, поддержка 0,05–0,10, достоверность 0,60–0,80), изучите полученное количество правил и скорректируйте. Когда ограничения активны, вы часто можете позволить себе немного более низкие пороги поддержки, поскольку нерелевантные правила отфильтровываются условиями меток.

Может ли этот метод обрабатывать непрерывные или числовые признаки?

Извлечение правил ассоциаций по своей природе работает с дискретными элементами. Непрерывные признаки должны быть дискретизированы на интервалы перед извлечением. Выбор стратегии разбиения влияет на то, какие наборы элементов становятся частыми, поэтому стоит поэкспериментировать с разбиением на интервалы равной ширины, равной частоты и основанным на предметной области, и проверить, насколько чувствительны результаты к выбору.

Как оценить качество обнаруженных правил?

Помимо поддержки и достоверности, оценивайте правила с помощью подъема (значения выше 1 указывают на истинную совместную встречаемость сверх случайной), убежденности и рычага. Если правила используются для прогнозирования, измеряйте точность классификации, F1 или AUC на отложенном размеченном наборе. Одних только мер интересности недостаточно для оценки практической полезности.

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

Источники

  1. Liu, B., Hsu, W., & Ma, Y. (2003). Integrating Classification and Association Rule Mining. In Proceedings of the 4th IEEE International Conference on Data Mining (ICDM), pp. 339–346.

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

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