Solution of clusterization problem by graph optimization methods
The rapid growth in the volume of processed information that takes place nowadays determines the urgency of the development of methods for reducing the dimension of computational problems. One of the approaches to reducing the dimensionality of data is their clustering, i.e., uniting into maximally...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Kazan Federal University
2019-09-01
|
| Series: | Учёные записки Казанского университета. Серия Физико-математические науки |
| Subjects: | |
| Online Access: | https://kpfu.ru/uz-eng-phm-2019-3-8.html |
| _version_ | 1797963610625933312 |
|---|---|
| author | I.V. Konnov O.A. Kashina E.I. Gilmanova |
| author_facet | I.V. Konnov O.A. Kashina E.I. Gilmanova |
| author_sort | I.V. Konnov |
| collection | DOAJ |
| description | The rapid growth in the volume of processed information that takes place nowadays determines the urgency of the development of methods for reducing the dimension of computational problems. One of the approaches to reducing the dimensionality of data is their clustering, i.e., uniting into maximally homogeneous groups. At the same time, it is desirable that representatives of different clusters should be as much as possible unlike each other. Along with the dimension reduction, clustering procedures have an independent value. For example, we know the market segmentation problem in economics, the feature typologization problem in sociology, faces diagnostics in geology, etc.
Despite the large number of known clusterization methods, the development and study of new ones remain relevant. The reason is that there is no algorithm that would surpass all the rest by all criteria (speed, insensitivity to clusters’ size and shape, number of input parameters, etc.).
In this paper, we propose a clustering algorithm based on the notions of the graph theory (namely, the maximum flow (the minimum cut) theorem) and compare the results obtained by it and by four other algorithms that belong to various classes of clusterization techniques. |
| first_indexed | 2024-04-11T01:32:04Z |
| format | Article |
| id | doaj.art-f0873a00cc9f46539211a7e11ecf06e5 |
| institution | Directory Open Access Journal |
| issn | 2541-7746 2500-2198 |
| language | English |
| last_indexed | 2024-04-11T01:32:04Z |
| publishDate | 2019-09-01 |
| publisher | Kazan Federal University |
| record_format | Article |
| series | Учёные записки Казанского университета. Серия Физико-математические науки |
| spelling | doaj.art-f0873a00cc9f46539211a7e11ecf06e52023-01-03T09:43:50ZengKazan Federal UniversityУчёные записки Казанского университета. Серия Физико-математические науки2541-77462500-21982019-09-01161342343710.26907/2541-7746.2019.3.423-437Solution of clusterization problem by graph optimization methodsI.V. Konnov0O.A. Kashina1E.I. Gilmanova2Kazan Federal University, Kazan, 420008 RussiaKazan Federal University, Kazan, 420008 RussiaKazan Federal University, Kazan, 420008 RussiaThe rapid growth in the volume of processed information that takes place nowadays determines the urgency of the development of methods for reducing the dimension of computational problems. One of the approaches to reducing the dimensionality of data is their clustering, i.e., uniting into maximally homogeneous groups. At the same time, it is desirable that representatives of different clusters should be as much as possible unlike each other. Along with the dimension reduction, clustering procedures have an independent value. For example, we know the market segmentation problem in economics, the feature typologization problem in sociology, faces diagnostics in geology, etc. Despite the large number of known clusterization methods, the development and study of new ones remain relevant. The reason is that there is no algorithm that would surpass all the rest by all criteria (speed, insensitivity to clusters’ size and shape, number of input parameters, etc.). In this paper, we propose a clustering algorithm based on the notions of the graph theory (namely, the maximum flow (the minimum cut) theorem) and compare the results obtained by it and by four other algorithms that belong to various classes of clusterization techniques.https://kpfu.ru/uz-eng-phm-2019-3-8.htmlclusteringmaximal flowminimal cutford–fulkerson theoremlabeling methodk-meanshierarchical clusterizationward’s proceduredbscan methodmaxflow algorithm |
| spellingShingle | I.V. Konnov O.A. Kashina E.I. Gilmanova Solution of clusterization problem by graph optimization methods Учёные записки Казанского университета. Серия Физико-математические науки clustering maximal flow minimal cut ford–fulkerson theorem labeling method k-means hierarchical clusterization ward’s procedure dbscan method maxflow algorithm |
| title | Solution of clusterization problem by graph optimization methods |
| title_full | Solution of clusterization problem by graph optimization methods |
| title_fullStr | Solution of clusterization problem by graph optimization methods |
| title_full_unstemmed | Solution of clusterization problem by graph optimization methods |
| title_short | Solution of clusterization problem by graph optimization methods |
| title_sort | solution of clusterization problem by graph optimization methods |
| topic | clustering maximal flow minimal cut ford–fulkerson theorem labeling method k-means hierarchical clusterization ward’s procedure dbscan method maxflow algorithm |
| url | https://kpfu.ru/uz-eng-phm-2019-3-8.html |
| work_keys_str_mv | AT ivkonnov solutionofclusterizationproblembygraphoptimizationmethods AT oakashina solutionofclusterizationproblembygraphoptimizationmethods AT eigilmanova solutionofclusterizationproblembygraphoptimizationmethods |