Convex Decomposition Based Cluster Labeling Method for Support Vector Clustering |
| |
Authors: | Yuan Ping Ying-Jie Tian Ya-Jian Zhou Yi-Xian Yang |
| |
Affiliation: | (1) Information Security Center, Beijing University of Posts and Telecommunications, Beijing, 100876, China;(2) Graduate University of Chinese Academy of Sciences, Beijing, 100190, China;(3) Department of Computer Science and Technology, Xuchang University, Xuchang, 461000, China |
| |
Abstract: | Support vector clustering (SVC) is an important boundary-based clustering algorithm in multiple applications for its capability
of handling arbitrary cluster shapes. However, SVC’s popularity is degraded by its highly intensive time complexity and poor
label performance. To overcome such problems, we present a novel efficient and robust convex decomposition based cluster labeling
(CDCL) method based on the topological property of dataset. The CDCL decomposes the implicit cluster into convex hulls and
each one is comprised by a subset of support vectors (SVs). According to a robust algorithm applied in the nearest neighboring
convex hulls, the adjacency matrix of convex hulls is built up for finding the connected components; and the remaining data
points would be assigned the label of the nearest convex hull appropriately. The approach's validation is guaranteed by geometric
proofs. Time complexity analysis and comparative experiments suggest that CDCL improves both the efficiency and clustering
quality significantly. |
| |
Keywords: | support vector clustering convex decomposition convex hull geometric |
本文献已被 CNKI SpringerLink 等数据库收录! |
|