Search

We introduce the exactCover global constraint dedicated to the exact cover problem, the goal of which is to select subsets such that each element of a given set belongs to exactly one selected subset. This NP-complete problem occurs in many applications, and we more particularly focus on a conceptual clustering application. We introduce three propagation algorithms for exactCover, called Basic, DL, and DL+: Basic ensures the same level of consistency as arc consistency on a classical decomposition of exactCover into binary constraints, without using any specific data structure; DL ensures the same level of consistency as Basic but uses Dancing Links to efficiently maintain the relation between elements and subsets; and DL+ is a stronger propagator which exploits an extra property to filter more values than DL. We also consider the case where the number of selected subsets is constrained to be equal to a given integer variable k, and we show that this may be achieved either by combining exactCover with existing constraints, or by designing a specific propagator that integrates algorithms designed for the NValues constraint. These different propagators are experimentally evaluated on conceptual clustering problems, and they are compared with state-of-the-art declarative approaches. In particular, we show that our global constraint is competitive with recent ILP and CP models for mono-criterion problems, and it has better scale-up properties for multi-criteria problems.

Due to the weak academic advising systems in most schools, students need assistance to explore universities/colleges and study fields that match their interests and future careers. Unfortunately, the orientation programs in most schools are not well designed to cater to students' varied needs. While career orientation programs are much needed at schools, a large number of Lebanese schools have not integrated such programs in their educational systems yet. Thus, this research focuses on developing a hybrid recommender system based on machine learning techniques. Our research focuses on the implementation of the formal concept analysis (FCA) to study university graduates' trajectories. This data mining technique is applied in knowledge presentation and data processing. FCA enables the discovery of hidden knowledge by using association rule mining and machine learning. The objective of this study is to discover the university graduates' trajectories and demonstrate the effectiveness of the FCA technique in data clustering.

International audience; Classification systems are used more and more often in artificial intelligence, especially to analyze texts and to extract knowledge they contain. The results of general clustering methods, though, are viewed too often being an absolute reference for classifying terms. This paper's goal is to evaluate quantitatively the quality of classification. Various tools are compared with relation to the same reference medical corpus. We analyze various methods such as hierarchical clustering, neural network, partitioning, co-word analysis which occur in different software systems. The evaluation method used is based on the comparison between a conceptual classfication taken as a reference, and the resulting classifications. This reference classification was realized with the help of a medical expert. It is an handmade classification according the real-world.

Enterprise Resource Planning (ERP) systems are essential for industrial companies to automatize and monitor their business processes in order to boost their competitiveness. ERP systems are generic software designed to serve a large variety of companies with different business processes. Therefore, they have many configuration options to support various business processes used in different companies. The implementation process of an ERP system consists in assigning values to ERP parameters according to the company requirements: It determines the exact operations and processes supported by the system in the specific company. Infologic is a French company that develops and integrates their own ERP system called Copilote. It has thousands of parameters that are used to adapt it as precisely as possible to customer requirements. However, this flexibility makes the implementation of Copilote a time consuming task that requires a deep knowledge of its functionalities and parameters. Reducing the complexity of the implementation of Copilote is a critical issue for Infologic who needs to integrate efficiently new system integrators to meet the demand of new customers. In this thesis, we study the implementation process of Copilote in order to understand the main issues encountered by Infologic. We propose a new approach for extracting a catalog of configuration parts from existing configurations of Copilote, and each configuration part is associated with the business requirement it fulfills in order to reuse it for next implementations of Copilote. To this aim, we propose to use constraint programming (CP) to easily integrate feedbacks of experts by means of new constraints or criteria. We introduce new CP models to solve conceptual clustering problems and a new global constraint for the exact cover problem with several propagation algorithms. We show it allows to model easily conceptual clustering problems and to solve it more efficiently thant existing delcarative approaches., Les ERP (Enterprise Resource Planning) sont incontournables dans les systèmes d'information des sociétés industrielles: ils jouent un rôle crucial pour automatiser et suivre leurs processus afin d'améliorer leur compétitivité. Un ERP est un logiciel générique qui est utilisé par plusieurs sociétés industrielles ayant des besoins et des processus différents. C'est pourquoi de nombreux paramètres permettent d'adapter le fonctionnement du système aux besoins d'une société. Le déploiement d'un ERP, qui vise à paramétrer le système en fonction des besoins collectés, est donc une tâche complexe qui requiert une profonde expertise du système mais aussi du métier de l'entreprise industrielle. Infologic est une société qui développe et installe son propre ERP appelé Copilote. La difficulté liée au déploiement de Copilote dans une société industrielle est un réel frein pour la croissance d'Infologic et réduire la complexité du paramétrage de Copilote est un enjeu vital pour Infologic. C'est pourquoi nous avons étudié le processus de déploiement de Copilote et particulièrement la phase de paramétrage du système. Nous proposons une approche visant à extraire, depuis l'ensemble des paramétrages existants, un catalogue de paramétrages correspondant à des besoins fonctionnels précédemment rencontrés afin de les réutiliser lors des prochains déploiements de Copilote. Nous proposons d’utiliser la programmation par contraintes pour cela, afin de pouvoir facilement personnaliser les solutions calculées en ajoutant des contraintes et des critères d’optimisation variés. Nous introduisons de nouveaux modèles à base de contraintes pour résoudre des problèmes de clustering conceptuel, ainsi qu'une contrainte globale pour le problème de couverture exacte avec plusieurs algorithmes de propagation. Nous montrons qu'elle permet de modéliser facilement des problèmes de clustering conceptuel, et de les résoudre plus efficacement que les approches déclaratives de l’état de l’art.

National audience; We propose an equitable conceptual clustering approach based on multi-agent optimization. In the context of conceptual clustering, each cluster is represented by an agent having its own satisfaction and the problem consists in finding the best cumulative satisfaction while emphasizing a fair compromise between all individual agents. The fairness goal is achieved using an equitable formulation of the Ordered Weighted Averages (OWA)operator. Experiments performed on UCI datasets and on instances coming from real application ERP show that our approach efficiently finds clusterings of consistently high quality.; Nous proposons une approche de clustering conceptuel qui exploite la notion d’équité en optimisation multiagents. L’idée consiste à s’assurer que les clusters obtenus soient équilibrés, i.e. approximativement de même taille. Dans notre approche, chaque agent représente un concept et l’utilité d’un agent correspondant à une mesure spécifique (par exemple la fréquence du concept). Le problème consiste alors à trouver la meilleure satisfaction cumulative tout en mettant l’accent sur un compromis équitable entre tous les agents individuels. Pour déterminer la solution optimale de meilleur compromis, nous avons exploité une formulation équitable de l’opérateur des moyennes pondérées ordonnées (en anglais, Ordered Weighted Averages - OWA), avec un jeu de poids particulièrement adapté à la recherche de solutions équitables. Les expériences effectuées sur les jeux de données de l’UCI et sur des instances issues d’une application réelle (ERP) montrent que notre approche trouve efficacement des clusterings de bonne qualité.

Combinatorial optimization problems have become the target of many scientific researches for their importance in solving academic problems and real problems encountered in the field of engineering and industry. Solving these problems by exact methods is often intractable because of the exorbitant time processing that these methods would require to reach the optimal solution(s). In this thesis, we were interested in the algorithmic context of solving combinatorial problems, and the modeling context of these problems. At the algorithmic level, we have explored the hybrid methods which excel in their ability to cooperate exact methods and approximate methods in order to produce rapidly solutions of best quality. At the modeling level, we worked on the specification and the exact resolution of complex problems in pattern set mining, in particular, by studying scaling issues in large databases. On the one hand, we proposed a first parallelization of the DGVNS algorithm, called CPDGVNS, which explores in parallel the different clusters of the tree decomposition by sharing the best overall solution on a master-worker model. Two other strategies, called RADGVNS and RSDGVNS, have been proposed which improve the frequency of exchanging intermediate solutions between the different processes. Experiments carried out on difficult combinatorial problems show the effectiveness of our parallel methods. On the other hand, we proposed a hybrid approach combining techniques of both Integer Linear Programming (ILP) and pattern mining. Our approach is comprehensive and takes advantage of the general ILP framework (by providing a high level of flexibility and expressiveness) and specialized heuristics for data mining (to improve computing time). In addition to the general framework for the pattern set mining, two problems were studied: conceptual clustering and the tiling problem. The experiments carried out showed the contribution of our proposition in relation to constraint-based approaches and specialized heuristics., Les problèmes d’optimisation combinatoire sont devenus la cible de nombreuses recherches scientifiques pour leur importance dans la résolution de problèmes académiques et de problèmes réels rencontrés dans le domaine de l’ingénierie et dans l’industrie. La résolution de ces problèmes par des méthodes exactes ne peut être envisagée à cause des délais de traitement souvent exorbitants que nécessiteraient ces méthodes pour atteindre la (les) solution(s) optimale(s). Dans cette thèse, nous nous sommes intéressés au contexte algorithmique de résolution des problèmes combinatoires, et au contexte de modélisation de ces problèmes. Au niveau algorithmique, nous avons appréhendé les méthodes hybrides qui excellent par leur capacité à faire coopérer les méthodes exactes et les méthodes approchées afin de produire rapidement des solutions. Au niveau modélisation, nous avons travaillé sur la spécification et la résolution exacte des problématiques complexes de fouille des ensembles de motifs en étudiant tout particulièrement le passage à l’échelle sur des bases de données de grande taille. D'une part, nous avons proposé une première parallélisation de l'algorithme DGVNS, appelée CPDGVNS, qui explore en parallèle les différents clusters fournis par la décomposition arborescente en partageant la meilleure solution trouvée sur un modèle maître-travailleur. Deux autres stratégies, appelées RADGVNS et RSDGVNS, ont été proposées qui améliorent la fréquence d'échange des solutions intermédiaires entre les différents processus. Les expérimentations effectuées sur des problèmes combinatoires difficiles montrent l'adéquation et l'efficacité de nos méthodes parallèles. D'autre part, nous avons proposé une approche hybride combinant à la fois les techniques de programmation linéaire en nombres entiers (PLNE) et la fouille de motifs. Notre approche est complète et tire profit du cadre général de la PLNE (en procurant un haut niveau de flexibilité et d’expressivité) et des heuristiques spécialisées pour l’exploration et l’extraction de données (pour améliorer les temps de calcul). Outre le cadre général de l’extraction des ensembles de motifs, nous avons étudié plus particulièrement deux problèmes : le clustering conceptuel et le problème de tuilage (tiling). Les expérimentations menées ont montré l’apport de notre proposition par rapport aux approches à base de contraintes et aux heuristiques spécialisées.

International audience; Unsupervised machine learning approaches involving several clustering algorithms working together to tackle difficult data sets are a recent area of research with a large number of applications such as cluster- ing of distributed data, multi-expert clustering, multi-scale clustering analysis or multi-view clustering. Most of these frameworks can be regrouped under the umbrella of collaborative clustering, the aim of which is to reveal the common underlying structures found by the different algorithms while analyzing the data.Within this context, the purpose of this article is to propose a collaborative framework lifting the limi- tations of many of the previously proposed methods: Our proposed collaborative learning method makes possible for a wide range of clustering algorithms from different families to work together based solely on their clustering solutions, thus lifting previous limitation requiring identical prototypes between the different collaborators. Our proposed framework uses a variational EM as its theoretical basis for the col- laboration process and can be applied to any of the previously mentioned collaborative contexts.In this article, we give the main ideas and theoretical foundations of our method, and we demonstrate its effectiveness in a series of experiments on real data sets as well as data sets from the literature.

In this work, we propose a novel way to consider the clustering and the reduction of the dimension simultaneously. Indeed, our approach takes advantage of the mutual reinforcement between data reduction and clustering tasks. The use of a low-dimensional representation can be of help in providing simpler and more interpretable solutions. We show that by doing so, our model is able to better approximate the relaxed continuous dimension reduction solution by the true discrete clustering solution. Experiment results show that our method gives better results in terms of clustering than the state-of-the-art algorithms devoted to similar tasks for data sets with different proprieties.

International audience; Clustering is the process of partitioning a dataset into groups based on the similarity between the instances. Many clustering algorithms were proposed, but none of them proved to provide good quality partition in all situations. Consensus clustering aims to enhance the clustering process by combining different partitions obtained from different algorithms to yield a better quality consensus solution. In this work, we propose a new consensus method that uses a pattern mining technique in order to reduce the search space from instance-based into pattern-based space. Instead of finding one solution, our method generates multiple consensus candidates based on varying the number of base clusterings considered. The different solutions are then linked and presented as a tree that gives more insight about the similarities between the instances and the different partitions in the ensemble.

International audience; In our data driven world, categorization is of major importance to help end-users and decision makers understanding information structures. Supervised learning techniques rely on annotated samples that are often difficult to obtain and training often overfits. On the other hand, unsupervised clustering techniques study the structure of the data without disposing of any training data. Given the difficulty of the task, supervised learning often outperforms unsupervised learning. A compromise is to use a partial knowledge, selected in a smart way, in order to boost performance while minimizing learning costs, what is called semi-supervised learning. In such use case, Spectral Clustering proved to be an efficient method. Also, Deep Learning outperformed several state of the art classification approaches and it is interesting to test it in our context. In this paper, we firstly introduce the concept of Deep Learning into an active semi-supervised clustering process and compare it with Spectral Clustering. Secondly, we introduce constraint propagation and demonstrate how it maximizes partitioning quality while reducing annotation costs. Experimental validation is conducted on two different real datasets. Results show the potential of the clustering methods.

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.

Data Stream Clustering is an active area of research which requires efficient algorithms capable of finding and updating clusters incrementally as data arrives. On top of that, due to the inherent evolving nature of data streams, it is expected that algorithms undergo both concept drifts and evolutions, which must be taken into account by the clustering algorithm, allowing incremental clustering updates. In this paper we present the Social Network Clusterer Stream+ (SNCStream+). SNCStream+ tackles the data stream clustering problem as a network formation and evolution problem, where instances and micro-clusters form clusters based on homophily. Our proposal has its parameters analyzed and it is evaluated in a broad set of problems against literature baselines. Results show that SNCStream+ achieves superior clustering quality (CMM), and feasible processing time and memory space usage when compared to the original SNCStream and other proposals of the literature.

The aim of collaborative clustering is to reveal the common underlying structure of data spread across multiple data sites by applying clustering techniques. The idea of Collaborative Clustering is that each collaborator share some information about the segmentation (structure) of its local data and improve its own clustering with the information provided by the other collaborators. This paper analyses the impact of the Quality of the potential Collaborators to the quality of the collaboration for a Topological Collaborative Clustering Algorithm based on the learning of a Self-Organizing Map. Experimental analysis on four real vector data-sets showed that the diversity between collaborators impact the quality of the collaboration. We also showed that the internal indexes of quality are a good estimator of the increase of quality due to the collaboration.

Clustering a graph, i.e., assigning its nodes to groups, is an important operation whose best known application is the discovery of communities in social networks. Graph clustering and community detection have traditionally focused on graphs without attributes, with the notable exception of edge weights. However, these models only provide a partial representation of real social systems, that are thus often described using node attributes, representing features of the actors, and edge attributes, representing different kinds of relationships among them. We refer to these models as attributed graphs. Consequently, existing graph clustering methods have been recently extended to deal with node and edge attributes. This article is a literature survey on this topic, organizing and presenting recent research results in a uniform way, characterizing the main existing clustering methods and highlighting their conceptual differences. We also cover the important topic of clustering evaluation and identify current open problems., Comment: Accepted for publication, Network Science journal

International audience; The aim of collaborative clustering is to reveal the common underlying structures found by different algorithms while analyzing data. The fundamental concept of collaboration is that the clustering algorithms operate locally but collaborate by exchanging information about the local structures found by each algorithm. In this framework, the one purpose of this article is to introduce a new method which allows to reinforce the clustering process by exchanging information between several results acquired by different clustering algorithms. The originality of our proposed approach is that the collaboration step can use clustering results obtained from any type of algorithm during the local phase. This article gives the theoretical foundations of our approach as well as some experimental results. The proposed approach has been validated on several data sets and the results have shown to be very competitive.

International audience; In our data driven world, clustering is of major importance to help end-users and decision makers understanding information structures. Supervised learning techniques rely on ground truth to perform the classification and are usually subject to overtraining issues. On the other hand, unsupervised clustering techniques study the structure of the data without disposing of any training data. Given the difficulty of the task, unsupervised learning tends to provide inferior results to supervised learning. To boost their performance, a compromise is to use learning only for some of the ambiguous classes. In this context, this paper studies the impact of pairwise constraints to unsupervised Spectral Clustering. We introduce a new generalization of constraint propagation which maximizes partitioning quality while reducing annotation costs. Experiments show the efficiency of the proposed scheme.

We present in this paper a new biomimetic method nammed CL-AntInc for data incremental clustering. This algorithm uses the behavior of real ants. We deal with the issue of data volume through a clustering heuristic. Dynamic graphs are constructed according to a simulation of colonial odors and pheromone mechanisms. We used numerical databases extracted from the Machine Learning Repository. The experimental results show the effectiveness of the suggested algorithm.

International audience; We are interested in local models for time series forecasting and we propose a new approach based on hierarchical clustering. This new approach uses a binary tree, k-means clustering and pruning strategies to find out the adequate clustering with MLP and SVM as predictors. The experimentations give very good results for this approach. Three strategies were tested and a comparative study with other methods show that the hierarchical predictor model outperformed the existing models on the three used datasets.

International audience; 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.

International audience; Indexing methods play a very important role in finding information in large image databases. They organize indexed images in order to facilitate, accelerate and improve the results for later retrieval. Alternatively, clustering may be used for structuring the feature space so as to organize the dataset into groups of similar objects without prior knowledge (unsupervised clustering) or with a limited amount of prior knowledge (semi-supervised clustering). In this paper, we introduce a new interactive semi-supervised clustering model where prior information is integrated via pairwise constraints between images. The proposed method allows users to provide feedback in order to improve the clustering results according to their wishes. Different strategies for deducing pairwise constraints from user feedback were investigated. Our experiments on different image databases (Wang, PascalVoc2006, Caltech101) show that the proposed method outperforms semi-supervised HMRF-kmeans (Basu et al., 2004).

International audience; Clustering is a popular task in knowledge discovery. In this chapter we illustrate this fact with a new clustering algorithm that is able to partition objects taking into account simultaneously their relational descriptions given by multiple dissimilarity matrices. The advantages of this algorithm are threefold: it uses any dissimilarities between objects, it automatically ponderates the impact of each dissimilarity matrice and it provides interpretation tools. We illustrate the usefulness of this clustering method with two experiments. The first one uses a data set concerning handwritten numbers (digitized pictures) that must be recognized. The second uses a set of reports for which we have an expert classification given a priori so we can compare this classification with the one obtained automatically.

International audience; We show how the quantum paradigm can be used to speed up unsupervised learning algorithms. More precisely, we explain how it is possible to accelerate learning algorithms by quantizing some of their subroutines. Quantization refers to the process that partially or totally converts a classical algorithm to its quantum counterpart in order to improve performance. In particular, we give quantized versions of clustering via minimum spanning tree, divisive clustering and k-medians that are faster than their classical analogues. We also describe a distributed version of k-medians that allows the participants to save on the global communication cost of the protocol compared to the classical version. Finally, we design quantum algorithms for the construction of a neighbourhood graph, outlier detection as well as smart initialization of the cluster centres.

This work describes and evaluates a novel interactive visual clustering system. It combines a 2D projection with a clustering algorithm that operates on this projected data. Users can interact directly through the 2D representation, by providing examples according to their expert ground truth. Each interaction incrementally updates the 2D projection and the associated clustering. Experiments show the effectiveness of the method, with as few as one interaction leading to a tangible influence on the visualization.

International audience; Model-based clustering is a popular tool which is renowned for its probabilistic foundations and its flexibility. However, high-dimensional data are nowadays more and more frequent and, unfortunately, classical model-based clustering techniques show a disappointing behavior in high-dimensional spaces. This is mainly due to the fact that model-based clustering methods are dramatically over-parametrized in this case. However, high-dimensional spaces have specific characteristics which are useful for clustering and recent techniques exploit those characteristics. After having recalled the bases of model-based clustering, this article will review dimension reduction approaches, regularization-based techniques, parsimonious modeling, subspace clustering methods and clustering methods based on variable selection. Existing softwares for model-based clustering of high-dimensional data will be also reviewed and their practical use will be illustrated on real-world data sets.

International audience; Model-based clustering is a popular tool which is renowned for its probabilistic foundations and its flexibility. However, model-based clustering techniques usually perform poorly when dealing with high-dimensional data streams, which are nowadays a frequent data type. To overcome this limitation of model-based clustering, we propose an online inference algorithm for the mixture of probabilistic PCA model. The proposed algorithm relies on an EM-based procedure and on a probabilistic and incremental version of PCA. Model selection is also considered in the online setting through parallel computing. Numerical experiments on simulated and real data demonstrate the effectiveness of our approach and compare it to sate-of-the-art online EM-based algorithms.

Short session: Clustering 3 (DM806); International audience; In many applications, entities of the domain are described through different aspects, or views, that classical clustering methods often process one by one. We introduce here a general architecture, named MVSim, that is able to deal simultaneously with all the information contained in such multi-view datasets by using several instances of an existing co-similarity algorithm. We show that this architecture offers an interesting formal framework to work with multi- view data, and experimentally provides better results than both single-view and multi-view approaches. Furthermore, this architecture can be easily parallelize thus reducing both time and space complexities of the computations.

In this paper we deal with data stated under the form of a binary relation between objects and properties. We propose an approach for clustering the objects and labeling them with characteristic subsets of properties. The approach is based on a parallel between formal concept analysis and graph clustering. The problem is made tricky due to the fact that generally there is no partitioning of the objects that can be associated with a partitioning of properties. Indeed a relevant partition of objects may exist, whereas it is not the case for properties. In order to obtain a conceptual clustering of the objects, we work with a bipartite graph relating objects with formal concepts. Experiments on artificial benchmarks and real examples show the effectiveness of the method, more particularly the fact that the results remain stable when an increasing number of properties are shared between objects of different clusters. © 2012 Springer-Verlag.

International audience; If the clustering task is widely studied both in graph clustering and in non supervised learning, combined clustering which exploits simultaneously the relationships between the ver- tices and attributes describing them, is quite new. In this paper, we present different scenarios for this task and, we evaluate their performances and their results on a dataset, with ground truth, built from several sources and containing a scientific social network in which textual data is associated to each vertex and the classes are known. We argue that, depending on the kind of data we have and the type of results we want, the choice of the clustering method is important and we present some concrete examples for underlining this.

International audience; In this paper, we present different combined cluster- ing methods and we evaluate their performances and their results on a dataset with ground truth. This dataset, built from several sources, contains a scientific social network in which textual data is associated to each vertex and the classes are known. Indeed, while the clustering task is widely studied both in graph clustering and in non supervised learning, combined clustering which exploits simultaneously the relationships between the vertices and attributes describing them, is quite new. We argue that, depending on the kind of data we have and the type of results we want, the choice of the clustering method is important and we present some concrete examples for underlining this.

International audience; The classical representation of a binary tree generated by a hierarchical clustering is a node-link-based visualization denoted as a dendrogram. It allows users to explore in a simple way the clusters and the relationships between instances. However, exploration of large dendrograms is known to be difficult due to the graphical and cognitive information overload involved. Here, we discuss the current approaches and we introduce Stacked Trees, a new Focus+Context visualization technique that allows the exploration of the hierarchical clustering of up to fifty thousands nodes on a standard-sized screen.

Part 2: Workshop; International audience; This article describes a proposition and first examples of using inductive learning methods in building of the image understanding system with the hierarchical structure of knowledge. This system may be utilized in various task of automatic image interpretation, classification and image enhancement. The paper points to the essential problems of the whole method: the constructing an effective algorithm of conceptual clustering and creation of the method of knowledge evaluation. Some possible solutions are discussed and first practical results (image filtering) are presented.

International audience; We present an improved relational clustering method integrating prior information. This new algorithm, entitled CEVCLUS, is based on two concepts: evidential clustering and constraint-based clustering. Evidential clustering uses the Dempster- Shafer theory to assign a mass function to each object. It provides a credal partition, which subsumes the notions of crisp, fuzzy and possibilistic partitions. Constraint-based clustering consists in taking advantage of prior information. Such background knowledge is integrated as an additional term in the cost function. Experiments conducted on synthetic and real data demonstrate the interest of the method, even for unbalanced datasets or non-spherical classes.

International audience; Information Extraction has recently been extended to new areas by loosening the constraints on the strict definition of the information extracted and allowing to design more open information extraction systems. In this new domain of unsupervised information extraction, we focus on the task of extracting and characterizing new relations between a given set of entity types. One of the challenges of this task is to deal with the large amount of candidate relations when extracting them from a large corpus.We propose in this paper an approach for the filtering of such candidate relations based on heuristics and machine learning models. More precisely, we show that the best model for achieving this task is a Conditional Random Field model, according to evaluations performed on a manually annotated corpus of about one thousand relations. We also tackle the problem of identifying semantically similar relations by clustering large sets of them. Such clustering is achieved by combining a classical clustering algorithm and a method for the efficient identification of pairs of highly similar relations. Finally, we evaluate the impact of our filtering of relations on this semantic clustering with both internal measures and external measures. Results show that the filtering procedure doubles the recall of the clustering while keeping the same precision.

We propose a new multi-view clustering method which uses clustering results obtained on each view as a voting pattern in order to construct a new set of multi-view clusters. Our experiments on a multilingual corpus of documents show that performance increases significantly over simple concatenation and another multi-view clustering technique., 33rd Annual Association for Computing Machinery’s Special Interest Group on Information Retrieval Conference (ACM SIGIR), July 19-23, 2010, Geneva, Switzerland

International audience; The aim of collaborative clustering is to make different clustering methods collaborate, in order to reach at an agreement on the partitioning of a common dataset. As different clustering methods can produce different partitioning of the same dataset, finding a consensual clustering from these results is often a hard task. The collaboration aims to make the methods agree on the partitioning through a refinement of their results. This process tends to make the results more similar. In this paper, after the introduction of the collaboration process, we present different ways to integrate background knowledge into it. Indeed, in recent years, the integration of background knowledge in clustering algorithms has been the subject of a lot of interest. This integration often leads to an improvement of the quality of the results. We discuss how such integration in the collaborative process is beneficial and we present experiments in which background knowledge is used to guide collaboration.

Data mining or knowledge discovery in database (KDD) refers to the non-trivial process of discovering interesting, implicit, and previously unknown knowledge from databases. Such a task implies to be able to perform analyses both on high-dimensional input data and large dataset. The most popular models used in KDD are the symbolic models. Unfortunately, these models suffer of very serious limitations. Rule generation is a highly time-consuming process that generates a huge number of rules, including a large ratio of redundant rules. Hence, this prohibits any kind of rule computation and selection as soon as data are numerous and they are represented by very high-dimensional description space. This latter situation is very often encountered with documentary data. To cope with these problems, preliminary KDD trials using numerical models have been made. An algorithm for knowledge extraction from self-organizing network has been proposed in [8]. This approach is based on a supervised generalized relevance learning vector quantization (GRLVQ) which is used for extracting decision trees. The different paths of the generated trees are then used for denoting rules. Nevertheless, the main defect of this method is to necessitate training data. On our own side, we have proposed a hybrid classification method for mapping an explicative structure issued from a symbolic classification into an unsupervised numerical self-organizing map (SOM) [15]. SOM map and Galois lattice are generated on the same data. The cosine projection is then used for associating lattice concepts to the SOM classes. Concepts properties act as explanation for the SOM classes. Furthermore, lattice pruning combined with migration of the associated SOM classes towards the top of the pruned lattice is used to generate explanation of increasing scope on the SOM map. Association rules can also be produced in such a way. Although it establishes interesting links between numerical and symbolic worlds this approach necessitates the time-consuming computation of a whole Galois lattice. In a parallel way, in order to enhance both the quality and the granularity of the data analysis and to reduce the noise which is inevitably generated in an overall classification approach, we have introduced the multi-viewpoint analysis and multilevel clustering approach based on a significant extension of the SOM model, named MultiSOM [19][25]. The viewpoint building principle consists in separating the description of the data into several sub-descriptions corresponding different property subsets or even different data subsets. In MultiSOM each viewpoint is represented by a single SOM map.

Geospatial clustering is an important topic in knowledge discovery research and geospatial information systems. However, current clustering research emphasizes the development of more efficient and effective clustering methods without paying much attention to domain knowledge and users' goals during the clustering process. Making better use of geospatial and clustering knowledge to select proper methods and datasets will help achieve clustering results that better meet users' requirements. In this article, we present the GEO_CLUST framework for performing geospatial clustering. The framework consists of the GeoCO ontology for geospatial clustering and the ontology reasoner reasoning mechanism. The GeoCO ontology is used to represent geospatial and clustering domain knowledge. The ontology reasoner uses classification and decomposition techniques to specify users' tasks. Using the framework, users can identify the appropriate geospatial data and clustering method based on their specific goals. To demonstrate the framework, two case studies on finding population density clusters in Western Canada and locating five hospitals in South Carolina are discussed. The results show that the framework can select the proper datasets and clustering methods with respect to users' goals.

This paper deals with clustering for multi-view data, i.e. objects described by several sets of variables or proximity matrices. Many important domains or applications such as Information Retrieval, biology, chemistry and marketing are concerned by this problematic. The aim of this data mining research field is to search for clustering patterns that perform a consensus between the patterns from different views. This requires to merge information from each view by performing a fusion process that identifies the agreement between the views and solves the conflicts. Various fusion strategies can be applied, occurring either before, after or during the clustering process. We draw our inspiration from the existing algorithms based on a centralized strategy. We propose a fuzzy clustering approach that generalizes the three fusion strategies and outperforms the main existing multi-view clustering algorithm both on synthetic and real datasets.

short paper (4 pages); International audience; We present a semi-supervised method to improve statistical parsing performance. We focus on the well-known problem of lexical data sparseness and present experiments of word clustering prior to parsing. We use a combination of lexicon-aided morphological clustering that preserves tagging ambiguity, and unsupervised word clustering, trained on a large unannotated corpus. We apply these clusterings to the French Treebank, and we train a parser with the PCFG-LA unlexicalized algorithm of Petrov et al. (2006). We find a gain in French parsing performance: from a baseline of F1=86.76% to F1=87.37% using morphological clustering, and up to F1=88.29% using further unsupervised clustering. This is the best known score for French probabilistic parsing. These preliminary results are encouraging for statistically parsing morphologically rich languages, and languages with small amount of annotated data.

Today, in many clustering applications we deal with a large amount of data that are delivered in form of data streams. To be able to face the problem of analyzing the data as soon as they are produced, we need to build models that can be incrementally updated. This paper presents an adaptation of a bio-inspired algorithm that dynamically creates and visualizes groups of data, to data stream clustering. We introduce a merge operator that can summarize a group of data and a split operator that uses information of a very small set of supervised data and permits to adapt the clustering to a change in the data stream.

International audience; This paper explores description and clusteringtechniques for virtual networks provisioning from sharedphysical resources. The contribution consists of a virtual resource description schema to specify properties and relations betweenvirtual resources and a conceptual clustering technique tofacilitate matching and discovery. Conceptual clustering providesa hierarchical classification of virtual resources and conceptdescriptions for clusters. Performance results benefits ofconceptual clustering for resource matching are reported

This paper describes a new topological map dedicated to clustering under probabilistic constraints. In general, traditional clustering is used in an unsupervised manner. However, in some cases, background information about the problem domain is available or imposed in the form of constraints in addition to data instances. In this context, we modify the popular GTM algorithm to take these "soft" constraints into account during the construction of the topology. We present experiments on synthetic known databases with artificial generated constraints for comparison with both GTM and another constrained clustering methods.

Biological databases are blooming today at an increasing rate to deal with the huge amount of data produced by genomic and post-genomic research. The need for a well-maintained searchable directory is therefore an important issue for a good exploitation of these databases. The BioRegistry repository is automatically generated from a publicly available list of biological databases (The Molecular Biology Database Collection published in Nucleic Acids Research) and aims at associating content metadata with each database in view of database retrieval and/or discovery. Such content metadata are either simple keywords or terms belonging to a medical thesaurus. Querying modalities including a search by semantic similarity are described. The use of conceptual clustering methods is proposed to build a semantic classification of biological databases enabling browsing through the BioRegistry repository and discovering previously unknown databases.

International audience; Clustering hypertext document collection is an important task in Information Retrieval. Most clustering methods are based on document content and do not take into account the hyper-text links. Here we propose a novel PageRank based clustering (PRC) algorithm which uses the hypertext structure. The PRC algorithm produces graph partitioning with high modularity and coverage. The comparison of the PRC algorithm with two content based clustering algorithms shows that there is a good match between PRC clustering and content based clustering.

International audience; This paper uses an optimization approach to address the problem of conceptual clustering. The aim of AGAPE, which is based on the tabu-search meta-heuristic using split, merge and a special “k-means” move, is to extract concepts by optimizing a global quality function. It is deterministic and uses no a priori knowledge about the number of clusters. Experiments carried out in topic extraction show very promising results on both artificial and real datasets.

The search for interesting groups in boolean data (sets of objects described by sets of properties) has motivated the design of methods for computing global patterns (e. G. . , partitions), and extracting local patterns s(e. G. , frequent itemsets, association rules, formal concepts. This thesis concerns co-clustering, i. E. , computing bi-partitions (coupled partitions on both dimensions). When using available co-clustering algorithms, the user can hardly exploit his/her domain knowledge since he/she has limited possibilities for setting just a few parameters. On the other hand, classical local pattern mining techniques usually provide huge collections of patterns that are hard to evaluate and interpret. We have designed a new co-clustering framework which computes a bi-partition by starting from collections of patterns that capture locally strong associations (e. G. , formal concepts, delta-bi-set that are a form of fault-tolerant patterns). The idea is that the available information about the local patterns can be exploited to build a relevant global pattern. It becomes possible to consider the declarative specification of constraints on the bi-partitions (e. G. , user-defined requirements about the shape of clusters) and to use such constraints at the local pattern mining step and then during the co-clustering phase. As such, our proposal is a contribution to the recent domain of constraint-based clustering. A dual approach consists in using local patterns to interpret bi-partitions. We propose a method for bi-cluster characterization by means of local patterns and their associated interestingness measures. The application of our methods to a gene expression data analysis scenario has illustrated the added-value of our proposal to give rise to plausible biological hypothesis.; La recherche de groupements intéressants dans les données booléennes (ensembles d'objets décrits par un ensemble de propriétés) a motivé la conception de méthodes d'extractions de motifs globaux (partitions) et de motifs locaux (ensembles fréquents, règles d'association et concepts formels). Cette thèse concerne la co-classification c'est-à-dire le calcul de bi-partitions (couplage de partitions sur les deux dimensions). Les algorithmes de co-classification disponibles ne permettent aux analystes d'exploiter leur connaissance du domaine qu'à travers un nombre réduit de paramètres. D'autre part, les techniques d'extraction de motifs locaux produisent d'énormes collections qui sont difficilement exploitables et interprétables. Nous avons développé une nouvelle méthode de co-classification qui calcule des bi-partitions à partir de motifs capturant des associations localement fortes (e. G. , des concepts formels, une forme de motif tolérant aux exceptions appelé delta-bi-ensemble). Le principe consiste à exploiter l'information contenue dans la collection des motifs locaux en la propageant au niveau global pour faciliter l'optimisation de la fonction objectif. Il devient alors possible de propager un certain nombre de contraintes depuis l'extraction des motifs locaux jusqu'à la construction de la bi-partition (e. G. , pour imposer des formes particulières aux groupes calculés). Il s'agit donc d'une contribution au domaine très récent de la classification sous contraintes. Une approche duale consiste à utiliser des motifs locaux pour faciliter l'interprétation de bi-partitions déjà calculées. Pour ce faire, nous proposons une méthode de caractérisation des bi-clusters au moyen de motifs locaux auxquels sont associés des mesures d'intérêt. L'application de nos méthodes à l'analyse de données d'expression de gènes a montré la pertinence de nos propositions pour expliciter des hypothèses biologiques plausibles.

DIVCLUS-T is a descendant hierarchical clustering methods based on the same monothetic approach than segmentation but from an unsupervised point of view. The dendrogram of the hierarchy is easy to interpret and can be read as decision tree. We present DIVCLUS-T on a small numerical and a small categorical example. DIVCLUS-T is then compared with two polythetic clustering methods: the Ward ascendant hierarchical clustering method and the k-means partitional method. The three algoritms are applied and compared on six databases of the UCI Machine Learning repository.

International audience; We applied different clustering algorithms to the task of clus- tering multi-word terms in order to reflect a humanly built ontology. Clustering was done without the usual document co-occurrence infor- mation. Our clustering algorithm, CPCL (Classification by Preferential Clustered Link) is based on general lexico-syntactic relations which do not require prior domain knowledge or the existence of a training set. Results show that CPCL performs well in terms of cluster homogeneity and shows good adaptability for handling large and sparse matrices.

International audience; Bi-clustering is a promising conceptual clustering approach. Within categorical data, it provides a collection of (possibly overlapping) bi-clusters, i.e., linked clusters for both objects and attribute-value pairs. We propose a generic framework for bi-clustering which enables to compute a bi-partition from collections of local patterns which capture locally strong associations between objects and properties. To validate this framework, we have studied in details the instance CDK-Means. It is a K-Means-like clustering on collections of formal concepts, i.e., connected closed sets on both dimensions. It enables to build bi-partitions with a user control on overlapping between bi-clusters. We provide an experimental validation on many benchmark datasets and discuss the interestingness of the computed bi-partitions.

In this paper we address the problem of organising probabilistic data by Galois concept lattices. Two lattices are proposed, the union lattice and the intersection lattice, corresponding to two distinct semantics, by choosing accordingly the join and meet operators. A new algorithm is proposed to construct the concept lattice. Two real data examples illustrate the presented approach. Dans cet article, nous nous intéressons à l’organisation de données probabilistes par des treillis de Galois. Deux correspondances de Galois sont établies, en définissant de façon appropriée les opérateurs de généralisation et d'extension. Ces correspondances permettent de construire deux treillis, appelés treillis de l’union et treillis de l’intersection, corres-pondant à ces deux correspondances de Galois. Un nouvel algorithme de construction de treillis est proposé. Deux exemples sur des données réelles illustrent l’approche présentée.