Mining Discrete Patterns via Binary Matrix Factorization

In general, binary matrix factorization (BMF) refers to the problem of finding two binary matrices of low rank such that the difference between their matrix product and a given binary matrix is minimal. BMF is an important tool in mining discrete patterns for high-dimensional data. One approximate matrix factor finds the dominant patterns, and the other shows how the original patterns are represented by the dominant ones. The problem of determining the exact optimal solution is NP-hard. We show that BMF is closely related with k-means clustering and propose a clustering approach for BMF. We prove that our approach has approximation ratio of 2. We further propose a randomized clustering algorithm that chooses k cluster centroids randomly based on preassigned probabilities to each point. The randomized clustering algorithm works well for large k. We experimentally demonstrate the nice theoretical properties of BMF on applications in pattern extraction and association rule mining.