Литературный обзор: K-means-кластеризация с дифференциальной приватностью в условиях горизонтальной и вертикальной федерации

Анализ современных работ по K-means, дифференциальной приватности и федеративному обучению

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

Нужна работа по этой теме? Получите консультацию за 10 минут! Telegram: @Diplomit Телефон/WhatsApp/MAX: +7 (987) 915-99-32, Email: admin@diplom-it.ru

Оформите заказ онлайн: Заказать ВКР

Дифференциальная приватность в K-means: от теории к практике

Распределенные и федеративные сценарии

1. Распределенный K-means с гарантиями локальной дифференциальной приватности

• Что сделано: В статье предложен первый механизм для распределенного алгоритма K-means, обеспечивающий локальную дифференциальную приватность (LDP). Это означает, что пользователи самостоятельно искажают свои данные на устройстве перед отправкой ненадежному серверу для кластеризации. Авторы также представили расширенный механизм для защиты промежуточных результатов (информации о принадлежности к кластерам на каждой итерации) и рассмотрели сценарий с разными требованиями пользователей к приватности.
• Результаты: Теоретически доказано, что механизм обеспечивает LDP. Эксперименты на реальных наборах данных показали, что подход сохраняет качество кластеризации лучше, чем стандартные методы с централизованной DP, особенно в условиях распределенного сценария без доверенного центра.
• Недостатки: Основное ограничение — неизбежное снижение утилиты (качества кластеризации) из-за сильного зашумления, характерного для модели LDP. Производительность алгоритма может значительно ухудшаться при очень строгих требованиях к приватности (малых ε).
• Перспективы: Предложенный механизм является фундаментальным для сценариев горизонтального федеративного обучения (HFL), где данные распределены по устройствам. Дальнейшие исследования могут быть направлены на разработку адаптивных схем распределения приватности для еще большего улучшения утилиты.

2. Федеративное обучение с неоднородной дифференциальной приватностью

• Что сделано: Исследована проблема гетерогенной (неоднородной) дифференциальной приватности в рамках FL. В этом сценарии разные клиенты могут иметь различные требования к приватности (разные ε). Авторы проанализировали оптимальное решение для упрощенной линейной задачи в байесовской постановке и предложили новый алгоритм FedHDP, который использует персонализацию и взвешенное усреднение на сервере с учетом выбора приватности клиентами.
• Результаты: Теоретический анализ показывает, что в условиях гетерогенной приватности оптимальным решением для клиентов является персонализированная модель, даже если данные однородны. Эксперименты демонстрируют, что FedHDP обеспечивает прирост производительности до 9.27% по сравнению с базовым DP-FL, когда 5% клиентов отказываются от DP.
• Недостатки: Исследование сфокусировано на теоретическом анализе для линейных моделей и упрощенных задач. Применение подхода к сложным нелинейным моделям (например, глубоким нейросетям) и реальным условиям требует дополнительного изучения.
• Перспективы: Этот подход крайне важен для практического внедрения DP в FL, так как позволяет клиентам гибко выбирать уровень приватности. Перспективой является интеграция подобных гетерогенных схем с алгоритмами кластеризации, такими как K-means, в рамках FL.

Нужна работа по этой теме? Получите консультацию за 10 минут! Telegram: @Diplomit Телефон/WhatsApp/MAX: +7 (987) 915-99-32, Email: admin@diplom-it.ru

Оформите заказ онлайн: Заказать ВКР

Централизованные и практические методы

3. Практическая дифференциально-приватная кластеризация (Google)

• Что сделано: Представлен новый практический алгоритм для дифференциально-приватной кластеризации в центральной модели (с доверенным сервером). Алгоритм использует locality-sensitive hashing (LSH) для создания приватного "ядра" данных — набора взвешенных точек-представителей, — на котором затем запускается стандартный алгоритм (например, K-means++).
• Результаты: Алгоритм реализован в открытой библиотеке Google. Оценка на нескольких наборах данных показала, что он обеспечивает конкурентное или лучшее качество (измеряемое потерей K-means и точностью кластерных меток) по сравнению с существующими базовыми методами (diffprivlib, dp-clustering-icml17).
• Недостатки: Алгоритм требует от пользователя априорного задания радиуса сферы, содержащей все данные, что может быть сложной задачей в условиях приватности. Также необходима отдельная обработка приватности на этапе предобработки данных.
• Перспективы: Эта работа демонстрирует переход теоретических наработок в область практических инструментов. Для целей ВКР важно, что алгоритм напрямую совместим с K-means++. Исследование показывает возможность создания эффективных и практичных DP-версий стандартных алгоритмов машинного обучения.

5. Улучшенный дифференциально-приватный алгоритм K-means кластеризации

• Что сделано: Предложен улучшенный алгоритм DP-Kmeans, который добавляет шум Лапласа не единообразно, а адаптивно на основе силуэтного коэффициента каждого кластера. Это позволяет добавлять разный уровень шума к разным кластерам в каждой итерации, уменьшая отклонение центроидов. Алгоритм также разработан для работы в распределенной среде MapReduce.
• Результаты: Эксперименты показывают, что новый алгоритм повышает полезность результатов кластеризации при условии обеспечения приватности, особенно при малых значениях бюджета приватности (ε), когда стандартные методы работают плохо. Эффективность алгоритма подтверждена на больших наборах данных.
• Недостатки: Метод все еще опирается на централизованную модель доверенного сборщика данных (MapReduce framework). Он не рассматривает сценарии с ненадежным координатором, как в LDP или FL.
• Перспективы: Предложенная идея адаптивного распределения бюджета приватности между кластерами является инновационной и может быть перенесена в контекст федеративного обучения (как горизонтального, так и вертикального) для улучшения качества кластеризации при строгих ограничениях приватности.

8. Differentially Private k-Means Clustering (Su et al., 2016)

• Что сделано: Эта статья предлагает комплексный алгоритм для дифференциально-приватного K-means в централизованной модели (с доверенным сборщиком данных). Авторы не просто добавляют шум на выходе, а модифицируют ключевые шаги алгоритма: 1) этап инициализации центроидов с помощью дифференциально-приватной версии K-means++, 2) итеративное обновление центроидов с добавлением шума Лапласа к суммам и счётчикам кластеров, 3) ограничение числа итераций для контроля утечки приватности.
• Результаты: Ключевые результаты включают строгое доказательство обеспечения дифференциальной приватности на всех этапах и всесторонние эксперименты, показывающие, что алгоритм значительно превосходит наивные методы и сохраняет практическую полезность кластеризации.
• Недостатки: Зависимость от доверенного центра. Алгоритм напрямую не предназначен для федеративных сценариев, где такого центра может не быть.
• Перспективы: Методы, предложенные в этой статье (DP K-means++, зашумление обновлений), являются основными кандидатами для переноса в архитектуры HFL и VFL. Вопросы, которые предстоит решить: как распределить добавление шума между клиентами и сервером в HFL и как согласовать вычисления в VFL, минимизируя раскрытие информации даже зашумлённых величин.

Вертикальное федеративное обучение (VFL) и приватность

4. Обзор угроз приватности и методов защиты в вертикальном федеративном обучении

• Что сделано: Это первый всесторонний обзор, систематизирующий угрозы приватности и методы защиты в вертикальном федеративном обучении (VFL). Угрозы и контрмеры классифицированы с точки зрения жизненного цикла модели, что охватывает этапы инициализации, обучения, вывода и обслуживания.
• Результаты: Обзор предоставляет четкую таксономию атак (например, вывод признаков, восстановление данных) и защитных механизмов (включая DP, гомоморфное шифрование, безопасные многосторонние вычисления) в контексте VFL. Это служит ценным ресурсом для понимания проблемного поля.
• Недостатки: Как и любой обзор, эта работа не предлагает новых алгоритмических решений, а фокусируется на систематизации существующих. Для исследования потребуется углубиться в конкретные статьи, предлагающие методы DP для VFL.
• Перспективы: Обзор четко обозначает открытые проблемы, такие как компромисс приватность-производительность в VFL, комплексные атаки и стандартизация оценок. Это задает направление для будущих исследований, в том числе для разработки DP K-means в рамках VFL.

7. Privacy-preserving k-means clustering via multi-party computation (Bunn & Ostrovsky, 2007)

• Что сделано: В этой ранней, но значимой работе исследуется задача конфиденциальной кластеризации в модели вертикального разделения данных (VFL), когда разные стороны владеют разными атрибутами одних и тех же субъектов. Авторы предлагают протокол, основанный на технике безопасных многосторонних вычислений (Secure Multi-Party Computation, MPC).
• Результаты: Главный результат — работающий криптографический протокол, гарантирующий конфиденциальность при условии честности, но любопытствующих участников.
• Недостатки: Высокие вычислительные и коммуникационные издержки, характерные для MPC того времени, а также отсутствие формальных гарантий дифференциальной приватности — защита обеспечивается только против получестных противников в рамках конкретного протокола.
• Перспективы: Перспективы для современных исследований видятся в комбинировании MPC с дифференциальной приватностью для создания защиты от более сильных противников, а также в оптимизации подобных протоколов для использования с улучшенными алгоритмами инициализации, такими как K-means++.

13. Differentially Private Vertical Federated Clustering (Z. Li et al., 2022)

• Что сделано: Предложен первый практический алгоритм для вертикального федеративного (VFL) k-means с дифференциальной приватностью. Алгоритм основан на ненадёжном центральном сервере. Каждая сторона локально вычисляет кандидатов в центроиды и закодированную информацию о принадлежности точек к кластерам, применяя DP. Эти зашумленные данные отправляются на сервер, который строит по ним взвешенную сетку (grid).
• Результаты: Представлен алгоритм с доказанными гарантиями ε-дифференциальной приватности. Подход превосходит базовые методы, приближаясь по качеству кластеризации к централизованному DP-решению.
• Недостатки: Качество результата зависит от точности построения взвешенной сетки, которая является аппроксимацией. Подход не использует продвинутые методы инициализации, такие как k-means++.
• Перспективы: Интеграция алгоритмов улучшенной инициализации (k-means++) в предложенную VFL-архитектуру, чтобы повысить качество начальных центроидов и снизить количество необходимых итераций, которые "расходуют" бюджет приватности.

Нужна работа по этой теме? Получите консультацию за 10 минут! Telegram: @Diplomit Телефон/WhatsApp/MAX: +7 (987) 915-99-32, Email: admin@diplom-it.ru

Оформите заказ онлайн: Заказать ВКР

Теоретические основы и улучшения алгоритма K-means++

Фундаментальные работы и обзоры

6. K-means++: The Advantages of Careful Seeding (Arthur & Vassilvitskii, 2007)

• Что сделано: В этой основополагающей статье представлен сам алгоритм K-means++, который стал стандартом де-факто для инициализации центроидов. Авторы формально описывают простую, но мощную стратегию выборки D² sampling.
• Результаты: Теоретическое доказательство того, что алгоритм в среднем гарантирует аппроксимацию целевой функции с коэффициентом O(log k), что является экспоненциальным улучшением по сравнению с полностью случайной инициализацией. Эксперименты подтверждают, что K-means++ не только находит лучшее решение, но и сходится быстрее.
• Недостатки: Не рассматриваются вопросы вычислительной эффективности на очень больших данных, распределённых вычислений или аспекты конфиденциальности.
• Перспективы: Любая система, использующая K-means (включая федеративные), выигрывает от этой инициализации. Ключевой задачей становится адаптация принципа "осторожной выборки" к условиям, когда данные распределены (HFL/VFL) и когда на центроиды или расстояния накладывается шум для обеспечения дифференциальной приватности.

9. Optimal k-means Clustering in One Dimension by Dynamic Programming (Wang & Song, 2011)

• Что сделано: Предложен фундаментально важный точный алгоритм для задачи K-means в одномерном случае, решаемый методом динамического программирования за время O(kn).
• Результаты: Этот результат является теоретически оптимальным.
• Недостатки: Статья не затрагивает напрямую федеративное обучение или приватность.
• Перспективы: В контексте HFL/VFL это открывает перспективу для разработки более эффективных и точных локальных шагов алгоритма. Если данные на стороне клиента можно обработать точно, это может снизить количество итераций и уменьшить совокупную утечку приватности.

10, 27. k-means++: A Survey — Обзорные статьи (Anselm, Ri, Wang, 2024)

• Что сделано: Представлен современный структурированный обзор алгоритма k-means++, его теоретических основ и последующих улучшений. Детально разбирается оригинальное доказательство, обсуждаются попытки улучшить результат и приводятся "плохие" примеры данных.
• Результаты: Систематизация знаний об алгоритме. Обзор служит отличной отправной точкой для понимания того, почему k-means++ стал стандартом, каковы пределы его эффективности.
• Недостатки: Не предлагает новых алгоритмических решений. Не рассматривает модификации для распределенных сред (HFL/VFL) или механизмы обеспечения конфиденциальности.
• Перспективы: Предоставляет прочный теоретический фундамент. Перспективой является применение принципов, изложенных в обзоре (анализ устойчивости D² sampling), к задачам федеративного обучения с добавлением шума для обеспечения приватности.

Улучшения и модификации K-means++

11. CAPKM++2.0: An upgraded version... (Li & Wang, 2023)

• Что сделано: Предложена усовершенствованная версия алгоритма Collaborative Annealing Power k-means++ (CAPKM++2.0). Модификация направлена на снижение зависимости от инициализации и повышение эффективности.
• Результаты: Эксперименты показали, что CAPKM++2.0 статистически значимо превосходит своего предшественника и шесть других классических алгоритмов по валидационным индексам кластеризации.
• Недостатки: Исследование проводится в рамках централизованной модели данных. Не рассматриваются сценарии распределенных данных или обеспечение дифференциальной приватности.
• Перспективы: Основная идея — использование совместной работы нескольких модулей и техники отжига — может быть адаптирована для федеративного обучения для достижения более качественной и стабильной кластеризации в условиях приватности.

12. Noisy k-means++ Revisited (Grunau et al., 2023)

• Что сделано: Теоретическая работа, доказывающая устойчивость k-means++ к адверсарному шуму в вероятностях выборки.
• Результаты: Строгое доказательство того, что даже при наличии небольшой адверсарной неточности в распределении D² sampling, алгоритм сохраняет первоначальную гарантию приближения O(log k).
• Недостатки: Работа является чисто теоретической и не содержит эмпирических экспериментов. Шум моделируется как адверсарное возмущение, а не стохастический шум (например, Гауссовский, используемый в DP).
• Перспективы: Имеет прямое и важнейшее значение для темы. Устойчивость алгоритма инициализации к контролируемому шуму — это фундаментальная предпосылка для создания его дифференциально-приватных версий.

17. Local Search k-means++ with Foresight (Conrads et al., 2024)

• Что сделано: Проведено исследование по улучшению практической эффективности алгоритма LS++ (Local Search k-means++). Предложен новый алгоритм Foresight LS++ (FLS++).
• Результаты: Новый алгоритм FLS++ демонстрирует лучшее качество решения, чем LS++, сохраняя при этом асимптотическую сложность и теоретические гарантии.
• Недостатки: Работа сосредоточена исключительно на централизованной setting. Вопросы распределённых вычислений и приватности данных не рассматриваются.
• Перспективы: Ключевая перспектива — адаптация принципов FLS++ для федеративных сценариев. Это включает разработку стратегий совместного выполнения локального поиска на распределённых данных с учётом ограничений на приватность.

20. k-variates++: more pluses in the k-means++ (Nock et al., 2016)

• Что сделано: Предложено двустороннее обобщение алгоритма инициализации k-means++, названное k-variates++. Обобщается процедура выборки и теоретическая гарантия. Показано, что схема эффективно сводится к конкретным алгоритмам для распределённой, потоковой и онлайн-кластеризации.
• Результаты: Главный результат — представлена новая адаптация k-variates++ для задач дифференциальной приватности (DP).
• Недостатки: Не раскрываются детали механизма добавления шума или точные гарантии приватности. Неясно, как алгоритм взаимодействует с архитектурой федеративного обучения.
• Перспективы: Работа является критически важным теоретическим мостом между K-means++ и темой. Прямо указывает на возможность построения дифференциально-приватных версий алгоритма инициализации.

22. Noisy, Greedy and Not So Greedy k-means++ (Bhattacharya et al., 2019)

• Что сделано: Проведён теоретический анализ жадной и шумной версий k-means++.
• Результаты: Для шумной версии доказано, что она сохраняет полилогарифмическую гарантию O(log² k) даже в условиях адверсарного искажения вероятностей.
• Недостатки: Не предлагает конкретного механизма для обеспечения дифференциальной приватности. Работа носит чисто теоретический характер.
• Перспективы: Предоставляет критически важный теоретический фундамент. Результат об устойчивости noisy k-means++ прямо указывает на то, что базовый алгоритм может быть робастным к преднамеренному зашумлению, необходимому для DP.

Нужна работа по этой теме? Получите консультацию за 10 минут! Telegram: @Diplomit Телефон/WhatsApp/MAX: +7 (987) 915-99-32, Email: admin@diplom-it.ru

Оформите заказ онлайн: Заказать ВКР

Прикладные исследования и гибридные модели с K-means++

Кластеризация в различных предметных областях

14. Using k-means++ algorithm for researchers clustering (Rukmi, Iqbal, 2017)

• Что сделано: Предложен метод кластеризации исследователей на основе их публикаций и характеристик социальных сетей с использованием K-means++.
• Результаты: Разработано приложение, представляющее информацию об исследователях в рамках кластеров.
• Недостатки: Работа является чисто прикладной и не содержит теоретического анализа. Не рассматриваются вопросы масштабируемости, конфиденциальности или совместной кластеризации без объединения данных.
• Перспективы: Предложенный конвейер может быть адаптирован для сценариев горизонтального федеративного обучения (HFL), где разные университеты хотят совместно проанализировать свои публикационные данные, не раскрывая их напрямую.

15. Hybrid model based on K-means++ algorithm... for short-term photovoltaic power prediction (2023)

• Что сделано: Предложена инновационная гибридная модель (HKSL) для прогнозирования мощности фотоэлектрических станций. K-means++ используется для классификации типов погоды.
• Результаты: Модель показала значительное снижение ошибки прогноза (RMSE) по сравнению с базовыми методами.
• Недостатки: Модель является централизованной. Не учитывает сценарий, когда данные распределены между разными участниками энергосети.
• Перспективы: Идеальный кандидат для применения вертикального федеративного обучения (VFL). Задача заключается в создании федеративного и дифференциально-приватного аналога модели.

16. A novel hybrid method of lithology identification based on k-means++ algorithm and fuzzy decision tree (2022)

• Что сделано: Предложен новый метод идентификации литологии по данным каротажа. K-means++ используется для оптимизации выбора начальных центров кластеров.
• Результаты: Точность предложенной модели достигла 93.92%, что превосходит результаты других алгоритмов машинного обучения.
• Недостатки: Метод централизован. Не рассматривает сценарий, когда разные типы данных каротажа находятся у разных компаний.
• Перспективы: Задачу можно переформулировать в контексте VFL. Перспективным направлением является разработка федеративной версии алгоритма с гарантиями дифференциальной приватности.

18. An indoor thermal comfort model based on K-means++ algorithm (2025)

• Что сделано: Впервые предложена модель прогноза группового теплового комфорта в помещении, основанная на неконтролируемом обучении с использованием алгоритма K-means++.
• Результаты: Модель достигла точности прогноза выше 90%, превосходя точность классической модели PMV-PPD (около 34%).
• Недостатки: Модель построена на предположении о наличии централизованного набора данных.
• Перспективы: Данная работа идеально иллюстрирует потребность в VFL с дифференциальной приватностью. Совместное обучение модели кластеризации K-means++ на распределённых данных с защитой приватности каждого источника является важной практической задачей.

19. Пространственная классификация гиперспектральных изображений с использованием метода кластеризации k-means++ (Зимичев и др., 2014)

• Что сделано: Предложен комплексный метод для классификации гиперспектральных изображений, учитывающий пространственную близость пикселей. Комбинируются SVM и сегментация, полученная с помощью k-means++.
• Результаты: Комбинация подходов позволяет повысить как точность, так и скорость классификации гиперспектральных данных.
• Недостатки: Статья является прикладной и устаревшей (2014 год). Не рассматривает распределённую обработку, конфиденциальность или федеративное обучение.
• Перспективы: Перспективой является адаптация конвейера к условиям горизонтального федеративного обучения (HFL), когда гиперспектральные снимки хранятся у разных организаций, которые хотят совместно обучить улучшенную модель, не обмениваясь исходными конфиденциальными данными.

23. K-Means++ Clustering Algorithm in Categorization of Glass Cultural Relics (2023)

• Что сделано: Алгоритм K-means++ используется для субкатегоризации древних стеклянных артефактов на основе данных об их химическом составе.
• Результаты: Разработанный конвейер (PCA + K-means++) успешно выделил шесть правдоподобных подкатегорий стекла. Алгоритм показал высокую устойчивость к случайному шуму.
• Недостатки: Статья является узкоспециализированным case-study. Не касается вопросов распределённых вычислений, конфиденциальности данных или федеративного обучения.
• Перспективы: Основная ценность — иллюстрация того, как подобные прикладные задачи могут стать движущей силой для более сложных исследований. Перспективой может быть рассмотрение подобной задачи в сценарии горизонтального федеративного обучения, требующего разработки дифференциально-приватных протоколов.

26. A K-means++ Based User Classification Method for Social E-commerce (Cui et al., 2021)

• Что сделано: Предложен и реализован метод классификации пользователей социальной e-commerce на основе алгоритма K-means++. Данные собираются через мобильное приложение с изолированным окружением (secure container).
• Результаты: Метод успешно апробирован на реальных данных. Кластеризация позволила выделить три устойчивых класса пользователей, которые статистически значимо различаются по уровню удержания.
• Недостатки: Исследование носит сугубо прикладной и централизованный характер. Предполагает сбор сырых поведенческих данных на центральный сервер.
• Перспективы: Архитектура сбора данных через secure container представляет значительный интерес для сценариев HFL. Каждое устройство могло бы локально запускать приватную версию K-means++, а затем безопасно агрегировать результаты на сервере для построения глобальной модели.

Гибридные и ускоренные методы

21. SOM++: Integration of Self-Organizing Map and K-Means++ Algorithms (Dogan et al., 2013)

• Что сделано: Предложен гибридный алгоритм SOM++, в котором K-means++ используется для интеллектуальной инициализации весов самоорганизующейся карты Кохонена (SOM).
• Результаты: Эксперименты показывают, что SOM++ имеет хорошую стабильность и значительно превосходит обычную SOM по времени обучения.
• Недостатки: Работа является узкоспециальной, посвящённой улучшению конкретного алгоритма (SOM).
• Перспективы: Идея использования K-means++ в качестве «умного инициализатора» для других алгоритмов является плодотворной. Открывает перспективу для создания гибридных федеративных алгоритмов.

25. Nyström Method with Kernel K-means++ Samples as Landmarks (Oglic, Gärtner, 2017)

• Что сделано: Предложено использование выборки по схеме kernel k-means++ для выбора ориентиров (landmarks) в методе Нюстрёма — методе низкоранговой аппроксимации ядерных матриц.
• Результаты: Получена первая теоретическая гарантия на относительную ошибку аппроксимации для метода Нюстрёма с ориентирами, выбранными через kernel k-means++.
• Недостатки: Работа не фокусируется на улучшении k-means++, а применяет его как готовый инструмент для другой задачи.
• Перспективы: Демонстрирует мощь k-means++ как инструмента выбора представительного подмножества данных. В сценариях HFL дифференциально-приватная версия k-means++ могла бы использоваться для выбора локальных ориентиров, которые затем безопасно агрегируются на сервере.

28. A Clustering Optimization for Energy Consumption Problems in Wireless Sensor Networks using Modified K-Means++ Algorithm (Mukti et al., 2022)

• Что сделано: Статья направлена на решение проблемы энергопотребления в беспроводных сенсорных сетях (WSN) через оптимизацию кластеризации. Авторы модифицируют алгоритм k-means++ для интеграции в протокол маршрутизации LEACH.
• Результаты: Предложенный протокол MKPP-LEACH формирует более сбалансированные кластеры, значительно сокращает общее энергопотребление сети и продлевает её жизненный цикл.
• Недостатки: Исследование носит централизованный характер. Не рассматривает распределённые сценарии и конфиденциальность данных (например, местоположение узлов).
• Перспективы: Демонстрирует эффективность k-means++ для оптимизации структуры сети. В сценариях HFL можно разработать протокол, в котором каждый клиент локально запускает приватную версию алгоритма для формирования локальных кандидатов, которые затем агрегируются на сервере для построения глобальной энергоэффективной кластерной структуры.

29. A Hybrid K-Means++ and Particle Swarm Optimization Approach for Enhanced Document Clustering (Hassan et al., 2025)

• Что сделано: Предложен гибридный подход, сочетающий K-Means++ для интеллектуальной инициализации центроидов и алгоритм роя частиц (PSO) для глобальной оптимизации кластеризации документов.
• Результаты: Гибридный метод K-Means++ PSO продемонстрировал превосходство над базовыми методами на нескольких наборах данных.
• Недостатки: Подход может столкнуться с проблемами масштабируемости на очень больших наборах данных из-за вычислительной сложности PSO.
• Перспективы: В контексте FL гибридный подход может быть адаптирован для сценариев горизонтальной FL: клиенты локально выполняют K-Means++, центроиды безопасно агрегируются на сервере и используются для инициализации глобальной кластеризации с помощью PSO.

30. Accelerating the k-Means++ Algorithm by Using Geometric Information (Rodríguez Corominas et al., 2025)

• Что сделано: Предложены два точных метода ускорения алгоритма инициализации k-means++ с использованием геометрической информации (неравенство треугольника и фильтр по нормам).
• Результаты: Ускоренные версии значительно сокращают количество просматриваемых точек и вычисляемых расстояний по сравнению со стандартным k-means++, сохраняя все теоретические гарантии.
• Недостатки: Практическое ускорение по времени не всегда соответствует теоретическому из-за ухудшения локальности доступа к данным. Алгоритмы не предназначены для распределённых сценариев «из коробки».
• Перспективы: Эти ускоренные точные методы могут быть адаптированы для клиентской стороны в горизонтальном FL (HFL). Клиенты могли бы локально выполнять ускоренный k-means++ для выбора репрезентативных кандидатов, которые затем агрегируются на сервере, что снижает коммуникационные издержки.

Теоретические ограничения и "плохие" случаи

24. A bad instance for k-means++ (Brunsch, Röglin, 2012)

• Что сделано: Даётся окончательный ответ на вопрос о вероятностных свойствах алгоритма k-means++. Авторы показывают, что на специально построенных инстанциях алгоритм ведёт себя плохо не только в среднем, но и с очень высокой вероятностью.
• Результаты: Строгое доказательство того, что существуют инстанции, на которых k-means++ достигает аппроксимации не лучше (2/3 — ε)·log k с вероятностью, экспоненциально близкой к 1.
• Недостатки: Основное ограничение — искусственность и высокая размерность построенных инстанций (размерность Θ(k²)), что мало соответствует практическим сценариям.
• Перспективы: Устанавливает фундаментальные пределы эффективности стандартного k-means++. Для исследования важна как предостережение: в распределённых сценариях (HFL/VFL) слепое доверие к k-means++ может быть опасно. Перспективой является исследование влияния шума DP или несбалансированности данных в федеративной среде на вероятность попадания в такие «плохие» сценарии.

Список дополнительных источников

1. A comparative study of K-Means, K-Means++ and Fuzzy C-Means clustering algorithms // 2017 3rd International Conference on Computational Intelligence & Communication Technology (CICT). – Ghaziabad, India, 2017. – P. 1–5. – DOI: 10.1109/CIACT.2017.7977272.

2. Robust k-means++ / A. Deshpande, P. Kacham, R. Pratap // Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI). – 2020. – Vol. 124. – P. 799–808.

3. Improving Scalable K-Means++ / M. A. [автор] // Algorithms. – 2021. – Vol. 14, iss. 1. – Art. 6. – DOI: 10.3390/a14010006.

4. Scalable K-Means++ / B. Bahmani, B. Moseley, A. Vattani, R. Kumar, S. Vassilvitskii. – 2012. – arXiv: 1203.6402.

5. A novel defect prediction method for web pages using k-means++ / M. M. Ozturk, U. Cavusoglu, A. Zengin // Expert Systems with Applications. – 2015. – Vol. 42, iss. 19. – P. 6496–6506.

6. Parallelization of the K-Means++ Clustering Algorithm / S. Daoudi, C. M. A. Zouaoui, M. C. El-Mezouar, N. Taleb // Ingénierie des Systèmes d'Information. – 2021. – Vol. 26, no. 1. – P. 59–66.

7. A Better k-means++ Algorithm via Local Search / S. Lattanzi, C. Sohler // Proceedings of the 36th International Conference on Machine Learning (ICML). – 2019. – Vol. 97. – P. 3662–3671.

8. CAPKM++2.0: An upgraded version of the collaborative annealing power -means++ clustering algorithm // Knowledge-Based Systems. – 2023. – Vol. 259. – Art. 110067.

9. Noisy k-means++ Revisited / C. Grunau, A. A. Özüdoğru, V. Rozhoň. – 2023. – arXiv: 2307.13685.

10. Notice of Violation of IEEE Publication Principles: K-means versus k-means ++ clustering technique / S. Agarwal, S. Yadav, K. Singh // 2012 World Congress on Information and Communication Technologies (WICT). – 2012. – P. 368–373.

11. Efficient k-means++ with random projection / J. Y. K. Chan, A. P. Leung // 2017 International Conference on Fuzzy Theory and Its Applications (iFUZZY). – 2017. – P. 22–27.

12. A bad instance for k-means++ / T. Brunsch, H. Röglin // Theoretical Computer Science. – 2013. – Vol. 493. – P. 7–18.

13. Beyond k-Means++: Towards better cluster exploration with geometrical information / Y. Ping, H. Li, B. Hao, C. Guo, B. Wang // Pattern Recognition. – 2024. – Vol. 145. – Art. 109886.

14. Nyström Method with Kernel K-means++ Samples as Landmarks / D. Oglic, T. Gärtner // Proceedings of the 34th International Conference on Machine Learning (ICML). – 2017. – Vol. 70. – P. 2652–2660.

15. Hybrid model based on K-means++ algorithm, optimal similar day approach, and long short-term memory neural network for short-term photovoltaic power prediction / R. Bai, Y. Shi, M. Yue, X. Du // Energy Reports. – 2023. – Vol. 9, Suppl. 8. – P. 456–466.

16. A novel hybrid method of lithology identification based on k-means++ algorithm and fuzzy decision tree / Q. Ren, H. Zhang, D. Zhang, X. Zhao, L. Yan, J. Rui // Journal of Petroleum Science and Engineering. – 2022. – Vol. 208, Part D. – Art. 109516.

17. Local Search k-means++ with Foresight / T. Conrads, L. Drexler, J. Könen, D. R. Schmidt, M. Schmidt. – 2024. – arXiv: 2406.02739.

18. An indoor thermal comfort model for group thermal comfort prediction based on K-means++ algorithm / Y. Liu, X. Li, C. Sun, Q. Dong, Q. Yin, B. Yan // Energy and Buildings. – 2024. – Vol. 310. – Art. 114080.

19. Пространственная классификация гиперспектральных изображений с использованием метода кластеризации k-means++ / Е. А. Зимичев, Н. Л. Казанский, П. Г. Серафимович // Компьютерная оптика. – 2022. – Т. 46, № 2. – С. 274–281.

20. PERFORMANCE COMPARISON OF K-MEANS, PARALLEL K-MEANS AND K-MEANS++ / R. Aliguliyev, S. F. Tahirzada // RT&A. – 2025. – №SI 7 (83).

21. Novel Automated K-means++ Algorithm for Financial Data Sets / G. Du, X. Li, L. Zhang, L. Liu, C. Zhao // Mathematical Problems in Engineering. – 2021. – Vol. 2021. – Art. ID 5521119.

22. k-variates++: more pluses in the k-means++ / R. Nock, R. Canyasse, R. Boreli, F. Nielsen // Proceedings of The 33rd International Conference on Machine Learning (ICML). – 2016. – Vol. 48. – P. 145–154.

23. SOM++: Integration of Self-Organizing Map and K-Means++ Algorithms // Advances in Knowledge Discovery and Data Mining: PAKDD 2013. – 2013. – P. 235–246.

24. Noisy, Greedy and Not So Greedy k-means++ / A. Bhattacharya, J. Eube, H. Röglin, M. Schmidt. – 2019. – arXiv: 1912.00653.

25. K-Means++ Clustering Algorithm in Categorization of Glass Cultural Relics / J. Meng, Z. Yu, Y. Cai, X. Wang // Applied Sciences. – 2023. – Vol. 13, iss. 8. – Art. 4736.

26. A Bad Instance for k-means++ // Theory and Applications of Models of Computation: TAMC 2011 / ed. by M. Ogihara, J. Tarui. – Berlin, Heidelberg : Springer, 2011. – P. 325–336.

27. A K-means++ Based User Classification Method for Social E-commerce / H. Cui, S. Niu, K. Li, C. Shi, S. Shao, Z. Gao // Intelligent Automation & Soft Computing. – 2021. – Vol. 28, no. 1. – P. 277–291.

28. Nyström Method with Kernel K-means++ Samples as Landmarks / D. Oglic, T. Gärtner // Proceedings of the 34th International Conference on Machine Learning (ICML 2017). – 2017. – P. 2652–2660.

29. Parallelization of the K-Means++ Clustering Algorithm / S. Daoudi, C. M. A. Zouaoui, M. C. El-Mezouar, N. Taleb // Intelligent Systems and Applications. – 2021. – P. 59–66.

30. A Hybrid K-Means++ and Particle Swarm Optimization Approach for Enhanced Document Clustering / E. Hassan et al. // IEEE Access. – 2025. – Vol. 13. – P. 48818–48840.

Нужна работа по этой теме? Получите консультацию за 10 минут! Telegram: @Diplomit Телефон/WhatsApp/MAX: +7 (987) 915-99-32, Email: admin@diplom-it.ru

Оформите заказ онлайн: Заказать ВКР