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

IMPROVING THE STABILITY OF SOCIAL NETWORK DATA CLUSTERING BASED ON MODIFIED ALGORITHMS

Gruzkov Timur Dmitrievich

Master's student, Department of Data Analysis and Programming Technologies, Institute of Computational Mathematics and Information Technologies, Kazan (Volga Region) Federal University,

Russia, Kazan

Vakhitov Galim Zaribzyanovich

Scientific supervisor, Candidate of Sciences, Associate Professor, Department of Data Analysis and Programming Technologies, Institute of Computational Mathematics and Information Technologies, Kazan (Volga Region) Federal University,

Russia, Kazan

АННОТАЦИЯ

В статье рассматривается задача повышения устойчивости кластеризации данных социальной сети. В качестве базовой схемы используются модифицированный k-means с центрами-представителями, DBSCAN и метод Уорда для контроля структуры данных. Предлагаются два авторских метода: АОУР для выбора конфигурации по критерию устойчивости в худшем случае и ЛОКУС для локальной коррекции пограничных объектов. Эксперимент на выборке из 8000 сообществ показал, что выбор параметров только по внутренним индексам качества недостаточен: наиболее устойчивой оказалась конфигурация, не совпадающая с конфигурацией с максимальным силуэтом. Применение ЛОКУС дополнительно повысило разделимость и воспроизводимость результата.

ABSTRACT

The article considers the problem of improving the stability of clustering social network data. A modified k-means algorithm with representative centers, DBSCAN and Ward's method are used as the basic scheme for controlling the data structure. Two original methods are proposed: AOUR for selecting a configuration according to the worst-case stability criterion and LOCUS for local correction of boundary objects. An experiment on a sample of 8,000 communities showed that selecting parameters only by internal quality indices is insufficient: the most stable configuration did not coincide with the configuration with the maximum silhouette. The use of LOCUS additionally increased the separability and reproducibility of the result.

Ключевые слова: кластеризация; социальные сети; устойчивость разбиения; k-means; DBSCAN; метод Уорда; ARI.

Keywords: clustering; social networks; partition stability; k-means; DBSCAN; Ward's method; ARI.

Введение

Социальные сети формируют большие массивы данных, включающие метаданные сообществ, показатели активности и текстовые характеристики. В прикладных задачах мониторинга такие данные целесообразно предварительно структурировать, чтобы сократить объем дальнейшего анализа. Одним из наиболее удобных инструментов такой первичной обработки является кластерный анализ [1; 2].

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

Цель статьи — показать, что повышение качества кластеризации в этой задаче достигается за счет совместного использования устойчивого выбора параметров и локальной корректировки пограничных объектов. Для этого рассматриваются базовые алгоритмы k-means и DBSCAN, а также предлагаются два авторских метода, ориентированные на устойчивость и интерпретируемость результата.

Материалы и методы

В эксперименте использована выборка из 8000 сообществ социальной сети, описанных 22 числовыми признаками. Текстовые и категориальные поля в евклидову метрику напрямую не включались и использовались только для интерпретации. Пропуски в числовых столбцах заполнялись медианой, после чего сравнивались две схемы нормирования: z-стандартизация и робастное нормирование по медиане и межквартильному размаху.

Основным алгоритмом выбран модифицированный k-means. В нем центр кластера трактуется как реальный объект, ближайший к среднему вектору своего кластера. Такая схема сохраняет интерпретируемость результата и делает кластеры удобными для последующего анализа. Для уменьшения зависимости от старта использовались инициализация k-means++ [3] и множественные перезапуски.

В качестве альтернативного подхода рассматривался DBSCAN [4], позволяющий выделять плотные области и шумовые объекты. Метод Уорда [5] применялся для контроля структуры данных и проверки разумности выбора числа кластеров. Качество оценивалось по коэффициенту силуэта [6], индексу Дэвиса–Болдина [7] и показателям устойчивости по скорректированному индексу Рэнда [8].

Для практической системы важно, что выбранные метрики оценивают разные стороны разбиения. Силуэт отражает соотношение внутрикластерной компактности и межкластерной разделимости, индекс Дэвиса–Болдина показывает близость наиболее похожих кластеров, а ARI позволяет количественно сравнивать разбиения, полученные при независимых запусках и ресэмплинге. Совместное использование этих показателей позволяет избежать ситуации, когда конфигурация выглядит удачной по одной метрике, но оказывается нестабильной в серии повторных вычислений.

Авторские модификации

Первый авторский метод — АОУР, адверсариальная оптимизация устойчивости разбиения. Для каждой конфигурации алгоритма строится базовое разбиение, после чего генерируются допустимые возмущения данных: бутстрэп-подвыборки, маскирование части признаков, робастный шум и изменение временного окна. На каждом варианте выполняется повторная кластеризация, а устойчивость измеряется по скорректированному индексу Рэнда. Интегральный показатель ASI определяется как минимальная согласованность по набору возмущений. Тем самым конфигурация выбирается не по лучшему разовому значению внутренней метрики, а по устойчивости в неблагоприятном случае.

Второй авторский метод — ЛОКУС, локальное уточнение кластеров устойчивыми соседствами. После базовой кластеризации для каждого объекта анализируются ближайшие соседи и расстояния до центров-представителей. Если объект имеет слабую локальную поддержку или его текущая метка противоречит соседнему окружению, выполняется локальная коррекция. Метод затрагивает только пограничные случаи и не требует полного перерасчета всего разбиения.

Совместное применение АОУР и ЛОКУС образует двухэтапную схему: сначала выбирается устойчивая конфигурация, затем корректируются только спорные объекты. Такая организация особенно удобна для мультиагентной системы, в которой процедуры подбора параметров и постобработки могут выполняться независимо.

Эксперимент и обсуждение результатов

Сравнение четырех конфигураций k-means при k = 3 показало, что лучшую разделимость по внутренним индексам дает робастное нормирование. Однако по критерию устойчивости ASI лучшей оказалась конфигурация Z-score + weighted. Это означает, что максимальный силуэт и максимальная воспроизводимость не совпадают. Итоги сравнения приведены в таблице 1.

Проверка устойчивости к инициализации показала, что переход от случайного выбора стартовых центров к k-means++ резко уменьшает разброс результата, а множественные перезапуски с n_init = 10 делают решение практически воспроизводимым. При выборе числа кластеров максимум коэффициента силуэта достигался при k = 2, однако для прикладной интерпретации был выбран вариант k = 3. Дендрограмма Уорда также указывала на наличие двух-трех крупных ветвей, что подтверждает такой выбор.

На подвыборке из 2000 объектов был дополнительно протестирован DBSCAN после понижения размерности до восьми главных компонент. Метод выделил 4 кластера и около 25,8 % шумовых точек. По внутренним метрикам он уступил k-means, однако оказался полезным как инструмент обнаружения аномальных и слабо типизированных объектов.

Применение АОУР позволило выбрать конфигурацию с максимальным ASI = 0,89. Далее на этой конфигурации был использован ЛОКУС. Постобработка изменила метки только у 6,4 % объектов, но при этом коэффициент силуэта вырос с 0,260 до 0,289, индекс Дэвиса–Болдина снизился с 1,475 до 1,361, а устойчивость на бутстрэп-подвыборках увеличилась с 0,951 до 0,960. Следовательно, локальная коррекция пограничных объектов дает заметный эффект без радикального изменения общей структуры кластеров. Значения ASI для сравниваемых конфигураций представлены на рисунке 1.

Таблица 1.

Сравнение конфигураций k-means по качеству и устойчивости

Рисунок 1. Значения ASI для сравниваемых конфигураций k-means

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

Заключение

В статье показано, что для данных социальной сети качество кластеризации следует оценивать не только по компактности и разделимости, но и по устойчивости к изменению входа. Предложенный метод АОУР позволяет выбирать параметры по критерию устойчивости в худшем случае, а метод ЛОКУС повышает согласованность границ кластеров за счет локальной коррекции пограничных объектов.

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

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

1. Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. М.: Финансы и статистика, 1989. 607 с.
2. Тан П.-Н., Штайнбах М., Кумар В. Введение в интеллектуальный анализ данных. М.: Вильямс, 2006. 814 с.
3. Arthur D., Vassilvitskii S. k-means++: The advantages of careful seeding // Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. 2007. P. 1027–1035.
4. Ester M., Kriegel H.-P., Sander J., Xu X. A density-based algorithm for discovering clusters in large spatial databases with noise // Proceedings of KDD-96. 1996. P. 226–231.
5. Ward J. H. Hierarchical grouping to optimize an objective function // Journal of the American Statistical Association. 1963. Vol. 58, № 301. P. 236–244.
6. Rousseeuw P. J. Silhouettes: a graphical aid to the interpretation and validation of cluster analysis // Journal of Computational and Applied Mathematics. 1987. Vol. 20. P. 53–65.
7. Davies D. L., Bouldin D. W. A cluster separation measure // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1979. Vol. PAMI-1, № 2. P. 224–227.
8. Hubert L., Arabie P. Comparing partitions // Journal of Classification. 1985. Vol. 2, № 1. P. 193–218.