# VIASCKDE Index: A Novel Internal Cluster Validity Index for Arbitrary-Shaped Clusters Based on the Kernel Density Estimation

Authors: Ali Şenol
Journal: Computational Intelligence and Neuroscience
 (2022)

---

## Abstract

The cluster evaluation process is of great importance in areas of machine learning and data mining. Evaluating the clustering quality of clusters shows how much any proposed approach or algorithm is competent. Nevertheless, evaluating the quality of any cluster is still an issue. Although many cluster validity indices have been proposed, there is a need for new approaches that can measure the clustering quality more accurately because most of the existing approaches measure the cluster quality correctly when the shape of the cluster is spherical. However, very few clusters in the real world are spherical. Therefore, a new Validity Index for Arbitrary-Shaped Clusters based on the kernel density estimation (the VIASCKDE Index) to overcome the mentioned issue was proposed in the study. In the VIASCKDE Index, we used separation and compactness of each data to support arbitrary-shaped clusters and utilized the kernel density estimation (KDE) to give more weight to the denser areas in the clusters to support cluster compactness. To evaluate the performance of our approach, we compared it to the state-of-the-art cluster validity indices. Experimental results have demonstrated that the VIASCKDE Index outperforms the compared indices.


---

## Body

## 1. Introduction

Clustering approaches are unsupervised learning techniques that separate data into groups called clusters according to the similarities and dissimilarities among the data [1, 2]. The DBSCAN [3], kmeans [4], BIRCH [5], Spectral Clustering [6], Agglomerative Clustering [7], HDBSCAN [8], Affinity Propagation [9], and OPTICS [10] are some examples of them, and they are used in many fields such as pattern recognition [11–13], machine learning [14–16], data mining [17, 18], web mining [1, 19], bioinformatics [20, 21], and streaming data mining [22, 23]. On the other hand, measuring the performance of any proposed clustering approach is also an important issue because each algorithm has its special point of view, and the results of each clustering technique vary. Therefore, to overcome this problem, cluster validation analysis or cluster validation indices have emerged. These approaches are generally used for two purposes, which are measuring the performance of clustering algorithms and contributing to clustering algorithms as a guide by finding the optimum number of clusters.Cluster validation indices are divided into two main categories as internal and external indices. In external indices, true class labels are compared with the labels that are assigned by the proposed algorithm to measure the performance. Therefore, to use these indices, there is a need for true class labels. The Purity [24], Rand Index [25], Adjusted Rand Index [26], Accuracy, Precision and Recall [27], F-Measure [28], and NMI [29] can be given as examples of these types of indices. On the other hand, in the internal indices, we do not need actual class labels to measure the quality of clusters. In these indices, the evaluation of clustering performance is based on how similar the data in the same cluster are to each other, known as compactness, and how dissimilar the data in different clusters are from each other, known as separation. The Silhouette Index (SI) [30], Dunn Index [31], Davies–Bouldin (DB) [32], Calinski-Harabasz (CH) [33], Xie-Beni (XB) [34], S_Dbw [35], and RMSSTD [36] can be mentioned as primary cluster validity indices. Besides, there are many new cluster validity indices such as the CVNN [37], CVDD [38], DSI [39], SCV [40], and AWCD [41].The main problem of the majority of state-of-the-art cluster validity indices is that they measure the cluster quality correctly when the shapes of the clusters are spherical. As an example, Silhouette Index (SI) uses the means of distances of each data in the cluster to evaluate their quality. Similarly, Davies–Bouldin (DB) uses cluster diameters and cluster centroids, and the Calinski-Harabasz (CH) uses the square of intracluster and intercluster distances. These all calculations are ideal if the shape of the cluster is spherical. However, the shapes of the minority of clusters are spherical in the real world. Additionally, if the shape is arbitrary, these indices cannot measure the cluster quality correctly because the center of gravity of any cluster is in the middle only if the shape is spherical.Similar to our approach, there is another kernel density estimation-based cluster validation index, named theMclus [42]. In the Mclus, the authors used a function of estimation of the mode to assess cluster quality. This mode function allows the index to assess the cluster quality by adopting interpoint distance measures that can be defined to have a probability density function. To evaluate clustering with the number of clusters greater than 1 (K > 1), they applied the mode estimation procedure for interpoint distances that are assumed to have a probability density function between the data members. On the other hand, in this study, we proposed a novel Internal Validity Index for Arbitrary-Shaped Clusters based on the kernel density estimation (the VIASCKDE Index). We aimed to calculate the cluster quality accurately by using compactness and separation of each data to support arbitrary-shaped clusters and the kernel density estimation (KDE) to weight denser regions in the clusters to the compactness of the clusters. Therefore, the advantages of our new approach can be listed as follows:(i)
The VIASCKDE Index can evaluate arbitrary-shaped clusters correctly(ii)
It weights denser regions to support the compactness of clusters(iii)
It is suitable for all types of clustering techniques, especially for density-based algorithms(iv)
It can be used for micro-cluster-based approaches(v)
It has greater performance when compared with state-of-the-art techniquesThe rest of this paper was organized as follows: in Section2, the related studies were reviewed. In the 3rd section, the problem with existing works and the need for the proposed approach was explained. While details about the VIASCKDE Index were given in the 4th section, the comparison of experimental results with the state-of-the-art approaches on real and synthetic datasets was given in the 5th section. After that, the discussion on the results was provided in Section 6. Finally, the conclusion of the study was presented in Section 7.


## 2. Background and Related Works

As cluster validation techniques, in internal methods, we do not need the actual class labels. The cluster validation operation is done by calculating the similarities in the intraclusters and the differences in the interclusters produced by the model to reveal how consistent the produced clusters are [43]. As mentioned above, in the internal methods, cluster quality is evaluated in the aspects of two concepts [44]:(1)
Compactness: it states how much the data, which is in the same cluster, are close to each other. Closer data mean better clustering.(2)
Separation: it evaluates how much the clusters are far from each other. In the clustering evaluation, it is expected to be far from each other as much as possible.The illustration of these two concepts is presented in Figure1, while the equation is demonstrated in Eq. (1). Here, α and β are the weights.(1)Index=α•Compactnessβ•Separation.Figure 1
The example of the relationship between the compactness and separation concepts of two clusters in a two-dimensional data space.There are many internal methods proposed in the literature. In this section, we focused on the validation indices that are relevant to our approach. To make definitions shorter and more understandable, the general definitions are as follows:LetX = {x1, x2,…,xn}∈ Rd be a dataset containing n points in a d-dimensional space, and xi ∈ Rd. X is a set of disjoint k clusters (where Ci is a cluster and i = 1,2,3,…,k), and ni data are in the Ci cluster. While the cluster center that is the gravity center of cluster Ci is the mean of the data that belongs to Ci and calculated by μ=1/ni∑xi∈Cixi, the mean of all datasets is calculated by μ¯=1/n∑x∈Xx. In the present study, the mentioned distance is the Euclidean distance; one of each x and y is data of the dataset, and the Euclidean distance between these two data is expressed as de(x,y). In light of this information, we can briefly list the main internal cluster validity indices as follows:Silhouette Index (SI) [30]: as given in Figure 2, the compactness value of one of the data in any cluster is calculated by measuring the distance from the data to each data in the same cluster. Then, the compactness of the cluster, which is notated as a(x), is calculated by measuring the mean of compactness of all the data that the cluster has. The average of the distances from the elements of the nearest cluster, to which the mentioned data do not belong, gives the separation value of that data. After that, the separation value of the cluster is found by calculating the mean of the separation values of all the data of the cluster and it is notated as b(x). From now on, we can calculate the SI value, which is the cluster validity index of the model. The equations to calculate SI, a(x), and b(x) are given in equations (2)–(4), respectively. The SI value is [−1, +1]. While -1 means the worst clustering, +1 means the best clustering.(2)ax=1ni−1∑x,y∈Ci,y≠xdex,y,(3)bx=minj=1,2,…,k;j≠i1nj∑x∈Cj,y∈Cjdex,y,(4)SI=1n∑i=1k∑x∈Cibx−axmaxax,bx.Figure 2
The example of Silhouette Index.Dunn Index (DI) [31]: the DI calculates the success of the model based on compactness and the separation between the clusters. To do this, the DI value of a cluster is calculated by the distance to the closest cluster and its own diameter. Let dminCi,Cj be the closest distance between clusters Ci and Cj, and let diam(Cl) be the diameter of the cluster Cl, and the values of these two variables are calculated by dminCi,Cj=minxi∈Ci,xj∈Cjdexi,yi and diamCl=maxxi∈Ci,xj∈Cjdexi,yi. Therefore, by knowing the value of dminCi,Cj and diam(Cl), the DI of the model is calculated by equation (5). The larger the result value, the more successful the clustering is.(5)DI=min1≤i≤kminj≠i,1≤j≤kdminCi,Cjmax1≤l≤kdiamCl.Calinski-Harabasz (CH) [33]: the CH calculates compactness and separation values via the mean of the squares of the interclass and intraclass distances. The CH index value is calculated by (6). In the CH index, the goal is to make the result as large as possible.(6)CH=∑i=1knide2μi,μ/k−1∑i=1k∑x∈Cide2x,μi/n−k.Davies–Bouldin (DB) [32]: the compactness value is calculated over the mean of the variance of the data in each cluster. On the other hand, the separation value is calculated over the distance from the center of the cluster to the center of the closest one. Let avg(Ci), which is calculated by (7), be the average of the distances of each data in the cluster i to the cluster center, and the avg(Ci) is calculated by (8).(7)avgCi=1nini−1∑xi,xj∈Cidexi,xj,(8)DB=1k∑i=1,i≠j,1≤j≤kkmaxavgCi+avgCjdeμi,μj.S_Dbw Index [35]: The S_Dbw calculates the compactness value of the clusters over the standard deviations (σ) of the data that the cluster has. On the other hand, it calculates the separation value by the distance between the centers of the clusters. The S_Dbw index is a type of index that considers the density of clusters. Let den be the density of the cluster, and the S_Dbw index value is calculated with the following equations:(9)S_Dbw=1k∑Ci∈CσCiσX+1kk−1∑Ci∈C∑Cj∈C,Ci≠CjdenCi,CjmaxdenCi,denCj,denCi=∑xp∈Cifxp,μi,denCi,Cj=∑xp∈Ci∪Cjfxp,μi+μj2,fxp,μi=0,dexp,μi>σC,1,otherwise.Distance-based Separability Index (DSI) [39]: the DSI is another approach that measures the cluster quality by the means of the distances based on intercluster and intracluster. Let Ci and Cj be two clusters and have Ni and Nj data points, respectively. The intracluster distance set of cluster Ci will be a set as given equation (13). Moreover, the intercluster distance set is measured based on the distances of data pairs of clusters Ci and Cj. To compute the DSI, the Kolmogorov–Smirnov (KS) test was utilized.(10)dCi=dex,y|x,y∈Ci;x≠y,IfCi=Ni,,thendCi=12Ni,Ni,−1,dCi,j=dex,y|x∈Ci;y∈Cj,IfCi=Ni,,Cj=Nj,,thendCi,j=Ni.Nj.LetSCi be Kolmogorov–Smirnov test of cluster Ci, which is calculated as SCi=KSdCi,dCi,j and SCj be of Cj, and the DSI of these two clusters is the result of the following equation:(11)DSICi,Cy=SCi+SCj2.RMSSTD [35]: the root-mean-square standard deviation (RMSSTD) aims to calculate the clustering quality by measuring the homogeneity of clusters. It is commonly used for hierarchical clustering. Let the dataset consists of k clusters, p be the number of independent variables, x¯ij be the mean of data in variable j and cluster i, and nij is the number of data in variable p and cluster k. RMSSTD is measured by equation (12). The lower RMSSTD means better clustering.(12)RMSSTD=∑i=1,2,…,pj=1,2,…,k∑a=1nijxa−x¯ij2∑i=1,2,…,nj=1,2,…,knij−1.


## 3. Statement of the Problem

Although many approaches have been proposed, analysis of the cluster quality is still an issue. Because there are many clustering approaches in the literature, they differ from each other in many aspects. Therefore, no cluster validation technique can evaluate the quality of all produced clusters precisely. However, some approaches have been used in this task including the Silhouette Index, Dunn Index, Davies–Bouldin, Calinski-Harabasz, and S_Dbw. Although these indices have been used commonly, each of them has a specific problem with cluster validation as given in Table1. For example, a significant part of the proposed cluster validity indices assumes the shapes of clusters are spherical. In fact, the minority of clusters are spherical in the real world as some examples are given in Figure 3. The SI can be given as an example of these kinds of indices. It cannot achieve a good score if the shape of the cluster is not spherical. On the other hand, the DB and the CH identify clusters that are compact and well separated. However, in the real world, very few clusters are in that shape. Similarly, despite being better than the DB and the CH in case of the clusters are not well separated, the DI encounters some issues with computational cost when the number of clusters or dimensionality is high. Besides, it is affected by the noisy data due to increasing diameter. As for the S_Dbw, although it is proposed as a density-supported validity index and gets a good score with the compact and well-separated clusters, it is affected by the distribution of the data. In addition, thanks to being a density-based clustering validity index, the DSI is good at dealing with arbitrary-shaped clusters. It can successfully evaluate any cluster quality. However, the DSI is also another cluster validity index that is affected when clusters are too close. Likewise, the RMSSTD is another validity index that encounters some problems when the clusters are close to each other. The examples of the problems on the shapes of clusters that existing indices come across can be increased.Table 1
Comparison of clustering validity indices that were used for experimentation in the present study.
Cluster validity IndexNotationRuntime complexityOptimal valueConsidering denser region?Handling arbitrary-shaped clusters?AdvantagesDisadvantagesSilhouette Index [30]SIOn2Max.✗✗The score is higher when the clusters are dense and well separatedGood at handling the spherical clusters, high computational complexityDunn Index [31]DIOn2Max.✗✓Competent at cluster validity taskHigh computational cost with high-dimensional data and the number of clustersCalinski-Harabasz Index [33]CHOnMax.✗✗Good at well separated and compact clusters, its computational complexity is very lowIt is not competent enough at the cluster validation task.Davies–Bouldin Index [32]DBOnMin.✗✗Good at well separated and compact clusters, its computational complexity is very lowIt is not competent enough at the cluster validation task.S_Dbw validity Index [35]S_DbwOnMin.✗✓Its computational complexity is very lowAffected negatively by the distribution of dataDistance-based Separability Index [39]DSIOn3Min✗✓Useful to discover the shape of clustersAffected negatively when clusters are too close and its computational complexity is highRoot-mean-square std dev [35]RMSSTDOnMin.✗✗Good for hierarchical clusteringHas issues when the clusters are close to each otherVIASCKDE Index (proposed)VIASCKDEOn2Max.✓✓It can handle the arbitrary-shaped clusters, take into account the denser regions, can be used for density-based and micro-cluster-based approachesHas issues when the clusters are close to each otherFigure 3
Some examples of the arbitrary-shaped cluster.Another problem with existing cluster validation indices is that they assume that all the data in any cluster have a homogeneous distribution. However, data inside the cluster mostly have various regions that have different densities, as seen in Figure4 (darker areas mean denser regions). Moreover, the data in the same cluster may not have homogeneous distribution as can be seen in Figure 4(b). So, any approach that considers the density of data in the clusters is still needed to support the compactness of the cluster. Although the S_Dbw and the DSI are two examples of cluster validity indices that take into consideration the density of clusters, they do not examine the density areas inside the clusters. These kinds of indices are useful to discover the shapes of clusters. However, maybe, some regions are denser than the other regions inside the cluster, and these indices do not take into account such problems. Giving more weight to denser regions may make the approach more accurate while identifying it because of supporting compactness. In the present study, we proposed a new cluster validity index that can discover the arbitrary-shaped clusters and weight the denser regions by using the Kernel. Density estimation was explained in Section 4.2.Figure 4
An example of various densities in clusters: example of an Aggregation dataset. (a)Density distribution of the dataset. (b) Density distribution inside a cluster.


## 4. Proposed Cluster Validity Index: A Novel Internal Cluster Validity Index for Arbitrary-Shaped Clusters Based on the Kernel Density Estimation (The VIASCKDE Index)

### 4.1. Basic Idea

In the present study, a new cluster validation index, which has been named shortly the VIASCKDE (the Validity Index for Arbitrary-Shaped Clusters based on the Kernel Density Estimation) index, was proposed. The VIASCKDE Index is a kind of index that is not affected by cluster shape, and thus, it can make a realistic evaluation of clustering performance regardless of the clusters’ shape. Unlike the existing cluster validation indices, our index calculates the compactness and separation values of the cluster based on calculating the compactness and separation values for each data separately. In other words, it calculates the compactness and separation values of the cluster over the distance of data, independent of parameters such as the cluster center because, in nonspherical clusters, the distance of the data to the closest data is more important than its distance to the cluster center. As can be seen in the example given in Figure5, the closest data in the cluster that “it belongs to” are used when calculating the compactness value for the data x. Similarly, the separation value of x is calculated by the distance to the closest data of the cluster that “it does not belong.”Figure 5
Relationship between the compactness and separation values of any data in the VIASCKDE Index.As mentioned before, another problem with existing cluster validity indices is to assume that the distribution of the data inside the cluster has homogeneous distribution, even if the shape of the cluster is arbitrary. Therefore, they weight each data of the cluster as the same value, whereas, as presented in Figure4, the distribution of data that is inside the same cluster may vary. Therefore, we need a new method that considers this situation. To overcome this problem, we proposed the kernel density estimation (KDE), which is detailed in the next section based on weighting method.


### 4.2. Kernel Density Estimation-Based Weighting

In the literature, there are two types of distribution estimation methods that are parametric and nonparametric. In parametric methods, for example, the Gaussian distribution assumes the distribution of any dataset is gathered around the center and the majority of the data is in a circle having a radius of the standard deviation. It means that the curve has only one peak on distribution. It is important to keep in mind that the univariate normal distribution, with meanµ and variance σ2, has the probability density function(13)fx=12πσ2e−x−μ/σ2/2,where x is in -∞ < x < ∞ interval. On the other hand, in nonparametric distribution estimation methods, it is assumed that there may be more than one distribution peaks on the curve. Let X=X1,…,XnT be an n-dimensional vector that has a multivariate Gaussian (or normal) distribution with the n-dimensional mean vector μϵRn and ∑ be the n x n covariance matrix. The multivariate Gaussian distribution is calculated as follows:(14)px,μ,Σ=12πnΣexp−12π−μTΣ−1x−μ.The kernel density estimation (KDE) is a nonparametric density estimator that is used for density estimation. It is also a method that is used to analyze existing data to decide which incoming data is placed correctly in which place. For this ability, it is commonly used in many areas such as data analysis procedures in healthcare services, artificial intelligence applications, the stock market, and many other areas [2]. The bar graph represents the histograms, and the orange line represents the KDE, and it is calculated over the histograms as presented in Figure 6. In analyzing the data and representing its application, it figures out the distribution of data according to various methods, which are given in Figure 7. Each one has its characteristic and equation. In mathematical formulation, the KDE is a function(15)Pn^n=1nh∑i=1nKXi−xh,where K(.) is one of the functions, which are given in Figure 7. The most commonly used one is the Gaussian function. These functions are known as smooth functions that control the amount of smoothing where the h > 0. The KDE smooths each data; here, it is Xi, one after the other one until reaching the final density estimation.Figure 6
An example of the kernel density estimation and its histogram.Figure 7
Types of kernel density estimation curves.In addition to estimating the density function of univariate data, as an example given in Figure6, we can apply the KDE to multivariate datasets. In this case, we have to use a kernel function that could process a multidimensional dataset. To achieve this, the mentioned kernel function should be constructed by a product kernel or a radial basis approach. Let X=X1,X2,X3,…,Xd′ denote a sample of size n from a multivariate random variable with density fx defined on Rd, and let x1,…,xn be an independent random sample drawn from fx. In the following example, we only considered the two-dimensional case without the loss of generality. Thus, Xi,i=1,…,n is given by Xi1,Xi2, where Xi1 and Xi2 denote the x and y coordinates, respectively. The multivariate kernel density estimator at point x is given by(16)fh^x=1nh−1/2∑i=1nKh−1/2x−Xi,where K(.) is a multivariate kernel function and h denotes a symmetric positive definite bandwidth matrix.Although KDE is a nonparametric probability density function to solve the inhomogeneous distribution problem, we can also use it as a weighting function to support the compactness of clusters. As the KDE of any data is the summation of the data around it, it is expected the weight of any data close to the edges of data distribution would be less, while the KDE of the data in the near center would be more. Therefore, the KDE could be used as a weighting function to weight the data. In our approach, doing that will support the compactness of the cluster regardless of its shape. Namely, we used the KDE to weight each data to give more importance to the data in the denser regions. Therefore, we calculated the weight of each data that isWKDE according to obtained KDE value. For example, let us assume we want to find WKDE values for data x1 = 30 and x2 = 40 in the example of the dataset given in Figure 6. WKDE for x1 would be 0.007, while WKDE would be 0.05 for x2, which is very high when compared to the other one. That makes our approach superior when compared with existing clustering validity indices, which ignore the distribution of data in the same cluster. In other density-based approaches, they would weight x1 and x2 as equal for this example and this would be incorrect.


### 4.3. Definitions and Equations

In light of these explanations, let us explain the details of the VIASCKDE Index.Definition 1.
(CoSeD—Compactness and Separation Value of a Data): the CoSeD can be described as the compactness and separation value of any data. To calculate this value, WKDE value of each data, which is explained in Section 4.2, is calculated first. Let a(x) (compactness) be the distance from x to the closest data of cluster Ci in which the data x also belong, and let b(x) (separation) be the distance from x to the closest data of cluster Cj in which the data x do not belong to; therefore, the compactness and separation value of the data x, CoSeD(x), are calculated by the following equation:(17)ax=minx∈Ci,y∈Cidex,y,bx=minx∈Ci,y∈Cj,x≠ydex,y,CoSeDx=WKDEbx−axmaxax,bx.Definition 2.
(CoSeC—Compactness and Separation Value of a Cluster): the CoSeC value is the average of the CoSeD values of the data owned by the cluster. The CoSeC value of the cluster Ci is calculated by equation (18), where Ci is the cluster to which the data x belong, and n is the number of the data that cluster Ci possesses.(18)CoSeCCi=1n∑i=1nCoSeDxi.Definition 3.
(theVIASCKDE, the Value of Overall Clustering): let k be the number of clusters, let nj be the number of data that cluster Cj possesses, and let CoSeCj be the value of cluster Cj, which is calculated in equation (18); therefore, the VIASCKDE Index value is calculated by equation (19). The VIASCKDE value is expected to be in between [−1, +1], where +1 refers to the best possible value, and -1 refers to the worst possible value.(19)VIASCKDE=∑j=1knjCoSeCj∑j=1knj.


### 4.4. The Algorithm

Let Gaussian_KDE be a function that calculates the KDE and MinMaxNormalization, which is also a function that normalizes the data to the range of [0, 1]. The CoSeD and CoSeC values were explained in Section4.3. In light of this information and the equation given in the previous section, the pseudocode of VIASCKDE Index was given in Algorithm 1.Algorithm 1: VIASCKDE Index.
Input;X, labelsOutput; VIASCKDEKDE_X←Gaussian_KDE(X.T)fork = 1 to size (unique (labels)) dodata_of_Cluster_k←X[labels = k]   ►data belongs to cluster kdata_not_belong_k_X[labels ≠ k]   ►data not belongs to cluster kkde_k←MinMaxNormalization (KDE_X [labels = k]) ►KDE of each►data of cluster k and normalize themfori = 1 to size (data_of_k)doai ← closed_data (data_of_cluster_k)  ►distance from ithdata►to closed one in Cluster kbi ← closed_data (k_ait_olmagan_verileri)  ►distance from ith►data to closest one that does not in the cluster kCoSeDi = kde_k[i]∗[(bi−ai)/max(ai, bi0)]  ►Compactness and►Separation of data iCoSeCk = mean (CoSeDk)   ►Compactness-separation of Cluster kVIASCKDE = ∑j=1knj.CoSeCj/∑j=1knj   ►Overall VIASCKDE value of Clustering


### 4.5. Computational Complexity

Letk be the number of clusters in the dataset, let n be the number of data that clusters possess, and let d be the number of features each data possesses; therefore, the time complexity of the VIASCKDE Index is calculated as the O(kn2d), since it calculates the distance of each data to all others. This means that the complexity of the proposed approach is the O(n2). This is acceptable when the index is compared with the complexity of other indices given in Table 1.


## 4.1. Basic Idea

In the present study, a new cluster validation index, which has been named shortly the VIASCKDE (the Validity Index for Arbitrary-Shaped Clusters based on the Kernel Density Estimation) index, was proposed. The VIASCKDE Index is a kind of index that is not affected by cluster shape, and thus, it can make a realistic evaluation of clustering performance regardless of the clusters’ shape. Unlike the existing cluster validation indices, our index calculates the compactness and separation values of the cluster based on calculating the compactness and separation values for each data separately. In other words, it calculates the compactness and separation values of the cluster over the distance of data, independent of parameters such as the cluster center because, in nonspherical clusters, the distance of the data to the closest data is more important than its distance to the cluster center. As can be seen in the example given in Figure5, the closest data in the cluster that “it belongs to” are used when calculating the compactness value for the data x. Similarly, the separation value of x is calculated by the distance to the closest data of the cluster that “it does not belong.”Figure 5
Relationship between the compactness and separation values of any data in the VIASCKDE Index.As mentioned before, another problem with existing cluster validity indices is to assume that the distribution of the data inside the cluster has homogeneous distribution, even if the shape of the cluster is arbitrary. Therefore, they weight each data of the cluster as the same value, whereas, as presented in Figure4, the distribution of data that is inside the same cluster may vary. Therefore, we need a new method that considers this situation. To overcome this problem, we proposed the kernel density estimation (KDE), which is detailed in the next section based on weighting method.


## 4.2. Kernel Density Estimation-Based Weighting

In the literature, there are two types of distribution estimation methods that are parametric and nonparametric. In parametric methods, for example, the Gaussian distribution assumes the distribution of any dataset is gathered around the center and the majority of the data is in a circle having a radius of the standard deviation. It means that the curve has only one peak on distribution. It is important to keep in mind that the univariate normal distribution, with meanµ and variance σ2, has the probability density function(13)fx=12πσ2e−x−μ/σ2/2,where x is in -∞ < x < ∞ interval. On the other hand, in nonparametric distribution estimation methods, it is assumed that there may be more than one distribution peaks on the curve. Let X=X1,…,XnT be an n-dimensional vector that has a multivariate Gaussian (or normal) distribution with the n-dimensional mean vector μϵRn and ∑ be the n x n covariance matrix. The multivariate Gaussian distribution is calculated as follows:(14)px,μ,Σ=12πnΣexp−12π−μTΣ−1x−μ.The kernel density estimation (KDE) is a nonparametric density estimator that is used for density estimation. It is also a method that is used to analyze existing data to decide which incoming data is placed correctly in which place. For this ability, it is commonly used in many areas such as data analysis procedures in healthcare services, artificial intelligence applications, the stock market, and many other areas [2]. The bar graph represents the histograms, and the orange line represents the KDE, and it is calculated over the histograms as presented in Figure 6. In analyzing the data and representing its application, it figures out the distribution of data according to various methods, which are given in Figure 7. Each one has its characteristic and equation. In mathematical formulation, the KDE is a function(15)Pn^n=1nh∑i=1nKXi−xh,where K(.) is one of the functions, which are given in Figure 7. The most commonly used one is the Gaussian function. These functions are known as smooth functions that control the amount of smoothing where the h > 0. The KDE smooths each data; here, it is Xi, one after the other one until reaching the final density estimation.Figure 6
An example of the kernel density estimation and its histogram.Figure 7
Types of kernel density estimation curves.In addition to estimating the density function of univariate data, as an example given in Figure6, we can apply the KDE to multivariate datasets. In this case, we have to use a kernel function that could process a multidimensional dataset. To achieve this, the mentioned kernel function should be constructed by a product kernel or a radial basis approach. Let X=X1,X2,X3,…,Xd′ denote a sample of size n from a multivariate random variable with density fx defined on Rd, and let x1,…,xn be an independent random sample drawn from fx. In the following example, we only considered the two-dimensional case without the loss of generality. Thus, Xi,i=1,…,n is given by Xi1,Xi2, where Xi1 and Xi2 denote the x and y coordinates, respectively. The multivariate kernel density estimator at point x is given by(16)fh^x=1nh−1/2∑i=1nKh−1/2x−Xi,where K(.) is a multivariate kernel function and h denotes a symmetric positive definite bandwidth matrix.Although KDE is a nonparametric probability density function to solve the inhomogeneous distribution problem, we can also use it as a weighting function to support the compactness of clusters. As the KDE of any data is the summation of the data around it, it is expected the weight of any data close to the edges of data distribution would be less, while the KDE of the data in the near center would be more. Therefore, the KDE could be used as a weighting function to weight the data. In our approach, doing that will support the compactness of the cluster regardless of its shape. Namely, we used the KDE to weight each data to give more importance to the data in the denser regions. Therefore, we calculated the weight of each data that isWKDE according to obtained KDE value. For example, let us assume we want to find WKDE values for data x1 = 30 and x2 = 40 in the example of the dataset given in Figure 6. WKDE for x1 would be 0.007, while WKDE would be 0.05 for x2, which is very high when compared to the other one. That makes our approach superior when compared with existing clustering validity indices, which ignore the distribution of data in the same cluster. In other density-based approaches, they would weight x1 and x2 as equal for this example and this would be incorrect.


## 4.3. Definitions and Equations

In light of these explanations, let us explain the details of the VIASCKDE Index.Definition 1.
(CoSeD—Compactness and Separation Value of a Data): the CoSeD can be described as the compactness and separation value of any data. To calculate this value, WKDE value of each data, which is explained in Section 4.2, is calculated first. Let a(x) (compactness) be the distance from x to the closest data of cluster Ci in which the data x also belong, and let b(x) (separation) be the distance from x to the closest data of cluster Cj in which the data x do not belong to; therefore, the compactness and separation value of the data x, CoSeD(x), are calculated by the following equation:(17)ax=minx∈Ci,y∈Cidex,y,bx=minx∈Ci,y∈Cj,x≠ydex,y,CoSeDx=WKDEbx−axmaxax,bx.Definition 2.
(CoSeC—Compactness and Separation Value of a Cluster): the CoSeC value is the average of the CoSeD values of the data owned by the cluster. The CoSeC value of the cluster Ci is calculated by equation (18), where Ci is the cluster to which the data x belong, and n is the number of the data that cluster Ci possesses.(18)CoSeCCi=1n∑i=1nCoSeDxi.Definition 3.
(theVIASCKDE, the Value of Overall Clustering): let k be the number of clusters, let nj be the number of data that cluster Cj possesses, and let CoSeCj be the value of cluster Cj, which is calculated in equation (18); therefore, the VIASCKDE Index value is calculated by equation (19). The VIASCKDE value is expected to be in between [−1, +1], where +1 refers to the best possible value, and -1 refers to the worst possible value.(19)VIASCKDE=∑j=1knjCoSeCj∑j=1knj.


## 4.4. The Algorithm

Let Gaussian_KDE be a function that calculates the KDE and MinMaxNormalization, which is also a function that normalizes the data to the range of [0, 1]. The CoSeD and CoSeC values were explained in Section4.3. In light of this information and the equation given in the previous section, the pseudocode of VIASCKDE Index was given in Algorithm 1.Algorithm 1: VIASCKDE Index.
Input;X, labelsOutput; VIASCKDEKDE_X←Gaussian_KDE(X.T)fork = 1 to size (unique (labels)) dodata_of_Cluster_k←X[labels = k]   ►data belongs to cluster kdata_not_belong_k_X[labels ≠ k]   ►data not belongs to cluster kkde_k←MinMaxNormalization (KDE_X [labels = k]) ►KDE of each►data of cluster k and normalize themfori = 1 to size (data_of_k)doai ← closed_data (data_of_cluster_k)  ►distance from ithdata►to closed one in Cluster kbi ← closed_data (k_ait_olmagan_verileri)  ►distance from ith►data to closest one that does not in the cluster kCoSeDi = kde_k[i]∗[(bi−ai)/max(ai, bi0)]  ►Compactness and►Separation of data iCoSeCk = mean (CoSeDk)   ►Compactness-separation of Cluster kVIASCKDE = ∑j=1knj.CoSeCj/∑j=1knj   ►Overall VIASCKDE value of Clustering


## 4.5. Computational Complexity

Letk be the number of clusters in the dataset, let n be the number of data that clusters possess, and let d be the number of features each data possesses; therefore, the time complexity of the VIASCKDE Index is calculated as the O(kn2d), since it calculates the distance of each data to all others. This means that the complexity of the proposed approach is the O(n2). This is acceptable when the index is compared with the complexity of other indices given in Table 1.


## 5. Experimental Study

### 5.1. Development Environment

To demonstrate the effectiveness of the VIASCKDE Index (https://github.com/senolali/VIASCKDE) on the experimental studies, the data were processed with using the Python language in the Anaconda Spyder environment. Various machine learning libraries of the Scikit-learn library such as the DBSCAN, Spectral Clustering, HDBSCAN, and metrics were used. The dataset was imported with the Pandas library, and mathematical operations were performed with the NumPy library. Visualization processes were also carried out with the matplotlib library. All experiments and comparison operations were performed on a computer with 16 GB RAM, Intel i7 processor, and Windows 11 operating system.


### 5.2. Used Datasets

To measure the performance of the proposed approach, we performed an experimental study in both synthetic and real datasets. Since the main purpose of our approach is to measure the performance of nonspherical clusters, artificial datasets containing clusters in different shapes were used. In Figure3, some of the used datasets that contain clusters in different shapes are demonstrated. In addition to these synthetic datasets, real datasets, which are frequently used in the clustering field, were also used for testing. Details of the datasets used in the comparison process are provided in Table 2. Additionally, as given in Figure 8, some imbalanced datasets were used to analyze the performance of our cluster validation index on the imbalanced data distribution.Table 2
Used datasets.
DatasetType# of Features# of data# of classesReferenceHalf-kernelSynthetic210002[45]Two spiralsSynthetic23123[45]OutlierSynthetic27004[45]CornersSynthetic220004[45]Cluster in clusterSynthetic210122[45]Crescent full moonSynthetic210002[45]MoonSynthetic25144[45]FaceSynthetic23224[46]WaveSynthetic22872[46]AggregationSynthetic27887[47]Zelnik1Synthetic26224[48]Zelnik5Synthetic25124[48]XclaraSynthetic230003[48]BananaSynthetic248112[48]D2c2sc13Synthetic258813[48]2sp2globSynthetic29993[48]Cure-t1-200nSynthetic220005[48]ThyroidReal42152[49]Fisher irisReal41503[49]Breast cancerReal86992[49]Figure 8
The distributions of some of the used datasets.


### 5.3. Experimental Procedure

For the experimental study, we used the procedure given below. But firstly, to ensure that each data are between the same ranges and to make it easy to determine parameters, the data were normalized using the min-max normalization that was demonstrated in (20). In addition, the ARI (Adjusted Rand Index) was used as the ground truth method to evaluate the performance of cluster validation indices by comparing the cluster labels that were produced by the clustering algorithm with the actual cluster labels. The reason we chose the ARI is that the generated cluster labels do not need to be the same as the actual cluster labels. For example, let us assume the clustering algorithm produced {1,1,1,2,2,2} cluster labels and actual labels are {2,2,2,4,4,4}. The accuracy value for this situation would be 0%, while it would be 100% with the ARI value, which should be the actual result.(20)zij=xij−minxjmaxxj−minxj.The procedure established in the testing process is as follows:Step #1:Select one of the algorithms (DBSCAN,HDBSCAN, and Spectral Clustering)Step #2:Test the algorithm with randomly selected parameters on one of the selected datasets.Step #3:Evaluate the cluster qualities of clusters that were produced by the selected algorithm with clustering validation indices (SI, DI, CH, DB, S_Dbw, DSI, RMSSTD, and VIASCKDE).Step #4:Calculate the VIASCKDE Index via produced clusters and evaluate it to see whether this is the best result so far. If it is, we accept this value as the best one for the VIASCKDE Index. Then, we do the same operation for the other indices.Step #5:To test each index sufficiently, go to Step #2 and repeat the cycle 100 times. If the cycle is completed go to Step #6.Step #6:Calculate the ARI value that corresponds to the most successful value obtained for each of the clustering validity indices including our proposed approach.Step #7:Compare the ARI values calculated by all cluster validity indices. Consider the one with the highest ARI value as the most competent one for this dataset.Step #8:Go to Step 2 and do the same operations for the new dataset. If all datasets are performed, go to Step 9.Step #9:If all algorithms are performed, finish the procedure; otherwise, go to Step 1.


### 5.4. Experimental Study

#### 5.4.1. The Selection of Density Distribution Estimation Method

We performed some experimental studies on the datasets to decide which data distribution method should be selected, either parametric or nonparametric. For the parametric method, we selected the Gaussian method and the KDE for the nonparametric method. We carried out experiments with the procedure given in Section5.3, by using the DBSCAN in which the parameters are randomly selected. Besides, the kernel = “Gaussian” and h = 0.05 were the parameters of KDE based on the VIASCKDE Index approach, while the Gaussian was the method of parametric VIASCKDE Index. According to obtained results, while the Gaussian-based method outperformed in 15 datasets, the KDE-based method was the best in 17 datasets, as demonstrated in Table 3. Therefore, we selected the KDE-based method as the weighting function for our approach.Table 3
ARI results obtained with the parametric and nonparametric methods.
DatasetsAdjusted Rand Index (ARI)MethodsGaussian WeightKDE WeightHalf-kernel1.00001.0000Two spirals1.00001.0000Outlier1.00001.0000Corners1.00001.0000Cluster in cluster1.00001.0000Crescent full moon1.00001.0000Moon0.74240.7424Face0.99491.0000Wave1.00001.0000Fisher iris0.74930.7493Breast cancer0.75400.7540Aggregation0.73380.9118Thyroid-0.06190.6783Zelnik11.00000.9488Zelnik51.00001.0000Xclara0.00010.0001Banana1.00001.0000Ds2c2sc130.31870.59042sp2glob1.00000.9880Cure-t1-2000n0.88500.8850


#### 5.4.2. The Kernel Selection for KDE

As mentioned in Section4.2, there are various kernels in the literature. The Gaussian, cosine, linear, tophat, and exponential can be given as examples, and they affect the smoothness of distribution. We fulfilled the operation with the procedure provided in Section 5.3 where the parameters of DBSCAN algorithm were selected randomly. We performed the experiments by choosing each kernel in each experimental study. As it can be seen in Table 4, the Gaussian kernel was the best in all of the selected datasets, when the bandwidth was 0.05.Table 4
Obtained results with the different kernels values.
KernelsDatasetsObtained VIASCKDE Values with eachkernelObtained ARI Values with eachkernelFaceAggregationOutliersThyroidCrescent full moonCure-t1-200nFaceAggregationOutliersThyroidCrescent full moonCure-t1-200nGaussian0.70630.63680.67970.49470.66230.65550.60850.82461.00000.50831.00000.8850Cosine0.59670.65640.64990.16990.63400.63430.60850.80891.00000.50831.00000.8850Exponential0.70050.63710.67140.55410.64260.66530.03860.80891.00000.50341.00000.8850Linear0.57360.64270.63060.15940.61690.63710.60850.80891.00000.50831.00000.8850Epanechnikov0.60210.65620.65810.17580.63880.62950.60850.80891.00000.50831.00000.8850Tophat0.64570.61650.64330.23060.66640.62990.60850.03331.00000.50831.00000.8850


#### 5.4.3. Bandwidth Selection for the KDE

One of the most important parameters of KDE is bandwidth (h). It possesses a direct effect on the results. When the h is too small, there would be many wiggly structures on the density curve. On the other hand, when the h is too large, the bumps on the curve would be smoothed out as given in Figure 9. To find which bandwidth is the best for our approach, we fulfilled some experimental studies with the procedure given in Section 5.3 by testing it with different bandwidth values on some datasets, which are provided in Table 2. The best bandwidth was found to be 0.05 as it can be seen in Table 5, when the kernel was the Gaussian.Figure 9
Types of the kernel density estimation curves.Table 5
Obtained results with the different bandwidth values.
BandwidthDatasetsObtained VIASCKDE values with eachbandwidthObtained ARI values with eachbandwidthFaceAggregationOutliersThyroidCrescent full moonCure-t1-200nFaceAggregationOutliersThyroidCrescent full moonCure-t1-200n0.010.33770.34440.46500.05560.47800.5264−0.03860.80891.00000.52771.00000.88500.030.66270.65650.65080.34930.66080.64210.60850.80891.00000.50341.00000.88500.050.70630.63880.67970.49470.66230.65550.60850.98981.00000.50341.00000.88500.10.73650.62250.68510.63060.64860.6565−0.03860.80891.00000.50341.00000.88500.30.78570.59470.67730.74020.61430.6189−0.03860.73381.00000.20991.00000.88500.50.75860.56890.54810.75910.59450.6039−0.03860.73381.00000.20991.00000.88501.00.74120.56360.52570.76180.59270.6018−0.03860.73381.00000.20991.00000.88501.50.73620.56290.52360.76180.59230.6016−0.03860.73381.00000.20991.00000.885020.73390.56260.52290.76180.59210.6015−0.03860.73381.00000.20991.00000.88502.50.73280.56250.52260.76180.59200.6015−0.03860.73381.00000.20991.00000.885030.73220.56240.52250.76180.59200.6015−0.03860.73381.00000.20991.00000.88503.50.73170.56240.52230.76180.59190.6015−0.03860.73381.00000.20991.00000.885040.73140.56230.52220.76170.59190.6015−0.03860.73381.00000.20991.00000.88504.50.33770.34440.46500.05560.47800.5264−0.03860.80891.00000.52771.00000.885050.66270.65650.65080.34930.66080.64210.60850.80891.00000.50341.00000.8850


#### 5.4.4. The Tests on Both Synthetic and Real Datasets

In this section, experimental works were executed on both synthetic and real datasets. To detect nonspherical clusters in the test process, the DBSCAN, Spectral Clustering, and HDBSCAN were used. The DBSCAN algorithm uses two parameters (MinPts: the clustering threshold value, and ε: the accessibility distance) and Spectral Clustering uses one parameter as input (n_clusters: the number of clusters) if the affinity =  “nearest_neighbors,” while the HDBSCAN Clustering uses two parameters (min_cluster_size: the number of clusters, and min_samples). To test each algorithm with different parameters, we performed the random search method on the procedure given in Section 5.3. The procedure given above with each cluster validity index was used as the leading method to reach better clustering results. As an example is given in Figure 10, each index proposed various results. It means that the cluster validation performance of each one is also different. According to obtained results, our index was the best one. The performance of each index in all datasets is presented in the following tables for each clustering algorithm (Tables 6–14).Figure 10
The clustering results suggested by each validity index when the DBSCAN algorithm was tested in the Aggregation dataset.Table 6
The best parameters for datasets that were detected by the cluster validity indices with the DBSCAN algorithm.
DatasetDBSCAN parametersBest parameters detected by indices for the DBSCAN algorithmSIDIDBCHS_DbwDSIRMSSTDVIASCKDEHalf-kernelε0.080.080.050.080.050.050.080.08MinPts77117151177Two spiralsε0.10.10.050.10.050.10.050.1MinPts1111151115111411Outlierε0.070.070.070.070.050.070.050.07MinPts151515158151415Cornersε0.10.10.10.10.10.10.10.1MinPts1515151515151515Cluster in clusterε0.060.060.060.060.060.060.060.06MinPts1212121212121412Crescent full moonε0.070.070.070.070.050.060.050.07MinPts1414141415121514Moonε0.060.080.060.060.050.050.060.06MinPts71197991515Faceε0.060.10.10.060.060.050.060.1MinPts158561512118Waveε0.090.090.060.090.050.060.050.06MinPts12512129121512Fisher irisε0.140.190.140.140.080.140.060.19MinPts156151551576Breast cancerε0.390.330.390.390.060.060.050.4MinPts858855145Aggregationε0.060.090.060.060.060.060.050.06MinPts137131314121413Thyroidε0.10.10.060.090.070.050.050.1MinPts551256895Zelnik1ε0.080.080.050.10.070.070.080.07MinPts61514755155Zelnik5ε0.060.10.050.10.060.050.050.1MinPts1413121315121413Xclaraε0.050.080.090.050.050.050.080.05MinPts1312151313131213Bananaε0.050.050.050.050.050.050.050.05MinPts99999999Ds2c2sc13ε0.090.090.060.060.050.060.090.05MinPts1010141413141082sp2globε0.10.10.050.070.080.10.060.07MinPts99121469514Cure-t1-2000nε0.10.10.10.10.10.10.10.1MinPts1010101010101010Table 7
Obtained values for each index based on the parameters given in Table6.
DatasetObtained values for the each indexSIDIDBCHS_DbwDSIRMSSTDVIASCKDEHalf-kernel0.20100.09491.8818127.89050.54190.50680.24950.7125Two spirals0.05880.13173.3241152.94470.58480.10690.280.7903Outlier0.56080.42910.40371075.56090.20990.96540.13020.6797Corners0.46140.28720.74362020.10680.49760.63580.11870.6295Cluster in cluster0.22310.2341208.84580.01690.85360.73320.22760.595Crescent full moon0.27840.19231.1646285.14230.32550.65680.24490.6623Moon0.23710.10520.9739244.17220.20810.87880.25250.7508Face0.45690.22171.1099213.02460.37250.76270.24230.6631Wave0.45250.12910.7119366.10950.23440.89350.26960.6495Fisher iris0.56920.12220.5234223.61370.33860.82960.25270.443Breast cancer0.56980.12280.8037900.19880.36060.96170.29930.2944Aggregation0.47630.14320.54611156.75390.20730.94420.18780.6388Thyroid0.4330.05982.762616.64290.53430.74860.15280.3275Zelnik10.20450.09925.697895.1960.25230.89390.21710.6604Zelnik50.49710.22240.8098413.88350.36510.83380.15340.7739Xclara0.66540.06561.18636889.01540.34920.74620.2290.8101Banana0.35890.12581.13223532.22010.76250.43340.21460.8076Ds2c2sc130.57240.2370.58911907.23880.19210.91930.10910.6052sp2glob0.38990.12782.7559158.51870.63740.80030.20890.8819Cure-t1-2000n0.45140.11960.67751365.07740.30540.7870.17210.6555Table 8
The best parameters for the datasets that were detected by the cluster validity indices with the Spectral Clustering algorithm are given in Table7.
DatasetSpectral clustering parametersBest parameters detected by indices for the Spectral Clustering algorithmSIDIDBCHS_DbwDSIRMSSTDVIASCKDEHalf-kerneln_clusters1421515141522Two spiralsn_clusters1521515151522Outliern_clusters244133424Cornersn_clusters1241212151422Cluster in clustern_clusters42415151522Crescent full moonn_clusters52513151426Moonn_clusters1521515151522Facen_clusters1121012151322Waven_clusters721515151522Fisher irisn_clusters222315223Breast cancern_clusters222211141512Aggregationn_clusters4261421522Thyroidn_clusters3233151523Zelnik1n_clusters1221312151333Zelnik5n_clusters82815151524Xclaran_clusters323310323Bananan_clusters92915141522Ds2c2sc13n_clusters3358215252sp2globn_clusters721515151527Cure-t1-2000nn_clusters5241321223Table 9
The best parameters for the datasets that were detected by the cluster validity indices with the HDBSCAN algorithm.
DatasetHDBSCAN ParameterBest parameters detected by the indices for the HDBSCAN algorithmSIDIDBCHS_DbwDSIRMSSTDVIASCKDEHalf-kerneln_clusters_size242422525252424n_samples661025252566Two spiralsn_clusters_size32531722156n_samples21727221912Outliern_clusters_size1616161616161616n_samples1212121212121212Cornersn_clusters_size88882288n_samples88882288Cluster in clustern_clusters_size2020911772020n_samples101022331010Crescent full moonn_clusters_size2020320332020n_samples1212212221212Moonn_clusters_size2262222102106n_samples34332425244Facen_clusters_size211392199139n_samples5198588198Waven_clusters_size16616163462n_samples1332313131935Fisher irisn_clusters_size5514551895n_samples1212161212212512Breast cancern_clusters_size1152522225n_samples3455355335355Aggregationn_clusters_size1712912232122n_samples25141614134144Thyroidn_clusters_size32333328n_samples272242164Zelnik1n_clusters_size11353202143n_samples1611251516171911Zelnik5n_clusters_size2020202020202020n_samples33333333Xclaran_clusters_size92231333313n_samples26393339Bananan_clusters_size2121132121162121n_samples1414161414241414Ds2c2sc13n_clusters_size222216224222416n_samples1919201961924102sp2globn_clusters_size2121212121212121n_samples2222222222222222Cure-t1-2000nn_clusters_size444444425n_samples66666664Table 10
Obtained values for each index based on the parameters are given in Table8.
DatasetObtained values for the each indexSIDIDBCHS_DbwRMSSTDDSIVIASCKDEHalf-kernel0.47480.09490.60661761.61980.22460.91630.24950.7395Two spirals0.31750.13171.0581378.8780.28570.78290.28650.8151Outlier0.61780.42910.40371804.4630.11760.96540.29240.6863Corners0.56720.28720.53154102.58830.18730.94390.2070.6575Cluster in cluster0.45470.23410.9465832.93850.27640.8570.22750.6052Crescent full moon0.49930.19230.57922022.70220.20550.91030.24230.6689Moon0.45430.12850.6781602.09070.21690.90980.26890.7527Face0.49960.23610.54731055.05730.17050.92710.24810.7575Wave0.49570.12910.631681.36810.16390.91240.25410.617Fisher iris0.62950.35810.4877356.2890.21630.89230.14320.4539Breast cancer0.58390.12910.7738993.01580.17960.77950.20310.4341Aggregation0.45410.10910.5891623.96840.14340.9210.29660.6944Thyroid0.55170.09730.85138.12910.38090.6850.13090.4832Zelnik10.50420.09920.663194.5860.28360.86140.21710.6544Zelnik50.59480.26510.53531832.56260.15480.94950.27630.7686Xclara0.69460.0230.420310843.72030.27790.9460.16120.8164Banana0.50870.12580.573414012.55970.18060.93430.21460.82Ds2c2sc130.39390.06390.80821133.55450.14340.90640.28960.61872sp2glob0.61020.14560.69211548.84650.25440.86930.23960.725Cure-t1-2000n0.49940.19210.65813615.53020.15820.90160.28170.6589Table 11
ARI values were obtained from the parameters that are given in Table6 and were proposed by each index.
DatasetObtained ARI values for the each indexSIDIDBCHS_DbwDSIRMSSTDVIASCKDEHalf-kernel1.00001.00000.99401.00000.91530.99401.00001.0000Two spirals1.00001.00000.98041.00000.98041.00000.99901.0000Outlier1.00001.00001.00001.00000.99731.00000.86211.0000Corners1.00001.00001.00001.00001.00001.00001.00001.0000Cluster in cluster1.00001.00001.00001.00001.00001.00000.88791.0000Crescent full moon1.00001.00000.99681.00000.91050.98730.85091.0000Moon0.93790.63220.92560.93790.78740.78740.79490.7949Face0.26450.99490.99610.28920.13040.12260.85210.9961Wave0.35141.00000.14410.35140.19130.14410.05080.0536Fisher iris0.45180.55030.45180.45180.23690.45180.01060.5503Breast cancer0.82400.81890.82400.8240−0.0779−0.0779−0.07800.8283Aggregation0.98980.73380.98980.98980.87700.98660.63300.9898Thyroid0.67150.6715−0.06640.73390.2940−0.1332−0.13960.6715Zelnik10.77081.00000.34090.78520.77240.77241.00000.7781Zelnik50.92141.00000.92781.00000.92160.91260.98391.0000Xclara0.98130.00010.00010.98130.98130.98130.00010.9813Banana1.00001.00001.00001.00001.00001.00001.00001.0000Ds2c2sc130.31870.31870.49110.49110.53250.49110.31870.59042sp2glob1.00001.00000.98500.99400.99851.00000.99700.9940Cure-t1-2000n0.88500.88500.88500.88500.88500.88500.88500.8850Table 12
ARI values, which were obtained from the parameters, were given in Table8 and were proposed by each index.
DatasetObtained ARI values for the each indexSIDIDBCHS_DbwRMSSTDDSIVIASCKDEHalf-kernel0.15141.00000.14220.14210.15150.14211.00001.0000Two spirals0.14011.00000.14350.14010.14010.14010.20471.0000Outlier0.84631.00001.00000.22360.23221.00000.22711.0000Corners0.45811.00000.45810.45810.39170.41990.33300.3330Cluster in cluster0.65841.00000.65840.13650.13680.13651.00001.0000Crescent full moon0.29341.00000.29340.10210.08690.09551.00000.2341Moon0.36290.29730.36290.36290.30920.30920.49160.4916Face0.06460.36620.07470.05800.04430.05380.36620.3662Wave0.29701.00000.13330.13230.13230.13561.00001.0000Fisher iris0.56810.56810.56810.74450.23950.56810.56810.7445Breast cancer0.89330.89330.89330.89330.28750.17790.06690.2534Aggregation0.79750.06460.90660.44530.04860.41560.11490.0646Thyroid0.63070.42040.63070.63070.08300.08300.42040.6307Zelnik10.31700.43520.30040.31700.22250.30071.00001.0000Zelnik50.65670.30960.65670.36380.37900.36380.50031.0000Xclara0.99390.62700.99390.99390.36020.99390.62700.9939Banana0.23941.00000.23940.13690.14630.13691.00001.0000Ds2c2sc130.32670.32670.27660.45310.02440.53440.02440.23942sp2glob0.78520.57090.32260.31950.31850.32260.57090.7852Cure-t1-2000n0.63340.34230.78180.33030.17570.35460.17570.8427Table 13
Obtained values for each index based on the parameters given in Table9.
DatasetObtained values for the each indexSIDIDBCHS_DbwDSIRMSSTDVIASCKDEHalf-kernel0.2010.09491.8878171.89840.55890.46620.24950.7125Two spirals0.40710.13171.1858259.03490.01360.99570.280.8151Outlier0.56080.42910.40371075.56090.20990.96540.12350.6881Corners0.46140.28720.74362020.10680.04370.97910.11870.6268Cluster in cluster0.22310.23414.40832.56240.06420.9470.22750.6052Crescent full moon0.27840.19231.0934285.14230.05270.98290.24230.6623Moon0.23710.07941.1729244.17220.32430.70210.26280.7002Face0.4170.22170.9539204.56650.40310.85570.23390.6654Wave0.37460.12911.1785168.99360.31550.78620.25410.617Fisher iris0.62950.35810.4659353.36740.44880.92960.14780.4722Breast cancer0.43060.11251.1919493.46320.19580.95750.29830.0143Aggregation0.49250.14320.6452778.94480.27010.84810.14970.6108Thyroid0.43590.06831.6838.42350.65190.79130.15320.3833Zelnik10.00080.099213.253512.74330.30220.72870.21710.541Zelnik50.46630.22241.0459413.88350.45930.74250.14930.7739Xclara0.67450.02951.2137008.87460.04750.99180.11140.7814Banana0.35890.12581.02883532.22010.76250.70030.21460.82Ds2c2sc130.57240.2370.58291785.90020.18310.89280.10930.60452sp2glob0.38990.12782.7973158.4080.63740.80030.20880.7146Cure-t1-2000n0.45140.11960.67751365.07740.30540.7870.17210.655Table 14
ARI values, which were obtained from the parameters, are given in Table9 and were proposed by each index.
DatasetObtained ARI values for the each indexSIDIDBCHS_DbwDSIRMSSTDVIASCKDEHalf-kernel1.00001.00000.99800.79010.79010.79011.00001.0000Two spirals0.00791.00000.00790.75240.00760.00760.99901.0000Outlier1.00001.00001.00001.00001.00001.00001.00001.0000Corners1.00001.00001.00001.00000.82610.82611.00001.0000Cluster in cluster1.00001.00000.52850.53600.52740.52741.00001.0000Crescent full moon1.00001.00000.11601.00000.11600.11601.00001.0000Moon0.93791.00000.93790.93790.29330.36970.29331.0000Face0.18830.99491.00000.18831.00001.00000.99491.0000Wave0.26091.00000.17090.26090.25280.21401.00001.0000Fisher iris0.56810.56810.56570.56810.56810.56380.54820.5682Breast cancer0.83490.85220.00110.85220.00110.0011-0.07070.8522Aggregation0.79620.73380.73230.73380.81540.80890.73380.8089Thyroid0.48850.56620.48850.48850.48800.4885-0.02550.4873Zelnik10.93131.00000.32070.88801.00000.96800.97711.0000Zelnik51.00001.00001.00001.00001.00001.00001.00001.0000Xclara0.98610.99040.39360.98800.39360.39360.39360.9904Banana1.00001.00000.83081.00001.00000.82781.00001.0000Ds2c2sc130.31870.31870.31800.31870.76240.31870.31650.42602sp2glob1.00001.00001.00001.00001.00001.00001.00001.0000Cure-t1-2000n0.88500.88500.88500.88500.88500.88500.88500.8850


## 5.1. Development Environment

To demonstrate the effectiveness of the VIASCKDE Index (https://github.com/senolali/VIASCKDE) on the experimental studies, the data were processed with using the Python language in the Anaconda Spyder environment. Various machine learning libraries of the Scikit-learn library such as the DBSCAN, Spectral Clustering, HDBSCAN, and metrics were used. The dataset was imported with the Pandas library, and mathematical operations were performed with the NumPy library. Visualization processes were also carried out with the matplotlib library. All experiments and comparison operations were performed on a computer with 16 GB RAM, Intel i7 processor, and Windows 11 operating system.


## 5.2. Used Datasets

To measure the performance of the proposed approach, we performed an experimental study in both synthetic and real datasets. Since the main purpose of our approach is to measure the performance of nonspherical clusters, artificial datasets containing clusters in different shapes were used. In Figure3, some of the used datasets that contain clusters in different shapes are demonstrated. In addition to these synthetic datasets, real datasets, which are frequently used in the clustering field, were also used for testing. Details of the datasets used in the comparison process are provided in Table 2. Additionally, as given in Figure 8, some imbalanced datasets were used to analyze the performance of our cluster validation index on the imbalanced data distribution.Table 2
Used datasets.
DatasetType# of Features# of data# of classesReferenceHalf-kernelSynthetic210002[45]Two spiralsSynthetic23123[45]OutlierSynthetic27004[45]CornersSynthetic220004[45]Cluster in clusterSynthetic210122[45]Crescent full moonSynthetic210002[45]MoonSynthetic25144[45]FaceSynthetic23224[46]WaveSynthetic22872[46]AggregationSynthetic27887[47]Zelnik1Synthetic26224[48]Zelnik5Synthetic25124[48]XclaraSynthetic230003[48]BananaSynthetic248112[48]D2c2sc13Synthetic258813[48]2sp2globSynthetic29993[48]Cure-t1-200nSynthetic220005[48]ThyroidReal42152[49]Fisher irisReal41503[49]Breast cancerReal86992[49]Figure 8
The distributions of some of the used datasets.


## 5.3. Experimental Procedure

For the experimental study, we used the procedure given below. But firstly, to ensure that each data are between the same ranges and to make it easy to determine parameters, the data were normalized using the min-max normalization that was demonstrated in (20). In addition, the ARI (Adjusted Rand Index) was used as the ground truth method to evaluate the performance of cluster validation indices by comparing the cluster labels that were produced by the clustering algorithm with the actual cluster labels. The reason we chose the ARI is that the generated cluster labels do not need to be the same as the actual cluster labels. For example, let us assume the clustering algorithm produced {1,1,1,2,2,2} cluster labels and actual labels are {2,2,2,4,4,4}. The accuracy value for this situation would be 0%, while it would be 100% with the ARI value, which should be the actual result.(20)zij=xij−minxjmaxxj−minxj.The procedure established in the testing process is as follows:Step #1:Select one of the algorithms (DBSCAN,HDBSCAN, and Spectral Clustering)Step #2:Test the algorithm with randomly selected parameters on one of the selected datasets.Step #3:Evaluate the cluster qualities of clusters that were produced by the selected algorithm with clustering validation indices (SI, DI, CH, DB, S_Dbw, DSI, RMSSTD, and VIASCKDE).Step #4:Calculate the VIASCKDE Index via produced clusters and evaluate it to see whether this is the best result so far. If it is, we accept this value as the best one for the VIASCKDE Index. Then, we do the same operation for the other indices.Step #5:To test each index sufficiently, go to Step #2 and repeat the cycle 100 times. If the cycle is completed go to Step #6.Step #6:Calculate the ARI value that corresponds to the most successful value obtained for each of the clustering validity indices including our proposed approach.Step #7:Compare the ARI values calculated by all cluster validity indices. Consider the one with the highest ARI value as the most competent one for this dataset.Step #8:Go to Step 2 and do the same operations for the new dataset. If all datasets are performed, go to Step 9.Step #9:If all algorithms are performed, finish the procedure; otherwise, go to Step 1.


## 5.4. Experimental Study

### 5.4.1. The Selection of Density Distribution Estimation Method

We performed some experimental studies on the datasets to decide which data distribution method should be selected, either parametric or nonparametric. For the parametric method, we selected the Gaussian method and the KDE for the nonparametric method. We carried out experiments with the procedure given in Section5.3, by using the DBSCAN in which the parameters are randomly selected. Besides, the kernel = “Gaussian” and h = 0.05 were the parameters of KDE based on the VIASCKDE Index approach, while the Gaussian was the method of parametric VIASCKDE Index. According to obtained results, while the Gaussian-based method outperformed in 15 datasets, the KDE-based method was the best in 17 datasets, as demonstrated in Table 3. Therefore, we selected the KDE-based method as the weighting function for our approach.Table 3
ARI results obtained with the parametric and nonparametric methods.
DatasetsAdjusted Rand Index (ARI)MethodsGaussian WeightKDE WeightHalf-kernel1.00001.0000Two spirals1.00001.0000Outlier1.00001.0000Corners1.00001.0000Cluster in cluster1.00001.0000Crescent full moon1.00001.0000Moon0.74240.7424Face0.99491.0000Wave1.00001.0000Fisher iris0.74930.7493Breast cancer0.75400.7540Aggregation0.73380.9118Thyroid-0.06190.6783Zelnik11.00000.9488Zelnik51.00001.0000Xclara0.00010.0001Banana1.00001.0000Ds2c2sc130.31870.59042sp2glob1.00000.9880Cure-t1-2000n0.88500.8850


### 5.4.2. The Kernel Selection for KDE

As mentioned in Section4.2, there are various kernels in the literature. The Gaussian, cosine, linear, tophat, and exponential can be given as examples, and they affect the smoothness of distribution. We fulfilled the operation with the procedure provided in Section 5.3 where the parameters of DBSCAN algorithm were selected randomly. We performed the experiments by choosing each kernel in each experimental study. As it can be seen in Table 4, the Gaussian kernel was the best in all of the selected datasets, when the bandwidth was 0.05.Table 4
Obtained results with the different kernels values.
KernelsDatasetsObtained VIASCKDE Values with eachkernelObtained ARI Values with eachkernelFaceAggregationOutliersThyroidCrescent full moonCure-t1-200nFaceAggregationOutliersThyroidCrescent full moonCure-t1-200nGaussian0.70630.63680.67970.49470.66230.65550.60850.82461.00000.50831.00000.8850Cosine0.59670.65640.64990.16990.63400.63430.60850.80891.00000.50831.00000.8850Exponential0.70050.63710.67140.55410.64260.66530.03860.80891.00000.50341.00000.8850Linear0.57360.64270.63060.15940.61690.63710.60850.80891.00000.50831.00000.8850Epanechnikov0.60210.65620.65810.17580.63880.62950.60850.80891.00000.50831.00000.8850Tophat0.64570.61650.64330.23060.66640.62990.60850.03331.00000.50831.00000.8850


### 5.4.3. Bandwidth Selection for the KDE

One of the most important parameters of KDE is bandwidth (h). It possesses a direct effect on the results. When the h is too small, there would be many wiggly structures on the density curve. On the other hand, when the h is too large, the bumps on the curve would be smoothed out as given in Figure 9. To find which bandwidth is the best for our approach, we fulfilled some experimental studies with the procedure given in Section 5.3 by testing it with different bandwidth values on some datasets, which are provided in Table 2. The best bandwidth was found to be 0.05 as it can be seen in Table 5, when the kernel was the Gaussian.Figure 9
Types of the kernel density estimation curves.Table 5
Obtained results with the different bandwidth values.
BandwidthDatasetsObtained VIASCKDE values with eachbandwidthObtained ARI values with eachbandwidthFaceAggregationOutliersThyroidCrescent full moonCure-t1-200nFaceAggregationOutliersThyroidCrescent full moonCure-t1-200n0.010.33770.34440.46500.05560.47800.5264−0.03860.80891.00000.52771.00000.88500.030.66270.65650.65080.34930.66080.64210.60850.80891.00000.50341.00000.88500.050.70630.63880.67970.49470.66230.65550.60850.98981.00000.50341.00000.88500.10.73650.62250.68510.63060.64860.6565−0.03860.80891.00000.50341.00000.88500.30.78570.59470.67730.74020.61430.6189−0.03860.73381.00000.20991.00000.88500.50.75860.56890.54810.75910.59450.6039−0.03860.73381.00000.20991.00000.88501.00.74120.56360.52570.76180.59270.6018−0.03860.73381.00000.20991.00000.88501.50.73620.56290.52360.76180.59230.6016−0.03860.73381.00000.20991.00000.885020.73390.56260.52290.76180.59210.6015−0.03860.73381.00000.20991.00000.88502.50.73280.56250.52260.76180.59200.6015−0.03860.73381.00000.20991.00000.885030.73220.56240.52250.76180.59200.6015−0.03860.73381.00000.20991.00000.88503.50.73170.56240.52230.76180.59190.6015−0.03860.73381.00000.20991.00000.885040.73140.56230.52220.76170.59190.6015−0.03860.73381.00000.20991.00000.88504.50.33770.34440.46500.05560.47800.5264−0.03860.80891.00000.52771.00000.885050.66270.65650.65080.34930.66080.64210.60850.80891.00000.50341.00000.8850


### 5.4.4. The Tests on Both Synthetic and Real Datasets

In this section, experimental works were executed on both synthetic and real datasets. To detect nonspherical clusters in the test process, the DBSCAN, Spectral Clustering, and HDBSCAN were used. The DBSCAN algorithm uses two parameters (MinPts: the clustering threshold value, and ε: the accessibility distance) and Spectral Clustering uses one parameter as input (n_clusters: the number of clusters) if the affinity =  “nearest_neighbors,” while the HDBSCAN Clustering uses two parameters (min_cluster_size: the number of clusters, and min_samples). To test each algorithm with different parameters, we performed the random search method on the procedure given in Section 5.3. The procedure given above with each cluster validity index was used as the leading method to reach better clustering results. As an example is given in Figure 10, each index proposed various results. It means that the cluster validation performance of each one is also different. According to obtained results, our index was the best one. The performance of each index in all datasets is presented in the following tables for each clustering algorithm (Tables 6–14).Figure 10
The clustering results suggested by each validity index when the DBSCAN algorithm was tested in the Aggregation dataset.Table 6
The best parameters for datasets that were detected by the cluster validity indices with the DBSCAN algorithm.
DatasetDBSCAN parametersBest parameters detected by indices for the DBSCAN algorithmSIDIDBCHS_DbwDSIRMSSTDVIASCKDEHalf-kernelε0.080.080.050.080.050.050.080.08MinPts77117151177Two spiralsε0.10.10.050.10.050.10.050.1MinPts1111151115111411Outlierε0.070.070.070.070.050.070.050.07MinPts151515158151415Cornersε0.10.10.10.10.10.10.10.1MinPts1515151515151515Cluster in clusterε0.060.060.060.060.060.060.060.06MinPts1212121212121412Crescent full moonε0.070.070.070.070.050.060.050.07MinPts1414141415121514Moonε0.060.080.060.060.050.050.060.06MinPts71197991515Faceε0.060.10.10.060.060.050.060.1MinPts158561512118Waveε0.090.090.060.090.050.060.050.06MinPts12512129121512Fisher irisε0.140.190.140.140.080.140.060.19MinPts156151551576Breast cancerε0.390.330.390.390.060.060.050.4MinPts858855145Aggregationε0.060.090.060.060.060.060.050.06MinPts137131314121413Thyroidε0.10.10.060.090.070.050.050.1MinPts551256895Zelnik1ε0.080.080.050.10.070.070.080.07MinPts61514755155Zelnik5ε0.060.10.050.10.060.050.050.1MinPts1413121315121413Xclaraε0.050.080.090.050.050.050.080.05MinPts1312151313131213Bananaε0.050.050.050.050.050.050.050.05MinPts99999999Ds2c2sc13ε0.090.090.060.060.050.060.090.05MinPts1010141413141082sp2globε0.10.10.050.070.080.10.060.07MinPts99121469514Cure-t1-2000nε0.10.10.10.10.10.10.10.1MinPts1010101010101010Table 7
Obtained values for each index based on the parameters given in Table6.
DatasetObtained values for the each indexSIDIDBCHS_DbwDSIRMSSTDVIASCKDEHalf-kernel0.20100.09491.8818127.89050.54190.50680.24950.7125Two spirals0.05880.13173.3241152.94470.58480.10690.280.7903Outlier0.56080.42910.40371075.56090.20990.96540.13020.6797Corners0.46140.28720.74362020.10680.49760.63580.11870.6295Cluster in cluster0.22310.2341208.84580.01690.85360.73320.22760.595Crescent full moon0.27840.19231.1646285.14230.32550.65680.24490.6623Moon0.23710.10520.9739244.17220.20810.87880.25250.7508Face0.45690.22171.1099213.02460.37250.76270.24230.6631Wave0.45250.12910.7119366.10950.23440.89350.26960.6495Fisher iris0.56920.12220.5234223.61370.33860.82960.25270.443Breast cancer0.56980.12280.8037900.19880.36060.96170.29930.2944Aggregation0.47630.14320.54611156.75390.20730.94420.18780.6388Thyroid0.4330.05982.762616.64290.53430.74860.15280.3275Zelnik10.20450.09925.697895.1960.25230.89390.21710.6604Zelnik50.49710.22240.8098413.88350.36510.83380.15340.7739Xclara0.66540.06561.18636889.01540.34920.74620.2290.8101Banana0.35890.12581.13223532.22010.76250.43340.21460.8076Ds2c2sc130.57240.2370.58911907.23880.19210.91930.10910.6052sp2glob0.38990.12782.7559158.51870.63740.80030.20890.8819Cure-t1-2000n0.45140.11960.67751365.07740.30540.7870.17210.6555Table 8
The best parameters for the datasets that were detected by the cluster validity indices with the Spectral Clustering algorithm are given in Table7.
DatasetSpectral clustering parametersBest parameters detected by indices for the Spectral Clustering algorithmSIDIDBCHS_DbwDSIRMSSTDVIASCKDEHalf-kerneln_clusters1421515141522Two spiralsn_clusters1521515151522Outliern_clusters244133424Cornersn_clusters1241212151422Cluster in clustern_clusters42415151522Crescent full moonn_clusters52513151426Moonn_clusters1521515151522Facen_clusters1121012151322Waven_clusters721515151522Fisher irisn_clusters222315223Breast cancern_clusters222211141512Aggregationn_clusters4261421522Thyroidn_clusters3233151523Zelnik1n_clusters1221312151333Zelnik5n_clusters82815151524Xclaran_clusters323310323Bananan_clusters92915141522Ds2c2sc13n_clusters3358215252sp2globn_clusters721515151527Cure-t1-2000nn_clusters5241321223Table 9
The best parameters for the datasets that were detected by the cluster validity indices with the HDBSCAN algorithm.
DatasetHDBSCAN ParameterBest parameters detected by the indices for the HDBSCAN algorithmSIDIDBCHS_DbwDSIRMSSTDVIASCKDEHalf-kerneln_clusters_size242422525252424n_samples661025252566Two spiralsn_clusters_size32531722156n_samples21727221912Outliern_clusters_size1616161616161616n_samples1212121212121212Cornersn_clusters_size88882288n_samples88882288Cluster in clustern_clusters_size2020911772020n_samples101022331010Crescent full moonn_clusters_size2020320332020n_samples1212212221212Moonn_clusters_size2262222102106n_samples34332425244Facen_clusters_size211392199139n_samples5198588198Waven_clusters_size16616163462n_samples1332313131935Fisher irisn_clusters_size5514551895n_samples1212161212212512Breast cancern_clusters_size1152522225n_samples3455355335355Aggregationn_clusters_size1712912232122n_samples25141614134144Thyroidn_clusters_size32333328n_samples272242164Zelnik1n_clusters_size11353202143n_samples1611251516171911Zelnik5n_clusters_size2020202020202020n_samples33333333Xclaran_clusters_size92231333313n_samples26393339Bananan_clusters_size2121132121162121n_samples1414161414241414Ds2c2sc13n_clusters_size222216224222416n_samples1919201961924102sp2globn_clusters_size2121212121212121n_samples2222222222222222Cure-t1-2000nn_clusters_size444444425n_samples66666664Table 10
Obtained values for each index based on the parameters are given in Table8.
DatasetObtained values for the each indexSIDIDBCHS_DbwRMSSTDDSIVIASCKDEHalf-kernel0.47480.09490.60661761.61980.22460.91630.24950.7395Two spirals0.31750.13171.0581378.8780.28570.78290.28650.8151Outlier0.61780.42910.40371804.4630.11760.96540.29240.6863Corners0.56720.28720.53154102.58830.18730.94390.2070.6575Cluster in cluster0.45470.23410.9465832.93850.27640.8570.22750.6052Crescent full moon0.49930.19230.57922022.70220.20550.91030.24230.6689Moon0.45430.12850.6781602.09070.21690.90980.26890.7527Face0.49960.23610.54731055.05730.17050.92710.24810.7575Wave0.49570.12910.631681.36810.16390.91240.25410.617Fisher iris0.62950.35810.4877356.2890.21630.89230.14320.4539Breast cancer0.58390.12910.7738993.01580.17960.77950.20310.4341Aggregation0.45410.10910.5891623.96840.14340.9210.29660.6944Thyroid0.55170.09730.85138.12910.38090.6850.13090.4832Zelnik10.50420.09920.663194.5860.28360.86140.21710.6544Zelnik50.59480.26510.53531832.56260.15480.94950.27630.7686Xclara0.69460.0230.420310843.72030.27790.9460.16120.8164Banana0.50870.12580.573414012.55970.18060.93430.21460.82Ds2c2sc130.39390.06390.80821133.55450.14340.90640.28960.61872sp2glob0.61020.14560.69211548.84650.25440.86930.23960.725Cure-t1-2000n0.49940.19210.65813615.53020.15820.90160.28170.6589Table 11
ARI values were obtained from the parameters that are given in Table6 and were proposed by each index.
DatasetObtained ARI values for the each indexSIDIDBCHS_DbwDSIRMSSTDVIASCKDEHalf-kernel1.00001.00000.99401.00000.91530.99401.00001.0000Two spirals1.00001.00000.98041.00000.98041.00000.99901.0000Outlier1.00001.00001.00001.00000.99731.00000.86211.0000Corners1.00001.00001.00001.00001.00001.00001.00001.0000Cluster in cluster1.00001.00001.00001.00001.00001.00000.88791.0000Crescent full moon1.00001.00000.99681.00000.91050.98730.85091.0000Moon0.93790.63220.92560.93790.78740.78740.79490.7949Face0.26450.99490.99610.28920.13040.12260.85210.9961Wave0.35141.00000.14410.35140.19130.14410.05080.0536Fisher iris0.45180.55030.45180.45180.23690.45180.01060.5503Breast cancer0.82400.81890.82400.8240−0.0779−0.0779−0.07800.8283Aggregation0.98980.73380.98980.98980.87700.98660.63300.9898Thyroid0.67150.6715−0.06640.73390.2940−0.1332−0.13960.6715Zelnik10.77081.00000.34090.78520.77240.77241.00000.7781Zelnik50.92141.00000.92781.00000.92160.91260.98391.0000Xclara0.98130.00010.00010.98130.98130.98130.00010.9813Banana1.00001.00001.00001.00001.00001.00001.00001.0000Ds2c2sc130.31870.31870.49110.49110.53250.49110.31870.59042sp2glob1.00001.00000.98500.99400.99851.00000.99700.9940Cure-t1-2000n0.88500.88500.88500.88500.88500.88500.88500.8850Table 12
ARI values, which were obtained from the parameters, were given in Table8 and were proposed by each index.
DatasetObtained ARI values for the each indexSIDIDBCHS_DbwRMSSTDDSIVIASCKDEHalf-kernel0.15141.00000.14220.14210.15150.14211.00001.0000Two spirals0.14011.00000.14350.14010.14010.14010.20471.0000Outlier0.84631.00001.00000.22360.23221.00000.22711.0000Corners0.45811.00000.45810.45810.39170.41990.33300.3330Cluster in cluster0.65841.00000.65840.13650.13680.13651.00001.0000Crescent full moon0.29341.00000.29340.10210.08690.09551.00000.2341Moon0.36290.29730.36290.36290.30920.30920.49160.4916Face0.06460.36620.07470.05800.04430.05380.36620.3662Wave0.29701.00000.13330.13230.13230.13561.00001.0000Fisher iris0.56810.56810.56810.74450.23950.56810.56810.7445Breast cancer0.89330.89330.89330.89330.28750.17790.06690.2534Aggregation0.79750.06460.90660.44530.04860.41560.11490.0646Thyroid0.63070.42040.63070.63070.08300.08300.42040.6307Zelnik10.31700.43520.30040.31700.22250.30071.00001.0000Zelnik50.65670.30960.65670.36380.37900.36380.50031.0000Xclara0.99390.62700.99390.99390.36020.99390.62700.9939Banana0.23941.00000.23940.13690.14630.13691.00001.0000Ds2c2sc130.32670.32670.27660.45310.02440.53440.02440.23942sp2glob0.78520.57090.32260.31950.31850.32260.57090.7852Cure-t1-2000n0.63340.34230.78180.33030.17570.35460.17570.8427Table 13
Obtained values for each index based on the parameters given in Table9.
DatasetObtained values for the each indexSIDIDBCHS_DbwDSIRMSSTDVIASCKDEHalf-kernel0.2010.09491.8878171.89840.55890.46620.24950.7125Two spirals0.40710.13171.1858259.03490.01360.99570.280.8151Outlier0.56080.42910.40371075.56090.20990.96540.12350.6881Corners0.46140.28720.74362020.10680.04370.97910.11870.6268Cluster in cluster0.22310.23414.40832.56240.06420.9470.22750.6052Crescent full moon0.27840.19231.0934285.14230.05270.98290.24230.6623Moon0.23710.07941.1729244.17220.32430.70210.26280.7002Face0.4170.22170.9539204.56650.40310.85570.23390.6654Wave0.37460.12911.1785168.99360.31550.78620.25410.617Fisher iris0.62950.35810.4659353.36740.44880.92960.14780.4722Breast cancer0.43060.11251.1919493.46320.19580.95750.29830.0143Aggregation0.49250.14320.6452778.94480.27010.84810.14970.6108Thyroid0.43590.06831.6838.42350.65190.79130.15320.3833Zelnik10.00080.099213.253512.74330.30220.72870.21710.541Zelnik50.46630.22241.0459413.88350.45930.74250.14930.7739Xclara0.67450.02951.2137008.87460.04750.99180.11140.7814Banana0.35890.12581.02883532.22010.76250.70030.21460.82Ds2c2sc130.57240.2370.58291785.90020.18310.89280.10930.60452sp2glob0.38990.12782.7973158.4080.63740.80030.20880.7146Cure-t1-2000n0.45140.11960.67751365.07740.30540.7870.17210.655Table 14
ARI values, which were obtained from the parameters, are given in Table9 and were proposed by each index.
DatasetObtained ARI values for the each indexSIDIDBCHS_DbwDSIRMSSTDVIASCKDEHalf-kernel1.00001.00000.99800.79010.79010.79011.00001.0000Two spirals0.00791.00000.00790.75240.00760.00760.99901.0000Outlier1.00001.00001.00001.00001.00001.00001.00001.0000Corners1.00001.00001.00001.00000.82610.82611.00001.0000Cluster in cluster1.00001.00000.52850.53600.52740.52741.00001.0000Crescent full moon1.00001.00000.11601.00000.11600.11601.00001.0000Moon0.93791.00000.93790.93790.29330.36970.29331.0000Face0.18830.99491.00000.18831.00001.00000.99491.0000Wave0.26091.00000.17090.26090.25280.21401.00001.0000Fisher iris0.56810.56810.56570.56810.56810.56380.54820.5682Breast cancer0.83490.85220.00110.85220.00110.0011-0.07070.8522Aggregation0.79620.73380.73230.73380.81540.80890.73380.8089Thyroid0.48850.56620.48850.48850.48800.4885-0.02550.4873Zelnik10.93131.00000.32070.88801.00000.96800.97711.0000Zelnik51.00001.00001.00001.00001.00001.00001.00001.0000Xclara0.98610.99040.39360.98800.39360.39360.39360.9904Banana1.00001.00000.83081.00001.00000.82781.00001.0000Ds2c2sc130.31870.31870.31800.31870.76240.31870.31650.42602sp2glob1.00001.00001.00001.00001.00001.00001.00001.0000Cure-t1-2000n0.88500.88500.88500.88500.88500.88500.88500.8850


## 5.4.1. The Selection of Density Distribution Estimation Method

We performed some experimental studies on the datasets to decide which data distribution method should be selected, either parametric or nonparametric. For the parametric method, we selected the Gaussian method and the KDE for the nonparametric method. We carried out experiments with the procedure given in Section5.3, by using the DBSCAN in which the parameters are randomly selected. Besides, the kernel = “Gaussian” and h = 0.05 were the parameters of KDE based on the VIASCKDE Index approach, while the Gaussian was the method of parametric VIASCKDE Index. According to obtained results, while the Gaussian-based method outperformed in 15 datasets, the KDE-based method was the best in 17 datasets, as demonstrated in Table 3. Therefore, we selected the KDE-based method as the weighting function for our approach.Table 3
ARI results obtained with the parametric and nonparametric methods.
DatasetsAdjusted Rand Index (ARI)MethodsGaussian WeightKDE WeightHalf-kernel1.00001.0000Two spirals1.00001.0000Outlier1.00001.0000Corners1.00001.0000Cluster in cluster1.00001.0000Crescent full moon1.00001.0000Moon0.74240.7424Face0.99491.0000Wave1.00001.0000Fisher iris0.74930.7493Breast cancer0.75400.7540Aggregation0.73380.9118Thyroid-0.06190.6783Zelnik11.00000.9488Zelnik51.00001.0000Xclara0.00010.0001Banana1.00001.0000Ds2c2sc130.31870.59042sp2glob1.00000.9880Cure-t1-2000n0.88500.8850


## 5.4.2. The Kernel Selection for KDE

As mentioned in Section4.2, there are various kernels in the literature. The Gaussian, cosine, linear, tophat, and exponential can be given as examples, and they affect the smoothness of distribution. We fulfilled the operation with the procedure provided in Section 5.3 where the parameters of DBSCAN algorithm were selected randomly. We performed the experiments by choosing each kernel in each experimental study. As it can be seen in Table 4, the Gaussian kernel was the best in all of the selected datasets, when the bandwidth was 0.05.Table 4
Obtained results with the different kernels values.
KernelsDatasetsObtained VIASCKDE Values with eachkernelObtained ARI Values with eachkernelFaceAggregationOutliersThyroidCrescent full moonCure-t1-200nFaceAggregationOutliersThyroidCrescent full moonCure-t1-200nGaussian0.70630.63680.67970.49470.66230.65550.60850.82461.00000.50831.00000.8850Cosine0.59670.65640.64990.16990.63400.63430.60850.80891.00000.50831.00000.8850Exponential0.70050.63710.67140.55410.64260.66530.03860.80891.00000.50341.00000.8850Linear0.57360.64270.63060.15940.61690.63710.60850.80891.00000.50831.00000.8850Epanechnikov0.60210.65620.65810.17580.63880.62950.60850.80891.00000.50831.00000.8850Tophat0.64570.61650.64330.23060.66640.62990.60850.03331.00000.50831.00000.8850


## 5.4.3. Bandwidth Selection for the KDE

One of the most important parameters of KDE is bandwidth (h). It possesses a direct effect on the results. When the h is too small, there would be many wiggly structures on the density curve. On the other hand, when the h is too large, the bumps on the curve would be smoothed out as given in Figure 9. To find which bandwidth is the best for our approach, we fulfilled some experimental studies with the procedure given in Section 5.3 by testing it with different bandwidth values on some datasets, which are provided in Table 2. The best bandwidth was found to be 0.05 as it can be seen in Table 5, when the kernel was the Gaussian.Figure 9
Types of the kernel density estimation curves.Table 5
Obtained results with the different bandwidth values.
BandwidthDatasetsObtained VIASCKDE values with eachbandwidthObtained ARI values with eachbandwidthFaceAggregationOutliersThyroidCrescent full moonCure-t1-200nFaceAggregationOutliersThyroidCrescent full moonCure-t1-200n0.010.33770.34440.46500.05560.47800.5264−0.03860.80891.00000.52771.00000.88500.030.66270.65650.65080.34930.66080.64210.60850.80891.00000.50341.00000.88500.050.70630.63880.67970.49470.66230.65550.60850.98981.00000.50341.00000.88500.10.73650.62250.68510.63060.64860.6565−0.03860.80891.00000.50341.00000.88500.30.78570.59470.67730.74020.61430.6189−0.03860.73381.00000.20991.00000.88500.50.75860.56890.54810.75910.59450.6039−0.03860.73381.00000.20991.00000.88501.00.74120.56360.52570.76180.59270.6018−0.03860.73381.00000.20991.00000.88501.50.73620.56290.52360.76180.59230.6016−0.03860.73381.00000.20991.00000.885020.73390.56260.52290.76180.59210.6015−0.03860.73381.00000.20991.00000.88502.50.73280.56250.52260.76180.59200.6015−0.03860.73381.00000.20991.00000.885030.73220.56240.52250.76180.59200.6015−0.03860.73381.00000.20991.00000.88503.50.73170.56240.52230.76180.59190.6015−0.03860.73381.00000.20991.00000.885040.73140.56230.52220.76170.59190.6015−0.03860.73381.00000.20991.00000.88504.50.33770.34440.46500.05560.47800.5264−0.03860.80891.00000.52771.00000.885050.66270.65650.65080.34930.66080.64210.60850.80891.00000.50341.00000.8850


## 5.4.4. The Tests on Both Synthetic and Real Datasets

In this section, experimental works were executed on both synthetic and real datasets. To detect nonspherical clusters in the test process, the DBSCAN, Spectral Clustering, and HDBSCAN were used. The DBSCAN algorithm uses two parameters (MinPts: the clustering threshold value, and ε: the accessibility distance) and Spectral Clustering uses one parameter as input (n_clusters: the number of clusters) if the affinity =  “nearest_neighbors,” while the HDBSCAN Clustering uses two parameters (min_cluster_size: the number of clusters, and min_samples). To test each algorithm with different parameters, we performed the random search method on the procedure given in Section 5.3. The procedure given above with each cluster validity index was used as the leading method to reach better clustering results. As an example is given in Figure 10, each index proposed various results. It means that the cluster validation performance of each one is also different. According to obtained results, our index was the best one. The performance of each index in all datasets is presented in the following tables for each clustering algorithm (Tables 6–14).Figure 10
The clustering results suggested by each validity index when the DBSCAN algorithm was tested in the Aggregation dataset.Table 6
The best parameters for datasets that were detected by the cluster validity indices with the DBSCAN algorithm.
DatasetDBSCAN parametersBest parameters detected by indices for the DBSCAN algorithmSIDIDBCHS_DbwDSIRMSSTDVIASCKDEHalf-kernelε0.080.080.050.080.050.050.080.08MinPts77117151177Two spiralsε0.10.10.050.10.050.10.050.1MinPts1111151115111411Outlierε0.070.070.070.070.050.070.050.07MinPts151515158151415Cornersε0.10.10.10.10.10.10.10.1MinPts1515151515151515Cluster in clusterε0.060.060.060.060.060.060.060.06MinPts1212121212121412Crescent full moonε0.070.070.070.070.050.060.050.07MinPts1414141415121514Moonε0.060.080.060.060.050.050.060.06MinPts71197991515Faceε0.060.10.10.060.060.050.060.1MinPts158561512118Waveε0.090.090.060.090.050.060.050.06MinPts12512129121512Fisher irisε0.140.190.140.140.080.140.060.19MinPts156151551576Breast cancerε0.390.330.390.390.060.060.050.4MinPts858855145Aggregationε0.060.090.060.060.060.060.050.06MinPts137131314121413Thyroidε0.10.10.060.090.070.050.050.1MinPts551256895Zelnik1ε0.080.080.050.10.070.070.080.07MinPts61514755155Zelnik5ε0.060.10.050.10.060.050.050.1MinPts1413121315121413Xclaraε0.050.080.090.050.050.050.080.05MinPts1312151313131213Bananaε0.050.050.050.050.050.050.050.05MinPts99999999Ds2c2sc13ε0.090.090.060.060.050.060.090.05MinPts1010141413141082sp2globε0.10.10.050.070.080.10.060.07MinPts99121469514Cure-t1-2000nε0.10.10.10.10.10.10.10.1MinPts1010101010101010Table 7
Obtained values for each index based on the parameters given in Table6.
DatasetObtained values for the each indexSIDIDBCHS_DbwDSIRMSSTDVIASCKDEHalf-kernel0.20100.09491.8818127.89050.54190.50680.24950.7125Two spirals0.05880.13173.3241152.94470.58480.10690.280.7903Outlier0.56080.42910.40371075.56090.20990.96540.13020.6797Corners0.46140.28720.74362020.10680.49760.63580.11870.6295Cluster in cluster0.22310.2341208.84580.01690.85360.73320.22760.595Crescent full moon0.27840.19231.1646285.14230.32550.65680.24490.6623Moon0.23710.10520.9739244.17220.20810.87880.25250.7508Face0.45690.22171.1099213.02460.37250.76270.24230.6631Wave0.45250.12910.7119366.10950.23440.89350.26960.6495Fisher iris0.56920.12220.5234223.61370.33860.82960.25270.443Breast cancer0.56980.12280.8037900.19880.36060.96170.29930.2944Aggregation0.47630.14320.54611156.75390.20730.94420.18780.6388Thyroid0.4330.05982.762616.64290.53430.74860.15280.3275Zelnik10.20450.09925.697895.1960.25230.89390.21710.6604Zelnik50.49710.22240.8098413.88350.36510.83380.15340.7739Xclara0.66540.06561.18636889.01540.34920.74620.2290.8101Banana0.35890.12581.13223532.22010.76250.43340.21460.8076Ds2c2sc130.57240.2370.58911907.23880.19210.91930.10910.6052sp2glob0.38990.12782.7559158.51870.63740.80030.20890.8819Cure-t1-2000n0.45140.11960.67751365.07740.30540.7870.17210.6555Table 8
The best parameters for the datasets that were detected by the cluster validity indices with the Spectral Clustering algorithm are given in Table7.
DatasetSpectral clustering parametersBest parameters detected by indices for the Spectral Clustering algorithmSIDIDBCHS_DbwDSIRMSSTDVIASCKDEHalf-kerneln_clusters1421515141522Two spiralsn_clusters1521515151522Outliern_clusters244133424Cornersn_clusters1241212151422Cluster in clustern_clusters42415151522Crescent full moonn_clusters52513151426Moonn_clusters1521515151522Facen_clusters1121012151322Waven_clusters721515151522Fisher irisn_clusters222315223Breast cancern_clusters222211141512Aggregationn_clusters4261421522Thyroidn_clusters3233151523Zelnik1n_clusters1221312151333Zelnik5n_clusters82815151524Xclaran_clusters323310323Bananan_clusters92915141522Ds2c2sc13n_clusters3358215252sp2globn_clusters721515151527Cure-t1-2000nn_clusters5241321223Table 9
The best parameters for the datasets that were detected by the cluster validity indices with the HDBSCAN algorithm.
DatasetHDBSCAN ParameterBest parameters detected by the indices for the HDBSCAN algorithmSIDIDBCHS_DbwDSIRMSSTDVIASCKDEHalf-kerneln_clusters_size242422525252424n_samples661025252566Two spiralsn_clusters_size32531722156n_samples21727221912Outliern_clusters_size1616161616161616n_samples1212121212121212Cornersn_clusters_size88882288n_samples88882288Cluster in clustern_clusters_size2020911772020n_samples101022331010Crescent full moonn_clusters_size2020320332020n_samples1212212221212Moonn_clusters_size2262222102106n_samples34332425244Facen_clusters_size211392199139n_samples5198588198Waven_clusters_size16616163462n_samples1332313131935Fisher irisn_clusters_size5514551895n_samples1212161212212512Breast cancern_clusters_size1152522225n_samples3455355335355Aggregationn_clusters_size1712912232122n_samples25141614134144Thyroidn_clusters_size32333328n_samples272242164Zelnik1n_clusters_size11353202143n_samples1611251516171911Zelnik5n_clusters_size2020202020202020n_samples33333333Xclaran_clusters_size92231333313n_samples26393339Bananan_clusters_size2121132121162121n_samples1414161414241414Ds2c2sc13n_clusters_size222216224222416n_samples1919201961924102sp2globn_clusters_size2121212121212121n_samples2222222222222222Cure-t1-2000nn_clusters_size444444425n_samples66666664Table 10
Obtained values for each index based on the parameters are given in Table8.
DatasetObtained values for the each indexSIDIDBCHS_DbwRMSSTDDSIVIASCKDEHalf-kernel0.47480.09490.60661761.61980.22460.91630.24950.7395Two spirals0.31750.13171.0581378.8780.28570.78290.28650.8151Outlier0.61780.42910.40371804.4630.11760.96540.29240.6863Corners0.56720.28720.53154102.58830.18730.94390.2070.6575Cluster in cluster0.45470.23410.9465832.93850.27640.8570.22750.6052Crescent full moon0.49930.19230.57922022.70220.20550.91030.24230.6689Moon0.45430.12850.6781602.09070.21690.90980.26890.7527Face0.49960.23610.54731055.05730.17050.92710.24810.7575Wave0.49570.12910.631681.36810.16390.91240.25410.617Fisher iris0.62950.35810.4877356.2890.21630.89230.14320.4539Breast cancer0.58390.12910.7738993.01580.17960.77950.20310.4341Aggregation0.45410.10910.5891623.96840.14340.9210.29660.6944Thyroid0.55170.09730.85138.12910.38090.6850.13090.4832Zelnik10.50420.09920.663194.5860.28360.86140.21710.6544Zelnik50.59480.26510.53531832.56260.15480.94950.27630.7686Xclara0.69460.0230.420310843.72030.27790.9460.16120.8164Banana0.50870.12580.573414012.55970.18060.93430.21460.82Ds2c2sc130.39390.06390.80821133.55450.14340.90640.28960.61872sp2glob0.61020.14560.69211548.84650.25440.86930.23960.725Cure-t1-2000n0.49940.19210.65813615.53020.15820.90160.28170.6589Table 11
ARI values were obtained from the parameters that are given in Table6 and were proposed by each index.
DatasetObtained ARI values for the each indexSIDIDBCHS_DbwDSIRMSSTDVIASCKDEHalf-kernel1.00001.00000.99401.00000.91530.99401.00001.0000Two spirals1.00001.00000.98041.00000.98041.00000.99901.0000Outlier1.00001.00001.00001.00000.99731.00000.86211.0000Corners1.00001.00001.00001.00001.00001.00001.00001.0000Cluster in cluster1.00001.00001.00001.00001.00001.00000.88791.0000Crescent full moon1.00001.00000.99681.00000.91050.98730.85091.0000Moon0.93790.63220.92560.93790.78740.78740.79490.7949Face0.26450.99490.99610.28920.13040.12260.85210.9961Wave0.35141.00000.14410.35140.19130.14410.05080.0536Fisher iris0.45180.55030.45180.45180.23690.45180.01060.5503Breast cancer0.82400.81890.82400.8240−0.0779−0.0779−0.07800.8283Aggregation0.98980.73380.98980.98980.87700.98660.63300.9898Thyroid0.67150.6715−0.06640.73390.2940−0.1332−0.13960.6715Zelnik10.77081.00000.34090.78520.77240.77241.00000.7781Zelnik50.92141.00000.92781.00000.92160.91260.98391.0000Xclara0.98130.00010.00010.98130.98130.98130.00010.9813Banana1.00001.00001.00001.00001.00001.00001.00001.0000Ds2c2sc130.31870.31870.49110.49110.53250.49110.31870.59042sp2glob1.00001.00000.98500.99400.99851.00000.99700.9940Cure-t1-2000n0.88500.88500.88500.88500.88500.88500.88500.8850Table 12
ARI values, which were obtained from the parameters, were given in Table8 and were proposed by each index.
DatasetObtained ARI values for the each indexSIDIDBCHS_DbwRMSSTDDSIVIASCKDEHalf-kernel0.15141.00000.14220.14210.15150.14211.00001.0000Two spirals0.14011.00000.14350.14010.14010.14010.20471.0000Outlier0.84631.00001.00000.22360.23221.00000.22711.0000Corners0.45811.00000.45810.45810.39170.41990.33300.3330Cluster in cluster0.65841.00000.65840.13650.13680.13651.00001.0000Crescent full moon0.29341.00000.29340.10210.08690.09551.00000.2341Moon0.36290.29730.36290.36290.30920.30920.49160.4916Face0.06460.36620.07470.05800.04430.05380.36620.3662Wave0.29701.00000.13330.13230.13230.13561.00001.0000Fisher iris0.56810.56810.56810.74450.23950.56810.56810.7445Breast cancer0.89330.89330.89330.89330.28750.17790.06690.2534Aggregation0.79750.06460.90660.44530.04860.41560.11490.0646Thyroid0.63070.42040.63070.63070.08300.08300.42040.6307Zelnik10.31700.43520.30040.31700.22250.30071.00001.0000Zelnik50.65670.30960.65670.36380.37900.36380.50031.0000Xclara0.99390.62700.99390.99390.36020.99390.62700.9939Banana0.23941.00000.23940.13690.14630.13691.00001.0000Ds2c2sc130.32670.32670.27660.45310.02440.53440.02440.23942sp2glob0.78520.57090.32260.31950.31850.32260.57090.7852Cure-t1-2000n0.63340.34230.78180.33030.17570.35460.17570.8427Table 13
Obtained values for each index based on the parameters given in Table9.
DatasetObtained values for the each indexSIDIDBCHS_DbwDSIRMSSTDVIASCKDEHalf-kernel0.2010.09491.8878171.89840.55890.46620.24950.7125Two spirals0.40710.13171.1858259.03490.01360.99570.280.8151Outlier0.56080.42910.40371075.56090.20990.96540.12350.6881Corners0.46140.28720.74362020.10680.04370.97910.11870.6268Cluster in cluster0.22310.23414.40832.56240.06420.9470.22750.6052Crescent full moon0.27840.19231.0934285.14230.05270.98290.24230.6623Moon0.23710.07941.1729244.17220.32430.70210.26280.7002Face0.4170.22170.9539204.56650.40310.85570.23390.6654Wave0.37460.12911.1785168.99360.31550.78620.25410.617Fisher iris0.62950.35810.4659353.36740.44880.92960.14780.4722Breast cancer0.43060.11251.1919493.46320.19580.95750.29830.0143Aggregation0.49250.14320.6452778.94480.27010.84810.14970.6108Thyroid0.43590.06831.6838.42350.65190.79130.15320.3833Zelnik10.00080.099213.253512.74330.30220.72870.21710.541Zelnik50.46630.22241.0459413.88350.45930.74250.14930.7739Xclara0.67450.02951.2137008.87460.04750.99180.11140.7814Banana0.35890.12581.02883532.22010.76250.70030.21460.82Ds2c2sc130.57240.2370.58291785.90020.18310.89280.10930.60452sp2glob0.38990.12782.7973158.4080.63740.80030.20880.7146Cure-t1-2000n0.45140.11960.67751365.07740.30540.7870.17210.655Table 14
ARI values, which were obtained from the parameters, are given in Table9 and were proposed by each index.
DatasetObtained ARI values for the each indexSIDIDBCHS_DbwDSIRMSSTDVIASCKDEHalf-kernel1.00001.00000.99800.79010.79010.79011.00001.0000Two spirals0.00791.00000.00790.75240.00760.00760.99901.0000Outlier1.00001.00001.00001.00001.00001.00001.00001.0000Corners1.00001.00001.00001.00000.82610.82611.00001.0000Cluster in cluster1.00001.00000.52850.53600.52740.52741.00001.0000Crescent full moon1.00001.00000.11601.00000.11600.11601.00001.0000Moon0.93791.00000.93790.93790.29330.36970.29331.0000Face0.18830.99491.00000.18831.00001.00000.99491.0000Wave0.26091.00000.17090.26090.25280.21401.00001.0000Fisher iris0.56810.56810.56570.56810.56810.56380.54820.5682Breast cancer0.83490.85220.00110.85220.00110.0011-0.07070.8522Aggregation0.79620.73380.73230.73380.81540.80890.73380.8089Thyroid0.48850.56620.48850.48850.48800.4885-0.02550.4873Zelnik10.93131.00000.32070.88801.00000.96800.97711.0000Zelnik51.00001.00001.00001.00001.00001.00001.00001.0000Xclara0.98610.99040.39360.98800.39360.39360.39360.9904Banana1.00001.00000.83081.00001.00000.82781.00001.0000Ds2c2sc130.31870.31870.31800.31870.76240.31870.31650.42602sp2glob1.00001.00001.00001.00001.00001.00001.00001.0000Cure-t1-2000n0.88500.88500.88500.88500.88500.88500.88500.8850


## 6. Evaluation of the Results and Discussion

In our approach, we used the compactness and separation values of each data to support the arbitrary-shaped clusters. In this case, our approach tended to divide the spherical clusters into small partitions. To cope with this issue, we used a density estimation method to support the compactness of clusters. In the literature, there are two types of density estimation methods, parametric and nonparametric methods. To decide which one is the best for our approach, we carried out some experiments on the datasets by using the DBSCAN as the clustering algorithm. According to the experimental study, the nonparametric method was better than the parametric method, and the results of it can be seen in Table3. After deciding that the nonparametric method was the best for our approach, we selected the kernel density estimation as the nonparametric density estimation method in order to support the multivariate (Table 4).The second point worth discussing is the selection of parameters of the kernel density estimation. The kernel density estimation has two parameters: the first one is the kernel method and the second one is the bandwidth. To find the best parameters of the kernel density estimation, we conducted some experimental studies. We carried out separate experiments for each parameter by using the procedure given in Section5.3 by using the DBSCAN with randomly selected parameters. As it can be seen in Tables 4 and 5, the Gaussian was the best kernel method and the h = 0.05 was the best bandwidth. These parameters were the parameters that were used in experimental studies, which were used to compare our approach with the other indices.One of the advantages of the proposed VIASCKDE Index is that it can realistically evaluate the clustering performance regardless of the cluster shape. To test the success of our index on different cluster types, we used the DBSCAN, Spectral Clustering, and HDBSCAN algorithms with the procedure given in Section5.3. The highest ARI values found as the best value by each index are given in Tables 11, 12 and 14. As it can be seen in the tables, the VIASCKDE Index reaches the highest ARI values on most of the datasets. The VIASCKDE Index reaches the highest ARI values in 47 of the 60 experiments, as given in Table 15. In addition, the ARI value of our index was very high, even if it was not the index that had the highest ARI value. In addition, when our index was compared with the density-based two indices, which were the S_Dbw and DSI, better results were obtained, and they are demonstrated in Table 15.Table 15
The number of highest ARI values that each index reached.
Index# of datasets that each index was the best on the different algorithmsDBSCANSpectral ClusteringHDBSCANTotalSI114924DI13101639DB75618CH134825S_Dbw50914DSI87520RMSSTD531119VIASCKDE (proposed index)15151747The other important advantage of our approach is that it considers the density of each cluster independently. For example, the Aggregation dataset has a nonhomogeneous density as it can be seen in Figure4, and each cluster also may have a nonhomogeneous distribution as it was given in Figure 4(b). So, our approach does not assume all data inside any cluster has homogeneous distribution and also does not weight each data equally. It gives more importance to the data in the denser regions by multiplying those data with a coefficient that is detected by the KDE. Doing that supports the compactness of clusters. In other words, this approach made our index got better results.Since the VIASCKDE Index has a density-based approach, it can also be used to evaluate the performance of the algorithms that are based on a microcluster structure, which is used by the majority of density-based clustering algorithms because such algorithms use the center of each of the microclusters as the actual data in the offline phase. Therefore, the VIASCKDE Index can also be used to evaluate the performance of micro-cluster-based clustering algorithms.


## 7. Conclusion and Future Works

In the present study, we proposed a cluster validation index, which is called the VIASCKDE Index to validate the clusters quality of both the spherical and nonspherical clusters. Our approach draws its strength from considering the distribution of data inside the clusters by using the KDE. Doing that supports the compactness of clusters irrespective of the cluster center, and thus, the shape of the cluster can be in the form of arbitrary cluster. Most of the cluster validity indices in the literature can only do a realistic cluster quality evaluation when the cluster shape is spherical. However, in many instances, the cluster shape is not spherical. Our proposed approach calculates the compactness and separation values only based on the data. This approach makes it possible to evaluate cluster quality irrespective of its shape. Experimental studies revealed that the VIASCKDE Index reached the highest ARI values in most of the datasets. This means that the approach we proposed is the most successful one among the others. It has been planned to carry out studies to decrease the runtime complexity of the proposed index in the future.



---

*Source: 4059302-2022-06-08.xml*