Логическая закономерность
Материал из MachineLearning.
Логическая закономерность (правило, rule) — в задачах классификации — легко интерпретируемое условие, выделяющее из обучающей выборки достаточно много объектов какого-то одного класса и практически не выделяющее объекты остальных классов. Логические закономерности являются элементарными «строительными блоками» для широкого класса логических алгоритмов классификации, называемых также алгоритмами индукции правил (rule induction).
Содержание |
Определения и обозначения
Пусть
— пространство объектов,
— множество имён классов,
— обучающая выборка.
Пусть — фиксированнный класс.
Объекты этого класса будем называть положительными (positive examples);
объекты остальных классов — отрицательными (negative examples).
Говорят, что предикат выделяет или покрывает (cover) объект
, если
.
Закономерностью называется предикат
, выделяющий много положительных объектов и мало отрицательных.
К закономерностям предъявляется три основных требования: интерпретируемость, информативность и взаимодополняемость.
Интерпретируемость
Предикат должен описываться простой логической формулой, понятной экспертам в данной прикладной области. На практике логические закономерности часто ищут в виде конъюнкций небольшого числа элементарных высказываний. Именно в такой форме люди привыкли выражать свой житейский и профессиональный опыт.
Пример (из области медицины). Решается вопрос о целесообразности хирургической операции. Закономерность: «если возраст пациента выше 60 лет и ранее он перенёс инфаркт, то операцию не делать — риск отрицательного исхода велик и составляет 60%».
Пример (из области банковской деятельности). Решается вопрос о выдаче кредита. Закономерность: «если заёмщик указал в анкете свой домашний телефон, и его зарплата превышает $1000 в месяц, и сумма кредита не превышает $10000, то кредит можно выдать — риск невозврата мал и составляет 10%».
Наряду с конъюнкциями используются и другие формы интерпретируемых закономерностей: шары, гиперплоскости, ядра.
Информативность
Введём четыре величины:
— число положительных объектов в выборке
;
— число отрицательных объектов в выборке
;
— число положительных объектов, выделяемых правилом
;
— число отрицательных объектов, выделяемых правилом
;
Интуитивно предикат является информативным, если одновременно
и
.
Формализовать это интуитивное требование не так просто.
Можно показать на примерах, что «наивные» попытки определить информативность предиката на выборке как функцию
приводят к неадекватным результатам. Существует несколько различных формальных определений информативности, в том числе
логическое, статистическое, энтропийное.
Взаимодополняемость
Набор закономерностей в совокупности должен образовывать алгоритм классификации .
Чаще всего логический классификатор представляет собой взвешенную сумму закономерностей:
где
— неотрицательные веса.
В данной форме могут быть представлены также решающие списки и деревья.
Требование взаимодополняемости закономерностей означает, что для любого объекта выборки должна найтись закономерность , выделяющая данный объект. В противном случае алгоритм
не сможет классифицировать объект, то есть произойдёт отказ от классификации.