научная статья по теме NP-ТРУДНОСТЬ НЕКОТОРЫХ КВАДРАТИЧНЫХ ЕВКЛИДОВЫХ ЗАДАЧ 2-КЛАСТЕРИЗАЦИИ Математика

Текст научной статьи на тему «NP-ТРУДНОСТЬ НЕКОТОРЫХ КВАДРАТИЧНЫХ ЕВКЛИДОВЫХ ЗАДАЧ 2-КЛАСТЕРИЗАЦИИ»

ДОКЛАДЫ АКАДЕМИИ НАУК, 2015, том 464, № 5, с. 535-538

-- ИНФОРМАТИКА

УДК 519.16+519.85

^-ТРУДНОСТЬ НЕКОТОРЫХ КВАДРАТИЧНЫХ ЕВКЛИДОВЫХ ЗАДАЧ

2-КЛАСТЕРИЗАЦИИ © 2015 г. А. В. Кельманов, А. В. Пяткин

Представлено академиком РАН Ю.И. Журавлевым 31.03.2015 г.

Поступило 13.04.2015 г.

Рассматриваются задачи двухкластерного разбиения конечного множества точек евклидова пространства. В этих задачах минимизируются следующие критерии: 1) сумма по обоим кластерам суммы квадратов попарных расстояний между элементами кластера, 2) сумма умноженных на мощность кластеров сумм квадратов расстояний от элементов кластера до его геометрического центра. Под геометрическим центром кластера (центроидом) понимается точка, равная среднему значению элементов кластера. Кроме того, рассматривается близкая к 2) в постановочном плане задача, в которой на входе задан желаемый центр одного из кластеров, а центр другого, как и в задаче 2), неизвестен (является оптимизируемой переменной). Анализируются варианты задач, в которых мощности кластеров заданы на входе либо неизвестны. Установлено, что все рассмотренные задачи МР-трудны в сильном смысле и для общего случая этих задач не существует полностью полиномиальной приближенной схемы (БРТЛ8), если Р Ф МР.

Б01: 10.7868/80869565215290058

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

Задача разбиения конечного множества на несколько подмножеств (кластеров) имеет приложения в компьютерной геометрии, теории графов, анализе данных и распознавании образов. Эта задача индуцируется многими естественно -научными и техническими проблемами, в частности в таких областях, как обработка изображений, статистическая физика, биоинформатика, проектирование микросхем и др. Задача играет ключевую роль в проблемах классификации и интерпретации наблюдаемых данных. Среди множества разнообразных задач кластеризации задачи 2-кластеризации (т.е. разбиения всего на два подмножества), как простейшие, имеют фундаментальное значение. Несколько таких задач рассматриваются в настоящей работе.

Институт математики им. С.Л. Соболева Сибирского отделения Российской Академии наук, Новосибирск

Новосибирский государственный университет E-mail: kelm@math.nsc.ru

1. Одна из рассматриваемых задач — Min-Sum bi-clustering. Эта задача впервые была сформулирована в [1], рассматривалась также в [2]. В этих работах показано, что она относится к числу NP-трудных задач. В терминах теории графов она имеет следующую формулировку. Задан неориентированный взвешенный граф с неотрицательными весами на ребрах. Требуется разбить множество вершин на две части таким образом, чтобы суммарный по обоим кластерам вес суммы внут-рикластерных весов ребер был минимален. Труд-норешаемость метрического случая этой задачи, который называют еще как Min-Sum All-Pairs bi-clustering (см., например, [3, 4]), установлена в цитируемых работах.

Мы анализируем геометрический случай этой задачи, в котором вершины заданы точками евклидова пространства, а веса ребер — квадратами расстояний между этими точками. Ниже эта задача называется Quadratic Euclidean Min-Sum All-Pairs bi-clustering. Вопрос о статусе вычислительной сложности этой задачи до последнего времени оставался открытым.

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

536

КЕЛЬМАНОВ, ПЯТКИН

2. Кроме того, в настоящей работе рассматривается задача кластеризации, тесно связанная с упомянутой выше задачей Min-Sum 2-clustering. В публикациях эта задача имеет название Balanced Variance-based 2-clustering [5]. В этой задаче требуется минимизировать сумму (по обоим кластерам) умноженных на мощность искомых кластеров сумм квадратов внутрикластерных расстояний от элементов кластеров до их геометрических центров. Под геометрическим центром кластера (или центроидом) понимается точка, равная среднему значению элементов кластера. Мы анализируем сложностной статус евклидова случая этой задачи и называем его Euclidean Balanced Variance-based 2-clustering. Статус вычислительной сложности этой задачи ранее также не был установлен.

В отличие от задачи Euclidean Balanced Variance-based 2-clustering, в хорошо известной известной труднорешаемой [6] задаче MSSC (Minimum Sum-of-Squares Clustering) минимизируется сумма по обоим кластерам внутрикластерных сумм квадратов расстояний от элементов кластера до его геометрического центра, т.е. умножение (как балансировка) внутрикластерных сумм на мощности искомых кластеров отсутствует.

3. Наконец, еще одна задача 2-кластеризации, рассматриваемая в настоящей работе, в постановочном плане близка к упомянутой выше задаче Euclidean Balanced Variance-based 2-clustering, но не эквивалентна ей. Мы называем эту задачу Euclidean Balanced Variance-based 2-clustering with given center. В этой задаче предполагается, что на входе задачи в некоторой точке евклидова пространства (без потери общности — в начале координат) задан желаемый центр одного из кластеров.

Напомним, что задачи кластеризации, близкие в постановочном плане к задаче MSSC, в которых на входе для нескольких кластеров задаются желаемые геометрические центры, а другие центры — оптимизируемые переменные, впервые были рассмотрены в [7—10] и там же установлено, что эти задачи NP-трудны даже в 2-кластерном случае, когда задан один желаемый геометрический центр, а другой — неизвестен.

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

Рассматриваемая в настоящей работе задача Euclidean Balanced Variance-based 2-clustering with given center относится к числу новых (ранее не изучавшихся) задач.

Заметим, что размерность пространства считается частью входа во всех сформулированных ниже задачах.

Задача 1. Quadratic Euclidean Min-Sum All-Pairs 2-clustering. Дано: множество ЗД = {y1, ..., yN} точек из f^. Найти: разбиение множества ЗД на два непустых подмножества Ж и % таких, что h (Ж, %) =

- XXII--z2 + XXII--Z1

х е Жг е Ж - е %z е %

Задача 2. Euclidean Balanced Variance-based 2-clustering. Дано: множество ЗД = {y1, ..., yN} точек из f^. Найти: разбиение множества ЗД на два непустых подмножества Ж и % таких, что

^ min.

(1)

g(ж, %) = m £ il* - х(ж)ii2

+

1X11*

г е %

х е Ж

- г

^ min,

(2)

где - (Ж) = Ж X - и z (%) = X г - геометриче-

х е Ж z е %

ские центры подмножеств Ж и % соответственно.

Задача 3. Euclidean Balanced Variance-based 2-clustering with given center. Дано: множество ЗД = {y1, ..., yN} точек из Найти: разбиение множества ЗД на два непустых подмножества Ж и % таких, что

f(Ж, %) = \Ж\ X II- - -(Ж)||2 + |%| X И2 ^ min,(3)

х е Ж

г е %

где х (Ж) = -Ж- X * — геометрический центр под-

ж

х е Ж

множества Ж.

Утверждения о сложности первых двух задач легко устанавливаются с помощью недавно опубликованного результата о сильной NP-трудности квадратичной евклидовой задачи Max-Cut [11, 12]. В цитированных работах к этой задаче построено полиномиальное сведение задачи Minimum Bisection для кубических графов [13]. Для доказательства сильной NP-трудности третьей задачи мы используем аналогичное сведение, но строим другой пример входа анализируемой задачи. Далее, опираясь на [14], мы показываем, что для всех рассмотренных задач не существует полностью полиномиальной приближенной схемы (FPTAS), если P Ф NP. Наконец, устанавливаем NP-трудность этих задач в случае, когда мощности кластеров заданы на их входе.

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

Теорема. Задачи 1, 2 и 3 NP-трудны в сильном смысле.

+

NP-ТРУДНОСТЬ НЕКОТОРЫХ КВАДРАТИЧНЫХ ЕВКЛИДОВЫХ ЗАДАЧ

537

Для доказательства труднорешаемости задачи 1 мы используем полиномиальное сведение к ней следующей NP-трудной в сильном смысле [12] задачи.

Задача Quadratic Euclidean Max-Cut. Дано: множество ЗД = {y1, ..., yN} точек из [Rq. Найти: разбиение множества ЗД на два подмножества Ж и % таких, что

X X 1Ь - z\\2 ^ max.

х е Ж z е %

Легко установить справедливость следующего равенства:

h (Ж, %) = XX \\х - z||2 - XX ||х - zll2.

х е ЗД z е ЗД

х е Ж z е %

В правой части этого равенства первая двойная сумма — константа, а вторая — целевая функция задачи Quadratic Euclidean Max-Cut. Следовательно, целевая функция ^Ж, %) задачи 1 минимальна тогда и только тогда, когда максимальна целевая функция NP-трудной в сильном смысле задачи Quadratic Euclidean Max-Cut.

Для доказательства труднорешаемости задач 2 и 3 используется хорошо известный факт (тождество): для любого непустого конечного множества ЗД точек евклидова пространства и геометрического центра y (ЗД) = -ЗД X У этого множества

У е ЗД

справедливо

XX Их - zll2 = 21ЗД| X 1У - У(ЗД )112

х е ЗД z е ЗД

y е ЗД

Применяя это тождество к множествам Ж и Ж и их геометрическим центрам, установим связь между целевыми функциями (1) и (2):

Н(Ж, Ж) = 2g(Ж, Ж). (4)

Аналогичным образом для целевой функции (3) задачи 3 получим

я ж, ж ) = 1xx1 - ^2+ж x и2.

(5)

A =

х е Ж z е Ж У е %

Из (4) видно, что отыскание минимума задачи 2 эквивалентно отысканию минимума задачи 1. Отсюда следует труднорешаемость задачи 2.

Факт труднорешаемост

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком