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

Материал из 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»

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

@@ Строка 1: / Строка 1: @@
-'''Логическая закономерность''' (правило, rule) — в задачах [[классификация|классификации]] — легко интерпретируемое условие, выделяющее из [[обучающая выборка|обучающей выборки]] достаточно много объектов какого-то одного класса и практически не выделяющее объекты остальных классов.
+{{TOCright}}
+'''Логическая закономерность''' в задачах [[классификация|классификации]] — легко интерпретируемое правило (rule), выделяющее из [[обучающая выборка|обучающей выборки]] достаточно много объектов какого-то одного класса и практически не выделяющее объекты остальных классов.
 ''Логические закономерности'' являются элементарными «строительными блоками» для широкого класса [[Логический классификатор|логических алгоритмов классификации]], называемых также алгоритмами [[индукция правил|индукции правил]] (rule induction).
@@ Строка 13: / Строка 14: @@
 Говорят, что предикат <tex>\phi: X\to\{0,1\}</tex> ''выделяет'' или ''покрывает'' (cover) объект <tex>x</tex>, если <tex>\phi(x)=1</tex>.
-''Закономерностью'' называется предикат <tex>\phi(x)</tex>, выделяющий много положительных объектов и мало отрицательных.
-К&nbsp;''закономерностям'' предъявляется три основных требования: интерпретируемость, информативность и взаимодополняемость.
-=== Интерпретируемость ===
+Пусть <tex>f_j:\:X\to D_j</tex>, <tex>j=1,\ldots,n</tex> — [[признак]]и, с помощью которых описываются объекты.
-Предикат <tex>\phi(x)</tex> должен описываться простой логической формулой, понятной экспертам в данной прикладной области. На&nbsp;практике логические закономерности часто ищут в&nbsp;виде конъюнкций небольшого числа элементарных высказываний. Именно в&nbsp;такой форме люди привыкли выражать свой житейский и&nbsp;профессиональный опыт.
+Признаки могут быть разнотипными, то есть в общем случае множества <tex>D_j</tex> различны.
+Наиболее распространённый случай — когда все признаки числовые: <tex>D_j=\mathbb{R}</tex>.
+При этом числами могут кодироваться признаки, измеренные в различных [[Шкала измерения|шкалах]], в частности, бинарные, номинальные и порядковые признаки.
+''Закономерностью'' называется предикат <tex>\phi(x)</tex>, удовлетворяющий требованиям ''интерпретируемости'' и ''информативности''.
+К&nbsp;набору закономерностей, образующих [[логический классификатор]], дополнительно предъявляется требование ''взаимодополняемости'' (различности).
+== Интерпретируемость ==
+Предикат <tex>\phi(x)</tex> называется «хорошо интерпретируемым» или ''правилом'', если он описывается простой формулой, понятной экспертам в данной прикладной области.
+Строгого формального определения ''интерпретируемости'' не существует.
+В&nbsp;большинстве практических задач для интерпретируемости необходимо (но не достаточно), чтобы предикат <tex>\phi(x)</tex> зависел от небольшого числа <tex>K</tex> признаков.
+Часто вводится ограничение <tex>1 \leq K \leq 7</tex>.
+Кроме того, накладывается ограничение на функциональный вид правил.
+Чаще всего применяются конъюнкции, реже — шары или гиперплоскости.
+Другие виды правил могут диктоваться спецификой задачи.
+=== Конъюнкции ===
+Люди привыкли выражать свой житейский и&nbsp;профессиональный опыт в&nbsp;виде правил вида
+«если <tex>\phi(x)</tex>, то относительно объекта <tex>x</tex> принять решение <tex>y</tex>».
+Причём в роли <tex>\phi(x)</tex> часто выступают конъюнкции небольшого числа элементарных высказываний.
+Такие правила называются ''логическими'':
+:<tex>\phi(x) = \prod_{j\in\omega}\bigl[ f_j(x) \leq=\geq a_j\bigr],</tex>
+где
+<tex>\omega</tex> —&nbsp;подмножество призаков мощности не более&nbsp;<tex>K</tex>,
+<tex>a_j</tex> —&nbsp;пороговое значение признака.
+Для количественных и порядковых признаков используются знаки сравнения <tex>\leq</tex> или <tex>\geq</tex>;
+для бинарных и номинальных — только равенство.
 '''Пример''' (из области медицины).
 Решается вопрос о целесообразности хирургической операции.
 Закономерность:
-«'''если''' возраст пациента выше 60 лет и ранее он перенёс инфаркт,
+«'''если''' возраст пациента выше 60 лет '''и''' ранее он перенёс инфаркт,
 '''то''' операцию не делать — риск отрицательного исхода велик и составляет 60%».
@@ Строка 31: / Строка 57: @@
 '''и''' его зарплата превышает $1000 в месяц,
 '''и''' сумма кредита не превышает $10000,
-'''то''' кредит можно выдать — риск невозврата мал и составляет 10%».
+'''то''' кредит можно выдать — риск невозврата мал и составляет 2%».
-Наряду с конъюнкциями используются и другие формы интерпретируемых закономерностей:
+Построение логических правил по выборке данных сводится к поиску таких
-шары, гиперплоскости, ядра.
+<tex>\omega</tex> и <tex>\{a_j\}_{j\in\omega}</tex>,
+при которых информативность правила максимальна.
-=== Информативность ===
+=== Шары ===
+=== Гиперплоскости ===
+== Информативность ==
 Введём четыре величины:
 :<tex>P_y = \sum\nolimits_{i=1}^m [y_i=y]</tex> — число положительных объектов в выборке <tex>X^m</tex>;
@@ Строка 50: / Строка 81: @@
 логическое, статистическое, энтропийное.
-=== Взаимодополняемость ===
+== Взаимодополняемость ==
 Набор закономерностей в совокупности должен образовывать алгоритм классификации <tex>a:\:X\to Y</tex>.
 Чаще всего [[логический классификатор]] представляет собой взвешенную сумму закономерностей:
-:<tex>a(x) = \arg\max_{y\in Y} \sum_{t=1}^T_y \alpha_{yt} \phi_{yt}(x),</tex>
+:<tex>a(x) = \arg\max_{y\in Y} \sum_{t=1}^{T_y} \alpha_{yt} \phi_{yt}(x),</tex>
 где
 <tex>\alpha_{yt}</tex> — неотрицательные веса.
 В&nbsp;данной форме могут быть представлены также [[Решающий список|решающие списки]] и [[Решающее дерево|деревья]].
-Требование взаимодополняемости закономерностей означает, что для любого объекта выборки должна найтись закономерность <tex>\phi_{yt}</tex>, выделяющая данный объект. В&nbsp;противном случае алгоритм <tex>a(x)</tex> не сможет классифицировать объект, то есть произойдёт [[отказ от классификации]].
+Требование взаимодополняемости закономерностей означает, что для любого объекта выборки должна найтись закономерность <tex>\phi_{yt}</tex>, выделяющая данный объект.
+В&nbsp;противном случае алгоритм <tex>a(x)</tex> не сможет классифицировать объект, то есть произойдёт [[отказ от классификации]].
+Существует много эвристик, направленных на увеличение различности закономерностей и и более равномерное покрытие выборки.
+*[[Жадный алгоритм (задача о покрытии)]]
+*[[Бустинг правил]]
+== Методы поиска закономерностей ==
+Поиск (или синтез) всех закономерностей по заданной выборке данных является [[NP-полная задача|NP-полной]] задачей [[комбинаторная оптимизация|комбинаторной оптимизации]].
+В&nbsp;общем случае для её решения требуется выполнить полный перебор всех наборов признаков.
+Поэтому на практике используются эвристические алгоритмы сокращённого перебора.
+*[[Стохастический локальный поиск]]
+*[[Алгоритм КОРА]] (поиск в глубину или метод ветвей и границ)
+*[[Алгоритм ТЕМП]] (поиск в ширину)
+*[[Генетический алгоритм (поиск правил)]]
+Для поиска коротких информативных наборов признаков подходят различные методы [[Отбор признаков|отбора признаков]], в том числе:
+*[[Add-Del]]
+*[[МГУА]]
+*[[Генетический алгоритм (отбор признаков)]]
+*[[Случайный поиск с адаптацией]]
 == Ссылки ==
 == Литература ==
+#{{П:Журавлёв 2006 Распознавание}}
+#{{П:Загоруйко 1999 Прикладные методы анализа данных и знаний}}
+#{{П:Загоруйко 1985 Алгоритмы обнаружения эмпирических закономерностей}}
+#{{П:Лбов 1981 Методы обработки разнотипных экспериментальных данных}}
 {{stub}}
 [[Категория:Логические алгоритмы классификации]]
 [[Категория:Энциклопедия анализа данных]]