2015 | OriginalPaper | Chapter
Fast Multiway Maximum Margin Clustering Based on Genetic Algorithm via the NystrÖm Method
Authors : Ying Kang, Dong Zhang, Bo Yu, Xiaoyan Gu, Weiping Wang, Dan Meng
Published in: Web-Age Information Management
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Motivated by theories of support vector machine, the concept of maximum margin has been extended to the applications in the unsupervised scenario, developing a novel clustering method
─
maximum margin clustering (MMC). MMC shows an outstanding performance in computational accuracy, which is superior to other traditional clustering methods. But the integer programming of labels of data instances induces MMC to be a hard non-convex optimization problem to settle. Currently, many techniques like semi-definite programming, cutting plane etc. are embedded in MMC to tackle this problem. However, the increasing time complexity and premature convergence of these methods limit the analytic capability of MMC for large datasets. This paper proposes a fast multiway maximum margin clustering method based on genetic algorithm (GAM3C). GAM3C initially adopts the NystrÖm method to generate a low-rank approximate kernel matrix in the dual form of MMC, reducing the scale of original problem and speeding up the subsequent analyzing process; and then makes use of the solution-space alternation of genetic algorithm to compute the non-convex optimization of MMC explicitly, obtaining the multiway clustering results simultaneously. Experimental results on real world datasets reflect that GAM3C outperforms the state-of-the-art maximum margin clustering algorithms in terms of computational accuracy and running time.