BROCCOLI: overlapping and outlier-robust biclustering through proximal stochastic gradient descent. (English) Zbl 1491.62047

Summary: Matrix tri-factorization subject to binary constraints is a versatile and powerful framework for the simultaneous clustering of observations and features, also known as biclustering. Applications for biclustering encompass the clustering of high-dimensional data and explorative data mining, where the selection of the most important features is relevant. Unfortunately, due to the lack of suitable methods for the optimization subject to binary constraints, the powerful framework of biclustering is typically constrained to clusterings which partition the set of observations or features. As a result, overlap between clusters cannot be modelled and every item, even outliers in the data, have to be assigned to exactly one cluster. In this paper we propose Broccoli, an optimization scheme for matrix factorization subject to binary constraints, which is based on the theoretically well-founded optimization scheme of proximal stochastic gradient descent. Thereby, we do not impose any restrictions on the obtained clusters. Our experimental evaluation, performed on both synthetic and real-world data, and against 6 competitor algorithms, show reliable and competitive performance, even in presence of a high amount of noise in the data. Moreover, a qualitative analysis of the identified clusters shows that Broccoli may provide meaningful and interpretable clustering structures.


62H30 Classification and discrimination; cluster analysis (statistical aspects)
Full Text: DOI


[1] Asteris M, Papailiopoulos D, Dimakis AG (2015) Orthogonal NMF through subspace exploration. In: Advances in neural information processing systems, pp 343-351
[2] Barracchia EP, Pio G, D’Elia D, Ceci M (2020) Prediction of new associations between NCRNAS and diseases exploiting multi-type hierarchical clustering. BMC Bioinform 21(1):70
[3] Bauckhage C (2015) K-means clustering is matrix factorization. arXiv preprint arXiv:1512.07548
[4] Bolte, J.; Sabach, S.; Teboulle, M., Proximal alternating linearized minimization or nonconvex and nonsmooth problems, Math Program, 146, 1-2, 459-494 (2014) · Zbl 1297.90125
[5] Boutell, MR; Luo, J.; Shen, X.; Brown, CM, Learning multi-label scene classification, Pattern Recogn, 37, 9, 1757-1771 (2004)
[6] Briggs F, Huang Y, Raich R, Eftaxias K, Lei Z, Cukierski W, Hadley SF, Hadley A, Betts M, Fern XZ et al (2013) New methods for acoustic classification of multiple simultaneous bird species in a noisy environment. In: 2013 IEEE international workshop on machine learning for signal processing (MLSP), pp 1-8
[7] Cai, D.; He, X.; Han, J.; Huang, TS, Graph regularized nonnegative matrix factorization for data representation, IEEE Trans Pattern Anal Mach Intell, 33, 8, 1548-1560 (2011)
[8] Cheng Y, Church GM (2000) Biclustering of expression data. In: Proceedings of the eighth international conference on intelligent systems for molecular biology, vol 8, pp 93-103
[9] Cho H, Dhillon IS, Guan Y, Sra S (2004) Minimum sum-squared residue co-clustering of gene expression data. In: Proceedings of the SIAM international conference on data mining (SDM), pp 114-125
[10] Del Buono, N.; Pio, G., Non-negative matrix tri-factorization for co-clustering: an analysis of the block matrix, Inf Sci, 301, 13-26 (2015)
[11] Dhillon IS (2001) Co-clustering documents and words using bipartite spectral graph partitioning. In: Proceedings of the ACM SIGKDD international conference on knowledge discovery and data mining (KDD), pp 269-274
[12] Ding, C.; Li, T.; Peng, W., Nonnegative matrix factorization and probabilistic latent semantic indexing: equivalence chi-square statistic, and a hybrid method, AAAI, 42, 137-143 (2006)
[13] Ding C, Li T, Peng W, Park H (2006b) Orthogonal nonnegative matrix t-factorizations for clustering. In: Proceedings of the ACM SIGKDD international conference on knowledge discovery and data mining (KDD), pp 126-135
[14] Diplaris S, Tsoumakas G, Mitkas PA, Vlahavas I (2005) Protein classification with multiple algorithms. In: Panhellenic conference on informatics, pp 448-456
[15] Driggs D, Tang J, Davies M, Schönlieb CB (2020) Spring: a fast stochastic proximal alternating method for non-smooth non-convex optimization. arXiv preprint arXiv:2002.12266
[16] Elisseeff A, Weston J (2002) A kernel method for multi-labelled classification. In: Advances in neural information processing systems, pp 681-687
[17] Gaul W, Schader M (1996) A new algorithm for two-mode clustering. In: Data analysis and information systems. Springer, pp 15-23 · Zbl 0896.62060
[18] Han J, Song K, Nie F, Li X (2017) Bilateral k-means algorithm for fast co-clustering. In: AAAI, pp 1969-1975
[19] Hardt M, Recht B, Singer Y (2016) Train faster, generalize better: stability of stochastic gradient descent. In: Proceedings of the international conference on machine learning (ICML), pp 1225-1234
[20] Hartigan, JA, Direct clustering of a data matrix, J Am Stat Assoc, 67, 337, 123-129 (1972)
[21] Hess, S.; Morik, K.; Piatkowski, N., The PRIMPING routine—tiling through proximal alternating linearized minimization, Data Min Knowl Discovery (DAMI), 31, 4, 1090-1131 (2017) · Zbl 1409.68233
[22] Hochreiter, S.; Bodenhofer, U.; Heusel, M.; Mayr, A.; Mitterecker, A.; Kasim, A.; Khamiakova, T.; Van Sanden, S.; Lin, D.; Talloen, W.; Bijnens, L.; Göhlmann, H.; Shkedy, Z.; Clevert, DA, Fabia: factor analysis for bicluster acquisition, Bioinformatics (Oxford, England), 26, 1520-7 (2010)
[23] Hoffer E, Hubara I, Soudry D (2017) Train longer, generalize better: closing the generalization gap in large batch training of neural networks. In: Advances in neural information processing systems (NIPS), pp 1731-1741
[24] Kluger, Y., Spectral biclustering of microarray data: coclustering genes and conditions, Genome Res, 13, 4, 703-716 (2003)
[25] Koyutürk M, Grama A (2003) PROXIMUS: a framework for analyzing very high dimensional discrete-attributed datasets. In: Proceedings of the ACM SIGKDD international conference on knowledge discovery and data mining (KDD), pp 147-156
[26] Laclau, C.; Brault, V., Noise-free latent block model for high dimensional data, Data Min Knowl Discovery (DAMI), 33, 2, 446-473 (2019) · Zbl 1458.68171
[27] Li T (2005) A general model for clustering binary data. In: Proceedings of the ACM SIGKDD international conference on knowledge discovery in data mining (KDD), pp 188-197
[28] Lloyd, S., Least squares quantization in PCM, IEEE Trans Inf Theory, 28, 2, 129-137 (1982) · Zbl 0504.94015
[29] Long B, Zhang ZM, Yu PS (2005) Co-clustering by block value decomposition, vol ’05. Association for Computing Machinery, New York, NY, USA, KDD, pp 635-640
[30] Mirkin, B.; Arabie, P.; Hubert, LJ, Additive two-mode clustering: the error-variance approach revisited, J Classif, 12, 2, 243-263 (1995) · Zbl 0850.62475
[31] Nie F, Wang X, Deng C, Huang H (2017) Learning a structured optimal bipartite graph for co-clustering. In: Advances in neural information processing systems (NIPS), pp 4129-4138
[32] Parikh, N.; Boyd, S., Proximal algorithms, Found Trends Optim, 1, 3, 127-239 (2014)
[33] Pio G, Ceci M, Loglisci C, D’Elia D, Malerba D (2012) Hierarchical and overlapping co-clustering of MRNA: MIRNA interactions. In: ECAI 2012, IOS Press, frontiers in artificial intelligence and applications, vol 242, pp 654-659
[34] Pio G, Ceci M, D’Elia D, Loglisci C, Malerba D (2013) A novel biclustering algorithm for the discovery of meaningful biological correlations between micrornas and their target genes. BMC Bioinform 14(S-7):S8
[35] Pio G, Ceci M, Malerba D, D’Elia D (2015) Comirnet: a web-based system for the analysis of MIRNA-gene regulatory networks. BMC Bioinform 16(S-9):S7
[36] Pompili, F.; Gillis, N.; Absil, PA; Glineur, F., Two algorithms for orthogonal nonnegative matrix factorization with application to clustering, Neurocomputing, 141, 15-25 (2014)
[37] Rabbany, R.; Zaïane, OR, Generalization of clustering agreements and distances for overlapping clusters and network communities, Data Min Knowl Disc, 29, 5, 1458-1485 (2015) · Zbl 1405.62084
[38] Song, K.; Yao, X.; Nie, F.; Li, X.; Xu, M., Weighted bilateral k-means algorithm for fast co-clustering and fast spectral clustering, Pattern Recognit, 109, 107560 (2020)
[39] Trohidis, K.; Tsoumakas, G.; Kalliris, G.; Vlahavas, IP, Multi-label classification of music into emotions, ISMIR, 8, 325-330 (2008)
[40] Vichi M (2001) Double k-means clustering for simultaneous classification of objects and variables. In: Advances in classification and data analysis, pp 43-52
[41] Wang H, Nie F, Huang H, Makedon F (2011) Fast nonnegative matrix tri-factorization for large-scale data co-clustering. In: Proceedings of the international joint conference on artificial intelligence (IJCAI), p 1553
[42] Wang, J.; Tian, F.; Yu, H.; Liu, CH; Zhan, K.; Wang, X., Diverse non-negative matrix factorization for multiview data representation, IEEE Trans. Cybern., 48, 9, 2620-2632 (2018)
[43] Whang JJ, Dhillon IS (2017) Non-exhaustive, overlapping co-clustering. In: Proceedings of the ACM conference on information and knowledge management (CIKM), pp 2367-2370
[44] Yang, J.; Wang, H.; Wang, W.; Yu, P., An improved biclustering method for analyzing gene expression profiles, Int J Artif Intell Tools, 14, 771-790 (2005)
[45] Yokota T, Kawai K, Sakata M, Kimura Y, Hontani H (2019) Dynamic pet image reconstruction using nonnegative matrix factorization incorporated with deep image prior. In: Proceedings of the IEEE/CVF international conference on computer vision (ICCV)
[46] Yoo, J.; Choi, S., Orthogonal nonnegative matrix tri-factorization for co-clustering: multiplicative updates on Stiefel manifolds, Inf Process Manag, 46, 5, 559-570 (2010)
[47] Zha H, He X, Ding C, Simon H, Gu M (2001) Bipartite graph partitioning and data clustering. In: Proceedings of the international conference on information and knowledge management, pp 25-32
[48] Zhang Z, Li T, Ding C, Zhang X (2007) Binary matrix factorization with applications. In: IEEE International conference on data mining (ICDM), pp 391-400
[49] Zhang, ZY; Li, T.; Ding, C.; Ren, XW; Zhang, XS, Binary matrix factorization for analyzing gene expression data, Data Min. Knowl. Discov (DAMI), 20, 1, 28 (2010)
[50] Zhang, ZY; Wang, Y.; Ahn, YY, Overlapping community detection in complex networks using symmetric binary matrix factorization, Phys Rev E, 87, 6, 062803 (2013)
[51] Zhou J, Qi J (2011) Fast iterative image reconstruction using sparse matrix factorization with GPU acceleration. In: Progress in biomedical optics and imaging—proceedings of SPIE 7961
[52] Zhou X, Leonardos S, Hu X, Daniilidis K (2015) 3d shape estimation from 2d landmarks: A convex relaxation approach. In: proceedings of the IEEE conference on computer vision and pattern recognition, pp 4447-4455
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.