Алгоритмы с оценками для некоторых задач поиска подмножества и подпоследовательности векторов в евклидовом пространстве тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Романченко, Семён Михайлович

• Романченко, Семён Михайлович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Романченко, Семён Михайлович

Оглавление

Введение

1 Квадратичные модели поиска похожих элементов

2 Задачи поиска подмножества векторов

2.1 Постановки задач

2.2 Несуществование схемы РРТАБ для общего случая

2.3 Геометрические основы алгоритмов

2.4 Алгоритмы решения задач

2.4.1 Приближённый полиномиальный алгоритм с гарантированной достижимой оценкой 2 точности

2.4.2 Точный псевдополиномиальный алгоритм

2.4.3 Схема РРТАБ для специального случая

2.5 Заключение к главе

3 Задачи поиска подпоследовательности векторов

3.1 Постановки задач

3.2 Алгоритмы решения задач

3.2.1 Вспомогательная задача и точный полиномиальный алгоритм её решения

3.2.2 2-приближённый полиномиальный алгоритм

3.2.3 Псевдополиномиальный алгоритм, гарантирующий оптимальное решение задач

3.3 Заключение к главе

Заключение

Литература

Введение диссертации (часть автореферата) на тему «Алгоритмы с оценками для некоторых задач поиска подмножества и подпоследовательности векторов в евклидовом пространстве»

Введение

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

Рассматриваемые в работе задачи возникают, в частности, в анализе данных и распознавании образов, в математической статистике, в теории приближения и комбинаторной геометрии. Они моделируют простейшую в содержательном плане и в то же время актуальную для многих естественно-научных и технических приложений проблему поиска в конечном множестве (или в конечной последовательности) объектов заданного числа похожих элементов. Формализация этой проблемы, например, в виде задачи аппроксимации по критерию минимума суммы квадратов уклонений индуцирует несколько полиномиально эквивалентных экстремальных задач, которые, как установлено совсем недавно, ЫР-трудны в сильном смысле. Мотивацией исследования послужило отсутствие каких-

либо полиномиальных алгоритмов с доказуемыми оценками точности для решения этих задач.

В работе исследовались две совокупности труднорешаемых задач. Первая включает задачи поиска подмножества, вторая — задачи поиска подпоследовательности.

Полиномиально эквивалентные задачи из первой совокупности имеют следующие формулировки:

1. В конечном множестве векторов евклидова пространства найти иод-множество заданной мощности, минимизирующее сумму квадратов расстояний от элементов подмножества до его центра, который определяется как среднее значение по всем элементам подмножества.

2. В конечном множестве векторов евклидова пространства найти такое подмножество заданной мощности, что сумма квадратов всевозможных попарных расстояний между его элементами минимальна.

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

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

константы соответствуют минимальному и максимальному допустимому интервалу между двумя последовательными повторами похожих элементов.

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

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

Теоретическая и практическая значимость. Работа носит теоретический характер. Её результаты могут быть использованы, в частности, при решении геометрических задач дискретной оптимизации, в математической теории анализа данных и распознавания образов, а также в теории приближения. Подходы к построению алгоритмов и технические приёмы, предложенные в работе, могут использоваться для исследования новых задач в указанных областях. Разработанные алгоритмы могут быть использованы в приложениях, связанных с анализом данных и распознаванием образов.

На защиту выносится совокупность эффективных алгоритмов с гарантированными оценками точности для решения задач дискретной

оптимизации, которые моделируют одну из фундаментальных естественно-научных проблем поиска подмножества похожих элементов в конечных множествах и последовательностях.

Апробация работы. Результаты диссертации докладывались на следующих российских и международных конференциях: IV и V Всероссийские конференции «Проблемы оптимизации и экономические приложения» (г. Омск, 2009, 2012), 15-я и 16-я Всероссийские конференции «Математические методы распознавания образов» (г. Петрозаводск, 2011, г. Казань 2013), XIV Всероссийская конференция «Математическое программирование и приложения» (г. Екатеринбург, 2011), XV и XVI Байкальские международные школы-семинары «Методы оптимизации и их приложения» (г. Иркутск, 2011, 2014), 9-я международная конференция «Интеллектуализация обработки информации» (г. Будва, Черногория, 2012), международная конференция «Дискретная оптимизация и исследование операций» (г. Новосибирск, 2013), IV-я международная конференция «Optimization and applications» (Petrovac, Montenegro, 2013).

Публикации. По результатам исследований опубликовано 16 работ. В их числе 5 статей в журналах, входящих в список ВАК РФ (из них 4 — в переводных журналах, входящих в международные системы цитирования Web of Science и Scopus); 4 статьи опубликовано в рецензируемых трудах российских и международных конференций и 7 — в виде тезисов докладов.

Структура и объем диссертации. Диссертация состоит из введения, 3 глав, заключение и списка цитируемой литературы, содержащей 62 источника. Работа изложена на 81 странице, содержит 5 рисунков.

Во введении обоснована актуальность темы диссертационной работы, приведено краткое изложение содержания работы, сформулированы основные выносимые на защиту результаты.

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

Общей чертой анализируемых моделей является подход, основанный на аппроксимации данных по критерию минимума суммы квадратов уклонений. Одной из наиболее известных (более полувека) [46] экстремальных задач, возникающих в рамках этого подхода является задача MSSC (Minimum-Sum-of-Squares Clustering). В этой задаче требуется разбить заданное множество векторов евклидова пространства на семейство непустых подмножеств (кластеров) так, чтобы минимизировать сумму по всем подмножествам суммы квадратов расстояний от элементов подмножества до его геометрического центра. Под геометрическим центром множества понимается среднее арифметическое векторов, входящих в это множество. Искомые кластеры трактуются как подмножества, элементы которых соответствуют похожим (по указанному критерию) объектам.

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

чи МБЭС был установлен лишь несколько лет назад [33,36]. Этот факт стимулировал исследования близких в постановочном плане задач. К их числу относятся задачи, рассмотренные в диссертационной работе. Эти задачи моделируют существенно более простые в содержательном плане проблемы поиска всего одного подмножества или одной подпоследовательности похожих объектов. Статус вычислительной сложности задач, индуцированных этими проблемами, был установлен совсем недавно: эти задачи ИР-трудны в сильном смысле [10,11]. В результате анализа существующих работ установлено, что какие-либо полиномиальные алгоритмы с оценками точности для решения этих задач до настоящего времени отсутствовали. Этот факт определил направление исследований и специфику полученных в работе результатов.

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

Для общего случая рассматриваемых задач построен эффективный приближённый алгоритм с достижимой оценкой 2 его точности. Для специального случая задач, когда размерность пространства фиксирована, а компоненты входных векторов имеют целочисленные значения, обоснован точный псевдополиномиальный алгоритм. Доказано, что если Р^ИР, то для общего случая рассматриваемых задач не существует схемы полностью полиномиальной приближённой схемы (РРТАБ). Для случая фиксированной размерности пространства такая схема обоснована.

Задачи третьей главы постановочном плане близки к задачам, рас-

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

Для этих задач обоснован эффективный 2-приближённый алгоритм. Показано, что для общего случая задач поиска подпоследовательности, как и для общего случая задач поиска подмножества, не существует схемы РРТАБ, если Ру^Р. Построен точный псевдополиномиальный алгоритм для случая, когда входные данные целочисленны, а размерность пространства фиксирована.

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

Глава 1

Квадратичные модели поиска похожих элементов

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

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

Содержательные проблемы анализа данных и распознавания образов, как правило, формулируются следующим образом: по результатам измерений характеристик некоторых наблюдаемых объектов требуется принять решение о взаимосвязи объектов между собой, а также определить (предсказать) отношение с новыми объектами. Эти задачи делят-

ся на два класса: классификации (supervised learning) и кластеризации (unsupervised learning). В задачах первого класса предполагается наличие некоторых обучающих данных («меток» на некоторой части входных объектов, определяющих структуру данных), в то время как во втором классе таких данных нет.

Целью задач кластеризации является выделение естественных групп (классов) в заданном множестве входных объектов. Под естественностью группы объектов обычно понимают похожесть объектов из одной группы и различие из разных. Отношения похожести и различия объектов основываются на понятии «меры близости» наборов характеристик объектов. Эти отношения между объектами обычно удовлетворяют определённому набору свойств: рефлексивности, неотрицательности, симметричности [47]. Причём неравенство треугольника, как свойство отношения между объектами, может и не выполняться. Формализация «меры близости» между объектами, адекватно отражающей проблему, само по себе нетривиальная задача, требующая знаний экспертов-прикладников. Без этих знаний на одних и тех же входных данных можно получить совершенно различные решения задачи кластеризации.

Среди известных критериев кластеризации можно отметить, например, критерии максимизации отдалённости объектов разных кластеров (например, максимизация разреза) и критерии минимизации близости объектов одного кластера (например, минимизация среднеквадратичного уклонения, радиуса, диаметра, клики и др.). Кроме того, для кластеризации применяются классические статистические критерии (например, максимум правдоподобия, максимум апостериорной вероятности, мини-

мум вероятности ошибки).

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

Среди постановок, базирующихся на минимизации целевой функции, вероятно, самой известной является [46, 54, 59] задача MSSC (Minimum Sum-of-Squres Clustering) — кластеризация (разбиение) векторов евклидова пространства по критерию минимума суммы квадратов расстояний. Задача имеет следующую формулировку

Задача MSSC. Дано: множество У = ... ,уп} векторов из lZq, натуральное число J > 1. НАЙТИ: разбиение множества У на непустые

подмножества (кластеры) С\,... ,Cj такое, что

j

3=1

где y(Cj) = щ Y^yeCj yd = 1, — Центр j-го кластера.

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

указанному критерию) объектам.

Задача МББС моделирует [44,46,55] содержательную проблему, в которой требуется разбить таблицу с результатами многократных измерений набора характеристик для нескольких объектов на непустые подмножества, содержащие результаты измерений каждого из объектов, и оценить характеристики этих объектов в условиях, когда соответствие между объектом и результатом измерений отсутствует, а каждому результату измерения сопутствует измерительная ошибка. В качестве примера на рисунке 1.1 изображены результаты измерений двумерного набора характеристик пяти объектов.

*епе« 1еп01Ь 1000 пишЬ« о( гере»и 100 ♦ поев 1вуе4<5 • * *• • *.. • •„ • • V • • * * * ... * ♦ ♦ ♦ ч . *• ♦ . ....... » •''> О о »♦ о 1°° ° . • к »® %.»

„ 7 • °«? ♦ ° ° ° йО< ... • .. • ». - 4 / ♦ • ° в °° д. •лГу» / • . * \„ 8 ° • 1 ° °8 8 * „ 8 % ° ° • ° ^ 1 » ° « а о 0° О о

Рис. 1.1.

В сотнях опубликованных работ были обоснованы разнообразные алгоритмы решения задачи МББС и её специальных случаев, предложена

масса полиномиальных эвристических алгоритмов (без каких-либо теоретических гарантий по точности), ориентированных на решение индивидуальных (прикладных) задач.

Самым популярным эвристическим алгоритмом для решения задачи МББС является алгоритм /г-теапэ. Первые формулировки появились независимо в [40,54,55,61]. Хотя алгоритм и был предложен более полувека назад, он всё ещё остаётся наиболее распространённым алгоритмом, используемым при решении прикладных задач. Простота реализации и во многих случаях приемлемые практические результаты обеспечили ему такую популярность.

Идея алгоритма основана на простом замечании, что для заданных центров кластеров каждый вектор исходного множества принадлежит тому кластеру, расстояние до центра которого минимально [54]. Начав с некоторого разбиения, алгоритм итеративно производит перераспределение векторов по кластерам, выбирая для каждого вектора кластер с ближайшим геометрическим центром. Таким образом, /с-теапя является по своей сути жадным алгоритмом, а получаемое с его помощью решение — лишь локальный оптимум. Однако в некоторых ситуациях даже такое решение обеспечивает хороший с точки зрения приложения результат. Так в [57] показано, что с большой вероятностью А;-теап8 находит глобальный оптимум, если кластеры «хорошо разделены». В то же время, полученное алгоритмом решение может оказаться сколь угодно хуже оптимального [48].

На основе алгоритма /г-теапэ разработано целое множество различных модификаций. Некоторые основаны на использовании различных эвристик, включающих ограничение на минимальный размер кластеров, на

число процедур объединения и разбиения кластеров. Среди таких алгоритмов в качестве наиболее популярных можно выделить эвристические алгоритмы ISODATA [34] и FORGY [40]. В этих алгоритмах каждый элемент исходного множества приписывается к единственному кластеру (так называемое, строгое приписывание).

В отличие от упомянутых, эвристический алгоритм Fuzzy c-means, предложенный в [38], а затем улучшенный в [35], позволяет каждому элементу принадлежать множеству кластеров. Предварительная обработка исходных данных, суть которой состоит в замене групп элементов их геометрическими центрами, в некоторых ситуациях позволяет [39] ускорить алгоритмы к-means и Fuzzy c-means.

Идея итеративного локально оптимального перемещения текущего центра одного из кластеров в один из элементов исходного множества лежит в основе алгоритма J-means и его модификации VNS J-means (комбинации алгоритма J-means и эвристики Variable Neighborhood Search) [42].

Разработанный для выделения кластеров произвольной формы, алгоритм Kernel fc-means основан на предварительной эвристической настройке функции похожести [60].

Значительно меньше работ посвящено алгоритмам с гарантированными оценками точности. В работе [56] был предложен (1 + е)-приближённый алгоритм с трудоёмкостью 0(N logJ Ne~2qj2). В основе алгоритма лежит идея аппроксимации центров кластеров точками из конечного множества специального вида (сетки). На основе этой идеи в [48] предложен алгоритм, который находит (9 + е)-приближённое решение задачи за время <D(N [log N + £-q log(l/e) + N J3 log N]). В этой же работе

показано, что любой подход, основанный на фиксированном числе замен центров кластеров на элементы из специального множества кандидатов, обеспечит нахождение приближённого решения с оценкой точности не лучше (9 — е). Кроме того, в [43] был предложен (1 + £)-приближённый алгоритм с трудоёмкостью 0{N + JJ+2£"(2<7+1)jr(logJ+1 N) logJ

В работе [45] обоснован точный алгоритм, имеющий трудоёмкость 0(NqJ+1). Идея доказательства основана на оценке числа возможных диаграмм Вороного, получаемых по всевозможным J-элементным подмножествам исходного множества, и их эффективному перебору на основе kd-деревьев. Там же обоснован рандомизированный алгоритм 2-кластеризации, позволяющий получить (1 + £)-приближённое решение задачи за время 0(N(l/e)q).

Ещё один рандомизированный алгоритм, основанный на приближении центров кластеров центрами подмножеств случайно выбранных векторов, предложен в [53]. Алгоритм гарантирует нахождение (1 + s)-приближённого решения задачи за время

Несмотря на обилие предложенных алгоритмов, факт труднорешае-мости задачи MSSC был установлен лишь несколько лет назад [33,36]. Этот факт стимулировал исследования близких в постановочном плане задач. К их числу относятся задачи, рассмотренные в диссертационной работе.

Как описано выше, в содержательной проблеме, которой индуцируется задача MSSC, требуется найти разбиение таблицы измерений для нескольких объектов. При этом полагается, что все измерения имеют информационную ценность, т.е. что в таблице не содержится посторонних данных. Однако на практике нередки ситуации [44,46], когда табличные

данные содержат «мусор» в виде случайных измерений, или же измерений объектов, не имеющих информационной ценности. В этом случае экстремальные задачи, моделирующие такие проблемы, можно разделить на две группы.

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

5еие51епд1Ь 1 ООО

51ге100 1Ш уес!о( |47.-71] Ттт/тах 10/60 Ь|М) [45 8.-67 2] 0(М) 78579.00

О

о

о

о

о

Рис. 1.2.

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

Одна из множества содержательных проблем первой группы моделируются [4,13] задачами поиска во множестве У = ... , пдг} векторов

Рис. 1.3.

из Жд такого семейства непересекающихся подмножеств С\,... , С/, что

EEiif-^)ii2+ Е ihi2^™».

где С — С\ u ... u Cj. Индуцированные этой моделью задачи получили названия J-MSSC-F и J-MSSC-NF, где символы F и NF обозначают наличие (Fixed) или отсутствие (NotFixed) ограничений на мощности искомых кластеров. Символы MSSC подчеркивают сходство с классической задачей MSSC. Символ J обозначает число кластеров с оптимизируемым центром.

Так как для любого непустого подмножества С конечного множества векторов из Ж4 справедливо равенство

Е 1Ы12 = Еы2-^нЕг/112.

уеС у&у\с уеУ 1 1 уеС

частному случаю задачи J-MSSC-F — задаче 1-MSSC-F — полиномиально эквивалентна задача отыскания во множестве векторов подмножества фиксированной мощности с максимальной длиной суммы векторов этого подмножества:

задача LVS (subset with the Longest Vector Sum). дано: множество У и натуральное М. найти: подмножество С С У мощности М такое, что

|| Y^VII max .

yec

Задача 1-MSSC-NF, в свою очередь, полиномиально эквивалентна задаче, в которой требуется найти подмножество векторов, которое достав-

ляст максимум нормированному на мощность значению квадрата длины суммы векторов из искомого подмножества:

ЗАДАЧА MNLVS (Maximum Normalized Length of Vector Sum). ДАНО: множество У. НАЙТИ: подмножество С С У такое, что

В [1,4,12,13] установлена NP-тpyднocть в сильном смысле обеих задач максимизации. Из этих результатов, как обобщение, следует NP-трудность в сильном смысле задач У-МЭЗС-Р и «/-МЯЗС-КР. Как показано в [13], параметрические варианты этих задач, когда параметр J не является частью входа (фиксирован), также являются NP-тpyдными в сильном смысле задачами.

В алгоритмическом плане задачи слабо изучены. Лишь для простейшего случая 3 — 1 построены алгоритмы с гарантированными оценками качества. В [4] для задачи построен эффективный приближённый алгоритм с трудоёмкостью Алгоритм не имеет гарантированной оценки точности, однако, на некоторых подклассах тестов в ходе численных экспериментов показывает приемлемую для приложений точность [4]. В [5] для задач ГУБ и MNLVS был предложен алгоритм, позволяющий получить оптимальное решение за время 0{ц21У2<?). Из этого результата следует факт полиномиальной разрешимости задач для случая фиксированной размерности пространства.

Далее, в [1] предложен алгоритм решения задачи с относительной погрешностью е = (у — 1)/(8/2), где I — целочисленный параметр алгоритма, имеющии временную сложность 0(д2И(21 + I)9). Фактически,

предложенный алгоритм реализует полностью полиномиальную приближённую схему (РРТАБ) для случая фиксированной размерности пространства. Кроме того, для случая целочисленных входных данных в [1] и [3] построены точные алгоритмы с трудоёмкостью 0{Идч+1(МВ)ч~1) и 0{дМ N {2М В)ч~1), соответственно, где В — максимальное абсолютное значение компонент входных векторов. Алгоритмы являются псевдо-польномиальными при фиксированной размерности пространства и обладают лучшей по сравнению с точным алгоритмом трудоёмкостью, если МВ < Ы2.

Из формул, связывающих целевые функции задач ЬУБ и 1-М88С-Р, а также М]ЧЬУ8 и 1-М88С-КР, следует возможность применения точных и асимптотически точных алгоритмов, предложенных для задач ЬУ8 и МГ^ЬУЗ, для получения аналогичных решений задач 1-М88С-Р и 1-М88С-КЕ соответственно.

В работах [7] и [30] для задач 1-М88С-Е и 1-М88С-№, соответственно, предложены 2-приближённые алгоритмы, полиномиальные относительно N и д. Временная сложность этих алгоритмов равна 0(д1V2).

В [8] для задачи 1-М88С-Г предложена полиномиальная приближённая схема (РТАБ), позволяющая решать задачу с произвольной относительной погрешностью е > 0 за время 0(^Аг2/£+1(9/£:)3//е).

Список литературы диссертационного исследования кандидат наук Романченко, Семён Михайлович, 2014 год

Литература

[1] Бабурин А. Е., Гимади Э.Х., Глебов Н. И., ПяткинА. В. Задача отыскания подмножества векторов с максимальным суммарным весом // Дискретный анализ и исследование операций.— 2007.— Т. 14, №1. - С. 32-42.

[2] ГалашовА. Е., Кельманов А. В. 2-приближённый алгоритм для одной задачи поиска семейства непересекающихся подмножеств векторов // Автоматика и телемеханика.— 2014.— №4.— С. 5-19.

[3] Гимади Э. X., Глазков Ю. В., Рыков И. А. Задача выбора подмножества векторов с целочисленными координатами в евклидовом пространстве с максимальной нормой суммы // Дискретный анализ и исследование операций. — 2008. — Т. 15, №4. — С. 31-43.

[4] Гимади ЭХ., Кельманов А В., Кельманова М А., Хамидуллин С А. Апостериорное обнаружение в числовой последовательности квазипериодического фрагмента при заданном числе повторов // Сибирский журнал индустриальной математики. — 2006. — Т. 9. №1(25). - С. 55-74.

[5] ГимадиЭ.Х., ПяткинА. В., Рыков И. А. О полиномиальной разрешимости некоторых задач выбора подмножеств векторов в евклидовом пространстве фиксированной размерности // Дискретный анализ и исследование операций. — 2008. — Т. 15, Nfi6. — С. 11-19.

[6] Гимади Э. X., Кельманов А. В., Пяткин А. В., Хачай М. Ю. Эффективные алгоритмы с оценками точности для некоторых задач поиска нескольких клик в полном неориентированном взвешенном графе // Труды Института математики и механики УрО РАН.— 2014.-— Т. 20, № 2,— С. 99-112.

[7] Долгушев А. В., Кельманов А. В. Приближенный алгоритм решения одной задачи кластерного анализа // Дискретный анализ и исследование операций. - 2011. - Т.18, №2. - С. 29-40.

[8] Долгушев А. В., Кельманов А. В., ШенмайерВ. В. Приближенная полиномиальная схема для одной задачи кластерного анализа // Интеллектуализация обработки информации: 9-я международная конференция. Республика Черногория, г. Будва, 16-22 сентября 2012 г.: Сборник докладов. — М.: Торус Пресс, 2012. — С. 242-244.

[9] И.И. Еремин, Э.Х. Гимади, A.B. Кельманов, A.B. Пяткин, М.Ю. Хачай. 2-приближённый алгоритм поиска клики с минимальным весом вершин и ребер // Труды Института математики и механики УрО РАН. - 2013. - Т.19, №2,- С. 134-143.

[10] Кельманов А. В., ПяткинА. В. NP-полнота некоторых задач выбора подмножества векторов // Дискретный анализ и исследование операций. - 2010. - Т.17, №5. - С. 37-45.

fil] Кельманов A. В., Пяткин А. В. О сложности некоторых задач выбора подпоследовательности векторов // Журнал вычислительной математики и математической физики. — 2012. — Т. 52, JYe 12.— С. 22842291.

[12] Кельманов А. В., Пяткин А. В. Об одном варианте задачи выбора подмножества векторов // Дискретный анализ и исследование операций. - 2008. - Т. 15, №5,- С. 20-34.

[13] Кельманов А. В., Пяткин А. В. О сложности некоторых задач поиска подмножеств векторов и кластерного анализа // Журнал вычислительной математики и математической физики. — 2009. — Т. 49, №11. - С. 2059-2067.

[14] Кельманов A.B., Романченко С.М. Приближённый алгоритм для решения одной задачи поиска подмнодества векторов // Дискретный анализ и исследование операций.— 2011.— Т.18, №4.— С. 61-69.

[15] А.В.Кельманов, С.М.Романченко. Псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подмножества векторов и кластерного анализа // Автоматика и телемеханика.— 2012.- №2 — С 156-162.

[16] Кельманов A.B., Романченко С.М., Хамидуллин С.А. Приближённые алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов // Дискретный анализ и исследование операций,- 2012,- Т.19, №3,- С. 27 38.

[17] Кельманов А. В., Романченко С. М., Хамидуллин С. А. Точные псевдополиномиальные алгоритмы для некоторых труднорешаемых за-

дач поиска подпоследовательности векторов // Журнал вычислительной математики и математической физики.— 2013.— Т. 53, № 1 — С. 143-153.

[18] Кельманов А. В., Романченко С. М. РРТАБ для одной задачи поиска подмножества векторов // Дискретный анализ и исследование операций,- 2014,- Т.21, №3,- С. 41-52.

[19] Кельманов А. В., Романченко С. М. Алгоритмы с оценками для некоторых задач поиска подмножества векторов и кластерного анализа // Математические методы распознавания образов: 15-я Всероссийская конференция (ММРО-15), г. Петрозаводск, 11-17 сентября 2011 г.: Сборник докладов. - М.: МАКС Пресс, 2011. - С. 273-276.

[20] Кельманов А. В., Романченко С. М., Хамидуллин С. А. 2-приближенный алгоритм для одной задачи поиска в векторной последовательности совокупности «похожих» элементов // Математические методы распознавания образов: 15-я Всероссийская конференция (ММРО-15), г. Петрозаводск, 11-17 сентября 2011 г.: Сборник докладов. - М.: МАКС Пресс, 2011. - С. 281-283.

[21] А. В. Кельманов, С. М. Романченко. Псевдополиномиальные алгоритмы для некоторых задач поиска подмножества векторов и кластерного анализа // Труды XV Байкальской международной школы-семинара «Методы оптимизации и их приложения», Иркутск, 23-29 июня 2011 г. Т.4: Дискретная оптимизация, Иркутск: РИО ИДСТУ СО РАН, 2011. - С. 144-149.

[22] Кельманов А. В., Романченко С. М., Хамидуллин С. М. Точные псев-

дополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов // Интеллектуализация обработки информации: 9-я международная конференция. Республика Черногория, г. Будва, 16-22 сентября 2012 г.: Сборник докладов. - М.: Торус Пресс, 2012. - С. 275-278.

[23] Кельманов А. В., Романченко С. М. Об одной задаче поиска наборов векторов // Материалы IV Всероссийской конференции «Проблемы оптимизации и экономические приложения». Омск, 29 июня -4 июля 2009. Материалы конференции. — Омск: Полиграфический центр КАН - С. 134.

[24] Кельманов А. В., Романченко С. М. Приближённый алгоритм для решения одной задачи поиска подмножества векторов // Тез. докл. XIV -й Всероссийской конференции «Математическое программирование и приложения». г.Екатеринбург, 28 февраля - 4 марта 2011 г. Екатеринбург: УрО РАН.— С. 100.

[25] Кельманов А. В., Романченко С. М., Хамидуллин С. А. Точный псевдополиномиальный алгоритм для одной МР-трудной задачи поиска подпоследовательности векторов // Материалы V Всероссийской конференции «Проблемы оптимизации и экономические приложения». Омск, 2-6 июля 2012. Материалы конференции. — Омск: Изд-во Ом. гос. ун-та.— С. 134.

[26] Кельманов А. В., Романченко С. М. РРТАБ для одной труднореша-емой задачи поиска подмножества векторов // Математические методы распознавания образов: 16-я Всероссийская конференция

(ММРО-16), г. Казань, 6-12 сентября 2013 г.: Тезисы докладов. — М.: Торус Пресс, 2011. - С. 33.

[27] Alexander Kel'manov, Semyon Romanchenko. A fully polynomial time approximation scheme for a problem of choosing a vector subset // Proceedings of IV International Conference «Optimization and applications» (OPTIMA-2013), Petrovac, Montenegro, September 22-28, 2013,- P. 89.

[28] А. В. Кельманов, С. M. Романчепко. FPTAS для одной NP-трудной задачи поиска подмножества векторов // Материалы международной конференции «Дискретная оптимизация и исследование операций», DOOR-2013, Новосибирск, Академгородок, 24-28 июня 2013. — Новосибирск: Изд-во Института математики СО РАН, 2013.-- С. 158.

[29] Кельманов А. В., Хамидуллин С. А. Апостериорное обнаружение заданного числа одинаковых подпоследовательностей в квазипериодической последовательности // Журнал вычислительной математики и математической физики. — 2001. — Т. 41, №5,— С. 807-820.

[30] Кельманов А. В., Хандеев В. И. Полиномиальный алгоритм с оценкой точности 2 для решения одной задачи кластерного анализа // Дискретный анализ и исследование операций. — 2013. — Т. 20, №4,— С. 36-45.

[31] Кельманов А. В., Хандеев В. И. Рандомизированный алгоритм для одной задачи кластерного анализа // Материалы международной конференции «Дискретная оптимизация и исследование операций»,

DOOR-2013, Новосибирск, Академгородок, 24-28 июня 2013. — Новосибирск: Изд-во Института математики СО РАН, 2013. — С. 160.

[32] С. М. Романченко. Алгоритмы с оценками для некоторых квадратичных задач поиска подмножества и подпоследовательности векторов евклидова пространства // Материалы XVI Байкальской международной школы-семинара «Методы оптимизации и их приложения», Иркутск, 30 июня—6 июля 2014 г. Иркутск: ИСЭМ СО РАН,- С. 86.

[33] AloiseD., DeshpandeA., HansenP., PopatP. NP-hardness of Euclidean sum-of-squares clustering // Machine Learning.— 2009.— Vol.75, №2.— P. 245-248.

[34] Ball G., Hall D. ISODATA a novel method of data analysis and patern classification // Technical report NTIS AD 699616. Standford Research Institute, Standford, CA.1965.

[35] Bezdek J.C., Pattern Recognition with Fuzzy Objective Function Algorithms // Plenum: New York, 1981.

[36] P. Bonsma, H. Broersma, V. Patel, A. Pyatkin. The complexity of finding uniform sparsest cuts in various graph classes // Journal of Discrete Algorithms.- 2012,- Vol. 14,- P. 136-149.

[37] Brucker P. On the Complexity of Clustering Problems // Optimization and Operations Research, Lecture Notes in Economics and Mathematical Systems.- 1978.- Vol. 157.- P.45-54.

[38] Dunn, J.C. A fuzzy relative of the ISODATA process and its use in

detection compact wel-separated clusters //J. Cybernet. — 1973. — Vol. 3,- P. 32-57.

[39] Eschrich S., Ke Jingwei, Hall, L.O., Goldgof D.B., Fast accurate fuzzy clustering through data reduction // IEEE Trans. Fuzzy System. — 2003,- Vol. 11 (2).- P. 262-270.

[40] Forgy, E. Cluster Analysis of Multivariate Data: Efficienty vs. Intcrpretability of Classification // Biometrics.— 1965.— Vol.21.— P. 768.

[41] Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. — San Francisco: Freeman, 1979. — P. 314.

[42] Hansen P., Mladenovic N., J-means: A new local search heuristic for minimum sum of squares clustering // Pattern Recognition. — 2001.— Vol. 34,- P. 405-413.

[43] Har-Peled S., Mazumdar S. Corcsets for k-means and k-median clustering and their applications // Proceedings of the 36th Annual Symposium on Theory of Computing, 2004,- P. 291-300.

[44] HastieT., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference and Prediction // — New York: Spinger-Verlag. 2009.

[45] Inaba M., Katoh N., Imai H. Applications of Weighted Voronoi Diagrams and Randomization to Variance-Based Clustering / Proc. Annual Symp. on Comput. Geometry — 1994.- P. 332-339.

[46] Jain A.K. Data clustering: 50 years beyond K-means. // Pattern Recognition Lett.— 2010,- Vol. 31- P. 651-666.

[47] Jain A.K. and DubesR.C. Algorithms for clustering data // New Jersey, Englewood Cliffs: Prentice HallPattern, 1988.

[48] Kanungo T., Mount D.M., Netanyahu N. S.,Piatko C.D., Silverman R., Wu A. Y. An Efficient k-Means Clustering Algorithm: Analysis and Implementation // IEEE Transactions on Pattern Analysis and Machine Intelligence.- 2002. - Vol 24, part 7,- P. 881-892.

[49] A.V.Kel'manov, S.M.Romanchenko. An Approximation Algorithm for Solving a Problem of Search for a Vector Subset // Journal of Applied and Industrial Mathematics.- 2012,- Vol. 6, No.l.- P. 90-96.

[50] A.V.Kel'manov, S.M.Romanchenko. Pseudopolynomial Algorithms for Certain Computationally Hard Vector Subset and Cluser Analysis Problems // Automation and Remote Control.— 2012.— Vol. 73, No 2.- P.349-354.

[51] A.V.Kel'manov, S.M.Romanchenko, S.A.Khamidullin. Approximation Algorithms for Some Intractable Problems of Choosing a Vector Subsequence // Journal of Applied and Industrial Mathematics.— 2012,- Vol.6, No.4,— P.443-451.

[52] A.V. Kel'manov, S.M. Romanchenko. FPTAS for a Vector Subset Search Problem // Journal of Applied and Industrial Mathematics.— 2014.— Vol. 8, №3. P. 329-336.

[53] Kumar A., Sabharwal Y., Sen S. A simple linear time (1 + e)-

approximation algorithm for K-means clustering in any dimensions // Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004,- P. 454-462.

[54] Lloyd, S.P. Least squares quantization in PCM. // IEEE Trans. Inform. Theory.- 1982 - Vol. 28,- P. 129-137.

[55] MacQueen, J.B. Some methods for classification and analysis of miltivariate observations // Proc. 5-th Berkley Symp. of Mathematics, Statistics and Probability. - 1967. - P. 281-297.

[56] Matousek J. On approximate geometric k-clustering // Discrete and Computational Geometry.- 2000,- Vol. 24,- P. 61-84.

[57] Meila, Marina. The uniqueness of a good optimum for k-means. // Proc. 23rd Internat. Conf. Machine Learning, 2006.- P. 625-632.

[58] Papadimitriou C. H. Computational Complexity. — New-York: Addison-Wesley, 1994,- P. 523.

[59] RaoM. Cluster Analysis and Mathematical Programming. // Journal of the American Statistical Association.— 1971,— Vol. 66.— P. 622-626.

[60] Scholkoph B., Smola A., Muller K.R., Nonlinear component analysis as a kernel eigenvalue problem

Neural Comput.- 1998,- Vol. 10(5).- P. 1299-1319.

[61] Steinhaus, H. Sur la division des corp materiels en parties. // Bull. Acad. Polon. Sci.- 1956. - Vol. 4.- P. 801-804.

[62J WirthH. Algorithms + Data Structures = Programs // New Jersey: Prentice Hall, 1976,- P.366.