Mathématiques et sciences humaines/Mathematics and social sciences

n° 161, Printemps 2003, spécial Recherche opérationnelle et aide à la décision

Version imprimable   Signaler cette page  

Partitions optimisées selon différents critères : évaluation et comparaison

Partitions optimizing different criteria: evaluation and comparison

Alain Guenoche

Télécharger le texte intégral (1009k)

Résumé

Dans cet article, nous étudions et comparons des méthodes de partitionnement d'un ensemble d'éléments muni d'une distance, méthodes qui opèrent à partir de cette seule donnée. On cherche à construire une partition à nombre de classes fixé qui optimise un critère (séparation, diamètre ou inertie). Les méthodes étudiées fonctionnent sur le même principe : le nombre maximum de classes étant fixé, on construit une partition pour chaque valeur du nombre de classes variant de 2 au maximum. Tous les critères étudiés conduisent à des problèmes d'optimisation NP-difficiles. L'algorithme général combine des méthodes de descente et des métaheuristiques pour construire des partitions sous-optimales. Plusieurs façons d'évaluer la qualité des classes et de comparer ces partitions sont proposées ; elles sont indépendantes du critère optimisé et des cardinaux des classes. Elles permettent de choisir la partition la plus compatible avec une distance donnée. Par simulation de plusieurs types de distance (euclidienne, booléenne, ou distance d'arbre) on étudie les critères qui donnent en moyenne les meilleurs résultats.

Abstract

In this article, we study and compare partitionning methods applied to a distance matrix. Given the maximum number of classes and a criterion, we build one partition optimizing this criterion for each number of classes varying from 2 to this maximum. All the studied criteria lead to NP-hard problems. The general algorithm combines optimization and metaheuristic technics to build sub-optimal solutions. Several ways to evaluate the quality of the classes and to compare partitions corresponding to different criteria are proposed. They allow to chose the best partition fitting a distance matrix and, simulating several types of metric, to designate the criterion providing generally the best results.

Index

Pour citer cet article

Alain Guenoche, « Partitions optimisées selon différents critères : évaluation et comparaison », Mathématiques et sciences humaines, n° 161, Printemps 2003, spécial Recherche opérationnelle et aide à la décision, [En ligne], mis en ligne le 10 février 2006. URL : http://msh.revues.org/document2879.html. Consulté le 17 mai 2008.

 
Page générée par Lodel - Nous adhérons à www.revues.org

ISSN : 0987 6936
Ecole des hautes études en sciences sociales