Содержание к диссертации
Введение
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].
На основе алгоритма /c-means разработано целое множество различных модификаций. Некоторые основаны на использовании различных эвристик, включающих ограничение на минимальный размер кластеров, на число процедур объединения и разбиения кластеров. Среди таких алгоритмов в качестве наиболее популярных можно выделить эвристические алгоритмы ISODATA [34] и FORGY [40]. В этих алгоритмах каждый элемент исходного множества приписывается к единственному кластеру (так называемое, строгое приписывание).
В отличие от упомянутых, эвристический алгоритм Fuzzy c-means, предложенный в [38], а затем улучшенный в [35], позволяет каждому элементу принадлежать множеству кластеров. Предварительная обработка исходных данных, суть которой состоит в замене групп элементов их геометрическими центрами, в некоторых ситуациях позволяет [39] ускорить алгоритмы /c-means и Fuzzy c-means.
Идея итеративного локально оптимального перемещения текущего центра одного из кластеров в один из элементов исходного множества лежит в основе алгоритма J-means и его модификации VNS J-means (комбинации алгоритма J-means и эвристики Variable Neighborhood Search) [42].
Разработанный для выделения кластеров произвольной формы, алгоритм Kernel /c-means основан на предварительной эвристической настройке функции похожести [60].
Значительно меньше работ посвящено алгоритмам с гарантированными оценками точности. В работе [56] был предложен (1 + є)-приближённый алгоритм с трудоёмкостью 0(Nlog Ne 2qJ ). В основе алгоритма лежит идея аппроксимации центров кластеров точками из конечного множества специального вида (сетки). На основе этой идеи в [48] предложен алгоритм, который находит (9 + е)-приближённое решение задачи за время 0(N [logTV + e q\og{\/e) + NJ:ilogN]).
Приближённый полиномиальный алгоритм с гарантированной достижимой оценкой 2 точности
В [1,4,12,13] установлена NP-трудность в сильном смысле обеих задач максимизации. Из этих результатов, как обобщение, следует NP-трудность в сильном смысле задач J-MSSC-F и J-MSSC-NF. Как показано в [13], параметрические варианты этих задач, когда параметр J не является частью входа (фиксирован), также являются NP-трудными в сильном смысле задачами.
В алгоритмическом плане задачи слабо изучены. Лишь для простейшего случая J = 1 построены алгоритмы с гарантированными оценками качества. В [4] для задачи LVS построен эффективный приближённый алгоритм с трудоёмкостью O(qN). Алгоритм не имеет гарантированной оценки точности, однако, на некоторых подклассах тестов в ходе численных экспериментов показывает приемлемую для приложений точность [4]. В [5] для задач LVS и MNLVS был предложен алгоритм, позволяющий получить оптимальное решение за время 0(q2N2q). Из этого результата следует факт полиномиальной разрешимости задач для случая фиксированной размерности пространства.
Далее, в [1] предложен алгоритм решения задачи LVS с относительной погрешностью є = (q — 1)/(8/ ), где / — целочисленный параметр алгоритма, имеющий временную сложность 0(q N(21 + l)q). Фактически, предложенный алгоритм реализует полностью полиномиальную приближённую схему (FPTAS) для случая фиксированной размерности пространства. Кроме того, для случая целочисленных входных данных в [1] и [3] построены точные алгоритмы с трудоёмкостью 0(Nqq+l(MB)q l) и 0(qMN(2MB)q 1), соответственно, где В — максимальное абсолютное значение компонент входных векторов. Алгоритмы являются псевдо-польномиальными при фиксированной размерности пространства и обладают лучшей по сравнению с точным алгоритмом трудоёмкостью, если MB N2.
Из формул, связывающих целевые функции задач LVS и 1-MSSC-F, а также MNLVS и 1-MSSC-NF, следует возможность применения точных и асимптотически точных алгоритмов, предложенных для задач LVS и MNLVS, для получения аналогичных решений задач 1-MSSC-F и 1-MSSC-NF соответственно.
В работах [7] и [30] для задач 1-MSSC-F и 1-MSSC-NF, соответственно, предложены 2-приближённые алгоритмы, полиномиальные относительно N и q. Временная сложность этих алгоритмов равна О(qN2).
В [8] для задачи 1-MSSC-F предложена полиномиальная приближённая схема (PTAS), позволяющая решать задачу с произвольной относительной погрешностью є 0 за время 0(qN2 +l(9/e):i ).
В [31] для этой же задачи обоснован приближённый рандомизированный алгоритм и установлены условия его асимптотической точности. Предложенный алгоритм позволяет получить (1 + o-\/log N)-приближённое решение задачи с вероятностью 1 — y/\ogN — N-13 8, где (З Є (0,1) — константа такая, что М (3N. Трудоёмкость алгоритма равна G(qN2). Одна из множества содержательных проблем второй группы индуцирует следующую экстремальную задачу.
ЗАДАЧА FDVS-(M9)SD (Family of Disjoint Vector Subsets, Euclidean case for Squared Distances). ДАНО: множество У и натуральные Мі,..., Mj. НАЙТИ: непересекающиеся подмножества С\,... ,Cj такие, что
Отличие целевой функции задачи FDVS-(K9)SD от целевых функций задачи J-MSSC-F состоит в отсутствии слагаемого, соответствующего векторам, которые не входят в кластеры с оптимизируемыми центрами. В отличие от задачи MSSC требуется построить не разбиение исходного множества, а найти семейство непересекающихся подмножеств, которое может не покрывать исходное множество. Кроме того, в этой задаче мощности искомых подмножеств фиксированы.
В [10] доказана NP-трудность в сильном смысле частного случая этой задачи, когда J = 1, получившего название VS-2 (Vector Subset). Отсюда следует труднорешаемость общего случая задачи FDVS-@R9)SD. Отсутствие каких-либо эффективных алгоритмов с оценками точности для этой задачи (даже для случая одного подмножества) послужило стимулом к поиску таких алгоритмов, а также к поиску и выделению подслу-чаев, для которых возможно построение точных или приближённых алгоритмов, имеющих полиномиальную или псевдополиномиальную сложность. В настоящей работе исследуется простейший случай этой задачи — поиск одного подмножества векторов. Эта задача возникает в ситуации, когда обрабатываемые данные содержат результаты многократных измерений характеристик одного информационно важного объекта среди набора однократных измерений произвольных объектов.
Алгоритмы решения задач
На шаге 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), то для одного из сомножителей в оценке вычислительной сложности алгоритма имеем
В главе 2 исследованы NP-трудные задачи кластеризации заданного множества векторов евклидова пространства и поиска в этом множестве подмножества векторов фиксированной мощности по критерию минимума суммы квадратов расстояний.
Для решения задач предложен эффективный приближённый алгоритмы с гарантированной оценкой точности 2, показана достижимость полученной оценки.
Для специального подслучая рассматриваемых задач, когда размерность пространства фиксирована, а компоненты входных векторов цело-численны, построен точный псевдополиномиальный алгоритм.
Доказано, что для общего случая задач не существует полностью полиномиальной приближённой схемы (FPTAS), если P NP. Для случая фиксированной размерности пространства такая схема обоснована. Глава З
Задачи поиска подпоследовательности векторов
В этой главе рассматриваются обобщения задач, изученных в главе 2. Они моделируют проблемы помехоустойчивого анализа многомерных последовательностей (временных рядов). Результаты третьей главы опубликованы в работах [16,17,20,22,25,51].
Пусть элементы векторной последовательности ,?! Є ЛГ определяются формулами (2.1) и (2.2). Рассмотрим модель анализа данных в виде следующей экстремальной задачи.
НАЙТИ: набор АЛ = (пі,... ,пм) номеров элементов последовательности, вектор 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.
ЗАДАЧА VSS-3. ДАНО: последовательность уп,п Є ЛҐ векторов из WLq, натуральные числа Tmin,Tmax и М 1. НАЙТИ: подмножество Л4 = {пі,..., пм} Q А/" номеров элементов последовательности такое, Формула (3.1) в этих задачах задаёт ограничения на порядок выбора векторов из последовательности уп,п Є ЛГ. Заметим, что на практике возможна ситуация, в которой значения Тт[п и Ттах неизвестны. В такой ситуации достаточно положить Тт[п = 1,
Специальные случаи задач VSS-2, VSS-3 и MSSC-Case-S, когда min = 1 и Tmax = N, эквивалентны соответствующим задачам из главы 2. Поэтому сформулированные выше задачи поиска подпоследовательности NP-трудны в сильном смысле, и для этих задач не существует схемы FPTAS в общем случае, если P NP.
Как показано в [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, по допустимому решению одной из задач можно построить допустимые решения остальных задач, сохранив оценки точности решений.
2-приближённый полиномиальный алгоритм
Для вычисления оптимального значения целевой функции на третьем шаге потребуется 0{N) операций.
Наконец, из формул (3.19) и (3.20) видно, что на шаге 4 требуется (9(М(Ттах — Тт[п + 1)) операций. Суммируя затраты на все шаги, получаем оценку, приведённую в формулировке теоремы.
Замечание 3.1. В оценку временной сложности алгоритма ЛА ВХОДЯТ числовые значения М и (Ттах — Тт[п + 1). Эти значения ограничены сверху размером N входа задачи. Поэтому в общем случае трудоёмкость алгоритма есть величина 0{N(q + Л 2)).
Алгоритм ЛА находит подпоследовательность тех векторов исходной последовательности уп п Є Л/", которые наиболее близки к заданному вектору в смысле минимума суммы квадратов расстояний, и при этом удовлетворяют ограничениям (3.1) исходной задачи. Поэтому решение, построенное алгоритмом для любого Ь Є Ж4 будет допустимым решением исходной задачи VSS-2.
В качестве примера, демонстрирующего достижимость оценки алгоритма, очевидно, можно использовать пример для задачи VS-2 из теоремы 2.2. Теорема доказана. Псевдополиномиальный алгоритм, гарантирующий оптимальное решение задач Допустим теперь, что компоненты векторов из последовательности Уп,п Є ЛГ имеют целочисленные значения. Следуя логике из главы 2, представим алгоритм решения задачи VSS-2 в виде псевдокода. Алгоритм Лъ Шаг 1. Построим множество В по формулам (2.20). Шаг 2. Для каждого Ь Є , найдём оптимальное решение А4(Ь) вспомогательной задачи 1 и значение Gm[n(b) с помощью алгоритма ЛА Шаг 2. Среди построенных решений выберем решение с наименьшим значением Gm[n(b).
Теорема 3.3. Если все векторы последовательности уп,п Є J\f имеют целочисленные компоненты, то алгоритм AQ находит оптимальное решение задачи VSS-2 за врем„я 0(N(N2 + q)(2MB + l)q).
Доказательство. Пусть АЛ — оптимальное решение задачи VSS-2, а у (АЛ ) = jj Y neM Уп — Центр подмножества {уп,п Є М }.
Из целочисленности компонент векторов входной последовательности и определений (2.19) и (2.20) следует, что вектор у (АЛ ) лежит во множестве В. Поэтому из пошаговой записи
Оценим временную сложность алгоритма. Общая трудоёмкость получается из произведения трудоёмкости алгоритма ЛА решения вспомога 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 для специальных случаев и др.) для решения рассмотренных в работе задач.
Представляет интерес выяснение сложностного статуса рассмотренных задач в случае, когда размерность пространства фиксирована.
