3.3. Применение целочисленного программирования в кластерном анализе

В этом параграфе кластерная проблема будет рассмотрена в терминах целочисленного программирования; впервые это было сделано Вайнодом [380] и Рао [291].

Рис. 2. Граф для объектов

Балинский [12] в своем обзоре рассматривает новые методы целочисленного программирования. Посоветуем читателю также работы [11], [26], [134] и [228].

В формулировке Вайнода [380] рассматривается случай одной измеряемой характеристики в соответствии с которой и выполняется разбиение на кластеры. Предположим, у нас имеется объектов со значениями Обозначим через , число объектов в группе Число объектов в максимальном (по числу их) кластере обозначим через . Если специально не определено, то . «Издержки», связанные с включением объекта в группу, обозначим через очевидно, . Положим если объект принадлежит группе, и — в противном случае. Имеем есть сумма элементов в столбце матрицы

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

Положим если объект является ведущим, и в противном случае.

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

при условии, что

Ограничение (1) означает, что никакой объект не может содержаться более чем в одной группе. Ограничен ние (2) означает, что существует ровно групп. Последнее условие означает, что, прежде чем объекты будут присоединены к группе, содержащей элемент, этот элемент должен быть ведущим. Ограничение (3) можно переписать следующим образом:

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

В этом случае в качестве издержек может выступать любая метрика расстояния из главы 1. Порядок матрицы С при этом не меняется; задача заключается в минимизации С с учетом его нового определения.

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

Проблема заключается в разбиении

Обозначим через группу, минимальное значение которой равно . Элемент назовем ведущим элементом группы . Матрица А определяется так же, как и в предыдущем случае, т. е. или 0 в зависимости от того, принадлежит ли или нет. Поскольку z упорядочены, не может принадлежать к это означает, что элементы матрицы А, которые лежат выше диагонали, равны нулю, или

Задачу теперь можно представить как минимизацию

где есть среднее группы

и

Для того чтобы (3.17) обращалось в минимум, необходимо выполнение так называемого условия цепи (string property). Условие цепи означает, что не существует группы, содержащей z, и и не содержащей все z, значения которых лежат между ними. Это означает, что матрица не может содержать прерывающихся цепочек из единиц, расположенных ниже главной диагонали, т. е.

Максимальная цепочка содержит членов, поскольку максимальное число элементов, которое может содержать группа, равно .

Лемма 3.1. Условие цепи является необходимым условием минимальности. Доказательство. При объединении объектов увеличение ВСК равно следу матрицы (1.10), т. е.

То же происходит при объединении увеличение равно

Однако , что и доказывает необходимый результат.

Минимизация эквивалентна минимизации при соответствующем выборе

Значения необходимо определить только для , т. е. для элементов ниже главной диагонали. Значение численно равно приращению ВСК при включении элемента в группу, состоящую из элементов . Принимая во внимание (1.10), имеем:

При таком определении можно показать, что

с помощью которого первоначальную задачу квадратичного программирования можно свести к задаче линейного программирования. Окончательно задачу можно сформулировать следующим образом:

при условии:

Обобщение второй формулировки Вайнода на многомерный случай более затруднительно, чем первой. Пусть имеется точек в -мерном пространстве. Поскольку условие цепи нельзя непосредственно обобщить с одномерного случая на многомерный, Вайнод [380] предлагает обобщенное условие цепи, которое можно применить и в многомерном случае. Им также установлено, что условие цепи — это необходимое условие минимума ВСК - Рао [291] приводит контрпример и предлагает альтернативную форму обобщенного условия цепи, которое также представляет собой необходимое условие минимума ВСК.

Мы приведем оба определения после чего коротко обсудим два соответствующие им варианта проблемы (Рао и Вайнода). Пусть обозначает матрицу парных евклидовых расстояний. Элементы столбца перегруппируем в порядке возрастания, т. е.

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

Приведем теперь два определения обобщенного условия цепи.

1. (Вайнод). Цепь из единиц для столбца матрицы А проходит через причем

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

Вайнод определяет как приращение ВСК при включении в группу из объектов Значение аналогично (3.18) и в многомерном случае равно:

Пользуясь матрицей издержек, соответствующей уравнению (3.19), и матрицей А, элементы которой удовлетворяют

неравенству задачу минимизации ВСК можно свести к минимизации

При формулировке задачи линейного целочисленного программирования требует выполнения условия цепи 2. Задача, таким образом, заключается в том, чтобы найти

при условии

где или 1 (за исключением последнего элемента); —матрица ; — вектор-столбец порядка ; b - вектор-столбец порядка равный ; — вектор-строка порядка .

Заметим, что минимизируемая величина (3.20) снова является линейной функцией переменных, состоящих из 0 и 1. Каждый элемент Y служит индикатором группы, т. е. или 1 в зависимости от того, пользуются ли группой в окончательном решенйи или нет. Вектор является вектором значений целевой функции; а представляет собой значение целевой функции группы. Например, если в качестве целевой функции рассматривается ВСК, то d имеет вид:

Вектор У содержит m единиц и нулей. Выражение определяет значение целевой функции для данной альтернативы разбиения.

Матрица А аналогична соответствующей матрице из (3.17); однако теперь ее порядок равен . Матрица А удовлетворяет следующим условиям:

1) последняя строка А состоит из единиц, т. е.

2) каждая строка А, за исключением последней, соответствует одному объекту и содержит только одну единицу; все остальные элементы равны нулю;

3) каждый столбец А, за исключением последнего, представляет собой коэффициенты группы, т. е.

4) последний столбец А состоит из нулей, за исключением последнего элемента, который равен 1. Последний элемент в векторе b равен общему числу кластеров, т. е. .

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

При условии, что объект является ведущим, возможны следующие разбиения на группы: , Число таких групп равно

Поскольку всего имеется объектов, то отсюда следует, что общее число возможных групп равно включая и ту группу, которая содержит все объекты. Число элементов в векторе У соответствует общему числу возможных кластеров с тем ограничением, что общее число возможных кластеров равно . Задача (3.20) вместе с соответствующими ограничениями может быть решена различными методами, описанными в работе [127].

Рао приводит другие критерии минимизации, которыми также можно пользоваться и которые приводят к задаче математического программирования. Это

1) минимизация суммы средних квадратов внутригрупповых расстояний;

2) минимизация общей суммы внутригрупповых расстояний;

3) минимизация максимума внутригрупповых расстояний.

С вычислительной точки зрения эти критерии неудобны, за исключением случаев небольших значений пит. Если число групп , то они более удобны. Это значение довольно популярно, если иметь в виду метод Эдвардса и Кавалли-Сфорца [93], который делит все объекты на две компактные группы, и процедура повторяется.