Christel Vrain

IJCAI Conference 2018 Conference Paper

Descriptive Clustering: ILP and CP Formulations with Applications

• Thi-Bich-Hanh Dao
• Chia-Tung Kuo
• S. S. Ravi
• Christel Vrain
• Ian Davidson

In many settings just finding a good clustering is insufficient and an explanation of the clustering is required. If the features used to perform the clustering are interpretable then methods such as conceptual clustering can be used. However, in many applications this is not the case particularly for image, graph and other complex data. Here we explore the setting where a set of interpretable discrete tags for each instance is available. We formulate the descriptive clustering problem as a bi-objective optimization to simultaneously find compact clusters using the features and to describe them using the tags. We present our formulation in a declarative platform and show it can be integrated into a standard iterative algorithm to find all Pareto optimal solutions to the two objectives. Preliminary results demonstrate the utility of our approach on real data sets for images and electronic health care records and that it outperforms single objective and multi-view clustering baselines.

AAAI Conference 2017 Conference Paper

A Framework for Minimal Clustering Modification via Constraint Programming

• Chia-Tung Kuo
• S. Ravi
• Thi-Bich-Hanh Dao
• Christel Vrain
• Ian Davidson

Consider the situation where your favorite clustering algorithm applied to a data set returns a good clustering but there are a few undesirable properties. One adhoc way to fix this is to re-run the clustering algorithm and hope to find a better variation. Instead, we propose to not run the algorithm again but minimally modify the existing clustering to remove the undesirable properties. We formulate the minimal clustering modification problem where we are given an initial clustering produced from any algorithm. The clustering is then modified to: i) remove the undesirable properties and ii) be minimally different to the given clustering. We show the underlying feasibility sub-problem can be intractable and demonstrate the flexibility of our constraint programming formulation. We empirically validate its usefulness through experiments on social network and medical imaging data sets.

AIJ Journal 2017 Journal Article

Constrained clustering by constraint programming

• Thi-Bich-Hanh Dao
• Khanh-Chuong Duong
• Christel Vrain

Constrained Clustering allows to make the clustering task more accurate by integrating user constraints, which can be instance-level or cluster-level constraints. Few works consider the integration of different kinds of constraints, they are usually based on declarative frameworks and they are often exact methods, which either enumerate all the solutions satisfying the user constraints, or find a global optimum when an optimization criterion is specified. In a previous work, we have proposed a model for Constrained Clustering based on a Constraint Programming framework. It is declarative, allowing a user to integrate user constraints and to choose an optimization criterion among several ones. In this article we present a new and substantially improved model for Constrained Clustering, still based on a Constraint Programming framework. It differs from our earlier model in the way partitions are represented by means of variables and constraints. It is also more flexible since the number of clusters does not need to be set beforehand; only a lower and an upper bound on the number of clusters have to be provided. In order to make the model-based approach more efficient, we propose new global optimization constraints with dedicated filtering algorithms. We show that such a framework can easily be embedded in a more general process and we illustrate this on the problem of finding the optimal Pareto front of a bi-criterion constrained clustering task. We compare our approach with existing exact approaches, based either on a branch-and-bound approach or on graph coloring on twelve datasets. Experiments show that the model outperforms exact approaches in most cases.

ECAI Conference 2016 Conference Paper

A Framework for Actionable Clustering Using Constraint Programming

• Thi-Bich-Hanh Dao
• Christel Vrain
• Khanh-Chuong Duong
• Ian Davidson

Consider if you wish to cluster your ego network in Facebook so as to find several useful groups each of which you can invite to a different dinner party. You may require that each cluster must contain equal number of males and females, that the width of a cluster in terms of age is at most 10 and that each person in a cluster should have at least r other people with the same hobby. These are examples of cardinality, geometric and density requirements/constraints respectfully that can make the clustering useful for a given purpose. However existing formulations of constrained clustering were not designed to handle these constraints since they typically deal with low-level, instance-level constraints. We formulate a constraint programming (CP) languages formulation of clustering with these cluster-level styles of constraints which we call actionable clustering. Experimental results show the potential uses of this work to make clustering more actionable. We also show that these constraints can be used to improve the accuracy of semi-supervised clustering.

ECAI Conference 2016 Conference Paper

Repetitive Branch-and-Bound Using Constraint Programming for Constrained Minimum Sum-of-Squares Clustering

• Tias Guns
• Thi-Bich-Hanh Dao
• Christel Vrain
• Khanh-Chuong Duong

Minimum sum-of-squares clustering (MSSC) is a widely studied task and numerous approximate as well as a number of exact algorithms have been developed for it. Recently the interest of integrating prior knowledge in data mining has been shown, and much attention has gone into incorporating user constraints into clustering algorithms in a generic way.

JMLR Journal 2013 Journal Article

QuantMiner for Mining Quantitative Association Rules

• Ansaf Salleb-Aouissi
• Christel Vrain
• Cyril Nortet
• Xiangrong Kong
• Vivek Rathod
• Daniel Cassard

In this paper, we propose QuantMiner, a mining quantitative association rules system. This system is based on a genetic algorithm that dynamically discovers “good” intervals in association rules by optimizing both the support and the confidence. The experiments on real and artificial databases have shown the usefulness of QuantMiner as an interactive, exploratory data mining tool. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2013. ( edit, beta )

IJCAI Conference 2011 Conference Paper

Generative Structure Learning for Markov Logic Networks Based on Graph of Predicates

• Quang-Thang Dinh
• Matthieu Exbrayat
• Christel Vrain

In this paper we present a new algorithm for generatively learning the structure of Markov Logic Networks. This algorithm relies on a graph of predicates, which summarizes the links existing between predicates and on relational information between ground atoms in the training database. Candidate clauses are produced by means of a heuristical variabilization technique. According to our first experiments, this approach appears to be promising.

IJCAI Conference 2007 Conference Paper

• Ansaf Salleb-Aouissi
• Christel Vrain
• Cyril Nortet

In this paper, we propose QuantMiner, a mining quantitative association rules system. This system is based on a genetic algorithm that dynamically discovers "good" intervals in association rules by optimizing both the support and the confidence. The experiments on real and artificial databases have shown the usefulness of QuantMiner as an interactive data mining tool. Keywords: Association rules, quantitative (numeric) attributes, unsupervised discretization, genetic algorithm

ECAI Conference 2004 Conference Paper

PoBOC: An Overlapping Clustering Algorithm, Application to Rule-Based Classification and Textual Data

• Guillaume Cleuziou
• Lionel Martin
• Christel Vrain

ECAI Conference 2002 Conference Paper

Mining maximal frequent itemsets by a boolean approach

• Ansaf Salleb
• Zahir Maazouzi
• Christel Vrain