An Optimization Model for Fuzzy Binary Clustering
Xianwen Ren, Yong Wang, Jiguang Wang, Yu Xia · 2010
Abstract Clustering has been a powerful tool to visualize complex data with extensive applica-tions in many disciplines. In this paper, we propose an optimization-based solution to the fuzzy binary clustering problem by grouping all the data points into two clusters. Our model are based on two assumptions. One is that the similar objects are labeled similarly, which is known as the “cluster assumption ” in semi-supervised learning. The other assumption is that the most dissimilar two objects belong to different clusters. The problem is formulated as a quadratic programming model and can seek the optimal fuzzy labels for the objects. Our model can be solved efficiently by designing a fast algorithm. In addition, it can be reformulated as a linear programming solved efficiently if the similarity matrix is sparse. Furthermore, this model can then be extended to explore the hard-binary-clustering and multiple-clustering problems by a few modifications. Experiments on both simulated and real data sets demonstrate the effectiveness of our method.