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

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

Содержание

1 Определения и обозначения
2 Интерпретируемость
3 Информативность
4 Взаимодополняемость
5 Методы поиска закономерностей
6 Ссылки
7 Литература

Логическая закономерность в задачах классификации — легко интерпретируемое правило (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-полной задачей комбинаторной оптимизации. В общем случае для её решения требуется выполнить полный перебор всех наборов признаков. Поэтому на практике используются эвристические алгоритмы сокращённого перебора.

Стохастический локальный поиск
Алгоритм КОРА (поиск в глубину или метод ветвей и границ)
Алгоритм ТЕМП (поиск в ширину)
Генетический алгоритм (поиск правил)

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

Ссылки

Литература

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

Это незавершённая статья. Вы поможете проекту, исправив и дополнив её.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9B%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B7%D0%B0%D0%BA%D0%BE%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D1%81%D1%82%D1%8C»

Категории: Незавершённые статьи | Логические алгоритмы классификации | Энциклопедия анализа данных