8.1. Минимизация набора прецедентов (алгоритм STOLP)

Очевидный недостаток описанных здесь методов состоит в том, что в памяти машины нужно хранить сведения обо всех реализациях обучающей выборки. Естественно возникает вопрос: нельзя ли сохранять в качестве прецедентов не все, а лишь часть реализаций каждого образа? Например, оставить в качестве прецедентов только такие «точки опоры» образа , которые обеспечивают выполнение следующего условия: расстояние от любой точки обучающей выборки -го образа до ближайшего своего прецедента меньше расстояния до ближайшего прецедента чужого образа. Такой набор прецедентов обеспечит безошибочное распознавание всех реализаций обучающей выборки. Контрольные реализации распознаются по методу ближайшего соседа.

Сложность решения этой задачи состоит в том, что состав прецедентов -го образа зависит от того, какие реализации других образов выбраны в качестве прецедентов [149]. Из этого становится очевидным комбинаторный характер задачи, оптимальное решение которой в общем случае требует полного перебора всех вариантов. Если количество образов , число реализаций каждого (-го) образа в обучающей выборке равно , то число возможных вариантов оставления по одному прецеденту для каждого образа  равно . Если же оставлять по  прецедентов на образ, то число вариантов возрастает до величины . Перебор вариантов можно сократить с помощью алгоритма STOLP. Рассмотрим его работу на примере с двумя образами (см. рис. 18.)

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

Затем делается пробное распознавание всех точек обучающей выборки с опорой на прецеденты и с использованием правила ближайшего соседа: точка относится к тому образу, расстояние до прецедента которого минимально. Среди точек, распознанных неправильно, выбирается точка с максимальным значением  и ею пополняется список прецедентов, после чего повторяется процедура пробного распознавания всех точек. Так продолжается до тех пор, пока все точки обучающей выборки не станут распознаваться без ошибок. В примере на рис. 18 в качестве первых прецедентов были выбраны точки 1 и 2. Затем список прецедентов пополнился точками 3, 4 и 5.

При количестве образов большем, чем два, целесообразно применять ускоряющие приемы, описанные в § 4. В частности, описанная процедура выбора прецедентов должна начинаться с пары самых близких образов. В качестве расстояния между образами  и  принимается расстояние  между двумя самыми близкими точками  и , принадлежащими разным образам (расстояние Хаусдорфа). После решения задачи для двух первых образов выбирается следующая самая близкая пара образов. Если среди них окажется образ  (или ) с выделенными на предыдущем этапе прецедентами, то эти прецеденты включается с самого начала в рассмотрение и в случае необходимости будут дополнены новыми.

Рис. 18

К концу рассмотрения парных сочетаний всех образов каждый из них будет представлен в памяти набором прецедентов, достаточным для безошибочного распознавания всех своих объектов обучающей выборки. Распознавание новых объектов можно делать по правилу одного или нескольких ближайших соседей. Если число образов  и объем обучающей выборки  очень велики, то алгоритм STOLP может потребовать слишком большого машинного времени. Для его сокращения необходима разработка аналогов тех алгоритмов, которые были описаны в § 4 для случая распознавания большого числа образов с помощью статистических решающих правил (алгоритмы попутного разделения, покоординатного вычеркивания, отбора сильнейшего конкурента). Сложность разработки этих аналогов состоит в том, что здесь не удастся ограничиться сравнением с одним «эталоном» на образ, в качестве которого там использовался вектор математического ожидания нормального распределения. Теперь придется иметь дело с заметно большим числом прецедентов. Отсутствует здесь и помогавшее в прошлом понятие разделяющей поверхности.

Можно предположить, что среди распознаваемых объектов встречаются не только реализации одного из заданных  образов, но и некоторого неизвестного -го образа. Введем пороговую величину  и будем считать, что точки, удаленные от прецедентов -го образа на расстояние, большее , заведомо не принадлежит -му образу. Если объект  не принадлежит ни одному из  образов, то будем относить его к -му образу. В качестве порога  примем расстояние между двумя самыми далекими друг от друга точками -го образа («диаметр» образа).

При таком пороговом правиле принятия решений появляется возможность сократить перебор в алгоритме STOLP. Если ближайшие точки двух разных образов  и  удалены друг от друга на расстояние, большее , то роль прецедентов в противостоянии этих образов могут выполнить любые две реализации из обучающей выборки (по одной реализации из каждого образа). И никакая контрольная точка  не будет для этих образов спорной: она однозначно будет отнесена либо к одному из них, либо ни к одному. Если в образах  и , оказавшихся в очередной самой близкой паре, уже имеются прецеденты, выделенные на предыдущих шагах алгоритма, и эти образы удалены на расстояние, большее , то попытками дополнить список прецедентов этих образов можно не заниматься. А такие пары по мере перехода от самых близких пар к более далеким будут встречаться все чаще.

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