International audience

Exploratory Data Analysis (EDA) is the interactive process of gaining insights from a dataset. Comparisons are popular insights that can be specified with comparison queries, i.e., specifications of the comparison of subsets of data. In this work, we consider the problem of automatically computing sequences of comparison queries that are coherent, significant and whose overall cost is bounded. Such an automation is usually done by either generating all insights and solving a multi-criteria optimization problem, or using reinforcement learning. In the first case, a large search space has to be explored using exponential algorithms or dedicated heuristics. In the second case, a dataset-specific, time and energy-consuming training, is necessary. We contribute with a novel approach, consisting of decomposing the optimization problem in two: the original problem, that is solved over a smaller search space, and a new problem of generating comparison queries, aiming at generating only queries improving existing solutions of the first problem. This allows to explore only a portion of the search space, without resorting to reinforcement learning. We show that this approach is effective, in that it finds good solutions to the original multi-criteria optimization problem, and efficient, allowing to generate sequences of comparisons in reasonable time.

International audience

Evolutionary Algorithms have been regularly used for solving multi and many objectives optimization problems. The effectiveness of such methods is determined generally by their ability to generate a well-distributed front (diversity) that is as close as possible to the optimal Pareto front (proximity). Analysis of current multi-objective evolutionary frameworks shows that they are still sub-optimal and present poor versatility on different geometries and dimensionalities. For that, in this paper, we present AGE-MOEA++, a new Multi and Many Objective Evolutionary Algorithm that: (1) incorporates the principle of Pareto Front (PF) shape fitting to enhance the convergence in different shaped high dimensional objective spaces, and (2) adapts K-means ++ fundamentals in order to best manage the diversity in non-uniform distributed PF. The empirical study shows that our proposal has better results than the state-of-the-art approaches in terms of IGD and is competitive in terms of GD.

This paper deals with the Campaign Allocation Problem of commercial Ads in TV breaks that we formalize as a multi-stakeholders multiobjective problem with highly competing objectives for different brands and numerous constraints. The problem is NP-hard with a high dimensional objective space and scalability issues in terms of the number of breaks. Moreover, the expected solution should be able to focus on a sub-part of the Pareto front according to decision maker’s (DM) knowledge. To tackle these challenges, we propose to use R-NSGA-II, a Many-Objective Evolutionary Algorithm (MaOEA), combined with a novel gene encoding/decoding process. Experiments show that this approach obtains better results than usual MaOEA (NSGA-II, NSGA-III) according to industrial performance criteria, scales to large instances, and incorporates decision maker’s preferences during the optimization process.

This paper describes a new semi-supervised clustering algorithm as part of a more general framework of interactive exploratory clustering, that favors the exploration of possible clustering solutions so that an expert tailors the best clustering according to her domain knowledge and preferences. Co ntrary to most existing approaches, the novel algorithm considers the feature space as a first class citizen for the exploration of alternative solutions. Our proposal represents and integrates quantitative preferences on attributes that will guide the exploration of possible solutions by learning an appropriate space metric. It also achieves a compromise clustering based on expert confidence, between a data-driven and a user-driven solution and converges with a good complexity. We show experimentally that our method is also able to deal with irrelevant user preferences and correct those choices in order to achieve a better solution. Experiments show that the best results may be achieved only with the addition of preferences to traditional metric learning algorithms and that our approach performs better than state-of-the-art algorithms.

Active learning for semi-supervised clustering allows algorithms to solicit a domain expert to provide side information as instances constraints, for example a set of labeled instances called seeds. The problem consists in selecting the queries to the expert that are likely to improve either the re levance or the quality of the proposed clustering. However, these active methods suffer from several limitations: (i) they are generally tailored for only one specific clustering paradigm or cluster shape and size, (ii) they may be counter-productive if the seeds are not selected in an appropriate manner and, (iii) they have to work efficiently with minimal expert supervision. In this paper, we propose a new active seed selection algorithm that relies on a k-nearest neighbors structure to locate dense potential clusters and efficiently query and propagate expert information. Our approach makes no hypothesis about the underlying data distribution and can be paired with any clustering algorithm. Comparative experiments conducted on real data sets show the efficiency of this new approach compared to existing ones.

This paper proposes a new semi-supervised clustering framework to represent and integrate quantitative preferences on attributes. A new metric learning algorithm is derived that achieves a compromise clustering between a data-driven and a user-driven solution and converges with a good complexity. We observe experimentally that the addition of preferences may be essential to achieve a better clustering. We also show that our approach performs better than the state-of-the art algorithms.

The objective of any tutoring system is to provide resources to learners that are adapted to their current state of knowledge. With the availability of a large variety of online content and the disjunctive nature of results provided by traditional search engines, it becomes crucial to provide learners with adapted learning paths that propose a sequence of resources that match their learning objectives. In an ideal case, the sequence of documents provided to the learner should be such that each new document relies on concepts that have been already defined in previous documents. Thus, the problem of determining an effective learning path from a corpus of web documents depends on the accurate identification of outcome and prerequisite concepts in these documents and on their ordering according to this information. Until now, only a few works have been proposed to distinguish between prerequisite and outcome concepts, and to the best of our knowledge, no method has been introduced so far to benefit from this information to produce a meaningful learning path. To this aim, this article first describes a concept annotation method that relies on machine-learning techniques to predict the class of each concept—prerequisite or outcome—on the basis of contextual and local features. Then, this categorization is exploited to produce an automatic resource sequencing on the basis of different representations and scoring functions that transcribe the precedence relation between learning resources. Experiments conducted on a real dataset built from online resources show that our concept annotation approach outperforms the baseline method and that the learning paths automatically generated are consistent with the ground truth provided by the author of the online content.

This paper introduces a racing mechanism in the cluster selection process for one-pass clustering algorithms. We focus on cases where data are not numerical vectors and where it is not necessarily possible to compute a mean for each cluster. In this case, the distance of each point to existing clusters can be computed exhaustively with a quadratic complexity which is not tractable in most of nowadays use cases. In this paper we first introduce a stochastic approach for estimating the distance of each new data point to existing clusters based on Hoeffding and Bernstein bounds, that reduces the number of computations by simultaneously selecting the quantity of data to be sampled and by eliminating the non-competitive clusters. Second, this paper shows that it is possible to improve the efficiency of our approach by reducing the theoretical values of the Hoeffding and Bernstein bounds. Our algorithms, tested on real data sets, provide significant acceleration of the one-pass clustering algorithms, while making less error (or any depending on parameters) than one-pass clustering algorithm with fixed number of comparisons with each cluster.

The objective of any tutoring system is to provide meaningful learning to the learner, thence it is important to know whether a concept mentioned in a document is a prerequisite for studying that document, or it can be learned from it. In this paper, we study the problem of identifying defined concepts and prerequisite concepts from learning resources available on the web. Statistics and machine learning tools are exploited in order to predict the class of each concept. Two groups of features are constructed to categorize the concepts: contextual features and local features. The contextual features enclose linguistic information and the local features contain the concept properties such as font size and font weigh. An aggregation method is proposed as a solution to the problem of the multiple occurrences of a defined concept in a document. This paper shows that best results are obtained with the SVM classifier than with other classifiers.

In this paper, we address the problem of active query selection for clustering with constraints. The objective is to determine automatically a set of queries and their associated must-link and can-not link constraints to help constraints based clustering algorithms to converge. Some works on active constraints learning have already been proposed but they are only applied to K-Means like clustering algorithms which are known to be limited to spherical clusters while we are interested in constraints-based clustering algorithms that deals with clusters of arbitrary shapes and sizes (like Constrained-DBSCAN, Constrained-Hierarchical Clustering. . . ). Our novel approach relies on a k-nearest neighbors graph to estimate the dense regions of the data space and generates queries at the frontier between clusters where the cluster membership is most uncertain. Experiments show that our framework improves the performance of constraints based clustering algorithms.

K-Means algorithm is one of the most used clustering algorithm for Knowledge Discovery in Data Mining. Seed based K-Means is the integration of a small set of labeled data (called seeds) to the K-Means algorithm to improve its performances and overcome its sensitivity to initial centers. These centers are, most of the time, generated at random or they are assumed to be available for each cluster. This paper introduces a new efficient algorithm for active seeds selection which relies on a Min-Max approach that favors the coverage of the whole dataset. Experiments conducted on artificial and real datasets show that, using our active seeds selection algorithm, each cluster contains at least one seed after a very small number of queries and thus helps reducing the number of iterations until convergence which is crucial in many KDD applications.

The objective of any tutoring system is to provide a meaningful learning to the learner. Therefore an automated tutoring system should be able to know whether a concept mentioned in a document is a prerequisite for studying that document, or it can be learned from it. This paper addresses the problem of identifying defined concepts and prerequisite concepts from learning resources in html format. In this paper a supervised machine learning approach was taken to address the problem, based on linguistic features which enclose contextual information and stylistic features such as font size and font weight. This paper shows that contextual information in addition to format information can give better results when used with the SVM classifier than with the (LP)2algorithm.

This paper introduces a new tool for web usage mining and visualization that relies on the bio-mimetic relational clustering algorithm Leader Ant and the definition of prototypes based on typicality computation to produce an efficient visualization of the activity of users on a website. The tool is evaluated on a real web log file from the French museum of Bourges website and shows that it can easily produce meaningful visualizations of typical user navigation.