# Adaptive Clustering via Symmetric Nonnegative Matrix Factorization of the Similarity Matrix
## 1 Introduction
For example, sparsity and/or regularizing constraints can be easily embedded [5], classification labels can be incorporated through a supervisor [11], and extensions to tensor nonnegative factorization have been studied [12]. Since our goal was to obtain clustering through the symmetric matrix \(A\), we restricted our analysis to the symmetric NMF problem. When a clustering problem is proposed, the dimension of the clustering, that is, the number \(k\) of the clusters, can be either given a priori or looked for. In this paper we consider both cases:  
* problem \(\mathcal{P}_{k\ell ix}\), with an a priori assigned rank \(k\) of matrix \(W\). The matrix \(W\) is computed using NMF and the clustering is obtained. * \(\mathcal{P}_{k\ell x}\), where an interval \(\mathcal{J}_{k}=[k_{\text{min}},k_{\text{max}}]\) is assigned. The number \(k\) varies in \(\mathcal{J}_{k}\) and the best \(k\), according to a given criterium, has to be found. The algorithm solving \(\mathcal{P}_{k\ell ix}\) is a constitutive brick of a larger procedure for \(\mathcal{P}_{k\ell x\ell}\). When dealing with \(\mathcal{P}_{k\ell x\ell}\), the factorization of \(A\) must be performed for each \(k\) in \(\mathcal{J}_{k}\), and a validity index must be provided to compare the clusterings obtained with different \(k\) to decide which is the best one. Our contribution consists in devising an algorithm which implements a heuristic approach by improving a multistart policy. The algorithm, especially suitable when working in a multitasking/multiprocessor environment, lets the computation efforts be concentrated on the more promising runs, without any a priori knowledge. Each run applies a BCD technique known as alternating nonnegative least squares, which replaces the BPP method used in [13] by the GCD method of [7]. This choice, as shown in a previous paper [14], leads to a saving in the computational cost of the single run. The suggested heuristics enjoys the same effectiveness of the standard implementation of a multistart approach, with a considerable reduction of the cost. Its only drawback is more complicated coding. The paper is organized as follows: Section 2 is devoted to recall the alternating nonnegative least squares procedure for NMF with both general matrices and symmetric matrices, constituting the basis of our proposed algorithm. Section 3 describes the validity indices used for comparison criteria. Next, in Section 4, the algorithm for problem \(\mathcal{P}_{kfix}\) is presented, with a priority queue implementation to reduce the computational time. The extension of the algorithm to problem \(\mathcal{P}_{kvar}\), described in Section 5, requires particular attention to the scale parameter \(\sigma\) chosen for the construction of \(A\) by using (1) and (2). The experiments are described and commented on in Section 6. Notations: the \((i,j)\)th element of a matrix \(M\) is denoted by \((M)_{i,j}\) or by the lowercase \(m_{i,j}\). The notation \(M\geq O\) means that all the elements of \(M\) are nonnegative. Several parameters enter in the description of the algorithm. In the text, where they are introduced, the notation \"(Section 6)\" appears, meaning that the values assigned to them in the experiments are listed at the beginning of Section 6.