This thesis focuses on some data mining problems with an operations research point of view. Data mining is the process of learning new knowledge from large datasets. The problems in this field are close to the ones encountered in operations research: Large instances, complex objectives and algorithmic difficulty. Moreover, learning knowledge from a dataset can be viewed as a particular optimization problem with a partially known objective function. This thesis is divided into two main parts. The first part starts with an introduction to data mining. Then it presents a specific method from the field of discrete optimization known as Logical Analysis of Data (LAD). In this part, an original medical application and an extension of LAD to survival analysis are presented. Survival analysis is the modeling of time to event (typically death or failure). The proposed heuristics are derived from classical operations research methods such as integer programming, problem decomposition and greedy algorithms. The second part is more theoretical and focuses on two combinatorial problems encountered while solving practical data mining problems. The first one is a problem of graph partition into dense subgraphs for unsupervised learning. We emphasize the algorithmic complexity of this problem, and give a polynomial algorithm based on dynamic programming when the graph is a tree. This algorithm relies on famous combinatorial optimization results in matching theory. The second problem is a generalization of test cover for feature selection. The rows of a binary matrix are bicolored. The objective is to find a minimum subset of columns such that any pair of rows with different colors are still distinct when the matrix is restricted to the subset of columns. We give complexity results and tight bounds on the size of the optimal solutions for various matrix structures.
