A strongly balanced constrained clustering (SBCC) problem requires that clusters satisfy the equality constraints on cluster weights while it is also required to ensure connectivity of each cluster in practical scenarios. However, existing methods usually transform the strong balancing constraints into inequality constraints and obtain an approximate solution to the SBCC problem, resulting in the failure to guarantee the accuracy of the solution and cluster’s connectivity. In this paper, we propose a balance adjustment method, by combining a shelved-retrieved strategy and an adjacent allocation method to get the high quality solution satisfying the connectivity of each cluster. To verify the validity and rationality of the proposed method, we conducted experiments on three synthetic datasets and in two real-world scenarios. The results show that our method can generate the clusters fulfilling the constraints in the SBCC, which demonstrates that our method outperforms existing methods. Therefore, the balance adjustment method is capable of solving the SBCC problem and provides high quality solutions, which allows for on-demand resource allocation.
| [1] |
Aurenhammer F, Hoffmann F, Aronov B. Minkowski-type theorems and least-squares clustering. Algorithmica, 1998, 2016176.
|
| [2] |
Balzer, M.: Capacity-constrained voronoi diagrams in continuous spaces. In: 2009 Sixth International Symposium on Voronoi Diagrams, pp. 79–88. IEEE (2009)
|
| [3] |
Borgwardt S, Brieden A, Gritzmann P. Constrained minimum-k-star clustering and its application to the consolidation of farmland. Oper. Res. Int. J., 2011, 111117.
|
| [4] |
Borgwardt S, Brieden A, Gritzmann P. Geometric clustering for the consolidation of farmland and woodland. Math. Intell., 2014, 36: 37-44.
|
| [5] |
Brieden A, Gritzmann P. A quadratic optimization model for the consolidation of farmland by means of lend-lease agreements. Operations Research Proceedings 2003, 2004Springer324331.
|
| [6] |
Brieden A, Gritzmann P. On optimal weighted balanced clusterings: gravity bodies and power diagrams. SIAM J. Discret. Math., 2012, 262415434.
|
| [7] |
Brieden A, Gritzmann P, Klemm F. Constrained clustering via diagrams: a unified theory and its application to electoral district design. Eur. J. Oper. Res., 2017, 26311834.
|
| [8] |
Galvao Lauro C, Novaes Antonio GN, Souza De Cursi JE, Souza João C. A multiplicatively-weighted Voronoi diagram approach to logistics districting. Comput. Oper. Res., 2006, 33193114.
|
| [9] |
Ganganath, N., Cheng, CT., Chi, KT.: Data clustering with cluster size constraints using a modified k-means algorithm. In: 2014 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, pp. 158–161. IEEE (2014)
|
| [10] |
Hu CW, Li H, Qutub AA. Shrinkage clustering: a fast and size-constrained clustering algorithm for biomedical applications. BMC Bioinform., 2018, 191111.
|
| [11] |
Xin S-Q, Lévy B, Chen Z, Chu L, Yaohui Yu, Changhe T, Wang W. Centroidal power diagrams with capacity constraints: computation, applications, and extension. ACM Trans. Graph. (TOG), 2016, 356112.
|
| [12] |
Yang K, Shekhar AH, Oliver D, Shekhar S. Capacity-constrained network-Voronoi diagram. IEEE Trans. Knowl. Data Eng., 2015, 271129192932.
|
| [13] |
Zhao Q, Xu M, Fränti P. Sum-of-squares based cluster validity index and significance analysis. Adaptive and Natural Computing Algorithms: 9th International Conference, ICANNGA 2009, Kuopio, Finland, April 23–25, 2009, Revised Selected Papers 9, 2009Springer313322.
|
| [14] |
Zhu S, Wang D, Li T. Data clustering with size constraints. Knowl. Based Syst., 2010, 238883889.
|
Rights & permissions
School of Mathematical Sciences, University of Science and Technology of China and Springer-Verlag GmbH Germany, part of Springer Nature
PDF
