Решение задачи кластеризации методами оптимизации на графах

И.В. Коннов, О.А. Кашина, Э.И. Гильманова
Казанский (Приволжский) федеральный университет, г. Казань, 420008, Россия

Полный текст PDF
DOI: 10.26907/2541-7746.2019.3.423-437

Для цитирования: Коннов И.В., Кашина О.А., Гильманова Э.И. Решение задачи кластеризации методами оптимизации на графах // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2019. – Т. 161, кн. 3. – С. 423–437. – doi: 10.26907/2541-7746.2019.3.423-437.

For citation: Konnov I.V., Kashina O.A., Gilmanova E.I. Solution of clusterization problem by graph optimization methods. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2019, vol. 161, no. 3, pp. 423–437. doi: 10.26907/2541-7746.2019.3.423-437. (In Russian)

Аннотация

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

 Несмотря на большое число известных методов решения задачи кластеризации, проблема разработки и исследования новых алгоритмов не теряет актуальности. Дело в том, что не существует алгоритма, который превосходил бы все остальные по всем критериям (быстродействие, нечувствительнсть к размерам и форме кластеров, количество параметров и т. д.).

 В статье представлен алгоритм кластеризации, основанный на применении теории графов (теоремы о максимальном потоке и минимальном разрезе) и проведён сравнительный анализ его с четырьмя другими алгоритмами – представителями различных классов методов кластеризации.

Ключевые слова: кластеризация, максимальный поток, минимальный разрез, теорема Форда – Фалкерсона, метод расстановки пометок, метод k-средних, иерархическая кластеризация, метод Варда, метод DBSCAN, алгоритм MaxFlow

Благодарности. Работа выполнена за счет средств субсидии, выделенной Казанскому федеральному университету для выполнения государственного задания в сфере научной деятельности, проект № 1.12878.2018/12.1.

Работа первого и второго авторов выполнена при финансовой поддержке Российского фонда фундаментальных исследований, проект № 16-01-00109a.

Работа первого автора выполнена в рамках государственного задания Минобрнауки России, номер задания 1.460.2016/1.4.

Литература

1.  Xu D., Tian Y.  A comprehensive survey of clustering algorithms // Ann. Data Sci. – 2015. – V. 2, No 2. – P. 165–193. – doi: 10.1007/s40745-015-0040-1.

2.  Sharan R., Shamir R. CLICK: A clustering algorithm with applications to gene expression analysis // Proc. Int. Conf. Intell. Syst. Mol. Biol. – AAAI Press, 2000. – P. 307–316.

3.  Форд Л., Фалкерсон Д.  Потоки в сетях. – М.: Наука, 1966. – 276 с.

4. Ford L.R. Jr., Fulkerson D.R., Maximal flow through a network // Can. J. Math. – 1956. – V. 8. – P. 399–404. – doi: 10.4153/CJM-1956-045-5.

5. Dinitz Y. Dinitz' algorithm: The original version and Even's version // Goldreich O., Rosenberg A.L., Selman A.L. (Eds.) Theoretical Computer Science. Lecture Notes in Computer Science, V. 3895. – Berlin, Heidelberg: Springer, 2006. – P. 218–240.

6. Edmonds J., Karp R.M. Theoretical improvements in algorithmic efficiency for network flow problems // J. Assoc. Comput. Mach. – 1972. – V. 19, No 2. – P. 248–264.

7. Адельсон-Вельский Г.М., Диниц Е.А., Карзанов А.В. Потоковые алгоритмы. – М.: Наука, 1975. – 119 с.

8. Сивоголовко Е. Методы оценки качества четкой кластеризации // Компьютерные инструменты в образовании. – 2011. – Вып. 4. – С. 14–31.

9. Steinhaus H. Sur la division des corps materiels en parties // Bull. Acad. Polon. Sci., Cl. III. – 1956. – V. IV, No 12. – P. 801–804.

10. Lloyd S. Least square quantization in PCM // Trans. Inf. Theory. – 1982. – V. IT-28, No 2. – P. 129–137.

11. MacQueen J. Some methods for classification and analysis of multivariate observations // Proc. 5th Berkeley Symp. on Mathematical Statistics and Probability. – 1967. – P. 281–297.

12. Johnson S. Hierarchical clustering schemes // Psychometrika. – 1967. – V. 32, No 3. – P. 241–254. – doi: 10.1007/BF02289588.

13. Ward J.H. Hierarchical grouping to optimize an objective function // J. Am. Stat. Assoc. – 1963. – V. 58, No 301. – P. 236–244. – doi: 10.1080/01621459.1963.10500845.

14. Ester M., Kriegel H.-P., Sander J., Xu X. A density-based algorithm for discovering clusters in large spatial databases with noise // Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining (KDD-96) – AAAI Press, 1996. – P. 226–231.

15. Franti P., Sieranoja S. Clustering basic benchmark. – URL: http://cs.joensuu.fi/sipu/ datasets/.

Поступила в редакцию

17.10.18

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

Казанский (Приволжский) федеральный университет

ул. Кремлевская, д. 18, г. Казань, 420008, Россия

E-mail:  konn-igor@yandex.ru

Кашина Ольга Андреевна, кандидат физико-математических наук, доцент кафедры анализа данных и исследования операций

Казанский (Приволжский) федеральный университет

ул. Кремлевская, д. 18, г. Казань, 420008, Россия

E-mail:  olga.kashina@mail.ru

Гильманова Элина Ильдаровна, студент Института вычислительной математики и информационных технологий

Казанский (Приволжский) федеральный университет

ул. Кремлевская, д. 18, г. Казань, 420008, Россия

E-mail:  elgilm21@gmail.com

Контент доступен под лицензией Creative Commons Attribution 4.0 License.