9.2. Классификация при ограничениях на связи между объектами

Довольно типичной является ситуация, когда исследова тель желает получить разбиение совокупности объектов на классы, согласованное с матрицей ограничений где если объекты по априорным сведениям, являются разнородными, и если таких сведений об объектах нет. Например, в задачах формирования нескольких экспертных комиссий для анализа некоторой производственно-экономической системы объектами группировки являются эксперты, описываемые их профессиональными показателями, но при формировании комиссий желательно учитывать особенности взаимоотношений между экспертами.

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

Приведем примеры построения матриц ограничений .

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

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

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

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

Опишем схему соответствукнцего агломеративного алгоритма иерархической классификации.

Схема алгоритма

1. Выберем меру близости между подмножествами исследуемой совокупности. Подадим на вход алгоритма разбиение на одноточечные классы и матрицу ограничений

2. Допустим, что на шаге имеется разбиение и матрица ограничений .

Найдем

Объединим классы в одни класс и получим разбиение где

Далее, получим матрицу ограничений где если

3. Если — единичная матрица, то объявляем разбиение итоговой классификацией. Если вне диагонали матрицы имеются ненулевые элементы, то возвращаемся к шагу 2, заменив .

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

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