9.2. Алгоритм DW [120]

В основе этого алгоритма также лежит гипотеза проективной компактности. Рассмотрим его работу на примере распознавания двух образов. Элементарным высказыванием  в этом алгоритме называется выражение следующего вида:

а)   для признака , измеренного в номинальной шкале;

б) для признака в любой более сильной шкале.

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

Работа по проверке истинности или ложности выражений  по отношению к объекту  организуется с помощью таблицы . Вершине дерева с номером  (т. е. высказыванию ) сопоставляется -я строка таблицы, в которой описываются характеристики  этой вершины:

 — номер строки, занимаемый данной вершиной;

 — номер строки, куда следует переходить, если  истинно;

 — номер строки, куда следует переходить, если  ложно;

 — номер признака, на котором построено высказывание ;

 — порог , использованный при построении высказывания ;

 — количество объектов первого образа в -й вершине;

 — количество объектов второго образа в -й вершине.

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

При выборе вариантов пороговых значений  и их сочетаний возникает большой перебор, сокращение которого основано на методе наращивания «лучшего к лучшему» [2]. На первом шаге строится наилучшее в смысле некоторого критерия  элементарное высказывание  и его дополнение . С помощью этих высказываний обучающая выборка делится на две группы: группу объектов , удовлетворяющих , и группу , удовлетворяющих . Если группа  содержит объекты разных образов, то для нее ищется высказывание  и его дополнение , наилучшие с точки зрения критерия . Та же процедура для группы  дает наилучшее высказывание  и его дополнение . В результате обучающая выборка делится на четыре группы. Процесс такого деления можно представить в виде дерева , показанного на рис. 22.

Рис. 22

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

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

Большое значение имеет наглядная форма представления ЛРП в виде списка правил типа «если ... то ...». Как показал опыт, некоторые заказчики, получив решение в виде ЛРП, признаются, что оно само по себе им более интересно и полезно, чем возможность использовать его для автоматического распознавания новых объектов: им становятся видны и понятны простые закономерности, которые имеют место в изучаемой ими области.

Наконец, самое важное достоинство ЛРП состоит в том, что формулировка закономерностей в виде конъюнкций соответствует форме представления знаний в интеллектуальных системах. Следовательно, методы поиска ЛРП могут использоваться для автоматического извлечения знаний из данных.