Name
Abstract | ||
|---|---|---|
Matrix decomposition methods represent a data matrix as a product of two factor matrices: one containing basis vectors that represent meaningful concepts in the data, and another describing how the observed data can be expressed as combinations of the basis vectors. Decomposition methods have been studied extensively, but many methods return real-valued matrices. Interpreting real-valued factor matrices is hard if the original data is Boolean. In this paper, we describe a matrix decomposition formulation for Boolean data, the Discrete Basis Problem. The problem seeks for a Boolean decomposition of a binary matrix, thus allowing the user to easily interpret the basis vectors. We also describe a variation of the problem, the Discrete Basis Partitioning Problem. We show that both problems are NP-hard. For the Discrete Basis Problem, we give a simple greedy algorithm for solving it; for the Discrete Basis Partitioning Problem we show how it can be solved using existing methods. We present experimental results for the greedy algorithm and compare it against other, well known methods. Our algorithm gives intuitive basis vectors, but its reconstruction error is usually larger than with the real-valued methods. We discuss about the reasons for this behavior. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1109/TKDE.2008.53 | Principles of Data Mining and Knowledge Discovery |
Keywords | Field | DocType |
binary matrix,original data,boolean data,discrete basis partitioning problem,observed data,decomposition method,boolean decomposition,discrete basis problem,basis vector,data matrix,greedy algorithm | Singular value decomposition,Logical matrix,Change of basis,Computer science,Matrix (mathematics),Matrix decomposition,Algorithm,Basis function,Matrix multiplication,LU decomposition | Journal |
Volume | Issue | ISSN |
20 | 10 | 1041-4347 |
ISBN | Citations | PageRank |
3-540-45374-1 | 61 | 3.60 |
References | Authors | |
35 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pauli Miettinen | 1 | 260 | 22.26 |
| Taneli Mielikäinen | 2 | 759 | 39.97 |
| Aristides Gionis | 3 | 6808 | 386.81 |
| Gautam Das | 4 | 4083 | 335.74 |
| Heikki Mannila | 5 | 6595 | 1495.69 |