{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:48:57Z","timestamp":1760240937829,"version":"build-2065373602"},"reference-count":25,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2019,10,17]],"date-time":"2019-10-17T00:00:00Z","timestamp":1571270400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The problem of clustering, that is, the partitioning of data into groups of similar objects, is a key step for many data-mining problems. The algorithm we propose for clustering is based on the symmetric nonnegative matrix factorization (SymNMF) of a similarity matrix. The algorithm is first presented for the case of a prescribed number k of clusters, then it is extended to the case of a not a priori given k. A heuristic approach improving the standard multistart strategy is proposed and validated by the experimentation.<\/jats:p>","DOI":"10.3390\/a12100216","type":"journal-article","created":{"date-parts":[[2019,10,17]],"date-time":"2019-10-17T11:07:59Z","timestamp":1571310479000},"page":"216","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Adaptive Clustering via Symmetric Nonnegative Matrix Factorization of the Similarity Matrix"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0382-3195","authenticated-orcid":false,"given":"Paola","family":"Favati","sequence":"first","affiliation":[{"name":"Istituto di Informatica e Telematica-Consiglio Nazionale delle Ricerche (IIT-CNR), Via G. Moruzzi 1, 56124 Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3299-1967","authenticated-orcid":false,"given":"Grazia","family":"Lotti","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica, University of Parma, Parco Area delle Scienze 53\/A, 43124 Parma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ornella","family":"Menchi","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, University of Pisa, Largo Pontecorvo 3, 56127 Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8890-4490","authenticated-orcid":false,"given":"Francesco","family":"Romani","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, University of Pisa, Largo Pontecorvo 3, 56127 Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,10,17]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1007\/s10898-014-0247-2","article-title":"SymNMF: Nonnegative low-rank approximation of a similarity matrix for graph clustering","volume":"62","author":"Kuang","year":"2015","journal-title":"J. Glob. Optim."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1002\/env.3170050203","article-title":"Positive matrix factorization: A non-negative factor model with optimal solution of error estimates of data values","volume":"5","author":"Paatero","year":"1994","journal-title":"Environmetrics"},{"key":"ref_3","unstructured":"Lee, D.D., and Seung, H.S. Algorithms for non-negative matrix factorization. Advances in Neural Information Processing Systems 2001, Proceedings of the 2000 Conference (NIPS 2000), Denver, CO, USA, 1 January 2001, Neural Information Processing Systems Foundation."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1137\/07069239X","article-title":"Nonnegative matrix factorization based on alternating nonnegativity constrained least squares and active set method","volume":"30","author":"Kim","year":"2008","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/s10898-013-0035-4","article-title":"Algorithms for nonnegative matrix and tensor factorization: An unified view based on block coordinate descent framework","volume":"58","author":"Kim","year":"2014","journal-title":"J. Glob. Optim."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1587\/transfun.E92.A.708","article-title":"Fast local algorithms for large scale nonnegative matrix and tensor factorizations","volume":"92","author":"Cichocki","year":"2009","journal-title":"IEICE Trans. Fund. Electron. Commun. Comput. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Hsieh, C.J., and Dhillon, I.S. (2011, January 21\u201324). Fast coordinate descent methods with variable selection for non-negative matrix factorization. Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data-Mining, San Diego, CA, USA.","DOI":"10.1145\/2020408.2020577"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"735","DOI":"10.1016\/j.patrec.2019.07.026","article-title":"Efficient algorithm for sparse symmetric nonnegative matrix factorization","volume":"125","author":"Belachew","year":"2019","journal-title":"Pattern Recogn. Lett."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Kuang, D., Ding, C., and Park, H. (2012, January 26\u201328). Symmetric nonnegative matrix factorization for graph clustering. Proceedings of the 2012 SIAM International Conference on Data-Mining (SDM 2012), Anaheim, CA, USA.","DOI":"10.1137\/1.9781611972825.10"},{"key":"ref_10","first-page":"205","article-title":"LIBNMF\u2014A library for nonnegative matrix factorization","volume":"30","author":"Janecek","year":"2011","journal-title":"Comput. Inform."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"6348","DOI":"10.1109\/TNNLS.2018.2830761","article-title":"Pairwise constraint propagation-induced symmetric nonnegative matrix factorization","volume":"29","author":"Wu","year":"2018","journal-title":"IEEE Trans. Neural Netw. Learn. Syst."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Cichocki, A., Zdunek, R., Phan, A.H., and Amari, S. (2009). Nonnegative Matrix and Tensor Factorizations: Applications to Explanatory Multi-Way Data Analysis and Blind Source Separation, Wiley.","DOI":"10.1002\/9780470747278"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"3261","DOI":"10.1137\/110821172","article-title":"Fast nonnegative matrix factorization: An active-set-like method and comparisons","volume":"33","author":"Kim","year":"2011","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Favati, P., Lotti, G., Menchi, O., and Romani, F. (2019). Adaptive computation of the Symmetric Nonnegative Matrix Factorization (NMF). arXiv.","DOI":"10.3390\/a12100216"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1364","DOI":"10.1137\/070709967","article-title":"On the complexity of nonnegative matrix factorization","volume":"20","author":"Vavasis","year":"2009","journal-title":"SIAM J. Optim."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/S0167-6377(99)00074-7","article-title":"On the convergence of the block nonlinear Gauss-Seidel method under convex constraints","volume":"26","author":"Grippo","year":"2000","journal-title":"Oper. Res. Lett."},{"key":"ref_17","unstructured":"Lawson, C.L., and Hanson, R.J. (1974). Solving Least Squares Problems, Prentice-Hall."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rck, \u00c5. (1996). Numerical Methods for Least Squares Problems, SIAM.","DOI":"10.1137\/1.9781611971484"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Kim, H., and Park, H. (2008, January 15\u201319). Toward faster nonnegative matrix factorization: A new algorithm and comparisons. Proceedings of the 8th IEEE International Conference on Data-Mining (ICDM), Pisa, Italy.","DOI":"10.1109\/ICDM.2008.149"},{"key":"ref_20","unstructured":"Desgraupes, B. (2019, October 15). Clustering Indices. Available online: https:\/\/cran.r-project.org\/web\/packages\/clusterCrit\/vignettes\/clusterCrit.pdf."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1109\/TPAMI.1979.4766909","article-title":"A cluster separation measure","volume":"1","author":"Davis","year":"1979","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell. PAMI"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"2353","DOI":"10.1016\/j.patrec.2005.04.007","article-title":"New indices for cluster validity assessment","volume":"26","author":"Kim","year":"2005","journal-title":"Pattern Recogn. Lett."},{"key":"ref_23","unstructured":"(2019, October 15). NIST\/SEMATECH e-Handbook of Statistical Methods, Available online: http:\/\/www.itl.nist.gov\/div898\/handbook."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Favati, P., Lotti, G., Menchi, O., and Romani, F. (2019). An adaptive procedure for the global minimization of a class of polynomial functions. Algorithms, 12.","DOI":"10.3390\/a12050109"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Liu, Y., Li, Z., Xiong, H., Gao, X., and Wu, J. (2010, January 13\u201317). Understanding of internal clustering validation measures. Proceedings of the IEEE International Conference on Data-Mining, Sydney, Australia.","DOI":"10.1109\/ICDM.2010.35"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/10\/216\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:27:14Z","timestamp":1760189234000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/10\/216"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,17]]},"references-count":25,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2019,10]]}},"alternative-id":["a12100216"],"URL":"https:\/\/doi.org\/10.3390\/a12100216","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,10,17]]}}}