caa a22 4500 605477876 CHVBK 20210128100403.0 cr unu---uuuuu 210128e20151001xx s 000 0 eng 10.1007/s10994-015-5487-y doi (NATIONALLICENCE)springer-10.1007/s10994-015-5487-y Triadic Formal Concept Analysis and triclustering: searching for optimal patterns [Elektronische Daten] [Dmitry Ignatov, Dmitry Gnatyshak, Sergei Kuznetsov, Boris Mirkin] This paper presents several definitions of "optimal patterns” in triadic data and results of experimental comparison offive triclustering algorithms onreal-world and synthetic datasets. The evaluation is carried over such criteria as resource efficiency, noise tolerance and quality scores involving cardinality, density, coverage, and diversity of the patterns. An ideal triadic pattern is a totally dense maximal cuboid (formal triconcept). Relaxations of this notion under consideration are: OAC-triclusters; triclusters optimal with respect to the least-square criterion; and graph partitions obtained by using spectral clustering. We show that searching for an optimal tricluster cover is an NP-complete problem, whereas determining the number of such covers is #P-complete. Our extensive computational experiments lead us to a clear strategy for choosing a solution at a given dataset guided by the principle of Pareto-optimality according to the proposed criteria. The Author(s), 2015 Formal Concept Analysis nationallicence Triclustering nationallicence Triadic data nationallicence Multi-way set nationallicence Tripartite graphs nationallicence Pattern mining nationallicence Suboptimal solutions nationallicence Ignatov Dmitry Department of Data Analysis and Artificial Intelligence, Computer Science Faculty, National Research University Higher School of Economics, Moscow, Russia aut Gnatyshak Dmitry Department of Data Analysis and Artificial Intelligence, Computer Science Faculty, National Research University Higher School of Economics, Moscow, Russia aut Kuznetsov Sergei Department of Data Analysis and Artificial Intelligence, Computer Science Faculty, National Research University Higher School of Economics, Moscow, Russia aut Mirkin Boris Department of Data Analysis and Artificial Intelligence, Computer Science Faculty, National Research University Higher School of Economics, Moscow, Russia aut Machine Learning Springer US; http://www.springer-ny.com 101/1-3(2015-10-01), 271-302 0885-6125 101:1-3<271 2015 101 10994 https://doi.org/10.1007/s10994-015-5487-y text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s10994-015-5487-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Ignatov Dmitry Department of Data Analysis and Artificial Intelligence, Computer Science Faculty, National Research University Higher School of Economics, Moscow, Russia aut NATIONALLICENCE 700 1- Gnatyshak Dmitry Department of Data Analysis and Artificial Intelligence, Computer Science Faculty, National Research University Higher School of Economics, Moscow, Russia aut NATIONALLICENCE 700 1- Kuznetsov Sergei Department of Data Analysis and Artificial Intelligence, Computer Science Faculty, National Research University Higher School of Economics, Moscow, Russia aut NATIONALLICENCE 700 1- Mirkin Boris Department of Data Analysis and Artificial Intelligence, Computer Science Faculty, National Research University Higher School of Economics, Moscow, Russia aut NATIONALLICENCE 773 0- Machine Learning Springer US; http://www.springer-ny.com 101/1-3(2015-10-01), 271-302 0885-6125 101:1-3<271 2015 101 10994