An incremental clustering algorithm based on hyperbolic smoothing

详细信息    查看全文

• 作者：A. M. Bagirov (1)
  B. Ordin (2)
  G. Ozturk (3)
  A. E. Xavier (4)
  
  1. Faculty of Science and Technology ; Federation University Australia ; Ballarat ; VIC ; Australia
  2. Department of Mathematics ; Faculty of Science ; Ege University ; Izmir ; Turkey
  3. Department of Industrial Engineering ; Faculty of Engineering ; Anadolu University ; Eskisehir ; Turkey
  4. Department of Systems Engineering and Computer Science ; Graduate School of Engineering ; Federal University of Rio de Janeiro ; Rio de Janeiro ; Brazil
  
• 关键词：Nonsmooth optimization ; Cluster analysis ; Smoothing techniques ; Nonlinear programming ; 65K05 ; 90C25
• 刊名：Computational Optimization and Applications
• 出版年：2015
• 出版时间：May 2015
• 年：2015
• 卷：61
• 期：1
• 页码：219-241
• 全文大小：226 KB
• 参考文献：1. Al-Sultan, KS (1995) A tabu search approach to the clustering problem. Pattern Recognit. 28: pp. 1443-1451 CrossRef
  2. Bache, K., Lichman, M.: UCI Machine Learning Repository. School of Information and Computer Science, University of California, Irvine, CA (2013). http://archive.ics.uci.edu/ml.
  3. Bagirov, AM (2008) Modified global $$k$$ k -means algorithm for sum-of-squares clustering problems. Pattern Recognit. 41: pp. 3192-3199 CrossRef
  4. Bagirov, AM, Karasozen, B, Sezer, M (2008) Discrete gradient method: A derivative free method for nonsmooth optimization. J. Optim. Theory Appl. 137: pp. 317-334 CrossRef
  5. Bagirov, AM, Rubinov, AM, Yearwood, J (2002) A global optimisation approach to classification. Optim. Eng. 3: pp. 129-155 CrossRef
  6. Bagirov, AM, Rubinov, AM, Soukhoroukova, NV, Yearwood, J (2003) Supervised and unsupervised data classification via nonsmooth and global optimization.. TOP: Span. Oper. Res. J. 11: pp. 1-93 CrossRef
  7. Bagirov, AM, Ugon, J (2005) An algorithm for minimizing clustering functions. Optimization 54: pp. 351-368 CrossRef
  8. Bagirov, AM, Ugon, J, Webb, D (2011) Fast modified global $$k$$ k -means algorithm for sum-of-squares clustering problems. Pattern Recognit. 44: pp. 866-876 CrossRef
  9. Bagirov, AM, Yearwood, J (2006) A new nonsmooth optimization algorithm for minimum sum-of-squares clustering problems. Eur. J. Oper. Res. 170: pp. 578-596 CrossRef
  10. Bagirov, AM, Nuaimat, A, Sultanova, N (2013) Hyperbolic smoothing method for minimax problems. Optimization 62: pp. 759-782 CrossRef
  11. Bock, HH Clustering and neural networks. In: Rizzi, A, Vichi, M, Bock, HH eds. (1998) Advances in Data Science and Classification. Springer, Berlin, pp. 265-277 CrossRef
  12. Brown, DE, Entail, CL (1992) A practical application of simulated annealing to the clustering problem. Pattern Recognit. 25: pp. 401-412 CrossRef
  13. Diehr, G (1985) Evaluation of a branch and bound algorithm for clustering. SIAM J. Sci. Stat. Comput. 6: pp. 268-284 CrossRef
  14. Dubes, R, Jain, AK (1976) Clustering techniques: the user鈥檚 dilemma. Pattern Recognit. 8: pp. 247-260 CrossRef
  The Solver Manuals. GAMS Development Corporation, Washington, D.C.
  15. Hansen, P, Jaumard, B (1997) Cluster analysis and mathematical programming. Math. Programm. 79: pp. 191-215
  16. Hansen, P, Mladenovic, N (2001) $$J$$ J -means: a new heuristic for minimum sum-of-squares clustering. Pattern Recognit. 4: pp. 405-413 CrossRef
  17. Hansen, P, Mladenovic, N (2001) Variable neighborhood decomposition search. J. Heuristic. 7: pp. 335-350 CrossRef
  18. Koontz, WLG, Narendra, PM, Fukunaga, K (1975) A branch and bound clustering algorithm. IEEE Trans. Comput. 24: pp. 908-915 CrossRef
  19. Jensen, RE (1969) A dynamic programming algorithm for cluster analysis. Appl. Stat. 28: pp. 1034-1057
  20. Likas, A, Vlassis, M, Verbeek, J (2003) The global $$k$$ k -means clustering algorithm. Pattern Recognit. 36: pp. 451-461 CrossRef
  21. Merle, O, Hansen, P, Jaumard, B, Mladenovic, N (2001) An interior point method for minimum sum-of-squares clustering. SIAM J. Sci. Comput. 21: pp. 1485-1505 CrossRef
  22. Reinelt, G (1991) TSP-LIB-A traveling salesman library. ORSA J. Comput. 3: pp. 319-350 CrossRef
  23. Selim, SZ, Al-Sultan, KS (1991) A simulated annealing algorithm for the clustering. Pattern Recognit. 24: pp. 1003-1008 CrossRef
  24. Spath, H (1980) Cluster Analysis Algorithms. Ellis Horwood Limited, Chichester
  25. Sun, LX, Xie, YL, Song, XH, Wang, JH, Yu, RQ (1994) Cluster analysis by simulated annealing. Comput. Chem. 18: pp. 103-108 CrossRef
  26. Teboulle, M (2007) A unified continuous optimization framework for center-based clustering methods. J. Mach. Learn. Res. 8: pp. 65-102
  27. Xavier, AE (2010) The hyperbolic smoothing clustering method. Pattern Recognit. 43: pp. 731-737 CrossRef
  28. Xavier, AE, Oliveira, AAFD (2005) Optimal covering of plane domains by circles via hyperbolic smoothing. J. Glob. Optim. 31: pp. 493-504 CrossRef
  29. Xavier, AE, Xavier, VL (2011) Solving the minimum sum-of-squares clustering problem by hyperbolic smoothing and partition into boundary and gravitational regions. Pattern Recognit. 44: pp. 70-77 CrossRef
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Optimization
  Operations Research and Mathematical Programming
  Operation Research and Decision Theory
  Statistics
  Convex and Discrete Geometry
  
• 出版者：Springer Netherlands
• ISSN：1573-2894

文摘

Clustering is an important problem in data mining. It can be formulated as a nonsmooth, nonconvex optimization problem. For the most global optimization techniques this problem is challenging even in medium size data sets. In this paper, we propose an approach that allows one to apply local methods of smooth optimization to solve the clustering problems. We apply an incremental approach to generate starting points for cluster centers which enables us to deal with nonconvexity of the problem. The hyperbolic smoothing technique is applied to handle nonsmoothness of the clustering problems and to make it possible application of smooth optimization algorithms to solve them. Results of numerical experiments with eleven real-world data sets and the comparison with state-of-the-art incremental clustering algorithms demonstrate that the smooth optimization algorithms in combination with the incremental approach are powerful alternative to existing clustering algorithms.