Автоматика и телемеханика, № 4, 2014
Задачи математического пр о граммир ования
© 2014 г. А.Е. ГАЛАШОВ
(Новосибирский государственный университет), А.В. КЕЛЬМАНОВ, д-р физ.-мат. наук (Институт математики им. С.Л. Соболева СО РАН, Новосибирск)
2-ПРИБЛИЖЕННЫЙ АЛГОРИТМ ДЛЯ ОДНОЙ ЗАДАЧИ ПОИСКА СЕМЕЙСТВА НЕПЕРЕСЕКАЮЩИХСЯ ПОДМНОЖЕСТВ ВЕКТОРОВ1
Рассматривается задача поиска в конечном множестве векторов евклидова пространства семейства непересекающихся подмножеств, имеющих заданные мощности. Критерием поиска является минимум суммы квадратов расстояний от элементов подмножеств до их центров. Центры подмножеств являются оптимизируемыми величинами и определяются как средние значения по элементам искомых подмножеств. Показано, что задача МР-трудна в сильном смысле. Предложен 2-приближенный алгоритм решения задачи. При фиксированном числе искомых подмножеств алгоритм полиномиален.
1. Введение
Предметом исследования настоящей работы является одна из слабо изученных задач поиска семейства непересекающихся подмножеств в конечном множестве векторов евклидова пространства. Цель работы — анализ сложности этой задачи и обоснование эффективного алгоритма ее решения.
Необходимость исследования — отсутствие каких-либо полиномиальных алгоритмов с гарантированными оценками точности для решения задачи и актуальность задачи для ряда математических дисциплин и технических приложений. Среди математических дисциплин можно отметить, например, компьютерную геометрию, теорию приближения и математическую статистику. Геометрическая трактовка задачи ясна из ее формулировки (см. аннотацию и раздел 3). Интерпретация задачи в виде аппроксимационной и статистической проблем приведена далее в разделе 2. Эта же задача индуцируется, в частности, следующей актуальной прикладной проблемой, характерной для анализа данных и распознавания образов.
1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проекты №№12-01-00090, 13-07-00070).
Имеется таблица, включающая результаты многократных измерений набора числовых информационно значимых характеристик для конечного семейства уникальных материальных объектов. Число проведенных измерений для каждого из этих объектов известно. Кроме того, эта таблица включает результаты однократных измерений некоторых произвольных (случайных) объектов. Характеристики уникальных объектов из семейства в отличие от характеристик остальных объектов имеют принципиальную информационную ценность. В каждом результате измерения, представленном в таблице, имеется ошибка, причем соответствие между элементами таблицы и объектами неизвестно. Требуется, используя критерий минимума суммы квадратов расстояний, найти семейство непересекающихся подмножеств наборов, элементы которого соответствуют уникальным объектам, и оценить по результатам измерения набор характеристик каждого из этих объектов (учитывая, что данные содержат ошибку измерения).
Сформулированная проблема является разновидностью так называемой проблемы «обучения» компьютера распознаванию образов [1]. Ее можно трактовать как одну из возможных многочисленных проблем кластерного анализа данных [2]. Оптимизационная модель сформулированной содержательной проблемы и NP-трудная экстремальная задача, которая индуцируется этой проблемой, приведены далее. Здесь лишь отметим, что эта экстремальная задача отлична от классической [3-5] NP-трудной [6-9] задачи MSSC (Minimum Sum-of-Squares Clustering) кластеризации по критерию минимума суммы квадратов.
Напомним, что задача MSSC в публикациях иногда фигурирует под названием k-Means (k-средних) [2, 4, 8], которое соответствует названию одного из ранних эвристических алгоритмов [4], предложенных для ее решения. Содержательная проблема, индуцирующая задачу MSSC, состоит в разбиении имеющейся таблицы. При этом предполагается, что таблица не содержит результатов измерений произвольных объектов. Однако, судя по имеющимся публикациям (см., например, [1, 2], и цитированные в [1, 2] источники), на практике нередки ситуации, когда табличные данные содержат «мусор» в виде случайных измерительных данных («выбросов»), подлежащих «цензурированию». Рассматриваемая ниже задача моделирует эту ситуацию.
Статья имеет следующую структуру. Формализация сформулированной содержательной проблемы анализа данных и вывод экстремальной задачи, которая индуцируется оптимизационной моделью анализа данных, приведены в разделе 2. В разделе 3 анализируется сложностной статус индуцированной задачи, приводится обзор алгоритмических результатов для ее частного случая и дается важная для приложений трактовка ее оптимального решения. Приближенный алгоритм решения задачи с гарантированной оценкой точности обоснован в разделе 4.
2. Постановка задачи
Рассмотрим модель анализируемых данных в виде последовательности.
Пусть векторная последовательность хп € М9, п , где N = },
имеет следующую структуру
(1) Хп = <
п е М1,
wJ, п е ,
где М С N, М = 0, М ПМк = 0, 2 = к, 2,к = 11.
Допустим, что для обработки доступна последовательность (таблица)
(2) уп = Хп + вп, п е N,
где вп — вектор помехи (ошибки измерения), независимый от вектора Хп.
Учитывая зависимость элементов последовательности (1) от векторов и множеств, положим
(3) М3 ,W1,...,WJ, Кг е^ЛОцЦМ)}) = £ 11Уп - Хп|12
п&М
и рассмотрим модель анализа данных в виде следующей оптимизационной задачи.
Задача 1 (аппроксимация последовательности). Дано: последовательность уп, п е N, векторов из М9 и натуральные числа М1,..., MJ. Найти: семейство (М1, ..., MJ} непересекающихся подмножеств множества N и совокупности (w1,... ,WJ}, (vi,i е )} векторов, минимизирую-
щих (3), при ограничениях 1 = Mj, 2 = 1,..., 3, на мощности искомых подмножеств и при условии, что структура последовательности Хп описывается формулой (1).
В этой модели анализа данных величина 3 ассоциируется с числом уникальных объектов, векторы Wl,...,WJ соответствуют наборам измеряемых характеристик этих объектов (см. содержательную проблему в разделе 1). Мощность Mj множества , 2 = 1,...,3, трактуется как число измерений, проведенных для 2-го объекта. Векторы из совокупности ^е )} интерпретируются как наборы характеристик произ-
вольных (не совпадающих с уникальными) объектов.
Задача 1, по сути, состоит в аппроксимации последовательности уп последовательностью Хп по критерию минимума суммы квадратов уклонений при условии, что структура последовательности Хп задана формулой (1). Покажем, что к этой же задаче приводит одна из возможных статистических моделей содержательной проблемы анализа данных, сформулированной в разделе 1.
Пусть, например, в (2) вектор вп е Фо,о-2/, п е N, где Ф0;О-2/ — ^-мерное гауссовское распределение с параметрами (0, а21), а I — единичная матрица. Тогда, обозначив плотность распределения вектора вп через рп, функцию
правдоподобия от выборки e = {ei,... } можно записать в виде N N 1 . 1
Ле|0, а2) = П I'" = Ц {27т)Ф{а2)Ф 6ХР {-^2 (Уп ~ XnfiVn ~ хп) \ =
1 • //гт ш / 2 ; ,т2 i ^ i i 2( / (
n=1 n=1
N
еХР "¿2
(2na2)qN/2 F | 2qa2 n=i ;
Поэтому для логарифмической функции правдоподобия имеем:
£(е| 0, а2) = 1П2ТГ - Щ- 1п,2 - * £ "
г= 1
Отсюда видно, что при фиксированных N, а и д задача максимизации этой функции сводится к минимизации суммы квадратов уклонений (как и в задаче 1). Другими словами, статистический подход к решению проблемы с использованием критерия максимума правдоподобия сводится к задаче 1 в случае, когда множество {еп|п € .М"} трактуется как последовательность независимых одинаково распределенных гауссовских случайных величин.
Вернемся к задаче 1. Раскрыв сумму квадратов в правой части (3) с учетом (1), получим
(4) s(•) = £ - wjу2 + Е
n - wj У + ууп - Vn
j=1 n&Mj neN\(U/=i Mj)
2
Используя дифференцирование, легко установить, что минимум функционала (4) достигается ] = 1,..., 3, и равен
нала (4) достигается при vn = уп, п € W\(Uj=1Mj), wj = щ^Т^пем^Ут
J 1
(5) Smin(Mi,...,Mj) = E \Уп~Тм~\ E Уп
j=i neMj 1 j 1 neMj
Таким образом, как модель приближения (в виде задачи 1), так и приведенная статистическая модель индуцируют одну и ту же задачу минимизации целевой функции (5).
2
3. Экстремальная задача
Положим Cj = {yn|n € Mj}, Y = {yn|n € N} и, переходя в (5) от суммирования по индексам к суммированию по элементам множеств, получим следующую задачу дискретной оптимизации.
Задача FDVS-(Rq)SD (Family of Disjoint Vector Subsets, Euclidean case for Squared Distances). Дано: множество Y = {yi,...,yN} векторов из Rq
и натуральные числа Mi,..., Mj. Найти: семейство (Ci,..., Cj} непересекающихся подмножеств множества Y такое, что
(6) m, = m) II2 ^ min,
j=i yeCj
где у (Сj) = ■nJ-r у — центр подмножества Сj, при ограничениях \Cj\ = Mj, j yeCj
j = 1,..., J, на мощности искомых подмножеств.
Напомним, что в классической задаче MSSC целевая функция такая же, как и в задаче FDVS-(Rq)SD. Однако в задаче MSSC требуется найти разбиение множества Y на подмножества (кластеры), причем мощности искомых кластеров не заданы на входе, а являются оптимизируемыми величинами. Напротив, в задаче FDVS-(Rq)SD мощности искомых подмножеств заданы, причем семейство искомых непересекающихся подмножеств может не покрывать все множество Y.
Сложностной статус задачи устанавливает следующая теорема.
Теорема 1. Задача FDVS-(Rq)SD NP-трудна в сильном смысле.
Справедливость теоремы 1 следует из того, что частный случай задачи FDVS-(Rq)SD, когда J = 1, является NP-трудной в сильном смысле задачей [10].
Из теоремы 1 следует, что задачи (см. раздел 2) приближения по критерию минимума суммы квадратов уклонений и максимально правдоподобного анализа данных, индуцирующие задачу FDVS-(Rq)SD, относятся к числу труднорешаемых проблем.
Кроме того, из теоремы 1 следует, что для общего случая задачи FDVS-(Rq)SD не существует [11] точных полиномиального и псевдополиномиального алгоритмов (в предположении, что гипотеза P = NP верна). Наконец, если P = NP, то для этой задачи не существует полностью полиномиальная приближенная схема (FPTAS). Действительно, в соответствии с [11] отсутствие FPTAS для NP-трудной
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.