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

Журнал вычислительной математики и математической физики, 2019, T. 59, № 9, стр. 1617-1625

Полиномиальная разрешимость одномерного случая одной NP-трудной задачи кластеризации

А. В. Кельманов 1, 2, *, В. И. Хандеев 1, 2, **

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

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

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

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

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

Аннотация

Рассматривается задача разбиения конечного множества точек евклидова пространства на кластеры по критерию минимума суммы по всем кластерам внутрикластерных сумм квадратов расстояний между элементами кластеров и их центрами. Центры одной части кластеров заданы на входе задачи, а центры другой части кластеров неизвестны и определяются как центроиды (геометрические центры). Известно, что в общем случае эта задача NP-трудна в сильном смысле. В работе конструктивно доказано, что одномерный случай задачи разрешим за полиномиальное время. Библ. 20.

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

ВВЕДЕНИЕ

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

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

Рассматриваемая задача имеет следующую формулировку.

Задача 1. Дано: $N$-элементное множество $\mathcal{Y}$ точек в евклидовом пространстве размерности $d$, натуральное число $K$ и набор $\{ {{c}_{1}},\; \ldots ,\;{{c}_{J}}\} $ точек. Найти: разбиение множества $\mathcal{Y}$ на $K + J$ непустых кластеров ${{\mathcal{C}}_{1}},\; \ldots ,\;{{\mathcal{C}}_{K}}$, ${{\mathcal{D}}_{1}},\; \ldots ,\;{{\mathcal{D}}_{J}}$ такое, что

$F({{\mathcal{C}}_{1}},\; \ldots ,\;{{\mathcal{C}}_{K}};{{\mathcal{D}}_{1}},\; \ldots ,\;{{\mathcal{D}}_{J}}) = \sum\limits_{k = 1}^K \,\sum\limits_{y \in {{\mathcal{C}}_{k}}} {{\left\| {y - \bar {y}({{\mathcal{C}}_{k}})} \right\|}^{2}} + \sum\limits_{j = 1}^J \,\sum\limits_{y \in {{\mathcal{D}}_{j}}} {{\left\| {y - {{c}_{j}}} \right\|}^{2}} \to min,$
где
$\bar {y}({{\mathcal{C}}_{k}}) = \tfrac{1}{{{\text{|}}{{\mathcal{C}}_{k}}{\text{|}}}}\sum\limits_{y \in {{\mathcal{C}}_{k}}} y $
есть центроид $k$-го кластера.

Задачу 1 можно рассматривать как модификацию известной задачи K-Means (K-Средних). В этой задаче дано $N$-элементное множество $\mathcal{Y}$ точек в евклидовом пространстве размерности $d$ и натуральное число $K$. Требуется найти разбиение входного множества $\mathcal{Y}$ на непустые непересекающиеся кластеры ${{\mathcal{C}}_{1}},\; \ldots ,\;{{\mathcal{C}}_{K}}$, минимизирующее сумму

$\sum\limits_{k = 1}^K \,\sum\limits_{y \in {{\mathcal{C}}_{k}}} {{\left\| {y - \bar {y}({{\mathcal{C}}_{k}})} \right\|}^{2}},$
где $\bar {y}({{\mathcal{C}}_{k}})$ – центроид $k$-го кластера.

Другое распространенное название задачи K-Means – MSSS (Minimum Sum-of-Squares Clustering), т.е. кластеризация по критерию минимума суммы квадратов. В статистике эта задача известна с прошлого века и связана с именем Фишера (см., например, [1], [2]). На практике (в самых разнообразных приложениях) она возникает в ситуациях, когда имеется гипотеза о том, что имеющаяся совокупность $\mathcal{Y}$ выборочных (входных) данных содержит $K$ однородных кластеров (подмножеств) ${{\mathcal{C}}_{1}},\; \ldots ,\;{{\mathcal{C}}_{K}}$, в которых точки разбросаны относительно соответствующих неизвестных средних значений $\bar {y}({{\mathcal{C}}_{1}}),\; \ldots ,\;\bar {y}({{\mathcal{C}}_{K}})$. Однако соответствие данных и кластеров неизвестно. Очевидно, что в этой ситуации для корректного применения классических статистических методов (проверки гипотез и оценивания) к обработке выборочных данных требуется сначала разбить их на однородные группы (кластеры). Эта ситуация типична, в частности, для отмеченных выше (во введении) прикладных проблем, связанных с обработкой данных.

Сильная NP-трудность задачи K-Means доказана относительно недавно [3]. Однако полиномиальная разрешимость этой задачи на числовой прямой установлена еще в прошлом веке в [4]. В этой работе представлен полиномиальный алгоритм с временем работы $\mathcal{O}(K{{N}^{2}})$, реализующий схему динамического программирования. Этот алгоритм опирается на хорошо известный точный полиномиальный алгоритм решения задачи о ближайшем соседе (Nearest neighbor search problem, NNSP) [5]. Заметим, что полиномиальная разрешимость одномерного случая задачи K-Means за время $\mathcal{O}(KNlogN)$ следует из более ранних (см. [4]) работ отечественных авторов [6]–[9], где представлены ускоренные эффективные алгоритмы для ряда специальных случаев задачи NNSP. Тем не менее в последующие годы для одномерного случая задачи K-Means были предложены новые алгоритмы с временем работы $\mathcal{O}(KNlogN)$. Обзор и свойства этих алгоритмов можно найти в [10], [11].

В отличие от задачи K-Means, Задача 1 моделирует прикладную проблему, в которой у части кластеров, а именно, у ${{\mathcal{D}}_{1}},\; \ldots ,\;{{\mathcal{D}}_{J}}$, соответствующие центры ${{c}_{1}},\; \ldots ,\;{{c}_{J}}$ квадратичного разброса данных известны заранее (заданы). Введенные обозначения позволяют назвать Задачу 1 как K-Means and Given J-Centers. Эта прикладная проблема также типична для анализа и интерпретации данных, распознавания образов и машинного обучения. В частности, двухкластерный вариант задачи – $1$-Mean and Given $1$-Center – связан с решением прикладной проблемы обработки сигналов, а именно, с проблемой совместного обнаружения квазипериодически повторяющегося импульса неизвестной формы и оценивания этой формы в условиях гауссовского шума с нулевым средним [12]–[14]. В этом двухкластерном варианте задачи нулевое среднее соответствует кластеру с заданным в начале координат центром. Первое сообщение об этом двухкластерном варианте Задачи 1, по-видимому, было сделано в [12]. Заметим, что более простые экстремальные задачи, которые индуцируются прикладными проблемами помехоустойчивого обнаружения и различения импульсов заданных форм, характерны, в частности, для радиолокации, электронной разведки, гидроакустики, геофизики, технической и медицинской диагностики, космического мониторинга (см., например, [15]–[17]).

Сильная NP-трудность Задачи 1 установлена в [18]–[20]. Заметим, что задача K-Means не эквивалентна Задаче 1 и не является ее частным случаем. Поэтому вопрос о разрешимости Задачи 1 на числовой прямой требует самостоятельного изучения. Этот вопрос до последнего времени оставался открытым. В настоящей работе мы доказываем, что в одномерном случае Задача 1 разрешима за полиномиальное время.

2. СВОЙСТВА ОПТИМАЛЬНОГО РЕШЕНИЯ В ОДНОМЕРНОМ СЛУЧАЕ

Всюду далее будем считать, что $d = 1$. Одномерный случай Задачи 1 будем называть Задача 1D.

Наше доказательство опирается на несколько приведенных ниже вспомогательных утверждений, которые раскрывают структуру оптимального решения Задачи 1D.

Обозначим через $\mathcal{C}_{1}^{ * },\; \ldots ,\;\mathcal{C}_{K}^{ * }$, $\mathcal{D}_{1}^{ * },\; \ldots ,\;\mathcal{D}_{J}^{ * }$ оптимальные кластеры в Задаче 1D.

Лемма 1. Если в Задаче 1D ${{c}_{m}} < {{c}_{\ell }}$, где $1 \leqslant m \leqslant J$, $1 \leqslant \ell \leqslant J$, то для любых $x \in \mathcal{D}_{m}^{ * }$ и $z \in \mathcal{D}_{\ell }^{ * }$ выполнено неравенство $x \leqslant z$.

Доказательство. Пусть существуют $x \in \mathcal{D}_{m}^{ * }$ и $z \in \mathcal{D}_{\ell }^{ * }$ такие, что $x > z$. Тогда для точек $x$, $z$ и ${{c}_{m}}$, ${{c}_{\ell }}$ имеем

(2.1)
$\begin{gathered} {{(x - {{c}_{m}})}^{2}} + {{(z - {{c}_{\ell }})}^{2}} - ({{(z - {{c}_{m}})}^{2}} + {{(x - {{c}_{\ell }})}^{2}}) = \\ = {{((x - z) + (z - {{c}_{m}}))}^{2}} + {{(z - {{c}_{\ell }})}^{2}} - ({{(z - {{c}_{m}})}^{2}} + {{((x - z) + (z - {{c}_{\ell }}))}^{2}}) = \\ = 2(x - z)(x - {{c}_{m}}) - 2(x - z)(x - {{c}_{\ell }}) = 2(x - z)({{c}_{\ell }} - {{c}_{m}}) > 0. \\ \end{gathered} $
Положим $\mathcal{D}_{m}^{'} = \mathcal{D}_{m}^{ * }{\backslash }\{ x\} \cup \{ z\} $ и $\mathcal{D}_{\ell }^{'} = \mathcal{D}_{\ell }^{ * }{\backslash }\{ z\} \cup \{ x\} $. Используя (2.1), получаем оценку
$\begin{gathered} \sum\limits_{y \in \mathcal{D}_{m}^{ * }} {{(y - {{c}_{m}})}^{2}} + \sum\limits_{y \in \mathcal{D}_{\ell }^{ * }} {{(y - {{c}_{\ell }})}^{2}} = \sum\limits_{y \in \mathcal{D}_{m}^{ * }{\backslash }\{ x\} } {{(y - {{c}_{m}})}^{2}} + \sum\limits_{y \in \mathcal{D}_{\ell }^{ * }{\backslash }\{ z\} } {{(y - {{c}_{\ell }})}^{2}} + {{(x - {{c}_{m}})}^{2}} + {{(z - {{c}_{\ell }})}^{2}} > \\ > \;\sum\limits_{y \in \mathcal{D}_{m}^{ * }{\backslash }\{ x\} } {{(y - {{c}_{m}})}^{2}} + \sum\limits_{y \in D_{\ell }^{ * }{\backslash }\{ z\} } {{(y - {{c}_{\ell }})}^{2}} + {{(z - {{c}_{m}})}^{2}} + {{(x - {{c}_{\ell }})}^{2}} = \sum\limits_{y \in \mathcal{D}_{m}^{'}} {{(y - {{c}_{m}})}^{2}} + \sum\limits_{y \in \mathcal{D}_{\ell }^{'}} {{(y - {{c}_{\ell }})}^{2}}, \\ \end{gathered} $
что противоречит предположению об оптимальности $\mathcal{D}_{1}^{ * },\; \ldots ,\;\mathcal{D}_{J}^{ * }$ и, как следствие, предположению об оптимальности $\mathcal{C}_{1}^{ * },\; \ldots ,\;\mathcal{C}_{K}^{ * }$, $\mathcal{D}_{1}^{ * },\; \ldots ,\;\mathcal{D}_{J}^{ * }$. Лемма 1 доказана.

Лемма 2. Если в Задаче 1D $\bar {y}(\mathcal{C}_{m}^{ * }) < \bar {y}(\mathcal{C}_{\ell }^{ * })$, где $1 \leqslant m \leqslant K$, $1 \leqslant \ell \leqslant K$, то для любых $x \in \mathcal{C}_{m}^{ * }$ и $z \in \mathcal{C}_{\ell }^{ * }$ справедливо неравенство $x \leqslant z$.

Доказательство. Как и в доказательстве леммы 1, предположим, что существуют такие $x \in \mathcal{C}_{m}^{ * }$ и $z \in \mathcal{C}_{\ell }^{ * }$, для которых $x > z$. Тогда, аналогично доказательству (2.1), для точек $x$, $z$ и $\bar {y}(\mathcal{C}_{m}^{ * })$, $\bar {y}(\mathcal{C}_{\ell }^{ * })$ получим неравенство

(2.2)
${{(x - \bar {y}(\mathcal{C}_{m}^{ * }))}^{2}} + {{(z - \bar {y}(\mathcal{C}_{\ell }^{ * }))}^{2}} > {{(z - \bar {y}(\mathcal{C}_{m}^{ * }))}^{2}} + {{(x - \bar {y}(\mathcal{C}_{\ell }^{ * }))}^{2}}.$

Далее, для центроидов $\bar {y}(\mathcal{C}_{m}^{ * })$ и $\bar {y}(\mathcal{C}_{m}^{'})$, где $\mathcal{C}_{m}^{'} = \mathcal{C}_{m}^{ * }{\backslash }\{ x\} \cup \{ z\} $, имеем

(2.3)
$\begin{gathered} \sum\limits_{y \in \mathcal{C}_{m}^{'}} {{(y - \bar {y}(\mathcal{C}_{m}^{ * }))}^{2}} = \sum\limits_{y \in \mathcal{C}_{m}^{'}} {{(y - \bar {y}(\mathcal{C}_{m}^{'}) + \bar {y}(\mathcal{C}_{m}^{'}) - \bar {y}(\mathcal{C}_{m}^{ * }))}^{2}} = \\ = \sum\limits_{y \in \mathcal{C}_{m}^{'}} {{(y - \bar {y}(\mathcal{C}_{m}^{'}))}^{2}} + 2\sum\limits_{y \in \mathcal{C}_{m}^{'}} ((y - \bar {y}(\mathcal{C}_{m}^{'}))(\bar {y}(\mathcal{C}_{m}^{'}) - \bar {y}(\mathcal{C}_{m}^{ * })) + \left| {\mathcal{C}_{m}^{'}} \right|{{(\bar {y}(\mathcal{C}_{m}^{'}) - \bar {y}(\mathcal{C}_{m}^{ * }))}^{2}} = \\ = \sum\limits_{v \in \mathcal{C}_{m}^{'}} {{(y - \bar {y}(\mathcal{C}_{m}^{'}))}^{2}} + \left| {\mathcal{C}_{m}^{'}} \right|{{(\bar {y}(\mathcal{C}_{m}^{'}) - \bar {y}(\mathcal{C}_{m}^{ * }))}^{2}}, \\ \end{gathered} $
так как
$\sum\limits_{y \in \mathcal{C}_{m}^{'}} ((y - \bar {y}(\mathcal{C}_{m}^{'}))(\bar {y}(\mathcal{C}_{m}^{'}) - \bar {y}(\mathcal{C}_{m}^{ * })) = 0,$
в силу того, что
$\sum\limits_{y \in \mathcal{C}_{m}^{'}} (y - \bar {y}(\mathcal{C}_{m}^{'})) = 0$.
Поэтому из (2.3) следует оценка
(2.4)
$\sum\limits_{y \in \mathcal{C}_{m}^{'}} {{(y - \bar {y}(\mathcal{C}_{m}^{ * }))}^{2}} \geqslant \sum\limits_{y \in \mathcal{C}_{m}^{'}} {{(y - \bar {y}(\mathcal{C}_{m}^{'}))}^{2}}.$
Аналогичным образом найдем
(2.5)
$\sum\limits_{y \in \mathcal{C}_{\ell }^{'}} {{(y - \bar {y}(\mathcal{C}_{\ell }^{ * }))}^{2}} \geqslant \sum\limits_{y \in \mathcal{C}_{\ell }^{'}} {{(y - \bar {y}(\mathcal{C}_{\ell }^{'}))}^{2}},$
где $\mathcal{C}_{\ell }^{'} = \mathcal{C}_{\ell }^{*}{\backslash }\{ z\} \cup \{ x\} $.

Из неравенств (2.2), (2.4) и (2.5) получим следующую оценку:

$\begin{gathered} \sum\limits_{y \in \mathcal{C}_{m}^{ * }} {{(y - \bar {y}(\mathcal{C}_{m}^{ * }))}^{2}} + \sum\limits_{y \in \mathcal{C}_{\ell }^{ * }} {{(y - \bar {y}(C_{\ell }^{ * }))}^{2}} > \sum\limits_{y \in \mathcal{C}_{m}^{'}} {{(y - \bar {y}(\mathcal{C}_{m}^{ * }))}^{2}} + \sum\limits_{y \in \mathcal{C}_{\ell }^{'}} {{(y - \bar {y}(\mathcal{C}_{\ell }^{ * }))}^{2}} \geqslant \\ \geqslant \sum\limits_{y \in \mathcal{C}_{m}^{'}} {{(y - \bar {y}(\mathcal{C}_{m}^{'}))}^{2}} + \sum\limits_{y \in \mathcal{C}_{\ell }^{'}} {{(y - \bar {y}(\mathcal{C}_{\ell }^{'}))}^{2}}, \\ \end{gathered} $
которая противоречит предположению об оптимальности $\mathcal{C}_{1}^{ * },\; \ldots ,\;\mathcal{C}_{K}^{ * }$ и, как следствие, – предположению об оптимальности $\mathcal{C}_{1}^{ * },\; \ldots ,\;\mathcal{C}_{K}^{ * }$, $\mathcal{D}_{1}^{ * },\; \ldots ,\;\mathcal{D}_{J}^{ * }$. Лемма 2 доказана.

Лемма 3. Для оптимального решения Задачи 1D справедливы следующие утверждения:

a) если $\bar {y}(\mathcal{C}_{m}^{ * }) < {{c}_{\ell }}$, где $1 \leqslant m \leqslant K$, $1 \leqslant \ell \leqslant J$, то для любых $x \in \mathcal{C}_{m}^{ * }$ и $z \in \mathcal{D}_{\ell }^{ * }$ справедливо неравенство $x \leqslant z$;

б) если $\bar {y}(\mathcal{C}_{m}^{ * }) > {{c}_{\ell }}$, где $1 \leqslant m \leqslant K$, $1 \leqslant \ell \leqslant J$, то для любых $x \in \mathcal{C}_{m}^{ * }$ и $z \in \mathcal{D}_{\ell }^{ * }$ выполнено неравенство $x \geqslant z$.

Доказательство. Докажем лемму для случая a). Как и в доказательстве леммы 1, предположим, что существуют такие $x \in \mathcal{C}_{m}^{ * }$ и $z \in \mathcal{D}_{\ell }^{ * }$, для которых $x > z$. Тогда, аналогично доказательству (2.1), для точек $x$, $z$ и $\bar {y}(\mathcal{C}_{m}^{ * })$, ${{c}_{\ell }}$ получим

${{(x - \bar {y}(\mathcal{C}_{m}^{ * }))}^{2}} + {{(z - {{c}_{\ell }})}^{2}} > {{(z - \bar {y}(\mathcal{C}_{m}^{ * }))}^{2}} + {{(x - {{c}_{\ell }})}^{2}}.$

Из этого неравенства и (2.4) следует оценка

$\begin{gathered} \sum\limits_{y \in \mathcal{C}_{m}^{ * }} {{(y - \bar {y}(\mathcal{C}_{m}^{ * }))}^{2}} + \sum\limits_{y \in \mathcal{D}_{\ell }^{ * }} {{(y - {{c}_{\ell }})}^{2}} > \sum\limits_{y \in \mathcal{C}_{m}^{'}} {{(y - \bar {y}(\mathcal{C}_{m}^{ * }))}^{2}} + \sum\limits_{y \in \mathcal{D}_{\ell }^{'}} {{(y - {{c}_{\ell }})}^{2}} \geqslant \\ \geqslant \sum\limits_{y \in \mathcal{C}_{m}^{'}} {{(y - \bar {y}(\mathcal{C}_{m}^{'}))}^{2}} + \sum\limits_{y \in \mathcal{D}_{\ell }^{'}} {{(y - {{c}_{\ell }})}^{2}}, \\ \end{gathered} $
где $\mathcal{C}_{m}^{'} = \mathcal{C}_{m}^{ * }{\backslash }\{ x\} \cup \{ z\} $ и $\mathcal{D}_{\ell }^{'} = \mathcal{D}_{\ell }^{ * }{\backslash }\{ z\} \cup \{ x\} $. Эта оценка противоречит предположению об оптимальности $\mathcal{C}_{1}^{ * },\; \ldots ,\;\mathcal{C}_{K}^{ * }$, $\mathcal{D}_{1}^{ * },\; \ldots ,\;\mathcal{D}_{J}^{ * }$.

Случай б) доказывается аналогичным образом. Лемма 3 доказана.

Лемма 4. Для каждого $k \in \{ 1,\; \ldots ,\;K\} $ и каждого $j \in \{ 1,\; \ldots ,\;J\} $ в Задаче 1D справедливо: $\bar {y}(\mathcal{C}_{k}^{ * }) \ne {{c}_{j}}$.

Доказательство. Пусть существуют такие $m \in \{ 1,\; \ldots ,\;K\} $ и $\ell \in \{ 1,\; \ldots ,\;J\} $, для которых $\bar {y}(\mathcal{C}_{m}^{ * }) = {{c}_{\ell }}$.

Рассмотрим произвольные точки $x \in \mathcal{C}_{m}^{ * }$ и $z \in \mathcal{D}_{\ell }^{ * }$. Положим $\mathcal{C}_{m}^{'} = \mathcal{C}_{m}^{*}{\backslash }\{ x\} \cup \{ z\} $ и $\mathcal{D}_{\ell }^{'} = \mathcal{D}_{\ell }^{ * }{\backslash }\{ z\} \cup \{ x\} $. Тогда справедливо равенство

(2.6)
$\sum\limits_{y \in \mathcal{C}_{m}^{ * }} {{(y - \bar {y}(\mathcal{C}_{m}^{*}))}^{2}} + \sum\limits_{y \in \mathcal{D}_{\ell }^{ * }} {{(y - {{c}_{\ell }})}^{2}} = \sum\limits_{y \in \mathcal{C}_{m}^{'}} {{(y - \bar {y}(\mathcal{C}_{m}^{*}))}^{2}} + \sum\limits_{y \in \mathcal{D}_{\ell }^{'}} {{(y - {{c}_{\ell }})}^{2}}.$
Далее, поскольку $\mathcal{Y}$ – множество, $x \ne z$ и $\bar {y}(\mathcal{C}_{m}^{*}) \ne \bar {y}(\mathcal{C}_{m}^{'})$. Поэтому из (2.3) следует оценка
(2.7)
$\sum\limits_{y \in \mathcal{C}_{m}^{'}} {{(y - \bar {y}(\mathcal{C}_{m}^{*}))}^{2}} > \sum\limits_{y \in \mathcal{C}_{m}^{'}} {{(y - \bar {y}(\mathcal{C}_{m}^{'}))}^{2}}.$
Наконец, применяя (2.7) к правой части (2.6), получаем
$\sum\limits_{y \in \mathcal{C}_{m}^{ * }} {{(y - \bar {y}(\mathcal{C}_{m}^{*}))}^{2}} + \sum\limits_{y \in \mathcal{D}_{\ell }^{ * }} {{(y - {{c}_{\ell }})}^{2}} > \sum\limits_{y \in \mathcal{C}_{m}^{'}} {{(y - \bar {y}(\mathcal{C}_{m}^{'}))}^{2}} + \sum\limits_{y \in \mathcal{D}_{\ell }^{'}} {{(y - {{c}_{\ell }})}^{2}},$
что противоречит предположению об оптимальности $\mathcal{C}_{1}^{ * },\; \ldots ,\;\mathcal{C}_{K}^{ * }$, $\mathcal{D}_{1}^{ * },\; \ldots ,\;\mathcal{D}_{J}^{ * }$. Лемма 4 доказана.

Лемма 5. Для каждых $k,j \in \{ 1, \ldots ,K\} $ таких, что $k \ne j$, в Задаче 1D справедливо $\bar {y}(\mathcal{C}_{k}^{*}) \ne \bar {y}(\mathcal{C}_{j}^{*})$.

Доказательство. Как и в доказательстве леммы 4, предположим, что существуют такие $m,\ell \in \{ 1, \ldots ,K\} $, для которых $\bar {y}(\mathcal{C}_{m}^{*}) = \bar {y}(\mathcal{C}_{\ell }^{*})$.

Рассмотрим произвольные точки $x \in {{\mathcal{C}}_{m}}$ и $z \in {{\mathcal{C}}_{\ell }}$. Пусть $\mathcal{C}_{m}^{'} = \mathcal{C}_{m}^{*}{\backslash }\{ x\} \cup \{ z\} $, $\mathcal{C}_{\ell }^{'} = \mathcal{C}_{\ell }^{*}{\backslash }\{ z\} \cup \{ x\} $. Тогда справедливо равенство

(2.8)
$\sum\limits_{y \in \mathcal{C}_{m}^{ * }} {{(y - \bar {y}(\mathcal{C}_{m}^{*}))}^{2}} + \sum\limits_{y \in \mathcal{C}_{\ell }^{ * }} {{(y - {{c}_{\ell }})}^{2}} = \sum\limits_{y \in \mathcal{C}_{m}^{'}} {{(y - \bar {y}(\mathcal{C}_{m}^{*}))}^{2}} + \sum\limits_{y \in \mathcal{C}_{\ell }^{'}} {{(y - {{c}_{\ell }})}^{2}}.$

По аналогии с доказательством (2.7), найдем оценки

(2.9)
$\sum\limits_{y \in \mathcal{C}_{m}^{'}} {{(y - \bar {y}(\mathcal{C}_{m}^{*}))}^{2}} > \sum\limits_{y \in \mathcal{C}_{m}^{'}} {{(y - \bar {y}(\mathcal{C}_{m}^{'}))}^{2}}$
и
(2.10)
$\sum\limits_{y \in \mathcal{C}_{\ell }^{'}} {{(y - \bar {y}(\mathcal{C}_{\ell }^{*}))}^{2}} > \sum\limits_{y \in \mathcal{C}_{\ell }^{'}} {{(y - \bar {y}(\mathcal{C}_{\ell }^{'}))}^{2}}.$
Наконец, применяя оценки (2.9) и (2.10) к правой части (2.8), получаем
$\sum\limits_{y \in \mathcal{C}_{m}^{ * }} {{(y - \bar {y}(\mathcal{C}_{m}^{ * }))}^{2}} + \sum\limits_{y \in \mathcal{C}_{\ell }^{ * }} {{(y - \bar {y}(\mathcal{C}_{\ell }^{ * }))}^{2}} > \sum\limits_{y \in \mathcal{C}_{m}^{'}} {{(y - \bar {y}(\mathcal{C}_{m}^{'}))}^{2}} + \sum\limits_{y \in \mathcal{C}_{\ell }^{'}} {{(y - \bar {y}(\mathcal{C}_{\ell }^{'}))}^{2}},$
что противоречит предположению об оптимальности $\mathcal{C}_{1}^{ * },\; \ldots ,\;\mathcal{C}_{K}^{ * }$, $\mathcal{D}_{1}^{ * },\; \ldots ,\;\mathcal{D}_{J}^{ * }$. Лемма 5 доказана.

Заметим, что леммы 4 и 5 справедливы также и для многомерного случая.

Леммы 1–5 устанавливают взаимное расположение на числовой прямой оптимальных кластеров $\mathcal{D}_{1}^{ * },\; \ldots ,\;\mathcal{D}_{J}^{ * }$ с заданными центрами и кластеров $\mathcal{C}_{1}^{ * },\; \ldots ,\;\mathcal{C}_{K}^{ * }$ с неизвестными центрами. Эти леммы служат базой для доказательства следующего утверждения.

Теорема 1. Пусть в Задаче 1D точки ${{y}_{1}}, \ldots ,{{y}_{N}}$ входного множества $\mathcal{Y}$, а также точки ${{c}_{1}},\; \ldots ,\;{{c}_{J}}$ упорядочены так, что

${{y}_{1}} < \ldots < {{y}_{N}};\quad {{c}_{1}} < \ldots < {{c}_{J}}.$
Тогда оптимальному разбиению $\mathcal{Y}$ на кластеры $\mathcal{C}_{1}^{ * },\; \ldots ,\;\mathcal{C}_{K}^{ * },\;\mathcal{D}_{1}^{ * },\; \ldots ,\;\mathcal{D}_{J}^{ * }$ соответствует разбиение последовательности $1,\; \ldots ,\;N$ натуральных чисел на непересекающиеся целочисленные отрезки.

Доказательство. Справедливость теоремы 1 следует из лемм 1–5. Теорема 1 доказана.

3. ПОЛИНОМИАЛЬНАЯ РАЗРЕШИМОСТЬ ЗАДАЧИ В ОДНОМЕРНОМ СЛУЧАЕ

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

Теорема 2. Существует алгоритм, который находит оптимальное решение Задачи 1D за полиномиальное время.

Доказательство теоремы проводится конструктивно, а именно: мы обосновываем алгоритм, который реализует схему динамического программирования и позволяет находить точное решение задачи за время $\mathcal{O}(KJ{{N}^{2}})$.

Без ограничения общности допустим, что точки ${{y}_{1}},\; \ldots ,\;{{y}_{N}}$ входного множества $\mathcal{Y}$, а также точки ${{c}_{1}},\; \ldots ,\;{{c}_{J}}$ упорядочены как в теореме 1.

Пусть ${{\mathcal{Y}}_{{s,t}}} = \{ {{y}_{s}},\; \ldots ,\;{{y}_{t}}\} $, где $1 \leqslant s \leqslant t \leqslant N$, – подмножество из $t - s + 1$ точек входного множества $\mathcal{Y}$ с номерами от $s$ до $t$.

Положим

$f_{{s,t}}^{j} = \sum\limits_{i = s}^t \,{{({{y}_{i}} - {{c}_{j}})}^{2}},\quad j = 1,\; \ldots ,\;J,$
${{f}_{{s,t}}} = \sum\limits_{i = s}^t \,{{({{y}_{i}} - \bar {y}({{\mathcal{Y}}_{{s,t}}}))}^{2}} \equiv \sum\limits_{i = s}^t \,\mathcal{Y}_{i}^{2} - \frac{1}{{t - s + 1}}\mathop {\left( {\sum\limits_{i = s}^t \,{{y}_{i}}} \right)}\nolimits^2 ,$
где $\bar {y}({{\mathcal{Y}}_{{s,t}}})$ – центроид подмножества ${{\mathcal{Y}}_{{s,t}}}$.

В соответствии с теоремой 1, пусть $\{ i{\kern 1pt} *,i{\kern 1pt} {\text{*}} + 1,\; \ldots ,\;N\} $ – номера элементов оптимального кластера, содержащего точку ${{y}_{N}}$.

Заметим, что для оптимального значения $F{\text{*}}$ целевой функции Задачи 1D возможны два случая:

(3.11)
$F{\kern 1pt} {\text{*}} = \left\{ \begin{gathered} \sum\limits_{k = 1}^{K - 1} \,\sum\limits_{y \in \mathcal{C}_{k}^{ * }} {{(y - \bar {y}({{\mathcal{C}}_{k}}))}^{2}} + \sum\limits_{j = 1}^J \sum\limits_{y \in \mathcal{D}_{j}^{ * }} {{(y - {{c}_{j}})}^{2}} + {{f}_{{i*,N}}},\quad {\text{если}}\quad \mathcal{C}_{K}^{ * } = \{ {{y}_{{i*}}},{{y}_{{i* + 1}}},\; \ldots ,\;{{y}_{N}}\} , \hfill \\ \sum\limits_{k = 1}^K \,\sum\limits_{y \in \mathcal{C}_{k}^{ * }} {{(y - \bar {y}(\mathcal{C}_{k}^{ * }))}^{2}} + \sum\limits_{j = 1}^{J - 1} \sum\limits_{y \in \mathcal{D}_{j}^{ * }} {{(y - {{c}_{j}})}^{2}} + f_{{i*,N}}^{J},\quad {\text{если}}\quad \mathcal{D}_{J}^{ * } = \{ {{y}_{{i*}}},{{y}_{{i* + 1}}},\; \ldots ,\;{{y}_{N}}\} . \hfill \\ \end{gathered} \right.$

Обозначим Задачу 1D через $\langle K,J,N\rangle $. Погрузим эту задачу в семейство $\{ \langle k,j,n\rangle ,\;k = 0,\; \ldots ,\;K;$ $j = 0,\; \ldots ,\;J;\;n = 1,\; \ldots ,\;N\} $ подзадач, где $\langle k,j,n\rangle $ – подзадача нахождения разбиения множества $\{ {{y}_{1}},\; \ldots ,\;{{y}_{n}}\} $ на непустые кластеры ${{\mathcal{C}}_{1}},\; \ldots ,\;{{\mathcal{C}}_{k}}$, ${{\mathcal{D}}_{1}},\; \ldots ,\;{{\mathcal{D}}_{j}}$ такие, что

$\sum\limits_{m = 1}^k \,\sum\limits_{y \in {{\mathcal{C}}_{m}}} {{(y - \bar {y}({{\mathcal{C}}_{m}}))}^{2}} + \sum\limits_{\ell = 1}^j \,\sum\limits_{y \in {{\mathcal{D}}_{\ell }}} {{(y - {{c}_{\ell }})}^{2}} \to min.$

Пусть ${{F}_{{k,j}}}(n)$ – оптимальное значение целевой функции подзадачи $\langle k,j,n\rangle $. Тогда, в соответствии с (3.11), возможны два случая:

(3.12)
${{F}_{{k,j}}}(n) = \left\{ \begin{gathered} \sum\limits_{m = 1}^{k - 1} \,\sum\limits_{y \in \mathcal{C}_{m}^{ * }} {{(y - \bar {y}({{\mathcal{C}}_{m}}))}^{2}} + \sum\limits_{\ell = 1}^j \,\sum\limits_{y \in \mathcal{D}_{\ell }^{ * }} {{(y - {{c}_{\ell }})}^{2}} + {{f}_{{i*,n}}},\quad {\text{если}}\quad \mathcal{C}_{k}^{ * } = \{ {{y}_{{i*}}},{{y}_{{i* + 1}}},\; \ldots ,\;{{y}_{n}}\} , \hfill \\ \sum\limits_{m = 1}^k \,\sum\limits_{y \in \mathcal{C}_{m}^{ * }} {{(y - \bar {y}(\mathcal{C}_{m}^{ * }))}^{2}} + \sum\limits_{\ell = 1}^{j - 1} \,\sum\limits_{y \in \mathcal{D}_{\ell }^{ * }} {{(y - {{c}_{\ell }})}^{2}} + f_{{i*,n}}^{j},\quad {\text{если}}\quad \mathcal{D}_{j}^{ * } = \{ {{y}_{{i*}}},{{y}_{{i* + 1}}},\; \ldots ,\;{{y}_{n}}\} , \hfill \\ \end{gathered} \right.$
где $\mathcal{C}_{1}^{ * },\; \ldots ,\;\mathcal{C}_{k}^{ * }$, $\mathcal{D}_{1}^{ * },\; \ldots ,\;\mathcal{D}_{j}^{ * }$ – оптимальные кластеры в подзадаче $\langle k,j,n\rangle $, а $\{ i{\kern 1pt} *,i{\kern 1pt} {\text{*}} + 1,\; \ldots ,\;n\} $ – номера элементов оптимального кластера, содержащего точку ${{y}_{n}}$.

Для проведения вычислений определим начальные и граничные условия, которые следуют из свойств оптимального решения:

(3.13)
${{F}_{{k,j}}}(n) = \left\{ \begin{gathered} 0,\quad {\text{если}}\quad n = k = j = 0, \hfill \\ + \infty ,\quad {\text{если}}\quad n = 0,\quad k = 0,\; \ldots ,\;K,\quad j = 0,\; \ldots ,\;J,\quad k + j \ne 0, \hfill \\ + \infty ,\quad {\text{если}}\quad k = - 1,\quad j = --1,\; \ldots ,\;J,\quad n = 0,\; \ldots ,\;N, \hfill \\ + \infty ,\quad {\text{если}}\quad j = - 1,\quad k = --1,\; \ldots ,\;K,\quad n = 0,\; \ldots ,\;N. \hfill \\ \end{gathered} \right.$
Тогда, в соответствии с принципом оптимальности Беллмана, для двух случаев (3.12) имеем
(3.14)
${{F}_{{k,j}}}(n) = \mathop {\min }\limits_{i = 1}^n \{ {{F}_{{k - 1,j}}}(i - 1) + {{f}_{{i,n}}}\} ,\quad k = 0,\; \ldots ,\;K,\quad j = 0,\; \ldots ,\;J,\quad n = 1,\; \ldots ,\;N,$
в первом случае, когда $\mathcal{C}_{k}^{ * } = \{ {{y}_{{i*}}},{{y}_{{i* + 1}}},\; \ldots ,\;{{y}_{n}}\} $. Во втором случае, когда $\mathcal{D}_{j}^{ * } = \{ {{y}_{{i*}}},{{y}_{{i* + 1}}},\; \ldots ,\;{{y}_{n}}\} $, имеем

(3.15)
${{F}_{{k,j}}}(n) = \mathop {min}\limits_{i = 1}^n \{ {{F}_{{k,j - 1}}}(i - 1) + f_{{i,n}}^{j}\} ,\quad k = 0,\; \ldots ,\;K,\quad j = 0,\; \ldots ,\;J,\quad n = 1,\; \ldots ,\;N.$

Объединяя (3.14) и (3.15), получаем, что для ${{F}_{{k,j}}}(n)$ выполнено равенство

(3.16)
$\begin{gathered} {{F}_{{k,j}}}(n) = \min \left\{ {\mathop {\min }\limits_{i = 1}^n \{ {{F}_{{k - 1,j}}}(i - 1) + {{f}_{{i,n}}}\} ,\;\mathop {\min }\limits_{i = 1}^n \{ {{F}_{{k,j - 1}}}(i - 1) + f_{{i,n}}^{j}\} } \right\}, \\ k = 0,\; \ldots ,\;K,\quad j = 0,\; \ldots ,\;J,\quad n = 1,\; \ldots ,\;N. \\ \end{gathered} $

Таким образом, для оптимального значения целевой функции Задачи 1D справедлива формула

$F* = {{F}_{{K,J}}}(N).$
Таблица значений функции
${{F}_{{k,j}}}(n),\quad k = - 1,0,1,\; \ldots ,\;K,\quad j = - 1,0,1,\; \ldots ,\;J,\quad n = 0,\; \ldots ,\;N,$
вычисляется по формуле (3.13) и рекуррентной формуле (3.16). В целом формулы (3.13), (3.16) реализуют прямой ход алгоритма.

Далее, из принципа оптимальности Беллмана следует, что кластеры $\mathcal{C}_{1}^{ * },\; \ldots ,\;\mathcal{C}_{K}^{ * }$ и $\mathcal{D}_{1}^{ * },\; \ldots ,\;\mathcal{D}_{J}^{ * }$ находятся по следующему рекуррентному правилу, которое реализует обратный ход алгоритма, начиная с $k = K$, $j = J$, $n = N$.

Пошаговая запись этого правила выглядит следующим образом.

Шаг 1. Если

(3.17)
$\mathop {min}\limits_{i = 1}^n ({{F}_{{k - 1,j}}}(i - 1) + {{f}_{{i,n}}}) \leqslant \mathop {min}\limits_{i = 1}^n ({{F}_{{k,j - 1}}}(i - 1) + f_{{i,n}}^{j}),$
то
(3.18)
$\mathcal{C}_{k}^{ * } = \{ {{y}_{{i*}}},{{y}_{{i* + 1}}},\; \ldots ,\;{{y}_{n}}\} ,$
где
(3.19)
$i{\kern 1pt} * = arg\mathop {min}\limits_{i = 1}^n ({{F}_{{k - 1,j}}}(i - 1) + {{f}_{{i,n}}}),\quad k: = k - 1,\quad n: = i{\kern 1pt} {\text{*}} - 1.$
Если, однако,
(3.20)
$\mathop {min}\limits_{i = 1}^n ({{F}_{{k - 1,j}}}(i - 1) + {{f}_{{i,n}}}) > \mathop {min}\limits_{i = 1}^n ({{F}_{{k,j - 1}}}(i - 1) + f_{{i,n}}^{j}),$
то
$\mathcal{D}_{j}^{ * } = \{ {{y}_{{i*}}},{{y}_{{i* + 1}}},\; \ldots ,\;{{y}_{n}}\} ,$
где

$i* = arg\mathop {min}\limits_{i = 1}^n ({{F}_{{k,j - 1}}}(i - 1) + f_{{i,n}}^{j});\quad j: = j - 1,\quad n: = i{\kern 1pt} {\text{*}} - 1.$

Шаг 2. Если $k > 0$ или $j > 0$, то идти на Шаг 1, иначе – конец вычислений.

Докажем индукцией по $k$ и $j$, что для произвольных $k,j,n$ это правило находит кластеры $\mathcal{C}_{1}^{ * },\; \ldots ,\;\mathcal{C}_{k}^{ * },\;\mathcal{D}_{1}^{ * },\; \ldots ,\;\mathcal{D}_{j}^{ * }$, которые являются оптимальным решением подзадачи $\langle k,j,n\rangle $.

Рассмотрим случай (3.17), когда наибольшая точка ${{y}_{n}}$ из поднабора ${{y}_{1}} < \ldots < {{y}_{n}}$ входит в кластер $\mathcal{C}_{k}^{ * }$. Случай (3.20), когда точка ${{y}_{n}}$ входит в кластер $\mathcal{D}_{j}^{ * }$, анализируется аналогично.

Заметим, что в силу формул (3.16) и (3.14) существует оптимальное решение $\mathcal{C}_{1}^{'},\; \ldots ,\;\mathcal{C}_{{k - 1}}^{'}$, $\mathcal{C}_{k}^{ * },\;\mathcal{D}_{1}^{'},\; \ldots ,\;\mathcal{D}_{j}^{'}$ подзадачи $\langle k,j,n\rangle $, в котором для последнего кластера $\mathcal{C}_{k}^{ * }$ справедливы формулы (3.18) и (3.19). Поэтому для кластеров $\mathcal{C}_{1}^{'},\; \ldots ,\;\mathcal{C}_{{k - 1}}^{'}$, $\mathcal{C}_{k}^{ * }$, $\mathcal{D}_{1}^{'},\; \ldots ,\;\mathcal{D}_{j}^{'}$ имеем

(3.21)
${{F}_{{k,j}}}(n) = F(\mathcal{C}_{1}^{'},\; \ldots ,\;\mathcal{C}_{{k - 1}}^{'},\;\mathcal{C}_{k}^{ * };\;\mathcal{D}_{1}^{'},\; \ldots ,\;\mathcal{D}_{j}^{'}) = F(\mathcal{C}_{1}^{'},\; \ldots ,\;\mathcal{C}_{{k - 1}}^{'};\;\mathcal{D}_{1}^{'},\; \ldots ,\;\mathcal{D}_{j}^{'}) + {{f}_{{i*,n}}} = {{F}_{{k - 1,j}}}(i{\kern 1pt} {\text{*}} - 1) + {{f}_{{i*,n}}}.$
По индукционному предположению, для подзадачи $\langle k - 1,j,i{\kern 1pt} {\text{*}} - 1\rangle $ правило обратного хода находит оптимальные кластеры $\mathcal{C}_{1}^{ * },\; \ldots ,\;\mathcal{C}_{k}^{ * },\;\mathcal{D}_{1}^{ * },\; \ldots ,\;\mathcal{D}_{j}^{ * }$, то есть кластеры, для которых
(3.22)
$F(\mathcal{C}_{1}^{ * },\; \ldots ,\;\mathcal{C}_{{k - 1}}^{ * };\;\mathcal{D}_{1}^{ * },\; \ldots ,\;\mathcal{D}_{j}^{ * }) = {{F}_{{k - 1,j}}}(i{\kern 1pt} {\text{*}} - 1).$
Тогда из (3.21) и (3.22) получим
$F(\mathcal{C}_{1}^{ * },\; \ldots ,\;\mathcal{C}_{k}^{ * };\;\mathcal{D}_{1}^{ * },\; \ldots ,\;\mathcal{D}_{j}^{ * }) = F(\mathcal{C}_{1}^{ * },\; \ldots ,\;\mathcal{C}_{{k - 1}}^{ * };\;\mathcal{D}_{1}^{ * },\; \ldots ,\;\mathcal{D}_{j}^{ * }) + {{f}_{{i*,n}}} = {{F}_{{k - 1,j}}}(i{\kern 1pt} {\text{*}} - 1) + {{f}_{{i*,n}}} = {{F}_{{k,j}}}(n),$
из чего следует оптимальность кластеров $\mathcal{C}_{1}^{ * },\; \ldots ,\;\mathcal{C}_{k}^{ * },\;\mathcal{D}_{1}^{ * },\; \ldots ,\;\mathcal{D}_{j}^{ * }$.

Сформулируем следующий алгоритм решения Задачи 1D.

Алгоритм $A$

Вход: $N$-элементное множество $\mathcal{Y}$ точек, натуральное число $K$ и набор $\{ {{c}_{1}},\; \ldots ,\;{{c}_{J}}\} $ точек.

Шаг 1. Отсортируем по возрастанию точки ${{y}_{1}},\; \ldots ,\;{{y}_{N}}$ и точки ${{c}_{1}},\; \ldots ,\;{{c}_{J}}$.

Шаг 2. Вычислим значения $f_{{s,t}}^{j}$ и ${{f}_{{s,t}}}$.

Шаг 3. Найдем оптимальные значения ${{F}_{{k,j}}}(n)$, используя формулы (3.13) и (3.16).

Шаг 4. Найдем оптимальные кластеры $\mathcal{C}_{1}^{ * },\; \ldots ,\;\mathcal{C}_{k}^{ * },\;\mathcal{D}_{1}^{ * },\; \ldots ,\;\mathcal{D}_{j}^{ * }$, используя правила обратного хода.

Выход: кластеры $\mathcal{C}_{1}^{ * },\; \ldots ,\;\mathcal{C}_{k}^{ * },\;\mathcal{D}_{1}^{ * },\; \ldots ,\;\mathcal{D}_{j}^{ * }$.

Оценим трудоемкость алгоритма. Шаг 1 требует $\mathcal{O}(NlogN)$ операций. Шаг 2 может быть выполнен за время $\mathcal{O}(J{{N}^{2}})$ с использованием префиксного суммирования. Время работы шага 3 определяется трудоемкостью вычислений по формуле (3.16). Эта формула вычисляется $\mathcal{O}(KJN)$ раз, и каждое вычисление значения ${{F}_{{k,j}}}(n)$ требует $\mathcal{O}(N)$ операций. Наконец, шаг 4 требует $\mathcal{O}((K + J)N)$ операций. Суммируя затраты на всех шагах, получаем оценку $\mathcal{O}(KJ{{N}^{2}})$ времени работы алгоритма, то есть алгоритм полиномиален. Теорема 2 доказана.

ЗАКЛЮЧЕНИЕ

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

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

  1. Fisher R.A. Statistical Methods and Scientific Inference. New York. Hafner, 1956. 350 p.

  2. MacQueen J.B. Some Methods for Classification and Analysis of Multivariate Observations, in Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. 1967. V. 1. Univ. of California Press, Berkeley, 1967. P. 281–297.

  3. Alois D., Deshpande A., Hansen P., Popat P. NP-hardness of Euclidean sum-of-squares clustering // Mach. Learn. 2009. V. 75. № 2. P. 245–248.

  4. Rao M. Cluster analysis and mathematical programming // J. Amer. Stat. Assoc. 1971. V. 66. P. 622–626.

  5. Bellman R. Dynamic Programming. Princeton University Press, Princeton, New Jersy, 1957. 342 p.

  6. Глебов Н.И. О выпуклых последовательностях // Дискретный анализ. 1965. Вып. 4. Изд-во ИМ СО РАН, Новосибирск. С. 10–22.

  7. Гимадутдинов Э.Х. О свойствах решений одной задачи оптимального размещения точек на отрезке // Управляемые системы. 1969. Вып. 2. Изд-во ИМ СО РАН, Новосибирск. С. 77–91.

  8. Гимадутдинов Э.Х. Об одном классе задач нелинейного программирования // Управляемые системы. 1969. Вып. 3. Изд-во ИМ СО РАН, Новосибирск. С. 101–113.

  9. Гимади (Гимадутдинов) Э.Х. Выбор оптимальных шкал в одном классе задач типа размещения, унификации и стандартизации // Управляемые системы. 1970. Вып. 6. Изд-во ИМ СО РАН, Новосибирск. С. 57–70.

  10. Xiaolin Wu. Optimal quantization by matrix searching // J. Algorithms. 1991. V. 12. № 4. P. 663–673.

  11. Grønlund A., Larsen K.G., Mathiasen A., Nielsen J.S., Schneider S., Song M. Fast exact k-means, k-medians and Bregman divergence clustering in 1D // CoRR arXiv:1701.07204. 2017.

  12. Кельманов А.В., Кельманова М.А., Хамидуллин С.А. Совместное обнаружение и оценивание повторяющегося фрагмента в зашумленной числовой последовательности при заданном числе квазипериодических повторов // Тез. докл. Российской конф. “Дискретный анализ и исследование операций” (DAOR-4). Новосибирск, 2004. Изд-во ИМ СО РАН, Новосибирск. С. 185.

  13. Гимади Э.Х., Кельманов А.В., Кельманова М.А., Хамидуллин С.А. Апостериорное обнаружение в числовой последовательности квазипериодического фрагмента при заданном числе повторов // Сиб. ж. индустр. математики. 2006. Т. 9. № 1(25). С. 55–74.

  14. Gimadi E.Kh., Kel’manov A.V., Kel’manova M.A., Khamidullin S.A. A Posteriori detecting a quasiperiodic fragment in a numerical sequence // Pattern Recognition and Image Analysis. 2008. V. 18. № 1. P. 30–42.

  15. Кельманов А.В., Хамидуллин С.А. Апостериорное обнаружение заданного числа одинаковых подпоследовательностей в квазипериодической последовательности // Ж. вычисл. матем. и матем. физ. 2001. Т. 41. № 5. С. 807–820.

  16. Kel’manov A.V., Jeon B. A Posteriori joint detection and discrimination of pulses in a quasiperiodic pulse train // IEEE Trans. on Signal Proc. 2004. V. 52. № 3. P. 645–656.

  17. Carter J.A., Agol E., et al. Kepler-36: A pair of planets with neighboring orbits and dissimilar densities // Science. 2012. V. 337. № 6094. P. 556–559.

  18. Кельманов А.В., Пяткин А.В. О сложности одного из вариантов задачи выбора подмножества “похожих” векторов // Докл. АН. 2008. Т. 421. № 5. С. 590–592.

  19. Кельманов А.В., Пяткин А.В. Об одном варианте задачи выбора подмножества векторов // Дискретн. анализ и исслед. опер. 2008. Т. 15. № 5. С. 20–34.

  20. Кельманов А.В., Пяткин А.В. О сложности некоторых задач поиска подмножеств векторов и кластерного анализа // Ж. вычисл. матем. и матем. физ. 2009. Т. 49. № 11. С. 2059–2065.

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

Инструменты

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

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

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