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

• Панасенко Анна Владимировна
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Панасенко Анна Владимировна

2.1 Вспомогательная задача

2.2 Точный псевдополиномиальный алгоритм для специального случая задачи

2.3 Приближенный алгоритм

3 Близкие в постановочном плане задачи

3.1 Задача взвешенной кластеризации конечного множества точек евклидова пространства с произвольными весами

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

3.1.2 Аппроксимационная схема

3.1.3 Ускоренная аппроксимационная схема

3.2 Задача о нахождении подмножества наибольшей мощности

3.2.1 Формулировка задачи и алгоритмическая сложность

3.2.2 Точный псевдополиномиальный алгоритм для специального случая задачи

Заключение

Список обозначений и сокращений

Литература

Введение

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

Общая характеристика работы

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

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

Анализ данных и распознавание образов (АД и РО) — это область мате-

1 Работа поддержана грантами РФФИ 16-07-00168, 16-31-00186 мол-а, 18-31-00398 мол-а, 19-07-00397, 1931-90031 Аспиранты, РНФ 16-11-10041.

матики и информатики, занимающаяся построением и исследованием наиболее общих математических методов и вычислительных алгоритмов извлечения знаний из экспериментальных (в широком смысле слова) данных; процесс исследования, фильтрации, преобразования и моделирования данных с целью извлечения полезной информации и принятия решений. Математические задачи анализа данных и распознавания образов индуцируются прикладными проблемами из широкого спектра естественно-научных, гуманитарных и технических сфер. Классификация данных предшествовала кластеризации данных. Кластеризация (кластерный анализ) — это совокупность методов, выполняющих выделение групп объектов, называемых кластерами, таким образом, чтобы объекты одного кластера были похожи, а объекты разных кластеров существенно различались [1]. Понятие «похожести» объектов тесно связано с тем, каким критерием руководствуется исследователь. От выбранного им критерия напрямую зависит результат решения задачи.

Например, представим себе, что нам нужно из набора двуцветных и округлых либо угловатых объектов сформировать две группы. Мы можем делать это, очевидно, по форме или по цвету. А может, мы и вовсе будем ориентироваться на материал. Во всех этих случаях получатся свои разбиения на кластеры. Теперь представим себе, что перед исследователем (или перед практиком) находится просто набор каких-то данных, не поддающийся осмыслению и охвату обычным взглядом (например, из-за объёмов имеющихся данных). Исследователь пока ещё смутно понимает, какой критерий приведёт его именно к тому разбиению, которое он хочет получить. Но в его руках имеются все методы и алгоритмы, разработанные на текущий момент времени. Он может применить их и затем уже по результату понять, какой же из критериев был нужным и привёл к формированию интересующих его совокупностей. Люди, занимающиеся созданием алгоритмов для задач с конкретными критериями, работают,

в частности, для того, чтобы у практиков не иссякали методы, которые они могут свободно взять и применить к поставленной перед ними задаче. То, насколько хороший алгоритм они смогут предложить, зависит от того, к какому классу вычислительной сложности относится решаемая задача. Сложностной статус задачи также напрямую зависит от критерия, которым руководствуется исследователь при разбиении данных на кластеры. Какие-то из задач полиномиально разрешимы. Для каких-то сложностной статус неизвестен. Какие-то из задач заведомо труднорешаемы, что уже было успешно доказано. Этот вариант встречается в реальной практике чаще всего. Решать такие задачи точным образом представляется крайне затруднительной затеей, по крайней мере до тех пор, пока не нашлось конструктивного доказательства равенства классов P и NP. Для задач, характеризующихся большим объёмом данных, особо актуальны алгоритмы, позволяющие находить приемлемое по точности решение за сублинейное или линейное время.

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

Задача Cardinality-weighted variance-based 2-clustering with given center. Дано N-элементное множество У точек из Rd и натуральное число M. Найти разбиение У на два непустых кластера C и У \ C такое, что

|C| ^ ||У - y(C)||2 + |Y\C| ^ |М|2 ^ min ,

yeC уеУ\С

где y(C) = |1 y — центроид множества C, при условии |C| = M.

1 | yeC

Эта задача — задача взвешенной 2-кластеризации, в которой центр одного

из кластеров фиксирован (без ограничения общности — в начале координат), центр другого является оптимизируемой величиной, а в качестве весов выступают мощности соответствующих кластеров. Она является КР-трудной в сильном смысле, что установлено в [2,3] в 2015 году. Для доказательства этого факта авторами было использовано сведение к задаче о максимальном разрезе. Каких-либо алгоритмических результатов для этой задачи к тому моменту предложено не было.

Сформулированная выше задача моделирует следующую прикладную проблему. Пусть у нас есть множество У, состоящее из N результатов измерений ё характеристик какого-то объекта, который может находиться в двух различных состояниях (например, активном и пассивном). Каждое измерение выполнено с некоторой ошибкой, и никто не знает верного соответствия между элементами входного множества и состояниями. Однако дополнительно известно, что в точности М раз объект находился в активном состоянии (или, другими словами, вероятность того, что объект находится в активном состоянии, есть величина N). Требуется найти 2-разбиение входного множества и оценить характеристики объекта (т.е., оценить у (С)).

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

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

ятностным распределением помехи.

Постараемся проследить путь, который привёл к появлению задач, исследованию которых посвящена диссертационная работа. Начнём с задачи, которая, на первый взгляд, не сильно похожа на сформулированную выше ключевую задачу работы. Удобнее всего её изложить в терминах теории графов. Пусть имеется неориентированный взвешенный граф, веса рёбер которого — неотрицательные числа. Требуется разбить множество вершин графа на две части так, чтобы суммарный по обоим кластерам вес суммы внутрикластерных весов ребер был минимален. Эта задача, получившая название Min-sum bi-clustering, впервые была сформулирована в [4] в 1976 году, а в дальнейшем рассматривалась и в [5]. В этих работах была установлена NP-трудность предложенной задачи.

Метрический случай этой задачи имеет название Min-sum all-pairs bi-clustering, а его труднорешаемость была установлена, в частности, в [6,7].

Задача, в которой вершинами являются точки евклидова пространства, а в качестве весов рёбер выступают квадраты расстояния между ними, имеет название Quadratic Euclidean Min-Sum All-Pairs bi-clustering (или 2-clustering).

Задача Quadratic Euclidean Min-Sum All-Pairs 2-clustering. Дано: множество У = {y 1,... ,Vn} точек из Rd. Найти: разбиение множества У на два непустых подмножества C и У \ C таких, что

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

x — z

2

■> mm.

xGC zGC

xey\C z&y\C

2015 году была доказана [2,3] NP-трудность в сильном смысле евклидова случая задачи, который и был сформулирован выше.

Эквивалентной задаче Quadratic Euclidean Min-Sum All-Pairs 2-clustering является другая известная задача — задача Min-Sum 2-clustering, в евклидовом случае которой (с весами — мощностями кластеров, и стоящими внутри сумм квадратами расстояний от точек кластеров до центров соответствующих кластеров) требуется разбить входное множество У на два кластера так, чтобы минимизировать сумму

|C| £ ||y - y(C)||2 + |У \ C| £ ||y - y(Y\C)||2 ,

yeC yey\C

где y (C) = |1 y — центроид множества C.

| | yeC

В силу эквивалентности, к ней применимы результаты, устанавливающие сложностной статус задачи Quadratic Euclidean Min-Sum All-Pairs 2-clustering. Для рассматриваемых задач известен также ряд алгоритмических результатов [4,6-12].

Работа [8] инициировала начало исследований в контексте построения приближённых алгоритмов для задачи Min-sum all-pairs k-clustering, также являющейся близкой к рассматриваемым в работе задачам. В ней был предложен вероятностный алгоритм для случая кластеризации множества точек евклидова пространства с квадратом евклидовых расстояний в качестве весов ребер. Этот алгоритм либо находил решение с точностью (1 + г), либо мог быть превра-щён в алгоритм, позволяющий находить оптимальное разбиение, если изменить назначение не более чем г доли точек входного множества. Время работы предложенного алгоритма линейно в случае, когда размерность d пространства — величина порядка o(log n/ log log n), и есть величина nO(loglogn) иначе.

В [6] авторами была предложена полиномиальная приближенная схема для

решения задачи Metric Max Cut, целевая функция которой является дополнительной к целевой функции задачи Metric min-sum all-pairs 2-clustering (в задаче о максимальном разрезе требуется максимизировать сумму весов ребер между двумя кластерами). Позже в работе [9] этот алгоритм был использован, чтобы построить полиномиальную приближенную схему уже для самой задачи Metric min-sum all-pairs 2-clustering. А в работе [10] другими авторами для решения задачи Metric min-sum all-pairs k-clustering в случае произвольного не фиксированного k был предложен полиномиальный O( 1 log1+e п)-приближенный алгоритм, имеющий трудоемкость nO(1/e).

В работе [7] также исследовалась задача Min-sum all-pairs k-clustering. В контексте неё рассматривался как метрический случай весов рёбер, так и не метрический случай квадратов расстояний между точками евклидова пространства. Авторами был предложен алгоритм, который для произвольного £ > 0 и произвольного фиксированного k находит разбиение входного множества на k кластеров и ошибается не более чем в (1 + е) раз. В метрическом случае предложенный алгоритм является рандомизированным с временной сложностью O(n2k + nk+12O(1/e3fc+1)). В случае квадрата евклидовых расстояний алгоритм является детерминированным с временной сложностью O(k/e4).

Задача Quadratic Euclidean min-sum all-pairs 2-clustering рассматривалась также в [11]. В этой работе применение нашли диаграммы Вороного. Авторы смогли построить алгоритм с трудоемкостью O(nd+1), где d — размерность пространства. В случае задачи k-кластеризации диаграммы Вороного помогли уже другим авторам [12], которым удалось построить алгоритм с трудоемкостью

O(n(d+2)k+1).

Основное отличие рассматриваемых в диссертационном исследовании задач заключается в фиксированности центра одного из кластеров, чего не было в задаче Min-Sum 2-clustering, где оба центра — оптимизируемые величины. Из-

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

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

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

Основные результаты диссертации.

1. Для взвешенной квадратичной задачи двухкластерного разбиения конечного множества точек евклидова пространства при фиксированном центре одного из кластеров и весах, равных мощностям кластеров:

а) построен точный алгоритм для целочисленного варианта задачи, который псевдополиномиален в случае, если размерность пространства фиксирована;

б) построен приближенный алгоритм, который является полностью полиномиальной приближенной схемой (ЕРТАБ), если размерность пространства ограничена константой;

в) обоснован 2-приближённый полиномиальный алгоритм для общего случая задачи;

г) предложен рандомизированный алгоритм, который при заданных относительной ошибке и вероятности несрабатывания для установленных значений параметров находит приближённое решение за линейное время; найдены достаточные условия, при которых алгоритм полиномиален и асимптотически точен;

д) построена аппроксимационная схема (РТАБ) для общего случая задачи;

е) установлен статус вычислительной сложности и построен точный полиномиальный (почти линейный) алгоритм для одномерного случая задачи.

2. Для взвешенной квадратичной задачи двухкластерного разбиения конечной последовательности точек евклидова пространства при фиксированном центре одного из кластеров и весах, равных мощностям кластеров:

а) установлен статус вычислительной сложности (сильная КР-трудность);

б) построен точный алгоритм для целочисленного варианта задачи, который псевдополиномиален в случае, если размерность пространства фиксирована;

в) обоснован 2-приближенный полиномиальный алгоритм.

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

а) построен приближенный алгоритм, который при фиксированной размерности пространства реализует схему ЕРТАБ;

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

4. Для модификации задачи из пункта 1, в которой требуется найти подмножество наибольшей мощности при ограничениях на значение целевой функции:

а) установлен статус вычислительной сложности (сильная КР-трудность);

б) построен точный алгоритм для случая целочисленных входов и показано, что при фиксированной размерности пространства он псевдополино-миален.

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

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

численных экспериментов и т.п.

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

Личный вклад автора. Постановки задач предложены научными руководителями. Подходы к построению алгоритмов найдены совместно. Доказательства утверждений получены соискателем лично. Конфликт интересов с соавторами отсутствует.

Апробация работы. Результаты диссертации докладывались на международной конференции «Optimization and Applications» (Петровац, Черногория, 2015-2017, 2020), всероссийской конференции «Mathematical methods for pattern recognition» (Светлогорск, 2015), международной конференции «Optimization Problems and their Economical Applications» (Омск, 2015), международной конференции «Intelligent data Processing» (Барселона, Испания, 2016; Москва, Россия - Гаэта, Италия, 2018), международной конференции «Discrete Optimization and Operations Research» (Владивосток, 2016), международной конференции «SIBIRCON» (Новосибирск, 2017), международной конференции, посвященной 60-летию института математики им. С.Л.Соболева (Новосибирск, 2017), международной школе-семинаре «Methods of Optimization and Their Applications» (с.Максимиха, Байкал, 2017), международной конференции «Analysis of Images, Social networks and Texts» (Москва, 2017-2018), международной конференции «Computational and Applied Mathematics» (Новосибирск, 2017), международной конференции «Optimization Problems and Their Applications» (Омск, 2018), международной летней школе-конференции «Numerical Computations: Theory and Algorithms» (Изола-ди-Капо-Риццуто, Италия, 2019), международной кон-

ференции «Learning and Intelligent Optimization Conference» (Ханья, Греция, 2019), международной конференции «Mathematical Optimization Theory and Operations Research» (Екатеринбург, Новосибирск, 2019, 2020), неоднократно на семинаре «Дискретные экстремальные задачи», на семинаре «Дискретный анализ» и на семинаре «Математические модели принятия решений» в ИМ СО РАН.

Публикации. По теме диссертации опубликованы работы [36-59]. Основные результаты диссертации опубликованы в [36-52] в изданиях, входящих в список ВАК, в том числе 11 публикаций — в журналах, индексируемых системой цитирования Web of Science, 17 — Scopus, 11 — RSCI (ядро РИНЦ).

Структура и объем диссертации. Диссертация состоит из введения, 3 глав, заключения, списка обозначений и сокращений и списка литературы. Она изложена на 95 страницах. Главы диссертации подразделяются на параграфы, параграфы подразделяются на подпараграфы. Все утверждения (леммы, замечания, теоремы, следствия, свойства) имеют двойную нумерацию: номер главы и номер утверждения в текущей главе. Формулы также имеют двойную нумерацию: номер главы и номер формулы внутри главы. Список литературы содержит 59 наименований. Работы автора по теме диссертации приведены отдельным списком.

Благодарности

Автор выражает благодарность своему научному руководителю Владимиру Ильичу Хандееву за помощь и поддержку в процессе обучения и научной деятельности. Автор выражает благодарность Александру Васильевичу Кельмано-ву, своему первому научному руководителю, за постановку интересной задачи, внимание к работе, полезные обсуждения и помощь в профессиональном становлении. Также автор благодарит всех сотрудников лаборатории анализа данных

ИМ СО РАН и кафедры теоретической кибернетики ММФ НГУ за создание творческой атмосферы, необходимой для написания этой работы.

Глава 1

Задача взвешенной кластеризации конечного множества точек евклидова пространства

В этой главе рассматривается задача взвешенной 2-кластеризации конечного множества точек евклидова пространства при фиксированном (в начале координат) центре одного из кластеров. Здесь весами являются мощности искомых кластеров.

Задача 1. Дано: множество Y = {Уъ... ,Vn} точек из Rd и натуральное число M. Найти: разбиение множества Y на два кластера C и Y \ C такое, что

Fi(C) = |C| £ \\y - y(C)\\2 + |Y\C| £ \\y\\2 ^ min, (1.1)

yeC yey\C

где y(C) = -г! У — геометрический центр (центроид) кластера C, при ограни-

1 1 yeC

чении |C| = M.

Эта задача NP-трудна в сильном смысле [2,3]. Подробнее про неё как про основную задачу диссертационного исследования было сказано во введении.

1.1 Точный алгоритм для задачи двухкластерного разбиения множества точек на прямой

1.1.1 Структура оптимального решения

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

Лемма 1.1. Для произвольной точки x € Rd и конечного множества Zc Rd верно равенство:

Е lly - xll2 = Е lly - y(z)ll2 + |ZH|X - y(z)||2.

y€Z y€Z

Пусть C С Y, |C| = M и x € Rd. Введем новое обозначение:

Gi(C, x) = M E ||y - x112 + (N - M) Е ||y||2 . (1.2)

У€С y€Y\C

Всюду далее до конца параграфа считаем, что размерность пространства равна единице: d =1. Пусть C* используется для обозначения оптимального решения задачи 1.

Лемма 1.2. 1) Пусть M > N. Если xa,xb € C*, xk € Y и xa < xk < xb, то xk € C*.

2) Пусть M < N. Если xa, xb € Y\C*, xk € Y и xa < xk < xb, то xk € Y\C*.

Рис. 1.1. Пример структуры оптимального решения в случае 2М — N > 0. Белые точки — элементы множества С*, черные точки — элементы множества У\ С *.

Рис. 1.2. Пример структуры оптимального решения в случае 2М — N < 0. Белые точки — элементы множества С *, черные точки — элементы множества У \ С *.

Доказательство. 1) Предположим, что найдутся ха,хь € С * и хк Е У \ С * такие, что ха < хк < хь. Тогда обозначим за С1 и С2 следующие множества:

С1 = (С* \ {хь}) и {Хк}, С2 = (С* \ {ха}) и {Хк}.

В рамках этих обозначений верны равенства:

^ (С *) = ^(С*,у(С*)) = С1(Сьу(С*))+

+ М||жь - у(С*)||2 - М||ж* - У(С*)||2 - (Ж - М)||ж6||2 + (Ж - М)||ж*||2 .

По Лемме 1.1, ^(С^С*)) = ^(С^ + М2||у(С*) - у(Сх)|2 = ^(С^ + ||жь -ж*||2 . Поэтому,

^ (С*) = ^ (С1) + М2 ||у(С*) - у(С1)|2 + М ||жь - у(С *)||2+

+ (Ж - М)||ж*||2 - М||ж* - у(С*)||2 - (Ж - М)||ж6||2 > > ^(С*) + М2||у(С*) - у(С1)|2 + М||жь - у(С*)||2+ + (Ж - М)||ж*||2 - М||ж* - у(С*)||2 - (Ж - М)||ж6||2 = = ^(С*) + ||жь - ж*||2 + (2М - Ж)(||жь||2 - ||ж*||2) + 2М(ж* - ж6,у(С*)> .

Далее, поскольку ё = 1, имеем:

(ж - ж*)2 + (2М - Ж)(ж2 - ж*) + 2М(ж* - жь)у(С*) < 0 , (1.3)

(жь - ж*)((2М - Ж + 1)жь + (2М - Ж - 1)ж* - 2Му(С*)) < 0 . Так как жь > ж*, получаем неравенства:

2Му(С*) > (2М - Ж + 1)ж + (2М - Ж - 1)ж* > (2М - Ж)(жь + ж*). (1.4)

Аналогично работая с С2, имеем:

(жа - ж*)((2М - Ж + 1)жа + (2М - Ж - 1)ж* - 2Му(С*)) < 0 .

Но мы знаем, что ха < , поэтому 2Му(С*) < (2М — N + 1)ха + (2М — N — 1)х* < (2М — N)(ха + х^) . (1.5) Неравенства (1.4) и (1.5) позволяют сделать вывод, что

(2М — N)хь < (2М — N)ха . Если 2М — N > 0, то хь < ха. Противоречие.

Если 2М — N = 0, то из неравенств (1.4) и (1.5) следует, что: 2Му(С*) = 0. Подставляя это в (1.3), получаем: (хь — хк)2 < 0. Противоречие.

2) Случай, когда М < у, рассматривается аналогично. Лемма доказана. □

Замечание 1.1. Если N = 2М, то одно из следующих утверждений верно: 1) х < у для всех х € С*, у Е У \ С*; 2) х > у для всех х € С*, у Е У \ С*.

Рис. 1.3. Пример структуры оптимального решения в случае 2М — N = 0. Белые точки — элементы множества С*, черные точки — элементы множества У \ С * (или наоборот).

1.1.2 Точный алгоритм и его обоснование

В этом разделе представлен точный алгоритм для решения одномерного случая задачи 1. Основная идея алгоритма заключается в следующем. В первую очередь, алгоритм сортирует входное множество в порядке возрастания. Если у искомого кластера С мощность М > Ж/2, то алгоритм формирует последовательность из (Ж - М + 1) множества, каждое из которых состоит из М последовательных точек. В другом случае, алгоритм формирует последовательность из (М + 1) множества, каждое из которых является дополнением до множества из (Ж - М) последовательных точек. В качестве решения алгоритм выбирает одно из построенных множеств, для которого значение целевой функции минимально.

Перед тем, как представить алгоритм, введём некоторые вспомогательные обозначения для двух рассматриваемых случаев значения мощности М. Упорядочим точки входного множества У = {ж1,...,ж^} так, что ж; < ж^+1 для г €{1,...,Ж - 1}.

1. М > я. Введем обозначения: С; = {ж;, ... , ж;+м-1} для г € {1,..., Ж - М + 1}. В этом случае мы можем заметить, что

(С*+1) = ^(С*) +

+ (ж*+м - ж*)((2М - Ж + 1)ж*+м + (2М - Ж - 1)ж* - 2Му(С*+0) . (1.6)

2. М < N. Введем обозначения: Д = {ж;, ..., ж;+я-м-1} для г € {1,..., М + 1}, С; = У \ В;. В этом случае мы можем заметить, что

(С*+1) = ^(С*) + (ж* - ж*+я-м)((2М - Ж + 1)ж*+

+ (2М - Ж - 1)ж*+я-м - 2Му(С*+1)) . (1.7)

Тогда пошаговая запись алгоритма выглядит следующим образом:

Алгоритм Ai.

Вход алгоритма: множество Y, натуральное число M. Шаг 0. Упорядочить Y в порядке возрастания.

Шаг 1. Если M > у, то перейти к Шагу 2, иначе перейти к Шагу 4. Шаг 2. Вычислить y(Ci). Для всех k £ {1,..., N — M} вычислить y(Ck+1) с помощью соотношения: y(Ck+1) = y(Ck) + M(хк+м — xk).

Шаг 3. Вычислить F1(C1) по формуле (1.1). Для всех k £ {1,..., N — M} вычсилить Fi(Ck+i) по формуле (1.6). Перейти к Шагу 6.

Шаг 4. Вычислить y(C1). Для всех k £ {1,...,M} вычислить y(Ck+1) с помощью соотношения: y(Ck+1) = y(Ck) + M(хк — Xk+N—м).

Шаг 5. Вычислить F1(C1) по формуле (1.1). Для всех k £ {1,... , M} вычислить F1(Ck+1) по формуле (1.7).

Список литературы диссертационного исследования кандидат наук Панасенко Анна Владимировна, 2022 год

Литература

[1] Gan Guojun, Chaoqun Ma, Jianhong Wu. Data Clustering: Theory, Algorithms, and Applications. ASA-SIAM Series on Statistics and Applied Probability. — SIAM, Philadelphia, ASA, Alexandria, VA, 2007. 448 p.

[2] Кельманов А. В., ПяткинА.В., NP-трудность некоторых квадратичных евклидовых задач 2-кластеризации // Докл. АН. — 2015 — Т. 464, N 5. — С. 535-538.

[3] Кельманов А. В., Пяткин А. В., О сложности некоторых квадратичных евклидовых задач 2-кластеризации // Журн. вычисл. математики и мат. физики. — 2016 — Т. 56, N3. — С. 498-504.

[4] SahniS., Gonzalez T, P-Complete Approximation Problems //J. ACM — 1976 — 23 — P. 555-566.

[5] BruckerP., On the Complexity of Clustering Problems // Henn R. et al. (eds.) Optimization and Operations Research, LNE, Springer, Berlin, Heidelberg — 1978 — Vol. 157 — pp. 45-54.

[6] delaVegaF., KenyonC., A Randomized Approximation Scheme for Metric Max-Cut // Journal of Computer and System Sciences — 2001 — Vol. 63 — P. 531-541.

[7] delaVegaF., KarpinskiM., KenyonC., Rabani Y., Polynomial Time Approximation Schemes for Metric Min-Sum Clustering // Electronic Colloquium on Computational Complexity (ECCC) — 2002 — Report 25.

[8] Shulman L.J., Clustering for edge-cost minimization (extended abstract) // Proc. of the 32nd Ann. ACM Symp. on Theory of Computing — 2000 — P. 547-555.

[9] Indyk P.: A sublinear time approximation scheme for clustering in metric spaces // 40th Ann. Symp. on Foundations of Computer Science (Cat. No.99CB37039) — 1999 — pp. 154-159

[10] Bartal Y., Charikar M, Raz D.: Approximating min-sum k-clustering in metric spaces // STOC '01 — 2001 — P. 11-20

[11] Hasegawa S., Imai H., Inaba M, Katoh N., Nakano J., Efficient Algorithms for Variance-Based k-Clustering // Proc. of the 1st Pacific Conference on Computer Graphics and Applications (Pacific Graphics'93, Seoul, Korea), World Scientific, River Edge, NJ — 1993 — Vol. 1. — P. 75-89.

[12] Inaba M., Katoh N., ImaiH., Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering: (extended abstract) // SCG '94 Proc. of the tenth annual symposium on Computational geometry (Stony Brook, NY, USA, June 6-8, 1994) — 1994 — P. 332-339.

[13] Кельманов А. В., Романченко С. М., Приближенный алгоритм для решения одной задачи поиска подмножества векторов // Дискрет. анализ и исслед. операций — 2011 — Т. 18, N 1. — С. 61-69.

[14] Кельманов А. В., Хандеев В. И., Точный псевдополиномиальный алгоритм для одной задачи двухкластерного разбиения множества векторов // Дискрет. анализ и исслед. опер. — 2015 — Т. 22, № 4. — С. 50-62.

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

[16] Wirthl., Algorithms + data structures = programs. — New Jersey: Prentice Hall, 1976. 366 p.

[17] Кельманов А. В., Хандеев В. И. Полностью полиномиальная аппроксима-ционная схема для специального случая одной квадратичной евклидовой задачи 2-кластеризации // Журн. вычисл. математики и мат. физики. — 2016. — Т. 56, № 2. — С. 332-340.

[18] BallK., An Elementary Introduction to Modern Convex Geometry. Flavors of Geometry — MSRI Publications, 1997, Vol. 31.

[19] Golub,G.H., Van Loan,C.F., Matrix Computations. — Johns Hopkins University Press: Johns Hopkins Studies in the Mathematical Sciences, 1996.

[20] Кельманов А.В., Хандеев В.И. Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов // Журн. вычисл. математики и мат. физики. — 2015. — Т. 55, № 2. — С. 335-344.

[21] Кельманов А. В., Хамидуллин С. А. Приближённый полиномиальный алгоритм для одной задачи разбиения последовательности // Дискрет. анализ и исслед. опер. — 2014. — Т. 21, № 1. — С. 53-66.

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

[23] Aggarwal A., Imai H., Katoh N., Suri S., Finding k points with minimum diameter and related problems //J. Algorithms. — 1991 — Vol.12, No. 1. — P. 38-56.

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

[25] Шенмайер В. В., Решение некоторых задач поиска подмножества векторов с использованием диаграмм Вороного // Дискрет. анализ и исслед. опер. — 2016. — Т. 23, № 4. — С. 102-115.

[26] Kel'manov, A. V., Romanchenko, S. M., An Approximation Algorithm for Solving a Problem of Search for a Vector Subset //J. Appl. Ind. Math. — 2012 — Vol. 6, N 1 — P. 90-96

[27] Шенмайер В. В., Аппроксимационная схема для одной задачи поиска подмножества векторов // Дискрет. анализ и исслед. опер. — 2012. — Т. 19, N 2. — С. 92-100.

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

[29] GimadiE.Kh., Kel'manovA. V., Kel'manovaM. A., KhamidullinS. A.: A posteriori detecting a quasiperiodic fragment in a numerical sequence // Pattern Recognition and Image Analysis. 2008. Vol. 18, №1. P. 30-42. DOI: doi:10.1134/S1054661808010057

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

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

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

[33] Гимади Э. Х, Глазков Ю. В., Рыков И. А.: О двух задачах выбора подмножества векторов с целочисленными координатами в евклидовом пространстве с максимальной нормой суммы // Дискрет. анализ и исслед. опер. 2008. Т. 15, 4. С. 30-43.

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

[35] Долгушев А.В., Кельманов А.В., Шенмайер В.В. Полиномиальная аппрок-симационная схема для одной задачи разбиения конечного множества на

два кластера // Тр. Ин-та математики и механики УрО РАН. — 2015. — Т. 21, №3. — С. 100-109.

Работы автора по теме диссертации.

[36] Kel'manov A.V., Motkova A.V., Exact pseudopolynomial algorithms for a balanced 2-clustering problem //J. Appl. Ind. Math. — 2016 — Vol. 10, P. 349—355.

[37] Kel'manov A.V., Motkova A.V., A Fully Polynomial-Time Approximation Scheme for a Special Case of a Balanced 2-Clustering Problem // LNCS 9869

— 2016 — P. 182-192.

[38] Kel'manov A.V., Motkova A.V., An Approximation Scheme for a Weighted Two-Cluster Partition Problem // LNCS 10716 — 2017 — P. 323-333.

[39] Kel'manov A.V., Motkova A.V., Algorithms with performance guarantee for a weighted 2-partition problem // CEUR Workshop Proceedings 1987 — 2017 — P. 304-309.

[40] Kel'manov A.V., Motkova A.V., An approximation polynomial-time algorithm for a cardinality-weighted 2-clustering problem //Proceedings - 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON — 2017 — P. 94-96.

[41] Kel'manov A.V., Motkova A.V., Shenmaier V.V., Approximation scheme for the problem of weighted 2-Clustering with a fixed center of one cluster // Proceedings of the Steklov Institute of Mathematics — 2018 — Vol.303, Suppl.1

— P. 136-145.

[42] Kel'manov A., Khandeev V., Panasenko A., Randomized Algorithms for Some Clustering Problems // CCIS 871 — 2018 — P. 109-119.

[43] Kel'manov A., Khandeev V., Panasenko A., Exact Algorithms for the Special Cases of Two Hard to Solve Problems of Searching for the Largest Subset // LNCS 11179 — 2018 — P. 272-282.

[44] Kel'manov A., Motkova A., Polynomial-Time Approximation Algorithm for the Problem of Cardinality-Weighted Variance-Based 2-clustering with a Given Center // Comp.Math. and Math.Phys. — 2018 — Vol. 58, №1 — P. 130-136.

[45] Kel 'manov A., Panasenko A., Approximation Scheme for a Quadratic Eucledian Weighted 2-Clustering Problem // Pattern Recognition and Image Analysis. — 2018 — Vol.28, №1 — P. 17-23.

[46] Kel'manov A.V., Khandeev V.I., Panasenko A.V., Randomized Algorithms for Some Hard-to-Solve Problems of Clustering a Finite Set of Points in Euclidean Space // Computational Mathematics and Mathematical Physics — 2019 — Vol. 59, №5 — P. 842-850.

[47] Panasenko A., A PTAS for One Cardinality-Weighted 2-Clustering Problem // LNCS 11548 — 2019 — P. 581-592.

[48] Kel'manov A.V., Khandeev V.I., Panasenko A.V., Exact Algorithms of Search for a Cluster of the Largest Size in Two Integer 2-Clustering Problems // Numerical Analysis and Applications — 2019 — Vol. 12, №2 — P. 105-115.

[49] Kel 'manov A., Khamidullin S., Panasenko A., 2-Approximation polynomial-time algorithm for a cardinality-weighted 2-partitioning problem of a sequence // LNCS 11974 — 2020 — P. 386-393.

[50] Kel'manov A., Khamidullin S., Panasenko A., Exact algorithm for one cardinality-weighted 2-partitioning problem of a sequence // LNCS 11968 — 2020 — P. 135-145.

[51] Khandeev V., Panasenko A., Exact Algorithm for the One-Dimensional Quadratic Euclidean Cardinality-Weighted 2-Clustering with Given Center Problem // CCIS 1275 — 2020 — P. 30-35.

[52] Khamidullin S., Khandeev V., Panasenko A., Randomized Algorithms for Some Sequence Clustering Problems // LNCS 12096 — 2020 — P. 96-101.

[53] Kel'manov A.V., Motkova A.V., An approximation scheme for a balanced 2-clustering problem // Abstracts of the VII International Conference «Optimization and Applications» (0PTIMA-2016) — Petrovac, Montenegro: 2016. — P. 83.

[54] Kel'manov A.V., Motkova A.V., An Approximation Scheme for a Balanced 2-Clustering with Restrictions on the Cardinalities of Clusters // Book of abstracts of the 11th International Conference «Intelligent data Processing» (IDP-2016) — Moscow, Russia: 2016 — P. 76-77.

[55] Kel' manov A.V., Motkova A.V., An Approximation Scheme for a Balanced 2-Clustering with Restrictions on the Cardinalities of Clusters // Abstracts of the International Conference «Computational and Applied Mathematics 2017» (CAM 2017) — Novosibirsk: 2017 — P. 204.

[56] Kel'manov A.V., Motkova A.V., An Approximation Scheme for a Weighted 2-Clustering Problem // Abstracts of the 17th Baikal International School-Seminar «Methods of Optimization and Their Applications» (BAIKAL 2017) — Maksimiha, Baikal: 2017 — P. 107.

[57] Кельманов А.В., Моткова А.В., Шенмайер В.В., Аппроксимационная схема для задачи взвешенной 2-кластеризации // Тезисы докладов Международной конференции «Математика в современном мире», посвященной 60-летию Института математики им. С.Л. Соболева СО РАН — Новосибирск:

2017 — С. 436.

[58] Kel'manov A.V., Khandeev V.I., Panasenko A.V., Exact Algorithms for the Special Cases of Two Hard-to-Solve Problems // Abstracts of the 12th International Conference on Intelligent Data Processing: Theory and Applications (IDP-2018) — Moscow: 2018 — P. 54-55.

[59] Kel'manov A.V., Khandeev V.I., Panasenko A.V., Randomized Algorithms for Some Clustering Problems // Abstracts of the 12th International Conference on Intelligent Data Processing: Theory and Applications (IDP-2018) — Moscow:

2018 — P. 56-57.