Matrix programming improves multi-class data clustering success
Normalized Cuts and Data Clustering via Matrix Fractional Programming
Machine Learning
Summary
Grouping data into clusters is a common way to analyze information, but some clustering problems are tricky because they involve dividing data into multiple groups at once. The authors developed a new mathematical tool called a multidimensional quadratic transform that better handles these multi-group clustering tasks. This method can solve complicated grouping problems by turning them into simpler matching problems, which can be solved more easily. Their experiments show this approach can work well for grouping data and segmenting images.
What this means in practice
- •For data engineers: Cluster large datasets more efficiently when dividing data into multiple categories at once for analytics pipelines.
- •For computer vision teams: Segment images into multiple meaningful parts using improved clustering algorithms for clearer object identification.
Authors
Yannan Chen, Beichen Huang, Licheng Zhao, Chris Ding, Kaiming Shen
Abstract
The normalized cut (NCut) problem is a fundamental one in the area of data clustering. Despite its fractional structure, the NCut problem is seldom considered from a fractional programming (FP) perspective in the existing literature. The main reason is that the conventional FP method is inadequate for this problem case: the classical Dinkelbach's transform can only handle a single ratio and hence is limited to the two-class clustering, whereas the multi-class clustering involves multiple ratio terms. This work proposes a novel so-called multidimensional quadratic transform that is capable of dealing with the multi-ratio case; it recasts the NCut problem into a bipartite matching problem---which can be immediately solved by linear search. Furthermore, we explore the connection between the proposed FP method and the minorization-maximization (MM) theory, and in turn characterize the convergence behavior of our algorithm. Finally, we conduct experiments to numerically demonstrate the advantages of the proposed FP-based algorithm in a variety of data clustering and image segmentation tasks.