We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Triadic Formal Concept Analysis and triclustering: searching for optimal patterns.
- Authors
Mirkin, Boris; Ignatov, Dmitry; Gnatyshak, Dmitry; Kuznetsov, Sergei
- Abstract
This paper presents several definitions of 'optimal patterns' in triadic data and results of experimental comparison of five triclustering algorithms on real-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.
- Subjects
CLUSTER analysis (Statistics); SEQUENTIAL pattern mining; ALGORITHMS; DENSITY; NP-complete problems; LEAST squares; MACHINE learning; LAPLACIAN matrices
- Publication
Machine Learning, 2015, Vol 101, Issue 1-3, p271
- ISSN
0885-6125
- Publication type
Article
- DOI
10.1007/s10994-015-5487-y