# Adaptive Clustering via Symmetric Nonnegative Matrix Factorization of the Similarity Matrix
## 4 The Clustering Algorithm for Problem \(\mathcal{P}_{kfix}\)
* an array \(M\), containing in position \(i\) the partition \(\Pi\) corresponding to \(m_{i}\). Initially, the elements of \(M\) are empty sets. The belonging of an element to an item \(Y\) is denoted by using the subscript (\(Y\)). Moreover, \(A_{(Y)}\) denotes the similarity matrix \(A(\sigma)\) generated with the scale parameter \(\sigma\) associated with \(r_{(Y)}\). After the initialization of the queue, the adaptive process evolves as follows: an item \(Y\) is extracted from the queue according to its priority \(\xi_{(Y)}\), and the function Sym_NMF is applied. A new item is so built and, if it is recognized as promising by a specific function Control, it is inserted back into \(\mathcal{Q}\). Otherwise, if \(Y\) is not promising, no new item is inserted back into \(\mathcal{Q}\)--that is, \(Y\) is discarded. Two bounds, \(t_{\min}\) and \(t_{\max}\) (Section 6), are used to control the execution flow for each item. ```
functionKfix(\(k,\sigma^{(k)},q\));
```  
```
inizialize\(m,\ M,\ Q=\{\ \}\);  compute matrices\(A(\sigma_{i}^{(k)})\), for \(i=1,\ldots,3\), using (1) and (2);  generate randomly \(W_{0}(j)\), for \(j=1,\ldots,q\); for\(i=1\)to\(3\) \(A=A(\sigma_{i})\); \(\alpha=\max\ A\); for\(j=1\)to\(q\) \(W_{0}=W_{0}(j)\); \(r=i+3(j-1)\);  Enqueue\(\left(\mathcal{Q},\{r,0,W_{0},O,\alpha,0\}\right)\); endfor endfor \(\chi_{\min}=\infty\); whileLength\((\mathcal{Q})\geq 1\) \(Y=\texttt{Dequeue}\left(\mathcal{Q}\right)\); \(\{\
u,W,H,\alpha,cond\}=\texttt{Sym\_NMF}\left(A_{(Y)},W_{(Y)},H_{(Y)},\alpha _{(Y)},\lambda\right)\); \(\left(\Pi,\ k_{e}\right)=\texttt{Partition}\left(W\right)\); \(\chi=\texttt{DBindex}(\Pi)\); \(t=t_{(Y)}+\
u\); \(\xi=\chi+t/t_{\max}\); ifControl\((t,\chi,\Pi,k_{e},cond)\)thenEqueue\(\left(\mathcal{Q},\{r_{(Y)},t,W,H,\alpha,\xi\}\right)\) endwhile return\((M,\ m)\);
```  
At the end, the \(k\)th partition in \(M\), if not empty, is the solution of the problem for the given \(k\). Other partitions possibly present in \(M\) can be of interest, and will be used when Kfix is called for solving \(\mathcal{P}_{\mathit{kvar}}\). The core of the whole procedure is the following Boolean function Control, which verifies whether an item is promising (i.e., must be further processed) or not. ```
functionControl\((t,\chi,\Pi,k_{e},cond)\);
```  
```
if\(\chi<m_{k_{e}}\)then\(m_{k_{e}}=\chi\);\(M_{k_{e}}=\Pi\); if\(k_{e}<k\)thenreturn\(t<2\,t_{\min}\); if\(cond\mid\mid\mid\)(\(t>t_{\max}\))thenreturnFalse; if\(t<t_{\min}\)thenreturnTrue; return\(\chi<m_{k_{e}}(1+\exp(1-t/t_{\min}))\)
```  
If True is returned, the selected item is enqueued again, otherwise it is discarded. When the number \(k_{e}\) of clusters effectively found is equal to the expected \(k\), and the convergence of Sym_NMF has not been yet reached, the item is enqueued both when \(t<t_{\min}\) and when \(t_{\min}<t<t_{\max}\), provided that \(\chi\) satisfies a bound, which becomes tighter as \(t\) increases. When, instead, \(k_{e}<k\), the item is enqueued only if less than \(2\,t_{\min}\) iterations have been performed. In any case, the best value of the DB index and the corresponding clustering are maintained for each value of \(k_{e}\leq k\). **Remark 1**. : _(a) The use of the priority queue allows for an easy parallelization of the computation by simultaneously keeping active a number of items most equal to the number of the available processors. The numerical examples of Section 6 have been carried out both with eight active processors and one active processor in order to evaluate the scalability of the algorithm._  
_(b) The use of an internal validity index is fundamental in our heuristics. Because of its high impact in the algorithm, the choice of the DB index among the many indices listed in [20] has been driven by its low computational time complexity. The DB index, which turned out to be reliable in our experimentation, tends to detect clusters with separated convex envelopes._