Skip to main content
SpringerLink
Log in

Neighborhood search based improved bat algorithm for data clustering

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

Clustering is an unsupervised data analytic technique that can determine the similarity between data objects and put the similar data objects into one cluster. The similarity among data objects is determined through some distance function. It is observed that clustering technique gains wide popularity due to its unsupervised and can be used in diverse research filed such as image segmentation, data analytics, outlier detection, and so on. This work focuses on the data clustering problems and proposes a new clustering algorithm based on the behavior of micro-bats. The proposed bat algorithm to determine the optimal cluster center for data clustering problems. It is also observed that several shortcomings are associated with bat algorithm such as slow convergence rate, local optima, and trade-off among search mechanisms. The slow convergence issue is addressed through an elitist mechanism. While an enhanced cooperative method is introduced for handling population initialization issues. In this work, a Q-learning based neighbourhood search mechanism is also developed to effectively overcome the local optima issue. Several benchmark non-healthcare and healthcare datasets are selected for evaluating the performance of the proposed bat algorithm. The simulation results are evaluated using intracluster distance, standard deviation, accuracy, and rand index parameters and compared with nineteen existing meta-heuristic algorithms. It is observed that the proposed bat algorithm obtains significant results with these datasets.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Abbreviations

ABC:

Artificial Bee Colony

ACA:

Ant Clustering Algorithm

ACDE:

Automatic Clustering Differential Evolution

ACO:

Ant Colony Optimization

BATC:

Bat Algorithm based Clustering

BB-BC:

Big Bang–Big Crunch

CABC:

Cooperative Artificial Bee Colony

CCSSA:

Chaotic Charge System Search Algorithm

CPSO:

Cooperative Particle Swarm Optimization

CS:

Cuckoo Search

CSO:

Cat Swarm Optimization

CSS:

Charge System Search

DCPSO:

Dynamic Clustering Particle Swarm Optimization

DE:

Differential Evolution

FA:

Firefly algorithm

FPAC:

Flower Pollination Algorithm based Clustering

GA:

Genetic Algorithm

GAMS:

Genetic Algorithm with Message-based Similarity

GTCSA:

Gene Transposon based Clone Selection Algorithm

GWA:

Grey Wolf Algorithm

GWO:

Grey Wolf Optimizer

HABC:

Hybrid Artificial Bee Colony

HBMO:

Honey Bee Mating Optimization

KH:

Krill Herd

KHM:

K-harmonic Means

K-MWO:

K-means and Mussels Wandering Optimization

HS:

Harmony Search

IBAT:

Improved Bat

ICSO:

Improved Cat Swarm Optimization

ILS:

Iterated Local Search

MCSS:

Magnetic Charge System Search

MO:

Magnetic Optimization

PSO:

Particle Swarm Optimization

SA:

Simulated Annealing

TLBO:

Teaching learning Based Optimization

TS:

Tabu Search

VGA:

Variable-string-length Genetic Algorithm

MBOA:

Modified Butterfly Optimization Algorithm

WOA:

Whale Optimization Algorithm

ICSO:

Improved cat swarm optimization

Chaotic TLBO:

Chaotic Teaching Learning based optimization

VS:

Vortex Search

References

  1. Kushwaha N, Pant M, Kant S, Jain VK (2018) Magnetic optimization algorithm for data clustering. Pattern Recogn Lett 115:59–65

    Article  Google Scholar 

  2. Kant S, Ansari IA (2016) An improved K means clustering with Atkinson index to classify liver patient dataset. International Journal of System Assurance Engineering and Management 7(1):222–228

    Google Scholar 

  3. Aggarwal CC, Reddy CK (2014) Data clustering. Algorithms and applications. Chapman & Hall/CRC Data mining and Knowledge Discovery series, Londra

  4. Xu R, Wunsch D (2005) Survey of clustering algorithms. IEEE Trans Neural Netw 16(3):645–678

    Article  Google Scholar 

  5. Chang D-X, Zhang X-D, Zheng C-W (2009) A genetic algorithm with gene rearrangement for K-means clustering. Pattern Recogn 42(7):1210–1222

    Article  Google Scholar 

  6. Ester M, Kriegel HP, Sander J, Xu X (1996) A density-based algorithm for discovering clusters in large spatial databases with noise. In Kdd (Vol. 96, No. 34, pp. 226-231)

  7. Scheunders P (1997) A genetic c-means clustering algorithm applied to color image quantization. Pattern Recogn 30(6):859–866

    Article  Google Scholar 

  8. Gomez-Muñoz VM, Porta-Gándara MA (2002) Local wind patterns for modeling renewable energy systems by means of cluster analysis techniques. Renew Energy 2:171–182

    Article  Google Scholar 

  9. Mitra S, Banka H (2006) Multi-objective evolutionary bi clustering of gene expression data. Pattern Recogn 39:2464–2477

    Article  MATH  Google Scholar 

  10. Nanda SJ, Panda G (2014) A survey on nature inspired metaheuristic algorithms for partitional clustering. Swarm and Evolutionary computation 16:1–18

    Article  Google Scholar 

  11. Cura T (2012) A particle swarm optimization approach to clustering. Expert Syst Appl 39(1):1582–1588

    Article  Google Scholar 

  12. Jordehi AR (2015) Enhanced leader PSO (ELPSO): a new PSO variant for solving global optimisation problems. Appl Soft Comput 26:401–417

    Article  Google Scholar 

  13. Karaboga, D. (2005) An idea based on honey bee swarm for numerical optimization, Erciyes University, Kayseri, Turkey, Technical Report-TR06

  14. Karaboga D, Basturk B (2007) A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. J Glob Optim 39(3):459–471

    Article  MathSciNet  MATH  Google Scholar 

  15. Karaboga D, Akay B (2009) A comparative study of artificial bee colony algorithm. Appl Math Comput 214(1):108–132

    MathSciNet  MATH  Google Scholar 

  16. Dorigo M, Birattari M, Stutzle T (2006) Artificial ants as a computational intelligence technique. IEEE Comput Intell Mag 1:28–39

    Article  Google Scholar 

  17. Dorigo M, Maniezzo V, Colorni A (1996) Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, man, and cybernetics, Part B: Cybernetics 26(1):29–41

    Article  Google Scholar 

  18. Kumar Y, Sahoo G (2014) A charged system search approach for data clustering. Progress in Artificial Intelligence 2(2–3):153–166

    Article  Google Scholar 

  19. Hatamlou A (2013) Black hole: A new heuristic optimization approach for data clustering. Inf Sci 222:175–184

    Article  MathSciNet  Google Scholar 

  20. Erol OK, Eksin I (2006) A new optimization method: big bang–big crunch. Adv Eng Softw 37(2):106–111

    Article  Google Scholar 

  21. Jordehi AR (2014) A chaotic-based big bang–big crunch algorithm for solving global optimisation problems. Neural Comput & Applic 25(6):1329–1335

    Article  Google Scholar 

  22. Alatas B (2011) ACROA: artificial chemical reaction optimization algorithm for global optimization. Expert Syst Appl 38(10):13170–13180

    Article  Google Scholar 

  23. Maulik U, Bandyopadhyay S (2000) Genetic algorithm-based clustering technique. Pattern Recogn 33(9):1455–1465

    Article  Google Scholar 

  24. Ergezer M, Simon D, Du D Oppositional biogeography-based optimization. 2009 IEEE international conference on systems, man and cybernetics. IEEE, 2009

  25. Mirjalili S, Mirjalili SM, Lewis A (2014) Grey wolf optimizer. Adv Eng Softw 69:46–61

    Article  Google Scholar 

  26. Wang GG, Deb S, Coelho LDS (2015) Elephant herding optimization. In 2015 3rd International Symposium on Computational and Business Intelligence (ISCBI) (pp. 1–5). IEEE

  27. Chu SC, Tsai PW, Pan JS (2006) Cat swarm optimization. In: Pacific Rim international conference on artificial intelligence. Springer, Berlin, Heidelberg, pp 854–858

    Google Scholar 

  28. Yazdani M, Jolai F (2016) Lion optimization algorithm (LOA): a nature-inspired metaheuristic algorithm. Journal of computational design and engineering 3(1):24–36

    Article  Google Scholar 

  29. Mirjalili S (2016) SCA: a sine cosine algorithm for solving optimization problems. Knowl-Based Syst 96:120–133

    Article  Google Scholar 

  30. Salimi H (2015) Stochastic fractal search: a powerful metaheuristic algorithm. Knowl-Based Syst 75:1–18

    Article  Google Scholar 

  31. Kaveh A, Dadras A (2017) A novel meta-heuristic optimization algorithm: thermal exchange optimization. Adv Eng Softw 110:69–84

    Article  Google Scholar 

  32. Abraham A, Das S, Roy S (2008) Swarm intelligence algorithms for data clustering. In: Soft computing for knowledge discovery and data mining. Springer, Boston, pp 279–313

    Chapter  Google Scholar 

  33. Chowdhury K, Chaudhuri D, Pal AK (2021) An entropy-based initialization method of K-means clustering on the optimal number of clusters. Neural Comput & Applic 33(12):6965–6982

    Article  Google Scholar 

  34. Torrente A, Romo J (2021) Initializing k-means clustering by bootstrap and data depth. Journal of Classification 38(2):232–256

    Article  MathSciNet  MATH  Google Scholar 

  35. Ahmadi R, Ekbatanifard G, Bayat P (2021) A Modified Grey Wolf Optimizer Based Data Clustering Algorithm. Appl Artif Intell 35(1):63–79

    Article  Google Scholar 

  36. Ghany KKA, AbdelAziz AM, Soliman THA, Sewisy AAEM (2020) A hybrid modified step whale optimization algorithm with tabu search for data clustering. Journal of King Saud University-Computer and Information Sciences

  37. Sörensen K (2015) Metaheuristics—the metaphor exposed. Int Trans Oper Res 22(1):3–18

    Article  MathSciNet  MATH  Google Scholar 

  38. Yang X-S A new metaheuristic bat-inspired algorithm. Nature inspired cooperative strategies for optimization (NICSO 2010). Springer, Berlin, Heidelberg, 2010. 65–74

  39. Ashish T, Kapil S, Manju B (2018) Parallel bat algorithm-based clustering using mapreduce. In: Networking Communication and Data Knowledge Engineering. Springer, Singapore, pp 73–82

    Chapter  Google Scholar 

  40. Fister I Jr, Fister D, Yang XS (2013) A hybrid Bat algorithm. ELEKTROTEHNIˇSKI VESTNIK 80(1–2):1–7

    Google Scholar 

  41. Yilmaz S, Kucuksille EU (2013) Improved bat algorithm (IBA) on continuous optimization problems. Lecture Notes on Software Engineering 1(3):279

    Article  Google Scholar 

  42. Senthilnath J, Kulkarni S, Benediktsson JA, Yang XS (2016 Apr) A novel approach for multispectral satellite image classification based on the bat algorithm. IEEE Geosci Remote Sens Lett 13(4):599–603

    Article  Google Scholar 

  43. Neelima S, Satyanarayana N, Murthy PK (2018) Minimizing Frequent Itemsets Using Hybrid ABCBAT Algorithm. In: Data Engineering and Intelligent Computing. Springer, Singapore, pp 91–97

    Chapter  Google Scholar 

  44. Aboubi Y, Drias H, Kamel N (2016) BAT-CLARA: BAT-inspired algorithm for Clustering LARge Applications. IFAC-PapersOnLine. 49(12):243–248

    Article  Google Scholar 

  45. Fister I, Fong S, Brest J (2014) A novel hybrid self-adaptive bat algorithm. Sci World J 2014:70973

  46. Zhao D, He Y (2015) Chaotic binary bat algorithm for analog test point selection. Analog Integr Circ Sig Process 84(2):201–214

    Article  Google Scholar 

  47. Rahman MA, Islam MZ (2014) A hybrid clustering technique combining a novel genetic algorithm with K-Means. Knowl-Based Syst 71:345–365

    Article  Google Scholar 

  48. Liu R et al (2012) Gene transposon based clone selection algorithm for automatic clustering. Inf Sci 204:1–22

    Article  Google Scholar 

  49. Kumar Y, Sahoo G (2017) A two-step artificial bee colony algorithm for clustering. Neural Comput & Applic 28(3):537–551

    Article  Google Scholar 

  50. Cao F, Liang J, Jiang G (2009) An initialization method for the K-Means algorithm using neighborhood model. Computers & Mathematics with Applications 58(3):474–483

    Article  MathSciNet  MATH  Google Scholar 

  51. Han XH et al (2017) A novel data clustering algorithm based on modified gravitational search algorithm. Eng Appl Artif Intell 61:1–7

    Article  Google Scholar 

  52. Senthilnath J, Omkar SN, Mani V (2011) Clustering using firefly algorithm: performance study. Swarm and Evolutionary Computation 1(3):164–171

    Article  Google Scholar 

  53. Erisoglu M, Calis N, Sakallioglu S (2011) A new algorithm for initial cluster centers in k-means algorithm. Pattern Recogn Lett 32(14):1701–1705

    Article  Google Scholar 

  54. Kumar Y, Sahoo G (2015) Hybridization of magnetic charge system search and particle swarm optimization for efficient data clustering using neighborhood search strategy. Soft Comput 19(12):3621–3645

    Article  Google Scholar 

  55. Zhou Y et al (2017) A simplex method-based social spider optimization algorithm for clustering analysis. Eng Appl Artif Intell 64:67–82

    Article  Google Scholar 

  56. Boushaki SI, Kamel N, Bendjeghaba O (2018) A new quantum chaotic cuckoo search algorithm for data clustering. Expert Syst Appl 96:358–372

    Article  MATH  Google Scholar 

  57. Chang D et al (2012) A genetic clustering algorithm using a message-based similarity measure. Expert Syst Appl 39(2):2194–2202

    Article  Google Scholar 

  58. Zhang C, Ouyang D, Ning J (2010) An artificial bee colony approach for clustering. Expert Syst Appl 37(7):4761–4767

    Article  Google Scholar 

  59. Taherdangkoo M et al (2013) A robust clustering method based on blind, naked mole-rats (BNMR) algorithm. Swarm and Evolutionary Computation 10:1–11

    Article  Google Scholar 

  60. Hatamlou A (2012) In search of optimal centroids on data clustering using a binary search algorithm. Pattern Recogn Lett 33(13):1756–1760

    Article  Google Scholar 

  61. Bijari K et al (2018) Memory-enriched big bang–big crunch optimization algorithm for data clustering. Neural Comput & Applic 29(6):111–121

    Article  Google Scholar 

  62. Abualigah LM et al (2017) A novel hybridization strategy for krill herd algorithm applied to clustering techniques. Appl Soft Comput 60:423–435

    Article  Google Scholar 

  63. Pakrashi A, Chaudhuri BB (2016) A Kalman filtering induced heuristic optimization based partitional data clustering. Inf Sci 369:704–717

    Article  Google Scholar 

  64. Kang Q et al (2016) A weight-incorporated similarity-based clustering ensemble method based on swarm intelligence. Knowl-Based Syst 104:156–164

    Article  Google Scholar 

  65. Wang R et al (2016) Flower pollination algorithm with bee pollinator for cluster analysis. Inf Process Lett 116.1:1–14

    Article  Google Scholar 

  66. Hatamlou A, Hatamlou M (2013) PSOHS: an efficient two-stage approach for data clustering. Memetic Computing 5(2):155–161

    Article  Google Scholar 

  67. Yan X et al (2012) A new approach for data clustering using hybrid artificial bee colony algorithm. Neurocomputing 97:241–250

    Article  Google Scholar 

  68. Kwedlo W (2011) A clustering method combining differential evolution with the K-means algorithm. Pattern Recogn Lett 32(12):1613–1621

    Article  Google Scholar 

  69. Yin M et al (2011) A novel hybrid K-harmonic means and gravitational search algorithm approach for clustering. Expert Syst Appl 38(8):9319–9324

    Article  Google Scholar 

  70. Jiang H et al (2010) Ant clustering algorithm with K-harmonic means clustering. Expert Syst Appl 37(12):8679–8684

    Article  Google Scholar 

  71. Xiao J et al (2010) A quantum-inspired genetic algorithm for k-means clustering. Expert Syst Appl 37(7):4966–4973

    Article  Google Scholar 

  72. Žalik KR (2008) An efficient k′-means clustering algorithm. Pattern Recogn Lett 29(9):1385–1391

    Article  Google Scholar 

  73. Jiang B, Wang N (2014) Cooperative bare-bone particle swarm optimization for data clustering. Soft Comput 18(6):1079–1091

    Article  Google Scholar 

  74. Kumar Y, Singh PK (2018) Improved cat swarm optimization algorithm for solving global optimization problems and its application to clustering. Appl Intell 48(9):2681–2697

    Article  Google Scholar 

  75. Kumar Y, Singh PK (2019) A chaotic teaching learning based optimization algorithm for clustering problems. Appl Intell 49(3):1036–1062

    Article  Google Scholar 

  76. Fränti P, Sieranoja S (2018) K-means properties on six clustering benchmark datasets. Appl Intell 48(12):4743–4759

    Article  MATH  Google Scholar 

  77. Faris H, Ala’M AZ, Heidari AA, Aljarah I, Mafarja M, Hassonah MA, Fujita H (2019) An intelligent system for spam detection and identification of the most relevant features based on evolutionary random weight networks. Information Fusion 48:67–83

    Article  Google Scholar 

  78. Maulik U, Bandyopadhyay S (2000) Genetic algorithm-based clustering technique. Pattern Recognition 33.9:1455–1465

    Article  Google Scholar 

  79. Kumar Y, Sahoo G (2017) An Improved Cat Swarm Optimization Algorithm Based on Opposition-Based Learning and Cauchy Operator for Clustering. JIPS 13(4):1000–1013

    Google Scholar 

  80. Jensi R, Wiselin Jiji G (2016) An improved krill herd algorithm with global exploration capability for solving numerical function optimization problems and its application to data clustering. Appl Soft Comput 46:230–245

    Article  Google Scholar 

  81. Watkins CJ, Dayan P (1992) Q-learning. Mach Learn 8(3–4):279–292

    Article  MATH  Google Scholar 

  82. Bouyer A, Hatamlou A (2018) An efficient hybrid clustering method based on improved cuckoo optimization and modified particle swarm optimization algorithms. Appl Soft Comput 67:172–182

    Article  Google Scholar 

  83. Hatamlou A (2017) A hybrid bio-inspired algorithm and its application. Appl Intell 47(4):1059–1067

    Article  Google Scholar 

  84. Doğan B, Ölmez T (2015) A new metaheuristic for numerical function optimization: vortex search algorithm. Inf Sci 293:125–145

    Article  Google Scholar 

  85. Mirjalili S, Lewis A (2016) The whale optimization algorithm. Adv Eng Softw 95:51–67

    Article  Google Scholar 

  86. Wang G-G, Deb S, Cui Z (2019) Monarch butterfly optimization. Neural Comput & Applic 31(7):1995–2014

    Article  Google Scholar 

  87. Demšar J (2006) Statistical comparisons of classifiers over multiple data sets. The Journal of Machine Learning Research 7:1–30

    MathSciNet  MATH  Google Scholar 

  88. Derrac J, García S, Molina D, Herrera F (2011) A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm and Evolutionary Computation 1(1):3–18

    Article  Google Scholar 

  89. García S, Fernández A, Luengo J, Herrera F (2010) Advanced nonparametric tests for multiple comparisons in the design of experiments in computational intelligence and data mining: Experimental analysis of power. Inf Sci 180(10):2044–2064

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering & Information Technology, Jaypee University of Information Technology, Waknaghat, Solan, Himachal Pradesh, India

    Arvinder Kaur & Yugal Kumar

Authors
  1. Arvinder Kaur
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yugal Kumar
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yugal Kumar.

Additional information

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kaur, A., Kumar, Y. Neighborhood search based improved bat algorithm for data clustering. Appl Intell 52, 10541–10575 (2022). https://doi.org/10.1007/s10489-021-02934-x

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-021-02934-x

Keywords

Search

Navigation