Shifting Pattern Biclustering and Boolean Reasoning Symmetry

Abstract

There are several goals of the two-dimensional data analysis: one may be interested in searching for groups of similar objects (clustering), another one may be focused on searching for some dependencies between a specified one and other variables (classification, regression, associate rules induction), and finally, some may be interested in serching for well-defined patterns in the data called biclusters. It was already proved that there exists a mathematically proven symmetry between some patterns in the matrix and implicants of data-defined Boolean function. This paper provides the new look for a specific pattern search—the pattern named the δ-shifting pattern. The shifting pattern is interesting, as it accounts for constant fluctuations in data, i.e., it captures situations in which all the values in the pattern move up or down for one dimension, maintaining the range amplitude for all the dimensions. Such a behavior is very common in real data, e.g., in the analysis of gene expression data. In such a domain, a subset of genes might go up or down for a subset of patients or experimental conditions, identifying functionally coherent categories. A δ-shifting pattern meets the necessity of shifting pattern induction together with the bias of the real values acquisition where the original shifts may be disturbed with some outer conditions. Experiments with a real dataset show the potential of our approach at finding biclusters with δ-shifting patterns, providing excellent performance. It was possible to find the 12×9 pattern in the 112×9 input data with MSR=0.00653. The experiments also revealed that δ-shifting patterns are quite difficult to be found by some well-known methods of biclustering, as these are not designed to focus on shifting patterns—results comparable due to MSR had much more variability (in terms of δ) than patterns found with Boolean reasoning.

Keywords

• biclustering
• shifting patterns
• Boolean reasoning