An Information Theoretic Learning Artificial Immune Network for Alternative Clustering

Ederson Borges; Guilherme Palermo Coelho

doi:10.5753/jbcs.2024.3483

Authors

Ederson Borges Federal Institute of São Paulo (IFSP) https://orcid.org/0000-0002-6211-4631
Guilherme Palermo Coelho Universidade Estadual de Campinas (UNICAMP) - Faculdade de Tecnologia (FT) https://orcid.org/0000-0002-4641-0684

DOI:

https://doi.org/10.5753/jbcs.2024.3483

Keywords:

Information Theory, Artificial Immune Systems, Clustering, Diversity Maintenance

Abstract

Clustering is an unsupervised task employed when there is no prior knowledge about the structure and information contained in the data. Nowadays the amount of information and the dimensionality of data increased. Due to this, several datasets contain samples that can be clustered in different ways, presenting different partitions. Classical algorithms tend to obtain a single partition per execution and also require information like the number of clusters. Immuno-inspired algorithms were developed to reduce some of these drawbacks. They can find alternative solutions without knowing the number of clusters, but high dimensionality reduces their performance leading to low convergence rates. Information Theoretic Learning (ITL) uses statistical information of the data regardless of prior knowledge of the structure of these data and the dimensionality involved. Applied in several papers for clustering, ITL-based algorithms tend to present good performance for this task. This paper presents an immuno-inspired ITL-based algorithm (ITL-aiNet) capable of finding and maintaining high-quality and diverse solutions for datasets regardless of their dimensionality and structure. Real-world image and document datasets of varying dimensions were used in the experiments, allowing different ways of clustering. The results were evaluated using external indices. The proposed approach was capable of maintaining high-quality and diverse solutions, compared to other strategies found in the literature. The indices used to measure the quality and diversity of solutions indicated that the algorithm is capable of finding and maintaining good solutions. Solutions that have greater diversity than other algorithms in some datasets and higher quality in others.

Downloads

Download data is not yet available.

References

Aggarwal, C. C. and Reddy, C. K., editors (2014). Data Clustering. Chapman and Hall/CRC, Boca Raton, 1 edition. DOI: 10.1201/9781315373515.

Araújo, D., Neto, A. D., and Martins, A. (2013). Information-theoretic clustering: A representative and evolutionary approach. Expert Systems with Applications, 40(10):4190-4205. DOI: 10.1016/j.eswa.2013.01.027.

Bae, E. and Bailey, J. (2006). COALA: A novel approach for the extraction of an alternate clustering of high quality and high dissimilarity. Proceedings - IEEE International Conference on Data Mining, ICDM, pages 53-62. DOI: 10.1109/ICDM.2006.37.

Bezdek, J. C. and Pal, N. R. (1998). Some new indexes of cluster validity. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 28(3):301-315. DOI: 10.1109/3477.678624.

Borges, E. and Coelho, G. P. (2018). Cip-ainet: An entropy-based immune network for multiple clustering. In 2018 IEEE Congress on Evolutionary Computation (CEC), pages 1-8. DOI: 10.1109/CEC.2018.8477744.

Borges, E., Ferrari, D. G., and de Castro, L. N. (2012). Silhouette-based clustering using an immune network. In 2012 IEEE Congress on Evolutionary Computation, pages 1-9. IEEE. DOI: 10.1109/CEC.2012.6252945.

Chao, G., Sun, S., and Bi, J. (2021). A Survey on Multiview Clustering. IEEE Transactions on Artificial Intelligence, 2(2):146-168. DOI: 10.1109/TAI.2021.3065894.

Chikhi, N. F. (2016). Multi-view clustering via spectral partitioning and local refinement. Information Processing and Management, 52(4):618-627. DOI: 10.1016/j.ipm.2015.12.007.

Cover, T. M. and Thomas, J. A. (2005). Elements of Information Theory. John Wiley & Sons, Inc., 1 edition. DOI: 10.1002/047174882X.

Cunha, D., Cruz, D., Politi, A., de Castro, L. N., and Maia, R. D. (2017). Bio-inspired multiobjective clustering optimization: A survey and a proposal. Artificial Intelligence Research, 6(2):10. DOI: 10.5430/air.v6n2p10.

Dang, X. H. and Bailey, J. (2010). Generation of alternative clusterings using the CAMI approach. Proceedings of the 10th SIAM International Conference on Data Mining, SDM 2010, pages 118-129. DOI: 10.1137/1.9781611972801.11.

de Castro, L. N. and Von Zuben, F. J. (2002). aiNet: An Artificial Immune Network for Data Analysis. In Abbass, H. A., Sarker, R., and Newton, C. S., editors, Data Mining: A Heuristic Approach, pages 231-260. IGI Global. DOI: 10.4018/978-1-930708-25-9.ch012.

de França, F. O., Coelho, G. P., Castro, P. A., and Von Zuben, F. J. (2010). Conceptual and Practical Aspects of the aiNet Family of Algorithms. International Journal of Natural Computing Research, 1(1):1-35. DOI: 10.4018/jncr.2010010101.

Demšar, J. (2006). Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research, 7(1):1-30. Available online [link].

Dua, D. and Graff, C. (2017). UCI machine learning repository. Available online [link].

Ferraria, M. A., Ferraria, V. A., and de Castro, L. N. (2023). An Investigation Into Different Text Representations to Train an Artificial Immune Network for Clustering Texts. International Journal of Interactive Multimedia and Artificial Intelligence, 8(3):55. DOI: 10.9781/ijimai.2023.08.006.

Fu, L., Lin, P., Vasilakos, A. V., and Wang, S. (2020). An overview of recent multi-view clustering. Neurocomputing, 402:148-161. DOI: 10.1016/j.neucom.2020.02.104.

Geusebroek, J.-M., Burghouts, G. J., and Smeulders, A. W. M. (2005). The amsterdam library of object images. Int. J. Comput. Vision, 61(1):103–112. DOI: 10.1023/B:VISI.0000042993.50813.60.

Havrda, J. and Charvát, F. (1967). Quantification Method of Classification Processes. Kybernetika, 3(1):30-35. Available online [link].

Hossain, M. S., Ramakrishnan, N., Davidson, I., and Watson, L. T. (2013). How to "alternatize" a clustering algorithm. Data Mining and Knowledge Discovery, 27(2):193-224. DOI: 10.1007/s10618-012-0288-4.

Hubert, L. and Arabie, P. (1985). Comparing partitions. Journal of Classification, 2(1):193-218. DOI: 10.1007/BF01908075.

Jain, A. K. (2010). Data clustering: 50 years beyond k-means. Pattern Recognition Letters, 31(8):651 - 666. DOI: 10.1016/j.patrec.2009.09.011.

Jenssen, R. (2010). Kernel entropy component analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(5):847-860. DOI: 10.1109/TPAMI.2009.100.

Jerne, N. K. (1974). Towards a network theory of the immune system. Annales d'immunologie, 125C(1-2):373-89. Available online [link].

Kontonasios, K.-N. and De Bie, T. (2015). Subjectively interesting alternative clusterings. Machine Learning, 98(1-2):31-56. DOI: 10.1007/s10994-013-5333-z.

Niu, D., Dy, J. G., and Jordan, M. I. (2014). Iterative discovery of multiple alternative clustering views. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(7):1340-1353. DOI: 10.1109/TPAMI.2013.180.

Orouskhani, M., Shi, D., and Orouskhani, Y. (2020). Multi-objective evolutionary clustering with complex networks. Expert Systems with Applications, 165:113916. DOI: 10.1016/j.eswa.2020.113916.

Principe, J. C. (2010). Information Theoretic Learning: Renyi's Entropy and Kernel Perspectives. Springer New York, NY, 1 edition. DOI: 10.1007/978-1-4419-1570-2.

Rényi, A. (1961). On Measures of Entropy And Information. In Proceedings of 4th Berkeley Symposium, volume 1, page 457. Available online [link].

Rousseeuw, P. J. (1987). Silhouettes: A graphical aid to the interpretation and validation of cluster analysis. Journal of Computational and Applied Mathematics, 20(C):53-65. DOI: 10.1016/0377-0427(87)90125-7.

Shannon, C. E. (1948). A mathematical theory of communication. The Bell System Technical Journal, 27(July 1928):379-423. DOI: 10.1145/584091.584093.

Silva, D. G., Fantinato, D. G., Canuto, J., Duarte, L. T., Neves, A., Suyama, R., Montalv ao, J., and Attux, R. (2015). An Introduction to Information Theoretic Learning, Part I: Foundations. Journal of Communication and Information Systems, 31(April):68-79. DOI: 10.14209/jcis.2016.6.

Strehl, A. and Ghosh, J. (2002). Cluster ensembles - A knowledge reuse framework for combining multiple partitions. Journal of Machine Learning Research, 3(3):583-617. Available online [link].

Vinh, N. X. and Epps, J. (2010). MinCEntropy: A novel information theoretic approach for the generation of alternative clusterings. Proceedings - IEEE International Conference on Data Mining, ICDM, pages 521-530. DOI: 10.1109/ICDM.2010.24.

Wan, X., Liu, X., Liu, J., Wang, S., Wen, Y., Liang, W., Zhu, E., Liu, Z., and Zhou, L. (2023). Auto-Weighted Multi-View Clustering for Large-Scale Data. Proceedings of the AAAI Conference on Artificial Intelligence, 37(8):10078-10086. DOI: 10.1609/aaai.v37i8.26201.

Wang, X., Wang, J., Domeniconi, C., Yu, G., Xiao, G., and Guo, M. (2019). Multiple independent subspace clusterings. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 5353-5360. DOI: 10.1609/aaai.v33i01.33015353.

Wu, C., Ioannidis, S., Sznaier, M., Li, X., Kaeli, D., and Dy, J. (2018). Iterative spectral method for alternative clustering. In Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 115-123. PMLR. Available online [link].

Xie, X. L. and Beni, G. (1991). A Validity Measure for Fuzzy Clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(8):841-847. DOI: 10.1109/34.85677.

Zhang, L., Cao, Q., and Lee, J. (2013). A novel ant-based clustering algorithm using Renyi entropy. Applied Soft Computing Journal. DOI: 10.1016/j.asoc.2012.11.022.