# A New Method to Determine Cluster Number Without Clustering for EveryK Based on Ratio of Variance to Range in K-Means

Authors: Yong Ae Ri; Chol Ryong Kang; Kuk Hyon Kim; Yong Myong Choe; Un Chol Han
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

In many clustering algorithms such asK-means and FCM, the cluster number K needs to be known beforehand. In this paper, we propose a new method to determine the cluster number without clustering for every K in K-means. We introduce a new statistics RVR (ratio of variance to range) and conduct Monte Carlo analysis of its characteristics. Based on the RVR, we propose an algorithm to determine the cluster number K and perform clustering utilizing it. We evaluate its effectiveness by performing a simulation test with different types of datasets; first, with real datasets, whose real number of clusters and components are known and second, with synthetic datasets. We observe a significant improvement in speed and quality of determining the cluster number and therefore clustering. Finally, we hope the proposed algorithm to be used efficiently and widely for clustering of multidimensional data.


---

## Body

## 1. Introduction

Clustering analysis is being applied to many fields of engineering and social science. One of the most important problems in clustering is to determine the number of clusters properly. TheK-means clustering algorithm is widely used for its simplicity. However, application of this algorithm is restricted by the fact that K must be offered at the start. The possibility that the result of clustering reveals the underlying structure of the data depends on the choice of K. Thus, right choice of K is essential, especially in this algorithm.The indices such as DBI [1], SI [2], DU [3], CH [4], Elbow method [5], XB [6], Gap [7], PBM [8], and KL [9] have been studied to infer K and estimate the significance of the clustering result. These indices are all focusing on minimizing the variation within the cluster and maximizing the distance between the clusters as possible. In those approaches, the first thing to be determined beforehand was the range of K. Also, clustering was performed for every possible value of K, and then a value of the cluster number is determined. This is at a disadvantage of high complexity in case of a number of data points or high dimension. This would seem to become more serious when clustering the big datasets and when it comes to the density functions.Many algorithms have been studied, which determine the cluster number more effectively in the specialized datasets using the aforementioned methods. Dinh et al. [10] suggested an algorithm to estimate the optimal number of clusters in categorical data clustering by Silhouette Coefficient. And Moshtaghi et al. [11] developed two online versions (with and without forgetting factors) of the Xie–Beni and Davies–Bouldin internal validity indices.There are some literature on clustering probability distributions. Glick [12] defined K-point separation measurement and proposed the function S∗, which is a K-point separation measurement for the probability densities in L1[μ]. Vo-Van and Pham-Gia [13] suggested the algorithms for the clustering of density functions. Calò et al. [14] proposed a method for clustering of probability density functions based on the heuristic mixture modeling of the data. The method was introduced in the univariate context and then extended to multivariate densities by means of a factorial model performing the dimension reduction.Recently, more effective methods for determining the cluster number and clustering algorithms have been studied and developed. Saha and Mukherjee [15] suggested a clustering algorithm, CNAK, in which the cluster number K could be learned as well as it performs the clustering.In this paper, we propose a new approach for determining the cluster number. Firstly, we suggest a statistical quantity RVR termed as the ratio of variance to the range of cluster, and report the results of the Monte Carlo simulation. Then, we set RVR as a classifying criterion, suggest a method to determine the cluster number in multidimensional data, and design a clustering algorithm. Finally, we demonstrate the validity of the method by comparing the estimating results of the cluster number and compared with the other methods such as DBI, SI, DU, Gap, and CH, which have been widely applied in practice, with several example datasets.The rest of the paper is organized as follows. Section2 reviews the existing indices for determining the cluster number. Section 3 illustrates the principle of the proposed method and its algorithm. Section 4 describes datasets and the performance of our method. Finally, we conclude our work in Section 5.Appendix contains auxiliary theoretical material and the proofs of the Theorems1–3.


## 2. Background and Related Works

### 2.1. Indices for Determining Cluster Number and Validation of Clustering

A variety of cluster validity indices have been proposed to determine the cluster number. For instance, DBI, SI, DU, Gap statistic, XBI, PBM, CHI, Elbow method, Hypersphere density-based method [16], Log_means [17], and so on.The Davies–Bouldin index (DBI) [1], which is the most frequently used, will maximize the between-cluster distance and minimize the within-cluster distance on the other hand. They proposed the rate function which employs the rate of within-cluster dispersion to between-cluster separation. The scatter within the ith cluster can be written as(1)Si=1Ci∑x∈Cix−zi.The distance between the clusterCi and Cj, which is denoted dij, is defined as follows:(2)dij=zi−zj.Here,zi is the ith cluster’s center.Thus, DBI is defined as(3)DB=1K∑i=1KRi,qt,where(4)Ri,qt=maxj,j≠iSi,q+Sj,qdij,t.The minimumDB value corresponds to indicate the proper clustering.The Silhouette index proposed by Rousseeuw [2] was constructed to show how well each object is classified graphically in a given clustering. Silhouette value represents how similar the object is to its own cluster when compared to all other clusters or cluster centroids. Silhouette index is written as(5)SI=s¯=1n∑i=1nsi,where(6)si=bi−aimaxai,bi,ai=1Ci−1∑j∈Cj,i≠jdi,j,bi=mink,i≠k1Ck∑j∈Ckdi,j.Ci is ith cluster, Ci is the number of objects of cluster Ci, and d(i, j) is the Euclidean distance between the objects i and j. The silhouette coefficient varies between −1 and 1. The closer the value is to 1, the better clustering is. Average silhouette method computes the mean of silhouette value for different values of k. The optimal cluster number is the one that maximize the average silhouette over a range of possible values for k. The Silhouette index is useful when data is seeking compact and clearly separated clusters. Also, it depends on the actual partition of the objects, and not on the clustering algorithm that was used to obtain it so that it is used to improve the results of cluster analysis, or to compare the output of different clustering algorithms applied to the same data.Dunn’s index (DU) [3] implies not only the degree of compactness of clusters but also the degree of separation between clusters.(7)DuK=mini=1,…,kminj=i+1,…,kDCi,Cjmaxl=1,…,kdiamCl,where(8)diamCi=maxx,y∈CiDx,y,DCi,Cj=minx∈Ci,y∈CjDx,y.A large value ofDu(K) suggests the presence of compact and well-separated clusters, and the corresponding K provides an estimation of the cluster number.Milligan and Cooper [18] have showed that the index proposed by Calinski and Harabasz [4] outperforms the others through an experimental study on 30 different approaches. The Calinski–Harabasz (CH) index is based on a relationship between a “between cluster scatter matrix” (BCSM) and a “within cluster scatter matrix” (WCSM):(9)CH=traceBCSMtraceWCSM∗N−kk−1.The higher the value is, the “better” the clustering would be.Trace (BCSM) is merely a sum of squared distance between the center of each cluster and the center of dataset, and the weight is given by the size of cluster. trace (WCSM) is the sum of squared distance between the center of each cluster and all the points of that cluster. It is said that the optimal number of the cluster is chosen when the CH index has maximum value. CH index employs the center of cluster to calculate the division like DB. However, the division is measured according to the center of data rather than special clusters. Standardization factor (N − K)/(K − 1) decreases the index value as the K increases. CH is not defined when K is 1. CH has a defect of becoming unstable when the noise in the dataset is present. However, it is more stable than the other indexes for the noise. Due to this, it is better to eliminate the noise to decrease the effect on which the noise has before the clustering.TheGap Statistic proposed by Tibshirani et al. [7] compares the value of within-cluster dispersion with its expectation under the null uniform distribution.(10)Gapq=1B∑b=1BlogWqb−logWq.The optimal number of clusters is chosen via finding the smallestq such that(11)Gapq≥Gapq+1−sq+1,q=1,…,n−2.Elbow method [5] is a visual way to determine the optimal cluster number by figuring out the rate of change formed on the curve according to the cluster number. If the value of one cluster forms an angle (elbow) with the value of the next cluster or the former has the largest decrease, the cluster number at that value is the best one. This method presents the total intracluster scatter or the total Within-Cluster Sum of Squares (WCSS) as a function of the cluster number. The WCSS value will be smaller at greater k which is the cluster number, or vice versa.These indices all have one common point, declaring the presence of compact and well-separated clusters. All these methods keep clustering for differentk over certain ranges (or from 1 to n—Number of data points) and calculate the value of indices at each k. Then you find the optimal cluster number from the result. As a result, all these methods have difficulties when big data or very high-dimensional data are present. Furthermore, it would be worse in clustering distributions.


### 2.2. Clustering Probability Distributions

Glick [12] defined K-point separation measurement, which is a function on the K-fold product of a set in normed vector space. This function is bounded below and above by maximum and total distance between pairs of points in the collection, respectively. Glick’s definition is as follows:A symmetric functionU (a1, a2, …, ak) is called a K-point separation measurement (k ≥ 2) for a subset S in a vector space with norm •. For any elements a1, a2, …, ak ∈ S, the function U satisfies(12)maxi<jai−aj≤Ua1,a2,…,ak≤∑∑i<jai−aj.Note thatU (a1, a2, …, ak) ≥ 0, with equality if and only if a1 = a2 = … = ak; and, when k = 2, the separation U (a1, a2) = a1−a2.Then, Glick showed that ordinaryL1-distance between two integrable functions can be generalized to a nonpairwise separation measurement, S∗, for densities f1, f2, …, fk in L1[µ] and proved that S∗ is a K-point separation measurement.(13)12S∗f1,f2,…,fk=∫maxf1,f2,…,fk−1.Vo-Van and Pham-Gia [13] suggested the algorithms for clustering of density functions. The clustering criterion is a width of a cluster, which is defined by extending L1-distance between two density functions to more than 3 functions.The width of the subset {f1, f2, …, fn}, for n>2, introduced by Tai Vo Van et., is(14)wf1,f2,…,fn≡f1,f2,…,fn1=∫Rmfmaxxdx−1.The right side of (1) is the K-point separation measurement for L1 norm mentioned by Glick. This algorithm minimizes the total range and maximizes the distance between the clusters, simultaneously.


## 2.1. Indices for Determining Cluster Number and Validation of Clustering

A variety of cluster validity indices have been proposed to determine the cluster number. For instance, DBI, SI, DU, Gap statistic, XBI, PBM, CHI, Elbow method, Hypersphere density-based method [16], Log_means [17], and so on.The Davies–Bouldin index (DBI) [1], which is the most frequently used, will maximize the between-cluster distance and minimize the within-cluster distance on the other hand. They proposed the rate function which employs the rate of within-cluster dispersion to between-cluster separation. The scatter within the ith cluster can be written as(1)Si=1Ci∑x∈Cix−zi.The distance between the clusterCi and Cj, which is denoted dij, is defined as follows:(2)dij=zi−zj.Here,zi is the ith cluster’s center.Thus, DBI is defined as(3)DB=1K∑i=1KRi,qt,where(4)Ri,qt=maxj,j≠iSi,q+Sj,qdij,t.The minimumDB value corresponds to indicate the proper clustering.The Silhouette index proposed by Rousseeuw [2] was constructed to show how well each object is classified graphically in a given clustering. Silhouette value represents how similar the object is to its own cluster when compared to all other clusters or cluster centroids. Silhouette index is written as(5)SI=s¯=1n∑i=1nsi,where(6)si=bi−aimaxai,bi,ai=1Ci−1∑j∈Cj,i≠jdi,j,bi=mink,i≠k1Ck∑j∈Ckdi,j.Ci is ith cluster, Ci is the number of objects of cluster Ci, and d(i, j) is the Euclidean distance between the objects i and j. The silhouette coefficient varies between −1 and 1. The closer the value is to 1, the better clustering is. Average silhouette method computes the mean of silhouette value for different values of k. The optimal cluster number is the one that maximize the average silhouette over a range of possible values for k. The Silhouette index is useful when data is seeking compact and clearly separated clusters. Also, it depends on the actual partition of the objects, and not on the clustering algorithm that was used to obtain it so that it is used to improve the results of cluster analysis, or to compare the output of different clustering algorithms applied to the same data.Dunn’s index (DU) [3] implies not only the degree of compactness of clusters but also the degree of separation between clusters.(7)DuK=mini=1,…,kminj=i+1,…,kDCi,Cjmaxl=1,…,kdiamCl,where(8)diamCi=maxx,y∈CiDx,y,DCi,Cj=minx∈Ci,y∈CjDx,y.A large value ofDu(K) suggests the presence of compact and well-separated clusters, and the corresponding K provides an estimation of the cluster number.Milligan and Cooper [18] have showed that the index proposed by Calinski and Harabasz [4] outperforms the others through an experimental study on 30 different approaches. The Calinski–Harabasz (CH) index is based on a relationship between a “between cluster scatter matrix” (BCSM) and a “within cluster scatter matrix” (WCSM):(9)CH=traceBCSMtraceWCSM∗N−kk−1.The higher the value is, the “better” the clustering would be.Trace (BCSM) is merely a sum of squared distance between the center of each cluster and the center of dataset, and the weight is given by the size of cluster. trace (WCSM) is the sum of squared distance between the center of each cluster and all the points of that cluster. It is said that the optimal number of the cluster is chosen when the CH index has maximum value. CH index employs the center of cluster to calculate the division like DB. However, the division is measured according to the center of data rather than special clusters. Standardization factor (N − K)/(K − 1) decreases the index value as the K increases. CH is not defined when K is 1. CH has a defect of becoming unstable when the noise in the dataset is present. However, it is more stable than the other indexes for the noise. Due to this, it is better to eliminate the noise to decrease the effect on which the noise has before the clustering.TheGap Statistic proposed by Tibshirani et al. [7] compares the value of within-cluster dispersion with its expectation under the null uniform distribution.(10)Gapq=1B∑b=1BlogWqb−logWq.The optimal number of clusters is chosen via finding the smallestq such that(11)Gapq≥Gapq+1−sq+1,q=1,…,n−2.Elbow method [5] is a visual way to determine the optimal cluster number by figuring out the rate of change formed on the curve according to the cluster number. If the value of one cluster forms an angle (elbow) with the value of the next cluster or the former has the largest decrease, the cluster number at that value is the best one. This method presents the total intracluster scatter or the total Within-Cluster Sum of Squares (WCSS) as a function of the cluster number. The WCSS value will be smaller at greater k which is the cluster number, or vice versa.These indices all have one common point, declaring the presence of compact and well-separated clusters. All these methods keep clustering for differentk over certain ranges (or from 1 to n—Number of data points) and calculate the value of indices at each k. Then you find the optimal cluster number from the result. As a result, all these methods have difficulties when big data or very high-dimensional data are present. Furthermore, it would be worse in clustering distributions.


## 2.2. Clustering Probability Distributions

Glick [12] defined K-point separation measurement, which is a function on the K-fold product of a set in normed vector space. This function is bounded below and above by maximum and total distance between pairs of points in the collection, respectively. Glick’s definition is as follows:A symmetric functionU (a1, a2, …, ak) is called a K-point separation measurement (k ≥ 2) for a subset S in a vector space with norm •. For any elements a1, a2, …, ak ∈ S, the function U satisfies(12)maxi<jai−aj≤Ua1,a2,…,ak≤∑∑i<jai−aj.Note thatU (a1, a2, …, ak) ≥ 0, with equality if and only if a1 = a2 = … = ak; and, when k = 2, the separation U (a1, a2) = a1−a2.Then, Glick showed that ordinaryL1-distance between two integrable functions can be generalized to a nonpairwise separation measurement, S∗, for densities f1, f2, …, fk in L1[µ] and proved that S∗ is a K-point separation measurement.(13)12S∗f1,f2,…,fk=∫maxf1,f2,…,fk−1.Vo-Van and Pham-Gia [13] suggested the algorithms for clustering of density functions. The clustering criterion is a width of a cluster, which is defined by extending L1-distance between two density functions to more than 3 functions.The width of the subset {f1, f2, …, fn}, for n>2, introduced by Tai Vo Van et., is(14)wf1,f2,…,fn≡f1,f2,…,fn1=∫Rmfmaxxdx−1.The right side of (1) is the K-point separation measurement for L1 norm mentioned by Glick. This algorithm minimizes the total range and maximizes the distance between the clusters, simultaneously.


## 3. Methodology

### 3.1. Definition of RVR

Definition 1.
Suppose that a function U(a1,a2, …,ak) is a K-point separation measurement for a subset S in a vector space with norm •. Then, the function(15)RVRa1,a2,…,ak=1/k∑j=1kaj−a02Ua1,a2,…,ak2.
will be called the variance-range ratio separation measurement (RVR), wherea1, a2, …, ak are k points of S and a0 is a certain point of S.
At this point,a1, a2, …, ak are k objects contained in S (i.e., observations from a p-dimensional population or density functions and so on). The numerator of (2) is the average of squared distance from a1, a2, …, ak to a0. The smaller its value is, the more concentrated a1, a2, …, ak are around a0. On the other hand, the denominator implies how far k points are separated. The following definition is one of RVRs, which can be used easily for clustering of multidimensional data.


### 3.2. DWR and Cluster Number Prediction

#### 3.2.1. Definition of DWR

Definition 2.
Suppose thatS is a subset in a p-dimensional vector space and a1, a2, …, an are n points of S. Then, the function(16)DWRa1,a2,…,an=1/n∑j=1ndaj,a¯2Wa1,a,…,an2.
will be called the dispersion-width ratio separation measurement (DWR), whered(a, b) is an Euclidean distance between a and b, and(17)a¯=1n∑j=1naj,Wa1,a2,…,an=max1≤i<j≤ndai,aj.
The DWR is one of variance-range ratio separation measurements. Ifa1, a2, …, an are n samples from p-dimensional distribution, the numerator is a sample variance while the denominator is the distribution width of samples (diameter of the set of samples). One value of the numerator or denominator can show how compact the n samples are. The smaller the value is, the more compact samples are.
In Section3.2.2, we show the characteristics of DWR evaluated from various populations.


#### 3.2.2. Characteristic Analysis of DWR by Monte Carlo Method

In this section, we have a Monte Carlo analysis of the variation of DWR according ton under the assumption that a1, a2, …, an are n samples from p-dimensional population.Here, some examples with 1 and 2 dimensional samples are given. We observe the variation characteristic of DWR asn increases.(1) Monte Carlo Analysis for Univariate Samples Generated from One Population. The Monte Carlo experiment is conducted with sampled dataset obtained from a univariate population, for example, normal distribution and uniform distribution, to observe variation and asymptotic characteristics of DWR value while n is increasing.The values of DWR statistics withn random samples generated from distribution N (20, 1) and U (0, 1) are presented in Table 1. The variation of DWR observed with increasing n is shown in Figures 1(a) and 1(b) when the population follows a normal distribution or a uniform distribution.Table 1
DWR values with sampled dataset from distributionN (20, 1) and U (0, 1).
Sample size (n)DWRNormal distributionUniform distribution200.06846227711558210.115485429482692400.05960252777388310.08876032060884351000.03703875975894450.09152785836046430.04536321275257970.08393038868602640.03932719253668180.09018770093483894000.02282203690376280.090285327412448210000.02546655614031240.087317019276218820000.02003019887801830.085905789753356230000.02077235499405430.083186384785706250000.01833749693013260.08317327518325090.02008383418371850.0841035512896739100000.01503335161651650.0837606253988841150000.01496366515112010.0830553122746066200000.0167892708467180.0834863486029752300000.01528381029931050.0843417829485036500000.01596211496684880.08295830979263550.01218639058666350.08400893412667920.01394308616481950.08331279489953411000000.01385971740812590.08344882962453950.01109297080374420.08356593935403410.01265115186961660.08326499261600010.01276623354050690.08349933858015912000000.01145988230411480.08322898703169450.01287010607143840.08338346162467660.01334275971658650.08341530985348Figure 1
(a) Graph ofDWR with sampled dataset of size (n) from N (20, 1) n = 1, 2, …, k: k = 20, 100, 500) and (b) graph of DWR with sampled dataset of size n from U(0, 1) (n = 1, 2, …, k: k = 20, 100, 500).
(a)(b)The result of Monte Carlo experiment indicates that the value ofDWR statistics tends to decrease as the sample size increases. Furthermore, if the size of samples gets much larger, the DWR converges to a constant value. Then, the variation characteristic of the mean of DWR under such condition is observed using Monte Carlo simulation. The values of DWR are calculated several times by changing orders of samples for the same data, and then they are averaged.For the same data, by changing orders of samples, we calculated the values of DWR 3, 10, and 100 times and averaged them out. Figure2 shows the graph of average values of DWR for n, the number of samples. The first is graphed for one time of calculation and the rests are ones for averages of DWR when 3, 10, and 100 times repeated, respectively.Figure 2
Graph of DWR with sampled dataset of sizen from N (20, 1). (Average of DWR when 3, 10, 100 times repeated).The result of Monte Carlo experiment indicates thatDWR statistics tends to converge to a certain value as the sample size increases. Especially, we noticed that the more often experiments repeat, the smoother the graph of average-DWR values is, and the more distinct tendency to decrease it has. This means that the mean of DWR is decreasing function for n, the number of samples. And the results of Monte Carlo experiments fit to theoretical ones of Theorems 1–3.(2) Monte Carlo Analysis for Bivariate Samples. A Monte Carlo experiment is conducted with samples generated from 2-dimensional normal distribution to observe the variation and asymptotic characteristics of DWR value while number of samples, n, is increasing on 2-dimensional populations.The variation of DWR value observed from samples generated from 2- dimensional normal distributionN (0, 0, 1, 2, 0.7) in Figure 3. It can clearly be noticed that, in multidimensional population, DWR statistics also has variation and asymptotic characteristic as mentioned above.Figure 3
DWR with sampled dataset of size (n) from 2-dimensional normal distributionN (0, 0, 1, 4, 0.5). (n = 1, 2, …, k: k = 20, 200, 1000).As we can see above, variation of DWR value of samples from one population with increasingn has its own asymptotic property.(3) Monte -Carlo Analysis with Samples from Two or More Populations. In this section, let us conduct a Monte Carlo simulation to observe the variation characteristic of DWR when samples from two or more populations are added.First, let us observe the variation of DWR value when samples from two populations are added. Figure4 shows the variation of DWR when samples from N (15, 1.5) are added to the ones from N (10, 1), and Figure 5 shows the variation of DWR when samples from N (12, 1.5) are added to the ones from N (10, 1). Here, curve for the first population is black, blue for the second one, and red for the added ones.Figure 4
Variation of DWR value when samples fromN (15, 1.5) are added to ones from N (10, 1).Figure 5
Variation ofDWR value when samples from N (12, 1.5) are added to ones from N (10, 1).This is the case of well-separated populations. The result indicates that the graph of DWR has clear boundaries when the samples from the second population are added. In detail, if samples from different distributions are added to samples from the originally presented population, the value of DWR statistics decreases distinctly at the beginning, but if more samples are added, it has a tendency to increase. And then, if more samples are continuously added, it has a tendency to decrease. This characteristic also appears clearly, when sample size is not so big.Subsequently, Figure5 presents the variation of DWR when samples from N(10, 1) are added to N(12, 1.5). The intermix is very big and two populations are not well-separated but it also has distinct boundaries. Of course, it is vaguer than Figure 4. When the cluster number is big enough, it has more distinct boundaries.In some cases of Uniform-Uniform, Normal-Uniform, and 2-dimensional Normal distributions, the results of Monte Carlo experiments, where samples from two populations are added, are figured out and displayed in Figures6–8 to observe variation of DWR value. The variation characteristic of the DWR observed in the case of normal-normal populations appears to be the same in all cases including 2-dimensional populations.Figure 6
Variation ofDWR value when samples from U(0.8, 1.8) are added to the ones from U(0, 1).Figure 7
Variation ofDWR value when samples from U(1, 2) are added to the ones from N (0, 1).Figure 8
Variation of DWR value when samples fromN (5, 5, 2, 8, 0.8) are added to the ones from N (0, 0, 1, 4, 0.5).Figure9 is the result of Monte Carlo experiment in the case that samples from N(2, 1), N(5, 1), and U(−1, 1) are added in order.Figure 9
Variation of DWR value when samples fromN (2, 1), N (5, 1) and U(−1, 1) are added in order.The results of the Monte Carlo simulation above show that if we get samples from two different populations, the graphics of DWR would has clear boundaries when the second one is added to the first one. Actually, this is doubtless from the structure of equation (2) of Theorem 1. Mixing the second sample with the first one seldom affect the numerator at the beginning, since the numerator has the average value. However, the variation of denominator becomes very big even if only one clearly-separated sample from the first sample is added to them. At the moment, the variation of numerator is relatively smaller than denominator. So, the values of DWR decrease dramatically. Furthermore, if we keep mixing with the samples from the second population, the numerator of DWR gets bigger. Therefore, the value of DWR gets bigger for increasing the number of samples. At later, it is decreased alternatively if the number of samples is increased continuously.These boundary characteristics in the graphs of DWR can be used to determine cluster number contained in data.


#### 3.2.3. Some Characteristics of DWR

DWR is 1/4 ifn = 2.Theorem 1.
Assume that the DWR is defined in equation (2), for a subset S in a vector space with norm •. For any vector a1, a2, …, an ∈ S, make sure that 0 ≤ DWR(a1,a2, …, an)≤1.
(Proof is in Appendix.)
Theorem1 shows that the DWR (ξ1, ξ2, …, ξn) evaluated from the sample random variable ξ1, ξ2, …, ξn which is obtained from one population is the statistics whose value is in the bounded set from 0 to 1.
The following theorems are confirming the asymptotic property of DWR in several 1-dimensional distributions.Theorem 2.
Letξ1, ξ2, …, ξn, … be independent and have the uniform distribution on [a, b].
Let(18)DWRa1,a2,…,an=1/n∑j=1naj−a¯2max1≤i<j≤nai−aj2.
Then,(19)∀ε>0,limn⟶∞PDWRξ1,ξ2,…,ξn−112<ε=1.
(Proof is in Appendix.)
Theorem2 shows that the value of DWR statistics converges in probability to 1/12 when the sample from one uniformly distributed population on a finite interval gets larger in size.Theorem 3.
Letξ1, ξ2, …, ξn, … be independent and follow N(m, σ2).
Let(20)DWRa1,a2,…,an=1/n∑j=1naj−a¯2max1≤i<j≤nai−aj2.
Then,(21)∀ε>0,limn⟶∞PDWRξ1,ξ2,…,ξn<ε=1.
(Proof is in Appendix.)
Theorem3 shows that the value of DWR statistics converges in probability to 0 when the sample from a normal population gets larger in size.
In general, the value of the DWR statistics converges in probability to the division of variation of the population by the square of the sample distribution range.


#### 3.2.4. Cluster Number Prediction

We have discussed above about the variation characteristics of DWR as sample size gets larger in the case of either one or several populations. The results of the Monte Carlo simulation revealed the clear boundary character when samples chosen from two different populations are mixed. To make a clarification, the DWR has only decreasing tendency when on only one population and both dramatically decreasing tendency at first and increasing tendency afterwards with mixed samples from different populations as the sample size increases. If more samples are further added, we can clearly observe that value of the DWR statistics decreases again. You will come across with the variation characteristic of DWR when the samples from various populations are mixed. This can be readily seen when it comes to the samples small in size.From now on, it can be utilized to estimate the cluster number in a specific data. Utilizing DWR, we estimate the cluster number with 7 practical data and compare with other approaches (DBI, DU, SI, Gap, and CH).How to obtain the number of clusters and conduct the clustering by using DWR is described in Algorithm 1. Here, let us setK0, which is the initial value of number of the clusters, being about three times of the predicted number. Above all, the objects in the dataset Y are clustered into K0 clusters by utilizing the K-means algorithm which is canonically loaded on Applications program. Then, Algorithm 2 performs its function of ordering the clusters. After that, we graph out the DWR and determine the boundary point from it to decide the number of clusters K^. Subsecondly, the dataset Y is partitioned into K^ clusters through the K-means algorithm.Algorithm 1: Clustering with DWR.
Input:Y= dataset, K0= initial number of clustersOutput:K^= optimal number of clusters, C^= optimal set of clusters(1)
C← set of clusters from typical clustering algorithm with K0 as the cluster number(2)
I← order of clusters with Algorithm2C(3)
G← DWR graph from Algorithm3I(4)
K^← optimal number of clusters from DWR graph G(5)
C^← optimal set of clusters from typical clustering algorithm with K^ as the cluster numberAlgorithm 2: Ordering clusters.
Input:C= set of clustersOutput:I= order of clusters(1)
n← number of clusters, f:C⟶C,g:C⟶C(2)
fx←∅,gx←∅,for allx∈C(3)
S← set of all possible cluster pairs of C(4)
fort=1tonn−1/2do(5)
r,c← the closest cluster pair in S which is not connected with f(6)
iffr=∅andgc=∅do(7)
fr←c,gc←r(8)
end if(9)
S←S/r,c(10)
end for(11)
x← cluster in C with gx=∅(12)
I←x(13)
fort=1ton−1do(14)
x←fx,I←I∪x(15)
end forAlgorithm 2 describes the process of ordering clusters to picture the graph of DWR.Algorithm 3 describes the process of plotting DWR. We picture the graph of DWR while we are adding the samples in the order we have determined in Cluster Number Determination and Clustering Algorithm.Algorithm 3: Drawing DWR graph.
Input:I= order of clustersOutput:G= DWR graph from I(1)
Y=∅(2)
forXinIdo(3)
Y←Y∪X(4)
end for(5)
n←Y(6)
fori=1tondo(7)
yi←DWRvalue of setY1,2,…,i(8)
end for(9)
G←ploty1,y2,…,yn


## 3.1. Definition of RVR

Definition 1.
Suppose that a function U(a1,a2, …,ak) is a K-point separation measurement for a subset S in a vector space with norm •. Then, the function(15)RVRa1,a2,…,ak=1/k∑j=1kaj−a02Ua1,a2,…,ak2.
will be called the variance-range ratio separation measurement (RVR), wherea1, a2, …, ak are k points of S and a0 is a certain point of S.
At this point,a1, a2, …, ak are k objects contained in S (i.e., observations from a p-dimensional population or density functions and so on). The numerator of (2) is the average of squared distance from a1, a2, …, ak to a0. The smaller its value is, the more concentrated a1, a2, …, ak are around a0. On the other hand, the denominator implies how far k points are separated. The following definition is one of RVRs, which can be used easily for clustering of multidimensional data.


## 3.2. DWR and Cluster Number Prediction

### 3.2.1. Definition of DWR

Definition 2.
Suppose thatS is a subset in a p-dimensional vector space and a1, a2, …, an are n points of S. Then, the function(16)DWRa1,a2,…,an=1/n∑j=1ndaj,a¯2Wa1,a,…,an2.
will be called the dispersion-width ratio separation measurement (DWR), whered(a, b) is an Euclidean distance between a and b, and(17)a¯=1n∑j=1naj,Wa1,a2,…,an=max1≤i<j≤ndai,aj.
The DWR is one of variance-range ratio separation measurements. Ifa1, a2, …, an are n samples from p-dimensional distribution, the numerator is a sample variance while the denominator is the distribution width of samples (diameter of the set of samples). One value of the numerator or denominator can show how compact the n samples are. The smaller the value is, the more compact samples are.
In Section3.2.2, we show the characteristics of DWR evaluated from various populations.


### 3.2.2. Characteristic Analysis of DWR by Monte Carlo Method

In this section, we have a Monte Carlo analysis of the variation of DWR according ton under the assumption that a1, a2, …, an are n samples from p-dimensional population.Here, some examples with 1 and 2 dimensional samples are given. We observe the variation characteristic of DWR asn increases.(1) Monte Carlo Analysis for Univariate Samples Generated from One Population. The Monte Carlo experiment is conducted with sampled dataset obtained from a univariate population, for example, normal distribution and uniform distribution, to observe variation and asymptotic characteristics of DWR value while n is increasing.The values of DWR statistics withn random samples generated from distribution N (20, 1) and U (0, 1) are presented in Table 1. The variation of DWR observed with increasing n is shown in Figures 1(a) and 1(b) when the population follows a normal distribution or a uniform distribution.Table 1
DWR values with sampled dataset from distributionN (20, 1) and U (0, 1).
Sample size (n)DWRNormal distributionUniform distribution200.06846227711558210.115485429482692400.05960252777388310.08876032060884351000.03703875975894450.09152785836046430.04536321275257970.08393038868602640.03932719253668180.09018770093483894000.02282203690376280.090285327412448210000.02546655614031240.087317019276218820000.02003019887801830.085905789753356230000.02077235499405430.083186384785706250000.01833749693013260.08317327518325090.02008383418371850.0841035512896739100000.01503335161651650.0837606253988841150000.01496366515112010.0830553122746066200000.0167892708467180.0834863486029752300000.01528381029931050.0843417829485036500000.01596211496684880.08295830979263550.01218639058666350.08400893412667920.01394308616481950.08331279489953411000000.01385971740812590.08344882962453950.01109297080374420.08356593935403410.01265115186961660.08326499261600010.01276623354050690.08349933858015912000000.01145988230411480.08322898703169450.01287010607143840.08338346162467660.01334275971658650.08341530985348Figure 1
(a) Graph ofDWR with sampled dataset of size (n) from N (20, 1) n = 1, 2, …, k: k = 20, 100, 500) and (b) graph of DWR with sampled dataset of size n from U(0, 1) (n = 1, 2, …, k: k = 20, 100, 500).
(a)(b)The result of Monte Carlo experiment indicates that the value ofDWR statistics tends to decrease as the sample size increases. Furthermore, if the size of samples gets much larger, the DWR converges to a constant value. Then, the variation characteristic of the mean of DWR under such condition is observed using Monte Carlo simulation. The values of DWR are calculated several times by changing orders of samples for the same data, and then they are averaged.For the same data, by changing orders of samples, we calculated the values of DWR 3, 10, and 100 times and averaged them out. Figure2 shows the graph of average values of DWR for n, the number of samples. The first is graphed for one time of calculation and the rests are ones for averages of DWR when 3, 10, and 100 times repeated, respectively.Figure 2
Graph of DWR with sampled dataset of sizen from N (20, 1). (Average of DWR when 3, 10, 100 times repeated).The result of Monte Carlo experiment indicates thatDWR statistics tends to converge to a certain value as the sample size increases. Especially, we noticed that the more often experiments repeat, the smoother the graph of average-DWR values is, and the more distinct tendency to decrease it has. This means that the mean of DWR is decreasing function for n, the number of samples. And the results of Monte Carlo experiments fit to theoretical ones of Theorems 1–3.(2) Monte Carlo Analysis for Bivariate Samples. A Monte Carlo experiment is conducted with samples generated from 2-dimensional normal distribution to observe the variation and asymptotic characteristics of DWR value while number of samples, n, is increasing on 2-dimensional populations.The variation of DWR value observed from samples generated from 2- dimensional normal distributionN (0, 0, 1, 2, 0.7) in Figure 3. It can clearly be noticed that, in multidimensional population, DWR statistics also has variation and asymptotic characteristic as mentioned above.Figure 3
DWR with sampled dataset of size (n) from 2-dimensional normal distributionN (0, 0, 1, 4, 0.5). (n = 1, 2, …, k: k = 20, 200, 1000).As we can see above, variation of DWR value of samples from one population with increasingn has its own asymptotic property.(3) Monte -Carlo Analysis with Samples from Two or More Populations. In this section, let us conduct a Monte Carlo simulation to observe the variation characteristic of DWR when samples from two or more populations are added.First, let us observe the variation of DWR value when samples from two populations are added. Figure4 shows the variation of DWR when samples from N (15, 1.5) are added to the ones from N (10, 1), and Figure 5 shows the variation of DWR when samples from N (12, 1.5) are added to the ones from N (10, 1). Here, curve for the first population is black, blue for the second one, and red for the added ones.Figure 4
Variation of DWR value when samples fromN (15, 1.5) are added to ones from N (10, 1).Figure 5
Variation ofDWR value when samples from N (12, 1.5) are added to ones from N (10, 1).This is the case of well-separated populations. The result indicates that the graph of DWR has clear boundaries when the samples from the second population are added. In detail, if samples from different distributions are added to samples from the originally presented population, the value of DWR statistics decreases distinctly at the beginning, but if more samples are added, it has a tendency to increase. And then, if more samples are continuously added, it has a tendency to decrease. This characteristic also appears clearly, when sample size is not so big.Subsequently, Figure5 presents the variation of DWR when samples from N(10, 1) are added to N(12, 1.5). The intermix is very big and two populations are not well-separated but it also has distinct boundaries. Of course, it is vaguer than Figure 4. When the cluster number is big enough, it has more distinct boundaries.In some cases of Uniform-Uniform, Normal-Uniform, and 2-dimensional Normal distributions, the results of Monte Carlo experiments, where samples from two populations are added, are figured out and displayed in Figures6–8 to observe variation of DWR value. The variation characteristic of the DWR observed in the case of normal-normal populations appears to be the same in all cases including 2-dimensional populations.Figure 6
Variation ofDWR value when samples from U(0.8, 1.8) are added to the ones from U(0, 1).Figure 7
Variation ofDWR value when samples from U(1, 2) are added to the ones from N (0, 1).Figure 8
Variation of DWR value when samples fromN (5, 5, 2, 8, 0.8) are added to the ones from N (0, 0, 1, 4, 0.5).Figure9 is the result of Monte Carlo experiment in the case that samples from N(2, 1), N(5, 1), and U(−1, 1) are added in order.Figure 9
Variation of DWR value when samples fromN (2, 1), N (5, 1) and U(−1, 1) are added in order.The results of the Monte Carlo simulation above show that if we get samples from two different populations, the graphics of DWR would has clear boundaries when the second one is added to the first one. Actually, this is doubtless from the structure of equation (2) of Theorem 1. Mixing the second sample with the first one seldom affect the numerator at the beginning, since the numerator has the average value. However, the variation of denominator becomes very big even if only one clearly-separated sample from the first sample is added to them. At the moment, the variation of numerator is relatively smaller than denominator. So, the values of DWR decrease dramatically. Furthermore, if we keep mixing with the samples from the second population, the numerator of DWR gets bigger. Therefore, the value of DWR gets bigger for increasing the number of samples. At later, it is decreased alternatively if the number of samples is increased continuously.These boundary characteristics in the graphs of DWR can be used to determine cluster number contained in data.


### 3.2.3. Some Characteristics of DWR

DWR is 1/4 ifn = 2.Theorem 1.
Assume that the DWR is defined in equation (2), for a subset S in a vector space with norm •. For any vector a1, a2, …, an ∈ S, make sure that 0 ≤ DWR(a1,a2, …, an)≤1.
(Proof is in Appendix.)
Theorem1 shows that the DWR (ξ1, ξ2, …, ξn) evaluated from the sample random variable ξ1, ξ2, …, ξn which is obtained from one population is the statistics whose value is in the bounded set from 0 to 1.
The following theorems are confirming the asymptotic property of DWR in several 1-dimensional distributions.Theorem 2.
Letξ1, ξ2, …, ξn, … be independent and have the uniform distribution on [a, b].
Let(18)DWRa1,a2,…,an=1/n∑j=1naj−a¯2max1≤i<j≤nai−aj2.
Then,(19)∀ε>0,limn⟶∞PDWRξ1,ξ2,…,ξn−112<ε=1.
(Proof is in Appendix.)
Theorem2 shows that the value of DWR statistics converges in probability to 1/12 when the sample from one uniformly distributed population on a finite interval gets larger in size.Theorem 3.
Letξ1, ξ2, …, ξn, … be independent and follow N(m, σ2).
Let(20)DWRa1,a2,…,an=1/n∑j=1naj−a¯2max1≤i<j≤nai−aj2.
Then,(21)∀ε>0,limn⟶∞PDWRξ1,ξ2,…,ξn<ε=1.
(Proof is in Appendix.)
Theorem3 shows that the value of DWR statistics converges in probability to 0 when the sample from a normal population gets larger in size.
In general, the value of the DWR statistics converges in probability to the division of variation of the population by the square of the sample distribution range.


### 3.2.4. Cluster Number Prediction

We have discussed above about the variation characteristics of DWR as sample size gets larger in the case of either one or several populations. The results of the Monte Carlo simulation revealed the clear boundary character when samples chosen from two different populations are mixed. To make a clarification, the DWR has only decreasing tendency when on only one population and both dramatically decreasing tendency at first and increasing tendency afterwards with mixed samples from different populations as the sample size increases. If more samples are further added, we can clearly observe that value of the DWR statistics decreases again. You will come across with the variation characteristic of DWR when the samples from various populations are mixed. This can be readily seen when it comes to the samples small in size.From now on, it can be utilized to estimate the cluster number in a specific data. Utilizing DWR, we estimate the cluster number with 7 practical data and compare with other approaches (DBI, DU, SI, Gap, and CH).How to obtain the number of clusters and conduct the clustering by using DWR is described in Algorithm 1. Here, let us setK0, which is the initial value of number of the clusters, being about three times of the predicted number. Above all, the objects in the dataset Y are clustered into K0 clusters by utilizing the K-means algorithm which is canonically loaded on Applications program. Then, Algorithm 2 performs its function of ordering the clusters. After that, we graph out the DWR and determine the boundary point from it to decide the number of clusters K^. Subsecondly, the dataset Y is partitioned into K^ clusters through the K-means algorithm.Algorithm 1: Clustering with DWR.
Input:Y= dataset, K0= initial number of clustersOutput:K^= optimal number of clusters, C^= optimal set of clusters(1)
C← set of clusters from typical clustering algorithm with K0 as the cluster number(2)
I← order of clusters with Algorithm2C(3)
G← DWR graph from Algorithm3I(4)
K^← optimal number of clusters from DWR graph G(5)
C^← optimal set of clusters from typical clustering algorithm with K^ as the cluster numberAlgorithm 2: Ordering clusters.
Input:C= set of clustersOutput:I= order of clusters(1)
n← number of clusters, f:C⟶C,g:C⟶C(2)
fx←∅,gx←∅,for allx∈C(3)
S← set of all possible cluster pairs of C(4)
fort=1tonn−1/2do(5)
r,c← the closest cluster pair in S which is not connected with f(6)
iffr=∅andgc=∅do(7)
fr←c,gc←r(8)
end if(9)
S←S/r,c(10)
end for(11)
x← cluster in C with gx=∅(12)
I←x(13)
fort=1ton−1do(14)
x←fx,I←I∪x(15)
end forAlgorithm 2 describes the process of ordering clusters to picture the graph of DWR.Algorithm 3 describes the process of plotting DWR. We picture the graph of DWR while we are adding the samples in the order we have determined in Cluster Number Determination and Clustering Algorithm.Algorithm 3: Drawing DWR graph.
Input:I= order of clustersOutput:G= DWR graph from I(1)
Y=∅(2)
forXinIdo(3)
Y←Y∪X(4)
end for(5)
n←Y(6)
fori=1tondo(7)
yi←DWRvalue of setY1,2,…,i(8)
end for(9)
G←ploty1,y2,…,yn


## 3.2.1. Definition of DWR

Definition 2.
Suppose thatS is a subset in a p-dimensional vector space and a1, a2, …, an are n points of S. Then, the function(16)DWRa1,a2,…,an=1/n∑j=1ndaj,a¯2Wa1,a,…,an2.
will be called the dispersion-width ratio separation measurement (DWR), whered(a, b) is an Euclidean distance between a and b, and(17)a¯=1n∑j=1naj,Wa1,a2,…,an=max1≤i<j≤ndai,aj.
The DWR is one of variance-range ratio separation measurements. Ifa1, a2, …, an are n samples from p-dimensional distribution, the numerator is a sample variance while the denominator is the distribution width of samples (diameter of the set of samples). One value of the numerator or denominator can show how compact the n samples are. The smaller the value is, the more compact samples are.
In Section3.2.2, we show the characteristics of DWR evaluated from various populations.


## 3.2.2. Characteristic Analysis of DWR by Monte Carlo Method

In this section, we have a Monte Carlo analysis of the variation of DWR according ton under the assumption that a1, a2, …, an are n samples from p-dimensional population.Here, some examples with 1 and 2 dimensional samples are given. We observe the variation characteristic of DWR asn increases.(1) Monte Carlo Analysis for Univariate Samples Generated from One Population. The Monte Carlo experiment is conducted with sampled dataset obtained from a univariate population, for example, normal distribution and uniform distribution, to observe variation and asymptotic characteristics of DWR value while n is increasing.The values of DWR statistics withn random samples generated from distribution N (20, 1) and U (0, 1) are presented in Table 1. The variation of DWR observed with increasing n is shown in Figures 1(a) and 1(b) when the population follows a normal distribution or a uniform distribution.Table 1
DWR values with sampled dataset from distributionN (20, 1) and U (0, 1).
Sample size (n)DWRNormal distributionUniform distribution200.06846227711558210.115485429482692400.05960252777388310.08876032060884351000.03703875975894450.09152785836046430.04536321275257970.08393038868602640.03932719253668180.09018770093483894000.02282203690376280.090285327412448210000.02546655614031240.087317019276218820000.02003019887801830.085905789753356230000.02077235499405430.083186384785706250000.01833749693013260.08317327518325090.02008383418371850.0841035512896739100000.01503335161651650.0837606253988841150000.01496366515112010.0830553122746066200000.0167892708467180.0834863486029752300000.01528381029931050.0843417829485036500000.01596211496684880.08295830979263550.01218639058666350.08400893412667920.01394308616481950.08331279489953411000000.01385971740812590.08344882962453950.01109297080374420.08356593935403410.01265115186961660.08326499261600010.01276623354050690.08349933858015912000000.01145988230411480.08322898703169450.01287010607143840.08338346162467660.01334275971658650.08341530985348Figure 1
(a) Graph ofDWR with sampled dataset of size (n) from N (20, 1) n = 1, 2, …, k: k = 20, 100, 500) and (b) graph of DWR with sampled dataset of size n from U(0, 1) (n = 1, 2, …, k: k = 20, 100, 500).
(a)(b)The result of Monte Carlo experiment indicates that the value ofDWR statistics tends to decrease as the sample size increases. Furthermore, if the size of samples gets much larger, the DWR converges to a constant value. Then, the variation characteristic of the mean of DWR under such condition is observed using Monte Carlo simulation. The values of DWR are calculated several times by changing orders of samples for the same data, and then they are averaged.For the same data, by changing orders of samples, we calculated the values of DWR 3, 10, and 100 times and averaged them out. Figure2 shows the graph of average values of DWR for n, the number of samples. The first is graphed for one time of calculation and the rests are ones for averages of DWR when 3, 10, and 100 times repeated, respectively.Figure 2
Graph of DWR with sampled dataset of sizen from N (20, 1). (Average of DWR when 3, 10, 100 times repeated).The result of Monte Carlo experiment indicates thatDWR statistics tends to converge to a certain value as the sample size increases. Especially, we noticed that the more often experiments repeat, the smoother the graph of average-DWR values is, and the more distinct tendency to decrease it has. This means that the mean of DWR is decreasing function for n, the number of samples. And the results of Monte Carlo experiments fit to theoretical ones of Theorems 1–3.(2) Monte Carlo Analysis for Bivariate Samples. A Monte Carlo experiment is conducted with samples generated from 2-dimensional normal distribution to observe the variation and asymptotic characteristics of DWR value while number of samples, n, is increasing on 2-dimensional populations.The variation of DWR value observed from samples generated from 2- dimensional normal distributionN (0, 0, 1, 2, 0.7) in Figure 3. It can clearly be noticed that, in multidimensional population, DWR statistics also has variation and asymptotic characteristic as mentioned above.Figure 3
DWR with sampled dataset of size (n) from 2-dimensional normal distributionN (0, 0, 1, 4, 0.5). (n = 1, 2, …, k: k = 20, 200, 1000).As we can see above, variation of DWR value of samples from one population with increasingn has its own asymptotic property.(3) Monte -Carlo Analysis with Samples from Two or More Populations. In this section, let us conduct a Monte Carlo simulation to observe the variation characteristic of DWR when samples from two or more populations are added.First, let us observe the variation of DWR value when samples from two populations are added. Figure4 shows the variation of DWR when samples from N (15, 1.5) are added to the ones from N (10, 1), and Figure 5 shows the variation of DWR when samples from N (12, 1.5) are added to the ones from N (10, 1). Here, curve for the first population is black, blue for the second one, and red for the added ones.Figure 4
Variation of DWR value when samples fromN (15, 1.5) are added to ones from N (10, 1).Figure 5
Variation ofDWR value when samples from N (12, 1.5) are added to ones from N (10, 1).This is the case of well-separated populations. The result indicates that the graph of DWR has clear boundaries when the samples from the second population are added. In detail, if samples from different distributions are added to samples from the originally presented population, the value of DWR statistics decreases distinctly at the beginning, but if more samples are added, it has a tendency to increase. And then, if more samples are continuously added, it has a tendency to decrease. This characteristic also appears clearly, when sample size is not so big.Subsequently, Figure5 presents the variation of DWR when samples from N(10, 1) are added to N(12, 1.5). The intermix is very big and two populations are not well-separated but it also has distinct boundaries. Of course, it is vaguer than Figure 4. When the cluster number is big enough, it has more distinct boundaries.In some cases of Uniform-Uniform, Normal-Uniform, and 2-dimensional Normal distributions, the results of Monte Carlo experiments, where samples from two populations are added, are figured out and displayed in Figures6–8 to observe variation of DWR value. The variation characteristic of the DWR observed in the case of normal-normal populations appears to be the same in all cases including 2-dimensional populations.Figure 6
Variation ofDWR value when samples from U(0.8, 1.8) are added to the ones from U(0, 1).Figure 7
Variation ofDWR value when samples from U(1, 2) are added to the ones from N (0, 1).Figure 8
Variation of DWR value when samples fromN (5, 5, 2, 8, 0.8) are added to the ones from N (0, 0, 1, 4, 0.5).Figure9 is the result of Monte Carlo experiment in the case that samples from N(2, 1), N(5, 1), and U(−1, 1) are added in order.Figure 9
Variation of DWR value when samples fromN (2, 1), N (5, 1) and U(−1, 1) are added in order.The results of the Monte Carlo simulation above show that if we get samples from two different populations, the graphics of DWR would has clear boundaries when the second one is added to the first one. Actually, this is doubtless from the structure of equation (2) of Theorem 1. Mixing the second sample with the first one seldom affect the numerator at the beginning, since the numerator has the average value. However, the variation of denominator becomes very big even if only one clearly-separated sample from the first sample is added to them. At the moment, the variation of numerator is relatively smaller than denominator. So, the values of DWR decrease dramatically. Furthermore, if we keep mixing with the samples from the second population, the numerator of DWR gets bigger. Therefore, the value of DWR gets bigger for increasing the number of samples. At later, it is decreased alternatively if the number of samples is increased continuously.These boundary characteristics in the graphs of DWR can be used to determine cluster number contained in data.


## 3.2.3. Some Characteristics of DWR

DWR is 1/4 ifn = 2.Theorem 1.
Assume that the DWR is defined in equation (2), for a subset S in a vector space with norm •. For any vector a1, a2, …, an ∈ S, make sure that 0 ≤ DWR(a1,a2, …, an)≤1.
(Proof is in Appendix.)
Theorem1 shows that the DWR (ξ1, ξ2, …, ξn) evaluated from the sample random variable ξ1, ξ2, …, ξn which is obtained from one population is the statistics whose value is in the bounded set from 0 to 1.
The following theorems are confirming the asymptotic property of DWR in several 1-dimensional distributions.Theorem 2.
Letξ1, ξ2, …, ξn, … be independent and have the uniform distribution on [a, b].
Let(18)DWRa1,a2,…,an=1/n∑j=1naj−a¯2max1≤i<j≤nai−aj2.
Then,(19)∀ε>0,limn⟶∞PDWRξ1,ξ2,…,ξn−112<ε=1.
(Proof is in Appendix.)
Theorem2 shows that the value of DWR statistics converges in probability to 1/12 when the sample from one uniformly distributed population on a finite interval gets larger in size.Theorem 3.
Letξ1, ξ2, …, ξn, … be independent and follow N(m, σ2).
Let(20)DWRa1,a2,…,an=1/n∑j=1naj−a¯2max1≤i<j≤nai−aj2.
Then,(21)∀ε>0,limn⟶∞PDWRξ1,ξ2,…,ξn<ε=1.
(Proof is in Appendix.)
Theorem3 shows that the value of DWR statistics converges in probability to 0 when the sample from a normal population gets larger in size.
In general, the value of the DWR statistics converges in probability to the division of variation of the population by the square of the sample distribution range.


## 3.2.4. Cluster Number Prediction

We have discussed above about the variation characteristics of DWR as sample size gets larger in the case of either one or several populations. The results of the Monte Carlo simulation revealed the clear boundary character when samples chosen from two different populations are mixed. To make a clarification, the DWR has only decreasing tendency when on only one population and both dramatically decreasing tendency at first and increasing tendency afterwards with mixed samples from different populations as the sample size increases. If more samples are further added, we can clearly observe that value of the DWR statistics decreases again. You will come across with the variation characteristic of DWR when the samples from various populations are mixed. This can be readily seen when it comes to the samples small in size.From now on, it can be utilized to estimate the cluster number in a specific data. Utilizing DWR, we estimate the cluster number with 7 practical data and compare with other approaches (DBI, DU, SI, Gap, and CH).How to obtain the number of clusters and conduct the clustering by using DWR is described in Algorithm 1. Here, let us setK0, which is the initial value of number of the clusters, being about three times of the predicted number. Above all, the objects in the dataset Y are clustered into K0 clusters by utilizing the K-means algorithm which is canonically loaded on Applications program. Then, Algorithm 2 performs its function of ordering the clusters. After that, we graph out the DWR and determine the boundary point from it to decide the number of clusters K^. Subsecondly, the dataset Y is partitioned into K^ clusters through the K-means algorithm.Algorithm 1: Clustering with DWR.
Input:Y= dataset, K0= initial number of clustersOutput:K^= optimal number of clusters, C^= optimal set of clusters(1)
C← set of clusters from typical clustering algorithm with K0 as the cluster number(2)
I← order of clusters with Algorithm2C(3)
G← DWR graph from Algorithm3I(4)
K^← optimal number of clusters from DWR graph G(5)
C^← optimal set of clusters from typical clustering algorithm with K^ as the cluster numberAlgorithm 2: Ordering clusters.
Input:C= set of clustersOutput:I= order of clusters(1)
n← number of clusters, f:C⟶C,g:C⟶C(2)
fx←∅,gx←∅,for allx∈C(3)
S← set of all possible cluster pairs of C(4)
fort=1tonn−1/2do(5)
r,c← the closest cluster pair in S which is not connected with f(6)
iffr=∅andgc=∅do(7)
fr←c,gc←r(8)
end if(9)
S←S/r,c(10)
end for(11)
x← cluster in C with gx=∅(12)
I←x(13)
fort=1ton−1do(14)
x←fx,I←I∪x(15)
end forAlgorithm 2 describes the process of ordering clusters to picture the graph of DWR.Algorithm 3 describes the process of plotting DWR. We picture the graph of DWR while we are adding the samples in the order we have determined in Cluster Number Determination and Clustering Algorithm.Algorithm 3: Drawing DWR graph.
Input:I= order of clustersOutput:G= DWR graph from I(1)
Y=∅(2)
forXinIdo(3)
Y←Y∪X(4)
end for(5)
n←Y(6)
fori=1tondo(7)
yi←DWRvalue of setY1,2,…,i(8)
end for(9)
G←ploty1,y2,…,yn


## 4. Experimental Results and Discussion

### 4.1. Simulation

#### 4.1.1. Datasets

(1) Iris Dataset. The first dataset is Iris dataset that widely used for evaluating clustering method. It has 150 samples data with 3 classes: setosa, versicolor, and virginica. Each class has 50 samples having four features (sepal length, sepal width, petal length, and the petal width). This is shown in Figure 10. Note that two clusters of Iris dataset are overlapped and one cluster is separated from those clusters. For simulations, we used the Iris data in the datasets package (version 4.0.3) of R (R Development Core Team 2020).Figure 10
Iris dataset (the real number of clusters is three).(2) Synthetic Dataset. This is synthesized 2-d dataset with 250 data points consisting two clusters. This data is used in the synth.tr data of the MASS package (version 7.3–53) of R (R Development Core Team 2020).


#### 4.1.2. Experimental Results

(1) Results for Some Datasets. We calculated values of DBI, DU, SI, Gap, and CH for different values of K and our DWR with practical data.For our simulations, we used R packages implemented in R (R Development Core Team 2020) following the clv package (version 0.3–2.2) and the cluster package (version 2.1.1).(2) Results for Iris Dataset. In fact, Iris dataset is 4-dimensional data which consists of 3 clusters. Figure 10 shows 2-dimensional scatter plot of pairwise features. Figure 11 shows the graph of DBI, DU, SI, and Gap. And Figure 12 shows the graph of DWR with the initial number of clusters, k0 = 14, and the number of repeats, r = 3.Figure 11
Graph of Dunn’s index, Davies–Bouldin index, Average Silhouette index, and Gap statistic with the number of clusters for Iris dataset.Figure 12
Graph of DWR value with the number of objects for Iris dataset.DBI is minimized atn = 2, DU is maximized at n = 2, SI at n = 2, and Gap at n = 8. Thus, according to DBI, DU, SI, and Gap, their optimal numbers are 2, 2, 2, and 8. Our DWR graph shows the exact number of clusters 3.(3) Results for Synthetic Dataset. Synthe.tr dataset is 2-dimensional data which consists of 2 clusters. Figure 13 shows its 2-dimensional scatter plot. This data is very difficult to find the cluster number from the plot. Figure 14 shows the graph of DBI, DU, SI, and Gap. And Figure 15 shows the graph of DWR with k0 = 14 and r = 3.Figure 13
Synth.tr dataset (the optimal cluster number is 2).Figure 14
Graphs of Dunn’s index, Davies–Bouldin index, Average Silhouette index, Gap statistic with the number of clusters for synth.tr dataset.Figure 15
Graph ofDWR value with the number of objects for synth.tr dataset.As we can see on the graph, the optimal numbers from DBI, DU, SI, and Gap are 5, 5, 2, and 4. DWR graph has 1 clear boundary, so we can estimate that the cluster number is 2.


### 4.2. Comparative Study on Cluster Number Determination

We have chosen 7 real-world datasets,iris, wine, glass, ovarian, crab, landsat satellite, magic, and 6 synthetic datasets, synth1, synth2, synth3, synth4, synth5, synth6, synth7, synth8 for observing the performance of our algorithm in real-time. The results of estimating cluster numbers with DBI, SI, DU, Gap, CH, and the new approach are given in Tables 2 and 3.Table 2
Cluster number prediction on real-world datasets.
DatasetsInstancesFeature dimensionTrue KComparison of seven approaches in cluster number detectionCHDUSilhouetteGapDBDWRKRunning time (second)KRunning timeKRunning timeKRunning timeKRunning timeKRunning timeIris15043312121212131Wine17813311110121217131Glass21492313131217121Ovarian21610022111121212121Crab2006210113121213131Landsat satellite64353663171019315128463546Magic19020/6340102215217214727359525Total20343751411630314158633151916Sum of errors203366213Table 3
Cluster number prediction on synthetic datasets.
DatasetsInstancesFeature dimensionTrue KComparison of seven approaches in cluster number detectionCHDUSilhouetteGapDBDWRKRunning time (second)KRunning timeKRunning timeKRunning timeKRunning timeKRunning timesynth1150023143232102252121synth2900299191972159151synth340022151611312315131synth41000222115125252121synth5100022212121212121synth6100022212121212121synth73000555255583134151synth810001044224363172141Total295312431738391880388258Sum of errors24201311176The iris, wine, glass, ovarian, and crab are drawn from R or MATLAB. The landsat satellite and magic are downloaded from “UCI Machine learning repository” [19]. Clustered datasets synth1, synth2, synth3, synth4, synth5, synth6, synth7, and synth8 were generated. In Figure 16, 2-dimensional synthetic datasets such as synth1, synth2, synth3, synth4, synth5, and synth6 are plotted.Figure 16
2-dimensional synthetic datasets synth1, synth2, synth3, synth4, synth5, and synth6.Here, the estimation with DBI, SI, DU, Gap, and CH is conducted on NbClust, one of R packages, where the parameter “method” is set as “ward.D.” However, for the magic dataset, calculation of the indices is not possible for the stack memory error arises. So, we computed the value of all indices with 6,340 objects sampled randomly uniformly from the dataset.We found that the cluster number was well determined iniris, wine, glass, ovarian, magic, and synth1, synth4, synth5, synth6 while not in crab, synth2, synth3. Actually, the estimation of the cluster number of the dataset landsat satellite has a significant aberration for all indices. Anyway, the result of DWR is the most approximate among all the indices above for the currently informed data in this experiment; running time for the DWR is nearly the same as DBI and is remarkably shorter than for others.


### 4.3. Discussion

Our algorithm simply estimates the cluster number without clustering for everyK based on the graphics of DWR unlike other several approaches. In Tables 2 and 3, it seems that the results of our estimation for the cluster number are similar to the real cluster numbers for almost datasets. However, the results of datasets crab, synth2, and synth3 elucidate that the prediction of the number of clusters seems not always to go well. Although, in many cases, it is possible to predict an excellent outcome by choosing appropriate norm and K-point separation measurement of expression (2), there are exceptions in number prediction and clustering of some kinds of dataset such as heterogeneous distribution, sparse, and abnormal data.For example, we can assume that in Definition 1,a1, a2, …, ak are density functions, the norm of numerator is L1-norm in functional space and that U is the function of equation (1); then equation (2) is the dispersion-width ratio separation measurement for k distributions. This allows us use DWR for estimating the right number of clusters or clustering distributions.


## 4.1. Simulation

### 4.1.1. Datasets

(1) Iris Dataset. The first dataset is Iris dataset that widely used for evaluating clustering method. It has 150 samples data with 3 classes: setosa, versicolor, and virginica. Each class has 50 samples having four features (sepal length, sepal width, petal length, and the petal width). This is shown in Figure 10. Note that two clusters of Iris dataset are overlapped and one cluster is separated from those clusters. For simulations, we used the Iris data in the datasets package (version 4.0.3) of R (R Development Core Team 2020).Figure 10
Iris dataset (the real number of clusters is three).(2) Synthetic Dataset. This is synthesized 2-d dataset with 250 data points consisting two clusters. This data is used in the synth.tr data of the MASS package (version 7.3–53) of R (R Development Core Team 2020).


### 4.1.2. Experimental Results

(1) Results for Some Datasets. We calculated values of DBI, DU, SI, Gap, and CH for different values of K and our DWR with practical data.For our simulations, we used R packages implemented in R (R Development Core Team 2020) following the clv package (version 0.3–2.2) and the cluster package (version 2.1.1).(2) Results for Iris Dataset. In fact, Iris dataset is 4-dimensional data which consists of 3 clusters. Figure 10 shows 2-dimensional scatter plot of pairwise features. Figure 11 shows the graph of DBI, DU, SI, and Gap. And Figure 12 shows the graph of DWR with the initial number of clusters, k0 = 14, and the number of repeats, r = 3.Figure 11
Graph of Dunn’s index, Davies–Bouldin index, Average Silhouette index, and Gap statistic with the number of clusters for Iris dataset.Figure 12
Graph of DWR value with the number of objects for Iris dataset.DBI is minimized atn = 2, DU is maximized at n = 2, SI at n = 2, and Gap at n = 8. Thus, according to DBI, DU, SI, and Gap, their optimal numbers are 2, 2, 2, and 8. Our DWR graph shows the exact number of clusters 3.(3) Results for Synthetic Dataset. Synthe.tr dataset is 2-dimensional data which consists of 2 clusters. Figure 13 shows its 2-dimensional scatter plot. This data is very difficult to find the cluster number from the plot. Figure 14 shows the graph of DBI, DU, SI, and Gap. And Figure 15 shows the graph of DWR with k0 = 14 and r = 3.Figure 13
Synth.tr dataset (the optimal cluster number is 2).Figure 14
Graphs of Dunn’s index, Davies–Bouldin index, Average Silhouette index, Gap statistic with the number of clusters for synth.tr dataset.Figure 15
Graph ofDWR value with the number of objects for synth.tr dataset.As we can see on the graph, the optimal numbers from DBI, DU, SI, and Gap are 5, 5, 2, and 4. DWR graph has 1 clear boundary, so we can estimate that the cluster number is 2.


## 4.1.1. Datasets

(1) Iris Dataset. The first dataset is Iris dataset that widely used for evaluating clustering method. It has 150 samples data with 3 classes: setosa, versicolor, and virginica. Each class has 50 samples having four features (sepal length, sepal width, petal length, and the petal width). This is shown in Figure 10. Note that two clusters of Iris dataset are overlapped and one cluster is separated from those clusters. For simulations, we used the Iris data in the datasets package (version 4.0.3) of R (R Development Core Team 2020).Figure 10
Iris dataset (the real number of clusters is three).(2) Synthetic Dataset. This is synthesized 2-d dataset with 250 data points consisting two clusters. This data is used in the synth.tr data of the MASS package (version 7.3–53) of R (R Development Core Team 2020).


## 4.1.2. Experimental Results

(1) Results for Some Datasets. We calculated values of DBI, DU, SI, Gap, and CH for different values of K and our DWR with practical data.For our simulations, we used R packages implemented in R (R Development Core Team 2020) following the clv package (version 0.3–2.2) and the cluster package (version 2.1.1).(2) Results for Iris Dataset. In fact, Iris dataset is 4-dimensional data which consists of 3 clusters. Figure 10 shows 2-dimensional scatter plot of pairwise features. Figure 11 shows the graph of DBI, DU, SI, and Gap. And Figure 12 shows the graph of DWR with the initial number of clusters, k0 = 14, and the number of repeats, r = 3.Figure 11
Graph of Dunn’s index, Davies–Bouldin index, Average Silhouette index, and Gap statistic with the number of clusters for Iris dataset.Figure 12
Graph of DWR value with the number of objects for Iris dataset.DBI is minimized atn = 2, DU is maximized at n = 2, SI at n = 2, and Gap at n = 8. Thus, according to DBI, DU, SI, and Gap, their optimal numbers are 2, 2, 2, and 8. Our DWR graph shows the exact number of clusters 3.(3) Results for Synthetic Dataset. Synthe.tr dataset is 2-dimensional data which consists of 2 clusters. Figure 13 shows its 2-dimensional scatter plot. This data is very difficult to find the cluster number from the plot. Figure 14 shows the graph of DBI, DU, SI, and Gap. And Figure 15 shows the graph of DWR with k0 = 14 and r = 3.Figure 13
Synth.tr dataset (the optimal cluster number is 2).Figure 14
Graphs of Dunn’s index, Davies–Bouldin index, Average Silhouette index, Gap statistic with the number of clusters for synth.tr dataset.Figure 15
Graph ofDWR value with the number of objects for synth.tr dataset.As we can see on the graph, the optimal numbers from DBI, DU, SI, and Gap are 5, 5, 2, and 4. DWR graph has 1 clear boundary, so we can estimate that the cluster number is 2.


## 4.2. Comparative Study on Cluster Number Determination

We have chosen 7 real-world datasets,iris, wine, glass, ovarian, crab, landsat satellite, magic, and 6 synthetic datasets, synth1, synth2, synth3, synth4, synth5, synth6, synth7, synth8 for observing the performance of our algorithm in real-time. The results of estimating cluster numbers with DBI, SI, DU, Gap, CH, and the new approach are given in Tables 2 and 3.Table 2
Cluster number prediction on real-world datasets.
DatasetsInstancesFeature dimensionTrue KComparison of seven approaches in cluster number detectionCHDUSilhouetteGapDBDWRKRunning time (second)KRunning timeKRunning timeKRunning timeKRunning timeKRunning timeIris15043312121212131Wine17813311110121217131Glass21492313131217121Ovarian21610022111121212121Crab2006210113121213131Landsat satellite64353663171019315128463546Magic19020/6340102215217214727359525Total20343751411630314158633151916Sum of errors203366213Table 3
Cluster number prediction on synthetic datasets.
DatasetsInstancesFeature dimensionTrue KComparison of seven approaches in cluster number detectionCHDUSilhouetteGapDBDWRKRunning time (second)KRunning timeKRunning timeKRunning timeKRunning timeKRunning timesynth1150023143232102252121synth2900299191972159151synth340022151611312315131synth41000222115125252121synth5100022212121212121synth6100022212121212121synth73000555255583134151synth810001044224363172141Total295312431738391880388258Sum of errors24201311176The iris, wine, glass, ovarian, and crab are drawn from R or MATLAB. The landsat satellite and magic are downloaded from “UCI Machine learning repository” [19]. Clustered datasets synth1, synth2, synth3, synth4, synth5, synth6, synth7, and synth8 were generated. In Figure 16, 2-dimensional synthetic datasets such as synth1, synth2, synth3, synth4, synth5, and synth6 are plotted.Figure 16
2-dimensional synthetic datasets synth1, synth2, synth3, synth4, synth5, and synth6.Here, the estimation with DBI, SI, DU, Gap, and CH is conducted on NbClust, one of R packages, where the parameter “method” is set as “ward.D.” However, for the magic dataset, calculation of the indices is not possible for the stack memory error arises. So, we computed the value of all indices with 6,340 objects sampled randomly uniformly from the dataset.We found that the cluster number was well determined iniris, wine, glass, ovarian, magic, and synth1, synth4, synth5, synth6 while not in crab, synth2, synth3. Actually, the estimation of the cluster number of the dataset landsat satellite has a significant aberration for all indices. Anyway, the result of DWR is the most approximate among all the indices above for the currently informed data in this experiment; running time for the DWR is nearly the same as DBI and is remarkably shorter than for others.


## 4.3. Discussion

Our algorithm simply estimates the cluster number without clustering for everyK based on the graphics of DWR unlike other several approaches. In Tables 2 and 3, it seems that the results of our estimation for the cluster number are similar to the real cluster numbers for almost datasets. However, the results of datasets crab, synth2, and synth3 elucidate that the prediction of the number of clusters seems not always to go well. Although, in many cases, it is possible to predict an excellent outcome by choosing appropriate norm and K-point separation measurement of expression (2), there are exceptions in number prediction and clustering of some kinds of dataset such as heterogeneous distribution, sparse, and abnormal data.For example, we can assume that in Definition 1,a1, a2, …, ak are density functions, the norm of numerator is L1-norm in functional space and that U is the function of equation (1); then equation (2) is the dispersion-width ratio separation measurement for k distributions. This allows us use DWR for estimating the right number of clusters or clustering distributions.


## 5. Conclusion

In this paper, we have proposed a new method to determine the cluster number.Firstly, we have proposed a new statistics RVR and illustrated its characteristics by Monte Carlo analysis with the statistics DWR defined as the ratio of dispersion to width, which is one of RVRs. Based on it, we have designed a new algorithm for determining cluster number of multivariate dataset. Then, we have provided examples which determine the cluster number with 2 datasets. Finally, we have verified the significant improvements in speed and quality for determining cluster number by performing simulation some real-life datasets and synthetic datasets.Our algorithm simply determines the cluster number without clustering for every possibleK, the cluster number. Therefore, it reduces complexity and can effectively be used for clustering multidimensional data. In future, changing K-point separation measure according to structural property of data, we will improve our statistics to expand apt instance of data type. In recent time, our research focuses on the application of this idea to clustering large data, multivariate distributions, and spectral clustering and validating the clustering results. On the other hand, research on improving the algorithm by modulating the norm and K-point separation measurement of equation (2) in cluster number prediction and clustering of sparse and abnormal data will kick off in no time.



---

*Source: 6866747-2022-07-15.xml*