1. На главную
  2. Электронные версии
  3. Журнал вычислительной математики и математической физики
  4. T. 60, № 1, 2020

Журнал вычислительной математики и математической физики, 2020, T. 60, № 1, стр. 151-158

О сложности некоторых квадратичных задач разбиения конечного множества точек евклидова пространства на сбалансированные кластеры

А. В. Кельманов 1, 2, *, А. В. Пяткин 1, 2, **, В. И. Хандеев 1, 2, ***

1 Ин-т матем. им. С.Л. Соболева
630090 Новосибирск, пр-т акад. Коптюга, 4, Россия

2 Новосибирский гос. ун-т
630090 Новосибирск, ул. Пирогова, 2, Россия

* E-mail: kelm@math.nsc.ru
** E-mail: artem@math.nsc.ru
*** E-mail: khandeev@math.nsc.ru

Поступила в редакцию 20.05.2019
После доработки 20.05.2019
Принята к публикации 18.09.2019

Полный текст (PDF)

Аннотация

Рассматриваются три родственные между собой задачи разбиения $N$-элементного множества точек $d$-мерного евклидова пространства на два кластера так, чтобы сбалансировать значения: (1) внутрикластерного квадратичного разброса, нормированного на размер кластера, в первой задаче; (2) внутрикластерного квадратичного разброса, во второй задаче; (3) мощностно-взвешенного внутрикластерного разброса, в третьей задаче. Доказано, что все эти задачи NP-полны. Библ. 17.

Ключевые слова: eвклидово пространство, сбалансированное разбиение, квадратичный разброс, нормированный на размер кластера разброс, мощностно-взвешенный разброс, NP-полнота.

1. ВВЕДЕНИЕ

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

Исследование мотивировано открытостью указанного вопроса, а также важностью рассматриваемых задач как для математической теории оптимизации и вычислительной математики, так и для приложений, среди которых, в частности, анализ данных (Data analysis), интерпретация данных (Data mining) и статистика (Statistics). Примеры приложений приведены в следующем разделе.

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

2. ФОРМУЛИРОВКИ ЗАДАЧ И СВЯЗАННЫЕ С НИМИ ПРОБЛЕМЫ

Классическая математическая статистика и относительно новая дисциплина Data mining [1], [2], [3], [4] имеют похожие цели: и та, и другая ориентированы на анализ структур экспериментальных данных. Тем не менее имеется существенное отличие этих дисциплин. Оно обусловлено отличием математических задач, на решение которых фокусируются эти дисциплины, и, как следствие, – отличием создаваемых и применяемых математических инструментов в виде методов и алгоритмов.

Статистика ориентирована исключительно на анализ однородных выборочных данных (т.е. данных, принадлежащих одному и тому же распределению) или сопоставление (сравнение) выборочных данных, принадлежащих разным однородным распределениям. Data mining ставит своей целью выяснение (дословно – “раскопку”) структуры данных, которые, как правило, принадлежат разным распределениям, в условиях отсутствия информации о соответствии данных распределению [1], [2], [3], [4]. По сути, статистические методы как инструменты пригодны лишь для применения к частным случаям разнообразных проблем в Data mining.

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

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

Существует множество оптимизационных задач разбиения конечного множества объектов (точек) на кластеры по разнообразным критериям. Большинство из известных практически важных для Data mining задач разбиения данных на кластеры NP-трудны (см. цитируемые ниже работы). Однако у еще большей части задач статус вычислительной сложности остается не раскрытым. В настоящей работе мы рассматриваем несколько таких задач, которые по смыслу тесно связаны как с классическими задачами проверки статистических гипотез, так и с некоторыми прикладными проблемами (см. далее).

Заметим еще, что рассматриваемые задачи разбиения на кластеры не эквивалентны ни одной из хорошо известных труднорешаемых кластеризационных задач $k$-means (или $k$-MSSC) [5], [6], $k$-median [7], [8], $k$-cеnter [9], [10], $k$-Variance [11] и др. [12], [13], [14], [15]. Насколько нам известно, рассматриваемые задачи также не эквивалентны ни одной из других труднорешаемых квадратичных евклидовых задач разбиения, выявленных в последние годы. Этот факт, как и сказанное выше, мотивировал наше исследование.

Всюду далее $\left\| {\, \cdot \,} \right\|$ – евклидова норма. Рассматриваемые задачи имеют следующие формулировки в форме верификации свойств.

Задача 1 (cбалансированное 2-разбиение по дисперсионному критерию). Дано: $N$-элементное множество $\mathcal{Y}$ точек в евклидовом пространстве размерности $d$ и некоторое вещественное число $\varepsilon > 0$. Вопрос: существует ли такое разбиение множества $\mathcal{Y}$ на непустые кластеры $\mathcal{C}$ и $\mathcal{Y}{\backslash }\mathcal{C}$, что

(1.1)
$\left| {\frac{1}{{\left| \mathcal{C} \right|}}\sum\limits_{y \in \mathcal{C}} {{{{\left\| {y - \bar {y}(\mathcal{C})} \right\|}}^{2}}} - \frac{1}{{\left| {\mathcal{Y}{\backslash }\mathcal{C}} \right|}}\sum\limits_{y \in \mathcal{Y} \setminus \mathcal{C}} {{{{\left\| {y - \bar {y}(\mathcal{Y}{\backslash }\mathcal{C})} \right\|}}^{2}}} } \right| \leqslant \varepsilon ,$
где $\bar {y}(\mathcal{C}) = \tfrac{1}{{\left| \mathcal{C} \right|}}\sum\nolimits_{y \in \mathcal{C}} y $ и $\bar {y}(\mathcal{Y}{\backslash }\mathcal{C}) = \tfrac{1}{{\left| {\mathcal{Y}{\backslash }\mathcal{C}} \right|}}\sum\nolimits_{y \in \mathcal{Y}{\backslash }\mathcal{C}} y $ – центроиды (геометрические центры) кластеров $\mathcal{C}$ и $\mathcal{Y}{\backslash }\mathcal{C}$ соответственно?

Задача 2 (cбалансированное 2-разбиение по критерию суммарного квадратичного разброса). Дано: $N$-элементное множество $\mathcal{Y}$ точек в евклидовом пространстве размерности $d$ и некоторое вещественное число $\varepsilon > 0$. Вопрос: существует ли такое разбиение множества $\mathcal{Y}$ на непустые кластеры $\mathcal{C}$ и $\mathcal{Y}{\backslash }\mathcal{C}$, что

(1.2)
$\left| {\sum\limits_{y \in \mathcal{C}} {{{{\left\| {y - \bar {y}(\mathcal{C})} \right\|}}^{2}}} - \sum\limits_{y \in \mathcal{Y}{\backslash }\mathcal{C}} {{{{\left\| {y - \bar {y}(\mathcal{Y}{\backslash }\mathcal{C})} \right\|}}^{2}}} } \right| \leqslant \varepsilon ?$

Задача 3 (cбалансированное 2-разбиение по критерию мощностно-взвешенного суммарного квадратичного разброса). Дано: $N$-элементное множество $\mathcal{Y}$ точек в евклидовом пространстве размерности $d$ и некоторое вещественное число $\varepsilon > 0$. Вопрос: существует ли такое разбиение множества $\mathcal{Y}$ на непустые кластеры $\mathcal{C}$ и $\mathcal{Y}{\backslash }\mathcal{C}$, что

(1.3)
$\left| {\left| {\mathcal{C}{\kern 1pt} } \right|\sum\limits_{y \in \mathcal{C}} {{{{\left\| {y - \bar {y}(\mathcal{C}{\kern 1pt} )} \right\|}}^{2}}} - \left| {\mathcal{Y}{\backslash }\mathcal{C}{\kern 1pt} } \right|\sum\limits_{y \in \mathcal{Y}{\backslash }\mathcal{C}} {{{{\left\| {y - \bar {y}(\mathcal{Y}{\backslash }\mathcal{C})} \right\|}}^{2}}} } \right| \leqslant \varepsilon ?$

В статистике хорошо известен критерий Фишера сравнения дисперсий ($F$-критерий) по выборочным данным из двух распределений [16]. Если рассматривать кластеры $\mathcal{C}$ и $\mathcal{Y}{\backslash }\mathcal{C}$ как выборки из двух нормальных распределений с неизвестными средними, то этот критерий позволяет сравнить (проверить на равенство) выборочные дисперсии

(1.4)
$\frac{1}{{\left| \mathcal{C} \right| - 1}}\sum\limits_{y \in \mathcal{C}} {{{{\left\| {y - \bar {y}(\mathcal{C})} \right\|}}^{2}}} $
и
(1.5)
$\frac{1}{{\left| {\mathcal{Y}{\backslash }\mathcal{C}} \right| - 1}}\sum\limits_{y \in \mathcal{Y}{\backslash }\mathcal{C}} {{{{\left\| {y - \bar {y}(\mathcal{Y}{\backslash }\mathcal{C})} \right\|}}^{2}}} $
этих распределений по их отношению, которое близко к 1 в случае равенства.

Формулы (1.4) и (1.5) в статистике известны как несмещенные оценки дисперсии по выборочным данным. В задаче 1 фигурируют смещенные оценки, которые отличаются от несмещенных лишь знаменателями. Однако это отличие, как известно, несущественно в асимптотическом смысле, т.к. обе оценки являются асимптотически несмещенными.

Легко видеть, что в задаче 1 требуется разбить входное множество $\mathcal{Y}$ на два кластера по критерию сбалансированных выборочных дисперсий. Статистическая интерпретация задачи 1: можно ли разбить неоднородную выборку $\mathcal{Y}$ на две части (подвыборки) $\mathcal{C}$ и $\mathcal{Y}{\backslash }\mathcal{C}$ с выборочными дисперсиями, которые отличаются не более, чем на некоторое заданное число $\varepsilon > 0$?

Задачи 2 и 3 аналогичны по смыслу задаче 1, но отличаются критериями разбиения. В задаче 2 критерием является суммарный квадратичный разброс относительно среднего (т.е. центроида). В задаче 3 таким критерием является мощностно-взвешенный разброс относительно центроида или сумма квадратов попарных расстояний, так как для любого конечного множества $\mathcal{Z} \subset {{\mathbb{R}}^{d}}$ справедливо легко проверяемое равенство

(1.6)
$\left| \mathcal{Z} \right|\sum\limits_{z \in \mathcal{Z}} {{{{\left\| {z - \bar {z}(\mathcal{Z})} \right\|}}^{2}}} = \frac{1}{2}\sum\limits_{z \in \mathcal{Z}} {\sum\limits_{x \in \mathcal{Z}} {{{{\left\| {z - x} \right\|}}^{2}}} } ,$
где $\bar {z}(\mathcal{Z})$ – центроид множества $\mathcal{Z}$.

Статистические трактовки задач 2–3 в виде 2-разбиений неоднородной выборки $\mathcal{Y}$ аналогичны статистической трактовке задачи 1.

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

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

3. АНАЛИЗ СЛОЖНОСТИ

Для выяснения статуса вычислительной сложности сформулированных задач рассмотрим сначала следующую задачу, которая объединяет задачи 1–3.

Задача $\Pi (g(x))$. Дано: $N$-элементное множество $\mathcal{Y}$ точек в евклидовом пространстве размерности $d$ и вещественное число $\varepsilon > 0$. Вопрос: существует ли такое разбиение множества $\mathcal{Y}$ на непустые кластеры $\mathcal{C}$ и $\mathcal{Y}{\backslash }\mathcal{C}$, что

(1.7)
$\left| {\frac{1}{2}g(\left| \mathcal{C} \right|)\sum\limits_{y \in \mathcal{C}} {\sum\limits_{z \in \mathcal{C}} {{{{\left\| {y - z} \right\|}}^{2}}} } - \frac{1}{2}g(\left| {\mathcal{Y}{\backslash }\mathcal{C}} \right|)\sum\limits_{y \in \mathcal{Y}{\backslash }\mathcal{C}} {\sum\limits_{z \in \mathcal{Y}{\backslash }\mathcal{C}} {{{{\left\| {y - z} \right\|}}^{2}}} } } \right| \leqslant \varepsilon ?$

С учетом (1.6), будем считать, что весовой коэффициент $g(x)$ у сумм в неравенстве (1.7) объединенной задачи равен $1{\text{/}}{{x}^{2}}$ для задачи 1, $1{\text{/}}x$ – для задачи 2 и 1 – для задачи 3, где $x$ – мощность соответствующего кластера.

Докажем NP-полноту задачи $\Pi (g(x))$ для каждой функции $g(x)$ из множества $\left\{ {\tfrac{1}{{{{x}^{2}}}},\tfrac{1}{x},1} \right\}$. Воспользуемся известным NP-полным вариантом классической задачи Разбиение, которая имеет следующую формулировку [17].

Задача РРД (разбиение с равными долями). Дано мультимножество из $2K$ целых неотрицательных чисел ${{a}_{1}},\; \ldots ,\;{{a}_{{2K}}}$, сумма которых равна $2W$. Вопрос: существует ли разбиение этого мультимножества на два мультиподмножества по $K$ элементов каждое с суммой элементов в каждом из мультиподмножеств, равной $W$?

Справедлива

Теорема 1. Для каждой функции $g(x) \in \left\{ {\tfrac{1}{{{{x}^{2}}}},\tfrac{1}{x},1} \right\}$ задача $\Pi (g(x))$ NP-полна.

Доказательство. Рассмотрим произвольный пример задачи РРД, т.е. мультимножество $A = {\text{\{ }}{{a}_{1}},\; \ldots ,\;{{a}_{{2K}}}{\text{\} }}$, сумма элементов которого равна $2W$. Можно считать, что $K > 3$, а также, что $W \geqslant 9$, так как в противном случае задача, очевидно, решается за линейное время с помощью полного перебора или с помощью динамического программирования соответственно.

Положим $\varepsilon = \tfrac{1}{{3K}}$ и выберем рациональные числа ${{b}_{i}}$, $i = 1,\; \ldots ,\;2K$, удовлетворяющие соотношению

(1.8)
$\sqrt {{{a}_{i}}} \leqslant {{b}_{i}} \leqslant \sqrt {{{a}_{i}}} + \delta ,$
где

(1.9)
$\delta = \frac{\varepsilon }{{K(K - 1)Wg(K)}}.$

По произвольному входу задачи РРД построим пример входа задачи $\Pi (g(x))$. Положим $N = 2K$, $d = 4K$, $\mathcal{Y} = {\text{\{ }}{{y}_{1}},\; \ldots ,\;{{y}_{{2K}}}{\text{\} }}$, где для всех $i = 1,\; \ldots ,\;2K$ точка ${{y}_{i}}$ содержит рациональное число (параметр) $M > 0$ в компоненте $i$ и число ${{b}_{i}}$ в компоненте $2K + i$, а все остальные компоненты этой точки равны $0$.

Значения параметра $M$ уточним далее в зависимости от функции $g(x) \in \left\{ {\tfrac{1}{{{{x}^{2}}}},\tfrac{1}{x},1} \right\}$.

Зафиксируем некоторые свойства элементов семейства $\mathcal{Y}$ точек в построенном примере входа задачи $\Pi (g(x))$.

Свойство 1. Пусть подмножество $I \subset {\text{\{ }}1, \ldots ,\;2K{\text{\} }}$ содержит номера точек из кластера $\mathcal{C} \subset \mathcal{Y}$. Тогда для точек из $\mathcal{C}$ справедливо равенство:

(1.10)
$\sum\limits_{y \in \mathcal{C}} {\sum\limits_{z \in \mathcal{C}} {{{{\left\| {y - z} \right\|}}^{2}}} } = 2\left| \mathcal{C} \right|(\left| \mathcal{C} \right| - 1){{M}^{2}} + 2(\left| \mathcal{C} \right| - 1)\sum\limits_{i \in I} {b_{i}^{2}} ,$
которое следует из того, что в построенном примере для всех $i \ne j$, очевидно, выполнено

${{\left\| {{{y}_{i}} - {{y}_{j}}} \right\|}^{2}} = 2{{M}^{2}} + b_{i}^{2} + b_{j}^{2}.$

Далее, заметим, что согласно (1.8) имеет место оценка

(1.11)
${{a}_{i}} \leqslant b_{i}^{2} \leqslant {{a}_{i}} + {{\delta }^{2}} + 2\delta \sqrt {{{a}_{i}}} \leqslant {{a}_{i}} + \delta (\delta + 2\sqrt {2W} ) \leqslant {{a}_{i}} + W\delta ,$
поскольку $W > \delta + 2\sqrt {2W} $ при $W \geqslant 9$ и $\delta < \tfrac{1}{2}$.

Просуммировав неравенства (1.11), получим

Свойство 2. Для суммы квадратов координатных элементов (1.8) справедлива оценка

(1.12)
$\sum\limits_{i = 1}^{2K} {b_{i}^{2}} \leqslant 2W(1 + K\delta ).$

Свойство 3. Для любого разбиения множества ${\text{\{ }}1,\; \ldots ,\;2K{\text{\} }}$ индексов на подмножества ${{I}_{1}}$, ${{I}_{2}}$ одинаковой мощности $K$ имеют место неравенства

(1.13)
$\left| {\sum\limits_{i \in {{I}_{1}}} {{{a}_{i}}} - \sum\limits_{i \in {{I}_{2}}} {{{a}_{i}}} } \right| - KW\delta \leqslant \left| {\sum\limits_{i \in {{I}_{1}}} {b_{i}^{2}} - \sum\limits_{i \in {{I}_{2}}} {b_{i}^{2}} } \right| \leqslant \left| {\sum\limits_{i \in {{I}_{1}}} {{{a}_{i}}} - \sum\limits_{i \in {{I}_{2}}} {{{a}_{i}}} } \right| + KW\delta ,$
так как
$\sum\limits_{i \in {{I}_{1}}} {a_{i}^{2}} \leqslant \sum\limits_{i \in {{I}_{1}}} {b_{i}^{2}} \leqslant \sum\limits_{i \in {{I}_{1}}} {a_{i}^{2}} + KW\delta $
и
$\sum\limits_{i \in {{I}_{2}}} {a_{i}^{2}} \leqslant \sum\limits_{i \in {{I}_{2}}} {b_{i}^{2}} \leqslant \sum\limits_{i \in {{I}_{2}}} {a_{i}^{2}} + KW\delta $
в соответствии с (1.11).

Допустим теперь, что подмножество ${{I}_{1}}$ индексов содержит номера точек из $\mathcal{C}$, а подмножество ${{I}_{2}}$ – номера точек из $\mathcal{Y}{\backslash }\mathcal{C}$, причем $\left| {{{I}_{1}}} \right| = c$. Тогда в задаче $\Pi (g(x))$ неравенство (1.7) при $x = c$ в соответствии с (1.10) принимает вид:

(1.14)
$\begin{gathered} \left| {(\mathop c\limits_{_{{_{{_{{_{{_{{_{{}}}}}}}}}}}}}^{} (c - 1)g(c) - (2K - c)(2K - c - 1)g(2K - c)){{M}^{2}}} \right. + \\ + \;\;(c - 1)g(c)\sum\limits_{i \in {{I}_{1}}} {b_{i}^{2}} - (2K - c - 1)g(2K - c)\left. {\sum\limits_{i \in {{I}_{2}}} {b_{i}^{2}} } \right| \leqslant \varepsilon . \\ \end{gathered} $

Если в задаче РРД существует разбиение мультимножества $A$ на два требуемых подмножества, то для соответствующих подмножеств индексов выполняется равенство

(1.15)
$c = \left| {{{I}_{1}}} \right| = \left| {{{I}_{2}}} \right| = K$
и равенство
(1.16)
$\sum\limits_{i \in {{I}_{1}}} {{{a}_{i}}} = \sum\limits_{i \in {{I}_{2}}} {{{a}_{i}}} .$
Тогда, подставив (1.15) в (1.14) и учитывая (1.13) и (1.16), легко заметить, что для выполнения неравенства (1.7) в задаче $\Pi (g(x))$ достаточно, чтобы
$(K - 1)g(K)\left| {\sum\limits_{i \in {{I}_{1}}} {b_{i}^{2}} - \sum\limits_{i \in {{I}_{2}}} {b_{i}^{2}} } \right| \leqslant K(K - 1)g(K)W\delta \leqslant \varepsilon ,$
что выполняется, если имеет место равенство (1.9).

Таким образом, если в задаче РРД существует требуемое разбиение, то и в задаче $\Pi (g(x))$ требуемое разбиение также существует при выборе параметра $\delta $ по формуле (1.9).

Для доказательства обратной импликации укажем значение параметра $M$ для каждой из трех функций $g(x) \in \left\{ {\tfrac{1}{{{{x}^{2}}}},\tfrac{1}{x},1} \right\}$ в объединенной задаче $\Pi (g(x))$. Рассмотрим три случая.

I. При $g(x) = 1$ (что соответствует задаче 3) из (1.9) имеем

$\delta = \frac{\varepsilon }{{K(K - 1)W}}.$
При этом неравенство (1.14) в задаче $\Pi (g(x))$ принимает вид
$\varepsilon \geqslant \left| {(4Kc - 4{{K}^{2}} + 2K - 2c){{M}^{2}} + (c - 1)\sum\limits_{i \in {{I}_{1}}} {b_{i}^{2}} - (2K - c - 1)\sum\limits_{i \in {{I}_{2}}} {b_{i}^{2}} } \right|.$
Оценивая модуль суммы в правой части этого неравенства, с учетом (1.12) получим
(1.17)
$\begin{gathered} \varepsilon \geqslant \left| {2(K - c)(1 - 2K){{M}^{2}}} \right| - (c - 1)\sum\limits_{i \in {{I}_{1}}} {b_{i}^{2}} - (2K - c - 1)\sum\limits_{i \in {{I}_{2}}} {b_{i}^{2}} \geqslant \\ \geqslant \;2\left| {K - c} \right|(2K - 1){{M}^{2}} - 4KW(K\delta + 1) \geqslant \left| {K - c} \right|{{M}^{2}} - 4KW(K\delta + 1), \\ \end{gathered} $
так как $2(2K - 1) > 1$.

Выберем параметр $M$ так, что

${{M}^{2}} > \varepsilon + 4KW(K\delta + 1).$
Тогда коэффициент при ${{M}^{2}}$ в правой части (1.17) должен быть равен 0. Действительно, если $K \ne c$, то $\left| {K - c} \right| \geqslant 1$, и из неравенства (1.17) следует
$\varepsilon \geqslant {{M}^{2}} - 4KW(K\delta + 1) > \varepsilon ,$
противоречие. Таким образом, $\left| {K - c} \right| = 0$, а значит, $K = c$.

Далее, из целочисленности элементов мультимножества $A$ следует: если в задаче РРД

(1.18)
$\sum\limits_{i \in {{I}_{1}}} {{{a}_{i}}} \ne \sum\limits_{i \in {{I}_{2}}} {{{a}_{i}}} ,$
то
(1.19)
$\left| {\sum\limits_{i \in {{I}_{1}}} {{{a}_{i}}} - \sum\limits_{i \in {{I}_{2}}} {{{a}_{i}}} } \right| \geqslant 1.$
Поэтому из неравенства (1.14) с учетом (1.13) имеем
$\varepsilon \geqslant (K - 1)\left| {\sum\limits_{i \in {{I}_{1}}} {b_{i}^{2}} - \sum\limits_{i \in {{I}_{2}}} {b_{i}^{2}} } \right| \geqslant (K - 1)(1 - KW\delta ) = K - 1 - \varepsilon ,$
что противоречит условию $\varepsilon = \tfrac{1}{{3K}}$. Следовательно, в задаче РРД выполнено равенство (1.16).

II. Если $g(x) = 1{\text{/}}x$ (что соответствует задаче 2), то из (1.9) имеем

$\delta = \frac{\varepsilon }{{(K - 1)W}}.$
При этом неравенство (1.14) имеет вид
$\varepsilon \geqslant \left| {(c - 1 - (2K - c - 1)){{M}^{2}} + \frac{{c - 1}}{c}\sum\limits_{i \in {{I}_{1}}} {b_{i}^{2}} - \frac{{2K - c - 1}}{{2K - c}}\sum\limits_{i \in {{I}_{2}}} {b_{i}^{2}} } \right|.$
Оценивая модуль суммы в правой части этого неравенства, с учетом (1.12) получаем

(1.20)
$\varepsilon \geqslant \left| {2(c - K)} \right|{{M}^{2}} - \sum\limits_{i = 1}^{2K} {b_{i}^{2}} \geqslant 2\left| {K - c} \right|{{M}^{2}} - 2W(K\delta + 1).$

Выберем параметр $M$ так, что

${{M}^{2}} > \varepsilon + 2W(K\delta + 1).$
Тогда при этом выборе параметра $M$ из (1.20) имеем $K = c$, как и в случае I.

Далее, как и в рассмотренном случае I, если в задаче РРД имеет место неравенство (1.18), то из этого неравенства следует (1.19). Поэтому из (1.14) с учетом (1.13) имеем

$\varepsilon \geqslant \frac{{K - 1}}{K}\left| {\sum\limits_{i \in {{I}_{1}}} {b_{i}^{2}} - \sum\limits_{i \in {{I}_{2}}} {b_{i}^{2}} } \right| \geqslant \frac{{K - 1}}{K}(1 - KW\delta ) = \frac{{K - 1}}{K} - \varepsilon ,$
что противоречит условиям $\varepsilon = \tfrac{1}{{3K}}$ и $K > 3$. Следовательно, в задаче РРД выполнено равенство (1.16).

III. Наконец, при $g(x) = 1{\text{/}}{{x}^{2}}$ (что соответствует задаче 1) из (1.9) имеем

$\delta = \frac{{K\varepsilon }}{{(K - 1)W}}.$
При этом неравенство (1.14) имеет вид
$\varepsilon \geqslant \left| {\left( {\frac{{c - 1}}{c} - \frac{{2K - c - 1}}{{2K - c}}} \right){{M}^{2}} + \frac{{c - 1}}{{{{c}^{2}}}}\sum\limits_{i \in {{I}_{1}}} {b_{i}^{2}} - \frac{{2K - c - 1}}{{{{{(2K - c)}}^{2}}}}\sum\limits_{i \in {{I}_{2}}} {b_{i}^{2}} } \right|.$
Оценивая модуль суммы в правой части этого неравенства, с учетом (1.12) получаем

(1.21)
$\varepsilon \geqslant \left| {\frac{{2(K - c)}}{{c(2K - c)}}} \right|{{M}^{2}} - \sum\limits_{i = 1}^{2K} {b_{i}^{2}} \geqslant \frac{{\left| {K - c} \right|}}{{2{{K}^{2}}}}{{M}^{2}} - 2W(K\delta + 1).$

Выберем теперь параметр $M$ так, что

${{M}^{2}} > 2{{K}^{2}}(\varepsilon + 2W(K\delta + 1)).$
Тогда из (1.21) имеем $K = c$, как и в случаях I и II.

Далее, как и в рассмотренных случаях I и II, если в задаче РРД имеет место неравенство (1.18), то из этого неравенства следует (1.19). Поэтому из (1.14) с учетом (1.13) имеем

$\varepsilon \geqslant \frac{{K - 1}}{{{{K}^{2}}}}\left| {\sum\limits_{i \in {{I}_{1}}} {b_{i}^{2}} - \sum\limits_{i \in {{I}_{2}}} {b_{i}^{2}} } \right| \geqslant \frac{{K - 1}}{{{{K}^{2}}}}(1 - KW\delta ) = \frac{{K - 1}}{{{{K}^{2}}}} - \varepsilon ,$
т.е. $K - 1 \leqslant 2{{K}^{2}}\varepsilon = 2K{\text{/}}3$, что неверно при $K > 3$. Следовательно, в задаче РРД выполнено равенство (1.16).

Таким образом, в задаче $\Pi (g(x))$ для каждой функции $g(x)$ выполнение неравенства (1.7) влечет в задаче РРД существование разбиения множества $A$ на две равные по мощности доли с одинаковыми суммами элементов.

Из теоремы 1 и тождества (1.6) непосредственно вытекает основной результат настоящей работы:

Следствие. Задачи 1–3 NP-полны.

4. ЗАКЛЮЧЕНИЕ

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

Очевидно, что рассмотренные задачи 1–3 можно обобщить на случай, когда число кластеров больше, чем 2. В этих обобщениях задач вопросом является – можно ли разбить входное множество так, чтобы соответствующие неравенства (1.1), (1.2) и (1.3) выполнялись для всех пар кластеров. Ясно, что, когда число кластеров является частью входа, то эти обобщения тоже являются NP-полными задачами. Вопрос о статусе сложности параметрического случая этих задач, когда число кластеров не является частью входа, остается открытым. Построение приближенных эффективных алгоритмов с теоретическими гарантиями качества (точности и трудоемкости) представляется важным делом ближайшей перспективы.

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

  1. Aggarwal C.C. Data Mining: The Textbook. Berlin: Springer, 2015. 734 p.

  2. Hastie T., Tibshirani R., Friedman J. The elements of statistical learning: data mining, inference, and prediction. New York: Springer, 2001. 533 p.

  3. Han J., Kamber M., Pei J. Data Mining: Concepts and Techniques (3rd ed.). Waltham: Morgan Kaufmann Publishers is an inprint of Elsevier, 2012. 703 p.

  4. Shirkhorshidi A.S., Aghabozorgi S., Wah T.Y., Herawan T. Big Data Clustering: A Review // Lecture Notes in Computer Science. 2014. V. 8583. P. 707–720.

  5. Aloise D., Deshpande A., Hansen P., Popat P. NP-hardness of Euclidean sum-of-squares clustering // Machine Learning. 2009. V. 75. № 2. P. 245–248.

  6. Mahajan M., Nimbhorkar P., Varadarajan K. The planar k-means problem is NP-hard // Theoretical Computer Science. 2012. V. 442. P. 13–21.

  7. Arora S., Raghavan P., Rao S. Approximation schemes for Euclidean k-medians and related problems // Proceedings of the 30th Annual ACM Symposium on Theory of Computing. 1998. P. 106–113.

  8. Papadimitriou C.H. Worst-Case and Probabilistic Analysis of a Geometric Location Problem // SIAM J. Comput. 1981. V. 10. № 3. P. 542–557.

  9. Masuyama S., Ibaraki T., Hasegawa T. The computational complexity of the m-center problems in the plane // IEEE Trans. IECE Jpn. 1981. V. 64. № 2. P. 57–64.

  10. Hochbaum D.S., Shmoys D.B. A best possible heuristic for the k-center problem // Mathematics of Operations Research. 1985. V. 10. № 2. P. 180–184.

  11. Aggarwal H., Imai N., Katoh N., Suri S. Finding k points with minimum diameter and related problems // J. Algorithms. 1991. V. 12. № 1. P. 38–56.

  12. Brucker P. On the Complexity of Clustering Problems // Lecture Notes in Economics and Mathematical Systems. 1978. V. 157. P. 45–54.

  13. Indyk P. A sublinear time approximation scheme for clustering in metric space // Proc. of the 40th Ann. IEEE Symp. on Foundations of Computer Science (FOCS). New York: IEEE, 1999. P. 154–159.

  14. Hansen P., Jaumard B., Mladenovich N. Minimum sum of squares clustering in a low dimensional space // J. Classification. 1998. V. 15. P. 37–55.

  15. Hansen P., Jaumard B. Cluster analysis and mathematical programming // Mathematical Programming. 1997. V. 79. P. 191–215.

  16. Snedecor G.W., Cochran W.G. Statistical Methods, Eighth Edition. Iowa State University Press, 1989. 503 p.

  17. Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: Freeman, 1979. 314 p.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Журнал вычислительной математики и математической физики

Архивы выпусков Информация о журнале Отправить рукопись в журнал