---
tags: corrTD, info, kmeans, 2324
---
# <center>TD6 : algorithme des k moyennes</center>
Documents de base : le [cours](http://demeslay.maths.free.fr/fichiers/info/spe/03_Algo_apprentissage.pdf) (à partir de la page 6) et le [TD6](http://demeslay.maths.free.fr/fichiers/info/spe/TD06_Kmeans.pdf).
[TOC]
### Exercice 1 : choix des centres initiaux
Comme on doit déterminer k centres **distincts**, on procède à des tirages au sort en vérifiant qu'à chaque choix que ce n'est pas un centre déjà choisi. Comme on ne sait pas le nombre de tirages aléatoires auxquels on devra procéder, on utilise nécessairement une boucle `while`.
Il y a alors deux façons de procéder qui reviennent en fait au même.
```python=
from random import randint
def init_centres(datas: [tuple], k: int) -> [int]:
"""
Choix aléatoires de k éléments indices distincts parmi
ceux valides dans la liste datas.
"""
assert k < len(datas) # pour éviter une boucle infinie ensuite
centres = []
while len(centres) < k:
i = randint(0, len(datas)-1)
if i not in centres:
centres.append(i)
return centres
def init_centres_v2(datas: [tuple], k: int) -> [int]:
centres = []
"""
idem
"""
assert k < len(datas) # pour éviter une boucle infinie ensuite
for i in range(k):
a = randint(0, len(datas)-1)
while a in centres:
a = randint(0, len(datas)-1)
centres.append(a)
return centres
```
### Exercice 2 : trouver le centre le plus proche
La fonction `distance` peut être retrouvée dans l'exercice 1 du <a href=https://codimd.apps.education.fr/IqBFA2djRdavr8I3BnTo8Q?both>corrigé du TD5</a>.
```python=
def centre_proche(point: tuple, centres: [tuple]) -> int:
"""
Renvoie le centre le plus proche de point parmi ceux de
la liste centres.
"""
ind_proche = 0
dmin = distance(point, centres[0])
for i in range(1, len(centres)):
if distance(point, centres[i]) < dmin:
ind_proche = i
dmin = distance(point, centres[i])
return ind_proche
```
Et pour une version qui gère les égalités, on doit garder tous les centres à plus courte distance dans une liste. Dans notre algorithme de minimum, on doit donc distinguer deux cas suivant si le centre est à même distance ou strictement plus proche que le record précédent.
```python=
from random import randint
def centre_proche_egalite(point: tuple, centres: [tuple]) -> int:
"""
Renvoie le centre le plus proche de point parmi ceux de la
liste centres. Choix aléatoire en cas d'égalité.
"""
ind_proche = [0] # liste pour garder toutes les égalités
dmin = distance(point, centres[0])
for i in range(1, len(centres)):
# Si strictement plus proche, mise à jour de dmin
# et liste réinintialisée à une seule valeur.
if distance(point, centres[i]) < dmin:
ind_proche = [i]
dmin = distance(point, centres[i])
# Si égalité, on ajoute le centre à la liste des plus proches.
elif distance(point, centres[i]) == dmin:
ind_proche.append(i)
# On tire au sort un indice valide parmis les plus proches
ind_alea = randint(0, len(ind_proche)-1)
return ind_proche[ind_alea]
```
### Exercice 3 : isobarycentre
```python=
def isobarycentre(groupe: [tuple]) -> tuple:
"""
Renvoie les coordonnées de l'isobarycentre des points de groupe.
"""
n = len(groupe[0]) # nb de coordonnées d'un point
iso = [0] * n
for point in groupe:
for j in range(n):
iso[j] = iso[j] + point[j]
for j in range(n):
iso[j] = iso[j] / len(groupe)
return tuple(iso)
```
### Exercice 5 : Trouver le minimum global
* **Q1.** Stratégie :
1. On parcourt les centres.
2. Pour chacun d'eux, on regarde, grâce au dictionnaire `groupes`, les points qui y sont associés (par exemple pour le centre d'indice 0, la valeur `groupes[0]` est la liste de leurs indices dans `datas`).
3. On calcule alors les distances entre le centre et ces points et on somme le tout.
On peut alors donner une version où l'on parcourt par les indices :
```python=
def variance(datas: [tuple], centres: [tuple], groupes: dict) -> float:
"""
Renvoie la variance de la répartition des points de datas
dans les groupes de centres donnés.
"""
var = 0
for i in range(len(centres)): # ou range(len(groupes))
for j in range(len(groupes[i])):
var = var + distance(centres[i], groupes[i][j])
return var
```
ou l'équivalent où le parcours de `groupes` se fait par les valeurs, cela facilitant la lisibilité :
```python=
def variance(datas: [tuple], centres: [tuple], groupes: dict) -> float:
"""
Renvoie la variance de la répartition des points de datas
dans les groupes de centres donnés.
"""
var = 0
k = len(centres) # = len(groupes)
for i in range(k):
centre = centres[i]
for j in groupes[i]:
var = var + distance(centre, datas[j])
return var
```
* **Q2.** On reconnaît le principe d'un algorithme de minimum. On effectue `nb_repet` fois l'algo des k moyennes (ligne 10) et à chaque fois on regarde si la variance est meilleure que le record précédent (ligne 13), si c'est le cas, on met à jour la meilleure répartition (lignes 15 et 16).
```python=
def optimum(datas: [tuple], k: int, nb_repet: int) -> ([tuple], dict):
"""
Répète nb_repet fois l'algo des k-moyennes sur datas.
Renvoie la liste des coordonnées des centres et le
dictionnaire de répartition des éléments de datas dans
les groupes qui donne la variance la plus faible.
"""
mini = float('inf') # infini
max_iter = 100
for repet in range(nb_repet):
centres, groupes = k_moyennes(datas, k, max_iter)
var = variance(datas, centres, groupes)
if var < mini:
mini = var
best_centres = centres
best_groupes = groupes
return best_centres, best_groupes
```