On exploring data lakes by finding compact, isolated clusters

On exploring data lakes by finding compact, isolated clusters Patricia Jiménez a, ⇑ , Juan C. Roldán a , Rafael Corchuelo a a Universidad de Sevilla, ETSI Informática, Avda. de la Reina Mercedes, s/n, Sevilla E-41012, Spain article info Article history: Received 17 February 2021 Received in revised form 31 October 2021 Accepted 11 December 2021 Available online 15 January 2022 Keywords: Data lakes Clustering Meta-heuristics Genetic algorithms abstract Data engineers are very interested in data lake technologies due to the incredible abundance of datasets. They typically use clustering to understand the structure of the datasets before applying other methods to infer knowledge from them. This article presents the first proposal that explores how to use a meta-heuristic to address the problem of multi-way single-subspace automatic clustering, which is very appropriate in the context of data lakes. It was confronted with five strong competitors that combine the state-of-the-art attribute selection proposal with three classical single-way clustering proposals, a recent quantum-inspired one, and a recent deep-learning one. The evaluation focused on exploring their ability to find compact and isolated clusterings as well as the extent to which such clusterings can be considered good classifications. The statistical analyses conducted on the experimental results prove that it ranks the first regarding effectiveness using six standard coefficients and it is very efficient in terms of CPU time, not to mention that it did not result in any degraded clusterings or timeouts. Summing up: this proposal contributes to the array of techniques that data engineers can use to explore their data lakes. Ó2021 Elsevier Inc. All rights reserved. 1. Introduction The Web is currently the most important data source since it provides a plethora of datasets on virtually any topics. A data lake is a repository to which data engineers dump as many datasets as possible in an attempt not to miss any chances to infer new valuable knowledge [41,25,33,15]. It is then not surprising that many IT providers are competing to devise technologies that help data engineers work with their data lakes [22,4,34]. The key here is that data engineers are not expected to have any clues on the structure of the data; particularly, the data are not expected to be pre-classified. This precludes using supervised machine-learning methods directly on them and argues for using unsupervised methods on the hope to discover clusters of data that are compact, i.e., the data are similar within the clusters, and isolated, i.e., they are dissimilar amongst the clusters [18]. Every cluster is then a sub-group of data that may help data engineers understand the structure of the datasets in their data lakes. Once they are studied, they constitute the starting point to apply other machine-learning methods whose ultimate goal is to infer new knowledge [20]. That knowledge is expressed using models that capture the relationships amongst the attributes that flag a datum as belonging to one or another cluster. Much effort is currently being put on explaining the models so that data engineers can interpret them [17]. Ideally, a clustering technique must meet the following requirements in the context of data lakes: R1) it must be able to deal with business data, since typical data lakes provide datasets in which data are observations or aggregations of other data https://doi.org/10.1016/j.ins.2021.12.045 0020-0255/Ó2021 Elsevier Inc. All rights reserved. ⇑ Corresponding author. E-mail addresses: [email protected] (P. Jiménez), [email protected] (J.C. Roldán), [email protected] (R. Corchuelo). Information Sciences 591 (2022) 103–127 Contents lists available at ScienceDirect Information Sciences journal homepage: www.elsevier.com/locate/ins that cannot be assumed to be normally distributed or to have any spatial and/or temporal relationships; R2) it must be multi-way, which means that it must select a single subspace of informative attributes and cluster the original dataset in that subspace simultaneously, since single-way proposals perform these tasks independently and they are known to produce worse clusterings and multiple subspaces are often confusing for data engineers; R3) it must be able to deal with small- and high-dimensional data, since typical data lakes have datasets whose dimensionalities range from a few to thousands of attributes; R4) it must be automatic, that is, it must not require the user to provide the number of clusters manually, since the data engineer may not be assumed to know anything about the structure of the datasets; R5) it must not require per-dataset configuration, since typical data lakes provide far too many. In the literature, there are many proposals that attempt to address the previous challenges [48,21,26,23,42,7,16,46,36,2,47,14,9]. Many of them use algorithmic approaches whose goal is to find a good enough solution, but they usually have trouble to deal with large or high-dimensional datasets [11]. Many other proposals use metaheuristic approaches that map the problem onto nature-inspired processes. They are interesting insofar they can explore complex search spaces in parallel, which definitely contributes to both effectiveness and efficiency; it is then not surprising that they have found their way into many scientific and engineering problems [37,11]. Recently, some deep-learning approaches have been published and they have proven to be very effective when dealing with images, text, or sounds [35,24]. Unfortunately, meta-heuristics and deep learning are insufficiently explored; particularly, there are not any proposals to address multi-way single-subspace automatic clustering using meta-heuristics or the single- and multiple-subspace problems using deep learning. This article presents RóMULO, which explores the research niche regarding using meta-heuristics. It was confronted with five strong competitors that integrate the state-of-the-art GSPPCA method [8] to find subspaces of informative attributes and several methods to perform the clustering, namely: Affinity-Propagation, Mean-Shift, and OPTICS-Xi, which are classical proposals, as well as PQC, which is a quantum-inspired proposal [12], and DCC, which is a deep-learning proposal [43]. The evaluation focused on two key points, namely: first, exploring their ability to find compact and isolated clusterings, which was evaluated on 46 real-world data lakes with a total of 2561 datasets that provide 15435171 unclassified data; second, exploring the extent to which such clusterings can be considered good classifications, which was evaluated on five additional data lakes with a total of one hundred datasets that provide 1200552 pre-classified data. The comparison was performed in terms of both effectiveness and efficiency. Regarding effectiveness, six standard coefficients were computed, namely: Silhouette, Davies-Bouldin, Calin ´ski-Harabasz, Adjusted Rand, Fowlkes-Mallows, and Accuracy. Regarding efficiency, the CPU time was used as the main measure. Additionally, the ratio of degraded clusterings and the ratio of timeouts were computed. The experimental results were studied using a statistically sound method, which confirmed that RóMULO ranks at the first position regarding the six effectiveness coefficients and it is very efficient for practical purposes; furthermore, it was the only proposal that did not result in any degraded clusterings or timeouts. The rest of the article is organised as follows: Section 2analyses the related work; Section 3describes the details of the proposal; Section 4presents the experimental analysis; finally, Section 5concludes the article. 2. Related work This section reports on the most closely-related work. First, it introduces a conceptual framework that homogenises the vocabulary in this area; then, the literature is reviewed along two axes: single-way versus multi-way proposals; finally, there is a discussion that makes it clear the motivation behind RóMULO. 2.1. Conceptual framework A dataset is a set of the form fx 1 ;x 2 ;...;x n g, where each x i is a d-dimensional vector of attributes x i ¼ðx i;1 ;x i;2 ;...;x i;d Þ (nP0;dP1;16i6n). Clustering dataset Xseeks to find kclusters (1 6k6n) such that they are as compact (high intra-similarity) and isolated (low inter-similarity) as possible [10]. The problem can be formalised as the following optimisation problem: max fðX;M;CÞ st X k j¼1 M½i;j>016i6n 06M½i;j6116i6n;16j6k C½j2P 1 XP 1 ðARÞ16j6k where fdenotes a fitness function, Xdenotes the input dataset, Mdenotes a membership matrix, Cdenotes a clustering, and A denotes a set of attributes. As usual, P 1 denotes the non-empty powerset and Rdenotes the real numbers. The fitness function helps assess how compact and isolated the clusters are. In the literature, there are many choices to implement it. They range from simple coefficients to multi-objective functions [47,5,19,30,27,31]. Some coefficients can be computed on the clusterings themselves because they focus on compactness and isolation only, but other coefficients require the clustering plus a ground truth because they also measure the extent to which the clustering can be used to classify the P. Jiménez, J.C. Roldán and R. Corchuelo Information Sciences 591 (2022) 103–127 104 data into a number of pre-defined classes. They all can be used to assess the same clustering from different, complementary perspectives, which argues for a means to combine them using multi-objective functions. The Lexicase method is such a multi-objective function and it was specifically designed to work in the context of genetic search strategies [19,27]. The membership matrix Mhas nrows and kcolumns; intuitively, M½i;jindicates if the i-th datum in Xbelongs to cluster C½jor not (n¼jXj;16k6n;16i6n;16j6k). A clustering proposal is hard if it assigns every datum to a single cluster ( 8 16i6n:9 1 16j6k:M½i;j¼1) and overlapping otherwise ( 8 16i6n:916j6k:M½i;j>0). The latter can be crisp if the membership matrix is Boolean ( 8 16i6n: 8 16j6k:M½i;j2f0;1g) or fuzzy if it is a likelihood matrix ( 8 16i6n: 8 16j6k:06M½i;j61). The components of clustering C½jare pairs of the form ðX 0 ;A 0 Þ, where X 0 denotes a non-empty subset of the input dataset X and A 0 is a non-empty subset of AR(1 6j6k;16k6n;n¼jXj). Intuitively, X 0 denotes the subset of data in a particular cluster and A 0 denotes a set of pairs ða i ;w i Þin which each a i refers to an attribute and each w i to a weight that represents how informative it is (1 6i6d;dP1). A clustering proposal is single-way [23,47] if it clusters the data using all of the input attributes, i.e., A 0 ¼fða i ;1Þg d i¼1 (dP1); it is multi-way [23,46,14,9] if it finds the subspace of most informative attributes and clusters the datasets simultaneously, i.e., A 0 ¼fða i ;w i Þg d i¼1 (dP1;06w i 61). The latter can be further subclassified as crisp or fuzzy depending on whether the weights are Boolean or real. The single-way proposals must necessarily rely on a pre-processor that selects the informative attributes [28,8], but Jain [23] found out that this typically results in worse clusterings. A proposal is single-subspace if all of the clusters refer to the same subspace of attributes; it is multiple-subspace if each cluster may refer to a different subset of attributes. A proposal is manual if the user must provide the number of clusters to find beforehand; it is automatic if it can find the number of clusters automatically. Clustering is inherently complex from a computational point of view. A basic hard single-way manual proposal has to explore a search space whose size is the Stirling partition number [3,47], namely: Sðn;kÞ¼1 k!X k i¼0 ð1Þ ki k i  i n : If the number of clusters kis not known beforehand, then the search must be performed in a larger space whose size is the Bell number, namely: BðnÞ¼X n k¼0 Sðn;kÞ: The search space grows by Oð2 d Þin multiple-subspace clustering problems with regard to single-subspace problems because there are 2 d 1 non-empty subsets of attributes in a dataset with d-dimensional data (dP1). Thus, in a data engineering context, it does not generally make sense to try to find the optimal solution to a clustering problem, but an approximate solution that is good enough for practical purposes. 2.2. Single-way clustering Originally, most approaches to single-way clustering were algorithmic, but meta-heuristic approaches have found their way into this field because their nature-inspired approaches help explore complex search spaces using multi-core and/or multi-threaded CPUs. Recently, some proposals that are based on deep learning have also found their way into clustering, with a focus on unstructured data like images, text, or sounds. Fig. 1 summarises the existing approaches; the labels on the vertical axis describe the approach and the bars show the total number of proposals grouped by several temporal periods. The surveys by Jain [23] and Xu and Tian [47] focus on algorithmic approaches. The most common ones are the following: a) data distribution, which assumes that the clusters can be identified by finding sub-distributions of data; b) model fitting, which generalises the previous idea to arbitrary statistical models whose parameters are fit to the data; c) density of data, which assumes that clusters are high-density groups of data; d) graph theory, which assumes that the data are the nodes of a graph in which the edges represent distance-based relationships amongst them; e) grid search, which assumes that the data may be arranged in a grid in which the clusters are squared groups of data; f) k-means variants like bisecting k-means, kdmeans, single-pass k-means, k-medoids, kernel k-means, sort-means, k-harmonic means, or x-means; g) fractal theory, which assumes that the clusters are subgroups that share some geometric properties with the whole dataset; h) kernel functions, which project the input data onto higher-dimensionality attribute spaces in which clusters can be made apart easily; i) ensemble modelling, which first generates candidate clusters using other techniques and then merges the results using consensus functions; j) spectral graph theory, which addresses the problem as a graph partitioning problem; k) affinity propagation, which computes the centroids of the clusters as the data with the highest affinity to the other data; l) quantum mechanics, which maps the clustering problem onto some phenomena that are formalised using Schrödinger’s equation; and m) hybrid approaches that have managed to successfully combine two or more of the previous ones. The surveys by Hruschka et al. [21], Bong and Rajeswari [7], Rana et al. [42], Alam et al. [2], Nanda and Panda [36], García and Gómez-Flores [14], and Figueiredo et al. [13] focus on meta-heuristic approaches. The most common ones are the following: a) evolutionary approaches, which are based on genetic algorithms, evolutionary strategies, genetic programming, or P. Jiménez, J.C. Roldán and R. Corchuelo Information Sciences 591 (2022) 103–127 105 differential evolution; b) physical approaches, which are based on simulated annealing, memetic algorithms, harmony search, shuffled frog leaping, quantum theory, gravitational search, or river dynamics; c) collective-intelligence approaches, which are based on ant colonies, particle swarms, bee swarms, fish swarms, cat swarms, or invasive weeds; and d) bioinspired approaches, which are based on artificial immunity, bacterial foraging, or fireflies. The surveys by Min et al. [35] and Karim et al. [24] focus on deep-learning approaches, which can be grouped as follows: a) proposals that use an auto-encoder to compute a latent attribute space on which clustering techniques like k-means have proven to work better than on the original datasets; b) proposals that use variational auto-encoders, which learn the distribution model of the input data so that it can be used to generate new synthetic data for learning purposes; c) proposals that rely on fully connected networks, convolutional networks, and deep-belief networks that must be trained using two complementary loss functions; and d) proposals that rely on min–max adversarial games between two neural networks, namely: a generative network that generates both similar and dissimilar synthetic data regarding a particular cluster and a discriminative network that learns to classify a new datum as belonging to that cluster or not. 2.3. Multi-way clustering Jain [23], Sim et al. [46], García and Gómez-Flores [14], and Deng et al. [9] surveyed the existing multi-way clustering proposals, which can be subclassified according to whether they attempt to find the clusters in a single or multiple subspaces. Most proposals use algorithmic approaches, only a few use meta-heuristic approaches, and none uses a deeplearning approach, cf. Fig. 2. Fig. 1. Single-way clustering proposals. P. Jiménez, J.C. Roldán and R. Corchuelo Information Sciences 591 (2022) 103–127 106 Regarding the algorithmic approaches to single-subspace clustering, there are only two: a) the separate-feature approach, which learns the weights of the attributes before finding the clusters, and b) the coupled-feature approach, which learns the weights of the attributes during the clustering process. Regarding the multiple-subspace problem, there are a few more algorithmic approaches, namely: a) projected clustering, which relies on distance functions and/or data patterns; b) subspace clustering, which aims at finding all possible clusters in all possible subspaces; c) projection/subspace approaches, which somewhat combine the previous approaches; d) multiweight k-means, e) multi-weight fuzzy c-means, and g) probability mixture, which are somewhat inspired by the classical single-way counterparts; finally, h) there are some miscellaneous approaches that address the three most important problems with the previous ones, namely [26,9]: they focus on cluster compactness and neglect cluster isolation, they are very sensitive to the configuration parameters, and they do not deal well with datasets with clusters of diverging sizes. Regarding the meta-heuristic approaches to single-subspace clustering, no proposal was found in the literature. Regarding multiple-subspace clustering, there are three approaches, namely: a) co-evolutionary clustering, which leverages attribute weighting methods to deal with complex data and noisy and correlated attributes; b) particle swarm, which seeks for near-optimal variable weights for a given objective function; and c) multi-objective evolution, which benefits from both the merits of crisp subspace clustering and the good properties of the multi-objective optimisation-based approach for fuzzy clustering. Unfortunately, the previous approaches have stability problems that hinder applying them to many real-world datasets [26,9]. Fig. 2. Multi-way clustering proposals. P. Jiménez, J.C. Roldán and R. Corchuelo Information Sciences 591 (2022) 103–127 107 Realise that there are not any deep-learning approaches to multi-way clustering since such techniques are not intended to select any informative attributes, but to transform the original attributes into so-called latent attributes. They somewhat encode the original attributes by aggregating the results output by several neurons on the hope that other techniques, including clustering, become more effective and/or efficient when working on them. The latent attribute space is then not generally expected to be understood by a data engineer; contrarily, a subspace of the original attributes helps data engineers focus on the informative attributes that he or she needs to understand in order to grasp the structure of a dataset. 2.4. Discussion The ideal clustering technique in the context of data lakes must meet the following requirements: R1: Must be able to deal with business data. Typical data lakes provide business data that represent real-world entities or events by means of vectors with many attributes. They can be observations or aggregations of other data that cannot be assumed to be normally distributed or to have any spatial and/or temporal relationships. They may also include unstructured data like images, text, or sounds, which can be dealt with using specific-purpose proposals [39]. R2: Must perform multi-way clustering. Typical data lakes provide many attributes that are uninformative regarding the structure of the data and make it difficult for data engineers to find it. Single-way proposals require a pre-processor to find the most informative attributes and then cluster the dataset that results from projecting the original dataset onto that subspace; multi-way proposals find the subspace of attributes and cluster the projected datasets simultaneously, which has been proven to produce better results [23]. R3: Must deal with high-dimensional data. High data dimensionality is problematic because of two reasons [48,3,47,9]: on the one hand, many attributes might be uninformative and introduce noise that does not help the data engineer understand the structure of the data or the clustering algorithm to find good clusters; on the other hand, more attributes means more inefficiency and more chances to miss the important attributes and the relationships amongst them that help find good clusters [29]. R4: Must not require the user to provide the number of clusters. This means that the proposal must be able to guess the number of clusters in the input datasets automatically and not require the user to set it beforehand. This is the case of data lakes, since data engineers cannot be assumed to have any prior knowledge of the datasets in their data lakes, but their topic. Unfortunately, not knowing the number of clusters beforehand is known to increase the size of the search space exponentially [38,1], which is even more problematic in the context of data lakes as the size of the datasets increases. R5: Must not require per-dataset configuration. Finding the appropriate values of the configuration parameters typically requires to perform grid search, which is an inherently costly and difficult procedure [29]. Furthermore, fine-tuning the configuration parameters may induce a particular clustering instead of finding the actual clusters in the dataset [46].In the context of data lakes, there are typically too many datasets, which implies that fine-tuning the configuration parameters for each particular dataset is not generally a good idea. The analysis of the literature in the previous sections reveals that there are many clustering proposals that might well meet the previous requirements. What shines in this analysis is that there are some clear research niches, cf. Figs. 1 and 2, namely: using meta-heuristics to address the multi-way single-subspace problem or deep-learning to address the multi-way single- or multiple-subspace problem. This article presents a proposal that explores the first research niche and meets the previous requirements. A quick reader might think that single-subspace clustering is not an actual problem since one might use a multiplesubspace technique and then select the best subspace. That is not possible due to a subtle, but very important difference between single- and multiple-subspace clustering. Single-subspace clustering refers to finding one subspace of attributes in which the best possible clustering can be computed; note that a proposal like RóMULO can find multiple subspaces and clusterings, but returns the best one, which is typically more than enough for practical purposes. What matters here is that the best subspace (or the suboptimal ones) results in complete clusterings of the original dataset. Contrarily, multiple-subspace clustering refers to finding multiple clusters in likely different subspaces of attributes; there is not generally a best subspace because all of the subspaces complement each other to produce a set of clusterings of the original dataset. Selecting just one of the subspaces returned leads to a partial clustering of the original dataset. The idea of returning multiple complementary clusterings in the context of data lakes is not that appealing since the ultimate goal is to help a data engineer understand his or her datasets and to infer new knowledge from them. The more compact and isolated the data returned and the less dimensions is generally the better because this helps focus on groups of similar data. Finally, it is worth mentioning that a reviewer highlighted a possible connection between clustering in the context of data lakes and so-called collaborative fuzzy clustering [40,44]. This technique was devised to deal with multiple datasets that provide complementary data, but cannot be merged, e.g., because of legal or performance issues. Collaborative fuzzy clustering is a very good clustering technique in that context, but it is not generally applicable in the context of data lakes because of the following reasons: it assumes that the datasets have the same attributes, it does not compute a subspace of informative attributes, and it requires the number of clusters to be set beforehand. P. Jiménez, J.C. Roldán and R. Corchuelo Information Sciences 591 (2022) 103–127 108 3. The algorithm Algorithm1: The main method of RóMULO. This section introduces the algorithm behind RóMULO. Algorithm1 sketches its main method and illustrates it using a graphical abstract. It works on an input dataset Xand outputs a subspace of attributes Aand a clustering C. The method performs three steps in sequence: computing the initial population, evolving it, and computing the results. For the sake of readability, the configuration parameters of RóMULO are introduced as constants that are denoted using uppercase, multi-letter identifiers. Algorithm2: Method to generate a population. method generatePopulation(X) returns P n:¼jXj d:¼dim X P:¼£ repeat PSIZE times k:¼uniformð2;dn=2eÞ A:¼ðbernoullið0:50Þ;... d ;bernoullið0:50ÞÞ P:¼P[fðk;AÞg end end The first step consists in generating a population Pwith PSIZE individuals, cf. Algorithm2. Generally speaking, the individuals are expected to encode the information that the meta-heuristic requires to make decisions regarding how to explore the search space. Since RóMULO outputs a number of clusters and a subspace of attributes, then the search space consists of tuples of the form ðk;AÞ, where kdenotes the number of clusters and Ais a Boolean vector that encodes the attributes that must be used to compute the clusters. The method first initialises nand dto the number of data and attributes in the input dataset X, respectively, and Pto an empty set. It then iterates to generate a population with PSIZE individuals in set P. The individuals are generated with random numbers of clusters (which are drawn from a Uniform distribution in interval ½2;n=2, where ndenotes the number of data in the input dataset), and random subspaces of attributes (which are drawn from a Bernoulli distribution with mean 0:50, i.e., every attribute has the same chances to be selected). The second step consists in evolving the initial population NGEN times using a ðMU þLAMBDAÞgenetic strategy [6]. The evolution is performed by generating dLAMBDAPSIZEeoffsprings and then selecting the best dMU PSIZEeindividuals to create the new generation. Both LAMBDA and MU are introduced as percentages of the initial population size. P. Jiménez, J.C. Roldán and R. Corchuelo Information Sciences 591 (2022) 103–127 109 Algorithm3: Method to generate the offspring. method generateOffspring(P) returns S:¼£ repeat dLAMBDA PSIZEetimes if bernoulliðCXPBÞthen x;y:¼crossover(P) S:¼S[fx;yg else if bernoulliðMUTPBÞthen x:¼mutate(P) S:¼S[fxg else fxg:¼pickðP;1Þ S:¼S[fxg end end end Algorithm3 shows the method that generates the offspring. It iterates a total of dLAMBDAPSIZEetimes and produces the offspring as follows: it first determines if two new offsprings must be generated by crossing two existing individuals, which happens according to a Bernoulli random variable with mean probability CXPB; if crossing is not selected, then the method determines if a new offspring must be generated by mutating an existing individual, which happens according to a Bernoulli random variable with mean probability MUTPB; if neither crossing nor mutation are selected, then one random individual is picked from the population and cloned. (In the pseudo-code, pickðk;PÞdenotes a random subset of kdifferent individuals from population P.). Algorithm4: Method to crossover two individuals. method crossover(P) returns (x 0 ;y 0 ) fx;yg:¼pickðP;2Þ (k 1 ;A 1 ):¼x (k 2 ;A 2 ):¼y d:¼dim P p:¼uniformð1;d1Þ x 0 :¼(k 2 ;A 2 ½1:pA 1 ½pþ1:d) y 0 :¼(k 1 ;A 1 ½1:pA 2 ½pþ1:d) end Algorithm4 presents the method to perform crossover. First, it picks any two individuals xand yfrom population Pand extracts their components ðk 1 ;A 1 Þand ðk 2 ;A 2 Þ. Next, it computes the number of attributes din population Pand generates a random natural pin interval ½1;d1. Then it generates the following offsprings: x 0 ¼ðk 2 ;A 2 ½1:pA 1 ½pþ1:dÞ and y 0 ¼ðk 1 ;A 1 ½1:pA 2 ½pþ1:dÞ, where v ½i:jdenotes the slice of vector v from its i-th position up to its j-th position and v udenotes the catenation of vectors v and u. Summing up, the offsprings exchange the number of clusters in their parents and a part of their subspaces of attributes. Algorithm5: Method to mutate an individual. method mutate(P) returns x 0 fxg:¼pickðP;1Þ (k;A):¼x k 0 :¼uniformðk1;kþ1Þ p:¼uniformð1;jAjÞ d:¼dim P A 0 :¼A½1:p1ðnot A½pÞ  A½pþ1:d x 0 :¼(k 0 ;A 0 ) end P. Jiménez, J.C. Roldán and R. Corchuelo Information Sciences 591 (2022) 103–127 110 Algorithm5 presents the method to perform mutation. First, it picks an individual xfrom population Pand extracts its components ðk;AÞ. Next, it computes a random natural in interval ½k1;kþ1, which will be used as the number of clusters in the offspring; it also computes a random natural in interval ½1;jAj that represents the attribute to be mutated in the offspring. Finally, it assembles and returns the new offspring. Once the new offspring has been generated, the ðMU þLAMBDAÞgenetic strategy selects the best dMU PSIZEeindividuals from both the current population and the offspring. It is implemented using the version of the Lexicase method that was described by Cava et al. [27]. Helmuth et al. [19] published an in-depth analysis of Lexicase; their conclusion was that this method is very appropriate in cases in which it is not easy to aggregate multiple quality indicators into a single value. This is the case of RóMULO, whose search strategy seeks to minimise the number of clusters and to maximise the Silhouette coefficient, to minimise the Davis-Bouldin coefficient, and to maximise the Calin ´ski-Harabasz coefficient. Intuitively, it seeks to minimise the number of clusters since the smaller number of clusters the easier for a data engineer to understand them; it seeks to optimise the other coefficients because they are known to achieve their best values when the clusters are compact and isolated. Aggregating the four indicators into a meaningful single value is not easy because they range in different intervals whose lower and upper bounds do not have homogeneous interpretations. In such cases, the Lexicase method provides a good solution to implement a multi-objective fitness function. Note that selecting the best individuals requires to evaluate them using the three previous coefficients. Simply put: the original dataset must be projected onto the subspace of attributes selected by each individual and then the projection must be clustered using any applicable proposal in the literature. Note that the decision on which exact proposal must be used requires some experimentation, which is the reason why it is deferred to the section on the experimental analysis. The main loop of the algorithm evolves the initial population NGEN times. When it finishes, the best individual from the last population is selected. Let that individual be ðk;AÞ. The main method then projects the input dataset onto the subspace of attributes denoted by Aand then clusters the resulting projection using the same method used to compute the coefficients that guide the search process. 4. Experimental analysis This section presents the details behind the experimental analysis, namely: first, the experimental setting is described; then, the configuration procedure is explained; next, the experimental methodology is introduced; after that, the experimental results regarding clustering power are presented; finally, the experimental results regarding classification power are also presented. 4.1. Experimental setting RóMULO 1 was implemented using Python 3.7.6 and several components: DEAP 1.3.1 to implement the meta-heuristic, Pandas 1.0.3 to implement the datasets, NumPy 1.18.2 to implement vector and matrix operations, and Scikit-Learn 0.24.2 to leverage the implementation of some classical clusterers and to compute performance measures; the implementations of GSPPCA [8], PQC [12], and DCC [43] were provided by their authors. The experiments regarding the ability to find compact and isolated clusterings were run on a collection of 46 data lakes that provide 15435171 unclassified data that are grouped into 2561 datasets. They were sampled from several open-data governmental repositories (Brazil, Canada, France, Spain, USA, and UK) and several reputed organisations (Kaggle, UCI, World Bank, and World Health Organisation). Table 1 provides a description in terms of name, number of datasets, number of data, number of attributes, and ratio of informative attributes according to GSPPCA. The data lakes have an average of 55:67 datasets, with a global minimum of four datasets and a global maximum of 531 datasets. They range in average size from 556:28 to 7632:70 data per dataset, with an average of 3755:78 data, a global minimum of three data, and a global maximum of 43828 data; the average number of attributes ranges from 38:76 to 2995:02 attributes per dataset, with an average of 477:64 attributes, a global minimum of three attributes, and a global maximum of 69166 attributes. The average ratio of informative attributes ranges from 0:19 to 0:87 per dataset, with an average of 0:55, a global minimum smaller than 0:01, and a global maximum that equals 1:00. As of the time of writing this article, this is the largest experimentation repository in the context of data lakes. These data were not pre-classified because they are business data without any particular purposes. The experiments regarding the extent to which the clusterings returned by RóMULO or the competitors can be considered good classifications were run on five additional data lakes that provide 1200552 pre-classified data that are grouped into 100 datasets. They were randomly sampled from the open-data repositories by Kaggle, OpenML, and the UCI, plus some standard evaluation datasets from Scikit-Learn and some common synthetic datasets. Table 2 summarises them: the data lakes have an average of 20:00 datasets, with a global minimum of four datasets and a global maximum of 53 datasets. They range in average size from 154:60 to 35461:20 data per dataset, with an average of 7674:36 data, a global minimum of seven data, and a global maximum of 52619 data; the average number of attributes ranges from 15:60 to 3465:20 attributes per dataset, with an average of 520:96 attributes, a global minimum of two attributes, and a global maximum of 10000 attributes. The 1 RóMULO and the experimental data lakes are available at https://doi.org/10.17632/y5v2zy356t.1. P. Jiménez, J.C. Roldán and R. Corchuelo Information Sciences 591 (2022) 103–127 111 with roughly ten thousand 4570-dimensional data. The problem with this dataset is that the data are too deeply interwoven 2 and RóMULO could not find a single subspace to make them apart. In this particular case, the competitors based on OPTICS- Xi and PQC failed to produce any results and the competitor based on DCC attained a coefficient of 0:79, but the competitors Table 8 Clustering power: Degradation. 2 The datasets in which RóMULO performed the worst were explored as follows: they were projected onto 100 random subspaces of attributes varying the ratio of selected attributes from 10%to 100%in equally-sized increments; the projections were then re-projected onto a three-dimensional space using the well-known t-SNE method; the resulting data were analysed visually and clustered using the three classical methods in the experimental study. If the experimenter could not spot any compact and isolated clusters and the clusterings computed were degraded or resulted in very poor effectiveness coefficients, the conclusion was then that the data in those datasets are too deeply interwoven. That makes it difficult to set them apart without the help of a data engineer who can really understand the meaning of the data and performs some attribute engineering. P. Jiménez, J.C. Roldán and R. Corchuelo Information Sciences 591 (2022) 103–127 118 based on Affinity-Propagation and Mean-shift attained positive results; the latter were designed to find the clusters by selecting a number of data that is grown/shifted to form the clusters using affinity/density criteria, which generally helps them identify the clusters in the subspace of attributes returned by GSPPCA more easily than RóMULO can do on the original attributes. The statistical analysis confirms that RóMULO ranks at position 2:39 and it is followed by the competitors based on Mean-Shift at position 2:44, Affinity-Propagation at position 2:92, OPTICS-Xi at position 3:74, DCC at position 4:20, and PQC at position 5:31. The p-value returned by the statistical tests is zero or nearly zero in each comparison, which is a strong indication that the experimental results support the hypothesis that RóMULO ranks the first regarding the Silhouette coefficient. Regarding the Davies-Bouldin coefficient, cf. Table 5, RóMULO ranks at the first position and it is followed by the competitors based on Mean-Shift, Affinity-Propagation, OPTICS-Xi, DCC, and PQC. RóMULO attains an average Davies-Bouldin Table 9 Clustering power: Timeouts. P. Jiménez, J.C. Roldán and R. Corchuelo Information Sciences 591 (2022) 103–127 119 coefficient of 1:95, with a minimum that is nearly zero and a maximum of 12:25. The maximum occurs in a dataset from the ‘‘WiFi Hotspots” data lake with roughly thirteen thousand 18-dimensional data. Note that the dataset is relatively large in data, but small in dimensionality. The problem with this dataset is that the data are too deeply interwoven in all possible subspaces, which resulted in very bad results using all of the competitors. In this particular case, the competitors based on Mean-Shift and PQC failed to produce any results; the competitors based on OPTICS-Xi and DCC produced clusterings with the highest Davies-Bouldin coefficients; the exception was the competitor based on Affinity-Propagation which attained a coefficient as small as 0:80 but output a large number of small clusters due to its approach to select a subset of data and grow/shift them to form the clusters. The statistical analysis confirms that RóMULO ranks at position 2:42 and it is followed by the competitors based on Mean-Shift at position 2:50, Affinity-Propagation at position 2:84, OPTICS- Xi at position 3:13, DCC at position 4:76, and PQC at position 5:35. Note that the p-value returned by the statistical tests is zero or nearly zero in each comparison, which is a strong indication that the experimental results support the hypothesis that RóMULO ranks the first regarding the Davies-Bouldin coefficient. Regarding the Calin ´ski-Harabasz coefficient, cf. Table 6, RóMULO ranks at the first position and it is followed by the competitors based on Affinity-Propagation, Mean-Shift, OPTICS-Xi, DCC, and PQC. RóMULO attains an average Calin ´ski-Harabasz coefficient of 197:08, with a minimum of 0:74 and a maximum of 993:36. The minimum occurs in a dataset from the ‘‘WiFi Hotspots” data lake with six 14-dimensional data. This is a very small dataset both in terms of number of data and attributes, but there is not a single subspace in which good clusters can be found because the data are deeply interwoven regarding all of the attributes. In this particular case, the competitors returned degenerated clusterings. The statistical analysis confirms that RóMULO ranks at position 2:12 and it is followed by the competitors based on Affinity-Propagation at position 2:67, Mean-Shift at position 2:94, OPTICS-Xi at position 3:17, DCC at position 4:78, and PQC at position 5:32. Note that the pvalue returned by the statistical tests is zero in each comparison, which is a strong indication that the experimental results support the hypothesis that RóMULO ranks the first regarding the Calin ´ski-Harabasz coefficient. Regarding efficiency, cf. Table 7, RóMULO ranks at the fifth position. The statistical tests return a zero p-value for every comparison, which is a strong indication that the differences in rank are significant. Clearly, the search strategy used in RóMULO has a negative impact on its efficiency, which is clearly compensated because of its ability to find better clusterings. Table 10 Classification power: Adjusted Rand. P. Jiménez, J.C. Roldán and R. Corchuelo Information Sciences 591 (2022) 103–127 120 Note that the experiments run with RóMULO took from a minimum of 0:01 minutes to a maximum of 187:20 minutes. The minimum was achieved on the smallest datasets; the maximum occurred on a dataset in the ‘‘Steller Sea Lions” data lake that has 37270 data with 181 attributes each. Note that this is not the largest dataset in the experimental repositories, but one in which RóMULO could not easily find the appropriate subspace of informative attributes. The other proposals were also inefficient when working on this dataset and the reason was, again, that it provides many uninformative attributes that result in too deeply interwoven data. Note, too, that the timings vary significantly from data lake to data lake; recall that they consists of real-world datasets whose size ranges from an average minimum of 556:28 data to an average maximum of 7632:70 data per data lake and whose dimensionalities range from an average minimum of 38:76 attributes to an average maximum of 2995:02 attributes; inevitably, that has an important impact on the variance of the clustering time. Tables 8 and 9 report on the ratio of degraded clusterings and timeouts, respectively. Note that RóMULO is the only proposal that attains 0:00 degradation ratio and 0:00 timeout ratio. The reason is that its search strategy quickly discards individuals that result in degraded clusterings and focus on promising candidates without timing out. Regarding the ratio of degraded clusterings, it is closely followed by the competitors based on Affinity-Propagation and OPTICS-Xi with an average ratio of 0:03, and then come the competitors based on PQC with an average ratio of 0:08, DCC with an average ratio of 0:10, and Mean-Shift with an average ratio of 0:11. Regarding the ratio of timeouts, it is identical to the competitor based on DCC with a ratio of 0:00, it is closely followed by the competitors based on Mean-Shift with an average ratio of 0:02, OPTICS-Xi with an average ratio of 0:05, and then come the competitors based on Affinity-Propagation with an average ratio of 0:17 and PQC with an average ratio of 0:78. The conclusion is that RóMULO ranks the first regarding the Silhouette, the Davies-Bouldin, and the Calin ´ski-Harabasz coefficients. It is closely followed by the competitors based on Affinity-Propagation and Mean-Shift and then come the competitors based on OPTICS-Xi, DCC, and PQC. It performs quite well regarding efficiency and does not result in any degraded clusterings or timeouts. The statistical analysis confirmed that the differences in rank are significant. 4.5. Analysis of classification power Tables 10–15 summarise the results regarding the extent to which the clusterings returned by RóMULO and the competitors can be considered good classifications. The structure of these tables is the same as before. Table 11 Classification power: Fowlkes-Mallows. P. Jiménez, J.C. Roldán and R. Corchuelo Information Sciences 591 (2022) 103–127 121 Regarding the Adjusted Rand coefficient, cf. Table 10, RóMULO ranks at the first position and it is followed by the competitors based on Affinity-Propagation, Mean-Shift, OPTICS-Xi, DCC, and PQC. RóMULO attains an average Adjusted Rand coefficient of 0:04, with a minimum of 0:12 and a maximum of 1:00. The minimum occurs in a dataset from the ‘‘OpenML” data lake that has seven 1024-dimensional data with three classes. The other competitors attained similar values for this coefficient, ranging from the competitor based on Affinity-Propagation, which attained exactly the same value, to the competitor based on DCC, which attained a value of 0:01. Note that this is a particularly difficult dataset 3 because there are too few data, but they are highly dimensional and the number of sample data per class is very low; simply put, this dataset provides little evidence to learn a good classifier. The best value was attained on a dataset from the ‘‘Kaggle” data lake with roughly three hundred 21-dimensional data with two classes. The other competitors attained a value that was nearly 0:00 with this dataset, which is peculiar since there are many pairs of attributes that result in perfect linear classifiers. Such attributes are quickly discovered by RóMULO; unfortunately, GSPPCA selects five attributes whose values are too interwoven and make it difficult for the competitors to make the classes apart. The statistical analysis confirms that RóMULO ranks at position 2:46 and it is followed by the competitors based on Affinity-Propagation at position 2:83, Mean-Shift at position 3:33, OPTICS-Xi at position 3:56, DCC at position 4:25, and PQC at position 4:59. Note that the p-value returned by the statistical tests is below the significance level in every comparison, which supports the hypothesis that RóMULO ranks the first regarding the Adjusted Rand coefficient. Regarding the Fowlkes-Mallows coefficient, cf. Table 11, RóMULO ranks at the first position and it is closely followed by the competitor based on Mean-Shift; then come the competitors based on OPTICS-Xi, Affinity-Propagation, PQC, and DCC. RóMULO attains an average Fowlkes-Mallows coefficient of 0:38, with a minimum of 0:01 and a maximum of 1:00. The worst value is attained with a dataset from the ‘‘OpenML” data lake that provides 21427 data with 18 attributes and 287 classes. The competitors based on Affinity-Propagation, PQC, and DCC timed out with this dataset; only the competitors based on Mean-Shift and OPTICS-Xi could process it and they attained a Fowlkes-Mallows coefficient of 0:11 and 0:08, respectively. Table 12 Classification power: Accuracy. 3 The datasets in which RóMULO performed the worst were explored as follows: a ROC analysis was performed using Random Forest (tree learning), J4.8 (rule learning), Naive Bayes (Bayesian learning), and a five-layer Perceptron (neural leaning); k-means was also run by setting kto the number of classes in the corresponding dataset. The data were considered too deeply interwoven if the average ROC coefficient was close to 0:50, which basically indicates that the classifiers learnt make random predictions, or if the effectiveness coefficients were very poor. Such datasets are particularly difficult to deal with because they require a data engineer who can really understand their meaning to perform some attribute engineering. P. Jiménez, J.C. Roldán and R. Corchuelo Information Sciences 591 (2022) 103–127 122 The dataset was inspected and the conclusion was that the attributes had very few different values, which made it really difficult to make the 287 classes apart; note that it was not a problem with the amount of data, which is relatively large, but the few attributes and values in comparison with the relatively large number of classes. The best value was attained with the same dataset that maximised the Adjusted Rand coefficient; the competitors behaved similarly regarding the Fowlkes- Mallows coefficient. Basically, RóMULO could easily find the subspace of attributes that helps make the classes apart, but GSPPCA selected five attributes that did not help in this task. The statistical analysis confirms that RóMULO and the competitor based on Mean-Shift share the first position in the ranking because the p-value from their comparison is above the significance level; then come the competitors that are based on OPTICS-Xi, Affinity-Propagation, PQC, and DCC, whose comparisons result in statistically-significant differences because the returned p-values are zero or nearly zero. Regarding the Accuracy coefficient, cf. Table 12, the competitor that is based on Affinity-Propagation ranks at the first position and it is followed by RóMULO and the competitors that are based on Mean-Shift, OPTICS-Xi, DCC, and PQC. RóMULO attains an average Accuracy coefficient of 0:53, with a minimum of 0:02 and a maximum of 1:00. The worst value is attained in a dataset from the ‘‘OpenML” data lake that has 1480 data with 10000 attributes and 50 classes. The competitors based on PQC and DCC timed out on this dataset and the competitors based on Mean-Shift and OPTICS-Xi attained the same accuracy as RóMULO on it; only the competitor based on Affinity-Propagation could attain an accuracy of 0:40. The dataset was inspected and the conclusion was that its data are, again, far too interwoven to make the classes clearly apart using clustering; neither was RóMULO able to find any good subspaces of attributes. The best value was attained with the same dataset as was the case regarding the previous coefficients. The statistical analysis confirms that the competitor based on Affinity- Propagation ranks at the first position and it is closely followed by RóMULO, which is statistically indistinguishable from it because the p-value returned by Hommel’s test is above the significance level; then come the competitors that are based on Mean-Shift, OPTICS-Xi, DCC, and PQC, whose comparisons result in statistically-significant differences because the returned p-value is below the significance level in each case. Regarding efficiency, cf. Table 13, RóMULO ranked at the third position in these experiments; the results indicate that the competitor based on OPTICS-Xi is the most efficient one, which is closely followed by the one based on Affinity-Propagation; the competitors that are based on Mean-Shift, DCC, and PQC rank behind RóMULO. From the previous experimentation, it is clear that the search strategy of RóMULO has a negative impact on its efficiency, but it generally finds better clusterings; the Table 13 Classification power: Time. P. Jiménez, J.C. Roldán and R. Corchuelo Information Sciences 591 (2022) 103–127 123 experimentation to check how powerful it is for classification purposes confirms the previous finding, since it can work in reasonable times and attain very good classification scores. It takes from a minimum of 0:01 minutes on a small dataset from the ‘‘OpenML” data lake with 85 data that have four attributes and four classes to a maximum of 57:93 minutes on a large dataset from the ‘‘Kaggle” data lake with 51047 data that have 874 attributes and two classes; the other competitors timed out on this dataset where RóMULO could attain an Adjusted Rand Coefficient of 0:00, a Fowlkes-Mallows coefficient of 0:22, and an Accuracy coefficient of 0:43. Tables 14 and 15 report on the ratio of degraded clusterings and timeouts, respectively. Note that RóMULO and the competitor based on PQC are the only proposals that attain 0:00 degradation ratio in this experimentation; in the case of RóMULO, this is again due to its ability to quickly discard degraded clusterings; in the case of the competitor based on PQC, the result is not that surprising since it was the proposal that resulted in less degraded ratios in the previous experimentation. The statistical analysis confirms that RóMULO is closely followed by the proposals based on PQC, DCC, Affinity- Propagation, and OPTICS-Xi, which are indistinguishable from it because the p-values returned for these comparisons are clearly above the significance level; the last position in the rank is for the competitor based on Mean-Shift and the difference was confirmed to be statistically significant because the p-value returned was clearly below the significance level. Regarding the ratio of timeouts, RóMULO is again the only proposal that could process all of the datasets within the time constraints that were set; then come the competitors based on OPTICS-Xi with a ratio of 0:09, Mean-Shift with a ratio of 0:12, Affinity- Propagation with a ratio of 0:16, DCC with a ratio of 0:48, and PQC with a ratio of 0:58. The statistical analysis makes it clear that RóMULO and the competitors based on OPTICS-Xi, Mean-Shift, and Affinity-Propagation are statistically indistinguishable because the p-value returned by Hommel’s test is clearly above the significance level; it also makes it clear that the competitors based on DCC and PQC rank below the previous group because the p-value computed is zero in both cases and this implies that the differences in rank are very significant. The conclusion is that RóMULO ranks the first regarding the Adjusted Rand, the Fowlkes-Mallows, and the Accuracy coefficients. Regarding the first coefficient, the differences in rank are statistically significant with regard to all of the other competitors; regarding the second and the third coefficient RóMULO shares the first position in the rank with the competitors based on Mean-shift and Affinity-Propagation, respectively. It is closely followed by the competitors based on Affinity- Propagation, Mean-Shift, and OPTICS-Xi, and then come the competitors based on DCC and PQC. It performs quite well regarding efficiency and does not result in any degraded clusterings or timeouts. Table 14 Classification power: Degradation. P. Jiménez, J.C. Roldán and R. Corchuelo Information Sciences 591 (2022) 103–127 124 5. Conclusions This article introduces a new clustering proposal called RóMULO. It is intended to help data engineers extract new knowledge from their data lakes by finding compact and isolated clusters in a subspace of informative attributes. It explores a research niche that has not been studied before: using a genetic meta-heuristic to perform multi-way single-subspace automatic clustering. RóMULO was confronted with five strong competitors that combine the state-of-the-art attribute selection proposal with three classical single-way clustering proposals, a recent quantum-inspired one, and a recent deep-learning one. They were explored regarding their ability to find compact and isolated clusterings and the extent to which those clusterings can be considered good classifications. The first exploration was performed using the Silhouette, the Davies-Bouldin, and the Calin ´ski-Harabasz coefficients; the second one was performed using the Adjusted Rand, the Fowlkes-Mallows, and the Accuracy coefficients. Furthermore, it was very efficient regarding CPU time and it did not result in any degraded clusterings or timeouts. The conclusions regarding the rankings were supported by means of the corresponding statistical analyses at the standard significance level. Future research includes exploring how an engineer can include some background knowledge into the clustering process, e.g., to flag some data as belonging to the same or different clusters or to provide custom attribute transformers in the case of non-numeric attributes. Exploring whether some ideas based on collaborative filtering might help improve the efficiency in the case of large datasets is also worth exploring. Much attention shall also be paid to exploring other meta-heuristics, e.g., coral-reef or quantum optimisation, and deep learning. CRediT authorship contribution statement Patricia Jiménez: Conceptualization, Methodology, Validation, Resources, Data curation, Writing – review & editing. Juan C. Roldán: Conceptualization, Methodology, Validation, Resources, Data curation, Writing – review & editing. Rafael Corchuelo: Conceptualization, Methodology, Software, Validation, Resources, Data curation, Writing – original-draft, Writing – review & editing, Supervision, Project administration, Funding acquisition. Table 15 Classification power: Timeouts. P. Jiménez, J.C. Roldán and R. Corchuelo Information Sciences 591 (2022) 103–127 125 Declaration of Competing Interest The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. Acknowledgements The authors were partially supported by the Spanish National Research Council (TIN2016-75394-R, PID2020-112540RB- C44) and the Andalusian Research Council (P18-RT-1060, US-1381375). The work by Juan C. Roldán was also supported by a PIF grant from the University of Seville. The authors are very grateful to Dinamic Area, S.L. for providing an ideal industrial context and the machinery required to perform the experimental evaluation. References [1] Charu C. Aggarwal, An introduction to cluster analysis, in: Data clustering: algorithms and applications, CRC Press, 2013, pp. 1–28. [2] Shafiq Alam, Gillian Dobbie, Yun Sing Koh, Patricia Riddle, Saeed Ur Rehman, Research on particle swarm optimization based clustering: a systematic review of literature and techniques, Swarm Evol. Comput. 17 (2014) 1–13, https://doi.org/10.1016/j.swevo.2014.02.001. [3] Daniel Aloise, Amit Deshpande, Pierre Hansen, Preyas Popat, NP-hardness of Euclidean sum-of-squares clustering, Mach. Learn. 75 (2) (2009) 245–248, https://doi.org/10.1007/s10994-009-5103-0. [4] Amazon, Inc. Data lakes on Amazon Web Services. URL: https://aws.amazon.com/en/solutions/implementations/data-lake-solution, 2021. Accessed: 2021-10-12.. [5] Olatz Arbelaitz, Ibai Gurrutxaga, Javier Muguerza, Jesús M. Pérez, Íñigo Perona, An extensive comparative study of cluster validity indices, Pattern Recogn. 46 (1) (2013) 243–256, https://doi.org/10.1016/j.patcog.2012.07.021. [6] Hans-Georg Beyer, Hans-Paul Schwefel, Evolution strategies: a comprehensive introduction, Nat. Comput. 1 (1) (2002) 3–52, https://doi.org/10.1023/ A:1015059928466. [7] Chin-Wei Bong, Mandava Rajeswari, Multi-objective nature-inspired clustering and classification techniques for image segmentation, Appl. Soft Comput. 11 (4) (2011) 3271–3282, https://doi.org/10.1016/j.asoc.2011.01.014. [8] Charles Bouveyron, Pierre Latouche, Pierre-Alexandre Mattei, Bayesian variable selection for globally sparse probabilistic PCA, Electron. J. Stat. 12 (2) (2018) 3036–3070, https://doi.org/10.1214/18-EJS1450. [9] Zhaohong Deng, Kup-Sze Choi, Yizhang Jiang, Jun Wang, Shitong Wang, A survey on soft subspace clustering, Inf. Sci. 348 (2016) 84–106, https://doi. org/10.1016/j.ins.2016.01.101. [10] Michel M. Deza, Elena Deza, Encyclopedia of distances. Springer, 4th edition,., 2016. [11] Tansel Dökeroglu, Ender Sevinç, Tayfun Kucukyilmaz, Ahmet Cosar, A survey on new generation meta-heuristic algorithms, Comput. Ind. Eng. 137 (2019), https://doi.org/10.1016/j.cie.2019.106040. [12] Raúl V. Casaña, Paulo J.G. Eslava, Sandra Ortega-Martorell Lisboa, Ian H. Jarman, José D. Martín-Guerrero, Probabilistic quantum clustering, Knowl.- Based Syst. 194 (2020), https://doi.org/10.1016/j.knosys.2020.105567 105567. [13] Elliackin Figueiredo, Mariana Macedo, Hugo Valadares Siqueira, Clodomir J. Santana, Anu Gokhaled, Carmelo J.A. Bastos-Filhoa, Swarm intelligence for clustering: a systematic review with new perspectives on data mining, Eng. Appl. AI 82 (2019) 313–329, https://doi.org/10.1016/j. engappai.2019.04.007. [14] Adán J. García, Wilfrido Gómez-Flores, Automatic clustering using nature-inspired meta-heuristics: a survey, Appl. Soft Comput. 41 (2016) 192–213, https://doi.org/10.1016/j.asoc.2015.12.001. [15] Paolo Lo Giudice, Lorenzo Musarella, Giuseppe Sofo, Domenico Ursino, An approach to extracting complex knowledge patterns among concepts belonging to structured, semi-structured and unstructured sources in a data lake, Inf. Sci. 478 (2019) 606–626, https://doi.org/10.1016/j. ins.2018.11.052. [16] Raymond Greenlaw, Sanpawat Kantabutra, Survey of clustering: algorithms and applications, J. Inf. Retrieval Res. 3 (2) (2013) 1–29, https://doi.org/ 10.4018/ijirr.2013040101. [17] Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri, Franco Turini, Fosca Giannotti, and Dino Pedreschi. A survey of methods for explaining black box models. ACM Comput. Surv. 51(5): 93:1–93:42, 2019. doi: 10.1145/3236009.. [18] Jiawei Han, Micheline Kamber, Jian Pei, Cluster analysis: basic concepts and methods, in: Data Mining, Morgan Kaufmann, third edition, 2012, pp. 443– 495, https://doi.org/10.1016/B978-0-12-381479-1.00010-1. [19] Thomas Helmuth, Lee Spector, James Matheson, Solving uncompromising problems with Lexicase selection, IEEE Trans. Evol. Comput. 19 (5) (2015) 630–643, https://doi.org/10.1109/TEVC.2014.2362729. [20] Christian Hennig, What are the true clusters?, Pattern Recogn Lett. 64 (2015) 53–62, https://doi.org/10.1016/j.patrec.2015.04.009. [21] Eduardo R. Hruschka, Ricardo J.G.B. Campello, Alex A. Freitas, and André C.P.L.F. de Carvalho. A survey of evolutionary algorithms for clustering. IEEE Trans. Syst. Man Cybern. Part C 39 (2): 133–155, 2009. doi: 10.1109/TSMCC.2008.2007252.. [22] IBM, Inc. Data lake solutions. URL: https://www.ibm.com/analytics/data-lake, 2021. Accessed: 2021-10-12.. [23] Anil K. Jain, Data clustering: 50 years beyond k-means, Pattern Recogn. Lett. 31 (8) (2010) 651–666, https://doi.org/10.1016/j.patrec.2009.09.011. [24] Rezaul Karim, Oya Beyan, Achille Zappa, Ivan G. Costa, Dietrich Rebholz-Schuhmann, Michael Cochez, Stefan Decker, Deep learning-based clustering approaches for bioinformatics, Briefings Bioinform. 22 (1) (2021) 393–415, https://doi.org/10.1093/bib/bbz170. [25] Meike Klettke, Hannes Awolin, Uta Störl, Daniel Müller, and Stefanie Scherzinger. Uncovering the evolution history of data lakes. In BigData, pages 2462–2471, 2017. doi: 10.1109/BigData.2017.8258204.. [26] Hans-Peter Kriegel, Peer Kröger, and Arthur Zimek. Clustering high-dimensional data: a survey on subspace clustering, pattern-based clustering, and correlation clustering. TKDD, 3 (1): 1:1–1:58, 2009. doi: 10.1145/1497577.1497578.. [27] William la Cava, Thomas Helmuth, Lee Spector, Jason H. Moore, A probabilistic and multi-objective analysis of Lexicase selection and <texmath type=”inline”>epsilon </texmath>-Lexicase selection, Evol. Comput. J. (2019) 1–26, https://doi.org/10.1162/evco_a_00224. [28] Jundong Li, Kewei Cheng, Suhang Wang, Fred Morstatter, Robert P. Trevino, Jiliang Tang, Huan Liu, Feature selection: a data perspective, ACM Comput. Surv. 50 (6) (2018) 94:1–94:45, https://doi.org/10.1145/3136625. [29] Boris Lorbeer, Ana Kosareva, Bersant Deva, Dzenan Softic, Peter Ruppel, Axel Küpper, Variations on the clustering algorithm Birch, Big Data Res.11 (2018) 44–53, https://doi.org/10.1016/j.bdr.2017.09.002. [30] José M. Luna-Romera, Jorge García-Gutiérrez, María Martínez-Ballesteros, José C. Riquelme-Santos, An approach to validity indices for clustering techniques in Big Data, Prog. AI 7 (2) (2018) 81–94, https://doi.org/10.1007/s13748-017-0135-3. [31] José M. Luna-Romera, María Martínez-Ballesteros, Jorge García-Gutiérrez, José C. Riquelme-Santos, External clustering validity index based on chisquared statistical test, Inf. Sci. 487 (2019) 1–17, https://doi.org/10.1016/j.ins.2019.02.046. [32] S. Manochandar, M. Punniyamoorthy, Ramasamy K. Jeyachitra, Development of new seed with modified validity measures for k-means clustering, Comput. Ind. Eng. 141 (2020), https://doi.org/10.1016/j.cie.2020.106290 106290. P. Jiménez, J.C. Roldán and R. Corchuelo Information Sciences 591 (2022) 103–127 126 [33] Christian Mathis, Data lakes, Datenbank-Spektrum 17 (3) (2017) 289–293, https://doi.org/10.1007/s13222-017-0272-7. [34] Microsoft, Inc. Data lakes. URL: https://azure.microsoft.com/en-us/solutions/data-lake, 2021. Accessed: 2021-10-12.. [35] Erxue Min, Xifeng Guo, Qiang Liu, Gen Zhang, Jianjing Cui, Jun Long, A survey of clustering with deep learning from the perspective of network architecture, IEEE Access 6 (2018) 39501–39514, https://doi.org/10.1109/ACCESS.2018.2855437. [36] Satyasai J. Nanda, Ganapati Panda, A survey on nature inspired meta-heuristic algorithms for partitional clustering, Swarm Evol. Comput. 16 (2014) 1– 18, https://doi.org/10.1016/j.swevo.2013.11.003. [37] Frank Neumann, Carsten Witt, Bioinspired computation in combinatorial optimization, Springer, 2010, https://doi.org/10.1007/978-3-642-16544-3, ISBN 978-3-642-16543-6. [38] Satoshi Oyama, Katsumi Tanaka. How many objects? Determining the number of clusters with a skewed distribution. In ECAI, pages 771–772, 2008. doi: 10.3233/978-1-58603-891-5-771.. [39] Lakshmi Patibandla and Naralasetti Veeranjaneyulu. Survey on clustering algorithms for unstructured data. In Intelligent Engineering Informatics, volume 695. Springer, 2018. doi: 10.1007/978-981-10-7566-7_41.. [40] Witold Pedrycz, Collaborative fuzzy clustering, Pattern Recognit. Lett. 23 (14) (2002) 1675–1686, https://doi.org/10.1016/S0167-8655(02)00130-7. [41] Christoph Quix. Data lakes: a solution or a new challenge for big data integration? In DATA, page 7, 2016.. [42] Sandeep Rana, Sanjay Jasola, Rajesh Kumar, A review on particle swarm optimization algorithms and their applications to data clustering, Artif. Intell. Rev. 35 (3) (2011) 211–222, https://doi.org/10.1007/s10462-010-9191-9. [43] Sohil Atul Shah and Vladlen Koltun. Deep continuous clustering. CoRR, abs/1803.01449, 2018. URL: http://arxiv.org/abs/1803.01449.. [44] Yinghua Shen, Witold Pedrycz, Collaborative fuzzy clustering algorithm: some refinements, Int. J. Approx. Reason. 86 (2017) 41–61, https://doi.org/ 10.1016/j.ijar.2017.04.004. [45] David J. Sheskin, Handbook of parametric and nonparametric statistical procedures, Chapman & Hall/CRC Press (2020). [46] Kelvin Sim, Vivekanand Gopalkrishnan, Arthur Zimek, Gao Cong, A survey on enhanced subspace clustering, Data Min. Knowl. Discov. 26 (2) (2013) 332–397, https://doi.org/10.1007/s10618-012-0258-x. [47] Xu. Dongkuan, Yingjie Tian, A comprehensive survey of clustering algorithms, Ann. Data Sci. 2 (2) (2015) 165–193, https://doi.org/10.1007/s40745- 015-0040-1. [48] Xu. Rui, Donald C. Wunsch, Survey of clustering algorithms, IEEE Trans. Neural Networks 16 (3) (2005) 645–678, https://doi.org/10.1109/ TNN.2005.845141. P. Jiménez, J.C. Roldán and R. Corchuelo Information Sciences 591 (2022) 103–127 127