Algebraic method speeds up constrained k-means clustering tasks
An Algebraic Approach to Constrained K-means Clustering
Machine Learning
Summary
Clustering groups objects based on their features, but sometimes extra rules say which objects must or must not be grouped together. Existing methods that handle these rules can be slow or fail to find a valid grouping. The authors propose a new way using algebra to simplify these rules before grouping, making the process faster and able to check if a valid grouping is even possible. Their approach works especially well when there are few groups and rules, keeping quality high while saving time.
What this means in practice
- •For data engineers: Improve efficiency and reliability of clustering data sets when constraints specify which items must or must not be grouped together.
- •For marketing analysts: Segment customers into meaningful groups under specific business rules about customer relationships more quickly and reliably.
Authors
Hiroki Oohori, Kentaro Fukushima, Michio Yamamoto
Abstract
Clustering is typically performed using only object features, although additional information about relationships between objects may be available and can be incorporated through constraints. Among these, pairwise constraints require two objects to belong to the same cluster or to different clusters. Several extensions of the k-means algorithm accommodate such constraints, but they sometimes fail to find a feasible assignment or incur high computational cost. Motivated by these limitations, we propose an algebraic approach to k-means clustering with pairwise constraints. The algorithm simplifies the constraints using Gröbner bases before optimization, improving the efficiency of cluster assignment. It can also detect whether the constraint set has a feasible assignment before optimization. Comparative experiments with existing algorithms showed that the proposed algorithm achieved comparable or better clustering quality at a lower computational cost, particularly when the numbers of constraints and clusters were small.