CLUSTERS NUMBER CALCULATING METHOD FOR THE K-MEANS ALGORITHM
DOI:
https://doi.org/10.18413/2687-0932-2020-47-1-213-225Keywords:
cluster analysis, cluster, clustering stability, partition of a set, partition quality criterion, k-means, cluster center, centroidAbstract
In article the method of estimate of optimum number of clusters for an algorithm k-means is offered. The method provides calculation of optimum number of clusters for partitioning an source set on the basis of the analysis of several evaluation criteria. The main criterion is dynamics of redistribution of objects in clusters upon transition from one partitioning towards another. Assessment of dynamics is carried out at calculation of norm of matrix of transition. As an additional criterion, an estimate of the change in the potential energy of objects inside clusters of the same partition is used. The auxiliary criterion determines number of clusters according to characteristic points of plots of the main and additional criteria. The essence of a method consists in a rules set of use of the main, additional and auxiliary criteria. The sequence of execution of rules is implemented by way of function of the Matlab system. Contrastive analysis shows that the method of integrated assessment allows to increase the accuracy of determination of optimum number of clusters by 40 %.
Downloads
References
Бондарев В.А., Лисица А.В., Меньшутина Н.В. 2007. Применение правил остановки
кластерного анализа в случае слабой и сильной иерархии кластеров на примере белковых структур. Успехи в химии и химической технологии. Т. 21. 1 (69): 105–109. URL: https://cyberleninka.ru/article/n/primenenie-pravil-ostanovki-klasternogo-analiza-v-sluchae-slaboy-i-silnoyierarhii-klasterov-na-primere-belkovyh-struktur (дата обращения: 23.10.2019).
Елизаров С.И., Куприянов М.С. 2009. Проблема определения количества кластеров при
использовании методов разбиения. Изв. вузов. Приборостроение. 52 (12): 3–8. URL:
https://cyberleninka.ru/article/n/problema-opredeleniya-kolichestva-klasterov-pri-ispolzovanii-metodovrazbieniya (дата обращения: 22.10.2019).
Кольцов С.Н. 2017. Термодинамический подход к проблеме определения числа кластеров
на основе тематического моделирования. Письма в журнал технической физики. 43 (12): 90–95. URL: https://elibrary.ru/item.asp?id=29359329 (дата обращения: 22.10.2019).
Литвиненко В.И. 2009. Кластерный анализ данных на основе модифицированной
иммунной сети. УСиМ. (1): 54–61. URL: http://usim.irtc.org.ua/arch/2009/1/8.pdf (дата обращения: 30.11.2019).
Ложкинс А., Буре В.М., 2016. Вероятностный подход к определению локально-
оптимального числа кластеров. Вестник СПбГУ. Серия 10. Прикладная математика. Информатика. Процессы управления. (1): 28–37. URL: https://cyberleninka.ru /article/n/veroyatnostnyy-podhod-kopredeleniyu-lokalno-optimalnogo-chisla-klasterov (дата обращения: 22.10.2019).
Московкин В.М., Казимиру Эринелту. 2017. Матричная кластеризация как кластеризация
матриц одинаковой размерности. Научные ведомости БелГУ. Серия: Экономика. Информатика. 23 (272): 123–127. URL: https://elibrary.ru/item.asp?id=32265026 (дата обращения: 22.10.2019).
Миркин Б.Г. 2011. Методы кластер-анализа для поддержки принятия решений: обзор. М.,
Изд. дом Национального исследовательского университета «Высшая школа экономики», 88. URL: https://www.hse.ru/data/2011/05/19/1213868030/WP7_2011_03f.pdf (дата обращения: 25.10.2019).
Никитин Н.Н. 1990. Курс теоретической механики. 5-е изд., перераб. и доп. М., Высшая
школа, 607.
Селуков Д.А., Шилов В.С. 2016. Нахождение оптимального числа кластеров «методом
локтя». Инновационные технологии: теория, инструменты, практика. 1: 107–111. URL:
https://elibrary.ru/item.asp?id=28990633 (дата обращения: 25.10.2019).
Фролов В.В. 2019. Проектный расчет размерных цепей на основе имитационного
моделирования. Вестник витебского государственного технологического университета. 2 (37): 76–88. URL: https://elibrary.ru/item.asp?id=41653699 (дата обращения: 16.01.2020).
Шалымов Д.С. 2009. Рандомизированный метод определения количества кластеров на
множестве данных. Научно-технический вестник Санкт-Петербургского государственного
университета информационных технологий, механики и оптики. 5 (63): 111–116. URL:
https://cyberleninka.ru/article/n/randomizirovannyy-metod-opredeleniya-kolichestva-klasterov-na-mnozhestvedannyh. (дата обращения: 22.10.2019).
Шокина М.О. 2017. Применение алгоритма k-means++ для кластеризации
последовательностей с неизвестным количеством кластеров. Новые информационные технологии в автоматизированных системах. (20). URL: https://cyberleninka.ru /article/n/primenenie-algoritma-k-meansdlya-klasterizatsii-posledovatelnostey-s-neizvestnym-kolichestvom-klasterov (дата обращения: 22.10.2019).
Яцкив И., Гусарова Л. 2003. Методы определения количества кластеров при классификации без обучения. Transport and Telecommunication. 4 (1): 23–28. URL: http://www.tsi.lv/ sites/default/files/editor/science/Research_journals/Tr_Tel/2003/V1/yatskiv_gousarova.pdf (дата обращения: 25.10.2019).
MathWorks. 2019. Calinski-Harabasz criterion clustering evaluation object. URL: https://www.mathworks.com/help/stats/clustering.evaluation.calinskiharabaszevaluation-class.html (accessed 25 October 2019).
Fränti P., Virmajoki O. 2006. Iterative shrinking method for clustering problems. Pattern Recognition. 39 (5): 761–765.
Fränti P., Virmajoki O., Hautamäki V. 2006. Fast agglomerative clustering using a k-nearest neighbor graph. IEEE Trans. on Pattern Analysis and Machine Intelligence. 28 (11): 1875–1881.
Rezaei M., Fränti P. 2016. Set-matching measures for external cluster validity. IEEE Trans. on Knowledge and Data Engineering. 28 (8): 2173–2186.
Kärkkäinen I., Fränti P. 2007. Gradual model generator for single-pass clustering. Pattern Recognition. 40(3): 784–795.
Calinski T., Harabasz J. 1974. A dendrite method for cluster analysis. Communications in Statistics. 3(1): 1–27.
Davies D.L., Bouldin D.W. 1979. A Cluster Separation Measure. IEEE Transactions on Pattern Analysis and Machine Intelligence. PAMI-1 (2): 224–227.
Tibshirani R., Walther G., Hastie T. 2001. Estimating the number of clusters in a data set via the gap statistic. Journal of the Royal Statistical Society: Series B. 63 (2): 411–423.
Rouseeuw P.J. 1987. Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. Journal of Computational and Applied Mathematics. 20 (1): 53–65.
Abstract views: 990
Share
Published
How to Cite
Issue
Section
Copyright (c) 2020 ECONOMICS. INFORMATION TECHNOLOGIES
This work is licensed under a Creative Commons Attribution 4.0 International License.
