Accueil
Affiche (PDF)
 
Participants
Programme
Inscription
Site
Hébergement
Liens
 
 
Éditions précédentes
2004
2003
2002


    

Séance TB11 - Exploration de données II / Data mining II

Jour mardi, le 10 mai 2005
Salle Van Houtte
Président Pierre Hansen

Présentations

13h30 Comparaison empirique de méthodes ensemblistes basées sur des arbres de classification
  Denis Larocque, HEC Montréal, Méthodes quantitatives de gestion
Mounir Hamza, HEC Montréal, Méthodes quantitatives de gestion

Dans cette présentation, nous faisons une comparaison empirique des erreurs de classification de plusieurs méthodes ensemblistes basées sur des arbres de classification. Cette comparaison est basée sur 14 ensembles de données qui sont ouvertement disponibles et qui ont été utilisés par Lim, Loh et Shih (Machine Learning 40, 203-228, 2000). Les méthodes sont un seul arbre, le Bagging, le Boosting (Arcing) et les forêts aléatoires. Elles sont comparées sur différents aspects. Plus précisément, nous examinons l’effet du bruit, l’effet de permettre les combinaisons linéaires dans la construction des arbres, les différences entre certains critères de séparation et, pour les forêts aléatoires, l’effets du nombre de variables sélectionnées pour choisir la meilleure séparation à chaque nœud. De plus, nous comparons nos résultats avec ceux de Lim et al. (2000). Globalement, dans cette étude, les meilleurs résultats ont été obtenus avec les forêts aléatoires. En particulier, les forêts aléatoires sont les plus robustes face au bruit. L’effet de permettre les combinaisons linéaires et les différences entre les critères de séparation ne sont pas très grands en moyenne mais peuvent être importants pour certains ensembles de données.


13h55 Comparaison de fonctions de similarité entre chaînes de caractères dans une tâche de détection de doublons approximatifs
  Jean-Philippe Raymond, HEC Montréal

Lors de l’intégration de données provenant de différentes sources, il peut être nécessaire de procéder à l’identification des doublons approximatifs, des enregistrements qui font référence à la même entité sans toutefois être textuellement identiques. Pour ce faire, des fonctions de similarité entre chaînes de caractères peuvent être utilisées. De telles fonctions qui évaluent la similarité textuelle entre deux chaînes de caractères ont été proposées dans la littérature de diverses communautés de recherche (ex. : bases de données, recherche d’information et intelligence artificielle). Dans le cadre de cette présentation, nous faisons une comparaison empirique de plusieurs de ces fonctions dans une tâche de détection de doublons approximatifs et nous évaluons l’impact de quelques modifications apportées à celles-ci. Les résultats obtenus montrent que certaines modifications améliorent significativement la performance de fonctions de similarité sur lesquelles elles sont appliquées. Notamment, une variante de la méthode de niveau 2 conçue par Monge et Elkan (1996) et plus tard généralisée par Cohen, Ravikumar et Fienberg (2003) est proposée. Cette méthode a été appliquée sur plusieurs fonctions de similarité et les expérimentations indiquent que la nouvelle variante est généralement plus précise que la méthode originale et qu’elle permet à des fonctions de se comparer avantageusement aux autres fonctions existantes considérées dans cette étude.


14h20 Misclassification Minimization by Variable Neighborhood Search
  Alejandro Karam, HEC Montréal, Management Science, 3000, chemin de la Côte-Sainte-Catherine, Montreal, QC, Canada, H3T 2A7
Pierre Hansen, HEC Montréal, GERAD et Méthodes quantitatives de gestion, 3000, ch. de la Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7

We consider the problem of separating two sets of points in an Euclidean space, with intersecting convex hulls, with a hyperplane that minimizes the number of points lying on the "wrong" side of the plane. This problem is NP-complete, and only small instances can be tackled with exact algorithms. We propose and test a heuristic approach, based on the Variable Neighborhood Search framework, to determine the plane coefficients. Numerical experiments with instances of up to 100,000 points in 6 dimensions, suggest that the method is fast and reliable. The discriminating hyperplanes found appear to generalize well on holdout sets, as compared to those obtained by alternative procedures.


14h45 A Constraint Generation Algorithm for the Two-Groups Discrimination Problem
  Simon Blanchard, GERAD
Gilles Caporossi, HEC Montréal, GERAD et Méthodes quantitatives de gestion, 3000, ch. de la Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7
Pierre Hansen, HEC Montréal, GERAD et Méthodes quantitatives de gestion, 3000, ch. de la Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7

The two-groups discrimination problem consists in finding an hyperplan that best seperates the points of the first group from those of the second. Mathematical programming formulations can be used to solve to optimality for the L-1, L-2 and L-infinity norms. However, the actual methods are inefficient on large datasets. In this paper, a constraint generation algorithm is proposed in order to significantly reduce the number of points explicitly considered. We expect to obtain exact solutions for problems of increased size, within a reasonable time.