Abstract A nonconvex optimization approach is presented for the robust kernel-based clustering algorithms represented by the radial basis function and the Euler kernel function. The presented approach can handle local optimum problem caused by the non-convexity of the objective function. Difference of convex functions programming (DCP) is applied to escape the local optimum. The clustering accuracy is improved by transforming the objective function into the difference of the two convex functions. The fast and robust algorithm, difference of convex functions algorithm (DCA), is employed to optimize DCP. Consequently, a more robust and optimal solution can be searched by DCP and DCA. Experiments on several UCI datasets show the superiority of the algorithms based on DCP, especially on the large-scale datasets.
About author:: (HE Dan, born in 1992, master student. Her research interests include pattern recognition.)(CHEN Songcan(Corresponding author), born in 1962, Ph.D., professor. His research interests include pattern recognition, machine learning and intelligent computing.)
[1] NAYAK J, NAIK B, BEHERA H S. Fuzzy C-Means (FCM) Clustering Algorithm: A Decade Review from 2000 to 2014 // Proc of the International Conference on Computational Intelligence in Data Mining. New Delhi, India: Springer, 2015, II: 133-149. [2] DUNN J C. Well-Separated Clusters and Optimal Fuzzy Partitions. Journal of Cybernetics, 1974, 4(1): 95-104. [3] BEZDEK J C. Pattern Recognition with Fuzzy Objective Function Algorithms. Norwell, USA: Springer, 1981. [4] BLMER J, BRAUER S, BUJNA K. Complexity and Approximation of the Fuzzy K-Means Problem [C/OL]. [2016-02-08]. http://arxiv.org/pdf/1512.05947v1.pdf. [5] 张道强.基于核的联想记忆及聚类算法的研究与应用.博士学位论文.南京:南京航空航天大学, 2004. (ZHANG D Q. Kernel-Based Associative Memories, Clustering Algorithms and Their Applications. Ph.D Dissertation. Nanjing, China: Nanjing University of Aeronautics and Astronautics, 2004.) [6] CHEN S C, ZHANG D Q. Robust Image Segmentation Using FCM with Spatial Constraints Based on New Kernel-Induced Distance Measure. IEEE Trans on Systems, Man, and Cybernetics(Cybernetics), 2004, 34(4): 1907-1916. [7] ZHANG D Q, CHEN S C. A Novel Kernelized Fuzzy C-Means Algorithm with Application in Medical Image Segmentation. Artificial Intelligence in Medicine, 2004, 32(1): 37-50. [8] WU J S, ZHENG W S, LAI J H. Euler Clustering // Proc of the 23rd International Joint Conference on Artificial Intelligence. Palo Alto, USA: AAAI Press, 2013: 1792-1798. [9] AN L T H, TAO P D. Solving a Class of Linearly Constrained Indefinite Quadratic Problems by D.C. Algorithms. Journal of Global Optimization, 1997, 11(3): 253-285. [10] TAO P D, AN L T H. Convex Analysis Approach to D.C. Programming: Theory, Algorithms and Applications. Acta Mathematica Vietnamica, 1997, 22(1): 289-355. [11] ROCKAFELLAR R T. Convex Analysis. Princeton, USA: Princeton University Press, 2015. [12] HIRIART-URRUTY J B. From Convex Optimization to Nonconvex Optimization. Necessary and Sufficient Conditions for Global Optimality // CLARKE F H, DEM′YANOV V F, GIANNESSI F, eds. Nonsmooth Optimization and Related Topics. New York, USA: Springer, 1989: 219-239. [13] AN L T H, TAO P D. The DC (Difference of Convex Functions) Programming and DCA Revisited with DC Models of Real World Nonconvex Optimization Problems. Annals of Operations Research, 2005, 133(1): 23-46. [14] AN N T, NAM N M. Convergence Analysis of a Proximal Point Algorithm for Minimizing Differences of Functions [C/OL].[2016-02-08]. http://arxiv.org/pdf/1504.08079v4.pdf. [15] AN L T H, LE H M, TAO P D. Fuzzy Clustering Based on Nonconvex Optimisation Approaches Using Difference of Convex (DC) Functions Algorithms. Advances in Data Analysis and Classification, 2007, 1(2): 85-104. [16] LIWICKI S, TZIMIROPOULOS G, ZAFEIRIOU S, et al. Euler Principal Component Analysis. International Journal of Computer Vision, 2013, 101(3): 498-518. [17] FITCH A J, KADYROV A, CHRISTMAS W J, et al. Fast Robust Correlation. IEEE Trans on Image Processing, 2005, 14(8): 1063-1073. [18] AN L T H, BELGHITI M T, TAO P D. A New Efficient Algorithm Based on DC Programming and DCA for Clustering. Journal of Global Optimization, 2007, 37(4): 593-608.
2016, Vol. 29 
