This paper presents a novel enumerative biclustering algorithm to directly mine all maximal biclusters in mixed-attribute datasets (containing both numerical and categorical attributes), with or without missing values. The proposal is an extension of RIn-Close_CVC, which was originally conceived to mine perfect or perturbed biclusters with constant values on columns solely from numerical datasets, and without missing values. Even endowed with additional and more general features, the extended RIn-Close_CVC retains four key properties: (1) efficiency, (2) completeness, (3) correctness, and (4) non-redundancy. Our proposal is the first one to deal with mixed-attribute datasets without requiring any pre-processing step, such as discretization and itemization of real-valued attributes. This is a decisive aspect, because discretization and itemization implies a priori decisions, with information loss and no clear control over the consequences. On the other hand, even having to specify a priori an individual threshold for each numerical attribute, that will be used to indicate internal consistency per attribute, each threshold will be applied during the construction of the biclusters, shaping the peculiarities of the data distribution. We also explore the strong connection between biclustering and frequent pattern mining to (1) provide filters to select a compact bicluster set that exhibits high relevance and low redundancy, and (2) in the case of labeled datasets, automatically present the biclusters in a user-friendly and intuitive form, by means of quantitative class association rules. Our experimental results showed that the biclusters yield a parsimonious set of relevant rules, providing useful and interpretable models for five mixed-attribute labeled datasets.
BicPAM is a framework that relies on 3 steps: pre-processing (which includes normalization, discretization, itemization, handling of missing values, and tackling varying levels of noise), mining (where some FPM algorithm is used to mine the biclusters), and post-processing (in which the biclusters can be extended, merged and filtered out, among other possibilities). BicPAM makes available three discretization options (each one with key implications on the target solution), and the user can easily incorporate other options into the framework. BicPAM also makes available several FPM algorithms in the mining step, and the user can also incorporate others. To alleviate common drawbacks related to discretization procedures (such as information loss), the user can choose to assign multiple items over a single element, tackling the items-boundary problem. The drawback of this strategy is that it usually generates many redundant biclusters (even when using algorithms to mine closed frequent itemsets), guiding to extra computational cost, and the information loss is still present, though attenuated. For more contributions regarding biclustering based on FPM algorithms, see the survey of Henriques @cite_3 .
@cite_3
2195615921 2116396873 1977580401 2100038249
Mining matrices to find relevant biclusters, subsets of rows exhibiting a coherent pattern over a subset of columns, is a critical task for a wide-set of biomedical and social applications. Since biclustering is a challenging combinatorial optimization task, existing approaches place restrictions on the allowed structure, coherence and quality of biclusters. Biclustering approaches relying on pattern mining (PM) allow an exhaustive yet efficient space exploration together with the possibility to discover flexible structures of biclusters with parameterizable coherency and noise-tolerance. Still, state-of-the-art contributions are dispersed and the potential of their integration remains unclear.This work proposes a structured and integrated view of the contributions of state-of-the-art PM-based biclustering approaches, makes available a set of principles for a guided definition of new PM-based biclustering approaches, and discusses their relevance for applications in pattern recognition. Empirical evidence shows that these principles guarantee the robustness, efficiency and flexibility of PM-based biclustering. HighlightsPattern mining (PM) searches enable flexible, exhaustive and efficient biclusteringIntegration of existing dispersed PM-inspired contributions for biclustering.Principles for guided design and evaluation of new PM-based biclustering approachesPM-based biclustering solutions have parameterizable coherency and quality. The application of frequent patterns in classification has demonstrated its power in recent studies. It often adopts a two-step approach: frequent pattern (or classification rule) mining followed by feature selection (or rule ranking). However, this two-step process could be computationally expensive, especially when the problem scale is large or the minimum support is low. It was observed that frequent pattern mining usually produces a huge number of "patterns" that could not only slow down the mining process but also make feature selection hard to complete. In this paper, we propose a direct discriminative pattern mining approach, DDPMine, to tackle the efficiency issue arising from the two-step approach. DDPMine performs a branch-and-bound search for directly mining discriminative patterns without generating the complete pattern set. Instead of selecting best patterns in a batch, we introduce a "feature-centered" mining approach that generates discriminative patterns sequentially on a progressively shrinking FP-tree by incrementally eliminating training instances. The instance elimination effectively reduces the problem size iteratively and expedites the mining process. Empirical results show that DDPMine achieves orders of magnitude speedup without any downgrade of classification accuracy. It outperforms the state-of-the-art associative classification methods in terms of both accuracy and efficiency. Recovering low-rank and sparse matrices from incomplete or corrupted observations is an important problem in statistics, machine learning, computer vision, as well as signal and image processing. In theory, this problem can be solved by the natural convex joint mixed relaxations (i.e., l 1 -norm and trace norm) under certain conditions. However, all current provable algorithms suffer from superlinear per-iteration cost, which severely limits their applicability to large-scale problems. In this paper, we propose a scalable, provable and structured robust bilinear factorization (RBF) method to recover low-rank and sparse matrices from missing and grossly corrupted data, i.e., robust matrix completion (RMC), or incomplete and grossly corrupted measurements, i.e., compressive principal component pursuit (CPCP). Specifically, we first present two small-scale matrix trace norm regularized bilinear factorization models for RMC and CPCP problems, in which repetitively calculating SVD of a large-scale matrix is replaced by updating two much smaller factor matrices. Then, we apply the alternating direction method of multipliers (ADMM) to efficiently solve the RMC problems. Finally, we provide the convergence analysis of our algorithm, and extend it to address general CPCP problems. Experimental results verified both the efficiency and effectiveness of our method compared with the state-of-the-art methods. The discovery of biclusters, which denote groups of items that show coherent values across a subset of all the transactions in a data set, is an important type of analysis performed on real-valued data sets in various domains, such as biology. Several algorithms have been proposed to find different types of biclusters in such data sets. However, these algorithms are unable to search the space of all possible biclusters exhaustively. Pattern mining algorithms in association analysis also essentially produce biclusters as their result, since the patterns consist of items that are supported by a subset of all the transactions. However, a major limitation of the numerous techniques developed in association analysis is that they are only able to analyze data sets with binary and or categorical variables, and their application to real-valued data sets often involves some lossy transformation such as discretization or binarization of the attributes. In this paper, we propose a novel association analysis framework for exhaustively and efficiently mining "range support" patterns from such a data set. On one hand, this framework reduces the loss of information incurred by the binarization- and discretization-based approaches, and on the other, it enables the exhaustive discovery of coherent biclusters. We compared the performance of our framework with two standard biclustering algorithms through the evaluation of the similarity of the cellular functions of the genes constituting the patterns biclusters derived by these algorithms from microarray data. These experiments show that the real-valued patterns discovered by our framework are better enriched by small biologically interesting functional classes. Also, through specific examples, we demonstrate the ability of the RAP framework to discover functionally enriched patterns that are not found by the commonly used biclustering algorithm ISA. The source code and data sets used in this paper, as well as the supplementary material, are available at http: www.cs.umn.edu vk gaurav rap.