出版社：The Japanese Society for Artificial Intelligence
摘要：This paper proposes a constrained clustering method based on an iterative data division by a constrained graph cutting approach. Since our proposed constrained graph cut problem is formalized by semidefinite programming, must-link constraints can be naturally imported to the problem. Though the solution matrix obtained by solving the problem does not directly reflect cluster members, we introduce an efficient heuristic algorithm to produce clusters without any complex procedures such as matrix decomposition. In the experiments, we compared our method with other state-of-the art and well-known clustering techniques on the UCI repository and CLUTO datasets. Our method showed outperformed or comparable results compared with other traditional ones on more than half of the datasets. We also compared the calculation cost. Though our method tends to consume more time to calculate, the total cost is at most double compared with other SDP based method.
