Simultaneous Evolutionary Optimization of Features Subset and Clusters Number

Simultaneous Evolutionary Optimization of Features Subset and Clusters Number José David Martín J.D. Martín [email protected] BiBigData, NTTData Seville, Spain Beatriz Pontes B. Pontes bep[email protected] Department of Computer Languages and Systems, University of Seville Seville, Spain José C. Riquelme J.C. Riquelme [email protected] Department of Computer Languages and Systems, University of Seville Seville, Spain ABSTRACT Cluster analysis is a popular technique used to identify patterns in data mining. However, evaluating the accuracy of a clustering task is a challenging process which remains to be an open issue. In this work, we focus on two factors that significantly influence clustering performance: the optimal number of clusters and the subset of relevant attributes. While the former has been extensively studied, the latter has received comparatively less attention, especially in relation to its equivalent in supervised learning. Despite their clear interdependence, these factors have rarely been studied together. In this context, we propose an evolutionary algorithm that simultaneously optimizes both factors using ad-hoc variations of internal validation indices as a fitness function. KEYWORDS Feature Selection, Clustering, Genetic Algorithm ACM Reference Format: José David Martín, J.D. Martín, Beatriz Pontes, B. Pontes, José C. Riquelme, and J.C. Riquelme. 2023. Simultaneous Evolutionary Optimization of Features Subset and Clusters Number. In Genetic and Evolutionary Computation Conference Companion (GECCO ’23 Companion), July 15–19, 2023, Lisbon, Portugal. ACM, New York, NY, USA, 4 pages. https://doi.org/10.1145/3583133. 3590603 1 INTRODUCTION Nowadays, data analysis techniques try to discover interesting and novel patterns from records with multiple attributes. Feature selection is an important preprocessing step in pattern recognition to discover relevant features [ 3 ]. In most of the cases we can obtain the same information using a much smaller number of attributes in our data. This is still considered a challenge for the scientific community in several areas. One of the most widely used data analysis techniques is clustering [ 12 ]. Unsupervised separation of records into different subsets makes it possible to group records that look alike and differ from each other. From the centroids of these clusters, it is possible to establish patterns in the data according to the values of the attributes. Obtaining an optimal clustering is a complex task with multiple Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s). GECCO ’23 Companion, July 15–19, 2023, Lisbon, Portugal https://doi.org/10.1145/3583133.3590603 proposals in the literature [ 20 ]. A crucial point in the clustering task is to determine the appropriate clusters number. Although there are some clustering algorithms, such as density-based algorithms, that have a certain process of searching for the optimal cluster number, the dependence on other necessary parameters influences the final number of clusters found as optimal. On the other hand, selecting the relevant attributes for optimal clustering is a problem that, compared to the supervised version of the problem, has received much less attention. This article presents the implementation of an evolutionary algorithm designed to simultaneously find the optimal number of clusters, as well as the subset of the most important attributes to obtain the optimal clustering. In order to evaluate different approximations, we have used variants of internal validation indexes widely used in the literature. This way, the fitness function will prioritize those groupings with better validation indices, also taking into account the number of considered features. From the empirical point of view, synthetic databases of diverse nature have been used, as well as several real dataset from the public UCI Machine Learning repository, where our feature selection has been proven to be very effective. The rest of the document is organized as follows. Section 2 refers to previous works in the literature. The proposed genetic algorithm and the experimental results are presented in sections 3 and 4, respectively. We finally summarize the main conclusions of our work. 2 RELATED WORK Cluster analysis aims at identifying groups of similar objects within a dataset. The validation of the results obtained by clustering algorithms is a fundamental part of the clustering process. Most clustering techniques follow simple and easy ways to classify a given data set through a pre-specified number of clusters ( 𝐾 ), therefore the problem of determining “the right number of clusters” has attracted considerable interest. The most common strategy is to run the clustering algorithm several times with different 𝐾 values. Then, all the partitions are evaluated by means of cluster validation indexes (CVI) and the best partition and its corresponding 𝐾 value is selected. Most popular CVIs include Calinski-Harabasz [ 13 ], Silhouette [ 17 ], Dunn [ 7 ] and Davis-Bouldin [ 4 ]. De Amorim and Mirkin [ 5 ] use the Minkowski metric together with feature weighting in K-means clustering. In [ 15 ], a genetic algorithm is proposed to find the optimal number of clusters within a data set using Davis-Bouldin validation index within its fitness function. Finally, an extensive comparative study of cluster validity indices 307 GECCO ’23 Companion, July 15–19, 2023, Lisbon, Portugal José David Martín, J.D. Martín, Beatriz Pontes, B. Pontes, José C. Riquelme, and J.C. Riquelme  Figure 1: Chromosome with 10 attributes (5 selected) and 8 clusters. can be found in [ 2 ], where the authors compare 30 CVIs in many different environments with different characteristics. The next goal of our work correspond to the selection of a smaller number of attributes. This is especially interesting considering that it is increasingly common to use large data, with the consequent cost in time and execution to be able to group them. This problem has already been addressed for clustering problems in areas of different nature such as geometrical information [ 18 ]. Authors in [ 19 ] present a hybrid filter–wrapper feature selection method for clustering, combining the Laplacian Score ranking together with a modified Calinski-Harabasz index. In the text document clustering domain, the authors in [ 1 ] propose three different feature selection algorithms, combining feature weights schemes and dynamic dimension reductions. Using Genetic Algorithms (GAs) to perform selection of attributes, it is also possible to find several interesting examples in the literature, such as detecting aero engine rolling bearing faults [ 9 ]. There also exist many examples in the literature in which a genetic algorithm has been used as a basis for clustering the data [ 11 ]. Our starting hypothesis is that in order to select an adequate subset of characteristics in clustering, it is necessary to take into account simultaneously the optimal clusters number. The above approaches do not consider that the goodness of a clustering is largely determined by two factors, and therefore can not be optimized independently. More recently, a multi-objective differential evolution approach to perform both tasks simultaneously has been proposed [ 10 ]. In this sense, our approach benefits from being a simpler idea and not having to choose a solution from the Pareto front. We therefore prove that it is possible to perform simultaneous feature selection and cluster number optimization within a single-objective procedure. 3 OUR PROPOSAL This article presents the implementation of a GA as the search engine for the best clustering from a data set, aiming at finding both the set of relevant attributes and the number of clusters. The basic GA first constructs a (pseudo)-random initial population and then iterates through a series of generations until a certain stopping criteria is met. Individuals with higher fitness values have a better chance to evolve into the next generation by applying genetic operators such as selection, crossover, and mutation. In our work, each phenotype consists of an array of binary values with the dimension (number of total attributes) of the database to be clustered. It also contains and extra value that refers to the number of clusters in which the information will be divided ( 𝐾 ). In this representation, each value within the chromosome set to "1" indicates that the corresponding attribute will be selected to carry out the clustering, while a value of "0" indicates that the attribute will not be selected. An example of a database with 10 features chromosome (5 selected) and 𝐾=8is represented in figure 1. The initial population has been defined as a set of random individuals, subjecting the following restriction: each individual will have at least a 20% of the total attributes of the database set to "1". As for the value of the number of clusters, it will be randomly set to a value in the interval [2, 𝐾_𝑀𝐴𝑋 ] for each chromosome, being all these values configurable. 3.1 Fitness Function The goal of our approach is to achieve the best possible clustering with the most representative features in each database. For this purpose the K-means has been used as a clustering method. Subsequently, each individual is evaluated applying internal clustering validation indexes. Furthermore, a correction factor has been added to the fitness function: (1) Dunn corrections: used for the Dunn internal validation index: 𝐹𝑖𝑡𝑛𝑒𝑠𝑠 =𝐷𝑢𝑛𝑛 +√︁𝑓 𝑒𝑎𝑡𝑢𝑟𝑒𝑠 (1) 𝐹𝑖𝑡𝑛𝑒𝑠𝑠 =𝐷𝑢𝑛𝑛 +ln(𝑓 𝑒𝑎𝑡𝑢𝑟𝑒𝑠)(2) (2) Silhouette correction: we have defined the following correction within a range of [0,1], and multiplied by a 𝛼factor: 𝐹𝑖𝑡𝑛𝑒𝑠𝑠 =𝑆𝑖𝑙ℎ𝑜𝑢𝑒𝑡𝑡𝑒 +𝛼× (1−1 𝑓 𝑒𝑎𝑡𝑢𝑟𝑒𝑠 )(3) 3.2 Genetic Operators and Generational Change To evolve from one population to another, we first include the two best individuals (elitism). The rest of the individuals are selected by the selection tournament [ 14 ] in order to apply afterwards uniform crossover and the following mutation procedure: If an individual is selected to be mutated, there is a probability that each value representing an attribute on the chromosome changes, changing from "0" to "1", or vice versa. Another probability is applied in order to mutate its 𝐾 value, whose value can only be modified by one unit, as long as its final value is different from 1. The algorithm has been designed to perform a maximum number of generations. After each generational change, the fitness value of the best individual is compared to the best fitness value of the previous generation. If this value has not changed in a predefined number of consecutive iterations, a portion of the population with the worst fitness is eliminated and the same number of individuals is randomly generated. The generations follow one another and the algorithm will stop if it reaches ten iterations with no significant change in best the fitness value. Or, if it reaches the maximum number of generations. The best individual from the final population is returned. The final configuration of our approach can be found in section 4, where configuration parameters are also presented in table 1. 4 EXPERIMENTAL RESULTS In this section we present the experimental results of our approach. We have conducted experiments on both synthetic and real data, obtained from the UCI Machine Learning Repository. A set of 65 databases have been built following a Gaussian distribution with a standard deviation of 0.03, varying the number of features, dummies and clusters. 308 Simultaneous Evolutionary Optimization of Features Subset and Clusters Number GECCO ’23 Companion, July 15–19, 2023, Lisbon, Portugal Configuration Parameter Grip Value Selected POPULATION_SIZE [100, 250] 200 NUM_GENERATIONS [20, 100] 100 MUTATION_RATE [0.05, 0.3] 0.1 MUTATION_FEATURES [0.3, 0.7] 0.7 MUTATION_CLUSTERS [0.3, 0.7] 0.3 CROSSOVER_RATE [0.3, 0.7] 0.5 NUM_ELIT_CHROMOSOMES [2, 8] 2 TOURNAMENT_SIZE [2, 8] 2 K_MAX [10, 20] 18 Table 1: GA parameters. In order to establish the best value for each of the GA configuration parameters, a study of several ranges of values for each of them was performed. Both the ranges of tested values and the final parameter are shown in table 1. We have conducted experiments using Dunn and Silhouette together with different correction values as the fitness function, as explained in section 3.1. After these preliminary experiments, we have concluded that Silhouette outperforms Dunn in every configuration, being its most promising form the one in which a 𝛼=0.75 of correction has been added to the original index. 4.1 External Datasets In this section we present the results of our approach using data sets from a public repository [ 8 ]. We have selected the ID1, ID2 and ID3 databases, whose characteristics are summarized in table 2, as well as the results of our model. ID Features Clusters Selected Features Selected Clusters 𝐼 𝐷332 16 32 16 𝐼 𝐷364 16 62 (97%) 16 𝐼 𝐷3128 16 120 (94%) 16 𝐼 𝐷3256 16 219 (86%) 16 𝐼 𝐷3512 16 407 (79%) 16 𝐼 𝐷23 9 3 9 𝐼 𝐷25 9 5 9 𝐼 𝐷210 9 10 9 𝐼 𝐷215 9 14 (93%) 9 𝐼 𝐷14 2 4 2 𝐼 𝐷18 2 8 2 𝐼 𝐷116 2 16 2 𝐼 𝐷132 2 31 (97%) 2 𝐼 𝐷164 2 64 2 𝐼 𝐷1128 2 113 (88%) 2 𝐼 𝐷1256 2 187 (73%) 2 𝐼 𝐷1512 2 302 (59%) 2 Table 2: Overview table results of tests in external datasets. As it can be seen, our proposal achieves 100% accuracy in the optimal number of clusters in all tested datasets. In addition, in all the databases in which the ground truth file has been available, a confusion matrix has been used to check that each item has been assigned to its corresponding cluster, obtaining a 100% hit in these comprobations. As for the number of features, it can be seen that our approach performs an efficient selection, varying from 59% to 100% of the total number of attributes, and yet obtaining a perfect clustering. Through the application of our paradigm it has been possible to verify that it is not necessary to select the totality of the characteristics to obtain a good clustering of the data, for example, Database Features Classes Iris 4 3 Wine 13 3 Waveform 21 3 Parkinson 22 2 Sensor Readings 24 4 Steel Plates Faults 27 7 Phishing websites 30 2 Wdbc 30 2 Wpbc 32 2 Ionosphere 34 2 Statlog 36 7 Biodeg 41 2 First order 51 6 Divorce 54 2 Sonar 60 2 Table 3: Summary of the datasets used in Real Data experiments. with only 59% of the selected attributes, we continue obtaining a 100% success both in the confusion matrix and in the number of clusters, in the case of 512 features and 2 clusters. 4.2 Experiments on Real Data In this section we present the results using real databases from the UCI Machine Learning Repository [ 6 ]. We have selected a total of 15 datasets with number of features varying from 4 (Iris dataset) to 60 (Sonar dataset). Table 3 summarizes the number of features and classes of each dataset. Due to the unavailability of public clustering real datasets, together with their corresponding groupings, we have considered the number of classes in table 3 as the desired number of clusters. The same consideration has been previously assumed in other works [ 16 ]. Nevertheless, as expected, in most cases the obtained number of clusters does not match with the number of classes. For instance, the well known Iris dataset is organized in 3 different classes, while it has been proven that, according to its data distribution, its best clustering divides the data in only two different groups. Next, we present the results of applying 10 iterations of our algorithm to each dataset, letting the algorithm choose the best number of clusters. We have compared the reported Silhouette values of the obtained clusterings both with and without applying feature selection. The objective is to elucidate whether the feature selection in our algorithm outperforms the clustering considering all the variables. Table 4 presents the results on the 15 real datasets. First six columns report the mean percentages (and their corresponding deviations) of the number of selected features, the minimum and maximum numbers of selected features, the minimum and maximum numbers of obtained clusters, and the average Silhouette values (and their deviations), of 10 iterations for each dataset with F free, respectively. There exists several cases in which the algorithm reported the same elements in all the iterations. For example, for the Wine dataset, the same 10 features and 2 groupings where reported in every iteration, while for the Divorce dataset, the same 309 GECCO ’23 Companion, July 15–19, 2023, Lisbon, Portugal José David Martín, J.D. Martín, Beatriz Pontes, B. Pontes, José C. Riquelme, and J.C. Riquelme 2 groupings where reported, but with different numbers of features in different iterations. In other datasets, such as Ionosphere, not all iterations reported the same grouping nor features. Last two columns report the Silhouette value and the corresponding number of clusters of the best obtained grouping. In this case, we have selected the best value in the 10 iterations in order to contrast the results in the worst case scenario for our approach. Even in this situation, as it can be seen in table 4, applying feature selection (F free) outperforms the clusterings obtained without feature selection (Fixed F) in every dataset. In view of these results, it is also worth mentioning the case of the First order dataset, in which the same number of clusters (2) is obtained in both scenarios, but with a difference of 0.66 in their Silhouette values, meaning that our feature selection (with a mean of 47.45% of selected features) guides the algorithm to a much better clustering. Similarly, for the Waveform, Steel Plates Faults, Statlog, Divorce and Sonar datasets, the clustering with feature selection outperforms the clustering obtained with the same number of clusters (2) and the whole set of attributes. The set of features vary from a mean of 26.67% (Sonar) to 82.96% (Steel Plates Faults). Another interesting case is Parkinson, where our algorithm produces the same clustering, consisting of 2 clusters and 20 (out of 23) features, in all the iterations. This result also outperforms the best clustering obtained with the whole set of features, and corresponding to a grouping of size 10. Finally, in the case of the Iris dataset, the same Silhouette value has been reported in both situations. This is due to the small number of features in this dataset (4), where no feature selection has been performed. F Free Fixed F (best K) Database %Selected Features min F max F min C max C AVG Sil Sil C Iris 100.00(±0.00) 4 4 2 2 0.85(±0.00) 0.85 2 Wine 76.92(±0.00) 10 10 2 2 0.73(±0.00) 0.64 2 Waveform 33.81(±66.67) 6 9 2 2 0.63(±0.01) 0.46 2 Parkinson 90.91(±0.00) 20 20 2 2 0.95(±0.00) 0.71 10 Sensor Readings 20.42(±1.32) 4 5 5 14 0.84(±0.03) 0.26 10 Steel Plates Faults 82.96(±15.54) 16 25 2 2 0.95(±0.03) 0.84 2 Phishing websites 25.00(±1.76) 7 8 14 19 0.99(±0.01) 0.36 2 Wdbc 80.33(±6.18) 22 24 2 3 0.87(±0.01) 0.83 2 Wpbc 68.44(±15.41) 18 29 2 3 0.85(±0.06) 0.71 2 Ionosphere 33.82(±7.99) 7 17 2 3 0.63(±0.03) 0.42 4 Statlog 45.56(±1.94) 16 18 2 2 0.81(±0.00) 0.74 2 Biodeg 47.80(±9.43) 14 26 2 7 0.95(±0.01) 0.57 2 First order 47.45(±7.44) 16 27 2 2 0.98(±0.02) 0.32 2 Divorce 44.26(±3.20) 22 28 2 2 0.91(±0.00) 0.83 2 Sonar 26.67(±4.23) 12 21 2 2 0.81(±0.06) 0.33 2 Table 4: Results overview. CONCLUSIONS This article presents a new model for optimizing the number of clusters and features, combining in a GA the use of K-means clustering together with internal validation indices such as Dunn and Silhouette. Experiments carried out on diverse synthetic datasets have validated its usefulness, both for performing a correct clustering and for extracting the subset of most relevant attributes. It is important to highlight the high success rate in terms of the number of clusters within all the tests performed on synthetic data. An extensive experimentation on 15 real datasets from the UCI Repository has also confirmed the validity of our approach. The obtained results lead us to conclude that our proposal is a great system for determining the right number of clusters with a fairly reduced number of relevant attributes. All the material related to the implementations in this article can be found in the link https://github.com/Joseda13/ClusteringGA. ACKNOWLEDGMENTS This work has been supported by the Spanish Ministry of Science and Innovation under projects PID2020-117954RB-C22 and TED2021-131311B-C21, as well as by the Andalusian Government under proyect PYC20 RE 078 USE. REFERENCES [1] Laith Mohammad Abualigah, Ahamad Tajudin Khader, Mohammed Azmi AlBetar, and Osama Ahmad Alomari. 2017. Text feature selection with a robust weight scheme and dynamic dimension reduction to text document clustering. Expert Systems with Applications 84 (2017), 24 – 36. [2] Olatz Arbelaitz, Ibai Gurrutxaga, Javier Muguerza, Jesús M. Pérez, and Iñigo Perona. 2013. An extensive comparative study of cluster validity indices. Pattern Recognition 46, 1 (2013), 243 – 256. [3] Girish Chandrashekar and Ferat Sahin. 2014. A survey on feature selection methods. Computers Electrical Engineering 40, 1 (2014), 16 – 28. 40th-year commemorative issue. [4] D. L. Davies and D. W. Bouldin. 1979. A Cluster Separation Measure. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-1, 2 (April 1979), 224–227. [5] Renato Cordeiro de Amorim and Boris Mirkin. 2012. Minkowski metric, feature weighting and anomalous cluster initializing in K-Means clustering. Pattern Recognition 45, 3 (2012), 1061 – 1075. [6] Dua Dheeru and Efi Karra Taniskidou. 2017. UCI Machine Learning Repository. http://archive.ics.uci.edu/ml [7] J. C. Dunn. 1974. Well-Separated Clusters and Optimal Fuzzy Partitions. Journal of Cybernetics 4, 1 (1974), 95–104. [8] Pasi Fränti and Sami Sieranoja. 2018. K-means properties on six clustering benchmark datasets. , 4743–4759 pages. http://cs.uef.fi/sipu/datasets/ [9] Xiaoying Guan and Guo Chen. 2019. Sharing pattern feature selection using multiple improved genetic algorithms and its application in bearing fault diagnosis. Journal of Mechanical Science and Technology 33, 1 (2019), 129–138. [10] Emrah Hancer. 2020. A new multi-objective differential evolution approach for simultaneous clustering and feature selection. Engineering Applications of Artificial Intelligence 87 (2020), 103307. [11] E. R. Hruschka, R. J. G. B. Campello, A. A. Freitas, and A. C. Ponce Leon F. de Carvalho. 2009. A Survey of Evolutionary Algorithms for Clustering. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews) 39, 2 (2009), 133–155. https://doi.org/10.1109/TSMCC.2008.2007252 [12] Anil K. Jain. 2010. Data clustering: 50 years beyond K-means. Pattern Recognition Letters 31, 8 (2010), 651 – 666. Award winning papers from the 19th International Conference on Pattern Recognition (ICPR). [13] Marcin Kozak. 2012. A Dendrite Method for Cluster Analysis. Communications in Statistics - Theory and Methods 41, 12 (2012), 2279–2280. [14] Brad L. Miller and David E. Goldberg. 1995. Genetic Algorithms, Tournament Selection, and the Effects of Noise. Complex Systems 9 (11 1995). [15] Yongguo Liu, Mao Ye, Jun Peng, and Hong Wu. 2008. Finding the optimal number of clusters using genetic algorithms. 2008 IEEE Conference on Cybernetics and Intelligent Systems (2008), 1325–1330. [16] Parham Moradi and Mehrdad Rostami. 2015. Integration of graph clustering with ant colony optimization for feature selection. Knowledge-Based Systems 84 (2015), 144 – 161. [17] Peter J. Rousseeuw. 1987. Silhouettes: A graphical aid to the interpretation and validation of cluster analysis. J. Comput. Appl. Math. 20 (1987), 53–65. [18] Ronghua Shang, Zhu Zhang, Licheng Jiao, Chiyang Liu, and Yangyang Li. 2016. Self-representation based dual-graph regularized feature selection clustering. Neurocomputing 171 (2016), 1242 – 1253. [19] Saúl Solorio-Fernández, J. Ariel Carrasco-Ochoa, and José Fco. Martínez-Trinidad. 2016. A new hybrid filter–wrapper feature selection method for clustering based on ranking. Neurocomputing 214 (2016), 866 – 880. [20] Rui Xu and D. Wunsch. 2005. Survey of clustering algorithms. IEEE Transactions on Neural Networks 16, 3 (2005), 645–678. 310