We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 27 Issue 2
March  2012
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Yuan Ping, Ying-Jie Tian, Ya-Jian Zhou, Yi-Xian Yang. Convex Decomposition Based Cluster Labeling Method for Support Vector Clustering[J]. Journal of Computer Science and Technology, 2012, (2): 428-442. DOI: 10.1007/s11390-012-1232-1
Citation: Yuan Ping, Ying-Jie Tian, Ya-Jian Zhou, Yi-Xian Yang. Convex Decomposition Based Cluster Labeling Method for Support Vector Clustering[J]. Journal of Computer Science and Technology, 2012, (2): 428-442. DOI: 10.1007/s11390-012-1232-1
shu

Convex Decomposition Based Cluster Labeling Method for Support Vector Clustering

  • 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

Funds: This work was supported by the National Natural Science Foundation of China under Grant No. 60972077 and partially under Grant No. 70921061, the National Science and Technology Major Program under Grant No. 2010ZX03003-003-01, the Natural Science Foundation of Beijing under Grant No. 9092009, and the Fundamental Research Funds for the Central Universities under Grant No. 2011RC0212.
More Information
  • Received Date: July 14, 2011
  • Revised Date: November 20, 2011
  • Published Date: March 04, 2012
    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.
    • FullText(HTML)
    • References (41)
  • [1]
    Xu R, Wunsch D C. Hierarchical clustering. In Clustering,Hoboken: John Wiley&Sons, 2008.
    [2]
    Ben-Hur A, Horn D, Siegelmann H T, Vapnik V N. Supportvector clustering. Journal of Machine Learning Research,2001, 2: 125-137.
    [3]
    Schölkopf B, Platt J C, Shawe-Taylor J C, Smola AJ, Williamson R C. Estimating the support of a high-dimensional distribution. Neural Computation, 2001, 13(7):1443-1472.
    [4]
    Tax D M J, Duin R P W. Support vector domain description.Pattern Recognition Letters, 1999, 20(11-13): 1191-1199.
    [5]
    Burges C J C. A tutorial on support vector machines forpattern recognition. Data Mining and Knowledge Discovery,1998, 2(2): 121-167.
    [6]
    Yang J H, Estivill-Castro V, Chalup S K. Support vector clus-tering through proximity graph modelling. In Proc. the 9thInternational Conference on Neural Information Processing(ICONIP 2002), Orchid Country Club, Singapore, Nov. 18-22, 2002, pp.898-903.
    [7]
    Lee J, Lee D. An improved cluster labeling method for sup-port vector clustering. IEEE Transactions on Pattern Analy-sis and Machine Intelligence, 2005, 27(3): 461-464.
    [8]
    Lee J, Lee D. Dynamic characterization of cluster structuresfor robust and inductive support vector clustering. IEEETransactions on Pattern Analysis and Machine Intelligence,2006, 28(11): 1869-1874.
    [9]
    Lee D, Lee J. Equilibrium-based support vector machine forsemisupervised classification. IEEE Transactions on NeuralNetworks, 2007, 18(2): 578-583.
    [10]
    Lee S-H, Daniels K M. Cone cluster labeling for support vec-tor clustering. In Proc. the 6th SIAM Conference on DataMining, Bethesda, Maryland, Apr. 20-22, 2006, pp.484-488.
    [11]
    Varma C M B S, Asharaf S, Murty M N. Rough core vec-tor clustering. In Proc. the 2nd International Conferenceon Pattern Recognition and Machine Intelligence, Kolkata,India, Dec. 18-22, 2007, pp.304-310.
    [12]
    Hsieh T W, Taur J S, Tao C W, Kung S Y. A kernel-basedcore growing clustering method. International Journal of In-telligent Systems, 2009, 24(4): 441-458.
    [13]
    Ling P, Zhou C G, Zhou X. Improved support vector clus-tering. Eng. Applicat. Artificial Intelligence, 2010, 23(4):552-559.
    [14]
    Ping Y, Zhou Y J, Yang Y X. A novel scheme for acceleratingsupport vector clustering. Computing and Infomatics, 2012,31(2): in press.
    [15]
    Jung J H, Kim N, Lee J. Dynamic pattern denoising methodusing multi-basin system with kernels. Pattern Recognition,2011, 44(8): 1698-1707.
    [16]
    Vapnik V. The Nature of Statistical Learning Theory. NewYork: Springer-Verlag, 1995.
    [17]
    Jung K H, Lee D, Lee J. Fast support-based clustering methodfor large-scale problems. Pattern Recognition, 2010, 43(5):1975-1983.
    [18]
    Lee D, Lee J. Dynamic dissimilarity measure for support-based clustering. IEEE Transactions on Knowledge and DataEngineering, 2010, 22(6): 900-905.
    [19]
    Ben-Hur A, Horn D, Siegelmann H T, Vapnik V. A supportvector cluster method. In Proc. the 15th International Con-ference on Pattern Recognition, Barcelona, Spain, Sep. 3-7,2000, pp.724-727.
    [20]
    Estivill-Castro V, Lee I. AMOEBA: Hierarchical clusteringbased on spatial proximity using Delaunay diagram. In Proc.the 9th Int. Symposium on Spatial Data Handling, Beijing,China, Aug. 10-12, 2000, pp.7a.26-7a.41.
    [21]
    Estivill-Castro V, Lee I, Murray A T. Criteria on proximitygraphs for boundary extraction and spatial clustering. InProc. the 5th Pacific-Asia Conference on Knowledge Dis-covery and Data Mining (PAKDD2001), Hong Kong, China,Apr. 16-18, 2001, pp.348-357.
    [22]
    Ban T, Abe S. Spatially chunking support vector clustering al-gorithm. In Proc. International Joint Conference on NeuralNetworks, Budapest, Hungary, July 25-29, 2004, pp.413-418.
    [23]
    Puma-Villanueva W J, Bezerra G B, Lima C A M, Zuben FJ V. Improving support vector clustering with ensembles. InProc. International Joint Conference on Neural Networks,Montreal, Quebec, Canada, Jul. 31-Aug. 4, 2005, pp.13-15.
    [24]
    Chiang J H, Hao P Y. A new kernel-based fuzzy clusteringapproach: Support vector clustering with cell growing. IEEETransactions on Fuzzy Systems, 2003, 11(4): 518-527.
    [25]
    Wang F, Zhao B, Zhang C S. Linear time maximum marginclustering. IEEE Transactions on Neural Networks, 2010,21(2): 319-332.
    [26]
    Peng J M, Mukherjee L, Singh V, Schuurmans D, Xu L L. Anefficient algorithm for maximal margin clustering. Journal ofGlobal Optimization, 2011, 2: 1-15. doi: 10.1007/s10898-011-9691-4.
    [27]
    Lee S H, Daniels K. Gaussian kernel width selection and fastcluster labeling for support vector clustering. University ofMassachusetts, Lowell, Technical Report No. 2005-009, 2005.
    [28]
    Lee C H, Yang H C. Construction of supervised and unsuper-vised learning systems for multilingual text categorization.Expert Systems with Applications, 2009, 36(2): 2400-2410.
    [29]
    Lee D, Jung K H, Lee J. Constructing sparse kernel machinesusing attractors. IEEE Transactions on Neural Networks,2009, 20(4): 721-729.
    [30]
    Hao P Y, Chiang J H, Tu Y K. Hierarchically SVM classi-fication based on support vector clustering method and itsapplication to document categorization. Expert Systems withApplications, 2007, 33(3): 627-635.
    [31]
    Hocking T D, Joulin A, Bach F, Vert J P. Clusterpath: Analgorithm for clustering using convex fusion penalties. InProc. the 28th International Conference on Machine Learn-ing (ICML), Bellevue, WA, USA, Jun. 28-Jul. 2, 2011, pp.1-8.
    [32]
    Shamir O, Tishby N. Stability and model selection in k-meansclustering. Machine Learning, 2010, 80(2-3): 213-243.
    [33]
    Lee S H, Daniels K. Gaussian kernel width generator for sup-port vector clustering. In Proc. International Conferenceon Bioinformatics and Its Applications, Fort Lauderdale,Florida, USA, Dec. 16-19, 2004, pp.151-162.
    [34]
    Boyd S, Vandenberghe L. Convex Optimization. Cambridge,7th edition, New York: Cambridge University Press, 2009.
    [35]
    Li Y H, Maguire L. Selecting critical patterns based on localgeometrical and statistical information. IEEE Transactionson Pattern Analysis and Machine Intelligence, 2011, 33(6):1189-1201.
    [36]
    Kpotufe S, von Luxburg U. Pruning nearest neighbor clustertrees. In Proc. the 28th International Conference on Ma-chine Learning (ICML 2011), Bellevue, USA, Jun. 28-Jul. 2,2011, pp.225-232.
    [37]
    Kim H C, Lee J. Clustering based on gaussian processes. Neu-ral Computation, 2007, 19(11): 3088-3107.
    [38]
    Camastra F, Verri A. A novel kernel method for clustering.IEEE Transactions on Pattern Analysis and Machine Intel-ligence, 2005, 27(5): 801-805.
    [39]
    Frank A, Asuncion A. UCI machine learning repository.http://archive.ics.uci.edu/ml, 2010.
    [40]
    Hubert L, Arabie P. Comparing partitions. Journal of Clas-sification, 1985, 2(1): 193-218.
    [41]
    Wu M, Scholkopf B. A local learning approach for clustering.In Proc. the 20th Annual Conference on Advances Neural In-formation Processing Systems (NIPS 2007), Vancouver, B.C.,Canada, Dec. 4-7, 2006, pp.1529-1536.
    • Relative Articles

  • Related Articles

    [1]Xin Li, Zhang-Jin Huang, Zhao Liu. A Geometric Approach for Multi-Degree Spline[J]. Journal of Computer Science and Technology, 2012, 27(4): 841-850. DOI: 10.1007/s11390-012-1268-2
    [2]Hsien-Hsi Hsieh, Chin-Chen Chang, Wen-Kai Tai, Han-Wei Shen. Novel Geometrical Voxelization Approach with Application to Streamlines[J]. Journal of Computer Science and Technology, 2010, 25(5): 895-904. DOI: 10.1007/s11390-010-1070-y
    [3]JIANG Tianzi. Geometric Primitive Extraction by the Combination of Tabu Search and Subpixel Accuracy[J]. Journal of Computer Science and Technology, 1999, 14(1): 74-80.
    [4]Wang Haohong, Wu Ruixun, Cai Shijie. A New Algorithm for Two-Dimensional Line Clipping via Geometric Transformation[J]. Journal of Computer Science and Technology, 1998, 13(5): 410-416.
    [5]Gao Shuming, Peng Qunsheng. Hierarchical Geometric Constraint Model for Parametric Feature Based Modeling[J]. Journal of Computer Science and Technology, 1997, 12(3): 193-201.
    [6]Yang Changgui, Chen Yuian, Sun Jiaghang. Advanced Geometric Modeler with Hybrid Representation[J]. Journal of Computer Science and Technology, 1996, 11(1): 1-8.
    [7]L Wei, Liang Youdong. A New Representation and Algorithm for Constructing Convex Hulls in Higher Dim ensional Spaces[J]. Journal of Computer Science and Technology, 1992, 7(1): 1-5.
    [8]Tian Jie. The Geometric Continuity of Rational Bezler Triangular Surfaces[J]. Journal of Computer Science and Technology, 1991, 6(4): 383-388.
    [9]Lu Wei, Jin Tongguang, Liang Youdong. Geometric Modelling by Recursively Cutting Vertices[J]. Journal of Computer Science and Technology, 1989, 4(4): 363-373.
    [10]Zhang Fuyan, Cai Shijie, Wang Yulan, Ju Zhengwen. The Geometric Modelling of Furniture Parts and Its Application[J]. Journal of Computer Science and Technology, 1989, 4(3): 236-244.
    • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (39) PDF downloads (3439) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return