Анализ разделимости ядер кластеров на основе графов с использованием нового индекса CSI
Боковая панель статьи
Основное содержимое статьи
Аннотация
В данной статье представлен новый внутренний индекс валидности кластеризации, названный Индексом Разделимости Ядер (Core Separation Index, CSI), предназначенный для улучшения качества и автоматизации плотностных алгоритмов кластеризации на основе графов. Предложенный индекс оценивает качество выделения ядер кластеров путем измерения соотношения между внутренней связностью (cohesion) каждого ядра и его сопряженностью (coupling) с другими ядрами. Мы представляем теоретическое обоснование индекса CSI, включая теорему о его свойствах и строгое доказательство. Индекс интегрирован в алгоритм GDVA, основанный на анализе вариации плотности графа, что позволяет автоматически определять оптимальные параметры кластеризации. Проведено всестороннее экспериментальное сравнение индекса CSI с существующими индексами, такими как DVI, Silhouette и Dunn, на пяти синтетических наборах данных различной структуры. Результаты, оцененные с помощью внешних метрик Adjusted Rand Index (ARI) и Normalized Mutual Information (NMI), показывают, что CSI обеспечивает лучшее качество кластеризации (в среднем NMI 0.7460) и значительно превосходит другие индексы по скорости вычислений (в среднем 0.17с). Также продемонстрирована высокая корреляция предложенного индекса с внешними метриками качества, что подтверждает его надежность для оценки и выбора оптимальной структуры кластеров.
Информация о статье
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Библиографические ссылки
Jain, A.K. "Data clustering: 50 years beyond K-means." Pattern recognition letters 31.8 (2010): 651-666.
Schaeffer, S.E. "Graph clustering." Computer science review 1.1 (2007): 27-64.
Von Luxburg, U. "A tutorial on spectral clustering." Statistics and computing 17.4 (2007): 395-416.
Ester, M., et al. "A density-based algorithm for discovering clusters in large spatial databases with noise." Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. 1996.
Le, T.V. "Clustering by graph density variation analysis (GDVA) with density-based cluster validity indices (DVI)." Dissertation, Rutgers University, 2011.
Arbelaitz, O., et al. "A comprehensive survey of cluster validity indices." Pattern Recognition 46.1 (2013): 243-258.
Rousseeuw, P.J. "Silhouettes: a graphical aid to the interpretation and validation of cluster analysis." Journal of computational and applied mathematics 20 (1987): 53-65.
Dunn, J.C. "A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters." Journal of cybernetics 3.3 (1973): 32-57.
Davies, D.L., & Bouldin, D.W. "A cluster separation measure." IEEE transactions on pattern analysis and machine intelligence 1 (1979): 224-227.
Ng, A.Y., Jordan, M.I., & Weiss, Y. "On spectral clustering: Analysis and an algorithm." Advances in neural information processing systems 14 (2001).
Shi, J., & Malik, J. "Normalized cuts and image segmentation." IEEE Transactions on pattern Analysis and machine intelligence 22.8 (2000): 888-905.
Gower, J.C., & Ross, G.J. "Minimum spanning trees and single linkage cluster analysis." Journal of the Royal Statistical Society: Series C (Applied Statistics) 18.1 (1969): 54-64.
Van Dongen, S. "Graph clustering by flow simulation." PhD thesis, University of Utrecht, 2000.
Frey, B.J., & Dueck, D. "Clustering by passing messages between data points." science 315.5814 (2007): 972-976.
Ankerst, M., et al. "OPTICS: ordering points to identify the clustering structure." ACM Sigmod record. Vol. 28. No. 2. 1999.
Campello, R.J., Moulavi, D., & Sander, J. "Density-based clustering based on hierarchical density estimates." Pacific-Asia conference on knowledge discovery and data mining. Springer, Berlin, Heidelberg, 2013.
Vendramin, L., Campello, R. J., & Hruschka, E.R. "On the comparison of relative clustering validity criteria." Proceedings of the SIAM International Conference on Data Mining. 2009.
Давронов, Р. (2025). Графовый алгоритм кластеризации на основе вариации плотности. Международный Журнал Теоретических и Прикладных Вопросов Цифровых Технологий, 8(2), 58–64. https://doi.org/10.62132/ijdt.v8i2.264.