# Adaptive Clustering via Symmetric Nonnegative Matrix Factorization of the Similarity Matrix
## 4 The Clustering Algorithm for Problem \(\mathcal{P}_{kfix}\)  
Given a fixed value of \(k\), the algorithm Kfix we propose for problem \(\mathcal{P}_{kfix}\) searches the minimum of (6). This algorithm will be used in Section 5 for solving problem \(\mathcal{P}_{kvar}\). Before describing it, it is necessary to deal with the important issue of how to choose a suitable value of the scale parameter \(\sigma\) for the construction of the similarity matrix \(A\) according to (1) and (2). Values of \(\sigma\) that are too small or too large would reduce the variability of \(A\), making all the points equally distant, resulting in badly mixed-up clusters. Since we must discriminate between close and far points, an intermediate value between the smallest and the largest distance of the points should be chosen. Clearly, there is a strong correlation between the value of \(\sigma\) and the number \(k\) of clusters that the algorithm is expected to find: more clusters may have a smaller size and may require a smaller \(\sigma\) to separate them. To this aim, a triplet \(\sigma^{(k)}\) of suitable values (Section 6) is detected and tested for any \(k\). Besides the choice of \(\sigma\), the choice of the initial matrix \(W_{0}\) may also be critical, due to the fact that only a local minimum of problem (6) can be expected. It is common practice to tackle this issue by comparing the results obtained by applying Sym_NMF to several matrices \(W_{0}\), randomly generated with uniform distribution between \(0\) and \(1\). The number of the starting matrices is denoted \(q\) (Section 6). For any pair \(\{\sigma,W_{0}\}\) with \(\sigma\in\sigma^{(k)}\), matrix \(A(\sigma)\) is constructed using (1) and (2) and the function Sym_NMF is applied starting with \(W_{0}\). Then, the DB index \(\chi\) of the clustering so obtained is computed. A trivial multistart implementation could consist in carrying out, up to convergence, function Sym_NMF for any pair \(\{\sigma,W_{0}\}\) and choosing, at the end, the best \(\chi\). In the following we present a more sophisticated version, suitable for large problems, which uses a heuristic approach. The run for any pair \(\{\sigma,W_{0}\}\) is split in segments with a fixed number \(\lambda\) of iterations, and the execution scheduling is driven by the values \(\chi\) already found. The possibility of discarding the less promising runs is considered. The proposed strategy, which is accomplished by using a priority queue, specializes to the present clustering problem the procedure given in [24], where the global minimization of a polynomial function is dealt with. In [24], the heuristic approach is shown to outperform the multistart one for what regards the computational cost, maintaining the same efficacy. The items of the priority queue \(\mathcal{Q}\) have the form  
\[Y=\{r,t,W,H,\alpha,\xi\},\]  
where  
* \(r\) is the index which identifies the pair \(\{\sigma,W_{0}\}\). * \(t=t^{(r)}\) is the number of iterations computed until now by Sym_NMF on the item with index \(r\). Initially \(t=0\). * \(W=W^{(r)}\) and \(H=H^{(r)}\) are the NMF factors of \(A(\sigma)\) computed for the \(r\)th item. Initially \(W=W_{0}\), \(H=\mathcal{O}\). * \(\alpha=\alpha^{(r)}\) is the penalizing parameter of the \(r\)th item. Initially \(\alpha=\max A(\sigma)\). * \(\xi=\chi^{(r)}+t^{(r)}/t_{\max}\), where \(\chi^{(r)}\) is the DB index defined in (9) for the \(r\)th item, and \(t_{\max}\) (Section 6) is the maximum number of allowed iterations for the \(r\)th item. Initially \(\xi=0\). The queue is ruled, according to the minimum policy, by the value of \(\xi\), allowing to compute first the more promising items, keeping into account also the age of the computation. Initially, the priority queue contains \(3\,q\) items. Also referred in the procedure, but not belonging to the queue, are  
* an array \(\mathbf{m}\) of length \(k\), whose \(i\)th element contains the minimum of the DB indices computed so far for all the items returning \(k_{e}=i\). Initially, the elements of \(\mathbf{m}\) are set equal to \(\infty\).