МОДЕЛЬ ГРУППИРОВКИ ОБЪЕКТОВ, ОСНОВАННАЯ НА БИНАРНЫХ ОТНОШЕНИЯХ

Пономарев Андрей Васильевич

 ассистент СПбГЭТУ, г. Санкт-Петербург

E-mail: ponomarev.a.v@gmail.com

Различные практические постановки имеют в своей основе общую идею: образование групп из заданных объектов при определенных условиях и ограничениях. Многие из этих задач в настоящее время успешно решаются с применением тех или иных формальных моделей. Однако автору не удалось найти в литературе упоминания о попытках проанализировать и описать внутреннее родство таких задач, выделить общие идеи, подходы и методы, которые можно было бы применять последовательно, столкнувшись с той или иной задачей группировки объектов.

Ближе всего к намеченной автором цели находится область исследований, объединенная названием «кластерный анализ» [2]. Отличие в том, что в рамках кластерного анализа традиционно рассматривается группировка однородных объектов и каждый формируемый кластер тоже, в свою очередь, состоит из однородных объектов. В общем же случае, исходными данными для группировки могут быть объекты различных типов и искомые группы могут сами иметь определенные ограничения на соотношение объектов различных типов, входящих в нее. Хотя кластерный анализ, безусловно, является частным случаем группировки.

Под группировкой в данной работе понимается создание комплексных, сложных объектов из множества простых объектов наилучшим образом. Уточним это определение.

Пусть задано семейство множеств исходных объектов Q = (O⁽¹⁾, O⁽²⁾, …, O^(k)).

Базовой группой G на семействе исходных множеств назовем семейство множеств

G = (O⁽¹⁾(G), O⁽²⁾(G), …, O^(k)(G))

таких, что

O⁽ⁱ⁾(G) Í O⁽ⁱ⁾,   i Î {1, …, k}.

O⁽ⁱ⁾_G назовем компонентами группы.

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

Группировку G на семействе исходных множеств определим как множество попарно не пересекающихся групп на этом семействе.

Группировка G называется полной по O⁽ⁱ⁾, если ÈO⁽ⁱ⁾(G) = O⁽ⁱ⁾, при G Î G.

Группировка G называется полной, если она полная по любому из множеств семейства Q.

Группировка G называется частично полной, если она не является полной, но в семействе Q существует хотя бы одно множество O⁽ⁱ⁾, по которому данная группировка является полной.

Ограниченной группой (ОГ) или группой с ограничениями называется базовая группа, на состав которой наложены дополнительные ограничения. Например, может быть задано, что в группу должен входить строго один объект из исходного множества O⁽²⁾ и один или более объектов из исходного множества O⁽¹⁾. Это типичное ограничение на состав (структуру) иерархической группы.

На практике обычно ставится задача нахождения хороших (в ряде случаев, оптимальных) группировок на различных классах ОГ. Для точной постановки этой задачи нужно определить способ сравнения группировок. Самый простой вариант – поставить каждому варианту группировки в соответствие число и решать задачу поиска такой группировки на исходном семействе множеств, которой соответствует максимальное (или минимальное) число. Способ оценки группировки будем называть системой показателей (СП).

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

Итак, для определения задачи группировки необходимо задать:

1) семейство исходных множеств Q;

2) класс ограниченной группы – то есть, набор ограничений на соотношение объектов разных типов внутри группы;

3) тип группировки по отношению к покрытию исходных множеств: полная, частично полная, неполная;

4) систему показателей.

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

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

·     одноранговую группировку;

·     централизованную группировку.

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

Централизованная группировка характеризуется тем, что в каждой группе выделяется два (или более) видов объектов, находящихся в отношении «центр - сателлит» и класс ОГ и система показателей задачи группировки формулируются уже через взаимодействие объектов этих двух видов.

Здесь сразу можно выделить две подкатегории: двухуровневая (простейшая) централизованная группировка и многоуровневая централизованная группировка.

Двухуровневая централизованная группировка предполагает, что семейство исходных множеств Q состоит из двух множеств: множества первичных объектов O⁽¹⁾ и множества потенциальных центров групп O⁽²⁾, относительно которых происходит объединение первичных объектов. При рассмотрении этого вида группировок будем пользоваться альтернативным обозначением этих множеств S и C соответственно.

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

Для того чтобы сформулировать задачу группировки как задачу математического программирования, нужно показать способ перехода от терминологии описания задачи группировки к трем составляющим задачи МП: набору переменных, набору ограничений и целевой функции.

Рассмотрим для примера способ перехода к задаче математического программирования для двухуровневой централизованной группировки.

Пусть m = |C|, n = |S|. Введем бинарные переменные y_j (1 £ j £ m), каждая из которых соответствует образованию группы с центром в c_j, и переменные x_ij (1 £ j £ m, 1 £ i £ n), каждая из которых соответствует присоединению объекта s_i к группе с центром в c_j.

Целевая функция будет зависеть от системы показателей задачи группировки. В основе системы показателей, как правило, находится отображение D: S ´ C → R, задающее стоимость (или, наоборот, эффективность) присоединения s_i к группе с центром в c_j. Мы будем рассматривать D как эффективность, и решать задачу максимизации эффективности группировки.

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

Максимизировать

при ограничениях:

                         (1)

         (2)

Здесь условие (1) выражает общее для всех группировок требование вхождения объекта не более, чем в одну группу. При решении задачи полной по S группировки знак в этом ограничении должен быть заменен на строгое равенство.

Ограничение (2) выражает требование того, что объект s_i должен присоединяться только к действительному центру.

Разработаны программные модули, реализующие различные алгоритмы решения задачи двухуровневой централизованной группировки.

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

Список литературы:

1.            Мустафин Н., Пономарев А., Савосин С. Методы и алгоритмы группировки геологических объектов // Информационно-измерительные и управляющие системы. 2009. т. 4. с. 71-74.

2.            Elavarasi Anitha S., Akilandeswari J. A Survey on Partition Clustering Algorithms // International Journal of Enterprise Computing and Business Systems. Vol. 1 Issue 1 January 2011.