9.1. Алгоритм CORAL [108]
Выделим некоторое подмножество
значений признака
. Для сильных признаков — это интервал значений, для шкал порядка — ряд соседних порядковых позиций, для шкал наименований — одно или несколько имен. Тот факт, что значение признака
у объекта
принадлежит подмножеству
, обозначаем через
. Тогда попадание объекта
в область
, образованную границами подмножеств
, т. е. в гиперпараллелепипед
, запишем в форме логического высказывания:

В высказывание
могут входить не все
признаков, а любое их непустое подмножество из
признаков,
. Число
называется длиной высказывания. Логической закономерностью называем высказывание, удовлетворяющее двум условиям:
и
.
Здесь
есть индекс объектов своего образа,
— индекс объектов всех чужих образов,
— общее число своих объектов,
— общее число чужих объектов,
— число своих, удовлетворяющих высказыванию
,
— число чужих объектов, удовлетворяющих этому же высказыванию
, а
и
— некоторые пороговые величины в диапазоне от нуля до единицы. Желательно, чтобы высказывание
, используемое для различения своих от чужих, отбирало побольше своих и поменьше чужих объектов, т. е. чтобы
было как можно большим, а
— как можно меньшим. Если условие
на обучающей выборке удовлетворяется, то высказывание
включается в список «покрывающего набора» закономерностей. Набор закономерностей называется покрывающим для образа
, если для любой его реализации выполняется хотя бы одна закономерность из этого набора. Желательно, чтобы число закономерностей в покрывающем наборе было минимальным.
Поиск закономерностей
начинается с больших значений
(например, с
) и малых значений
(например,
). Просматриваются все возможные подмножества значений первого случайно выбранного признака и находится высказывание
, удовлетворяющее требованию
. Если таковое не находится, то процесс поиска повторяется при более низком пороге
, устанавливаемом автоматически. Если снижение порога вплоть до величины
не дает желаемого результата, тогда увеличивается порог
допустимой доли чужих среди своих. Если условие
не выполняется и при
, то делается переход к рассмотрению второго признака, случайно выбранного из оставшихся. Если на каком то шаге условие
выполняется, то те объекты своего образа
, которые удовлетворяют высказыванию
, из дальнейшего рассмотрения исключаются. Для оставшихся объектов образа
длина высказывания увеличивается на единицу. Описанный процесс продолжается до получения покрывающего набора закономерностей для всех объектов образа
. Аналогично строятся покрывающие наборы и для всех других распознаваемых образов.
Можно потребовать, чтобы алгоритм делал для каждого образа не по одному, а по несколько покрывающих наборов. Это требование перекликается с высказыванием Р. Фейнмана [155] о том, что мы можем говорить, что понимаем явление, если в состоянии объяснить его несколькими разными способами. С этой целью после получения первого покрытия исключаем из рассмотрения первый признак, включенный в это покрытие, и процесс поиска закономерностей начинается с другого случайно выбираемого признака.
Распознавание контрольного объекта
с помощью покрывающих наборов закономерностей сводится к проверке того, каким высказываниям удовлетворяют его характеристики. Если такое высказывание одно или если их несколько и все они находятся в списке образа
, то объект
распознается в качестве реализации образа
. Если же объект
удовлетворяет закономерностям нескольких образов, то решение принимается в пользу того образа, которому принадлежит закономерность с наибольшим значением величины
.
Анализ общего списка закономерностей может показать, что некоторые признаки из исходной системы
в них отсутствуют. Это означает, что они оказались неинформативными и в процессе принятия решений на них можно не обращать внимания. Для каждого
-го образа подмножество информативных признаков может оказаться разным. Это значит, что при проверке гипотезы о принадлежности объекта
к тому или иному образу нужно анализировать не все пространство признаков, а
-е его подпространство, что хорошо согласуется с интуитивными методами неформального распознавания. Действительно, одних людей мы узнаем по росту, других по походке, третьих по фигуре и цвету волос и т. д.