Bonjour,bonsoir,

Je suis débutant en ocaml depuis 1 mois et j'ai un projet à rendre, je n'arrive à tout faire. Donc j'ai besoin de l'aide des menbres du forum.
Le problème est de réaliser : L’algorithme des k-moyennes.

PARTIE 1:
On considère pour ce projet des multi-ensembles de points de R (n ∈ N).
Implantation demandée : chaque multi-ensemble de points de R(n) (n ∈ N) correspondra à un arbre binaire de recherche où les nœuds seront étiquetés par des couples indiquant le point et son poids. Les couples seront classées dans l’arbre selon l’ordre naturel d’OCaml sur la structure représentant les points.
Vous devez fournir toutes les fonctions nécessaires à la manipulation des arbres binaires de recherche : l’ajout d’un point avec la modification du poids, la suppression d’un point avec la modification du poids, le test de vacuité et la création de l’ensemble vide.

PARTIE 2:
L’algorithme considère en entrée les données suivantes :
• un multi-ensemble de m points de R(N)
(n ∈ N) : N = (pi)1≤i≤m ;
• un entier strictement positif k ≤ m ;
• une fonction de distance d prenant deux points et renvoyant un nombre réel positif.
L’algorithme renvoie en sortie une liste de k multi-ensembles [N1, . . . , Nk]
Pour cela, l’algorithme va raffiner des partitions de N au fur et à mesure. Au début, on choisit k points dans le nuage N. Ces k points (pi)1≤i≤k sont les points moyens respectifs des partitions N1, . . . , Nk. Tous les autres points p de N sont alors ajoutés au multi-ensemble Ni dont ils sont le plus proche.
Une fois ce premier partitionnement de N réalisé, on recommence en considérant comme représentant les points moyens des partitions ainsi constituées tant que V diminue.
Implantation demandée : en utilisant la structure que vous avez créé pour les multi-ensembles, écrivez l’algorithme des k-moyennes en OCaml. Vous pourrez tester votre implantation en utilisant les distances suivantes explicitées pour les points x = (x1, . . . , xn) et y = (y1, . . . , yn) de R(N) distance euclidienne.

PARTIE 3:
Représentation graphique des données. Dans le cas des points à deux dimensions, vous devrez fournir une bibliothèque de représentation graphique. Pour une partition d’un multi-ensemble N en k multi-ensembles ,chaque partition Ni sera représentée par un nuage de points d’une couleur particulière.
Implantation demandée : vous devez fournir les fonctions permettant de représenter une partition fixée. Vous devez également présenter une représentation dynamique, illustrant les différentes partitions calculées par l’algorithme des k-moyennes.

Pour le moment j'ai fais la partie 1, donc il me reste la partie 2 et 3 :

PARTIE1 :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
 
(* implementer le type abstrait de données multi-ensemble. *)
 
type 'e elem = ('e * int) ;;
 
type 'e multiens =
    Vide 
  | Noeud of 'e elem * 'e multiens * 'e multiens;;
 
(*test d'un ABR*)
(*sous-arbre droit superieur à la racine*)
let rec sgra r sd =
  match sd with 
  | Vide           -> true
  | Noeud(v,tf,tr) -> v < r && (sgra r tf) && (sgra r tr);;
 
(*test d'un ABR*)
(*sous-arbre gauche inferieur à la racine*)    
let rec spti r sd =
  match sd with
  | Vide           -> true
  | Noeud(v,tf,tr) -> v > r && (spti r tf) && (spti r tr);;
 
(*verifie que c'est un ABR *)
let rec isAb = function
  | Vide           -> true
  | Noeud(v,tf,tr) -> (sgra v tf)&&(spti v tr)&&(isAb tf)&&(isAb tr);;
 
(* parcours en profoncdeur d'un arbre binaire, sens gauche - droite *)
(*Parcour prefixe*)
let rec pref = function
  | Vide           -> []
  | Noeud(v,tf,tr) -> [v]@pref(tf)@pref(tr);;
 
(*Parcour infixe *)
let rec inf = function
  | Vide           -> []
  | Noeud(v,tf,tr) -> inf(tf)@[v]@inf(tr);;
 
(*Parcour suffixe*)
let rec suf = function
  | Vide           -> []
  | Noeud(v,tf,tr) -> suf(tf)@suf(tr)@[v];;
 
(* implantation des fonctions de mamipulation des listes *)
(*fonction d'ajout *)
 
let rec ajout elt arbre =
  match arbre with
  | Vide                         -> Noeud(elt,Vide,Vide)
  | Noeud(v,tf,td) when  v > elt -> Noeud(v,(ajout elt tf),td)
  | Noeud(v,tf,td) when  v < elt -> Noeud(v,tf,(ajout elt td))
  | Noeud(v,tf,td)               -> Noeud( (fst v, (snd v + snd elt)),tf,td);;  
 
(* obtenir un arbre a partir d'une liste *)
let arbre_de_liste li =
  let rec aux li arbre =
    match li with
    | []     -> arbre
    | hd::tl -> (aux tl (ajout hd arbre))
  in (aux li Vide);;
 
 
(*exple de test*)
 
 
(*fonction de suppression *)
let rec supprime elt arbre = 
  match arbre with
  | Vide                            -> Vide
  | Noeud(v,Vide,td) when v = elt   -> td
  | Noeud(v,tf,Vide) when v = elt   -> tf
  | Noeud(v,Vide,Vide) when v = elt -> Vide 
  | Noeud(v,tf,td) when (fst v = fst elt)&&(snd v > snd elt) -> Noeud((fst v,(snd v - snd elt)),tf,td)
  | Noeud(v,tf,td) when (fst v = fst elt)&&(snd v < snd elt) -> failwith" un souci avec le poid"
  | Noeud(v,tf,td) when v < elt     -> Noeud(v,tf,(supprime elt td))
  | Noeud(v,tf,td) when v > elt     -> Noeud(v,(supprime elt tf),td)
  | Noeud(v,tf,td)                  -> arbre_de_liste((inf tf)@(inf td));;
 
(* obtenir une liste a partir d'un arbre *)
let liste_de_arbre arbre =
  let rec aux arbre acc =
    match arbre with
    | Vide           -> acc
    | Noeud(v,tf,td) -> (aux (supprime v arbre) (v::acc) ) 
  in (aux arbre []);;
(* test d'exemple*)
 
 
(* fonction pour le test de vacuite *)
let test_vacuite arbre =  
  match arbre with 
  | Vide -> true 
  | _    -> false;;
(* test la présence d'une valeur dans l'arbre *)
let rec recherche k arbre =
  match arbre with
  | Vide                                   -> false
  | Noeud (v,tf,td) when (fst v) = (fst k) -> true
  | Noeud (v,tf,td)                        -> (recherche k tf) || (recherche k td);;
 
(* teste ajout des points dans le multienssemble *)
 
let arbre = (Noeud (([6.;5.],1),
                    Noeud(([2.;1.],3),
                          Noeud(([1.;4.],2),
                                Noeud(([0.;3.],1),Vide,Vide),
                                Vide),
                          Noeud(([7.;3.],5),
                                Noeud(([3.;8.],9),Vide,Vide),
                                Noeud(([5.;6.],4),Vide,Vide)
                               )
                         ),
                    Noeud(([8.;7.],5),
                          Noeud(([7.;3.],8),Vide,Vide),
                          Noeud(([9.;8.],6),Vide,Vide)
                         )
                   )
            );;
(ajout([3.;8.],9) arbre);;
 
(* PARTIE II *)
 
(* le multi-ensemble ci - dessus *) 
 
(* un entier k inferieur a la longueur de la liste *)

Merci de bien vouloir faire quelques chose qui pourait m'aider.