ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 6, с. 1076-1085
УДК 519.7
ПРИБЛИЖЕННЫЙ ПОЛИНОМИАЛЬНЫЙ АЛГОРИТМ ДЛЯ ОДНОЙ ЗАДАЧИ БИКЛАСТЕРИЗАЦИИ ПОСЛЕДОВАТЕЛЬНОСТИ1
© 2015 г. А. В. Кельманов*, **, С. А. Хамидуллин*
(*630090 Новосибирск, пр-т Акад. Коптюга, 4, Ин-т матем. СО РАН;
**630090Новосибирск, ул. Пирогова, 2, Новосибирск. гос. ун-т) e-mail: kelm@math.nsc.ru; kham@math.nsc.ru Поступила в редакцию 23.01.2014 г.
Рассматривается NP-трудная в сильном смысле задача разбиения конечной последовательности векторов евклидова пространства на два кластера по критерию минимума суммы квадратов расстояний от элементов кластеров до их центров. Центр первого кластера является оптимизируемой величиной и определяется как среднее значение по всем векторам, образующим этот кластер. Центр второго кластера фиксирован в начале координат. При этом разбиение подчинено условию: разность между номерами последующего и предыдущего векторов, входящих в первый кластер, ограничена сверху и снизу заданными константами. Предложен 2-приближенный полиномиальный алгоритм решения этой задачи. Библ. 14.
Ключевые слова: последовательность евклидовых векторов, кластеризация, минимум суммы квадратов расстояний, NP-трудность, полиномиальный приближенный алгоритм.
DOI: 10.7868/S0044466915060071
ВВЕДЕНИЕ
Предметом исследования настоящей работы является одна из труднорешаемых задач дискретной оптимизации. Цель исследования — обоснование приближенного полиномиального алгоритма с априорно доказуемой оценкой точности для ее решения.
Рассматриваемая задача индуцируется, в частности, актуальными проблемами теории приближения, статистического анализа многомерных временных рядов, а также математическими проблемами распознавания образов (см., например, [1]—[6] и цитированную там литературу). С другой стороны, эта задача важна для многих естественно-научных и технических приложений, в которых требуется классификация упорядоченных по времени данных численных экспериментов или результатов наблюдения за состояниями каких-либо материальных объектов (см., например, [7]—[10] и цитированную там литературу).
Пример содержательной проблемы, которая приводит к решению рассматриваемой задачи, состоит в следующем. Некоторый материальный объект может находиться в конечном множестве активных и пассивном состояниях. Допустим, что имеется таблица, содержащая упорядоченные по времени результаты измерений набора числовых информационно значимых характеристик этого объекта. В пассивном состоянии все числовые характеристики из набора равны нулю, а в любом активном — значение хотя бы одной характеристики не равно нулю. Табличные данные содержат измерительную ошибку. Соответствие элементов таблицы какому-либо состоянию объекта неизвестно. Однако известно, что временной интервал между двумя последовательными активными состояниями объекта ограничен сверху и снизу некоторыми константами. Требуется разбить таблицу на подмножества наборов, соответствующих пассивному и активным состояниям объекта, а также оценить по результатам измерения набор характеристик объекта в каждом активном состоянии (учитывая, что данные содержат ошибку измерения).
В [2] и [3] установлено, что формализация этой проблемы в виде задачи приближения по критерию минимума суммы квадратов уклонений индуцирует NP-трудную в сильном смысле экстремальную задачу даже в простейшем случае, когда таблица содержит упорядоченные по времени данные только об одном активном и одном пассивном состояниях объекта и необходимо раз-
1) Работа выполнена при финансовой поддержке РФФИ (коды проектов 15-01-00462, 13-07-00070).
бить эту таблицу всего на два кластера. Задача приближения фактически состоит (см. [2] и [3]) в аппроксимации заданной векторной последовательности такой искомой последовательностью, что она содержит неизвестный (подлежащий оцениванию) повторяющийся вектор, который перемежается с нуль-векторами. При этом число нуль-векторов между двумя последовательными повторами ненулевого вектора произвольно, но ограничено сверху и снизу заданными константами, а суммарное число повторов неизвестно. К идентичной формулировке (см. [2] и [3]) рассматриваемой ниже экстремальной задачи приводит статистическая постановка проблемы в случае, когда критерием решения является максимум правдоподобия, в предположении, что возмущающая ошибка (помеха) является некоррелированной последовательностью одинаково распределенных гауссовских случайных величин с нулевым средним и конечной дисперсией. Наконец, заметим, что рассматриваемая задача моделирует (см. [2] и [3]) одну из слабо изученных проблем кластеризации, возникающую в рамках известной обобщенной проблемы обучения компьютера распознаванию образов (Machine learning problem) [4], [5].
Таким образом, в силу того, что рассматриваемая NP-трудная задача является базовой для ряда теоретических и прикладных проблем, она показывает труднорешаемость этих проблем и по этой причине ее решение представляет значительный интерес. Формальная постановка задачи приведена в следующем разделе. Там же приведены характеристики существующего алгоритма, предложенного для одного из ее частных, но NP-трудных случаев. Здесь лишь отметим, что мотивацией данного исследования послужило отсутствие каких-либо эффективных алгоритмов с гарантированными оценками точности для общего случая этой задачи.
1. ФОРМУЛИРОВКА ЗАДАЧИ И ИЗВЕСТНЫЕ РЕЗУЛЬТАТЫ
Положим Я = {1,...,N}. Проблемы, сформулированные во введении, индуцируют (см. [3]) следующую задачу.
Задача 1-MSSC-S-NF. Дано: последовательность ty = (yь...,yN) векторов из [Rq, натуральные числа Tmin и Tmax. Найти: подмножество М = {n,..., nM} с Я номеров элементов последовательности ty такое, что
F(M) = XI |У j - У(М)|2 + X НУ J2 ^ min, (1.1)
jeM ie.N \ М
где y (M) = М ХеМУ', при ограничениях
Tmin < Пт - Пт_1 < Tmax, Ш = 2,..., M, (1.2)
на элементы набора М.
В этой задаче векторы последовательности ty с номерами из подмножества М соответствуют кластеру (подпоследовательности) с центром y (М). Неизвестный вектор У( М) в проблеме приближения (см. введение) соответствует вектору, повторяющемуся в искомой последовательности. Векторы с номерами из набора Я \ М ассоциируются с кластером, центр которого фиксирован в начале координат. Элементы из этого кластера в искомой последовательности заполняют промежутки между двумя последовательными повторами вектора y(М). Участок искомой последовательности, содержащий два последовательных повтора, выглядит (см. [3]) как ..., y(М),0,..., 0, y(М),..., причем неизвестное число нулевых элементов между повторами, согласно (1.2), лежит в интервале от 0 до N - 2.
Если номера членов последовательности ty интерпретировать как равномерные дискретные отсчеты времени, то элементы набора М = {n1,..., nM} номеров этой последовательности в содержательной проблеме соответствуют моментам времени, в которые объект находился в активном состоянии. При этом элементы последовательности соответствуют строкам таблицы. Номера из набора Я \ М соответствуют моментам времени, в которые объект находился в пассивном состоянии. Натуральные Tmin и Tmax в формулировке задачи соответствуют минимальному и максимальному интервалам времени между двумя последовательными активными состояниями объекта.
Набор символов MSSC-S в кратком названии этой задачи образован от английского словосочетания Minimum Sum-of-Squares Clustering, for the case of Sequence. Символы MSSC подчерки-
вают сходство с классической (см. [4]) труднорешаемой (см. [6]) задачей MSSC (Minimum Sum-of-Squares Clustering). Символы NF (от английского Not Fixed) указывают на то, что мощности искомых кластеров не фиксированы. Задача 1-MSSC-S-NF является частным, но NP-трудным случаем задачи J-MSSC-S-NF (когда J = 1) [3]. В задаче J-MSSC-S-NF требуется разбить входную последовательность на J + 1 кластер, причем центры J кластеров являются оптимизируемыми величинами, а центр одного из кластеров фиксирован в начале координат [3].
В [3] было установлено, что эта задача NP-трудна в сильном смысле для любых Tmin < Tmax. В тривиальном случае, когда Tmin = Tmax, задача разрешима за полиномиальное время.
Поскольку сформулированная задача NP-трудна в сильном смысле, для этой задачи не существует (см. [11]) полиномиальных и псевдополиномиальных алгоритмов, гарантирующих отыскание точного решения (в предположении справедливости гипотезы P Ф NP). Кроме того, если гипотеза P Ф NP верна, то из результатов работ [3] и [11] следует, что для этой задачи не существует полностью полиномиальной аппросимационной схемы (FPTAS).
На настоящий момент известен (см. [12]) только один полиномиальный приближенный алгоритм с оценкой точности, ориентированный на решение лишь частного (но тем не менее NP-труд-ного в сильном смысле) случая задачи 1-MSSC-S-NF, когда Tmin = 1 и Tmax = N. Этот алгоритм
позволяет находить 2-приближенное решение за время ©(qN2). Ниже для общего случая задачи 1-MSSC-S-NF построен полиномиальный 2-приближенный алгоритм, временная сложность
которого есть величина ©(N 2(N + q)).
2. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ
Суть предлагаемого подхода к построению приближенного алгоритма состоит в замене решения исходной задачи 1-MSSC-S-NF решением более простой вспомогательной задачи и последующей оценкой точности этой замены. Для построения алгоритма сформулируем свойства элементов из набора М.
Лемма 1. Пусть элементы набора (n1, ..., nM) принадлежат множеству Л и удовлетворяют системе ограничений (1.2). Тогда верно следующее:
1) M < Mmax, где
Mmax =L(N - 1)/TmJ+ 1; (2.1)
2) при каждом фиксированном M е {1,..., Mmax} для любого m е {1,..., M} элемент nm из набора (n1,..., nM) принадлежит множеству
fflm(M) = {n| 1 + (m - 1) Tmin < n < N - (M - m) Tmin};
3) при каждом фиксированном M e {2,..., Mmax} для любого m e {2,..., M} справедливо: если в наборе (n,..., nM) элемент nm = n, где n e rom(M), то элемент nm-1 принадлежит множеству
Ym-1(n) = {j max{ 1 + (m - 2) Tmin, n - T^} < j < n - T^J;
4) если в наборе (n1, ..., nM) элемент nm = n, то элемент nm-1 принадлежит множеству
Y(n) = {j
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.