Niveau école ingénieur

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 re : Algorithmique 19-12-23 à 16:38