УЛУЧШЕНИЕ АДАПТИВНОГО МЕТОДА КЛАСТЕРИЗАЦИИ K-СРЕДНИХ С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ САМООБУЧЕНИЯ

​IMPROVEMENT OF THE ADAPTIVE K-MEANS CLUSTERING METHOD USING SELF-LEARNING TECHNIQUES

Ekaterina Zhuikova

Graduate student, The Admiral Makarov State University of Maritime and Inland Shipping,

Russia, Saint-Petersburg

АННОТАЦИЯ

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

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

ABSTRACT

This article examines the improvement of the adaptive K-means method using self-learning techniques.

The study focuses on evaluating the effectiveness of this method in the context of processing various datasets, including both structured and unstructured data. The impact of choosing initial parameters and distance metrics on clustering results is analyzed, as well as their sensitivity to data changes.

The article proposes methods for dynamically changing the number of clusters and parameters depending on the data structure, which allows optimizing performance in various analytical tasks. The presented results provide valuable insights for the scientific community and practitioners involved in data analysis, contributing to the improvement of data-driven decision-making processes.

Ключевые слова: Кластеризация данных, адаптивный метод -средних, пороговая кластеризация, анализ данных, метрики оценки качества

Keywords: Data clustering, adaptive K-means method, self-learning techniques, data analysis, quality evaluation metrics

Введение

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

С ростом объемов данных и их разнообразия задача кластеризации становится всё более сложной, особенно в контексте обработки неструктурированных данных, требующих масштабируемых и эффективных решений [6]. К тому же выбор начальных параметров, таких как количество кластеров в алгоритме -средних, может значительно повлиять на результаты кластеризации, делая точность и адаптивность методов актуальными исследовательскими вопросами.

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

Улучшенный адаптивный алгоритм кластеризации -средних

Адаптивный метод кластеризации -средних начинается с инициализации, в ходе которой из выборки данных случайным образом выделяются  элементов [3], служащих начальными центрами для формирования кластеров. В предложенном улучшении алгоритм -средних дополнен механизмами самообучения, позволяющими динамически изменять количество кластеров и параметры в зависимости от структуры данных. Это достигается путём итеративного изменения количества кластеров и оценки качества кластеров с использованием различных метрик, таких как индекс силуэта [8], Davies-Bouldin Index (DBI) [9] и Calinski-Harabasz Index (CH) [9], что обеспечивает более точное и гибкое распределение данных по кластерам.

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

В большинстве случаев достаточной оказывается евклидова метрика, особенно при работе с спектральными данными, представленными в форме n-мерных векторов. Однако для расчета расстояния между двумя элементами  и  выражение принимает вид () [3]:

                                                               (1)

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

                                                                 (2)

где  — определяющий тип метрики, который при значении 2 возвращает евклидово расстояние, а при 1 — манхэттенское.

С использованием адаптивного подхода можно динамически определить оптимальное количество кластеров на основе структуры данных. Методы, такие как метод локтя [9] или индекс силуэта [8], позволяют оценивать внутрикластерное расстояние и различия между кластерами при разных значениях . Для метода локтя используется следующая формула для расчёта внутрикластерной суммы квадратов  () [9]:

                                                           (3)

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

Основная идея итеративного изменения количества кластеров заключается в следующем: алгоритм начинает с заданного начального количества кластеров . После каждой итерации оценивается качество кластеризации с использованием метрик, таких как индекс силуэта [8], Davies-Bouldin Index (DBI) [9] или Calinski-Harabasz Index (CH) [9]. Если качество кластеризации ниже заданного порога, количество кластеров увеличивается или уменьшается в зависимости от текущих результатов. Процесс продолжается до достижения оптимального качества кластеризации.

Для повышения эффективности алгоритма используются механизмы автоматического определения начальных центроидов и других параметров на основе анализа текущих данных. Это включает использование методов машинного обучения для предсказания оптимального числа кластеров и их параметров [6].

Процесс работы алгоритма после выбора :

1. Инициализация:
2. Алгоритм начинается с заданного начального количества кластеров .
3. Случайным образом выбираются K начальных центроидов из данных.
2. Итеративное изменение количества кластеров:
3. После каждой итерации оценивается качество кластеризации с использованием метрик, таких как индекс силуэта [8], Davies-Bouldin Index (DBI) [9] или Calinski-Harabasz Index (CH) [9].
4. Если качество кластеризации ниже заданного порога, количество кластеров увеличивается или уменьшается в зависимости от оценки текущих результатов.
5. Процесс продолжается до тех пор, пока не будет достигнуто оптимальное качество кластеризации.
3. Вычисление расстояний между кластерами:
4. Алгоритм сохраняет расстояния в двумерном массиве в виде треугольной матрицы.
4. Определение минимального расстояния  между кластерами:
5. Используется для определения ближайших пар кластеров.
5. Присвоение элементов к кластерам:
6. Каждый элемент  анализируется на предмет принадлежности к одному из кластеров:
7. Если расстояние до кластера равно , элемент сразу присваивается этому кластеру.
8. Если расстояние меньше , элемент присваивается ближайшему кластеру, и происходит пересчёт центроида.
9. Если  меньше расстояния до ближайшего кластера, происходит объединение двух ближайших кластеров, и элемент добавляется в новый, объединённый кластер.
6. Повторение процесса:
7. Процесс повторяется до тех пор, пока все элементы не будут сгруппированы.
8. В улучшенной версии алгоритм динамически изменяет количество кластеров и параметры в зависимости от структуры данных.
7. Оценка качества кластеров:
8. После каждой итерации оценивается качество кластеров с использованием метрик, таких как индекс силуэта, DBI и CH.
9. Метрики помогают определить, следует ли увеличивать или уменьшать количество кластеров.
8. Автоматическое определение параметров:
9. Включение механизмов автоматического определения начальных центроидов и других параметров на основе анализа текущих данных.
10. Использование методов машинного обучения для предсказания оптимального числа кластеров и их параметров.

Визуализация кластеризации данных

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

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

На рисунке 1 представлены трёхмерные точечные графики с центроидами для различных типов кластеров.

Рисунок 1. Графики кластеризации для каждого из типа данных

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

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

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

Заключение

Введение методов самообучения в адаптивный алгоритм K-средних позволяет динамически изменять количество кластеров и параметры в зависимости от структуры данных в реальном времени.

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

Использование метрик оценки качества кластеров, таких как индекс силуэта [8], Davies-Bouldin Index [9] и Calinski-Harabasz Index [9], помогает оптимизировать количество кластеров и другие параметры для достижения наилучших результатов.

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

Список литературы:

1. Балджа, А., Шин, Д., Канг, У. (2018). Введение в методы кластеризации для анализа больших данных. Springer.
2. Бахем, О., Лучич, М., Краузе, А. (2016). Практическая кластеризация методом k-средних для анализа данных большого масштаба. arXiv preprint arXiv:1602.06813.
3. Бхатия, С. К. Адаптивный метод кластеризации K-средних / Санджив К. Бхатия, кафедра математики и компьютерных наук, Университет Миссури – Сент-Луис, Сент-Луис, Миссури.
4. Кауфман, Л., Руссеув, П. Дж. (2009). Поиск групп в данных: введение в кластерный анализ (Том 344). Джон Уайли и сыновья.
5. МакКуин, Дж. (1967). Некоторые методы классификации и анализа многомерных наблюдений. В материалах пятого симпозиума Беркли по математической статистике и теории вероятностей (Том 1, № 14, стр. 281-297).
6. Педрегоса, Ф., Вароксо, Г., Грамфорт, А., Мишель, В., Тирион, Б., Гризель, О., Вандерплас, Дж. (2011). Scikit-learn: машинное обучение на Python. Journal of machine learning research, 12, 2825-2830.
7. Рокач, Л., Маймон, О. (2005). Методы кластеризации. В Data mining and knowledge discovery handbook (стр. 321-352). Спрингер, Бостон, Массачусетс.
8. Руссеув, П. Дж. (1987). Силуэты: графический инструмент для интерпретации и валидации кластерного анализа. Journal of computational and applied mathematics, 20, 53-65.
9. Тибширани, Р., Уолтер, Г., Хасти, Т. (2001). Оценка количества кластеров в наборе данных с помощью статистики разрыва. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 63(2), 411-423.
10. Чжу, С., Голдберг, М. (2009). Введение в кластеризацию больших и многомерных данных. Springer Science & Business Media.