Navigation – Plan du site

AccueilNuméros161Partitions optimisées selon diffé...

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

Partitions optimizing different criteria: evaluation and comparison
Alain Guénoche

Résumés

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.

Haut de page

Pour citer cet article

Référence électronique

Alain Guénoche, « Partitions optimisées selon différents critères : évaluation et comparaison »Mathématiques et sciences humaines [En ligne], 161 | Printemps 2003, mis en ligne le 10 février 2006, consulté le 29 mars 2024. URL : http://journals.openedition.org/msh/2879 ; DOI : https://doi.org/10.4000/msh.2879

Haut de page

Auteur

Alain Guénoche

Articles du même auteur

Haut de page

Droits d’auteur

Le texte et les autres éléments (illustrations, fichiers annexes importés), sont « Tous droits réservés », sauf mention contraire.

Haut de page
Search OpenEdition Search

You will be redirected to OpenEdition Search