An approach to validity indices for clustering techniques in Big Data

An approach to validity indices for clustering techniques in Big Data José María Luna-Romera1 · Jorge García-Gutiérrez1 · María Martínez-Ballesteros1 · José C. Riquelme Santos1 Abstract Clustering analysis is one of the most used Machine Learning techniques to discover groups among data objects. Some clustering methods require the number of clusters into which the data is going to be partitioned. There exist several cluster validity indices that help us to approximate the optimal number of clusters of the dataset. However, such indices are not suitable to deal with Big Data due to its size limitation and runtime costs. This paper presents two clustering validity indices that handle large amount of data in low computational time. Our indices are based on redefinitions of traditional indices by simplifying the intra-cluster distance calculation. Two types of tests have been carried out over 28 synthetic datasets to analyze the performance of the proposed indices. First, we test the indices with small and medium size datasets to verify that our indices have a similar effectiveness to the traditional ones. Subsequently, tests on datasets of up to 11 million records and 20 features have been executed to check their efficiency. The results show that both indices can handle Big Data in a very low computational time with an effectiveness similar to the traditional indices using Apache Spark framework. Keywords Clustering ·Big Data ·Clustering validity indices ·Intra-cluster distance BJosé María Luna-Romera [email protected] Jorge García-Gutiérrez jorg[email protected] María Martínez-Ballesteros [email protected] José C. Riquelme Santos [email protected] 1Department of Computer Languages and Systems, ETSII, University of Seville, Seville, Spain 1 Introduction In the last few years, available data has been increased considerably. Medicine, electricity, business or biology are some areas where data has been quickly generated [4,7,13,29,31, 40]. This information needs to be processed in order to discover knowledge, but traditional techniques are limited by the size of the data. This fact supposes a challenge to the research community because traditional machine learning methods cannot deal with large volume of data. Therefore, such learning techniques need to be redesigned to be able to handle Big Data. Among the traditional techniques to discover knowledge, clustering can be useful to analyze large datasets with the aim at finding groups with similar behavior. Clustering is formally defined in [15] as the process of grouping a set of data objects into multiple groups or clusters so that objects within a cluster have high similarity, but are very dissimilar to objects in other clusters. Dissimilarities and similarities are assessed based on the attribute values describing the objects and often involve distance measures. Each clustering method generates different solutions on the same dataset. Clustering analysis is also applied to detect unknown associations within the data. In particular, clustering techniques based on partitioning methods find the most suitable partition of the objects of the dataset into a given number of groups optimizing a chosen partitioning criterion. Nevertheless, such methods require the optimal number of clusters that the dataset is going to be partitioned. For this task, there exist cluster validity indices (CVI) that help to calculate it. The application and usability of these indices has been proven in several works in the literature [1–3,25]. However, the traditional indices are not suitable to deal with large datasets due to the high computational time costs and their inability to be parallelized. Traditional CVIs 2.1 Clustering methods Cluster analysis can be used as a mechanism to achieve a custom vision of the distribution of the data, to observe the features of each cluster and to target on a particular subset of data for other analysis. It is also used as a preprocessing step for further algorithms, such as classification or features selection, which would deal with the detected clusters and the selected features. In some cases, clustering analysis is also called automatic classification since clustering is a collection of similar data objects on each cluster, so data objects within the same cluster can be managed as an implicit class. Clustering can be found in the literature as data segmentation in some applications because large datasets are partitioned into groups by their similarity. Another use of clustering is the outlier detection, that could be defined as that data object that is far away from any cluster and it may be more interesting to not to include it in any of them. Some applications of clustering for outlier detection can be found in [26]. Clustering analysis is considered a branch of statistics, and it has been widely studied as distance-based cluster analysis. Clustering analysis implementations based on K-means or K-medoids have been developed into many statistical analysis software packages and systems [18]. In Machine Learning, clustering is a method of unsupervised learning, so the data object has no class label information. Clustering learns by observation instead of learning by examples. Some of the active research topics are focused on the scalability of clustering methods [6], the effectiveness of types of data [32], high-dimensional clustering techniques [18], and methods for clustering mixing numerical and nominal data in large datasets. There exist many clustering algorithms in the literature, so it is difficult to set a categorization. In many cases, an algorithm can be classified into several categories due to its features. However, most of the clustering techniques could be classified into the following categories [12]: Partitioning methods Given a set of nobjects, a partitioning method constructs kgroups of data, where each partition represents a cluster and k≤n. It splits the data objects into kclusters such each cluster must contains at least one data object. Most of these methods are distance-based, so given k, which is the number of groups to build, a partition method sets an initial solution. Then, it iterates and try to improve the solution by moving objects between the groups. Despite each clustering method takes its own criterion, a satisfying partitioning is where data objects in the same cluster are close and objects in different clusters are far away. Clustering methods usually work properly with spherical-shaped cluster when this operation is used [18]. Hierarchical methods This kind of methods create a hierarchical decomposition of the given set of data objects. It use pairwise distances, so such CVIs will have quadratic complexity. The use of this kind of CVIs on large data could take much longer to compute the evaluation measure than running the clustering algorithm. Nowadays, some frameworks are able to deal with Big Data. One of the first frameworks that allowed processing large datasets was Apache Hadoop [9]. Hadoop allows to work across clusters of computers using simple programming models based on Google’s MapReduce paradigm [9,14]. Additionally, one of the most used Big Data projects is the open-source cluster computing framework named Apache Spark [34]. Spark appeared as alternative to solve memory limitation that MapReduce suffered. MapReduce reads and writes from hard drive, as a result, it slows down the processing speed. Spark reduces the number of read/write cycles to disk and stores intermediate data in faster logical RAM memory. It uses an structured data, named RDD, especially designed for parallel computing that caches results in memory for processing large amounts of data [38]. Apache Spark contains an scalable Machine Learning library (MLlib) with a set of algorithms to handle classification, regression, decision tree, recommendation systems and clustering techniques [35]. The purpose of this paper is to show the limitations of traditional clustering indices and to present novel validity indices that can tackle Big Data, henceforth named BD-CVI. In particular, the proposed indices are implemented using Apache Spark framework. A data generator application is also presented to ensure the composition of data and to test the performance of the proposed indices. K -means method was selected for testing the performance of these CVIs and BD-CVIs. The remainder of this paper is organized as follows. Section 2 presents an outline of the background about clustering including a description of traditional indices and the state-of- the-art of Big Data clustering. Section 3 defines the BD-CVI proposed in this paper. Section 4 shows the experimental analysis and the obtained results. Section 5 reports the conclusions drawn by this paper. Lastly, “Appendix A” details the dataset generator application that was implemented to be used in the experimentation. 2 Related work In this section, clustering analysis is formally defined and a general classification of the main clustering methods is also presented (Sect. 2.1). In addition, main CVIs are described and classified by categories (Sect. 2.2). Furthermore, we provide a brief overview of previous works related to clustering analysis in Big Data (Sect. 2.3). successively groups the objects close to one another until all the data objects are merged into one. This kind of clustering methods leads to smaller computation costs by not having to worry about a combinatorial number of different choices due to once a step is done it can never be undone. Density-based methods This methods iteratively build a cluster as long as the density, defined as the number of objects in a cluster, exceeds some threshold. This kind of methods is used to detect outliers and discovers random-shape clusters. Grid-based methods This kind of methods compute the object space into a finite number of cells that form a grid structure. They are independent of size of the dataset and dependent on the number of cells in each dimension in the quantized space. 2.2 Cluster validity indices As stated in the introduction, this paper is focused on partitioning clustering methods because they need the number of clusters into which the dataset is going to be partitioned. Knowing a priori a proper approximation to the number of cluster could be very useful for any clustering algorithm, especially hierarchical ones. For this task, several CVIs have been proposed in the literature. A summary of the most representative CVIs of each category are presented as follows [10,33]: •Indices measuring compactness of clusters These indices measure both the distance between the points that belong to the same cluster and the compactness of them: *Maximum Cluster Diameter (Δ)[16] is the highest diameter among all the clusters in the dataset. It is calculated by the maximum distance between two points that belong to the same cluster. *Average Within-Cluster Distance (W)[33] measures the average distance of the points that belong to the same cluster. •Indices measuring separation between clusters This category evaluates the separation of the clouds of points and grades it when there is a gap between them: *Average Between-Cluster Distance (β)[33]isthe average distance of the points that are in different clusters. •Indices measuring relationships between compactness and separation This category measures the ratio between the compactness of the clusters and the existing separation between them: *Silhouette [30] is a measure that sets how compacted are the points that belong to the same cluster against the separation between the clusters. *Dunn [11] measures the relation between the minimum inter-cluster distance and the maximum intracluster distance. *Davies and Bouldin [8] is a measure that uses data object quantities and features inherent to the dataset to set the compactness and separation of the clusters. *Calinski and Harabasz [5] is based on getting a relation between the inter-cluster distance and the intra-cluster distance. 2.3 Clustering in Big Data Clustering analysis in Big Data has been the main focus of a lot of researchers in the last years. Some of the most relevant papers in this field are analyzed below. Two C-means algorithms based on the canonical polyadic decomposition and the tensor-train network for clustering Big Data are proposed in [39]. They stated that the algorithms are suitable for Big Data clustering in Internet of Things systems with low-end devices since they can achieve a high compression rate for heterogeneous samples to save the memory space significantly. Mohammed et al. [27] proposed a new cluster algorithm named FireflyClust, that it can deal with text documents in a hierarchical line. FireflyClust can handle Big Data, overcoming other methods such as Bisect K-means, hybrid Bisect K-means and Practical General Stochastic Clustering Method. In this case, the algorithm does not need the number of cluster as input parameter. An effective K-means algorithm design was proposed in [37]. The algorithm is based on MapReduce programming model that acquires a fast detection speed with a high scaleup. However, no method was applied to identify the optimum number of clusters, so the algorithm was tested using different knumber of clusters. Jerome and ätönen [20] proposed a hierarchical clustering technique for classifying anomalies into clusters and providing information regarding the behavior of the anomaly cluster by analyzing its centroid in Big Data. Overall, it is easier to detect anomalies than finding out reasons for anomalous behavior. This technique was also used to determine the severity of the anomaly by using a failure significance metric. A novel cluster center fast determination clustering algorithm for Big Data was proposed in [21]. The algorithm is based on the density and distance distribution of the data objects to determine the cluster center quickly by constructing the normal distribution function. Kim et al. [22] suggested an optimized combinatorial clustering algorithm for noisy performance with random sampling for Big Data. The algorithm outperforms conventional approaches through various numerical and qualitative thresholds such as mean and standard deviation of accuracy and computation speed. Tong et al. [36] proposed Scalable Clustering Using Boundary Information, a highly flexible and scalable clustering scheme. To achieve this, such algorithm firstly identifies the border points of the dataset, and then it groups boundary points into suitable clusters and includes the rest points to their nearest border point. The obtained reports confirm similar results than the standard DBSCAN method, but such method is able to handle Big Data. A novel method for assessing the robustness of clusters for partitioning algorithms is introduced in [23]. However, such method is not applied to Big Data, and moreover, the experiments have been carried out with supervised data where classes have been used as clusters. 3 Big Data indices As stated in Introduction, the main purpose of this paper is to provide efficient and suitable CVIs able to deal with Big Data. The proposed BD-CVIs are approximations of traditional indices because those indices require high computational cost and they are unable to be parallelized. Firstly, traditional CVIs are described in Sect. 3.1. Secondly, the definition of BD-CVIs is in Sect. 3.2. 3.1 Traditional CVIs From the traditional indices, we have selected those that had the best performance in the experiments (Sect. 4.3.3), and thus Silhouette and Dunn are detailed below: Let Ωbe the space of the objects with a given distance d. Then, {Ak}k=1...Nis a set of clusters so that kAk=Ω, and Ai∩Aj=∅ ∀i= j. Ckis the centroid of Ak, and C0the centroid of Ω. Let xi∈Ak, the distance from xito the own cluster Akis defined: ak(xi)=1 |Ak|−1 xj∈Ak j=i d(xi,xj)(1) where ak(xi)represents the dissimilarity of xito all other points within the same cluster kand bk(xi)=min j=i...N{aj(xi), j= k}(2) –Silhouette is defined in [30]as(Eq.4): sk(xi)=bk(xi)−ak(xi) max{ak(xi), bk(xi)}(3) Silhouette =1 |Ω| xi∈Ω sk(xi)(4) Silhouette index ranges [−1,1], where good values are near 1 and −1 closer values are bad clustering solutions. –Dunn index is defined in [11] and its purpose is to identify compact and well-separated clusters. For a given number of clusters N, the following equation defines the Dunn index: Dunn = min k=1...N{d(Ck,Cj), k= j} max k=1...N{max d(xi,xj), i= j,xi,xj∈Ak} (5) In a compact and well-separated clusters dataset, the distances between the clusters are wide and the distances between the points of the same cluster are small. Hence, a high value of the Dunn index means a compact and well-separated clusters solution. 3.2 BD-CVIs In this subsection, BD-Silhouette and BD-Dunn are going to be formally introduced: –BD-Silhouette is defined by two approaches to intracluster and inter-cluster mean distances. inter-cluster (Eq. 6) is the average of distances between each cluster centroid and global centroid C0: inter-cluster =1 N N  k=1 d(Ck,C0)(6) where C0is the center of the centroids of the clusters. intra-cluster (Eq. 8) distance is defined as the average of the distances between each point to the centroid of the cluster to which it belongs (Eq. 7). rk=1 |Ak| xi∈Ak d(xi,Ck)(7) intra-cluster =1 |N| N  xi∈Ak rk(8) Traditional Silhouette index takes intra-cluster distance instead, that is defined by the average distance between bk (xi ) is the smallest average dissimilarity of xi ∈ Ak to the points in other clusters. the points that belong to the same cluster (Eq. 1). The intra-luster distance is the main difference in BD- Silhouette. Equation 9represents BD-Silhouette that has been defined as the ratio between the difference of the intercluster and the intra-cluster, and the maximum of them. BD-Silhouette =inter-cluster −intra-cluster max{inter-cluster,intra-cluster} (9) BD-Silhouette returns a value in (−1,1), depending on the consistence of the cluster and the separation between them. The higher the cluster number is, the lower intracluster is because the points of the dataset tend to be more compact. BD-Silhouette takes the value −1ifa single cluster is defined for all the examples and tends to 1 when the number of clusters is increased. BD-Silhouette would be 1 in the extreme case of each data object being a cluster. Therefore, an optimal value for the number of clusters would be the first maximum of BD-Silhouette, which maximizes the coherence of the cluster with the lowest kpossible. –BD-Dunn simplifies the original Dunn index to facilitate its computation in Big Data, since it does not have to calculate in the denominator the distance between each pair of points of the dataset. On the contrary, original Dunn seeks the minimum distance between the centroids and the maximum distance between all the points that belong to the same cluster. Thus, BD-Dunn (Eq. 5)is the ratio between the minimum of the distances from the centroids to the global center and the maximum of the distances from each point in the set to its centroid. BD−Dunn = min k=1...N{d(Ck,C0)} max k=1...Nmax xi∈Ak {d(xi,Ck)}(10) BD-Dunn takes the value 0 if we define a single cluster for all the examples. However, BD-Dunn tends to infinity when the number of clusters increases. In the extreme case of each example belong to a different cluster, its value cannot be calculated because the denominator is zero. Figure 1illustrates a distribution of a dataset with 2 features and 3 clusters in different colors. The clusters are represented by circles, and the points are the red dots. Each cluster ihas its centroid denoted by Ci, and the global centroid as C0is also represented. Blue cluster has also highlighted some points in the cluster. In the figure, inter-cluster distance is represented by the red cluster as d(C1,C0)that Fig. 1 Representation of 3 clusters with inter-cluster and intra-cluster distance and the global centroid (C0) measures the distance between the centroid of the red cluster and the global centroid. The intra-cluster distance is represented in the blue cluster as the distance between the point X1and its centroid C2. As it happens with traditional CVIs, BD-CVIs return a value on each clustering solution. To get the optimum number of clusters of a large dataset, BD-CVI could be calculated on each clustering execution. The optimal number of clusters is chosen following a different criterion on each BD-CVI. BD- Silhouette and BD-Dunn are growing indices. BD-Silhouette reaches 1 when k=N, and BD-Dunn tends to infinity. Thus, in both BD-CVIs, the first maximum is a satisfactory solution because it maximizes the clustering coherence with the lowest number of clusters possible. Figure 2illustrates the graphical representation of the results of BD-Silhouette and BD-Dunn for a dataset with 5 clusters and 500,000 instances each. BD-Silhouette value increases with the number of clusters. Such index marks a possible optimal number of clusters when there is a change of trend in the values. In Fig. 2, BD-Silhouette is increased by the number of clusters until k=5. This change of trend indicates that k=5 may be an optimal number of clustering. BD-Dunn reveals the optimal number of clusters with the first maximum value of its plot. Figure 2shows a first maximum value on k=5, where the line of BD-Dunn increases with the number of clusters and decreases in k=6. This inflection point indicates that k=5 could be the optimal number of clusters. 4 Experimental study The experimental setup and the results are detailed in this section. A comparative framework is also presented to test Table 1 Generated datasets with number of clusters, total number of instances and the size in MB Dataset Clusters Instances Size (MB) 5–1k5 5000 1.00 5–2k510,000 2.00 5–5k525,000 5.00 5–10k550,000 10.00 5–100k5 500,000 100.00 5–500k52,500,000 501.00 5–1M55,000,000 1003.52 7–1k7 7000 1.40 7–2k714,000 2.80 7–5k735,000 7.00 7–10k770,000 14.00 7–100k7 700,000 140.00 7–500k73,500,000 703.00 7–1M77,000,000 1402.88 9–1k99000 1.81 9–2k918,000 3.62 9–5k945,000 9.03 9–10k990,000 18.00 9–100k9 900,000 181.00 9–500k94,500,000 903.00 9–1M99,000,000 1802.24 11–1k11 11,000 2.21 11–2k11 22,000 4.41 11–5k11 55,000 11.05 11–10k11 110,000 22.10 11–100k11 1,100,000 221.00 11–500k11 5,500,000 1095.68 11–1M11 11,000,000 2211.84 ters and number of instances were applied. Table 1shows the main features of the generated datasets in the experiments. There are 4 different groups of datasets with 5, 7, 9 and 11 clusters. Each group of datasets contains 7 datasets, with 1000, 2000, 5000, 10,000, 100,000, 500,000 and 1 million instances per cluster. Thus, a dataset with 5 clusters and 1000 instances per cluster has a total of 5000 instances. The datasets are easily identified following the next pattern: C−N{k,M}where Cis the optimal number of clusters of the dataset, Nis the number of instances of each cluster multiplied by a thousand if it is followed by a k,orbya million if it is followed by a M. For example, 5–10kdataset has 5 clusters and each one contains 10,000 instances, so it contains a total of 50,000 instances. All the datasets were created with 20 features, the standard deviation was 0.05, and the mean was 0.25 and 0.75 to ensure the separation of the clusters. Fig. 2 BD-Silhouette and BD-Dunn results for a dataset with 5 clusters and 500,000 instances each both CVIs and to test which CVIs and BD-CVIs have the best performance (Sects. 4.3.3, 4.4.3). 4.1 Experimental setup 4.1.1 Software and hardware In this paper, we compared the results of traditional CVIs and the proposed BD-CVIs with the datasets described in Sect. 4.1.2. A clustering algorithm is required to test the performance of the proposed BD-CVIs. As stated in Sect. 2, K -means is a partitioning method that previously needs the number of clusters into which the dataset is going to be partitioned, so that this algorithm has been selected in the experimental study. In addition, it is the paradigmatic clustering algorithm [19] and it is one of the available algorithms in Spark MLlib [35]. In the case of traditional CVIs, we have used the K -means package available in the Weka Software developed in Java [17]. Two different execution environments were used in our experiments. On the first hand, traditional CVIs have been tested in the EC2 instances from Amazon Web Services (AWS) that count with Intel Xeon E5-2666 v3 (Haswell) processors, 3.75 GB RAM memory and enough hard disk to manage datasets originally stored in AWS S3. On the other hand, BD-CVIs were executed in AWS Elastic Map Reduce. 5 instances of m3.xlarge that each one counts with Intel Xeon E5-2670 v2 (Ivy Bridge) processors with 4 vCPU, 15 GB RAM memory and 2 SSD of 40 GB were used. 4.1.2 Generated datasets A total of 28 datasets have been used which are generated using the dataset generator application described in “Appendix A”. In order to test the limits of the CVIs and the novel BD-CVIs, several combinations of number of clus- Table 2 Distance of traditional CVIs to the optimal solution by dataset Silhouette Dunn David–Bouldin Calinski–Harabasz ΔWβ 5–1k000 0 000 5–2k000 0 000 5–5k000 0 000 5–10k000 0 000 7–1k1011 111 7–2k000 0 000 7–5k111 1 222 7–10k2022 323 9–1k211 2 222 9–2k121 1 121 9–5k0101000 9–10k0202233 11–1k1022 033 11–2k000 0 000 11–5k0200 400 11–10k222 2 223 Total 10 11 10 14 17 16 17 The hits results are highlighted in bold 4.2 Results This section is divided in two subsections. Section 4.3 contains the results for the traditional CVIs and Sect. 4.4 shows the results for BD-CVIs. Each subsection includes the effectiveness results and the computational cost. Section 4.3 includes a statistical analysis to compare the effectiveness among CVIs. Section 4.4 provides a statistical analysis to compare the execution time among BD-CVIs. After executing the CVIs, the effectiveness and execution time of each index are measured. The effectiveness of the indices is calculated by the absolute value of the difference to the optimal solution. Thus, an index with 0 value is considered that it correctly predicts the optimal number of clusters, whereas an index with 2 means that predicts two number above or below the optimal solution. The goodness of fit of the indices is given by the sum of the absolute values of the differences between the real value and the estimated. Therefore, the lower the value, the better the index. The statistical analysis was carried out using the open-source platform Stat- Service [28]. 4.3 Results of traditional CVIs 4.3.1 Effectiveness Table 2shows the distance to the optimal number of clusters given by the CVIs on each dataset. The datasets were chosen until execution time was under 86,400 s (1 day). The correctly predicted clusters are highlighted in bold, and the last row of the table is the total of distances of each CVI. The lower the value is, the better the CVI is. Silhouette, Dunn and David–Bouldin obtained the best results since they had the lowest total of distances. The worst results (highest distances) were obtained by Maximum Cluster Diameter (Δ), Average Within-Cluster Distance (W) and Average Between-Cluster Distance (β). Figure 3a, b shows graphically the number of cluster by Silhouette, Dunn, Davies–Bouldin and Calinski–Harabasz. Δ,Wand βwere not included in these figures because their results were not so positive. The optimal results are represented by big red dots, so each CVI whose point is on it means that correctly predicted the optimal number of clusters. Datasets with 5 and 7 clusters are included in Fig. 3a and datasets with 9 and 11 clusters are in Fig. 3b. CVIs obtained very good results in Fig. 3a. Almost all the represented CVIs correctly predicted the optimal solution. Dunn correctly predicted all the datasets except 7–5k.However, Dunn was the only one CVI that set the optimal number of clusters in two datasets in Fig. 3b. 11–10k, 9–1kand 9–2k number of clusters were not estimated by any of the CVI in this figure. The results of the CVIs do not directly depend on the number of instances of the dataset. The results may be influenced by the number of clusters of the dataset. The lesser number of clusters have the dataset, the greater is the ratio of correct predictions. The optimal number of clusters for datasets with 5 clusters were correctly predicted by all the indices. The optimal number of clusters for datasets with 7 clusters was the most difficult to predict. (a) (b) Fig. 3 Results of traditional CVI Silhouette, Dunn, Davies–Bouldin, Calinski–Harabasz for different datasets. Optimal solution by a red dot. a Results for datasets with 5 and 7 clusters. bResults for datasets with 9 and 11 clusters (color figure online) Table 3 Average of elapsed time of CVIs in seconds Silhouette Dunn David–Bouldin Calinski–Harabasz ΔWβ 5–1k9.34 9.33 0.01 2.00 1.99 1.99 7.31 5–2k40.54 40.55 0.01 8.48 8.55 8.59 31.99 5–5k224.46 224.49 0.02 47.20 47.43 47.65 176.91 5–10k1586.37 1584.48 0.48 346.66 340.48 341.01 1238.27 7–1k18.51 18.51 0.01 3.87 3.92 3.92 14.50 7–2k73.48 73.62 0.01 15.73 15.41 15.44 58.14 7–5k906.27 905.93 0.03 450.55 431.62 453.36 368.85 7–10k34,771.06 34,540.32 0.43 91,003.92 86,179.63 99,349.86 3707.81 9–1k20.96 21.12 0.01 2.45 2.35 2.51 18.24 9–2k281.41 278.27 0.02 137.06 136.44 138.55 137.44 9–5k4823.15 4686.26 0.08 14,269.38 10,143.56 9776.66 1330.02 9–10k−−0.49 −−−16,552.37 11–1k35.35 34.26 0.01 4.09 3.79 3.55 29.34 11–2k497.75 495.99 0.02 246.05 248.54 246.80 246.21 11–5k8945.03 9178.18 0.14 23,155.30 20,852.84 21,976.94 2653.13 11–10k−−1.13 −−−36,766.93 was obtained by Davies–Bouldin with very high difference respect to the other CVIs. Davies–Bouldin lasts 1.13 s for the largest dataset (11–10k), while there were some indices whose execution time was higher than 86,400 s (1 day). Such cases are marked as “–”. There is a significant increase in the runtime of traditional CVIs for datasets with more than 4.3.2 Execution time Table 3 shows the execution time in seconds of each traditional CVI. Figure 4 is added for better understanding of Table 3. Time is generally increased with the number of instances of the dataset. The lowest execution time Fig. 4 Representation of traditional CVIs time by the number of instances by dataset Table 4 Sorted ranking of traditional CVIs for Friedman test CVI Ranking David–Bouldin 3.406 Silhouette 3.531 Dunn 3.656 Calinski–Harabasz 3.969 Δ4.250 W4.500 β4.688 50,000 instances. It can be noted that runtime is four times higher in those datasets even though the growth in the number of instances is less than 50%. 4.3.3 Statistical analysis After the results generation of the traditional CVIs, a statistical analysis was applied to check if significant differences exist among the effectiveness of the multiple CVIs. The nonparametric Friedman test is shown in Table 4. The highest result for a ranking would be 1, and the worst would be 7. As the ranking shows, Davies–Bouldin was in the first position with 3.406, followed by Silhouette and Dunn with 3.531 and 3.656, respectively. The statistic for Friedman was 5.0625, distributed according to a Chi-square distribution with 6◦of freedom. The p value for Friedman was 0.5358 and higher than 0.05. Therefore, the null hypothesis was accepted that they all behaved in a similar way with a level of significance of α=0.05. Given the results of Table 3, it makes no sense to perform a statistical test to show that Davies–Bouldin was the fastest CVI. 4.4 Results of BD-CVIs 4.4.1 Effectiveness BD-CVIs were applied to all datasets from Table 1, including those datasets used in Sect. 4.3. Davies–Bouldin was also included in these experiments for its great results in terms of efficiency in the previous experiments. (a) (b) Fig. 5 Results of BD-Silhouette, BD-Dunn and Davies–Bouldin for different datasets. Optimal solution by a red dot. aResults for datasets with 5and7clusters.bResults for datasets with 9 and 11 clusters (color figure online)