Содержание к диссертации
Введение
1 Квадратичные модели поиска похожих элементов 10
2 Задачи поиска подмножества векторов 27
2.1 Постановки задач 27
2.2 Несуществование схемы FPTAS для общего случая . 31
2.3 Геометрические основы алгоритмов 32
2.4 Алгоритмы решения задач 36
2.4.1 Приближённый полиномиальный алгоритм с гарантированной достижимой оценкой 2 точности . 37
2.4.2 Точный псевдополиномиальный алгоритм 40
2.4.3 Схема FPTAS для специального случая 42
2.5 Заключение к главе 49
3 Задачи поиска подпоследовательности векторов 50
3.1 Постановки задач 50
3.2 Алгоритмы решения задач 54
3.2.1 Вспомогательная задача и точный полиномиальный алгоритм её решения 54
3.2.2 2-приближённый полиномиальный алгоритм . 63
3.2.3 Псевдополиномиальный алгоритм, гарантирующий оптимальное решение задач 65
3.3 Заключение к главе 67
Заключение 68
Литература
- Несуществование схемы FPTAS для общего случая
- Приближённый полиномиальный алгоритм с гарантированной достижимой оценкой 2 точности
- Алгоритмы решения задач
- 2-приближённый полиномиальный алгоритм
Несуществование схемы FPTAS для общего случая
Анализ данных и распознавание образов являются фундаментальными проблемами теоретической кибернетики. Эти проблемы возникают во множестве естественнонаучных и технических приложений, связанных с обработкой данных, и вовлекают множество математических дисциплин для их эффективного решения (математическую статистику, теорию приближения, компьютерную геометрию, дискретную оптимизацию и др.).
Быстрое развитие технологий получения и хранения информации в последние десятилетия привело к невероятному росту объёмов данных (текст, изображения, видео, результаты измерений, данные численных экспериментов), требующих компьютерной обработки. Это стимулирует развитие различных алгоритмов автоматического анализа данных, их классификации и структурирования.
Содержательные проблемы анализа данных и распознавания образов, как правило, формулируются следующим образом: по результатам измерений характеристик некоторых наблюдаемых объектов требуется принять решение о взаимосвязи объектов между собой, а также определить (предсказать) отношение с новыми объектами. Эти задачи делят 12 ся на два класса: классификации (supervised learning) и кластеризации (unsupervised learning). В задачах первого класса предполагается наличие некоторых обучающих данных («меток» на некоторой части входных объектов, определяющих структуру данных), в то время как во втором классе таких данных нет.
Целью задач кластеризации является выделение естественных групп (классов) в заданном множестве входных объектов. Под естественностью группы объектов обычно понимают похожесть объектов из одной группы и различие из разных. Отношения похожести и различия объектов основываются на понятии «меры близости» наборов характеристик объектов. Эти отношения между объектами обычно удовлетворяют определённому набору свойств: рефлексивности, неотрицательности, симметричности [47]. Причём неравенство треугольника, как свойство отношения между объектами, может и не выполняться. Формализация «меры близости» между объектами, адекватно отражающей проблему, само по себе нетривиальная задача, требующая знаний экспертов-прикладников. Без этих знаний на одних и тех же входных данных можно получить совершенно различные решения задачи кластеризации.
Среди известных критериев кластеризации можно отметить, например, критерии максимизации отдалённости объектов разных кластеров (например, максимизация разреза) и критерии минимизации близости объектов одного кластера (например, минимизация среднеквадратичного уклонения, радиуса, диаметра, клики и др.). Кроме того, для кластеризации применяются классические статистические критерии (например, максимум правдоподобия, максимум апостериорной вероятности, мини 13 мум вероятности ошибки).
Многообразие критериев в комбинации с необозримым множеством структур (моделей) анализируемых данных порождает широкий спектр индуцированных экстремальных задач. Как показывает практика, большинство этих задач являются труднорешаемыми, что служит стимулом к построению различных алгоритмов с гарантированными оценками точности.
Среди постановок, базирующихся на минимизации целевой функции, вероятно, самой известной является [46, 54, 59] задача MSSC (Minimum Sum-of-Squres Clustering) — кластеризация (разбиение) векторов евклидова пространства по критерию минимума суммы квадратов расстояний. Задача имеет следующую формулировку
В этой задаче требуется разбить заданное множество векторов евклидова пространства на семейство непустых подмножеств (кластеров) так, чтобы минимизировать сумму по всем подмножествам суммы квадратов расстояний от элементов подмножества до его геометрического центра. Под геометрическим центром множества понимается среднее арифметическое векторов, входящих в это множество. Искомые кластеры трактуются как подмножества, элементы которых соответствуют похожим (по указанному критерию) объектам.
Задача MSSC моделирует [44,46,55] содержательную проблему, в которой требуется разбить таблицу с результатами многократных измерений набора характеристик для нескольких объектов на непустые подмножества, содержащие результаты измерений каждого из объектов, и оценить характеристики этих объектов в условиях, когда соответствие между объектом и результатом измерений отсутствует, а каждому результату измерения сопутствует измерительная ошибка. В качестве примера на рисунке 1.1 изображены результаты измерений двумерного набора характеристик пяти объектов.
В сотнях опубликованных работ были обоснованы разнообразные алгоритмы решения задачи MSSC и её специальных случаев, предложена масса полиномиальных эвристических алгоритмов (без каких-либо теоретических гарантий по точности), ориентированных на решение индивидуальных (прикладных) задач.
Самым популярным эвристическим алгоритмом для решения задачи MSSC является алгоритм /c-means. Первые формулировки появились независимо в [40,54,55,61]. Хотя алгоритм и был предложен более полувека назад, он всё ещё остаётся наиболее распространённым алгоритмом, используемым при решении прикладных задач. Простота реализации и во многих случаях приемлемые практические результаты обеспечили ему такую популярность.
Идея алгоритма основана на простом замечании, что для заданных центров кластеров каждый вектор исходного множества принадлежит тому кластеру, расстояние до центра которого минимально [54]. Начав с некоторого разбиения, алгоритм итеративно производит перераспределение векторов по кластерам, выбирая для каждого вектора кластер с ближайшим геометрическим центром. Таким образом, /c-means является по своей сути жадным алгоритмом, а получаемое с его помощью решение — лишь локальный оптимум. Однако в некоторых ситуациях даже такое решение обеспечивает хороший с точки зрения приложения результат. Так в [57] показано, что с большой вероятностью k-means находит глобальный оптимум, если кластеры «хорошо разделены». В то же время, полученное алгоритмом решение может оказаться сколь угодно хуже оптимального [48].
Приближённый полиномиальный алгоритм с гарантированной достижимой оценкой 2 точности
Объединив неравенства (2.28) и (2.29), получим утверждение леммы. Лемма доказана. Фактически, лемма 2.5 определяет область пространства (шар с центром вс ), любой вектор из которой позволяет гарантированно получить приближённое решение с требуемой точностью. В то же время, лемма 2.6 определяет область поиска, содержащую (неизвестный) центр оптимального решения.
Для произвольного у Є У и положительных чисел /г, Н определим векторное множество Элементы из этого множества соответствуют узлам равномерной сетки с центром в у и шагом h. Параметр Н определяет геометрические размеры сетки. Число точек сетки по каждой координате, очевидно, не превосходит 2 [- J + 1 2- + 1 и не зависит от вектора у.
Замечание 2.2. Для любого вектора ж Є Ж4 такого, что \\у — х\\ Н, где у — центр сетки В (у, h, Н), расстояние от вектора х до ближайшего узла сетки В(у, /г, Н) не превосходит y/qh/2, т.к. по каждой из q координат это расстояние, очевидно, не превосходит /г/2. Для построим множество См(Ь) по формуле (2.8) и вычислим значение F{CM) Шаг 5. Результатом работы алгоритма объявим то множество См(Ь), для которого значение целевой функции F(-) минимально.
Теорема 2.4. Для любого фиксированного є 0 алгоритм Az находит (1 + є)-приближённое решение задачи VS-2. Трудоёмкость алгоритма равна 0(q2N2(2y/qM/s + l)q).
Доказательство. Согласно пошаговой записи алгоритма, на шаге 2 возможны два случая. В первом случае, когда Т м{у) = 0, из леммы 2.6 получаем равенство \\у — с \\ = 0, которое вместе с леммой 2.2 доказывают оптимальность построенного множества См (у) Проанализируем второй случай, когда Т м{у) 0 для всех у Є У. Очевидно, что в ходе работы алгоритма будет рассмотрен каждый вектор у Є С . В соответствии с леммой 2.6, для всех векторов у Є С будет выполнено неравенство (2.27). Из этого неравенства и равенства (2.32) имеем \\у — с Н, т.е. центр оптимального кластера лежит в области сетки В(у, /г, Н). Рассмотрим вектор b = arg min b — с II ьєВ(уАН) из множества В (у, h, Н), ближайший к центру оптимально множества С . Согласно замечанию 2.2, из формулы (2.31) имеем ці ц2 Q 1 Є 2 / \
Поэтому вектор Ь удовлетворяет условиям леммы 2.5, и следовательно, множество См(Ь ) есть (1 + е)-приближённое решение задачи VS-2. Оценим время работы алгоритма. На шагах 1 и 2 вычисление Т м{у) и построение множества См (у) можно осуществить за O(qN) элементарных операций.
Время построения множества В (у, /г, Н) на шаге 3 определяется его мощностью. Из формул (2.31) и (2.32), получаем \B{y,h,H)\ {2H/h + l)q = {2 M/e + l)q. Таким образом, третий шаг потребует 0(q(2y/qM/s + l) q ) элементарных операций.
На шаге 4, для каждого вектора из множества В вычисляются М ближайших к нему элементов множества У. Эти вычисления, согласно утверждению 2.1, потребуют не более О(qN) элементарных операций для каждого вектора из В и 0{qN{2 JqM/ e + \) q ) операций для всех векторов из В. Поэтому суммарная сложность шагов 1-4 для каждого вектора у Є У равна 0{qN{2 /qM/e + 1) ).
Шаги 1-4 выполняются для каждого вектора у Є У, т.е. всего N раз. Отсюда следует окончательная оценка временной сложности алгоритма. Теорема доказана.
Покажем, что при фиксированной размерности q пространства предложенный алгоритм реализует схему FPTAS. Действительно, если є Є (0,1), то для одного из сомножителей в оценке вычислительной сложности алгоритма имеем
Отсюда следует, что при указанных условиях, вре мя работы алгоритма Аз есть величина 0(N (М/є)д). В силу того, что М N, вычислительная сложность алгоритма Аз ограничена полино мом от размера входа задачи и І/є. Следовательно, построенный алго ритм реализует схему FPTAS [41]. 2.5 Заключение к главе В главе 2 исследованы NP-трудные задачи кластеризации заданного множества векторов евклидова пространства и поиска в этом множестве подмножества векторов фиксированной мощности по критерию минимума суммы квадратов расстояний.
Для решения задач предложен эффективный приближённый алгоритмы с гарантированной оценкой точности 2, показана достижимость полученной оценки.
Для специального подслучая рассматриваемых задач, когда размерность пространства фиксирована, а компоненты входных векторов цело-численны, построен точный псевдополиномиальный алгоритм.
Доказано, что для общего случая задач не существует полностью полиномиальной приближённой схемы (FPTAS), если P NP. Для случая фиксированной размерности пространства такая схема обоснована. Глава З Задачи поиска подпоследовательности векторов
В этой главе рассматриваются обобщения задач, изученных в главе 2. Они моделируют проблемы помехоустойчивого анализа многомерных последовательностей (временных рядов). Результаты третьей главы опубликованы в работах [16,17,20,22,25,51].
НАЙТИ: набор АЛ = (пі,... ,пм) номеров элементов последовательности, вектор w и совокупность {vi,i Є ЛГ\А4} векторов, минимизирующих S(-), при условии, что последовательность описывается формулами (2.1) и (2.2), при следующих ограничениях на элементы подмножества M:
Задачи, рассматриваемые в данной главе, индуцируются проблемой, близкой в содержательном плане к проблеме из главы 2. Отличие состоит в дополнительных ограничениях (3.1) на порядок выбора векторов. Если номера членов последовательности интерпретировать равномерные дискретные промежутки времени, то параметры Tmm и Ттах соответствуют минимальному и максимальному интервалам времени между двумя последовательными повторами неизвестного информационно значимого набора. Эти параметры на практике часто бывают априори известны. Величина Ттах — Ттт + 1 определяет степень апериодичности повторов. Случай Tmin = Tmax соответствует самой простой ситуации, когда повторы периодичны. В случае Tmin Ттах подслучай Tmin = 1 и Ттах = N соответствует другой крайней ситуации, когда повторы в наибольшей степени апериодичны.
Поскольку модель анализа данных практически идентична (за исключением дополнительных ограничений (3.1)) модели из главы 2, сведение этой проблемы к сформулированным ниже экстремальным задачам осуществляется точно также, как и в [10]. По этой же причине рассматриваемые в данной главе задачи по своей сути являются обобщением задач главы 2.
Алгоритмы решения задач
Как показано в [11], параметрические варианты этих задач, когда величины Тт[п и Ттах не являются частью входа, также NP-трудны в сильном смысле, если Tmin т Tmax- И лишь в случае Tmin = Tmax задачи разрешимы за полиномиальное время. Действительно, в этом случае подмножество Л4 номеров элементов последовательности однозначно восстанавливается по его первому элементу ri\ Є Л4. Таким образом, для отыскания оптимального решения задачи достаточно за время O(qM) вычислить значение целевой функции для каждого допустимого П\ Є М и среди полученных 0{N) значений выбрать минимальное.
Кроме того, целевые функции задач выбора подпоследовательности связаны формулами h(Mu ...,Mj) = /2(Mi), f2(M) = щщММ), которые аналогичны формулам (2.5) и (2.6), связывающим целевые функции задач второй главы. Поэтому, как и в главе 2, по допустимому решению одной из задач можно построить допустимые решения остальных задач, сохранив оценки точности решений.
В качестве базовой далее рассматривается задача VSS-2. 3.2 Алгоритмы решения задач Суть подхода состоит в замене решения исходной задачи точным решением вспомогательной задачи и в последующей оценке точности этой замены. Оптимальное решение вспомогательной задачи находится с помощью специальной схемы динамического программирования, учитывающей ограничения на номера выбираемых векторов.
Вспомогательная задача и точный полиномиальный алгоритм её решения Для построения алгоритмов решения задачи VSS-2 рассмотрим следующую вспомогательную экстремальную задачу.
Доказательство. Справедливость (3.4) следует из двойного неравенства — результата сложения всех неравенств, входящих в (3.1), и очевидной верхней оценки пм Формула (3.5) устанавливается из комбинирования: 1) результата сложения первых т — 1 неравенств (3.1), 2) результата сложения последних М — т неравенств (3.1), 3) очевидных ограничений 1 п\,пм N.
Для доказательства третьего утверждения леммы заметим, что при каждом т = 2,...,М искомая область допустимых значений компо 57 ненты пт-\ является пересечением двух множеств, а именно: ujm-\ и [п — Ттах_,п — Tmin], где п Є иот. Используя (3.5), подставим формулу для множества иот-\ в последнее выражение. Из полученных неравенств устанавливаем справедливость формулы (3.6).
Лемма 3.2. Если параметры системы ограничений (3.1) связаны неравенством (3.4), то эта система совместна при каждом MG{2,...,7V}.
Доказательство. Для доказательства совместности системы ограничений достаточно показать, что справедливы следующие два условия: 1) шт т 0 при всех т = 1,.. . , М; 2) 7m-i(n) " 0 Для каждого п Є шт при всех т = 2,..., М.
Проверим первое условие. Прибавим тТт[п к обеим частям неравенства (3.4) и, перегруппировав члены, получим ЭТО неравенство в соответствии с определением (3.6) множества 7m-i (п) означает, что второе условие выполнено. Таким образом, оба условия леммы справедливы. наборов номеров последовательности уп,п Є Л/", допустимых в задаче 1. Заметим, что при М = 1 множество Фм не пусто при любых параметрах Tmin и Ттах, входящих в определение (3.9). Для остальных допустимых значений М справедлива
Лемма 3.3. При каждом М Є {2,..., N} множество Фм не пусто тогда и только тогда, когда имеет место неравенство (3.4). Доказательство. Справедливость леммы следует из лемм 3.1 и 3.2. Лемма 3.4. Пусть Фм 0 для некоторого М Є {1,... ,N}. Тогда для этого М оптимальное значение целевой функции вспомогательной задачи находится по формуле
Найдём значение Gm[n минимума по формуле (3.10). Шаг 4. Вычислим значения компонент оптимального набора {пі,... , им} по формулам (3.19) и (3.20). Набор Л4(Ь) = {йі(Ь)}.. .йм(Ь)} объявим результатом работы алгоритма.
Оценку сложности и точности алгоритма устанавливает
Алгоритм Л находит оптимальное решение задачи 1, трудоёмкость алгоритма равна (9(7V(M(Tmax — Tmm + 1) + q)).
Доказательство. Оптимальность решения следует из леммы 3.4. Оценим временную сложность алгоритма.
На первом шаге алгоритма требуется O(qN) операций. Основной вклад трудоёмкости вносит шаг 2.
Трудоёмкость этого шага определяется мощностью множеств иот и 7m-i входящих в формулы (3.10) и (3.11). Мощность первого множества не превосходит N, а мощность второго не больше Ттах — Т1П[п + 1. Вычисления по формуле (3.11) производятся для каждого m = 1,...,М. Поэтому трудоёмкость шага 2 есть величина 0(NM(Tm&x — Tm[n + 1)). Для вычисления оптимального значения целевой функции на третьем шаге потребуется 0{N) операций. Наконец, из формул (3.19) и (3.20) видно, что на шаге 4 требуется (9(М(Ттах — Тт[п + 1)) операций. Суммируя затраты на все шаги, получаем оценку, приведённую в формулировке теоремы.
Замечание 3.1. В оценку временной сложности алгоритма ЛА ВХОДЯТ числовые значения М и (Ттах — Тт[п + 1). Эти значения ограничены сверху размером N входа задачи. Поэтому в общем случае трудоёмкость алгоритма есть величина 0{N(q + Л 2)).
Алгоритм ЛА находит подпоследовательность тех векторов исходной последовательности уп п Є Л/", которые наиболее близки к заданному вектору в смысле минимума суммы квадратов расстояний, и при этом удовлетворяют ограничениям (3.1) исходной задачи. Поэтому решение, построенное алгоритмом для любого Ь Є Ж4 будет допустимым решением исходной задачи VSS-2.
2-приближённый полиномиальный алгоритм
Для вычисления оптимального значения целевой функции на третьем шаге потребуется 0{N) операций.
Наконец, из формул (3.19) и (3.20) видно, что на шаге 4 требуется (9(М(Ттах — Тт[п + 1)) операций. Суммируя затраты на все шаги, получаем оценку, приведённую в формулировке теоремы.
Замечание 3.1. В оценку временной сложности алгоритма ЛА ВХОДЯТ числовые значения М и (Ттах — Тт[п + 1). Эти значения ограничены сверху размером N входа задачи. Поэтому в общем случае трудоёмкость алгоритма есть величина 0{N(q + Л 2)).
Алгоритм ЛА находит подпоследовательность тех векторов исходной последовательности уп п Є Л/", которые наиболее близки к заданному вектору в смысле минимума суммы квадратов расстояний, и при этом удовлетворяют ограничениям (3.1) исходной задачи. Поэтому решение, построенное алгоритмом для любого Ь Є Ж4 будет допустимым решением исходной задачи VSS-2.
Представим алгоритм решения задачи VSS-2 в виде следующей последовательности шагов. Алгоритм Лъ-Вход. Последовательность уп, п Є J\f, натуральные Tmin, Tmax и М 1. Шаг 1. Для каждого п Є Л/", найдём А4(уп) оптимальное решение вспомогательной задачи 1 и значение Gm[n(yn) с помощью алгоритма .
Для оценки трудоёмкости алгоритма достаточно заметить, что шаг 1 — решение вспомогательной задачи 1 с помощью алгоритма ЛА — повторяется N раз, причём трудоёмкость этого алгоритма равна(9(7У(д + 7У2)).
В качестве примера, демонстрирующего достижимость оценки алгоритма, очевидно, можно использовать пример для задачи VS-2 из теоремы 2.2. Теорема доказана.
Псевдополиномиальный алгоритм, гарантирующий оптимальное решение задач Допустим теперь, что компоненты векторов из последовательности Уп,п Є ЛГ имеют целочисленные значения. Следуя логике из главы 2, представим алгоритм решения задачи VSS-2 в виде псевдокода. Алгоритм Лъ Шаг 1. Построим множество В по формулам (2.20). Шаг 2. Для каждого Ь Є , найдём оптимальное решение А4(Ь) вспомогательной задачи 1 и значение Gm[n(b) с помощью алгоритма ЛА Шаг 2. Среди построенных решений выберем решение с наименьшим значением Gm[n(b).
Если все векторы последовательности уп,п Є J\f имеют целочисленные компоненты, то алгоритм AQ находит оптимальное решение задачи VSS-2 за врем„я 0(N(N2 + q)(2MB + l)q).
Доказательство. Пусть АЛ — оптимальное решение задачи VSS-2, а у (АЛ ) = jj Y neM Уп — Центр подмножества {уп,п Є М }.
Из целочисленности компонент векторов входной последовательности и определений (2.19) и (2.20) следует, что вектор у (АЛ ) лежит во множестве В. Поэтому из пошаговой записи алгоритма имеем Объединив (3.27) и (3.28), получим оценку/2(JMA) f2(AA ), из которой очевидным образом следует оптимальность решения АЛА.
Оценим временную сложность алгоритма. Общая трудоёмкость получается из произведения трудоёмкости алгоритма ЛА решения вспомога 68 тельной задачи и мощности множества В, для каждого элемента которого решается вспомогательная задача. Поскольку, согласно (2.19) и (2.20), \Б\ = (2MB + l)q, а трудоёмкость ЛА есть величина 0(N(N2 + q)), результирующая трудоёмкость алгоритма равна 0(N(N2 + q)(2MB + l)q) Теорема доказана.
Замечание 3.2. При фиксированной размерности пространства сложность алгоритма AQ очевидно равна 0(N3(MB)q). При этом величина М N", т.е. ограничена размером входа задачи. Поэтому псевдополиномиальность алгоритма при фиксированной размерности q пространства следует из того, что временная сложность алгоритма ограничена полиномом от размера входа задачи и от значений числовых данных на входе задачи.
В главе 3 исследованы NP-трудные в сильном смысле задачи поиска в конечной последовательности векторов евклидова пространства подпоследовательности фиксированной длины по критерию минимума суммы квадратов расстояний от элементов подпоследовательности до её геометрического центра при ограничении на номера включаемых в искомую подпоследовательность векторов.
Показано, что для общего случая этих задач не существует полностью полиномиальной приближённой схемы.
Обоснован полиномиальный приближённый алгоритм с гарантированной достижимой оценкой 2 точности. Для специального случая задач, когда компоненты векторов имеют целочисленные значения, а размерность пространства фиксирована, предложен псевдополиномиальный алгоритм, гарантирующий отыскание оптимального решения задач.
Ядром построенных алгоритмов является предложенная схема динамического программирования, обеспечивающая точное эффективное решение вспомогательной экстремальной задачи. Заключение
Основные результаты диссертационной работы заключаются в следующем:
1. Для евклидовой задачи поиска в конечном множестве подмноже ства фиксированной мощности и для евклидовой задачи поиска в конеч ной последовательности подпоследовательности фиксированной длины по критерию минимума суммы квадратов расстояний от элементов под множества (подпоследовательности) до его (её) геометрического центра: а) построены приближённые полиномиальные алгоритмы и установ лена гарантированная достижимая оценка 2 точности этих алгоритмов; б) обоснованы точные псевдополиномиальные алгоритмы для случая, когда размерность пространства фиксирована, а компоненты векторов цел очисленны.
2. Установлено, что для общих случаев рассматриваемых задач не существует полностью полиномиальных приближённых схем (FPTAS), если P NP, И такая схема построена для задачи поиска подмножества для случая фиксированной размерности пространства. Результаты работы могут быть использованы в приложениях, связанных с анализом данных и распознаванием образов, а также в компьютер 71 ной геометрии, теории приближения, статистики и др. Представляется, что подходы к построению алгоритмов и технические приёмы, предложенные в работе, будут полезны при исследовании новых задач в указанных областях.
Делом ближайшей перспективы представляется обоснование алгоритмов другого типа (PTAS, рандомизированных, FPTAS для специальных случаев и др.) для решения рассмотренных в работе задач. Представляет интерес выяснение сложностного статуса рассмотренных задач в случае, когда размерность пространства фиксирована.
