Journal
SYMMETRY-BASEL
Volume 11, Issue 3, Pages -Publisher
MDPI
DOI: 10.3390/sym11030338
Keywords
clustering; constrained clustering; balanced size constraints; mean squared error; linear program
Categories
Funding
- National Natural Science Foundation of China [61402205]
- China Postdoctoral Science Foundation [2015M571688]
- Postgraduate Research AMP
- Practice Innovation Program of Jiangsu Province [KYCX18_2258]
Ask authors/readers for more resources
Clustering is to group data so that the observations in the same group are more similar to each other than to those in other groups. k-means is a popular clustering algorithm in data mining. Its objective is to optimize the mean squared error (MSE). The traditional k-means algorithm is not suitable for applications where the sizes of clusters need to be balanced. Given n observations, our objective is to optimize the MSE under the constraint that the observations need to be evenly divided into k clusters. In this paper, we propose an iterative method for the task of clustering with balanced size constraints. Each iteration can be split into two steps, namely an assignment step and an update step. In the assignment step, the data are evenly assigned to each cluster. The balanced assignment task here is formulated as an integer linear program (ILP), and we prove that the constraint matrix of this ILP is totally unimodular. Thus the ILP is relaxed as a linear program (LP) which can be efficiently solved with the simplex algorithm. In the update step, the new centers are updated as the centroids of the observations in the clusters. Assuming that there are n observations and the algorithm needs m iterations to converge, we show that the average time complexity of the proposed algorithm is O(mn1.65)-O(mn1.70). Experimental results indicate that, comparing with state-of-the-art methods, the proposed algorithm is efficient in deriving more accurate clustering.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available