§ 3. Групповое распознавание

Встречаются ситуации, когда к распознаванию предъявляется не один, а сразу несколько  объектов. При этом можно выделить два случая. В одном из них заранее известно, что все они принадлежат одному и тому же образу, и нужно узнать какому именно. В другом случае такого ограничения нет: каждый объект может принадлежать любому образу. В статистической постановке первая задача рассматривается в [1]. Здесь мы опишем алгоритм -TRF, предназначенный для ее решения в условиях малых выборок при опоре на гипотезу локальной компактности . Алгоритм -GURAM при тех же предположениях решает вторую задачу.

3.1. Алгоритм λ-ТРФ. Напомним, что таксономические решающие функции демонстрируют свои особые преимущества в случае, когда к распознаванию предъявляется сразу несколько контрольных объектов. Пусть нам известно, что все они принадлежат одному и тому же образу. Например, контрольная выборка описывает свойства нескольких изделий из данной партии и требуется вынести решение о том, принадлежит ли эта выборка классу «хороших» или «плохих» изделий.

С помощью алгоритма Прима [135] построим -КНП для каждого из  образов. Затем построим -КНП, который соединяет образы друг с другом. Для этого найдем минимальные -расстояния между всеми парами образов. В качестве расстояния между двумя образами используется минимальное -расстояние между -ближайшими точками, принадлежащими разным образам. Чтобы граф без петель, соединяющий все образы, имел минимальную суммарную длину своих (пограничных) ребер, воспользуемся тем же алгоритмом Прима.

Оценим функционал качества разделения образов в виде величины  средней длины граничных ребер:

, где

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

3.2. Алгоритм λ-GURAM. Теперь представим, что геологи вернулись из экспедиции и привезли коллекцию из  объектов, принадлежность каждого из которых тому или иному образу не известна.

Как и в алгоритме ТРФ (см. главу 5), вначале объединяем все реализации обучающей и контрольной выборок. Вычисляем -расстояния между всеми парами объектов этой смеси. Используя алгоритм Прима [135], строим кратчайший незамкнутый путь (-КНП).

Разные контрольные точки могут оказаться в разной ситуации (см. рис. 34). Некоторые контрольные точки (например, точка а) оказываются смежными только с другими контрольными точками. Назовем такие точки внутренними. Другие контрольные точки (например, b) связаны хотя бы одним ребром с точками обучающей выборки. Такие точки, а также ребра, соединяющие их с обучающими точками, называем пограничными. Распознавание контрольных точек делается последовательно (по одной точке). При этом каждая очередная распознанная контрольная точка добавляется к точкам обучающей выборки. Таким путем объем обучающей выборки растет в процессе распознавания, который выглядит следующим образом.

Рис. 34

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