Автоматика и телемеханика, № 2, 2012
© 2012 г. А.В. КЕЛЬМАНОВ, д-р физ.-мат. наук (Институт математики им. С.Л. Соболева Сибирского отделения РАН, Новосибирск),
С.М. РОМАНЧЕНКО (Новосибирский государственный университет)
ПСЕВДОПОЛИНОМИАЛЬНЫЕ АЛГОРИТМЫ ДЛЯ НЕКОТОРЫХ ТРУДНОРЕШАЕМЫХ ЗАДАЧ ПОИСКА ПОДМНОЖЕСТВА ВЕКТОРОВ И КЛАСТЕРНОГО АНАЛИЗА1
Анализируются некоторые ЖР-трудные задачи кластеризации и поиска в заданном множестве векторов евклидова пространства подмножества векторов фиксированной мощности. К этим задачам сводится одна из актуальных проблем анализа данных по критерию минимума суммы квадратов. Обоснованы псевдополиномиальные алгоритмы, гарантирующие отыскание оптимума этих задач в случае, когда компоненты векторов имеют целочисленные значения и размерность пространства фиксирована.
1. Введение
Предметом исследования настоящей работы являются некоторые труднорешае-мые экстремальные задачи поиска подмножества векторов евклидова пространства и кластерного анализа. Цель работы - обоснование алгоритмов для решения этих задач.
Одной из самых известных [1-9] экстремальных задач анализа данных и распознавания образов является задача MSSC (Minimum-Sum-of-Squares Clustering) -кластеризации (разбиения или классификации) конечного множества векторов евклидова пространства по критерию минимума суммы квадратов расстояний. Задача имеет следующую формулировку.
Задача MSSC. Дано: множество У = {y1,..., yN} векторов из Rq, натуральное число J > 1. Найти: 'разбиение множества У на непустые подмножества (кластеры ) Ci,..., CJ такое, что
j
S(CU • • • ,0) = £ £ \\у - y{Ci)f ->■ min,
j=i уеС
где y(Cj) = —— у, j = I,..., J, - центр j-го кластера.
I Cj I j
В некоторых публикациях эта задача фигурирует под названием k-Means, которое соответствует названию алгоритма, предложенного более полувека назад [3] для её решения. На протяжении нескольких десятилетий эта задача считалась NP-трудной. Однако совсем недавно [4] в доказательстве её труднорешаемости была обнаружена ошибка. Это породило новый всплеск исследований по изучению
1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (гранты №09-01-00032, №10-07-00195), целевой программы №2 Президиума РАН (грант №227), целевой программы СО РАН (интеграционный грант №44), целевой программы АВЦП Рос-образования (грант №2.1.1/3235), а также федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» (гос. контракт №14.740.11.0362).
алгоритмической сложности задачи МББС и задач, близких к ней по постановке. Напомним, что одномерный вариант этой задачи разрешим за полиномиальное время [5].
Четыре возможных многомерных случая задачи МББС индуцируются комбинированием размерности пространства и числа кластеров как элементов, которые либо являются, либо не являются частью входа задачи. Если размерность пространства и число кластеров не являются частью входа, то задача разрешима за полиномиальное время [6]. ЖР-трудность остальных трех случаев задачи установлена в [7-9].
В настоящей работе анализируются задачи, близкие к задаче МББС в постановочном плане. Одна из возможных содержательных трактовок проблемы, которая приводит к решению этих задач, состоит в следующем. Имеется таблица, содержащая результаты измерения набора числовых информационно значимых характеристик для совокупности некоторых материальных объектов. Часть объектов из этой совокупности идентичны и имеют одинаковые характеристики. Число идентичных объектов известно. Оставшиеся объекты различны и имеют отличающиеся характеристики. В каждом результате измерения, представленном в таблице, имеется ошибка, причем соответствие между объектом и набором неизвестно. Требуется, используя критерий минимума суммы квадратов расстояний, найти подмножество наборов, соответствующих идентичным объектам, и оценить по результатам измерения набор характеристик этих объектов (учитывая, что данные содержат ошибку измерения).
В [10] было установлено, что эта проблема сводится к четырем тесно связанным между собой труднорешаемым задачам оптимизации квадратичных функций. Одна из этих задач является задачей на максимум, а остальные - на минимум. Формулировки задач приведены в следующем параграфе. Здесь лишь отметим, что в форме верификации свойств эти задачи ЖР-полны в сильном смысле [10]. Поэтому, как известно [11], псевдополиномиальных алгоритмов для их решения не существует (в предположении справедливости гипотезы Р = ЖР). Эти факты послужили стимулом как к обоснованию приближенных алгоритмов, так и к поиску и выделению таких подклассов этих задач, для которых возможно построение точных или приближенных алгоритмов, имеющих полиномиальную или псевдополиномиальную сложность.
В [12] для задач на минимум были предложены эффективные приближенные алгоритмы с константной оценкой точности 2. Для задачи на максимум эффективные алгоритмы с доказуемыми оценками точности на сегодняшний день неизвестны. Ниже обоснованы псевдополиномиальные алгоритмы, гарантирующие оптимальность решения всех упомянутых экстремальных задач в случае, когда компоненты векторов имеют целочисленные значения, а размерность пространства фиксирована.
2. Задачи поиска подмножества векторов и кластерного анализа
Четыре сформулированные ниже задачи поиска подмножества векторов и кластерного анализа индуцируются [10] одной и той же математической моделью содержательной проблемы анализа данных, приведенной во введении.
Задача MSSC-Case. Дано: множество У = {y1,..., yN} векторов из Rq и натуральное число M > 1. Найти: 'разбиение множества У на J = N — M +1 непустых кластеров Ci,..., CJ такое, что мощность одного из этих кластеров равна M и целевая функция S(Ci,..., CJ) задачи MSSC минимальна.
Задача VS-1 (Vector Subset 1). Дано: множество У = {yi,... ,yN} векторов из Rq, натуральное число M > 1. Найти: подмножество C С У векторов такое,
что целевая функция 1
g(C) = 1С |
yec
5> + E
yeY\c
максимальна при ограничении |C| = M на мощность подмножества C.
Задача VS-2 (Vector Subset 2). Дано: множество У = {yi,..., yN} векторов из Rq и натуральное число M > 1. Найти: подмножество C С У векторов такое, что целевая функция
(1) F{C) = Y,\\y-y{C)\\\
yec
где у {С) = — ^2уес У> минимальна при ограничении \С\ = М на мощность искомого |C 1
подмножества.
Задача VS-3 (Vector Subset 3). Дано: множество У = {yi,... ,yN} векторов из Rq, натуральное число M > 1. Найти: подмножество C С У векторов такое, что целевая функция
н (c ) = ЕЕ iiy — zi2
yec zec
минимальна при ограничении |C| = M на мощность искомого подмножества.
Между целевыми функциями задач VS-1, VS-2 и VS-3 имеется однозначное соответствие [10]:
(2) р{С) = ^М2-СЗ(С) = ^ЩС).
yeY 1 1
Кроме того, если считать, что в задаче MSSC-Case мощность, например, j-го кластера Cj зафиксирована и равна M, то имеет место равенство [10]
(3) S(Ci,..., Cj,..., Cj ) = F (Cj),
так как из условий задачи следует, что мощности кластеров из совокупности {Ci,..., Cj,..., CJ}\ Cj равны 1. Поэтому задачи MSSC-Case и VS-2 эквивалентны.
Из связи (2) и (3) целевых функций следует, что по оптимальному или асимптотически оптимальному решению одной из четырех сформулированных задач можно найти соответственно оптимальное или асимптотически оптимальное решение остальных задач. Этот факт используется далее при построении псевдополиномиальных алгоритмов, гарантирующих оптимальное решение задач в случае, когда компоненты векторов имеют целочисленные значения, а размерность пространства фиксирована. В качестве базовой рассматривается задача VS-2.
2
3. Псевдополиномиальные алгоритмы решения задач
Обозначим через С* оптимальное решение задачи У8-2. Положим с* = у (С*), где У(:) - функция, определенная в формулировке этой задачи. Свойство оптимального решения устанавливает
Лемма 1 (см. [12, с. 62]). Для любого вектора у € С* и для любого вектора г € У \ С * справедливо неравенство
\\У - с*У < \\г - с*||.
Лемма 1 показывает, что оптимальное решение задачи VS-2 - подмножество C* С У - состоит из векторов, ближайших к вектору с* по расстоянию. Она устанавливает необходимое условие минимума и указывает на возможный подход к решению задачи.
Суть подхода состоит в следующем. Сначала вычисляется семейство значений функции
(4) G(b)= £ ||y - b||2, b ев,
уеУ(ъ)
где B - некоторое специально построенное (см. далее) конечное множество векторов из Rq, а подмножество У(b) С У состоит из M векторов, ближайших к вектору b по расстоянию. Затем в качестве решения задачи выбирается подмножество У(b) С У, для которого значение функции (4) имеет наименьшее значение. Иными словами, алгоритмическое решение ищется в виде
(5) СА = У{ЬА), сА = у{СА), где
(6) bA = argmin G(b).
ьев
В соответствии с формулировкой задачи VS-2 для значения целевой функции, найденного алгоритмом, далее положим
(7) Fa = F (Ca).
Допустим, что компоненты векторов из множества У имеют целочисленные значения. Положим
(8) B = max max |(y)j |,
УеУ je{i,...,q}
где (y)j - j-я компонента вектора у. Определим множество
(9) В={б| = Кг»)3'! ^МВ, j =
векторов. Заметим, что
(10) |B| = (2MB +l)q.
Наконец, допустим, что векторы из множества B упорядочены, например, в лексикографическом порядке.
Изложим алгоритм решения задачи VS-2 в виде псевдокода. Алгоритм 1.
1. Найдём значение B и мощность |B| множества B по формулам (8) и (10). Положим Ca = 0, Gmin = i = 0.
2. i := i +1; в соответствии с (9) сформируем i-й элемент bj множества B, учитывая лексикографический порядок его элементов, и положим b = bj.
3. Найдем множество У(b) ближайших к b векторов из множества У.
4. Вычислим значение G(b) функции (4).
5. Если G(b) ^ Gmin, то положим Gmin = G(b), Ca = У(b); иначе переходим к следующему шагу.
6. Если г < |В|, то переходим на шаг 2; иначе - к следующему шагу.
7. Подмножество Са, значение Ра = Р(Са) объявляем результатом работы алгоритма. Выход.
Связь между оптимальным и алгоритмическим решениями устанавливает
Лемма 2. Пусть в условиях задачи УБ-2 компоненты всех векторов из множества У имеют целочисленные значения в интер
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.