We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Ternary Matrix Factorization: problem definitions and algorithms.
- Authors
Maurus, Samuel; Plant, Claudia
- Abstract
Can we learn from the unknown? Logical data sets of the ternary kind are often found in information systems. They contain unknown as well as true/ false values. An unknown value may represent a missing entry (lost or indeterminable) or have meaning, like a Don't Know response in a questionnaire. In this paper, we introduce algorithms for reducing the dimensionality of logical data (categorical data in general) in the context of a new data mining challenge: Ternary Matrix Factorization (TMF). For a ternary data matrix, TMF exploits ternary logic to produce a basis matrix (which holds the major patterns in the data) and a usage matrix (which maps patterns to original observations). Both matrices are interpretable, and their ternary matrix product approximates the original matrix. TMF has applications in (1) finding targeted structure in ternary data, (2) imputing values through pattern discovery in highly incomplete categorical data sets, and (3) solving instances of its encapsulated Binary Matrix Factorization problem. Our elegant algorithm FasTer (FASt TERnary Matrix Factorization) has linear run-time complexity with respect to the dimensions of the data set and is parameter-robust. A variant of FasTer that exploits useful results from combinatorics provides accuracy bounds for a core part of the algorithm in certain situations. Experiments on synthetic and real-world data sets show that our algorithms are able to outperform state-of-the-art techniques in all three TMF applications with respect to run-time and effectiveness. Finally, convincing speedup and efficiency results on a parallel version of FasTer demonstrate its suitability for weak- and strong-scaling scenarios.
- Subjects
FACTORIZATION; MATHEMATICS; QUANTUM mechanics; TERNARY logic; MANY-valued logic
- Publication
Knowledge & Information Systems, 2016, Vol 46, Issue 1, p1
- ISSN
0219-1377
- Publication type
Article
- DOI
10.1007/s10115-015-0838-3