Balanced Clustering via Exclusive Lasso: A Pragmatic Approach

Authors

  • Zhihui Li Beijing Etrol Technologies Co., Ltd.
  • Feiping Nie Centre for OPTical Imagery Analysis and Learning, Northwestern Polytechnical University
  • Xiaojun Chang School of Computer Science, Carnegie Mellon University
  • Zhigang Ma School of Computer Science, Carnegie Mellon University
  • Yi Yang Centre for Artificial Intelligence, University of Technology Sydney

Keywords:

Balanced Clustering, k-means, Min-Cut

Abstract

Clustering is an effective technique in data mining to generate groups that are the matter of interest.Among various clustering approaches, the family of k-means algorithms and min-cut algorithms gain most popularity due to their simplicity and efficacy. The classical k-means algorithm partitions a number of data points into several subsets by iteratively updating the clustering centers and the associated data points. By contrast, a weighted undirected graph is constructed in min-cut algorithms which partition the vertices of the graph into two sets. However, existing clustering algorithms tend to cluster minority of data points into a subset, which shall be avoided when the target dataset is balanced. To achieve more accurate clustering for balanced dataset, we propose to leverage exclusive lasso on k-means and min-cut to regulate the balance degree of the clustering results. By optimizing our objective functions that build atop the exclusive lasso, we can make the clustering result as much balanced as possible. Extensive experiments on several large-scale datasets validate the advantage of the proposed algorithms compared to the state-of-the-art clustering algorithms.

Downloads

Published

2018-04-29

How to Cite

Li, Z., Nie, F., Chang, X., Ma, Z., & Yang, Y. (2018). Balanced Clustering via Exclusive Lasso: A Pragmatic Approach. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/11702