Pattern Discovery in High Dimensional Binary Data

High dimensional binary datasets arise in many areas of applications and pose significant challenges in data analysis. Pattern discovery is a key technique for analyzing these datasets. This paper presents algorithms for binary matrix factorization (BMF), which compresses large datasets into a much smaller set of dominant patterns for subsequent applications. 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. 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.