# Boundary Matching and Interior Connectivity-Based Cluster Validity Analysis
## 3 Materials and Methods
### Clustering Evaluation Based on Boundary and Interior Points
Note that the points in the same color indicate that they are partitioned into the same cluster by using C-means algorithm and the sign \(\Delta\) means the center of C-means. \[F(c)=R_{1}(c)\bullet R_{2}(c) \tag{13}\] \[s.t.,\left\{ \begin{array}{l}R_{1}(c)=\big{|}\Delta_{1}(c)\big{|}^{2}/ (1+(\
abla_{1}(c))^{2})^{3/2}\\ \Delta_{1}(c)=\mathit{bou}(c+1)+\mathit{bou}(c-1)-\mathit{bou}(c),\
abla_{1}(c) =\mathit{bou}(c+1)-\mathit{bou}(c-1)\\ R_{2}(c)=\big{|}\Delta_{2}(c)\big{|}^{2}/(1+(\
abla_{2}(c))^{2})^{3/2}\\ \Delta_{2}(c)=\mathit{con}(c+1)+\mathit{con}(c-1)-\mathit{con}(c),\
abla_{2}( c)=\mathit{con}(c+1)-\mathit{con}(c-1)\end{array} \right.\]  
where the symbol \(\Delta\) denotes a two-order difference operator of \(\mathit{bou}\) (\(c\)) and \(\mathit{con}(c)\), aiming to locate the maximal inflection points on curves of \(\mathit{bou}\) (\(c\)) and \(\mathit{con}(c)\), respectively. The optimal number of clusters \(c^{*}\) for any dataset is computed as  
\[c^{*}=\mathrm{argmax}_{c}F(c). \tag{14}\]  
The proposed validity index has the following characteristics. 1. Complementarity. The mathematical curvature and difference can reflect the varied tendency of a curve in (13), and thereby the real number of clusters \(c^{*}\) can be found. When \(c<c^{*}\), \(R_{1}(c)\) is nearly equivalent to \(R_{1}(c^{*})\) since the set of boundary points is approximately unchangeable, but \(R_{2}(c)<R_{2}(c^{*})\), since the number of center points successively increase. In sum, \(F(c)<F(c^{*})\). Inversely, when \(c>c^{*}\), \(R_{1}(c)\) successively decreases, and \(R_{2}(c)\) tends to be flat; therefore, \(F(c)<F(c^{*})\). Consequently, (13) can attain a maximum when \(c^{*}\) appears. 2. Monotonicity. Assume that \(c^{*}\) is the real number of clusters, and when \(c\) takes its two values \(c_{1}\) and \(c_{2}\) satisfying \(c_{1}<c_{2}<c^{*}\), \(F(c_{1})<F(c_{2})<F(c^{*})\); otherwise, when \(c^{*}<c_{1}<c_{2}\), \(F(c^{*})>F(c_{1})>F(c_{2})\); Hence, \(F(c)\) consists of two monotone functions at the two sides of \(c^{*}\), respectively. Therefore, for arbitrary two values \(c_{1}\) and \(c_{2}\) satisfying \(c_{1}<c_{2}\), \(c_{2}\) may refer to a more optimal clustering result. Usually, a larger value of \(F(c^{*})\) indicates a better clustering result. 3. Generalization. Equation (13) can provide a wide entry for any clustering algorithm only if the clustering results are available and the corresponding numbers of clusters are taken as the variable of \(F(c)\). Especially, a group of clustering results may result from different clustering algorithms and parameters, since any two clustering results are comparable according to the above monotonicity. For example, one clustering result with \(c_{1}\) results from C-means, and others from DBSCAN, and so on. Equation (13) can evaluate the results of any clustering algorithm and parameter in a trial-and-error way. In comparison, the existing validity indices can mainly work for a specific algorithm and parameter of the number of clusters since the center in them has to be defined, especially for the C-means algorithm. Hereafter, the cluster validity index of (13) based on boundary and interior points is called CVIBI. The evaluating process for any clustering results based on CVIBI is listed in Algorithm 2. ``` Input: a dataset \(X\in R^{D}\) containing \(n\) points and clustering results from any clustering algorithm at \(c=1,2,\ldots,c_{max}\). Output: the suggested number of clusters. Steps:
1. Calculate the density for each point in \(X\) according to (10);
2. Partition \(X\) into boundary and interior points;
3. Input clustering results at \(c=1,2,\ldots,c_{max}\);
4. Partition each cluster into boundary and interior points;
5. Compute values of \(\mathit{bou}\) (\(c\)) or \(\mathit{con}(c)\) at \(c\) equals \(1,2,\ldots,c_{max}\);
6. Solve the optimal value of (13);
7. Suggest an optimal number of clusters. 8. Stop.