7.10. ВЫБОР ДВОИЧНЫХ ПРИЗНАКОВ

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

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

7.10.1. Последовательный алгоритм

Рассматриваемый здесь алгоритм обеспечивает порождение одного двоичного признака в каждом цикле итерации по предъявленным образам. Процедура в основном сводится к заданию переменной пороговой величины и изменению порожденного признака, как только значение порога будет превышено. Алгоритм вводится разбором на частном примере.

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

Рис. Иллюстрация принципа действия последовательного алгоритма.

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

Порождение первого признака происходит так. Пусть — исходное значение признака — расстояние между определяемое как число единиц в пересечении

и образа . В таком случае при принимается в противном случае Выбрав в данном случае с помощью рис. и , устанавливаем, что Поэтому, как показано на рис. 7.3,б2, принимаем Так как пересечение и образа равно то, как показано на рис. принимаем Очевидно, что на следующем шаге итерации поэтому признак не изменяется, т. е. как показано на рис. 1.3,б4. Этот рисунок представляет окончательное значение признака так как к этому моменту просмотрены уже все предъявленные образы.

Для определения принака процедура полностью повторяется, за исключением того, что перед каждым сравнением величина порога вычисляется заново. Первое новое значение порога определяется выражением , где представляет окончательное значение признака В таком случае при принимаем в противном случае . В нашем случае так как то принимаем как показано на рис. 7.3,в. В основе подобного увеличения порога лежит желание избежать дублирования признаков. Перед выполнением очередного сравнения следует вычислить новое значение порога. Воспользовавшись скорректированным значением признака определяем новое значение пороговой величины: Поскольку то, как показано на рис. принимаем , наконец, теперь, поскольку принимаем как показано на рис. 7.3, в4. Внимательно изучив образы, можно убедиться в том, что признаки и найденные в процессе реализации описанной процедуры, представляют собой минимальный набор признаков, необходимый для безошибочного восстановления заданных образов.

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

где

Остались открытыми два вопроса, связанные с этим алгоритмом.

1) Каким образом выбирается значение пороговой величины ?

2) Сколько признаков должно быть порождено? К сожалению, к настоящему времени ответ ни на один из этих вопросов в общем случае неизвестен. Поскольку, однако, при решении реальных задач проблема заключается в выборе значения порога , то часто оказывается полезным повторить описанную процедуру с несколькими значениями порога и выбрать значение, приводящее к наилучшим результатам.

7.10.2. Параллельный алгоритм

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

Рассмотрим двоичных образов и допустим, что на шаге итерационного процесса работа ведется с признаками При предъявлении образа новые признаки определяются так:

(см. скан)

параметра определяется из выражения

(при ), где член учитывается при суммировании только в тех случаях, когда а) .

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

Для иллюстрации работы параллельного алгоритма воспользуемся образами, представленными на рис. 7.4, а. Примем, что равно , и выберем в качестве начального признака . После этого предъявляется признак . Так как то, как показано на рис. полагаем Поскольку этот признак позволяет восстановить образ предъявляется очередной образ. Так как то, как показано на рис. полагаем . Образ однако, не удается восстановить с помощью одного признака поэтому порождается новый признак как показано на рис. 7.4, e1. Далее, обнаружив, что полагаем Так как то для признака значение пороговой величины увеличивается до Как видно из рис. 7.4, эта операция позволяет избежать равенства признака признаку Поскольку то Единственным признаком, изменившимся на этом шаге, является признак Так как образ нельзя восстановить с помощью только этого признака, то порождается новый признак При предъявлении образа обнаруживается, что поскольку . В результате значение порога для признака не изменяется. С другой стороны, поэтому Эти два обстоятельства означают, что пороговое значение для признака также не изменяется. Поэтому, так как полагаем . Признак позволяет восстановить образ (единственный признак, подвергавшийся изменению); следовательно, на этом шаге не нужно порождать новый признак. Признаки, полученные в результате осуществления следующего шага, представлены на рис. 7.4. Поскольку, однако, эти признаки не позволяют восстановить все шесть заданных образов, необходимо выполнить новый цикл итерации.

(кликните для просмотра скана)

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

Параллельный алгоритм часто позволяет получить множество признаков за меньшее число итераций, чем последовательный алгоритм. Скорость процедуры повышается за счет порождения новых признаков, без полного определения старых. Этот прием, однако, усложняет механизм увеличения пороговой величины и часто приводит к получению большего, чем нужно для восстановления заданных образов, числа признаков. Как и в случае последовательного алгоритма, в принципе единственный способ определения искомого множества признаков заключается в реализации алгоритма с различными значениями пороговой величины и выборе лучших из полученных результатов.