# Adaptive Clustering via Symmetric Nonnegative Matrix Factorization of the Similarity Matrix
## 6 Experimentation
To this aim, the two datasets of five points _Well-separated_ (WS) and _Well-separated noise_ (WSN) of Figure 3 are generated, the latter one with 5% noise added to the former. We applied Kvar, with \(k\) varying in the interval \([2,\,20]\) and obtained the piecewise linear plots versus \(k\) of Figure 4. For dataset WSN, according to the DB index, both \(k=5\) and \(k=6\) seemed to be acceptable. This uncertainty is explained by the presence of noise which causes spurious clusters to appear. The DB** index correctly suggests \(k=5\). The presence of noise is confirmed by the CL index which is not zero for small values of \(k\). To analyze more thoroughly the performance of our algorithm when subclusters are present, a third experiment was carried out concerning the three datasets of Figure 5. Dataset C17 consists of 1700 points generated around 17 randomly chosen centers; dataset C23, consisting of 2300 points, has 23 clusters of 100 points which can be grouped in several ways in a lower number of clusters; dataset C27, consisting of 2700 points, has 27 clusters of 100 points which can be seen as 9 clusters of 300 points or three clusters of 900 points, depending on the granularity level of interest. Figure 4: Plots versus \(k\) of DB (dashed line), DB** (solid line) and CL (dotted line) for WS and WSN. Figure 5: Synthetic datasets C17, C23, and C27 of points in \(\mathbb{R}^{2}\). \[\sigma_{0}^{(k)}=\widehat{\sigma}/8\text{ for }20<k\leq 40,\;\sigma_{0}^{ (k)}=\widehat{\sigma}/16\text{ for }k>40.\]0 Synthetic datasets, well-separated (WS) and well-separated noise (WSN) of points in \(\mathbb{R}^{2}\). Problems C17, C23, and C27 have been tested with values of \(k\) ranging in the intervals [2; 25], [2; 30], and [2; 35], respectively. The resulting piecewise linear plots versus \(k\) of DB, DB**, and CL indices are shown in \[\sigma_{0}^{(k)}=\widehat{\sigma}/8\text{ for }20<k\leq 40,\;\sigma_{0}^{ (k)}=\widehat{\sigma}/16\text{ for }k>40.\]1 By using the DB** indices, it clearly appears that our algorithm is able to find good clusterings for all three problems. The inspection of the plot of the DB** index gives further information. For example, for problem C17, a local minimum of the DB** index for \(k=4\) evidences the clustering shown in Figure 7 on the left. For problem C23, a local minimum of the DB** index for \(k=7\) evidences the possible clustering shown in Figure 7 on the right. For problem C27, two local minima in the DB** plot for \(k=3\) and \(k=9\) evidence the two other expected clusterings. In all the experiments shown above, the measure CL helps decide the value of \(k_{\max}\) if not assigned. The fourth test regards the computational cost of algorithm Kvar when run on one or eight processors. Due to its iterative and heuristic structure, our algorithm is not suitable for a theoretical analysis of the complexity. In order to analyze how the required time increases as a function of the number of the points, the datasets SC, SD, DD, WS, and WSN have been generated with \(n\) varying in \(\{1000,2000,4000,8000\}\) and \(k\) varying in the interval \([2,15]\). Figure 8 shows the plots versus \(n\) of the costs in seconds, averaged on all the datasets. The times corresponding to runs with one processor are fitted with a solid line, where those corresponding to runs with eight processors are fitted with a dashed line. The resulting polynomial fits are \(1.5\times 10^{-5}\,n^{2.16}\) for one processor and \(1.4\times 10^{-6}\,n^{2.23}\) for eight processors. This shows that for the considered problems, the time grows slightly more than quadratically as a function of \(n\), but clearly less than cubically, as one could expect. It also shows that the whole procedure has a good degree of scalability. \[\sigma_{0}^{(k)}=\widehat{\sigma}/8\text{ for }20<k\leq 40,\;\sigma_{0}^{ (k)}=\widehat{\sigma}/16\text{ for }k>40.\]2 Plots versus \(k\) of DB (dashed line), DB** (solid line), and CL (dotted line) for C17, C23, and C27.