Графовый алгоритм кластеризации на основе вариации плотности
Боковая панель статьи
Основное содержимое статьи
Аннотация
Кластеризация является одной из основных задач анализа данных, направленной на группировку объектов в однородные подмножества без заранее заданных меток. В данной статье рассматривается метод кластеризации на графах. В нем используется концепция итеративного удаления узлов с низкой плотностью, чтобы обнаруживать «ядерные» узлы (core pixels) и определять структуру кластеров. Мы описываем теоретические основы метода, приводим детали реализации и анализируем полученные результаты на синтетических наборах данных (в том числе созданных при помощи библиотеки scikit-learn). Кроме того, сравниваем предложенный алгоритм с другими известными методами кластеризации, используя метрику ARI (Adjusted Rand Index). Эксперименты показывают, что данный подход эффективно выявляет структуры разной формы и плотности, а также демонстрирует конкурентоспособные результаты по сравнению с классическими методами.
Информация о статье
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Библиографические ссылки
Xu, R., & Wunsch, D. (2005). Survey of clustering algorithms. IEEE Transactions on Neural Net-works, 16(3), 645–678. https://doi.org/10.1109/TNN.2005.845141.
Lloyd, S. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129–137. https://doi.org/10.1109/TIT.1982.1056489.
Arthur, D., & Vassilvitskii, S. (2007). k-means++: the advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms (SODA), 1027–1035. https://dl.acm.org/doi/10.5555/1283383.1283494.
Theodoridis, S., & Koutroumbas, K. (2009). Pattern Recognition (4th ed.). Academic Press. https://doi.org/10.1016/B978-1-59749-272-0.X0001-8.
Ester, M., Kriegel, H. P., Sander, J., & Xu, X. (1996). A density-based algorithm for discovering clus-ters in large spatial databases with noise. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, 226–231. http://www.aaai.org/Papers/KDD/1996/KDD96-037.pdf.
Campello, R. J. G. B., Moulavi, D., & Sander, J. (2013). Density-based clustering based on hierar-chical density estimates. In Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), 160–172. https://doi.org/10.1007/978-3-642-37456-4_14.
Shi, J., & Malik, J. (2000). Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905. https://doi.org/10.1109/34.868688.
Jain, A.K. (2010). Data clustering: 50 years beyond K-means. Pattern Recognition Letters, 31(8), 651–666. https://doi.org/10.1016/j.patrec.2009.09.011.
Clauset, A., Newman, M. E. J., & Moore, C. (2004). Finding community structure in very large net-works. Physical Review E, 70(6), 066111. https://doi.org/10.1103/PhysRevE.70.066111.
Duan, L., Xu, L., Liu, Y., & Lee, J. (2015). Strong density-based clustering. In Springer Lecture Notes in Computer Science (LNCS), 9166, 144–156. https://doi.org/10.1007/978-3-319-13461-4_8.
Thang V. Le, Сasimir A Kulikowski, Ilya B. Muсhnik, Сoring Method for Сlustering a Graph / 19th International Сonferenсe on Pattern Reсognition (IСPR 2008). http://dx.doi.org/10.1109/IСPR.2008. 4760954.