Constrained Clustering Problems: New Optimization Algorithms

Constrained clustering problems are often considered in massive data clustering and analysis. They are used in modeling various issues in anomaly detection, classification, systems' misbehaviour, etc. In this paper, we focus on generalizing the K-Means clustering approach when involving linear constraints on the clusters' size. Indeed, to avoid local optimum clustering solutions which consists in empty clusters or clusters with few points, we propose linear integer programming approaches based on relaxation and rounding techniques to cope with scalability issues. We show the efficiency of the new proposed approach, and assess its performance using five data-sets from different domains.