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

Индукция правил (RIPPER)

Автор метода
William W. Cohen
Год
1995
Тип
Supervised rule learning algorithm
Семейство
Rule learning

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

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

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

Индукция правил, и в частности алгоритм RIPPER (Repeated Incremental Pruning to Produce Error Reduction), является методом обучения с учителем, который извлекает компактный набор правил классификации ЕСЛИ-ТО из размеченных обучающих данных.

Представленный Уильямом В. Коэном в 1995 году, RIPPER применяет стратегию разделения и завоевания (separate-and-conquer) в сочетании с отсечением по принципу минимальной длины описания (MDL) для генерации правил, которые являются одновременно точными и интерпретируемыми, что делает его знаковым алгоритмом в области индуктивного обучения правил.

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

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

История

Индукция правил имеет корни в ранних системах машинного обучения, таких как AQ (Michalski, 1969) и CN2 (Clark and Niblett, 1989). Работа Коэна 1995 года по RIPPER решала проблемы вычислительной неэффективности и тенденций к переобучению его предшественников, вводя инкрементальное отсечение и оптимизацию на основе MDL. Представленный на ICML 1995, RIPPER быстро стал эталонным алгоритмом благодаря своей конкурентоспособной точности и прозрачности, и он остается стандартным справочным материалом в литературе и учебниках по обучению правил.

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

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

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

  • Качество правил значительно ухудшается в очень высокоразмерных или разреженных пространствах признаков
  • Упорядоченные списки правил могут быть чувствительны к порядку классов; классы меньшинства, изучаемые последними, могут получить более слабые правила
  • Не производит калиброванных оценок вероятности, что ограничивает использование в задачах с учетом стоимости или ранжирования
  • Конъюнктивные правила не могут улавливать сложные взаимодействия, требующие невыровненных по осям границ, без инженерии признаков

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

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

  • Производит читаемые человеком правила ЕСЛИ-ТО, которые эксперты предметной области могут проверять и валидировать
  • Эффективное обучение по принципу разделения и завоевания с отсечением, управляемым MDL, уменьшает переобучение
  • Обрабатывает как номинальные, так и числовые атрибуты без необходимости обширной предварительной обработки
  • Как правило, быстрое время обучения по сравнению с ансамблевыми методами для умеренных размеров наборов данных

Применение

  • Поддержка принятия клинических решений и извлечение правил для медицинских диагнозов
  • Обнаружение мошенничества и аномалий при мониторинге финансовых транзакций
  • Текстовая категоризация с использованием лексических и структурных признаков
  • Обнаружение сетевых вторжений с помощью интерпретируемых правил оповещения
  • Прогнозирование оттока клиентов с помощью действенных бизнес-правил

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

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

1

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

Формула
\text{For each class } c \in \mathcal{C} \text{, grow a rule } R: \text{cond} \Rightarrow c \text{ maximizing } \frac{p}{p+n}
2

Каждое кандидатное правило отсекается на отложенном валидационном разделе с использованием метрики (p - n) / (p + n), где p и n подсчитывают правильно и неправильно охваченные экземпляры соответственно. Условия удаляются из хвоста правила внутрь до тех пор, пока отсечение не увеличит это значение, защищая от переобучения, вызванного высокоспецифичными конъюнкциями, которые случайно подходят обучающему набору.

Формула
\text{Prune rule } R \text{ by removing conditions to maximize } v(R, \text{prune set}) = \frac{p - n}{p + n}
3

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

Формула
\text{Minimize description length: } DL(\text{ruleset}) + DL(\text{data} \mid \text{ruleset})
4

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

Формула
\hat{y} = c_k \text{ where } R_k \text{ is the first rule in the ordered list that fires on instance } \mathbf{x}

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

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

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

Чем RIPPER отличается от дерева решений?

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

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

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

Какова роль принципа минимальной длины описания в RIPPER?

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

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

Источники

  1. Cohen, W. W. (1995). Fast effective rule induction. Proceedings of the 12th International Conference on Machine Learning, 115–123.

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