November  2020, 16(6): 2757-2779. doi: 10.3934/jimo.2019079

An incremental nonsmooth optimization algorithm for clustering using $ L_1 $ and $ L_\infty $ norms

1. 

Department of Mathematics, Faculty of Science, Ege University, Bornova, 35100, Izmir, Turkey

2. 

School of Mathematical Sciences, Chongqing Normal University, Chongqing, China

3. 

School of Science, Engineering and Information Technology, Federation University Australia, Ballarat, Victoria, 3353, Australia

4. 

Federation University Australia, Ballarat, Victoria, 3353, Australia

* Corresponding author: Burak Ordin

Received  August 2018 Revised  March 2019 Published  October 2020

An algorithm is developed for solving clustering problems with the similarity measure defined using the $ L_1 $ and $ L_\infty $ norms. It is based on an incremental approach and applies nonsmooth optimization methods to find cluster centers. Computational results on 12 data sets are reported and the proposed algorithm is compared with the $ X $-means algorithm.

Citation: Burak Ordin, Adil Bagirov, Ehsan Mohebi. An incremental nonsmooth optimization algorithm for clustering using $ L_1 $ and $ L_\infty $ norms. Journal of Industrial & Management Optimization, 2020, 16 (6) : 2757-2779. doi: 10.3934/jimo.2019079
References:
[1]

C. Aggarwal, A. Hinneburg and D. Keim, On the surprising behavior of distance metrics in high dimensional space, ICDT '01 Proceedings of the 8th International Conf. on Database Theory, (2001), 420–434. Google Scholar

[2]

D. Arthur and S. Vassilvitskii, k-means++: The advantages of careful seeding, SODA '07 Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, (2007), 1027–1035.  Google Scholar

[3]

K. Bache and M. Lichman, UCI Machine Learning Repository, University of California, Irvine, School of Information and Computer Sciences, 2013., Available from: http://archive.ics.uci.edu/ml. Google Scholar

[4]

A. M. Bagirov, Modified global k-means algorithm for minimum sum-of-squares clustering problems, Pattern Recognition, 41 (2008), 3192-3199.   Google Scholar

[5]

A. M. BagirovA. Al Nuaimat and N. Sultanova, Hyperbolic smoothing function method for minimax problems, Optimization, 62 (2013), 759-782.  doi: 10.1080/02331934.2012.675335.  Google Scholar

[6]

A. M. BagirovB. Karasözen and M. Sezer, Discrete gradient method: Derivative-free method for nonsmooth optimization, Journal of Optimization Theory and Applications, 137 (2008), 317-334.  doi: 10.1007/s10957-007-9335-5.  Google Scholar

[7]

A. M. Bagirov, N. Karmitsa and M. M. Mäkelä, Introduction to Nonsmooth Optimization, Springer, Cham, 2014. doi: 10.1007/978-3-319-08114-4.  Google Scholar

[8]

A. M. Bagirov and E. Mohebi, An algorithm for clustering using $L_1$-norm based on hyperbolic smoothing technique, Computational Intelligence, 32 (2016), 439-457.  doi: 10.1111/coin.12062.  Google Scholar

[9]

A. M. Bagirov and E. Mohebi, Nonsmooth optimization based algorithms in cluster analysis, Partitional Clustering Algorithms, (2015), 99–146. Google Scholar

[10]

A. M. BagirovB. OrdinG. Ozturk and A. E. Xavier, An incremental clustering algorithm based on hyperbolic smoothing, Computational Optimization and Applications, 61 (2015), 219-241.  doi: 10.1007/s10589-014-9711-7.  Google Scholar

[11]

A. M. BagirovA. M. Rubinov and J. Yearwood, A global optimization approach to classification, Optimization and Engineering, 3 (2002), 129-155.  doi: 10.1023/A:1020911318981.  Google Scholar

[12]

A. M. BagirovA. M. RubinovN. V. Soukhoroukova and J. Yearwood, Unsupervised and supervised data classification via nonsmooth and global optimization, TOP, 11 (2003), 1-93.  doi: 10.1007/BF02578945.  Google Scholar

[13]

A. M. Bagirov and J. Ugon, Piecewise partially separable functions and a derivative-free algorithm for large scale nonsmooth optimization, Journal of Global Optimization, 35 (2006), 163-195.  doi: 10.1007/s10898-005-3834-4.  Google Scholar

[14]

A. M. BagirovJ. Ugon and D. Webb, Fast modified global k-means algorithm for incremental cluster construction, Pattern Recognition, 44 (2011), 866-876.   Google Scholar

[15]

A. M. Bagirov and J. Yearwood, A new nonsmooth optimization algorithm for minimum sum-of-squares clustering problems, European Journal of Operational Research, 170 (2006), 578-596.  doi: 10.1016/j.ejor.2004.06.014.  Google Scholar

[16]

L. Bobrowski and J. C. Bezdek, c-means clustering with the $l_1$ and $l_\infty$ norms, IEEE Trans. on Systems, Man and Cybernetics, 21 (1991), 545-554.  doi: 10.1109/21.97475.  Google Scholar

[17]

H.-H. Bock, Clustering and neural networks, in Advances in Data Science and Classification (eds. A. Rizzi, M. Vichi and H.-H. Bock), Springer, Berlin, (1998), 265–277.  Google Scholar

[18]

J. Carmichael and P. Sneath, Taxometric maps, Systematic Zoology, 18 (1969), 402-415.   Google Scholar

[19]

M. E. CelebiH. A. Kingravi and P. A. Vela, A comparative study of efficient initialization methods for the k-means clustering algorithm, Expert Systems with Applications, 40 (2013), 200-210.   Google Scholar

[20]

F. H. Clarke, Optimization and Nonsmooth Analysis, Canadian Mathematical Society Series of Monographs and Advanced Texts, Wiley, 1983.  Google Scholar

[21]

K. A. J. Doherty, R. G. Adams and N. Davey, Non-Euclidean norms and data normalisation, Proceedings of ESANN, (2004), 181–186. Google Scholar

[22]

M. Ghorbani, Maximum entropy-based fuzzy clustering by using $L_1$-norm space, Turk. J. Math., 29 (2005), 431-438.   Google Scholar

[23]

C. Hanilci and F. Ertas, Comparison of the impact of some Minkowski metrics on VQ/GMM based speaker recognition, Computers and Electrical Engineering, 37 (2011), 41-56.   Google Scholar

[24]

P. HansenN. Mladenovic and D. Perez-Britos, Variable neighborhood decomposition search, Journal of Heuristics, 7 (2001), 335-350.  doi: 10.1007/0-306-48056-5_6.  Google Scholar

[25]

A. K. Jain, Data clustering: 50 years beyond $k$-means, Pattern Recognition Letters, 31 (2010), 651-666.   Google Scholar

[26]

A. K. JainM. N. Murty and P. J. Flynn, Data clustering: A review, ACM Comput. Surv., 31 (1999), 264-323.   Google Scholar

[27]

K. Jajuga, A clustering method based on the $L_1$-norm, Computational Statistics & Data Analysis, 5 (1987), 357-371.  doi: 10.1016/0167-9473(87)90058-2.  Google Scholar

[28]

D. R. JonesC. D. Perttunen and B. E. Stuckman, Lipschitzian optimization without the Lipschitz constant, Journal of Optimization Theory and Applications, 79 (1993), 157-181.  doi: 10.1007/BF00941892.  Google Scholar

[29]

L. Kaufman and P. J. Rousseeuw, Finding Groups in Data: An Introduction to Cluster Analysis, Wiley Series in Probability and Statistics, Wiley, 1990. doi: 10.1002/9780470316801.  Google Scholar

[30] J. Kogan, Introduction to Clustering Large and High-Dimensional Data, Cambridge University Press, 2007.   Google Scholar
[31]

A. LikasN. Vlassis and J. Verbeek, The global $k$-means clustering algorithm, Pattern Recognition, 36 (2003), 451-461.   Google Scholar

[32]

B. Ordin and A. M. Bagirov, A heuristic algorithm for solving the minimum sum-of-squares clustering problems, Journal of Global Optimization, 61 (2015), 341-361.  doi: 10.1007/s10898-014-0171-5.  Google Scholar

[33]

D. Pelleg and A. W. Moore, X-means: Extending $k$-means with efficient estimation of the number of clusters, ICML'00 Proceedings of the 17-th International Conference on Machine Learning, (2000), 727–734. Google Scholar

[34]

J. D. Pinter, Global Optimization in Action. Continous and Lipschitz Optimization: Algorithms, Implementations ans Applications, Kluwer Academic Publishers, Boston, 1996. doi: 10.1007/978-1-4757-2502-5.  Google Scholar

[35]

G. N. RamosY. HatakeyamaF. Dong and K. Hirota, Hyperbox clustering with Ant Colony Optimization method and its application to medical risk profile recognition, Applied Soft Computing, 9 (2009), 632-640.   Google Scholar

[36]

G. Reinelt, TSPLIB - a traveling salesman problem library, ORSA Journal of Computing, 3 (1991), 376-384.   Google Scholar

[37]

K. SaboR. Scitovski and I. Vazler, One-dimensional center-based $l_1$-clustering method, Optimization Letters, 7 (2013), 5-22.  doi: 10.1007/s11590-011-0389-9.  Google Scholar

[38]

R. Sedgewick and K. Wayne, Introduction to Programming in Java, Addison-Wesley, 2007. Google Scholar

[39]

R. de Souza and F. de Carvalho, Clustering of interval data based on city-block distances, Pattern Recognition Letters, 25 (2004), 353-365.  doi: 10.1016/j.patrec.2003.10.016.  Google Scholar

[40]

H. Späth, Algorithm 30: $L_1$ cluster analysis, Computing, 16 (1976), 379-387.  doi: 10.1007/BF02243486.  Google Scholar

[41]

N. Venkateswarlu and P. Raju, Fast isodata clustering algorithms, Pattern Recognition, 25 (1992), 335-342.   Google Scholar

[42]

A. E. Xavier and A. A. F. D. Oliveira, Optimal covering of plane domains by circles via hyperbolic smoothing, J. of Glob. Opt., 31 (2005), 493-504.  doi: 10.1007/s10898-004-0737-8.  Google Scholar

[43]

S. Xu, Smoothing method for minimax problems, Computational Optimization and Applications, 20 (2001), 267-279.  doi: 10.1023/A:1011211101714.  Google Scholar

[44]

R. Xu and D. Wunsch, Survey of clustering algorithms, IEEE Transactions on Neural Networks, 16 (2005), 645-678.   Google Scholar

[45]

M. S. Yang and W. L. Hung, Alternative fuzzy clustering algorithms with $L_1$-norm and covariance matrix, Advanced Concepts for Intelligent Vision, 4179 (2006), 654-665.   Google Scholar

[46]

J. ZhangL. PengX. Zhao and E. E. Kuruoglu, Robust data clustering by learning multi-metric $L_q$-norm distances, Expert Systems with Applications, 39 (2012), 335-349.   Google Scholar

show all references

References:
[1]

C. Aggarwal, A. Hinneburg and D. Keim, On the surprising behavior of distance metrics in high dimensional space, ICDT '01 Proceedings of the 8th International Conf. on Database Theory, (2001), 420–434. Google Scholar

[2]

D. Arthur and S. Vassilvitskii, k-means++: The advantages of careful seeding, SODA '07 Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, (2007), 1027–1035.  Google Scholar

[3]

K. Bache and M. Lichman, UCI Machine Learning Repository, University of California, Irvine, School of Information and Computer Sciences, 2013., Available from: http://archive.ics.uci.edu/ml. Google Scholar

[4]

A. M. Bagirov, Modified global k-means algorithm for minimum sum-of-squares clustering problems, Pattern Recognition, 41 (2008), 3192-3199.   Google Scholar

[5]

A. M. BagirovA. Al Nuaimat and N. Sultanova, Hyperbolic smoothing function method for minimax problems, Optimization, 62 (2013), 759-782.  doi: 10.1080/02331934.2012.675335.  Google Scholar

[6]

A. M. BagirovB. Karasözen and M. Sezer, Discrete gradient method: Derivative-free method for nonsmooth optimization, Journal of Optimization Theory and Applications, 137 (2008), 317-334.  doi: 10.1007/s10957-007-9335-5.  Google Scholar

[7]

A. M. Bagirov, N. Karmitsa and M. M. Mäkelä, Introduction to Nonsmooth Optimization, Springer, Cham, 2014. doi: 10.1007/978-3-319-08114-4.  Google Scholar

[8]

A. M. Bagirov and E. Mohebi, An algorithm for clustering using $L_1$-norm based on hyperbolic smoothing technique, Computational Intelligence, 32 (2016), 439-457.  doi: 10.1111/coin.12062.  Google Scholar

[9]

A. M. Bagirov and E. Mohebi, Nonsmooth optimization based algorithms in cluster analysis, Partitional Clustering Algorithms, (2015), 99–146. Google Scholar

[10]

A. M. BagirovB. OrdinG. Ozturk and A. E. Xavier, An incremental clustering algorithm based on hyperbolic smoothing, Computational Optimization and Applications, 61 (2015), 219-241.  doi: 10.1007/s10589-014-9711-7.  Google Scholar

[11]

A. M. BagirovA. M. Rubinov and J. Yearwood, A global optimization approach to classification, Optimization and Engineering, 3 (2002), 129-155.  doi: 10.1023/A:1020911318981.  Google Scholar

[12]

A. M. BagirovA. M. RubinovN. V. Soukhoroukova and J. Yearwood, Unsupervised and supervised data classification via nonsmooth and global optimization, TOP, 11 (2003), 1-93.  doi: 10.1007/BF02578945.  Google Scholar

[13]

A. M. Bagirov and J. Ugon, Piecewise partially separable functions and a derivative-free algorithm for large scale nonsmooth optimization, Journal of Global Optimization, 35 (2006), 163-195.  doi: 10.1007/s10898-005-3834-4.  Google Scholar

[14]

A. M. BagirovJ. Ugon and D. Webb, Fast modified global k-means algorithm for incremental cluster construction, Pattern Recognition, 44 (2011), 866-876.   Google Scholar

[15]

A. M. Bagirov and J. Yearwood, A new nonsmooth optimization algorithm for minimum sum-of-squares clustering problems, European Journal of Operational Research, 170 (2006), 578-596.  doi: 10.1016/j.ejor.2004.06.014.  Google Scholar

[16]

L. Bobrowski and J. C. Bezdek, c-means clustering with the $l_1$ and $l_\infty$ norms, IEEE Trans. on Systems, Man and Cybernetics, 21 (1991), 545-554.  doi: 10.1109/21.97475.  Google Scholar

[17]

H.-H. Bock, Clustering and neural networks, in Advances in Data Science and Classification (eds. A. Rizzi, M. Vichi and H.-H. Bock), Springer, Berlin, (1998), 265–277.  Google Scholar

[18]

J. Carmichael and P. Sneath, Taxometric maps, Systematic Zoology, 18 (1969), 402-415.   Google Scholar

[19]

M. E. CelebiH. A. Kingravi and P. A. Vela, A comparative study of efficient initialization methods for the k-means clustering algorithm, Expert Systems with Applications, 40 (2013), 200-210.   Google Scholar

[20]

F. H. Clarke, Optimization and Nonsmooth Analysis, Canadian Mathematical Society Series of Monographs and Advanced Texts, Wiley, 1983.  Google Scholar

[21]

K. A. J. Doherty, R. G. Adams and N. Davey, Non-Euclidean norms and data normalisation, Proceedings of ESANN, (2004), 181–186. Google Scholar

[22]

M. Ghorbani, Maximum entropy-based fuzzy clustering by using $L_1$-norm space, Turk. J. Math., 29 (2005), 431-438.   Google Scholar

[23]

C. Hanilci and F. Ertas, Comparison of the impact of some Minkowski metrics on VQ/GMM based speaker recognition, Computers and Electrical Engineering, 37 (2011), 41-56.   Google Scholar

[24]

P. HansenN. Mladenovic and D. Perez-Britos, Variable neighborhood decomposition search, Journal of Heuristics, 7 (2001), 335-350.  doi: 10.1007/0-306-48056-5_6.  Google Scholar

[25]

A. K. Jain, Data clustering: 50 years beyond $k$-means, Pattern Recognition Letters, 31 (2010), 651-666.   Google Scholar

[26]

A. K. JainM. N. Murty and P. J. Flynn, Data clustering: A review, ACM Comput. Surv., 31 (1999), 264-323.   Google Scholar

[27]

K. Jajuga, A clustering method based on the $L_1$-norm, Computational Statistics & Data Analysis, 5 (1987), 357-371.  doi: 10.1016/0167-9473(87)90058-2.  Google Scholar

[28]

D. R. JonesC. D. Perttunen and B. E. Stuckman, Lipschitzian optimization without the Lipschitz constant, Journal of Optimization Theory and Applications, 79 (1993), 157-181.  doi: 10.1007/BF00941892.  Google Scholar

[29]

L. Kaufman and P. J. Rousseeuw, Finding Groups in Data: An Introduction to Cluster Analysis, Wiley Series in Probability and Statistics, Wiley, 1990. doi: 10.1002/9780470316801.  Google Scholar

[30] J. Kogan, Introduction to Clustering Large and High-Dimensional Data, Cambridge University Press, 2007.   Google Scholar
[31]

A. LikasN. Vlassis and J. Verbeek, The global $k$-means clustering algorithm, Pattern Recognition, 36 (2003), 451-461.   Google Scholar

[32]

B. Ordin and A. M. Bagirov, A heuristic algorithm for solving the minimum sum-of-squares clustering problems, Journal of Global Optimization, 61 (2015), 341-361.  doi: 10.1007/s10898-014-0171-5.  Google Scholar

[33]

D. Pelleg and A. W. Moore, X-means: Extending $k$-means with efficient estimation of the number of clusters, ICML'00 Proceedings of the 17-th International Conference on Machine Learning, (2000), 727–734. Google Scholar

[34]

J. D. Pinter, Global Optimization in Action. Continous and Lipschitz Optimization: Algorithms, Implementations ans Applications, Kluwer Academic Publishers, Boston, 1996. doi: 10.1007/978-1-4757-2502-5.  Google Scholar

[35]

G. N. RamosY. HatakeyamaF. Dong and K. Hirota, Hyperbox clustering with Ant Colony Optimization method and its application to medical risk profile recognition, Applied Soft Computing, 9 (2009), 632-640.   Google Scholar

[36]

G. Reinelt, TSPLIB - a traveling salesman problem library, ORSA Journal of Computing, 3 (1991), 376-384.   Google Scholar

[37]

K. SaboR. Scitovski and I. Vazler, One-dimensional center-based $l_1$-clustering method, Optimization Letters, 7 (2013), 5-22.  doi: 10.1007/s11590-011-0389-9.  Google Scholar

[38]

R. Sedgewick and K. Wayne, Introduction to Programming in Java, Addison-Wesley, 2007. Google Scholar

[39]

R. de Souza and F. de Carvalho, Clustering of interval data based on city-block distances, Pattern Recognition Letters, 25 (2004), 353-365.  doi: 10.1016/j.patrec.2003.10.016.  Google Scholar

[40]

H. Späth, Algorithm 30: $L_1$ cluster analysis, Computing, 16 (1976), 379-387.  doi: 10.1007/BF02243486.  Google Scholar

[41]

N. Venkateswarlu and P. Raju, Fast isodata clustering algorithms, Pattern Recognition, 25 (1992), 335-342.   Google Scholar

[42]

A. E. Xavier and A. A. F. D. Oliveira, Optimal covering of plane domains by circles via hyperbolic smoothing, J. of Glob. Opt., 31 (2005), 493-504.  doi: 10.1007/s10898-004-0737-8.  Google Scholar

[43]

S. Xu, Smoothing method for minimax problems, Computational Optimization and Applications, 20 (2001), 267-279.  doi: 10.1023/A:1011211101714.  Google Scholar

[44]

R. Xu and D. Wunsch, Survey of clustering algorithms, IEEE Transactions on Neural Networks, 16 (2005), 645-678.   Google Scholar

[45]

M. S. Yang and W. L. Hung, Alternative fuzzy clustering algorithms with $L_1$-norm and covariance matrix, Advanced Concepts for Intelligent Vision, 4179 (2006), 654-665.   Google Scholar

[46]

J. ZhangL. PengX. Zhao and E. E. Kuruoglu, Robust data clustering by learning multi-metric $L_q$-norm distances, Expert Systems with Applications, 39 (2012), 335-349.   Google Scholar

Figure 1.  Illustration of the set $ B_2(y) $
Figure 2.  The number of distance evaluations vs the number of clusters
Figure 3.  Visualization of clusters for TSPLIB1060 data set
Figure 4.  Visualization of clusters for TSPLIB3038 data set
Figure 5.  The purity vs the number of clusters
Figure 6.  Data set with outliers
Table 1.  The brief description of data sets
Data sets Number of instances Number of attributes Number of classes
Bavaria postal 1 89 3 -
Bavaria postal 2 89 4 -
Fisher's Iris Plant 150 4 3
Breast Cancer 683 9 2
TSPLIB1060 1060 2 -
Image Segmentation 2310 19 7
TSPLIB3038 3038 2 -
Page Blocks 5473 10 5
EEG Eye State 14980 14 2
D15112 15112 2 -
KEGG Metabolic 53413 20 -
Relation Network
Pla85900 85900 2 -
Data sets Number of instances Number of attributes Number of classes
Bavaria postal 1 89 3 -
Bavaria postal 2 89 4 -
Fisher's Iris Plant 150 4 3
Breast Cancer 683 9 2
TSPLIB1060 1060 2 -
Image Segmentation 2310 19 7
TSPLIB3038 3038 2 -
Page Blocks 5473 10 5
EEG Eye State 14980 14 2
D15112 15112 2 -
KEGG Metabolic 53413 20 -
Relation Network
Pla85900 85900 2 -
Table 2.  Results for small and medium size data sets
$ k $ $ d_1 $ $ d_2^2 $ $ d_\infty $ $ d_1 $ $ d_2^2 $ $ d_\infty $ $ d_1 $ $ d_2^2 $ $ d_\infty $
Bavaria postal 1 Bavaria postal 2 Iris Plant
$ \times 10^6 $ $ \times 10^{10} $ $ \times 10^6 $ $ \times 10^6 $ $ \times 10^{10} $ $ \times 10^6 $ $ \times 10^2 $ $ \times 10^2 $ $ \times 10^2 $
2 4.0249 60.2547 3.9940 1.8600 5.2192 0.9456 2.1670 1.5235 0.9715
3 2.8284 29.4507 2.7892 1.2607 1.7399 0.6594 1.5920 0.7885 0.7420
4 2.1982 10.4561 2.1690 0.9633 0.7559 0.5210 1.3650 0.5726 0.6460
5 1.7208 5.9762 1.6948 0.7872 0.5442 0.4221 1.2460 0.4645 0.5860
6 1.3003 3.5909 1.2766 0.6736 0.3226 0.3459 1.1530 0.3904 0.5300
7 1.0704 2.1983 1.0368 0.5659 0.2215 0.2946 1.0620 0.3430 0.4915
8 0.8511 1.3385 0.8183 0.5097 0.1705 0.2550 1.0010 0.2999 0.4640
9 0.7220 0.8424 0.6993 0.4688 0.1401 0.2360 0.9540 0.2779 0.4435
10 0.6037 0.6447 0.5828 0.4340 0.1181 0.2173 0.9070 0.2583 0.4245
Breast Cancer TSPLIB1060 Image Segmentation
$ \times 10^4 $ $ \times 10^4 $ $ \times 10^4 $ $ \times 10^7 $ $ \times 10^9 $ $ \times 10^6 $ $ \times 10^6 $ $ \times 10^7 $ $ \times 10^5 $
2 0.6401 1.9323 0.1831 0.3864 9.8319 2.6809 0.5192 3.5606 1.4929
3 0.5702 1.6256 0.1607 0.3139 6.7058 2.1508 0.4160 2.7416 1.3284
5 0.5165 1.3707 0.1460 0.2310 3.7915 1.6546 0.3400 1.7143 1.1081
7 0.4651 1.2031 0.1372 0.1976 2.7039 1.3754 0.2892 1.3473 0.9408
10 0.4270 1.0212 0.1278 0.1563 1.7553 1.1048 0.2575 0.9967 0.8170
12 0.4068 0.9480 0.1234 0.1378 1.4507 1.0033 0.2401 0.8477 0.7635
15 0.3872 0.8711 0.1172 0.1198 1.1219 0.8827 0.2188 0.6556 0.6966
18 0.3707 0.8068 0.1112 0.1080 0.9004 0.7906 0.2021 0.5630 0.6481
20 0.3614 0.7698 0.1081 0.1015 0.7925 0.7378 0.1942 0.5137 0.6200
$ k $ $ d_1 $ $ d_2^2 $ $ d_\infty $ $ d_1 $ $ d_2^2 $ $ d_\infty $ $ d_1 $ $ d_2^2 $ $ d_\infty $
Bavaria postal 1 Bavaria postal 2 Iris Plant
$ \times 10^6 $ $ \times 10^{10} $ $ \times 10^6 $ $ \times 10^6 $ $ \times 10^{10} $ $ \times 10^6 $ $ \times 10^2 $ $ \times 10^2 $ $ \times 10^2 $
2 4.0249 60.2547 3.9940 1.8600 5.2192 0.9456 2.1670 1.5235 0.9715
3 2.8284 29.4507 2.7892 1.2607 1.7399 0.6594 1.5920 0.7885 0.7420
4 2.1982 10.4561 2.1690 0.9633 0.7559 0.5210 1.3650 0.5726 0.6460
5 1.7208 5.9762 1.6948 0.7872 0.5442 0.4221 1.2460 0.4645 0.5860
6 1.3003 3.5909 1.2766 0.6736 0.3226 0.3459 1.1530 0.3904 0.5300
7 1.0704 2.1983 1.0368 0.5659 0.2215 0.2946 1.0620 0.3430 0.4915
8 0.8511 1.3385 0.8183 0.5097 0.1705 0.2550 1.0010 0.2999 0.4640
9 0.7220 0.8424 0.6993 0.4688 0.1401 0.2360 0.9540 0.2779 0.4435
10 0.6037 0.6447 0.5828 0.4340 0.1181 0.2173 0.9070 0.2583 0.4245
Breast Cancer TSPLIB1060 Image Segmentation
$ \times 10^4 $ $ \times 10^4 $ $ \times 10^4 $ $ \times 10^7 $ $ \times 10^9 $ $ \times 10^6 $ $ \times 10^6 $ $ \times 10^7 $ $ \times 10^5 $
2 0.6401 1.9323 0.1831 0.3864 9.8319 2.6809 0.5192 3.5606 1.4929
3 0.5702 1.6256 0.1607 0.3139 6.7058 2.1508 0.4160 2.7416 1.3284
5 0.5165 1.3707 0.1460 0.2310 3.7915 1.6546 0.3400 1.7143 1.1081
7 0.4651 1.2031 0.1372 0.1976 2.7039 1.3754 0.2892 1.3473 0.9408
10 0.4270 1.0212 0.1278 0.1563 1.7553 1.1048 0.2575 0.9967 0.8170
12 0.4068 0.9480 0.1234 0.1378 1.4507 1.0033 0.2401 0.8477 0.7635
15 0.3872 0.8711 0.1172 0.1198 1.1219 0.8827 0.2188 0.6556 0.6966
18 0.3707 0.8068 0.1112 0.1080 0.9004 0.7906 0.2021 0.5630 0.6481
20 0.3614 0.7698 0.1081 0.1015 0.7925 0.7378 0.1942 0.5137 0.6200
Table 3.  Results for large data sets
$ k $ $ d_1 $ $ d_2^2 $ $ d_\infty $ $ d_1 $ $ d_2^2 $ $ d_\infty $ $ d_1 $ $ d_2^2 $ $ d_\infty $
TSPLIB3038 Page Blocks D15112
$ \times 10^6 $ $ \times 10^9 $ $ \times 10^6 $ $ \times 10^7 $ $ \times 10^{10} $ $ \times 10^6 $ $ \times 10^8 $ $ \times 10^{11} $ $ \times 10^8 $
2 3.7308 3.1688 2.5651 0.8414 5.7937 4.1746 0.8860 3.6840 0.6109
3 3.0056 2.1763 2.1221 0.6747 3.3134 3.4309 0.6908 2.5324 0.4896
5 2.2551 1.1982 1.5576 0.4882 1.3218 2.4671 0.4998 1.3271 0.3619
10 1.5508 0.5634 1.0738 0.3152 0.4533 1.4446 0.3618 0.6489 0.2524
15 1.2295 0.3560 0.8592 0.2555 0.2495 1.1784 0.2930 0.4324 0.2065
20 1.0597 0.2672 0.7379 0.2200 0.1672 1.0160 0.2501 0.3218 0.1768
25 0.9441 0.2145 0.6627 0.2004 0.1203 0.9020 0.2241 0.2530 0.1583
EEG Eye State Pla85900 Relation Network
$ \times 10^7 $ $ \times 10^8 $ $ \times 10^6 $ $ \times 10^{10} $ $ \times 10^{15} $ $ \times 10^{10} $ $ \times 10^7 $ $ \times 10^8 $ $ \times 10^6 $
2 0.5289 8178.1381 1.5433 2.0656 3.7491 1.4533 0.3586 11.3853 1.9821
3 0.4197 1833.8806 0.9049 1.6262 2.2806 1.1434 0.2800 4.9006 1.5112
5 0.2944 1.3386 0.5183 1.2587 1.3397 0.8712 0.2095 1.8837 1.0549
10 0.2191 0.4567 0.3947 0.8950 0.6829 0.6218 0.1459 0.6352 0.6667
15 0.1965 0.3500 0.3562 0.7335 0.4625 0.5082 0.1231 0.3512 0.5114
20 0.1827 0.2899 0.3292 0.6374 0.3517 0.4443 0.1108 0.2654 0.4440
25 0.1736 0.2596 0.3129 0.5693 0.2827 0.3981 0.1011 0.1946 0.4013
$ k $ $ d_1 $ $ d_2^2 $ $ d_\infty $ $ d_1 $ $ d_2^2 $ $ d_\infty $ $ d_1 $ $ d_2^2 $ $ d_\infty $
TSPLIB3038 Page Blocks D15112
$ \times 10^6 $ $ \times 10^9 $ $ \times 10^6 $ $ \times 10^7 $ $ \times 10^{10} $ $ \times 10^6 $ $ \times 10^8 $ $ \times 10^{11} $ $ \times 10^8 $
2 3.7308 3.1688 2.5651 0.8414 5.7937 4.1746 0.8860 3.6840 0.6109
3 3.0056 2.1763 2.1221 0.6747 3.3134 3.4309 0.6908 2.5324 0.4896
5 2.2551 1.1982 1.5576 0.4882 1.3218 2.4671 0.4998 1.3271 0.3619
10 1.5508 0.5634 1.0738 0.3152 0.4533 1.4446 0.3618 0.6489 0.2524
15 1.2295 0.3560 0.8592 0.2555 0.2495 1.1784 0.2930 0.4324 0.2065
20 1.0597 0.2672 0.7379 0.2200 0.1672 1.0160 0.2501 0.3218 0.1768
25 0.9441 0.2145 0.6627 0.2004 0.1203 0.9020 0.2241 0.2530 0.1583
EEG Eye State Pla85900 Relation Network
$ \times 10^7 $ $ \times 10^8 $ $ \times 10^6 $ $ \times 10^{10} $ $ \times 10^{15} $ $ \times 10^{10} $ $ \times 10^7 $ $ \times 10^8 $ $ \times 10^6 $
2 0.5289 8178.1381 1.5433 2.0656 3.7491 1.4533 0.3586 11.3853 1.9821
3 0.4197 1833.8806 0.9049 1.6262 2.2806 1.1434 0.2800 4.9006 1.5112
5 0.2944 1.3386 0.5183 1.2587 1.3397 0.8712 0.2095 1.8837 1.0549
10 0.2191 0.4567 0.3947 0.8950 0.6829 0.6218 0.1459 0.6352 0.6667
15 0.1965 0.3500 0.3562 0.7335 0.4625 0.5082 0.1231 0.3512 0.5114
20 0.1827 0.2899 0.3292 0.6374 0.3517 0.4443 0.1108 0.2654 0.4440
25 0.1736 0.2596 0.3129 0.5693 0.2827 0.3981 0.1011 0.1946 0.4013
Table 4.  CPU time in small and medium size data sets
$ k $ $ d_1 $ $ d_2^2 $ $ d_\infty $ $ d_1 $ $ d_2^2 $ $ d_\infty $ $ d_1 $ $ d_2^2 $ $ d_\infty $
Bavaria postal 1 Bavaria postal 2 Iris Plant
2 0.03 0.00 0.03 0.03 0.00 0.03 0.02 0.00 0.02
3 0.05 0.02 0.05 0.03 0.00 0.03 0.12 0.00 0.27
4 0.05 0.02 0.05 0.05 0.02 0.05 0.20 0.02 0.70
5 0.20 0.03 0.14 0.12 0.02 0.20 0.42 0.05 1.05
6 0.22 0.05 0.16 0.16 0.03 0.25 0.56 0.11 1.42
7 0.25 0.05 0.19 0.20 0.05 0.42 0.70 0.19 2.12
8 0.25 0.08 0.19 0.28 0.09 0.59 0.94 0.22 2.98
9 0.41 0.11 0.27 0.31 0.14 1.00 1.29 0.51 4.13
10 0.50 0.14 0.30 0.34 0.17 1.33 2.26 0.80 4.90
Breast Cancer TSPLIB1060 Image Segmentation
2 1.45 0.03 0.50 0.09 0.05 0.11 2.28 0.33 27.69
3 5.93 0.22 1.95 0.30 0.08 0.39 5.38 0.89 61.67
5 12.20 1.11 9.94 1.15 0.17 1.29 13.37 3.53 426.55
7 15.58 2.45 14.52 3.17 0.53 4.91 27.67 8.53 638.29
10 22.45 3.42 17.49 7.36 0.86 10.64 157.87 14.82 1144.10
12 25.05 5.91 32.53 9.41 1.53 17.89 210.59 23.13 1539.23
15 26.29 8.89 55.13 18.19 2.22 26.80 360.63 34.02 1903.06
18 28.92 12.37 85.97 30.81 3.40 35.66 508.86 41.34 2284.46
20 30.47 15.09 96.22 47.22 4.84 57.30 711.24 62.63 2866.97
$ k $ $ d_1 $ $ d_2^2 $ $ d_\infty $ $ d_1 $ $ d_2^2 $ $ d_\infty $ $ d_1 $ $ d_2^2 $ $ d_\infty $
Bavaria postal 1 Bavaria postal 2 Iris Plant
2 0.03 0.00 0.03 0.03 0.00 0.03 0.02 0.00 0.02
3 0.05 0.02 0.05 0.03 0.00 0.03 0.12 0.00 0.27
4 0.05 0.02 0.05 0.05 0.02 0.05 0.20 0.02 0.70
5 0.20 0.03 0.14 0.12 0.02 0.20 0.42 0.05 1.05
6 0.22 0.05 0.16 0.16 0.03 0.25 0.56 0.11 1.42
7 0.25 0.05 0.19 0.20 0.05 0.42 0.70 0.19 2.12
8 0.25 0.08 0.19 0.28 0.09 0.59 0.94 0.22 2.98
9 0.41 0.11 0.27 0.31 0.14 1.00 1.29 0.51 4.13
10 0.50 0.14 0.30 0.34 0.17 1.33 2.26 0.80 4.90
Breast Cancer TSPLIB1060 Image Segmentation
2 1.45 0.03 0.50 0.09 0.05 0.11 2.28 0.33 27.69
3 5.93 0.22 1.95 0.30 0.08 0.39 5.38 0.89 61.67
5 12.20 1.11 9.94 1.15 0.17 1.29 13.37 3.53 426.55
7 15.58 2.45 14.52 3.17 0.53 4.91 27.67 8.53 638.29
10 22.45 3.42 17.49 7.36 0.86 10.64 157.87 14.82 1144.10
12 25.05 5.91 32.53 9.41 1.53 17.89 210.59 23.13 1539.23
15 26.29 8.89 55.13 18.19 2.22 26.80 360.63 34.02 1903.06
18 28.92 12.37 85.97 30.81 3.40 35.66 508.86 41.34 2284.46
20 30.47 15.09 96.22 47.22 4.84 57.30 711.24 62.63 2866.97
Table 5.  CPU time in large data sets
$ k $ $ d_1 $ $ d_2^2 $ $ d_\infty $ $ d_1 $ $ d_2^2 $ $ d_\infty $ $ d_1 $ $ d_2^2 $ $ d_\infty $
TSPLIB3038 Page Blocks D15112
2 0.33 0.20 0.41 2.67 0.45 1.22 4.80 4.48 6.13
3 0.90 0.47 0.95 6.51 1.34 7.52 8.80 8.50 12.62
5 2.34 0.87 1.56 30.75 2.84 54.16 15.37 14.71 23.51
10 14.29 2.26 14.68 113.05 14.01 193.61 39.13 32.26 54.49
15 43.34 4.48 33.79 193.38 29.05 523.04 73.79 58.34 107.72
20 107.33 8.31 63.73 739.82 63.68 787.13 121.87 92.51 176.70
25 163.46 15.29 155.72 969.64 95.22 1085.21 168.96 136.61 274.31
EEG Eye State Pla85900 Relation Network
2 1.26 0.89 2.57 79.47 77.69 108.03 95.22 4.93 71.46
3 2.20 1.61 3.96 156.24 154.13 216.56 208.09 18.50 119.70
5 9.28 3.79 16.04 311.22 305.59 431.59 422.79 52.45 283.08
10 44.80 65.86 79.89 710.71 697.09 989.53 949.52 186.80 931.51
15 115.74 148.62 208.57 1138.17 1154.27 1566.55 1789.21 514.96 1963.96
20 252.27 243.49 415.32 1574.80 1575.67 2177.26 2687.01 787.71 3546.57
25 414.92 354.20 764.83 2041.79 2025.19 2830.90 4547.85 1197.28 5854.08
$ k $ $ d_1 $ $ d_2^2 $ $ d_\infty $ $ d_1 $ $ d_2^2 $ $ d_\infty $ $ d_1 $ $ d_2^2 $ $ d_\infty $
TSPLIB3038 Page Blocks D15112
2 0.33 0.20 0.41 2.67 0.45 1.22 4.80 4.48 6.13
3 0.90 0.47 0.95 6.51 1.34 7.52 8.80 8.50 12.62
5 2.34 0.87 1.56 30.75 2.84 54.16 15.37 14.71 23.51
10 14.29 2.26 14.68 113.05 14.01 193.61 39.13 32.26 54.49
15 43.34 4.48 33.79 193.38 29.05 523.04 73.79 58.34 107.72
20 107.33 8.31 63.73 739.82 63.68 787.13 121.87 92.51 176.70
25 163.46 15.29 155.72 969.64 95.22 1085.21 168.96 136.61 274.31
EEG Eye State Pla85900 Relation Network
2 1.26 0.89 2.57 79.47 77.69 108.03 95.22 4.93 71.46
3 2.20 1.61 3.96 156.24 154.13 216.56 208.09 18.50 119.70
5 9.28 3.79 16.04 311.22 305.59 431.59 422.79 52.45 283.08
10 44.80 65.86 79.89 710.71 697.09 989.53 949.52 186.80 931.51
15 115.74 148.62 208.57 1138.17 1154.27 1566.55 1789.21 514.96 1963.96
20 252.27 243.49 415.32 1574.80 1575.67 2177.26 2687.01 787.71 3546.57
25 414.92 354.20 764.83 2041.79 2025.19 2830.90 4547.85 1197.28 5854.08
Table 6.  Comparison of algorithms using $ d_1 $ and $ d_{\infty} $ functions
$ k $ $ d_1 $ $ d_{\infty} $ $ k $ $ d_1 $ $ d_{\infty} $
$ X $-means INCA $ X $-means INCA $ X $-means INCA $ X $-means INCA
Bavaria postal 1 Bavaria postal 2
2 44.21 0.00 44.58 0.00 2 13.31 0.00 15.95 0.00
3 34.44 0.00 111.42 0.00 3 15.29 0.00 23.33 0.00
4 48.73 0.00 63.68 0.00 4 27.51 0.00 30.53 0.00
5 102.81 0.00 102.90 0.00 5 14.30 0.00 45.22 0.00
6 149.68 0.00 166.86 0.00 6 10.24 0.00 72.81 0.00
7 148.86 0.00 226.41 0.00 7 20.39 0.00 97.27 0.00
8 188.37 0.00 312.47 0.00 8 32.67 0.00 122.49 0.00
9 338.74 0.00 370.37 0.00 9 39.57 0.00 132.80 0.00
10 404.43 0.00 466.69 0.00 10 42.22 0.00 149.03 0.00
Iris Plants Breast Cancer
2 2.05 0.00 1.01 0.00 2 14.46 0.00 5.60 0.00
3 2.07 0.00 6.45 0.00 3 15.35 0.00 14.25 0.00
4 12.42 0.00 12.02 0.00 5 15.11 0.00 9.26 0.00
5 5.34 0.00 10.58 0.00 7 20.19 0.00 10.40 0.00
6 7.15 0.00 30.88 0.00 10 18.15 0.00 14.19 0.00
7 11.85 0.00 21.67 0.00 12 19.75 0.00 12.80 0.00
8 17.12 0.00 26.90 0.00 15 18.75 0.00 14.41 0.00
9 21.59 0.00 31.06 0.00 18 21.63 0.00 15.84 0.00
10 23.72 0.00 28.98 0.00 20 22.22 0.00 15.50 0.00
$ k $ $ d_1 $ $ d_{\infty} $ $ k $ $ d_1 $ $ d_{\infty} $
$ X $-means INCA $ X $-means INCA $ X $-means INCA $ X $-means INCA
Bavaria postal 1 Bavaria postal 2
2 44.21 0.00 44.58 0.00 2 13.31 0.00 15.95 0.00
3 34.44 0.00 111.42 0.00 3 15.29 0.00 23.33 0.00
4 48.73 0.00 63.68 0.00 4 27.51 0.00 30.53 0.00
5 102.81 0.00 102.90 0.00 5 14.30 0.00 45.22 0.00
6 149.68 0.00 166.86 0.00 6 10.24 0.00 72.81 0.00
7 148.86 0.00 226.41 0.00 7 20.39 0.00 97.27 0.00
8 188.37 0.00 312.47 0.00 8 32.67 0.00 122.49 0.00
9 338.74 0.00 370.37 0.00 9 39.57 0.00 132.80 0.00
10 404.43 0.00 466.69 0.00 10 42.22 0.00 149.03 0.00
Iris Plants Breast Cancer
2 2.05 0.00 1.01 0.00 2 14.46 0.00 5.60 0.00
3 2.07 0.00 6.45 0.00 3 15.35 0.00 14.25 0.00
4 12.42 0.00 12.02 0.00 5 15.11 0.00 9.26 0.00
5 5.34 0.00 10.58 0.00 7 20.19 0.00 10.40 0.00
6 7.15 0.00 30.88 0.00 10 18.15 0.00 14.19 0.00
7 11.85 0.00 21.67 0.00 12 19.75 0.00 12.80 0.00
8 17.12 0.00 26.90 0.00 15 18.75 0.00 14.41 0.00
9 21.59 0.00 31.06 0.00 18 21.63 0.00 15.84 0.00
10 23.72 0.00 28.98 0.00 20 22.22 0.00 15.50 0.00
[1]

Jueyou Li, Guoquan Li, Zhiyou Wu, Changzhi Wu, Xiangyu Wang, Jae-Myung Lee, Kwang-Hyo Jung. Incremental gradient-free method for nonsmooth distributed optimization. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1841-1857. doi: 10.3934/jimo.2017021

[2]

Zehui Jia, Xue Gao, Xingju Cai, Deren Han. The convergence rate analysis of the symmetric ADMM for the nonconvex separable optimization problems. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020053

[3]

Qilin Wang, S. J. Li. Higher-order sensitivity analysis in nonconvex vector optimization. Journal of Industrial & Management Optimization, 2010, 6 (2) : 381-392. doi: 10.3934/jimo.2010.6.381

[4]

Juan Carlos De los Reyes, Carola-Bibiane Schönlieb. Image denoising: Learning the noise model via nonsmooth PDE-constrained optimization. Inverse Problems & Imaging, 2013, 7 (4) : 1183-1214. doi: 10.3934/ipi.2013.7.1183

[5]

Mohamed Aly Tawhid. Nonsmooth generalized complementarity as unconstrained optimization. Journal of Industrial & Management Optimization, 2010, 6 (2) : 411-423. doi: 10.3934/jimo.2010.6.411

[6]

Yigui Ou, Xin Zhou. A modified scaled memoryless BFGS preconditioned conjugate gradient algorithm for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2018, 14 (2) : 785-801. doi: 10.3934/jimo.2017075

[7]

Jie Shen, Jian Lv, Fang-Fang Guo, Ya-Li Gao, Rui Zhao. A new proximal chebychev center cutting plane algorithm for nonsmooth optimization and its convergence. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1143-1155. doi: 10.3934/jimo.2018003

[8]

Chunrong Chen, T. C. Edwin Cheng, Shengji Li, Xiaoqi Yang. Nonlinear augmented Lagrangian for nonconvex multiobjective optimization. Journal of Industrial & Management Optimization, 2011, 7 (1) : 157-174. doi: 10.3934/jimo.2011.7.157

[9]

Giancarlo Bigi. Componentwise versus global approaches to nonsmooth multiobjective optimization. Journal of Industrial & Management Optimization, 2005, 1 (1) : 21-32. doi: 10.3934/jimo.2005.1.21

[10]

Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171

[11]

Dmitry Pozharskiy, Noah J. Wichrowski, Andrew B. Duncan, Grigorios A. Pavliotis, Ioannis G. Kevrekidis. Manifold learning for accelerating coarse-grained optimization. Journal of Computational Dynamics, 2020, 7 (2) : 511-536. doi: 10.3934/jcd.2020021

[12]

Mikhail Langovoy, Akhilesh Gotmare, Martin Jaggi. Unsupervised robust nonparametric learning of hidden community properties. Mathematical Foundations of Computing, 2019, 2 (2) : 127-147. doi: 10.3934/mfc.2019010

[13]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020117

[14]

Chunrong Chen. A unified nonlinear augmented Lagrangian approach for nonconvex vector optimization. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 495-508. doi: 10.3934/naco.2011.1.495

[15]

Weijun Zhou, Youhua Zhou. On the strong convergence of a modified Hestenes-Stiefel method for nonconvex optimization. Journal of Industrial & Management Optimization, 2013, 9 (4) : 893-899. doi: 10.3934/jimo.2013.9.893

[16]

Hui Gao, Jian Lv, Xiaoliang Wang, Liping Pang. An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information. Journal of Industrial & Management Optimization, 2019  doi: 10.3934/jimo.2019135

[17]

A. M. Bagirov, Moumita Ghosh, Dean Webb. A derivative-free method for linearly constrained nonsmooth optimization. Journal of Industrial & Management Optimization, 2006, 2 (3) : 319-338. doi: 10.3934/jimo.2006.2.319

[18]

Dan Li, Li-Ping Pang, Fang-Fang Guo, Zun-Quan Xia. An alternating linearization method with inexact data for bilevel nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2014, 10 (3) : 859-869. doi: 10.3934/jimo.2014.10.859

[19]

Cristian Barbarosie, Anca-Maria Toader, Sérgio Lopes. A gradient-type algorithm for constrained optimization with application to microstructure optimization. Discrete & Continuous Dynamical Systems - B, 2020, 25 (5) : 1729-1755. doi: 10.3934/dcdsb.2019249

[20]

Xiangyu Gao, Yong Sun. A new heuristic algorithm for laser antimissile strategy optimization. Journal of Industrial & Management Optimization, 2012, 8 (2) : 457-468. doi: 10.3934/jimo.2012.8.457

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (10)
  • HTML views (54)
  • Cited by (0)

Other articles
by authors

[Back to Top]