§ 3. Групповое распознавание
Встречаются ситуации, когда к распознаванию предъявляется не один, а сразу несколько
объектов. При этом можно выделить два случая. В одном из них заранее известно, что все они принадлежат одному и тому же образу, и нужно узнать какому именно. В другом случае такого ограничения нет: каждый объект может принадлежать любому образу. В статистической постановке первая задача рассматривается в [1]. Здесь мы опишем алгоритм
-TRF, предназначенный для ее решения в условиях малых выборок при опоре на гипотезу локальной компактности
. Алгоритм
-GURAM при тех же предположениях решает вторую задачу.
3.1. Алгоритм λ-ТРФ. Напомним, что таксономические решающие функции демонстрируют свои особые преимущества в случае, когда к распознаванию предъявляется сразу несколько контрольных объектов. Пусть нам известно, что все они принадлежат одному и тому же образу. Например, контрольная выборка описывает свойства нескольких изделий из данной партии и требуется вынести решение о том, принадлежит ли эта выборка классу «хороших» или «плохих» изделий.
С помощью алгоритма Прима [135] построим
-КНП для каждого из
образов. Затем построим
-КНП, который соединяет образы друг с другом. Для этого найдем минимальные
-расстояния между всеми парами образов. В качестве расстояния между двумя образами используется минимальное
-расстояние между
-ближайшими точками, принадлежащими разным образам. Чтобы граф без петель, соединяющий все образы, имел минимальную суммарную длину своих (пограничных) ребер, воспользуемся тем же алгоритмом Прима.
Оценим функционал качества разделения образов в виде величины
средней длины граничных ребер:
, где 
Теперь добавим контрольные объекты к обучающим объектам образа
и построим
-КНП для этой смеси. После этого перестроим
-КНП между образами и найдем оценку
качества разделения в предположении, что контрольные объекты принадлежат образу
. Затем повторим процедуру добавления контрольных объектов поочередно ко всем остальным образам и получения оценок
. Выберем тот (
-й) вариант, для которого оценка
была максимальной. Присоединение контрольных объектов к
-му образу не ухудшило исходного качества
разделения образов или ухудшило его на минимальную величину. На этом основании принимается решение о принадлежности контрольных объектов этому
-му образу.
3.2. Алгоритм λ-GURAM. Теперь представим, что геологи вернулись из экспедиции и привезли коллекцию из
объектов, принадлежность каждого из которых тому или иному образу не известна.
Как и в алгоритме ТРФ (см. главу 5), вначале объединяем все реализации обучающей и контрольной выборок. Вычисляем
-расстояния между всеми парами объектов этой смеси. Используя алгоритм Прима [135], строим кратчайший незамкнутый путь (
-КНП).
Разные контрольные точки могут оказаться в разной ситуации (см. рис. 34). Некоторые контрольные точки (например, точка а) оказываются смежными только с другими контрольными точками. Назовем такие точки внутренними. Другие контрольные точки (например, b) связаны хотя бы одним ребром с точками обучающей выборки. Такие точки, а также ребра, соединяющие их с обучающими точками, называем пограничными. Распознавание контрольных точек делается последовательно (по одной точке). При этом каждая очередная распознанная контрольная точка добавляется к точкам обучающей выборки. Таким путем объем обучающей выборки растет в процессе распознавания, который выглядит следующим образом.

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