Логическая закономерность

Материал из MachineLearning.

Перейти к: навигация, поиск

Содержание

Логическая закономерность в задачах классификации — легко интерпретируемое правило (rule), выделяющее из обучающей выборки достаточно много объектов какого-то одного класса и практически не выделяющее объекты остальных классов. Логические закономерности являются элементарными «строительными блоками» для широкого класса логических алгоритмов классификации, называемых также алгоритмами индукции правил (rule induction).

Определения и обозначения

Пусть X — пространство объектов, Y — множество имён классов, X^m = (x_i,y_i)_{i=1}^mобучающая выборка.

Пусть y\in Y — фиксированнный класс. Объекты этого класса будем называть положительными (positive examples); объекты остальных классов — отрицательными (negative examples).

Говорят, что предикат \phi: X\to\{0,1\} выделяет или покрывает (cover) объект x, если \phi(x)=1.

Пусть f_j:\:X\to D_j, j=1,\ldots,nпризнаки, с помощью которых описываются объекты. Признаки могут быть разнотипными, то есть в общем случае множества D_j различны. Наиболее распространённый случай — когда все признаки числовые: D_j=\mathbb{R}. При этом числами могут кодироваться признаки, измеренные в различных шкалах, в частности, бинарные, номинальные и порядковые признаки.

Закономерностью называется предикат \phi(x), удовлетворяющий требованиям интерпретируемости и информативности.

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

Интерпретируемость

Предикат \phi(x) называется «хорошо интерпретируемым» или правилом, если он описывается простой формулой, понятной экспертам в данной прикладной области. Строгого формального определения интерпретируемости не существует. В большинстве практических задач для интерпретируемости необходимо (но не достаточно), чтобы предикат \phi(x) зависел от небольшого числа K признаков. Часто вводится ограничение 1 \leq K \leq 7. Кроме того, накладывается ограничение на функциональный вид правил. Чаще всего применяются конъюнкции, реже — шары или гиперплоскости. Другие виды правил могут диктоваться спецификой задачи.

Конъюнкции

Люди привыкли выражать свой житейский и профессиональный опыт в виде правил вида «если \phi(x), то относительно объекта x принять решение y». Причём в роли \phi(x) часто выступают конъюнкции небольшого числа элементарных высказываний. Такие правила называются логическими:

\phi(x) = \prod_{j\in\omega}\bigl[ f_j(x) \leq=\geq a_j\bigr],

где \omega — подмножество призаков мощности не более K, a_j — пороговое значение признака. Для количественных и порядковых признаков используются знаки сравнения \leq или \geq; для бинарных и номинальных — только равенство.

Пример (из области медицины). Решается вопрос о целесообразности хирургической операции. Закономерность: «если возраст пациента выше 60 лет и ранее он перенёс инфаркт, то операцию не делать — риск отрицательного исхода велик и составляет 60%».

Пример (из области банковской деятельности). Решается вопрос о выдаче кредита. Закономерность: «если заёмщик указал в анкете свой домашний телефон, и его зарплата превышает $1000 в месяц, и сумма кредита не превышает $10000, то кредит можно выдать — риск невозврата мал и составляет 2%».

Построение логических правил по выборке данных сводится к поиску таких \omega и \{a_j\}_{j\in\omega}, при которых информативность правила максимальна.

Шары

Гиперплоскости

Информативность

Введём четыре величины:

P_y = \sum\nolimits_{i=1}^m [y_i=y] — число положительных объектов в выборке X^m;
N_y = \sum\nolimits_{i=1}^m [y_i\neq y] — число отрицательных объектов в выборке X^m;
p_y(\phi) = \sum\nolimits_{i=1}^m [\phi(x_i)=1] [y_i=y] — число положительных объектов, выделяемых правилом \phi;
n_y(\phi) = \sum\nolimits_{i=1}^m [\phi(x_i)=1] [y_i\neq y] — число отрицательных объектов, выделяемых правилом \phi;

Интуитивно предикат \phi(x) является информативным, если одновременно p_y(\phi)\to \max и n_y(\phi)\to \min. Формализовать это интуитивное требование не так просто. Можно показать на примерах, что «наивные» попытки определить информативность предиката на выборке как функцию I\bigl(p_y(\phi),n_y(\phi)\bigr) приводят к неадекватным результатам. Существует несколько различных формальных определений информативности, в том числе логическое, статистическое, энтропийное.

Взаимодополняемость

Набор закономерностей в совокупности должен образовывать алгоритм классификации a:\:X\to Y. Чаще всего логический классификатор представляет собой взвешенную сумму закономерностей:

a(x) = \arg\max_{y\in Y} \sum_{t=1}^{T_y} \alpha_{yt} \phi_{yt}(x),

где \alpha_{yt} — неотрицательные веса. В данной форме могут быть представлены также решающие списки и деревья.

Требование взаимодополняемости закономерностей означает, что для любого объекта выборки должна найтись закономерность \phi_{yt}, выделяющая данный объект. В противном случае алгоритм a(x) не сможет классифицировать объект, то есть произойдёт отказ от классификации.

Существует много эвристик, направленных на увеличение различности закономерностей и и более равномерное покрытие выборки.

Методы поиска закономерностей

Поиск (или синтез) всех закономерностей по заданной выборке данных является NP-полной задачей комбинаторной оптимизации. В общем случае для её решения требуется выполнить полный перебор всех наборов признаков. Поэтому на практике используются эвристические алгоритмы сокращённого перебора.

Для поиска коротких информативных наборов признаков подходят различные методы отбора признаков, в том числе:

Ссылки

Литература

  1. Журавлёв, Ю. И., Рязанов, В. В., Сенько, О. В. «Распознавание». Математические методы. Программная система. Практические применения. — М.: ФАЗИС, 2006. — 176 с.  (подробнее)
  2. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999. — 270 с. — ISBN 5-86134-060-9  (подробнее)
  3. Публикация:Загоруйко 1985 Алгоритмы обнаружения эмпирических закономерностей
  4. Публикация:Лбов 1981 Методы обработки разнотипных экспериментальных данных
Личные инструменты