15.4. КЛАССИФИКАЦИЯ С ОГРАНИЧЕНИЯМИ В ВИДЕ ГРАФА СВЯЗЕЙ

15.4.1. Введение

Пусть множество, состоящее из элементов, которые требуется разбить на классы; расстояние на Будем считать, что -система весов на Пусть граф, задаваемый таблицей инцидентности с элементами

Граф описывает пространственную близость элементов из Близким элементам х и у соответствует далеким — Разброс класса обычно измеряется величиной

Введение пространственных ограничений позволяет переопределить меру разброса класса. Теперь его надо измерять величиной

Таким образом, на класс С накладывается штраф если его элементы не являются «соседями». В случае, когда критерий соседства не симметричен, имеются три возможности:

если то вклад в величину внутриклассового разброса равен когда точки х и у взаимно далекие;

если или наоборот, то внутриклассовый разброс изменяется на ;

если то такие точки являются взаимно соседними, и их вклад в величину разброса равен нулю.

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

Общий разброс классов разбиения зависит от расстояния и матрицы инцидентности и может быть измерен следующим критерием:

где . Здесь весовой коэффициент.

15.4.2. Изучение влияния весового множителя а

Если

Одним из оптимальных решений является разбиение при котором каждый элемент множества образует отдельный класс: Если то

и одним из решений является разбиение при котором все элементы из попадают в один класс: Если а то ни одно из описанных выше двух разбиений не обязано быть оптимальным. Например, при

а для некоторого а

Значение а можно определить, потребовав

откуда где

— цена, соответствующая соседним элементам и

— цена, соответствующая далеким элементам

15.4.3. Цена перегруппировки двух элементов

а) Цена перегруппировки двух соседних элементов х и у при равна

б) Цена перегруппировки двух далеких элементов х, у, когда имеет вид

в) Если элементы х и у не перегруппировываются, то Зависимость цены перегруппировки от элементов матрицы можно свести в следующую таблицу:

(см. скан)

Цена перегруппировки пары равна:

и возможны следующие случаи:

а) если х и у не принадлежат одному классу, то ;

б) если х и у перегруппированы, то

3) или в этом случае . Знак последнего выражения зависит от а. Например, если

то отрицательна при

15.4.4. Метод и алгоритм

Критерий можно выразить в виде функции от цены перегруппировки :

где разбиение на классов, а постоянная величина. Метод ядерных разбиений (см. [10] и гл. 2) позволяет оптимизировать критерий, похожий на (6). В данном случае пространством представительств является множество всех подмножеств

множества Мера адекватности, определенная на элементах из имеет вид

где При этом (6) принимает вид

где Когда в итоге сходимости алгоритма критерий (7) с точностью до постоянной эквивалентен критерию (5).

15.4.5. Применение классификации с ограничениями в виде графа связей

Описанный метод может оказаться полезным при применении метода ближайших соседей, а также метода автоматической классификации, минимизирующего критерий, зависящий от инерции. Метод ближайших соседей позволяет построить следующую матрицу инцидентности графа: если у — один из ближайших соседей х, иначе При этом Два элемента х и у взаимно являются соседями, когда Если потребовать в этом случае и в противном случае, то получится симметричная таблица к которой можно применить описанный метод. Таким образом, разбиение, полученное исходя из связных компонент графа, соответствующего таблице является решением, оптимальным в смысле критерия (5). Поиск разбиения, число классов которого превышает число связных компонент графа, определенного матрицей может быть только компромиссом между штрафом за исключение ветвей графа и выигрышем от создания новых классов в смысле критерия, зависящего, от критерия инерции, отвечающего расстоянию В этом случае можно найти локально-оптимальное решение.

ЛИТЕРАТУРА

(см. скан)

(см. скан)