Разработка алгоритма кластеризации на основе DC программирования1

1. Разработка алгоритма кластеризации на основе DC программирования

Федеральное государственное бюджетное образовательное
учреждение высшего образования
Иркутский национальный исследовательский
технический университет
Институт информационных технологий и анализа данных
имени Е. И. Попова
Разработка алгоритма
кластеризации на основе DC
программирования
Выполнила: Груздева Мария Сергеевна, ИСТб-22-1
Руководитель: Лемперт Анна Ананьевна, к.ф-м.н., доцент ИИТиАД

2. Кластеризация

Кластеризация — это группировка множества объектов
на подмножества (кластеры) таким образом, чтобы
объекты из одного кластера были более похожи друг на
друга, чем на объекты из других кластеров по какомулибо критерию.
Цели кластеризации:
• понимание данных путём выявления кластерной
структуры;
• сжатие данных, посредством выборки наиболее
типичного объекта из всех кластеров;
• обнаружение новизны, когда выделяются нетипичные
объекты, которые невозможно отнести ни к одному
кластеру.
1

3. Сравнительный анализ существующих алгоритмов

Алгоритм
Особенность постановки
Преимущества
Ограничения
k-means
(Ллойда)
Задача невыпуклой
оптимизации (MSSC)
Простота реализации;
высокая скорость (O(nkd));
Чувствительность к
инициализации; застревание в
локальных минимумах
Иерархическая
кластеризация
Метод пошаговой
оптимизации, где на каждом
этапе выбирается наилучшее
локальное
слияние/разделение
Наглядность
(дендрограмма); не требует
задания k заранее
Высокая вычислительная
сложность O(n³)
DBSCAN
Обнаружение кластеров
Решает задачу кластеризации произвольной формы;
на основе плотности данных автоматическое выявление
выбросов
Чувствительность к параметрам ε
и minPts;
Spectral
Clustering
Оптимизация
нормализованного разреза
графа
Работает с нелинейно
разделимыми и сложными
кластерами
Высокая сложность O(n²–n³);
необходимость построения
матрицы сходства
EM-алгоритм
(GMM)
Вероятностная модель
(оценка параметров смеси
распределений)
Мягкая кластеризация;
моделирование
эллипсоидальных
кластеров
Чувствительность к
инициализации; необходимость
выбора структуры ковариации
2

4. Цель и задачи

Цель: повысить точность кластеризации на основе решения задачи MSSC за счет
разработки алгоритма на основе DC оптимизации, а также создания приложения,
предназначенного для сравнительного тестирования разработанного метода с
классическим алгоритмом k-means.
Задачи:
1. Исследовать оптимальные методы локального поиска на основе DC.
• Разработать и протестировать DCA-алгоритм с решением выпуклых подзадач с
помощью решателя.
• Создать алгоритм с аналитическим вычислением X и Y.
• Проанализировать влияние параметров на качество кластеризации.
2. Разработать приложение для тестирования алгоритмов.
3. Реализовать запуск базовых и новых алгоритмов в приложении.
4. Провести эксперименты на реальных и синтетических данных и сравнить
алгоритмы.
3

5. Постановка задачи K-means (MSSC)

Оптимизационная постановка задачи: