# Boundary Matching and Interior Connectivity-Based Cluster Validity Analysis
## 3 Materials and Methods
### Clustering Evaluation Based on Boundary and Interior Points  
Once a clustering algorithm has partitioned a dataset \(X\) into \(c\) disjoint clusters, i.e., \(X=C_{1}\cup C_{2}\cup\dots\cup C_{c}\), we substitute \(X\) by \(C_{1}\), \(C_{2}\),..., \(C_{c}\), respectively, and find their boundary points using (10). The set of boundary points in \(C_{k}\) is denoted as \(BC_{k}\), while the set of boundary points in \(X\) is \(BX\). A boundary-point-matching index is defined as  
\[bou(c)=\sum\
olimits_{k=1}^{c}\frac{|BX\cap BC_{k}|}{|BX\cup BC_{k}|}. \tag{12}\]  
Equation (12) measures the matching degree of boundary points between the entire dataset \(X\) and the disjoint \(C\) clusters. In the mathematical meaning, it is clear that the values of \(bou\) (\(c\)) must fall in the interval [0, 1]. The following example can explain the cases that are smaller and equivalent to 1. Figure 5: All chains in two datasets with different characteristics: (a) chains in a dataset of spherical clusters; (b) chains in a dataset of nonspherical clusters. Figure 6a-c show the boundary and interior points determined by (10) when performing C-means algorithm at \(c\) is smaller, equal to or larger than 6, respectively, where interior points refer to the remaining points after removing boundary points. The red boundary points at \(c=3\) and 6 are similar to these in \(X\), but these boundary points at \(c\) equals 10 are different from those in \(X\). Figure 6d shows that the values of _bou_ (\(c\)) are nearly unchangeable when \(c<6\) but decrease fast when \(c>6\). When the number of clusters \(c\) is smaller than the actual one, and usually, any cluster does not be assigned two cluster centers. Therefore, the set of boundary points of all partitioned clusters are consistent with the entire set \(X\), and _bou_ (\(c\)) = 1. When \(c\) is larger than the actual number of clusters, there is at least one cluster the number of whose boundary points increase. Thus, _bou_ (\(c\)) < 1. It can be seen that the values of _bou_ (\(c\)) are helpful to find the real number of clusters for any clustering algorithm. Alternatively, we can regard any cluster in \(C_{1}\), \(C_{2}\),..., \(C_{c}\) as an independent dataset like \(X\), and accordingly, \(x_{max}\) in \(X\) become these points with maximal density in \(C_{1}\), \(C_{2}\),..., and \(C_{c}\), respectively. Thereby, we assess the connectivity among points according to (11) when \(c\) = 1, 2,..., \(c_{\max}\). The connectivity of \(X\) is reduced to the connectivity of each cluster. As \(c\) increases, the connectivity is enhanced since the number of maximal inter-cluster distances in these chains decreases. Figure 7a-c show the connectivity calculated using (11) and C-means when \(c\) equals 3, 6, and 10, respectively. This value becomes smaller when \(c<6\), while it tends to be flat when \(c>6\), as shown in Figure 7d. Consequently, there is an inflection point on the curve in Figure 7d. As \(c\) increases, both the curves calculated according to (11) and (12) have inversely varying tendencies. It is expected that the real number of clusters is encountered at \(c^{*}\), where the curve of (11) turns to be flat from fast-changing, and that of (12) becomes fast varying from slow-changing. Considering the variances of _bou_ (\(c\)) and _con_(\(c\)) can be calculated by curvature radius mathematically, we define a novel validity index according to _bou_ (\(c\)) for boundary points and _con_(\(c\)) for interior points, respectively. By combining (11) and (12), we define a function as follows  
Figure 6: (**a–c**) shows the determined boundary points by using C-means and (10) when \(c\) = 3, 6, and 10, respectively. Blue and red points refer to the interior and boundary points, respectively; (**d**) shows the curve of _bou_ (\(c\)) calculated according to (11); the sign \(\Delta\) means the center of C-means. Figure 7: (**a–c**) The chains when c = 3, 6, and 10, respectively; (**d**) shows the curve of (11).