# Boundary Matching and Interior Connectivity-Based Cluster Validity Analysis
## 3 Materials and Methods
### Clustering Evaluation Based on Boundary and Interior Points
## 4 Results and Discussion

We test the accuracy of CVIBI on two groups of typical datasets and compare it with three existing validity indices, i.e., DB, DC, and GS. In views of different characteristics of the investigated datasets, the clustering results are obtained using C-means, DPC, and DBSCAN algorithms, respectively, where the number of neighbors \(m\) in the experiments is fixed at the integer part of \(2D\pi\). ### Tests on Synthetic Datasets

Figure 8 shows five groups of synthetic datasets generated by the Matlab(r) toolbox, and each group consists of three datasets with different numbers of clusters. The determined boundary and interior points are in red and blue, respectively. The 15 datasets are denoted as sets 1-15, respectively. groups 1-4 contain the datasets with various densities, sizes, shapes, and distributions, respectively; and group 5 contains overlapped clusters. The characteristics of these datasets are listed in Table 2. The first column of Table 2 denotes the names of these datasets. The second and fourth columns represent the numbers of clusters and objects of datasets, respectively. The third column denotes the dimensions of these datasets. The last column shows the number of objects of each cluster in datasets. The number of neighbors \(m\) plays an essential role in CVIBI. Different values of \(m\) may lead to very different density and distance values, and thus to different evaluation results. As an example, we solve the range of \(m\) in which each number can lead to the correct number of clusters when using DPC. Let \(m=1,2,\ldots,n\), respectively. Along with these values of \(m\), DPC is used to cluster all points in sets 1-15, respectively. Figure 9 shows the solved ranges in the 15 datasets that are represented by blue bars, where the red line in any bar denotes the value that is the integer part of \(2D\pi\). All the experimental datasets used in Figure 8 are in the two-dimensional data space. Thus, \(D=2\) and the integer part of \(2D\pi\) is just 12. Figure 9 shows that all the values of \(2D\pi\) fall into the solved ranges corresponding to the correct number of clusters, which demonstrates the effectiveness and robustness of \(2D\pi\). Consequently, we can fix the number of neighbors \(m\) at \(2D\pi\) in experiments. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Name** & **Clusters** & **Dimension** & **Number of Objects** & **Number of Each Cluster** \\ \hline _Set 1_ & 3 & 2 & 600 & 83/164/353 \\ _Set 2_ & 4 & 2 & 350 & 30/60/120/240 \\ _Set 3_ & 5 & 2 & 830 & 30/60/120/240/480 \\ _Set 4_ & 3 & 2 & 420 & 60/120/240 \\ _Set 5_ & 4 & 2 & 900 & 60/120/240/480 \\ _Set 6_ & 5 & 2 & 1860 & 60/120/240/480/960 \\ _Set 7_ & 3 & 2 & 1018 & 341/336/341 \\ _Set 8_ & 4 & 2 & 404 & 134/90/90/90 \\ _Set 9_ & 5 & 2 & 494 & 134/90/90/90/90 \\ _Set 10_ & 3 & 2 & 360 & 120/120/120 \\ _Set 11_ & 4 & 2 & 800 & 200/200/200/200 \\ _Set 12_ & 5 & 2 & 1000 & 200/200/200/200 \\ _Set 13_ & 3 & 2 & 600 & 200/200/200 \\ _Set 14_ & 4 & 2 & 400 & 100/100/100/100 \\ _Set 15_ & 5 & 2 & 1000 & 200/200/200/200/200 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Characteristics of 15 datasets in Figure 8.

Figure 8: _Cont._

Figure 8: Five groups of synthetic datasets. #### 4.1.1 Relationship between CVIBI and the Number of Clusters

The correctness of clustering evaluation depends on whether the correct number of clusters can be found by the validity index. In order to test the correctness of CVIBI, all points in these 15 datasets are partitioned into \(c\) clusters by DPC, C-means, and DBSCAN at \(c=1\), \(2\),..., \(c_{max}\), respectively, where the number of clusters in DBSCAN is obtained by taking various values of \(\varepsilon\). Figure 10 shows the curves of CVIBI based on the three algorithms, respectively. The points marked by small circles in these curves are the suggested optimal values of (13). Datasets in group 1 and group 2 contain clusters with different densities and sizes, respectively.