Multi-Label Feature Selection with Graph-based Ant Colony Optimization and Generalized Jaccard Similarity

Sabah Robitan Mahmood; Tahsin Ali Mohammed Amin; Khalid Hassan Ahmed; Rebar Dara Mohammed; Pshtiwan Jabar Karim

doi:10.24017/science.2024.1.4

Authors

Sabah Robitan Mahmood Department of Information Technology, Technical College of Informatics, Sulaimani Polytechnic University, Sulaymaniyah, Iraq. https://orcid.org/0000-0001-9045-4839
Tahsin Ali Mohammed Amin Department of Database Technology, Technical College of Informatics, Sulaimani Polytechnic University, Sulaymaniyah, Iraq https://orcid.org/0009-0004-7046-5302
Khalid Hassan Ahmed Department of Information Technology, Technical College of Informatics, Sulaimani Polytechnic University, Sulaymaniyah, Iraq https://orcid.org/0009-0007-4547-2000
Rebar Dara Mohammed Department of Database Technology, Technical College of Informatics, Sulaimani Polytechnic University, Sulaymaniyah, Iraq https://orcid.org/0009-0009-2410-6655
Pshtiwan Jabar Karim Department of Computer Science, College of Science, University of Garmian, Kalar, Sulaymaniyah, Iraq https://orcid.org/0000-0003-0910-8424

Abstract

Multi-label learning is a technique that assigns multiple class labels to each data instance. The growth of digital technology resulted in the development of high-dimensional applications in real-world scenarios. Feature selection approaches are extensively used to reduce dimensionality in multi-label learning. The main problems of the recommender system are determining the best match of futures among users but have not engaged with previously. This paper proposes a strategy for selecting features using ant colony optimization (ACO) that incorporates mutual knowledge. The proposed method utilizes ACO to rank features based on their significance. Thus, the search space is mapped to a graph, and each ant traverses the graph, selecting a predetermined number of features. A new information-theoretical metric is introduced to evaluate the features chosen by each ant. Jaccard generalized similarity coefficient is used to select the most suitable communication target for efficient learning outcomes. Mutual information is employed to assess each features relevance to a set of labels and identify redundant features. Pheromones are assigned values based on the effectiveness of the ants in solving the problem. Finally, the features are ranked based on their pheromone values, and the top-ranked features are selected as the final set of attributes. The proposed method is evaluated using real-world datasets. The findings demonstrate that the proposed method outperforms most of existing and advanced approaches. This paper presents a novel feature selection approach for multi-label learning based on ACO. The experimental results confirm the effectiveness of the proposed method compared to existing techniques.

Keywords:

Multi-label optimization, Feature selection, Ant Colony, Relevance-redundancy, Generalized Jaccard similarity

References

H. Liu and L. Yu, “Toward integrating feature selection algorithms for classification and clustering,” IEEE Transactions on Knowledge and Data Engineering, vol. 17, no. 4, pp. 491–502, Apr. 2005, doi: 10.1109/TKDE.2005.66. DOI: https://doi.org/10.1109/TKDE.2005.66

M. Labani, P. Moradi, F. Ahmadizar, and M. Jalili, “A novel multivariate filter method for feature selection in text classification problems,” Eng. Appl. Artif. Intell., vol. 70, pp. 25–37, Apr. 2018, doi: 10.1016/j.engappai.2017.12.014. DOI: https://doi.org/10.1016/j.engappai.2017.12.014

P. Zhu, Q. Xu, Q. Hu, C. Zhang, and H. Zhao, “Multi-label feature selection with missing labels,” Pattern Recognit., vol. 74, pp. 488–502, Feb. 2018, doi: 10.1016/j.patcog.2017.09.036. DOI: https://doi.org/10.1016/j.patcog.2017.09.036

I. Jain, V. K. Jain, and R. Jain, “Correlation feature selection based improved-Binary Particle Swarm Optimization for gene selection and cancer classification,” Appl. Soft Comput., vol. 62, pp. 203–215, Jan. 2018, doi: 10.1016/j.asoc.2017.09.038. DOI: https://doi.org/10.1016/j.asoc.2017.09.038

E. A. Cherman, M. C. Monard, and J. Metz, “Multi-label Problem Transformation Methods: a Case Study,” CLEI Electron. J., vol. 14, no. 1, Apr. 2011, doi: 10.19153/cleiej.14.1.4. DOI: https://doi.org/10.19153/cleiej.14.1.4

M. R. Boutell, J. Luo, X. Shen, and C. M. Brown, “Learning multi-label scene classification,” Pattern Recognit., vol. 37, no. 9, pp. 1757–1771, Sep. 2004, doi: 10.1016/j.patcog.2004.03.009. DOI: https://doi.org/10.1016/j.patcog.2004.03.009

R. Huang, W. Jiang, and G. Sun, “Manifold-based constraint Laplacian score for multi-label feature selection,” Pattern Recognit. Lett., vol. 112, pp. 346–352, Sep. 2018, doi: 10.1016/j.patrec.2018.08.021. DOI: https://doi.org/10.1016/j.patrec.2018.08.021

Y. Lin, Q. Hu, J. Liu, and J. Duan, “Multi-label feature selection based on max-dependency and min-redundancy,” Neurocomputing, vol. 168, pp. 92–103, Nov. 2015, doi: 10.1016/j.neucom.2015.06.010. DOI: https://doi.org/10.1016/j.neucom.2015.06.010

J. Lee and D.-W. Kim, “Feature selection for multi-label classification using multivariate mutual information,” Pattern Recognit. Lett., vol. 34, no. 3, pp. 349–357, Feb. 2013, doi: 10.1016/j.patrec.2012.10.005. DOI: https://doi.org/10.1016/j.patrec.2012.10.005

A. Hashemi, M. B. Dowlatshahi, and H. Nezamabadi-pour, “MGFS: A multi-label graph-based feature selection algorithm via PageRank centrality,” Expert Syst. Appl., vol. 142, p. 113024, Mar. 2020, doi: 10.1016/j.eswa.2019.113024. DOI: https://doi.org/10.1016/j.eswa.2019.113024

R. S. Wills, “Google’s pagerank: The math behind the search engine,” Math. Intell., vol. 28, no. 4, pp. 6–11, Sep. 2006, doi: 10.1007/BF02984696. DOI: https://doi.org/10.1007/BF02984696

J. Zhang, Z. Luo, C. Li, C. Zhou, and S. Li, “Manifold regularized discriminative feature selection for multi-label learning,” Pattern Recognit., vol. 95, pp. 136–150, Nov. 2019, doi: 10.1016/j.patcog.2019.06.003. DOI: https://doi.org/10.1016/j.patcog.2019.06.003

M.-L. Zhang and Z.-H. Zhou, “ML-KNN: A lazy learning approach to multi-label learning,” Pattern Recognit., vol. 40, no. 7, pp. 2038–2048, Jul. 2007, doi: 10.1016/j.patcog.2006.12.019. DOI: https://doi.org/10.1016/j.patcog.2006.12.019

M. Paniri, M. B. Dowlatshahi, and H. Nezamabadi-pour, “MLACO: A multi-label feature selection algorithm based on ant colony optimization,” Knowl.-Based Syst., vol. 192, p. 105285, Mar. 2020, doi: 10.1016/j.knosys.2019.105285. DOI: https://doi.org/10.1016/j.knosys.2019.105285

P. Moradi and M. Rostami, “Integration of graph clustering with ant colony optimization for feature selection,” Knowl.-Based Syst., vol. 84, pp. 144–161, 2015, doi: https://doi.org/10.1016/j.knosys.2015.04.007. DOI: https://doi.org/10.1016/j.knosys.2015.04.007

S. Tabakhi, P. Moradi, and F. Akhlaghian, “An unsupervised feature selection algorithm based on ant colony optimization,” Eng. Appl. Artif. Intell., vol. 32, pp. 112–123, Jun. 2014, doi: 10.1016/j.engappai.2014.03.007. DOI: https://doi.org/10.1016/j.engappai.2014.03.007

H. Ghimatgar, K. Kazemi, M. S. Helfroush, and A. Aarabi, “An improved feature selection algorithm based on graph clustering and ant colony optimization,” Knowl.-Based Syst., vol. 159, pp. 270–285, Nov. 2018, doi: 10.1016/j.knosys.2018.06.025. DOI: https://doi.org/10.1016/j.knosys.2018.06.025

Z. Manbari, F. Akhlaghian Tab, and C. Salavati, “Fast unsupervised feature selection based on the improved binary ant system and mutation strategy,” Neural Comput. Appl., vol. 31, no. 9, pp. 4963–4982, Sep. 2019, doi: 10.1007/s00521-018-03991-z. DOI: https://doi.org/10.1007/s00521-018-03991-z

G. Doquire and M. Verleysen, “Feature Selection for Multi-label Classification Problems,” in Advances in Computational Intelligence, vol. 6691, J. Cabestany, I. Rojas, and G. Joya, Eds., in Lecture Notes in Computer Science, vol. 6691. , Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 9–16. doi: 10.1007/978-3-642-21501-8_2. DOI: https://doi.org/10.1007/978-3-642-21501-8_2

F. Li, D. Miao, and W. Pedrycz, “Granular multi-label feature selection based on mutual information,” Pattern Recognit., vol. 67, pp. 410–423, Jul. 2017, doi: 10.1016/j.patcog.2017.02.025. DOI: https://doi.org/10.1016/j.patcog.2017.02.025

P. Zhang, G. Liu, and J. Song, “MFSJMI: Multi-label feature selection considering join mutual information and interaction weight,” Pattern Recognit., vol. 138, p. 109378, Jun. 2023, doi: 10.1016/j.patcog.2023.109378. DOI: https://doi.org/10.1016/j.patcog.2023.109378

M. Hatami, S. R. Mahmood, and P. Moradi, “A Graph-based Multi-Label Feature Selection using ant Colony Optimization,” in 2020 10th International Symposium onTelecommunications (IST), Dec. 2020, pp. 175–180. doi: 10.1109/IST50524.2020.9345913. DOI: https://doi.org/10.1109/IST50524.2020.9345913

C. E. Shannon, “A mathematical theory of communication,” Bell System Technical Journal, vol. 27, no. 3, pp. 379–423, 1948, doi: https://doi.org/10.1002/j.1538-7305.1948.tb01338.x. DOI: https://doi.org/10.1002/j.1538-7305.1948.tb01338.x

S. R. Mahmood, M. Hatami, and P. Moradi, “A Trust-based Recommender System by Integration of Graph Clustering and Ant Colony Optimization,” in 2020 10th International Conference on Computer and Knowledge Engineering (ICCKE), Oct. 2020, pp. 598–604. doi: 10.1109/ICCKE50421.2020.9303647. DOI: https://doi.org/10.1109/ICCKE50421.2020.9303647

X.-Z. Wu and Z.-H. Zhou, “A Unified View of Multi-Label Performance Measures.” arXiv, Sep. 01, 2017. doi: 10.48550/arXiv.1609.00288.