Abstract
The Relevance Index method has been shown to be effective in identifying Relevant Sets in complex systems, i.e., variable sub-sets that exhibit a coordinated behavior, along with a clear independence from the remaining variables. The need for computing the Relevance Index for each possible variable sub-set makes such a computation unfeasible, as the size of the system increases. Because of this, smart search methods are needed to analyze large-size systems using such an approach. Niching metaheuristics provide an effective solution to this problem, as they join search capabilities to good exploration properties, which allow them to explore different regions of the search space in parallel and converge onto several local/global minima.
In this paper, we describe the application of a niching metaheuristic, K-means PSO, to a set of complex systems of different size, comparing, when possible, its results with the ground truth represented by the results of an exhaustive search, while we rely on the analysis of a domain expert to assess the results of larger systems. In all cases, we also compare the results of K-means PSO to another metaheuristic, based on a niching genetic algorithm, that we had previously developed.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
CUDA Toolkit. http://developer.nvidia.com/cuda-toolkit. Accessed 12 Mar 2018
Atabay, H.A., Sheikhzadeh, M.J., Torshizi, M.: A clustering algorithm based on integration of K-means and PSO. In: 2016 1st Conference on Swarm Intelligence and Evolutionary Computation (CSIEC), pp. 59–63, March 2016
Bird, S., Li, X.: Adaptively choosing niching parameters in a PSO. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, GECCO 2006, pp. 3–10. ACM, New York (2006)
Bokhari, S.M.A., Basharat, I., Khan, S.A., Qureshi, A.W., Ahmed, B.: A framework for clustering dental patients’ records using unsupervised learning techniques. In: 2015 Science and Information Conference (SAI), pp. 386–394, July 2015
Brits, R., Engelbrecht, A., van den Bergh, F.: A niching particle swarm optimizer. In: 4th Asia-Pacific Conference on Simulated Evolution and Learning, pp. 692–696, January 2002
Brits, R., Engelbrecht, A.P., van den Bergh, F.: Solving systems of unconstrained equations using particle swarm optimization. In: IEEE International Conference on Systems, Man and Cybernetics, vol. 3, p. 6, October 2002
Canale, S., Giorgio, A.D., Lisi, F., Panfili, M., Celsi, L.R., Suraci, V., Priscoli, F.D.: A future internet oriented user centric extended intelligent transportation system. In: 2016 24th Mediterranean Conference on Control and Automation (MED), pp. 1133–1139, June 2016
Clerc, M., Kennedy, J.: The particle swarm-explosion, stability, and convergence in a multidimensional complex space. IEEE Trans. Evol. Comput. 6(1), 58–73 (2002)
Cover, T., Thomas, A.: Elements of Information Theory, 2nd edn. Wiley-Interscience, New York (2006)
Doreswamy, Salma, M.U.: PSO based fast K-means algorithm for feature selection from high dimensional medical data set. In: 2016 10th International Conference on Intelligent Systems and Control (ISCO), pp. 1–6, January 2016
Filisetti, A., Villani, M., Roli, A., Fiorucci, M., Poli, I., Serra, R.: On some properties of information theoretical measures for the study of complex systems. In: Pizzuti, C., Spezzano, G. (eds.) WIVACE 2014. CCIS, vol. 445, pp. 140–150. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-12745-3_12
Gershenson, C., Fernandez, N.: Complexity and information: measuring emergence, self-organization, and homeostasis at multiple scales. Complexity 18(2), 29–44 (2012)
Goudarzi, S., Hassan, W.H., Anisi, M.H., Soleymani, A., Sookhak, M., Khan, M.K., Hashim, A.H.A., Zareei, M.: ABC-PSO for vertical handover in heterogeneous wireless networks. Neurocomputing 256(Supplement C), 63–81 (2017). Fuzzy Neuro Theory and Technologies for Cloud Computing
Kumar, G., Sarth, P.P., Ranjan, P., Kumar, S.: Satellite image clustering and optimization using K-means and PSO. In: 2016 IEEE 1st International Conference on Power Electronics, Intelligent Control and Energy Systems (ICPEICES), pp. 1–4, July 2016
Li, H., He, H., Wen, Y.: Dynamic particle swarm optimization and K-means clustering algorithm for image segmentation. Optik-Int. J. Light Electron Opt. 126(24), 4817–4822 (2015)
Li, X.: Adaptively choosing neighbourhood bests using species in a particle swarm optimizer for multimodal function optimization. In: Deb, K. (ed.) GECCO 2004. LNCS, vol. 3102, pp. 105–116. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24854-5_10
Liu, B., Li, Z.: Study on the automatic recognition of hidden defects based on Hilbert Huang transform and hybrid SVM-PSO model. In: 2017 Prognostics and System Health Management Conference (PHM-Harbin), pp. 1–7, July 2017
MacQueen, J., et al.: Some methods for classification and analysis of multivariate observations. In: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, pp. 281–297 (1967)
Nguyen, H.B., Xue, B., Andreae, P.: Mutual information for feature selection: estimation or counting? Evol. Intel. 9(3), 95–110 (2016)
Parsopoulos, K.E., Plagianakos, V.P., Magoulas, G.D., Vrahatis, M.N.: Improving the particle swarm optimizer by function “stretching”. In: Hadjisavvas, N., Pardalos, P.M. (eds.) Advances in Convex Analysis and Global Optimization. Nonconvex Optimization and Its Applications, pp. 445–457. Springer, Boston (2001). https://doi.org/10.1007/978-1-4613-0279-7_28
Passaro, A., Starita, A.: Particle swarm optimization for multimodal functions: a clustering approach. J. Artif. Evol. Appl. 2008, 15 p. (2008). https://doi.org/10.1155/2008/482032. Article ID 482032
Poli, R., Kennedy, J., Blackwell, T.: Particle swarm optimization. Swarm Intell. 1(1), 33–57 (2007)
Sani, L., et al.: Efficient search of relevant structures in complex systems. In: Adorni, G., Cagnoni, S., Gori, M., Maratea, M. (eds.) AI*IA 2016. LNCS (LNAI), vol. 10037, pp. 35–48. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-49130-1_4
Schoeman, I.L.: Niching in particle swarm optimization. Ph.D. thesis, School of Engineering, University of Pretoria (2010)
Sun, Q., Wang, Y., Jiang, Y., Shao, L., Chen, D.: Fault diagnosis of SEPIC converters based on PSO-DBN and wavelet packet energy spectrum. In: 2017 Prognostics and System Health Management Conference (PHM-Harbin), pp. 1–7, July 2017
Tononi, G., McIntosh, A., Russel, D., Edelman, G.: Functional clustering: identifying strongly interactive brain regions in neuroimaging data. Neuroimage 7, 133–149 (1998)
Vicari, E., et al.: GPU-based parallel search of relevant variable sets in complex systems. In: Rossi, F., Piotto, S., Concilio, S. (eds.) WIVACE 2016. CCIS, vol. 708, pp. 14–25. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-57711-1_2
Villani, M., Filisetti, A., Benedettini, S., Roli, A., Lane, D., Serra, R.: The detection of intermediate level emergent structures and patterns. In: Liò, P., Miglino, O., Nicosia, G., Nolfi, S., Pavone, M. (eds.) Proceedings of ECAL 2013, the 12th European Conference on Artificial Life. MIT Press (2013)
Villani, M., Roli, A., Filisetti, A., Fiorucci, M., Poli, I., Serra, R.: The search for candidate relevant subsets of variables in complex systems. Artif. Life 21(4), 412–431 (2015)
Will, A., Bustos, J., Bocco, M., Gotay, J., Lamelas, C.: On the use of niching genetic algorithms for variable selection in solar radiation estimation. Renew. Energy 50, 168–176 (2013)
Xue, B., Zhang, M., Browne, W.N., Yao, X.: A survey on evolutionary computation approaches to feature selection. IEEE Trans. Evol. Comput. 20(4), 606–626 (2016)
Yannibelli, V., Amandi, A.: A deterministic crowding evolutionary algorithm to form learning teams in a collaborative learning context. Expert Syst. Appl. 39(10), 8584–8592 (2012)
Acknowledgments
The work of Michele Amoretti was supported by the University of Parma Research Fund - FIL 2016 - Project “NEXTALGO: Efficient Algorithms for Next-Generation Distributed Systems”.
The authors would like to thank Andrea Roli, Roberto Serra, and Marco Villani for the enlightening discussions and comments on this work.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Silvestri, G. et al. (2018). Searching Relevant Variable Subsets in Complex Systems Using K-Means PSO. In: Pelillo, M., Poli, I., Roli, A., Serra, R., Slanzi, D., Villani, M. (eds) Artificial Life and Evolutionary Computation. WIVACE 2017. Communications in Computer and Information Science, vol 830. Springer, Cham. https://doi.org/10.1007/978-3-319-78658-2_23
Download citation
DOI: https://doi.org/10.1007/978-3-319-78658-2_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-78657-5
Online ISBN: 978-3-319-78658-2
eBook Packages: Computer ScienceComputer Science (R0)