Inscription / Connexion Nouveau Sujet
Niveau école ingénieur
Partager :

Algorithmique

Posté par
matheux14
19-12-23 à 12:58

Bonjour,

Voici un problème en relation avec l'algorithmique et qui implique un peu de Maths, que je voudrais résoudre.

Merci d'avance.

On souhaite faire une classification des primates (dans le but de comprendre l'évolution du singe). Pour ce faire, l'ADN d'un individu de chaque espèce est analysé : P_1 est un humain, P_2 est un chimpanzé, P_3 est un bonobo, P_4 est un gorille, P 5 est un orang-outan et P_6 est un gibon. Les distances euclidiennes entre chacun de ces individus, caractérisant leur ressemblance quant à l'ADN, sont données dans le tableau incomplet suivant :
$A=$\begin{tabular}{|c|c|c|c|c|c|c|}
 \\ \hline Individus & P1 & P2 & P3 & P4 & P5 & P6 \\
 \\ \hline P1 & 0 & 0.84 & 0.95 & 1.49 & 1.85 & 2.56 \\
 \\ \hline P2 & 0.84 & 0 & 0.70 & 1.11 & 1.87 & 2.38 \\
 \\ \hline P3 & 0.95 & 0.70 & 0 & 1.35 & $\mathrm{~d}$ & 2.15 \\
 \\ \hline P4 & 1.49 & 1.11 & 1.35 & 0 & 1.96 & 2.32 \\
 \\ \hline P5 & 1.85 & 1.87 & 2.05 & 1.96 & 0 & 2.30 \\
 \\ \hline P6 & 2.56 & 2.38 & 2.15 & 2.32 & 2.30 & 0 \\
 \\ \hline
 \\ \end{tabular}

1/ Montrer qu'à la première itération de la boucle répéter de l'algorithme du CAH, on a :

D\left(C_g, C_i\right)_{i \in\{1,4,5\}}= \begin{cases}d\left(P_2, P_i\right) & \text { pour le critère de saut minimal } \\ d\left(P_3, P_i\right) & \text { pour le critère de saut maximal } \\ \frac{1}{2} \times\left(d\left(P_2, P_i\right)+d\left(P_3, P_i\right)\right) & \text { pour le critère de la moyenne }\end{cases}

2/ Poursuivre l'algorithme du CAH en utilisant le critère de la moyenne. Représenter le dendrogramme.

3/ Si l'on decide de couper l'arbre pour former 4 clusters; quelles seront ces classes ?

4/ Proposer des commandes R pour répondre aux questions 2 et 3 précédentes.

Voici l'algorithme du CAH en question et des informations supplémentaires.

Algorithmique du \mathrm{CAH}
- Initialisation
- Chaque individu est placé dans son propre cluster.
- Calcul de la matrice de ressemblance A entre chaque couple de clusters
- Répéter
- Sélection dans A des deux clusters les plus proches Ci et Cj.
- Fusion de \mathrm{Ci} et \mathrm{Cj} pour former un cluster \mathrm{Cg}.
- Mise à jour de \mathrm{A} en calculant la ressemblance entre \mathrm{Cg} et les clusters existants .
Jusqu'à la fusion des 2 derniers clusters.

Critère du saut minimal

D\left(C_i, C_j\right)=\min _{P_i \in C_i, P_j \in C_j}\left(d\left(P_i, P_j\right)\right)

Critère du saut maximal

D\left(C_i, C_j\right)=\max _{P_i \in C_i, P_j \in C_j}\left(d\left(P_i, P_j\right)\right)


Critère de la moyenne

D\left(C_i, C_j\right)=\frac{1}{\operatorname{card}\left(C_i\right) \times \operatorname{card}\left(C_j\right)} \sum_{P_i \in C_i} \sum_{P_j \in C_j} d\left(P_i, P_j\right)


Critère de Ward

D\left(C_i, C_j\right)=\sqrt{\frac{\operatorname{card}\left(C_i\right) \times \operatorname{card}\left(C_j\right)}{\operatorname{card}\left(C_i\right)+\operatorname{card}\left(C_j\right)}} d\left(g_{C_i}, g_{C_j}\right)

N.B: D la distance entre clusters et $d$ la distance euclidienne entre individus.

Pour la 1ère question :

Pour calculer D(Cg​,Ci​) à chaque étape du CAH, j'ai essayé  d'utiliser la distance euclidienne entre les points correspondant aux individus Cg​ et Ci​. On peut utiliser la fonction dist() du package MASS en R pour calculer cette distance. Par exemple :

# Charger le package MASS
library(MASS)

# Calculer la distance euclidienne entre P1 et P2
dist(P1[1], P2[1])
#> [1] 0.84

# Calculer la distance euclidienne entre P2 et P3
dist(P2[1], P3[1])
#> [1] 0.70

# Calculer la distance euclidienne entre P3 et P4
dist(P3[1], P4[1])
#> [1] 0.35

# Calculer la distance euclidienne entre P4 et P5
dist(P4[1], P5[1])
#> [1] 0.01

# Calculer la distance euclidienne entre P5 et P6
dist(P5[1], P6[1])
#> [1] 0.02



On peut ensuite appliquer les règles du CAH pour obtenir D(Cg​,Ci​) à chaque étape, mais je ne sais pas si je suis sur la bonne voie.

Posté par
matheux14
re : Algorithmique 19-12-23 à 16:38



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1687 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !