Mining Non-Redundant High Order Correlations in Binary Data.

Area of Science:

• Computational Biology
• Data Mining
• Information Theory

Background:

• Traditional correlation methods often focus on pairwise relationships, which is insufficient for complex biological data.
• Identifying higher-order interactions among multiple features is essential for biological discovery.
• Ensuring non-redundancy in correlated feature sets is critical to avoid spurious findings.

Purpose of the Study:

• To develop a method for finding non-redundant, high-order correlations in binary data.
• To formalize these correlations using multi-information and identify Non-redundant Interacting Feature Subsets (NIFS).
• To create efficient algorithms for detecting NIFSs, addressing computational challenges.

Main Methods:

• Formalization of high-order correlations using multi-information, a generalization of pairwise mutual information.
• Definition and identification of Non-redundant Interacting Feature Subsets (NIFS), where subsets are weakly correlated.
• Development of efficient algorithms incorporating properties of NIFSs, bounds on correlations, and pruning strategies based on pairwise mutual information.

Main Results:

• Demonstrated the utility of NIFS properties for developing efficient algorithms.
• Introduced upper and lower bounds for correlation to effectively prune search spaces.
• Showcased the efficiency and effectiveness of the proposed approach through extensive experiments on synthetic and real-life datasets.

Conclusions:

• The proposed method effectively identifies non-redundant, high-order correlations in binary data.
• The developed algorithms offer an efficient solution to the computationally challenging problem of finding NIFSs.
• The approach is validated for its performance in biological and other data analysis applications.