Regrouper des données en amas

Il s'agit ici de résoudre un problème de classification de données très courant en analyse de données. L'un des secteurs d'activité le plus friand de ce type de problème est assurément celui de la médecine. En effet, considérons un ensemble de patients présentant tous la même maladie (pour le moment inconnue) mais avec des examents cliniques différents. Le but est de regrouper les patients en paquets afin de rattacher leur syndrôme à quelque chose de `` connu ''. La méthodologie retenue consiste à créer un graphe complet où les patients sont les sommets et les arcs sont valués conformément à une distance qui peut être, par exemple, le nombre de critères différents ou bien encore des fonctions de pondération (par exemple, une somme pondérée des différences) sur chacun des critères cliniques retenus. On peut définir des amas en créant un ACM puis en coupant les arcs de plus fort coût. Le plus compliqué est de savoir à partir de quelle limite de coût on ne doit plus retenir d'arcs. Nous verrons que l'algorithme de Kruskal est le mieux adapté pour cet exemple.