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

ВВЕДЕНИЕ

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

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

Несмотря на то что обе задачи интенсивно исследуются в последние годы и для них построены (см. следующий раздел) эффективные алгоритмы с теоретическими гарантиями качества (точности и временной сложности), быстрые алгоритмы с линейной трудоемкостью до настоящего времени отсутствовали. Между тем быстрые эффективные алгоритмы с теоретическими гарантиями качества – необходимый и востребованный (особенно в последние годы) математический инструмент для решения большеразмерных задач (Big-scaling problems), возникающих, в частности, при решении проблем редактирования и очистки данных (Data editing, Data cleaning), интерпретации данных (Data mining), а также проблем машинного обучения (Machine learning) (см. следующий раздел).

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

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

Всюду далее используются следующие обозначения: $\mathbb{R}$ – множество вещественных чисел, $\left\| {\, \cdot \,} \right\|$ – евклидова норма, $\langle \cdot , \cdot \rangle $ – скалярное произведение.

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

Задача 1. Дано: множество $\mathcal{Y} = \{ {{y}_{1}},\; \ldots ,\;{{y}_{N}}\} $ точек в евклидовом пространстве размерности $d$ и натуральное число $M \leqslant N$. Найти: подмножество $\mathcal{C} \subseteq \mathcal{Y}$ мощности $M$ такое, что

где

есть центроид множества $\mathcal{C}$.

Задача 2. Дано: $N$-элементное множество $\mathcal{Y}$ точек в евклидовом пространстве размерности $d$ и натуральное число $M \leqslant N$. Найти: разбиение множества $\mathcal{Y}$ на два непустых кластера $\mathcal{C}$ и $\mathcal{Y}{\backslash }\mathcal{C}$ такое, что

при ограничении ${\text{|}}\mathcal{C}{\text{|}} = M$.

Задачу 1 можно трактовать как поиск во множестве $\mathcal{Y}$ подмножества $\mathcal{C}$ в виде сферического сгущения из $M$ точек с минимальным суммарным квадратичным разбросом относительно их неизвестного центроида. Поскольку центроид одноточечного множества совпадает с единственной точкой этого множества, задачу можно также трактовать как разбиение множества $Y$ на $N - M + 1$ кластеров, мощность одного из которых равна $M$, а мощность остальных $N - M$ кластеров равна $1$.

В задаче 2 требуется найти 2-разбиение множества $\mathcal{Y}$, минимизирующее сумму мощностно взвешенных внутрикластерных суммарных квадратичных разбросов относительно заданного в начале координат центра одного кластера – $\mathcal{Y}{\backslash }\mathcal{C}$ – и относительно неизвестного центроида – $\bar {y}(\mathcal{C})$ – у другого кластера $\mathcal{C}$.

В прикладном плане обе рассматриваемые задачи можно трактовать, в частности, в виде проблем редактирования и очистки данных (Data editing, Data cleaning), интерпретации данных (Data mining), а также проблем машинного обучения (Machine learning) (см., например, [1]–[8] и цитированные там работы). Некоторые содержательные трактовки задач 1 и 2 можно найти в [9]–[18].

Задача 1 имеет следующую интерпретацию в терминах очистки или редактирования данных. Имеется таблица $\mathcal{Y}$, содержащая результаты $\{ {{y}_{1}},\; \ldots ,\;{{y}_{N}}\} $ измерений $d$-мерного набора $y$ числовых информационно значимых характеристик семейства некоторых объектов. Некоторые объекты в этом семействе идентичны и имеют одинаковые характеристики; число $M$ таких объектов известно. Остальные объекты имеют различные характеристики, не совпадающие с характеристиками идентичных объектов. В каждом результате измерения, представленном в таблице, имеется ошибка. При этом соответствие между объектами и элементами таблицы неизвестно. Требуется, используя критерий минимума суммы квадратов расстояний, найти подмножество $\mathcal{C}$ наборов, соответствующих идентичным объектам, и оценить по результатам измерений набор $\bar {y}(\mathcal{C})$ характеристик этих объектов (учитывая измерительные ошибки). Легко видеть, что оставшиеся одноэлементные кластеры можно трактовать как так называемые “выбросы”, которые могут присутствовать в таблице с данными из-за возможных сбоев измерительного прибора.

В терминах анализа данных задачу 2 можно трактовать аналогичным образом. Имеется таблица $\mathcal{Y}$, содержащая результаты измерений совокупности объектов из двух групп $\mathcal{C}$ и $\mathcal{Y}{\backslash }\mathcal{C}$, включающих однородные или одинаковые (по некоторому набору характеристик) изделия. Первая группа $\mathcal{C}$ содержит $M$ изделий, а вторая – $(N - M)$. Изделия из первой группы имеют неизвестные характеристики, а изделия из второй – заданные (в частности, можно считать, что значения всех характеристик равны нулю). Требуется, используя критерий (1), по результатам измерений разбить совокупность изделий на две группы (части) и оценить набор $\bar {y}(\mathcal{C})$ характеристик изделий из первой группы, учитывая, что данные получены с измерительной ошибкой. Поскольку ${\text{|}}\mathcal{Y}{\text{|}} = N$, ${\text{|}}\mathcal{C}{\text{|}} = M$ и ${\text{|}}\mathcal{Y}{\backslash }\mathcal{C}{\text{|}} = N - M$, а $N$ и $M$ заданы на входе задачи, нетрудно видеть, что задача 2 заключается в 2-разбиении данных по правилу Байеса при заданных априорных вероятностях

двух групп изделий.

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

Задача 1 известна также под названием $M$-Variance [19]. Сильная NP-трудность евклидова случая задачи доказана в [9]. В этой же работе установлено, что для общего случая задачи не существует полностью полиномиальной аппроксимационной схемы (FPTAS), если $P \ne NP$. Точные алгоритмы с трудоемкостью $\mathcal{O}(d{{N}^{{d + 1}}})$ предложены в [19], [20]. Если размерность $d$ пространства фиксирована (ограничена константой), то эти алгоритмы полиномиальны и их трудоемкость оценивается величиной $\mathcal{O}({{N}^{{d + 1}}})$.

В [10] предложен точный алгоритм для случая целочисленных входных данных. Трудоемкость алгоритма равна $\mathcal{O}(dN{{(2MB + 1)}^{d}})$, где $B$ – максимальное абсолютное значение координат точек входного множества. Если размерность пространства ограничена константой, то алгоритм псевдополиномиален и имеет трудоемкость $\mathcal{O}(N{{(MB)}^{d}})$.

Для общего случая задачи 1 в [11] представлен 2-приближенный полиномиальный алгоритм с трудоемкостью $\mathcal{O}(d{{N}^{2}})$. Полиномиальная приближенная схема (PTAS) построена в [21]. Время работы этой схемы $\mathcal{O}(d{{N}^{{2/\varepsilon + 1}}}{{(9{\text{/}}\varepsilon )}^{{3/\varepsilon }}})$, где $\varepsilon > 0$ – относительная ошибка.

В [12] предложен алгоритм, который позволяет находить $(1 + \varepsilon )$-приближенное решение задачи за время $\mathcal{O}(d{{N}^{2}}{{(2\sqrt d M{\text{/}}\varepsilon + 2)}^{d}})$ для заданного $\varepsilon \in (0,1)$. В случае фиксированной размерности $d$ пространства алгоритм имеет трудоемкость $\mathcal{O}({{N}^{2}}{{(M{\text{/}}\varepsilon )}^{d}})$ и реализует схему FPTAS.

Улучшенный алгоритм, позволяющий находить приближенное решение задачи с относительной погрешностью $\varepsilon $ за время

предложен в [13]. Этот алгоритм реализует схему FPTAS в случае фиксированной размерности $d$ пространства, поскольку в этом случае имеет трудоемкость $\mathcal{O}({{N}^{2}}{{(1{\text{/}}\varepsilon )}^{{d/2}}})$. В этой же работе была предложена другая улучшенная приближенная схема, имеющая трудоемкость

Эта схема остается полиномиальной в случае, когда размерность $d$ пространства есть величина $\mathcal{O}(logN)$, т.е. в случае, когда размерность пространства – медленно растущая функция от мощности входного множества. В этом случае алгоритм реализует схему PTAS с трудоемкостью

где $C$ – положительная константа.

Следующие результаты были получены для задачи 2. Напомним, что задача 2 в постановочном плане близка к известной [22]–[25] задаче Mini-Sum 2-clustering (другое название – Min-Sum All-Pairs 2-clustering), в которой требуется найти разбиение, минимизирующее сумму

В задаче Mini-Sum 2-clustering центроиды обоих кластеров неизвестны, а в задаче 2 неизвестен только один. Эти задачи не эквивалентны. Сильная NP-трудность евклидовых случаев обеих задач была установлена в [14], [15]. Там же доказано, что для общего случая этих задач не существует схемы FPTAS, если $P \ne NP$.

Точный алгоритм для случая целочисленных координат входных точек задачи 2 предложен в [16]; время работы алгоритма – $\mathcal{O}(dN{{(2MB + 1)}^{d}})$, где $B$ – максимальное абсолютное значение координат входных точек. Если размерность $d$ пространства ограничена константой, то алгоритм псевдополиномиален и имеет трудоемкость $\mathcal{O}(N{{(MB)}^{d}})$.

Приближенный эффективный алгоритм для общего случая задачи 2 представлен в [17]. Этот алгоритм находит $2$-приближенное решение задачи за время $\mathcal{O}(d{{N}^{2}})$.

В [18] предложен алгоритм, который находит приближенное решение задачи с относительной погрешностью $\varepsilon $ за время

В случае фиксированной размерности $d$ пространства этот алгоритм реализует схему FPTAS, так как в этом случае его трудоемкость равна $\mathcal{O}({{N}^{2}}{{(1{\text{/}}\varepsilon )}^{{d/2}}})$.

Кроме того, в [13] предложена модификация этого алгоритма с улучшенной трудоемкостью

Модифицированный алгоритм реализует FPTAS с трудоемкостью $\mathcal{O}({{N}^{2}}{{(1{\text{/}}\varepsilon )}^{{d/2}}})$ в случае фиксированной размерности $d$ пространства и остается полиномиальным в случае, когда размерность пространства есть величина $\mathcal{O}(logN)$. В последнем случае он реализует PTAS с трудоемкостью

где $C$ – положительная константа.

В настоящей работе для общего случая задач 1 и 2 предложены рандомизированные параметризованные алгоритмы. При условии $M \geqslant \beta N$, где $\beta \in (0,1)$ – некоторая константа, для заданных $\varepsilon > 0$ и $\gamma \in (0,1)$ алгоритмы находят $(1 + \varepsilon )$-приближенные решения задач с вероятностью не менее $1 - \gamma $ за время $\mathcal{O}(dN)$. Найдены условия асимптотической точности предложенных алгоритмов, то есть условия, при которых алгоритмы находят $(1 + {{\varepsilon }_{N}})$-приближенные решения задач за время $\mathcal{O}(d{{N}^{2}})$ с вероятностью не менее $1 - {{\gamma }_{N}}$, где ${{\varepsilon }_{N}} \to 0$ и ${{\gamma }_{N}} \to 0$ при $N \to \infty $.

2. ОСНОВЫ АЛГОРИТМОВ

Для обоснования алгоритмов нам потребуется несколько вспомогательных утверждений. Вероятностной основой алгоритмов являются следующие две леммы [26]. Первая основана на неравенстве Маркова, вторая – на неравенстве Чернова для вероятности больших уклонений.

Лемма 1. Пусть $\mathcal{Z}$ – произвольное $N$-элементное множество точек из ${{\mathbb{R}}^{d}}$, $\mathcal{C} \subseteq \mathcal{Z}$, ${\text{|}}\mathcal{C}{\text{|}} = M$, а $\mathcal{T}$ – мультимножество, полученное $k$ случайными независимыми выборками (с возвращением) по одному элементу из множества $\mathcal{Z}$. Пусть

суть центроиды множества $\mathcal{C}$ и мультимножества $\mathcal{T} \cap \mathcal{C}$ соответственно. Тогда для любого натурального $t \leqslant k$ и произвольного $\delta \in (0,1)$ справедлива оценка

Лемма 2. Пусть выполнены условия леммы 1. Тогда для произвольного $\nu \in (0,1)$ справедлива оценка

Доказательство следующей леммы приведено в [16].

Лемма 3. Пусть

Тогда справедливы следующие утверждения:

$1)$ для любого непустого множества $\mathcal{C} \subseteq \mathcal{Y}$ минимум функции $S(\mathcal{C},x)$ по $x \in {{\mathbb{R}}^{d}}$ достигается в точке $\bar {y}(\mathcal{C}) = \tfrac{1}{{{\text{|}}\mathcal{C}{\text{|}}}}\sum\limits_{y \in \mathcal{C}} \,y$;

$2)$ если ${\text{|}}\mathcal{C}{\text{|}} = M = {\text{const}}$, то для любой фиксированной точки $x \in {{\mathbb{R}}^{d}}$ минимум функции $S(\mathcal{C},x)$ по $\mathcal{C} \subseteq \mathcal{Y}$ достигается на множестве ${{\mathcal{B}}^{x}}$, состоящем из $M$ точек множества $\mathcal{Y}$, имеющих наименьшие значения функции

3. РАНДОМИЗИРОВАННЫЕ АЛГОРИТМЫ

Общий подход к построению алгоритмов для рассматриваемых труднорешаемых задач – классический. А именно, для каждой из задач строится семейство допустимых решений (кластеров) и в найденном семействе выбирается наилучшее в смысле минимума целевой функции. При этом построение допустимых решений опирается на отличающиеся свойства оптимальных решений задач. В задаче 1 это известное (см., например, [11]) свойство состоит в том, что $M$ точек оптимального решения являются точками множества $\mathcal{Y}$, ближайшими по расстоянию к неизвестному центроиду. В задаче 2 свойство оптимального решения устанавливается (см. [16]) утверждениями приведенной выше леммы 3.

Сформулируем алгоритм решения задачи 1.

Алгоритм ${{\mathcal{A}}_{1}}$

Вход: множество $\mathcal{Y}$, натуральное число $M$, натуральный параметр $k$.

Шаг 1. Сформируем мультимножество $\mathcal{T}$ точек с помощью $k$ независимых случайных выборок (с возвращением) по одному элементу из множества $\mathcal{Y}$.

Шаг 2. Для каждого непустого мультиподмножества $\mathcal{H}$ мультимножества $\mathcal{T}$ вычислим центроид $\bar {y}(\mathcal{H})$ и сформируем подмножество $\mathcal{C}$ из $M$ элементов множества $\mathcal{Y}$, ближайших (по расстоянию) к $\bar {y}(\mathcal{H})$. Вычислим и запомним значение функции $f(\mathcal{C})$.

Шаг 3. В семействе решений, найденных на шаге 2, выберем подмножество $\mathcal{C} = {{\mathcal{C}}_{{{{\mathcal{A}}_{1}}}}}$, для которого значение $f(\mathcal{C})$ минимально. Если оптимальных значений несколько, выберем любое из них.

Выход: множество ${{\mathcal{C}}_{{{{\mathcal{A}}_{1}}}}}$.

Алгоритм решения задачи 2 имеет сходную пошаговую запись. Основное отличие от алгоритма ${{\mathcal{A}}_{1}}$ состоит в построении допустимых решений задачи на шаге 2.

Алгоритм ${{\mathcal{A}}_{2}}$

Вход: множество $\mathcal{Y}$, натуральное число $M$, натуральный параметр $k$.

Шаг 1. Сформируем мультимножество $\mathcal{T}$ точек с помощью $k$ независимых случайных выборок (с возвращением) по одному элементу из множества $\mathcal{Y}$.

Шаг 2. Для каждого непустого мультиподмножества $\mathcal{H}$ мультимножества $\mathcal{T}$ вычислим центроид $\bar {y}(\mathcal{H})$ и сформируем подмножество $\mathcal{C}$ из $M$ элементов множества $\mathcal{Y}$ с наименьшими значениями функции ${{h}^{{\bar {y}(\mathcal{H})}}}(z),\;z \in \mathcal{Y}$ (используя формулу (2.2) при $x = \bar {y}(\mathcal{H})$). Вычислим и запомним значение функции $g(\mathcal{C})$.

Шаг 3. В семействе решений, найденных на шаге 2, выберем подмножество $\mathcal{C} = {{\mathcal{C}}_{{{{\mathcal{A}}_{2}}}}}$, для которого значение $g(\mathcal{C})$ минимально. Если оптимальных значений несколько, выберем любое из них.

Выход: множество ${{\mathcal{C}}_{{{{\mathcal{A}}_{2}}}}}$.

Свойства алгоритмов устанавливает

Теорема 1. Для произвольного вещественного $\delta \in (0,1)$ и натуральных $t \leqslant k$ алгоритмы ${{\mathcal{A}}_{1}}$ и ${{\mathcal{A}}_{2}}$ находят $\left( {1 + \tfrac{1}{{\delta t}}} \right)$-приближенные решения задач 1 и 2 за время $\mathcal{O}({{2}^{k}}d(k + N))$ вероятностью не менее $1 - (\delta + \alpha )$, где

Доказательство. Докажем оценку точности алгоритма ${{\mathcal{A}}_{1}}$. Пусть $\mathcal{C}_{1}^{ * }$ – оптимальное решение задачи 1, а ${{\mathcal{C}}_{{{{\mathcal{A}}_{1}}}}}$ – множество, найденное алгоритмом ${{\mathcal{A}}_{1}}$.

Предположим, что мультимножество $\mathcal{T}$ сформировано так, что ${\text{|}}\mathcal{T} \cap \mathcal{C}_{1}^{ * }{\text{|}} \geqslant 1$. В этом случае мультимножество $\mathcal{H} = \mathcal{T} \cap \mathcal{C}_{1}^{ * }$ было рассмотрено на шаге 2 алгоритма. Пусть $\mathcal{C}$ – подмножество из $M$ точек множества $\mathcal{Y}$, ближайших к $\bar {y}(\mathcal{T} \cap \mathcal{C}_{1}^{ * })$, построенное на этом шаге.

Из определения шага 3 следует неравенство

Кроме того, поскольку для произвольного конечного множества $\mathcal{Z} \subset {{\mathbb{R}}^{d}}$ минимум суммы $\sum\nolimits_{y \in \mathcal{Z}}^{} {{{{\left\| {y - x} \right\|}}^{2}}} $ по $x \in {{\mathbb{R}}^{d}}$ достигается в точке $x = \tfrac{1}{{{\text{|}}\mathcal{Z}{\text{|}}}}\sum\nolimits_{z \in \mathcal{Z}}^{} z $, для правой части (3.3) имеем

Далее, так как по определению шага 2 множество $\mathcal{C}$ состоит из $M$ точек, ближайших к $\bar {y}(\mathcal{H})$, справедлива оценка

Объединяя (3.3)–(3.5), получаем, что при ${\text{|}}\mathcal{T} \cap \mathcal{C}_{1}^{ * }{\text{|}} \geqslant 1$ справедлива цепочка неравенств

Применяя лемму 1 к $\mathcal{Z} = \mathcal{Y}$ и $\mathcal{C} = \mathcal{C}_{1}^{ * }$, получаем, что при ${\text{|}}\mathcal{T} \cap \mathcal{C}_{1}^{ * }{\text{|}} \geqslant t$ с вероятностью не менее $1 - \delta $ выполнено неравенство

Тогда из (3.6), (3.7) следует, что при ${\text{|}}\mathcal{T} \cap \mathcal{C}_{1}^{ * }{\text{|}} \geqslant t$ с вероятностью не менее $1 - \delta $ справедлива оценка В терминах условной вероятности эта оценка означает, что Поэтому, положив $\alpha = Pr({\text{|}}\mathcal{T} \cap \mathcal{C}_{1}^{ * }{\text{|}} < t)$, для безусловной вероятности противоположного события, т.е. для вероятности несрабатывания алгоритма, найдем равенство Отсюда следует, что вероятность срабатывания алгоритма ${{\mathcal{A}}_{1}}$ оценивается снизу величиной $1 - (\delta + \alpha )$.

Равенство

следует из того, что формирование мультимножества $\mathcal{T}$ состоит из $k$ независимых равновероятных испытаний, в которых “успех” – это событие “элемент, выбранный из $\mathcal{Y}$, лежит в $\mathcal{C}_{1}^{ * }$”.

Доказательство оценки точности алгоритма ${{\mathcal{A}}_{2}}$ частично повторяет доказательство оценки точности алгоритма ${{\mathcal{A}}_{1}}$.

Пусть $\mathcal{C}_{2}^{ * }$ – оптимальное решение задачи 2, а ${{\mathcal{C}}_{{{{\mathcal{A}}_{2}}}}}$ – решение, найденное алгоритмом ${{\mathcal{A}}_{2}}$. Предположим, что в алгоритме ${{\mathcal{A}}_{2}}$ мультимножество $\mathcal{T}$ сформировано так, что ${\text{|}}\mathcal{T} \cap \mathcal{C}_{2}^{ * }{\text{|}} \geqslant 1$. При этом условии пусть $\mathcal{C}$ – подмножество из $M$ точек множества $\mathcal{Y}$ с наименьшими значениями функции ${{h}^{{\bar {y}(\mathcal{H})}}}(z),\;z \in \mathcal{Y}$, построенное на шаге 2 для мультиподмножества $\mathcal{H} = \mathcal{T} \cap \mathcal{C}_{2}^{ * }$.

Из определения шага 3 следует, что

Справедливость следующего неравенства устанавливается с опорой на тот же факт, что и неравенство (3.4), установленное при доказательстве свойств алгоритма ${{\mathcal{A}}_{2}}$:

Далее, в соответствии с определением шага 2 множество $\mathcal{C}$ состоит из $M$ точек множества $\mathcal{Y}$ с наименьшими значениями ${{h}^{{\bar {y}(\mathcal{H})}}}(z),\;z \in \mathcal{Y}$. Поэтому, применяя лемму 3, для правой части (3.9) получим оценку

Наконец, как и при оценке свойств алгоритма ${{\mathcal{A}}_{1}}$, объединяя (3.8)–(3.10) и применяя лемму 1, получаем, что при ${\text{|}}\mathcal{T} \cap \mathcal{C}_{2}^{ * }{\text{|}} \geqslant t$ с вероятностью не менее $1 - \delta $ выполнено неравенство правая часть которого оценивается величиной $\left( {1 + \tfrac{1}{{\delta t}}} \right)g(\mathcal{C}_{2}^{ * })$. Окончание доказательства аналогично окончанию доказательства свойств алгоритма ${{\mathcal{A}}_{1}}$.

Оценим временную сложность алгоритмов. Шаг 1 требует $\mathcal{O}(k)$ операций. Шаг 2 выполняется ${{2}^{k}}$ раз. Центроид каждого мультиподмножества $\mathcal{H}$ в обоих алгоритмах вычисляется за $\mathcal{O}(dk)$ операций. В алгоритме ${{\mathcal{A}}_{1}}$ вычисление расстояний от этого центроида до точек множества $\mathcal{Y}$ требует $\mathcal{O}(dN)$ операций, а $M$ точек, ближайших к центроиду, выбираются за $\mathcal{O}(N)$ операций без сортировки (см., например, [27]). Аналогичным образом, в алгоритме ${{\mathcal{A}}_{2}}$ вычисление значений ${{h}^{{\bar {y}(\mathcal{H})}}}(z)$, $z \in \mathcal{Y}$, требует $\mathcal{O}(dN)$ операций, и нахождение $M$ наименьших элементов из $N$ осуществляется за $\mathcal{O}(N)$ операций без сортировки. Шаг 3 (выбор наименьшего элемента) требует не более $\mathcal{O}({{2}^{k}})$ операций.

Таким образом, временная сложность обоих алгоритмов есть величина $\mathcal{O}({{2}^{k}}d(k + N))$.

Следующее следствие устанавливает условия, при которых оба алгоритма имеют линейную по $d$ и по $N$ временную сложность при заданных верхних границах относительной погрешности $\varepsilon $ и вероятности $\gamma $ несрабатывания.

Следствие 1. Пусть $M \geqslant \beta N$, где $\beta \in (0,1)$ – константа, $\varepsilon > 0$ и $\gamma \in (0,1)$. Тогда при фиксированном параметре

алгоритмы ${{\mathcal{A}}_{1}}$ и ${{\mathcal{A}}_{2}}$ находят $(1 + \varepsilon )$-приближенные решения задач 1 и 2 за время $\mathcal{O}(dN)$ с вероятностью не менее $1 - \gamma $.

Доказательство. Докажем следствие для алгоритма ${{\mathcal{A}}_{1}}$ (доказательство для алгоритма ${{\mathcal{A}}_{2}}$ аналогично).

Пусть $\delta = \tfrac{\gamma }{2}$, $t = \left\lceil {\tfrac{1}{{\delta \varepsilon }}} \right\rceil = \left\lceil {\tfrac{2}{{\gamma \varepsilon }}} \right\rceil $. Заметим, что в этом случае $k \geqslant \tfrac{{2t}}{\beta }$ и $k \geqslant \tfrac{8}{\beta }ln\tfrac{2}{\gamma }$. Применяя лемму 2 к $\nu = \tfrac{1}{2}$ и $\mathcal{C} = \mathcal{C}_{1}^{ * }$, получаем, что

Тогда, в условиях следствия 1, выполнена следующая цепочка оценок:

Следовательно, по теореме 1 для заданного выше значения $k$ алгоритм ${{\mathcal{A}}_{1}}$ находит решение задачи 1 с относительной погрешностью $\tfrac{1}{{\delta t}} = \mathop {\left( {\tfrac{\gamma }{2}\left\lceil {\tfrac{2}{{\gamma \varepsilon }}} \right\rceil } \right)}\nolimits^{ - 1} \leqslant \varepsilon $ за время $\mathcal{O}({{2}^{k}}d(k + N))$ с вероятностью несрабатывания не более $\delta + \alpha \leqslant \tfrac{\gamma }{2} + \tfrac{\gamma }{2} = \gamma $. Поскольку параметр $k$ фиксирован, время работы алгоритма равно $\mathcal{O}(dN)$.

Условия асимптотической точности алгоритмов устанавливает

Теорема 2. Пусть $k = \left\lceil {lo{{g}_{2}}N} \right\rceil $ и $M \geqslant \beta N$, где $\beta \in (0,1)$ – константа. Тогда алгоритмы ${{\mathcal{A}}_{1}}$ и ${{\mathcal{A}}_{2}}$ находят $(1 + {{\varepsilon }_{N}})$-приближенные решения задач 1 и 2 с вероятностью не менее $1 - {{\gamma }_{N}}$ за время $\mathcal{O}(d{{N}^{2}})$, где ${{\varepsilon }_{N}}\;\xrightarrow[{N \to \infty }]{}\;0$, ${{\gamma }_{N}}\;\xrightarrow[{N \to \infty }]{}\;0$.

Доказательство. Оценка времени работы алгоритмов при условии $k = \left\lceil {lo{{g}_{2}}N} \right\rceil $ очевидна.

Оценим  относительную  погрешность и вероятность несрабатывания алгоритма ${{\mathcal{A}}_{1}}$. Пусть $\delta = {{(lo{{g}_{2}}N)}^{{ - 1/2}}}$, $t = \left\lceil {\tfrac{{kM}}{{2N}}} \right\rceil $ в условиях теоремы 1. Тогда относительная ошибка ${{\varepsilon }_{N}} = \tfrac{1}{{\delta t}} = {{(lo{{g}_{2}}N)}^{{1/2}}}{\text{/}}\left\lceil {\tfrac{{kM}}{{2N}}} \right\rceil $ ограничена сверху значением $\tfrac{2}{\beta }{{(lo{{g}_{2}}N)}^{{ - 1/2}}}\;\xrightarrow[{N \to \infty }]{}\;0$.

Далее, применяя лемму 2 для $\nu = \tfrac{1}{2}$ и $\mathcal{C} = \mathcal{C}_{1}^{ * }$, получаем

Следовательно, Таким образом, для вероятности ${{\gamma }_{N}}$ несрабатывания алгоритма ${{\mathcal{A}}_{1}}$ получаем ${{\gamma }_{N}} = \delta + \alpha \;\xrightarrow[{N \to \infty }]{}\;0$. Асимптотические свойства алгоритма ${{\mathcal{A}}_{2}}$ устанавливаются аналогично.

ЗАКЛЮЧЕНИЕ

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

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