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

КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

ОБЩИЕ СВЕДЕНИЯ

Номер проекта 17-71-10176

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

Руководитель Ушаков Антон Владимирович, Кандидат физико-математических наук

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

Конкурс №23 - Конкурс 2017 года по мероприятию «Проведение инициативных исследований молодыми учеными» Президентской программы исследовательских проектов, реализуемых ведущими учеными, в том числе молодыми учеными

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-202 - Интеллектуальный анализ данных и распознавание образов

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

Код ГРНТИ27.47.19

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

Аннотация
На сегодняшний день все больший интерес исследователей привлекают различного рода задачи, возникающие в области «больших данных» и интеллектуального анализа больших объемов информации. Этот интерес во многом продиктован современными технологиями и, соответственно, возрастающими возможностями по сбору и хранению больших массивов разнородной информации, анализ которой может улучшить качество обслуживания потребителей и получить значительные конкурентные преимущества, способствовать поиску новых взаимосвязей и закономерностей в сложных системах, например, для разработки средств персонализированной медицины. В рамках современных исследований в данной области, особую популярность получили задачи анализа социальных сетей и выявления различного рода закономерностей. Такого рода исследования имеют не только бизнес-ориентированные цели, но могут также оказать существенный вклад в такие области науки, как антропология, социальная психология, политология, различные отрасли социологии и др. Настоящий проект посвящен лишь малой части, возникающих в рамках данного направления задач, связанных в основном с техниками обучения без учителя и анализа социальных сетей. Более того, разработанные в рамках проекта подходы являются актуальными и с точки зрения развития теории и практики целочисленного программирования и дискретной оптимизации. Для достижения данной цели в рамках проекта планируется разработка, реализация и анализ параллельных алгоритмов для поиска приближенных решений в задачах кластеризации, основанных на модели задачи о p-медиане и ее модификации, имеющей вполне определенное практическое обоснование. Данная модифицированная модель представляет собой нелинейный вариант задачи о p-медиане с нефиксированным числом искомых кластеров (медиан), являющимся целочисленной переменной, в то время как в целевую функцию добавляется дополнительное нелинейное слагаемое, ограничивающее максимальное число кластеров. Такая модифицированная задача позволяет в какой-то степени преодолеть недостаток классической задачи о p-медиане (а также некоторых популярных алгоритмов, например, k-means и его современных модификаций), связанный с необходимостью знать наперед искомое число кластеров. Стоит отметить, что определение числа кластеров, вообще говоря, является довольно трудной задачей и является отдельным направлением исследований. В основе предлагаемых параллельных алгоритмов лежат чрезвычайно эффективные методы поиска близких к оптимальному допустимых решений задачи о p-медиане и ее нелинейного варианта. Фактически параллельные алгоритмы представляют собой так называемые «лагранжевы эвристики» и основаны на постепенном улучшении нижних и верхних оценок оптимального значения, получаемых с использованием двойственных по Лагранжу задач относительно различных групп ограничений, а также эвристических методов фиксирования переменных и современных метаэвристик. Предлагаемые схемы являются новыми и реализуют параллелизм по данным, а также предполагают использование специфических техник манипуляции с исходными данными, повышающими эффективность алгоритмов для задач большой и сверхбольшой размерности, в том числе с использованием большого числа параллельных процессоров. Отметим, что представленные параллельные алгоритмы позволят находить решение в задаче о p-медиане и ее модификации рекордной на сегодняшний день размерности. Основной вклад в развитие теории машинного обучения состоит в альтернативном, основанном на широком использование моделей и методов ЦЛП, подходе к известным задачам, возникающим в области кластеризации, классификации и анализа социальных сетей. Такой подход не получил в настоящий момент широкого распространения (особенно в области кластеризации и классификации) из-за заложенного еще в 1970-х убеждения о высокой сложности задач ЦЛП и об отсутствии эффективных методов их решения. Однако, развитие этой области математической оптимизации и появление современных эффективных алгоритмов приводит к постепенному росту числа публикаций, а также появлению новых программных пакетов (например, пакет CRIO) для решения задач кластеризации и классификации на основе целочисленного программирования. Более того, разрабатываемые в рамках проекта параллельные алгоритмы внесут существенный вклад и в область дискретных задач размещения, поскольку позволят найти решения задачи о p-медиане и ее модификации рекордных размерностей. Так, параллельный алгоритм для модифицированной задачи о p-медиане может вполне естественным образом найти применение для решения задач размещения большого числа относительно дешевых объектов инфраструктуры (таких как почтовые ящики, контейнеры для мусора и т.д.) для обслуживания огромного числа потребителей, минимизируя общее количество таких объектов. Помимо параллельных алгоритмов поиска близких к оптимальному решений задачи кластерного анализа, представленной в виде задачи о p-медиане, в рамках проекта предполагается исследование других моделей ЦЛП, возникающих в области анализа социальных сетей. На настоящий момент, в рамках проекта планируется исследование так называемой задачи оптимального разделения баз данных социальных сетей. Современный бурный рост социальных сетей и количества их пользователей приводит к стремительному увеличению объемов загружаемого на страницы пользователей контента, такого как фотографии, видеоматериалы, текстовые сообщения и т.п. Очевидно, что такой объем информации не может храниться на единственном сервере, а должен быть соответствующим образом распределен между сотнями и тысячами таких серверов. В связи с этим возникает проблема быстрого доступа пользователя к его личным данным с учетом естественных ограничений на пропускную способность сетей, а также минимизируя возникающие задержки. Задача осложняется тем, что помимо собственной информации пользователю необходимо предоставлять быстрый доступ также и к информации всей его группы контактов. В рамках проекта планируется исследование задачи оптимального разделения данных социальных сетей как модели ЦЛП. Предполагается теоретическое исследование полиэдральной структуры задачи, а также разработка различных «усиленных» (дающих лучшую двойственную оценку оптимального значения) формулировок. Поскольку реальные практические приложения требуют умения быстро находить решения задач большой размерности, то основное внимание в проекте будет уделено разработке эффективных точных алгоритмов, таких как метод ветвей и отсечений, ветвей и оценок, а также различных основанных на их базе эвристик, требующих, в частности, исследования полиэдральной структуры задачи, поиск новых семейств правильных неравенств и т.д. Отметим, что исследование представленной, по сути дела, задачи комбинаторной оптимизации с точки зрения теории и методов целочисленного программирования будет проводится впервые.

ОТЧЁТНЫЕ МАТЕРИАЛЫ

Публикации

1. Ушаков А.В. Гибридный распределенный алгоритм кластеризации больших данных на основе поиска k-медоидов Материалы VII международной конференции "Проблемы оптимизации и их приложения" (год публикации - 2018)

2. Ушаков А.В. Гибридный распределенный алгоритм кластеризации больших данных на основе поиска k-медоидов Проблемы оптимизации и их приложения (OPTA-2018), Омск: Изд-во Ом. гос. ун-та, 2018. С. 63. (год публикации - 2018)

3. Ушаков А.В. Параллельный алгоритм решения задачи о k-медоидах в приложении к кластеризации больших коллекций изображений Ляпуновские чтения: материалы науч. конф. Иркутск, 3-5 декаб. 2018 г. Иркутск, Изд-во ИДСТУ СО РАН, 2018. С. 85-86. (год публикации - 2018)

4. Ушаков А.В., Васильев И.Л. A parallel heuristic for a k-medoids clustering problem with unfixed number of clusters Proc 42th International Convention on Information and Communication Technology, Electronics and Microelectronics, MIPRO 2019 (год публикации - 2019)

5. Ушаков А.В., Васильев И.Л. A Computational Comparison of Parallel and Distributed k-median Clustering Algorithms on Large-scale Image Data Communications in Computer and Information Science (год публикации - 2019)

6. Ушаков А.В., Васильев И.Л. Near-Optimal Large-Scale K-medoids Clustering arXiv preprint (год публикации - 2019)

7. Ушаков А.В., Васильев И.Л. Near-Optimal Large-Scale K-medoids Clustering Information Sciences, -V. 545. - PP. 344-362 (год публикации - 2021)
10.1016/j.ins.2020.08.121

8. Ушаков А.В. Параллельный гибридный алгоритм кластеризации на основе задачи о p-медиане Ляпуновские чтения: материалы науч. конф. Иркутск, 5-7 декаб. 2017 г. Иркутск: Изд-во ИДСТУ СО РАН, С. 53. (год публикации - 2017)

9. Васильев И.Л., Ушаков А.В. A shared memory parallel heuristic algorithm for the large-scale p-median problem Optimization and Decision Science: Methodologies and Applications. ODS 2017. Springer Proceedings in Mathematics & Statistics, vol. 217. PP. 295-302 (год публикации - 2017)
10.1007/978-3-319-67308-0_30

Публикации

6. Ушаков А.В., Васильев И.Л. Near-Optimal Large-Scale K-medoids Clustering arXiv preprint (год публикации - 2019)