МЕТОД РАСЧЕТА ЧИСЛА КЛАСТЕРОВ ДЛЯ АЛГОРИТМА K-MEANS

Авторы

  • В.В. Фролов Харьковский национальный университет имени В.Н. Каразина
  • С.Е. Слипченко НТУ «ХПИ»
  • О.Ю. Приходько БГТУ им. В.Г. Шухова

DOI:

https://doi.org/10.18413/2687-0932-2020-47-1-213-225

Ключевые слова:

кластерный анализ, кластер, устойчивость кластеризации, разбиение множества, критерий качества разбиения, k-means, центр кластера, центроид

Аннотация

В статье предложен метод оценки оптимального числа кластеров для алгоритма k-средних. Метод обеспечивает расчет оптимального количества кластеров для разделения исходного множества на основе анализа нескольких критериев оценки. Основным критерием является динамика перераспределения объектов в кластерах при переходе от одного разбиения к другому. Оценка динамики проводится при расчете нормы матрицы перехода. В качестве дополнительного критерия используется оценка изменения потенциальной энергии объектов внутри кластеров одного и того же разбиения. Вспомогательный критерий определяет количество кластеров в соответствии с характерными точками графиков основного и дополнительного критериев. Суть метода заключается в наборе правил использования основных, дополнительных и вспомогательных критериев. Последовательность выполнения правил реализована в виде функции системы Matlab. Сравнительный анализ показывает, что метод комплексной оценки позволяет повысить точность определения оптимального количества кластеров на 40 %.

Биографии авторов

В.В. Фролов, Харьковский национальный университет имени В.Н. Каразина

доктор технических наук, доцент, профессор кафедры теоретической и
прикладной информатики Харьковского национального университета
имени В. Н. Каразина

С.Е. Слипченко, НТУ «ХПИ»

старший преподаватель кафедры технологии машиностроения и
металлорежущих станков Национального Технического Университета
«Харьковский политехнический Институт»

О.Ю. Приходько, БГТУ им. В.Г. Шухова

кандидат технических наук, доцент, доцент кафедры электроэнергетики и
автоматики БГТУ им. В.Г. Шухова, г. Белгород

Библиографические ссылки

Бондарев В.А., Лисица А.В., Меньшутина Н.В. 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.


Просмотров аннотации: 177

Опубликован

2020-09-09

Как цитировать

Фролов, В., Слипченко, С., & Приходько, О. (2020). МЕТОД РАСЧЕТА ЧИСЛА КЛАСТЕРОВ ДЛЯ АЛГОРИТМА K-MEANS. Экономика. Информатика, 47(1), 213-225. https://doi.org/10.18413/2687-0932-2020-47-1-213-225

Выпуск

Раздел

ИНФОКОММУНИКАЦИОННЫЕ ТЕХНОЛОГИИ

Наиболее читаемые статьи этого автора (авторов)