# Boundary Matching and Interior Connectivity-Based Cluster Validity Analysis
## 3 Materials and Methods
### Boundary Matching and Connectivity  
The density of any point in the existing clustering analysis is computed by counting the number of points in the point's neighborhood with a specified radius. However, the computed density only is a group of discrete integers such as 1, 2,..., and thus many points have the same density which is indistinguishable. Moreover, the defined density may greatly be affected by the specified radius. In this study, we first define a nonparametric density to find all boundary and interior points in any dataset. Assume \(X=\{x_{1},\ x_{2},\ \ldots,\ x_{n}\ \}\) is a dataset in a \(D\)-dimensional space \(R^{D}\). For any data point \(x_{k}\in X\), its \(m\) nearest neighbors are denoted as, \(x_{k,1}\), \(x_{k,2}\),..., \(x_{k,m}\), with distances \(d(x_{k},x_{k,1})\), \(d(x_{k},\ x_{k,2})\),..., \(d(x_{k},x_{k,m})\), where \(m\) is the integer part of \(2D\pi\), \(k=1\), \(2\),..., \(n\). Here, \(2D\) shows that oneinterval in any dimension in \(R^{D}\) can be measured by the two-interval endpoints, and \(\pi\) is a conversing coefficient when the \(m\) points are enclosed by a spherical neighborhood that is used in the existing density computation. Therefore, the density of any data point \(x_{k}\) in \(X\) is defined as  
\[density(x_{k})=\left\{\sum\
olimits_{j=1}^{m}d(x_{k},x_{k,j})\right\}^{-1}, \ k=1,2,\ldots,n \tag{10}\]  
**Definition 1**. : _Boundary point and interior point. A point is called as a boundary or interior point if half of its \(m\) nearest neighbors have a higher or lower (equal) density than its density, respectively._  
The proposed notion of boundary and interior points have the following two characteristics. (1) Certainty. Unlike the used density in other existing algorithms, the proposed density is fixed and unique for any point, which reduces the uncertainty in the clustering process. In fact, the clustering results in other algorithms may greatly be changed as the number of neighbors used for computing the density increases or decreases. Note that the effective estimation of the number of neighbors has been a difficult task, and so far, it remains unsolved [35]. (2) Locality. The classification of border or interior points is defined only by its \(m\) nearest neighbors, so the separating boundary or interior points presents local characteristics. Inversely, DBSCAN uses a global density to distinguish border or interior points in a density-skewed dataset, which even causes an entire cluster to be perfectly regarded as border points (see Figure 4). Therefore, the proposed density is a more reasonable local notion. Figure 4a shows a density-skewed dataset with three clusters of large, medium, and small density, respectively. The red points in Figure 4a,b represent the boundary points computed by using DBSCAN and (10), respectively. DBSCAN can find no interior points in the cluster with the lowest density; in comparison, owing to the locality of (10), the red border points and blue interior points determined are distributed more reasonably. The interior points are located at the center of any cluster and surrounded by border points, while the border points construct the shape and structure of any clusters. Specifically, after the removal of border points in any dataset, the separation of clusters is greatly enhanced (see Figure 4c). Therefore, the real number of clusters can be determined more easily by any clustering algorithm. In graph theory, a cluster is defined as a group of points that connect to each other [36; 37]. In order to assess the connectivity of points in a dataset \(X\), we calculate the density for all points in \(X\) and sort them in the order of increasing density. Assume \(x_{max}\) is the point with the highest density in \(X\), and thereby, a connecting rule among points is defined as follows. For any point \(x_{k}\)\(X\), the next point \(x_{k+1}\) is the point which is the nearest neighbor of \(x_{k}\) but has a higher density than \(x_{k}\). Subsequently, repeat the above steps until visiting the point \(x_{max}\).