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]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117

[2]

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, 2021, 17 (2) : 805-825. doi: 10.3934/jimo.2019135

[3]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005

[4]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[5]

Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122

[6]

Min Xi, Wenyu Sun, Jun Chen. Survey of derivative-free optimization. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 537-555. doi: 10.3934/naco.2020050

[7]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

[8]

Xinpeng Wang, Bingo Wing-Kuen Ling, Wei-Chao Kuang, Zhijing Yang. Orthogonal intrinsic mode functions via optimization approach. Journal of Industrial & Management Optimization, 2021, 17 (1) : 51-66. doi: 10.3934/jimo.2019098

[9]

Manxue You, Shengjie Li. Perturbation of Image and conjugate duality for vector optimization. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020176

[10]

Marek Macák, Róbert Čunderlík, Karol Mikula, Zuzana Minarechová. Computational optimization in solving the geodetic boundary value problems. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 987-999. doi: 10.3934/dcdss.2020381

[11]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[12]

Yi An, Bo Li, Lei Wang, Chao Zhang, Xiaoli Zhou. Calibration of a 3D laser rangefinder and a camera based on optimization solution. Journal of Industrial & Management Optimization, 2021, 17 (1) : 427-445. doi: 10.3934/jimo.2019119

[13]

Ripeng Huang, Shaojian Qu, Xiaoguang Yang, Zhimin Liu. Multi-stage distributionally robust optimization with risk aversion. Journal of Industrial & Management Optimization, 2021, 17 (1) : 233-259. doi: 10.3934/jimo.2019109

[14]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102

[15]

Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100

[16]

Bing Yu, Lei Zhang. Global optimization-based dimer method for finding saddle points. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 741-753. doi: 10.3934/dcdsb.2020139

[17]

C. J. Price. A modified Nelder-Mead barrier method for constrained optimization. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020058

[18]

Claudia Lederman, Noemi Wolanski. An optimization problem with volume constraint for an inhomogeneous operator with nonstandard growth. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020391

[19]

Hanyu Gu, Hue Chi Lam, Yakov Zinder. Planning rolling stock maintenance: Optimization of train arrival dates at a maintenance center. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020177

[20]

Lekbir Afraites, Chorouk Masnaoui, Mourad Nachaoui. Shape optimization method for an inverse geometric source problem and stability at critical shape. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021006

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (68)
  • HTML views (113)
  • Cited by (0)

Other articles
by authors

[Back to Top]