Premium
A novel framework for detecting maximally banded matrices in binary data
Author(s) -
Alqadah Faris,
Bhatnagar Raj,
Jegga Anil
Publication year - 2010
Publication title -
statistical analysis and data mining: the asa data science journal
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.381
H-Index - 33
eISSN - 1932-1872
pISSN - 1932-1864
DOI - 10.1002/sam.10089
Subject(s) - row , diagonal , binary number , permutation (music) , computer science , logical matrix , block matrix , data mining , matrix (chemical analysis) , row and column spaces , data structure , block (permutation group theory) , theoretical computer science , algorithm , pattern recognition (psychology) , artificial intelligence , mathematics , combinatorics , group (periodic table) , database , chemistry , physics , geometry , organic chemistry , eigenvalues and eigenvectors , materials science , quantum mechanics , acoustics , composite material , arithmetic , programming language
Binary data occurs often in real‐world applications ranging from social networks to bioinformatics. As such, extracting patterns from binary data has been a fundamental task of data mining. Recently, the utility of banded structures in binary matrices has been pointed out for applications such as paleontology, bioinformatics, and social networking. A binary matrix has a banded structure if both the rows and columns can be permuted so that the 1s exhibit a staircase pattern down the rows, along the leading diagonal. Natural interpretations of banded structures include overlapping communities in social networks, patterns of species occurring in spatially correlated sites, and overlapping roles of genes in various diseases. In this paper, we show the correspondence between formal concept analysis and banded structure; as a direct result of this correspondence a novel framework for discovering banded structures is presented. Utilizing the framework, the MMBS algorithm (mine maximally banded submatrices) is developed. The current state‐of‐the‐art algorithm, MBS, only allows for the discovery of a single band and assumes a fixed‐column permutation. On the other hand, MMBS facilitates the discovery of multiple bands that may possibly be overlapping or segmented. Our experimental results, presented here, clearly indicate the advantage of MMBS over MBS with both, synthetic and real datasets. Copyright © 2010 Wiley Periodicals, Inc. Statistical Analysis and Data Mining 3: 431‐445, 2010