Méthode des K-means sous python

Tout d’abord bonjour à tous !

Alors voilà, je viens d’aborder en statistiques la méthode des k-means comme classification, et je dois maintenant l’implémenter en python mais je dois admettre que je suis largué.

Je vous explique mon exemple: j’ai à ma disposition un dictionnaire regroupant N vins et 14 informations concernant chaque vin (son Id, son acidité, son ph, s’il est rouge ou blanc, etc…). On cherche donc à regrouper les vins en classes, classes dans lesquelles les informations évoquées sont logiquement homogènes.

Voilà les instructions (conseils) qui m’ont été données:

L’idée est d’estimer les centres µ des clusters à partir de données. On affecte ensuite l’observation au cluster Ck dont le centre µk est le plus proche.

Soit x1, x2, …, xN , l’ensemble de N observations (vins) où chaque observation est un vecteur de dimension d (d informations). Le principe de la méthode K-means est le suivant : — On initialise (au hasard ou non) K centres µ1, µ2, .., µK où chaque centre est également de dimension d. — On calcule la distance entre les N observations et les K centres et on affecte les observations aux centres dont ils sont le plus proche. Puis on redéfinit les centres à partir des observations qui ont été affectées aux différentes classes : ∀k ∈ {1, 2, …, K}, µk = 1 mk P i∈Ck xi avec mk = Card(Ck) — On répète en général plusieurs fois l’étape précédente jusqu’à éteindre un critère convergence donné (à définir) pour ne retenir que la solution la plus optimale selon ce critère.

Certains d’entre vous pourraient-ils m’apporter leur aide pour implémenter cette méthode en python?

Merci d’avance, Alexouu

Salut,

As-tu compris comment l’algorithme fonctionne ? Je te conseille de l’exécuter une fois à la main avec $N$ petit et $d = 2$ (tu te retrouves alors à regrouper des points sur un plan 2D).

Quelle expérience as-tu en Python ?

Salut Vayel !

Oui j’ai compris comment l’algorithme fonctionne. Plusieurs bémols: comment choisir K au début? comment choisir le critère de convergence? (sans trop se compliquer la vie si possible)

J’ai tous les outils pour pouvoir coder cela mais entre la théorie et la pratique …

Edit: Quand j’ai dit que je comprenais comment l’algorithme fonctionne ça voulait aussi dire : pas de problème pour le tester à la main

Dans un premier temps, je te conseille de commencer simple : prends un $K$ arbitraire (en voilà un : $K = 3$) et utilise la distance euclidienne. Pour le critère de convergence, fixe un nombre maximal d’itérations.

Ok super merci !

Sinon pour le code en lui-même, pourrais-tu m’en montrer le début pour que je voie comment commencer s’il te plaît?

Tout est dans ton énoncé :

Le principe de la méthode K-means est le suivant : — On initialise (au hasard ou non) K centres µ1, µ2, .., µK où chaque centre est également de dimension d. — On calcule la distance entre les N observations et les K centres et on affecte les observations aux centres dont ils sont le plus proche. Puis on redéfinit les centres à partir des observations qui ont été affectées aux différentes classes : ∀k ∈ {1, 2, …, K}, µk = 1 mk P i∈Ck xi avec mk = Card(Ck) — On répète en général plusieurs fois l’étape précédente jusqu’à éteindre un critère convergence donné (à définir) pour ne retenir que la solution la plus optimale selon ce critère.

Il te faut donc :

• Un tableau centers pour contenir les centres
• Une fonction dist pour calculer la distance entre un point et un centre
• Une fonction update_centers pour redéfinir les centres
• Une fonction train pour orchestrer le tout (faire la boucle while)

Pour le tableau centers, il faut donc qu’il contienne les K centres? Donc je fais un tableau (liste de listes?) de format K x d?

Yep

J’avance sur plusieurs fonctions à la fois, mais déjà je ne sais pas comment transformer mon dictionnaire initial en N (nombre total de vins) liste de 14 (nombre d’informations par vin) éléments.

D’autant plus que dans le processus il ne faudrait pas modifier la place des clés de départ du dictionnaire.

J’avance sur plusieurs fonctions à la fois, mais déjà je ne sais pas comment transformer mon dictionnaire initial en N (nombre total de vins) liste de 14 (nombre d’informations par vin) éléments.

Tu n’as pas besoin de créer une liste de 14 éléments en tant que valeur de ton dictionnaire, une liste vide suffira,

où tu ajouteras tes éléments selon le besoin.

Par exemple, on peut faire cela,

1
2
3

>>> d = {k: [] for k in range(11)}
>>> d
{0: [], 1: [], 2: [], 3: [], 4: [], 5: [], 6: [], 7: [], 8: [], 9: [], 10: []}

Oui mais ce que je veux faire c’est partir d’un dictionnaire où par exemple N=2 et d=2, mettons:

dict={Id1:1,pH1:6,Id2:2,pH2:7} et aboutir à L=[[Id1,1,pH1,6],[Id2,2,pH2,7]]

Dans L on a bien séparé les vins 1 et 2.

Cependant, je me rends compte que dans la sous-liste L1=[Id1,1,pH1,6] il y aurait en réalité 2*d éléments qui correspondent aux d clés+ les d valeurs du dictionnaire initial.

Dites moi ce que vous en pensez

Merci de votre aide !

Ta structure de données n’est pas assez structurée pour être pratique à utiliser : elle contient toutes les informations au même niveau. Je te conseille d’en concevoir une autre, avec ces critères en tête :

• Tu dois pouvoir facilement accéder à un vecteur (pas sûr que les ids soient nécessaires, tu peux probablement te contenter d’indices de liste)
• Pour les calculs de distance, tu dois pouvoir facilement obtenir un vecteur sous forme de liste de valeurs, avec les champs dans le même ordre pour tous les vecteurs

Ben les ids ce sont des clés existantes de mon dictionnaire d’origine donc je ne comptais pas y toucher.

Sinon pour les calculs de distance, si je ne dis pas de bêtises, sur les 14 infos, 2 sont de type qualitatives (Id+ une autre), donc comment faire?

Sinon concrètement comment me proposes-tu de découper le dictionnaire?

Merci

Je partirai plutôt sur une structure comme

1

vin = {id: None, pH: None}

Après je ne comprends pas de quoi vous parlez, pour moi python ou tous langages objets, est fait pour se rapprocher d’un cas concret, hors si je ne le comprends pas, c’est que c’est trop abstrait. Sans parler technique et syntaxe, expliquer clairement la problématique serait un plus pour avancer.

EDIT: Le début du topic n°1 était clair, le milieu et la fin ne l’était plus…

Pour moi si je ne regarde que le début, ma solution de dictionnaire est viable. Voir un namedTuple, pourquoi pas ?

Je voulais en fait transformer mon dictionnaire de départ en liste(s) car c’est plus facile à manipuler et une fois que c’est fait, on est sûr que les éléments ne bougent plus, alors que dans un dictionnaire l’ordre des clés peut être interverti aléatoirement, ce qui ne m’arrange pas.

Mais effectivement, je comprends que mes explications ont perdu en clarté !

J’ai vraiment du mal à implémenter cette classification, si quelqu’un pouvait me venir en aide

oui la fonction dist je l’ai

def dist(a,b): return np.linalg.norm(a-b)

en ayant importé numpy as np bien sûr

Yep. Il faudra juste veiller à ce que a et b soient des tableaux numpy.

Bloques-tu sur update_centers ? Tu as deux étapes :

1. Associer chaque vecteur à un centre (le plus proche)
2. Redéfinir les centres à partir des vecteurs qui leur sont associés

Pour que a soit soit un tableau numpy il faut qu’il soit de la forme a=np.array?

Donc si je reprends l’exemple de ta matrice data, il faudrait que je la slice en 4 listes avec par exemple a =[1,8,6,7] et b=[1.1,8.3,5.7,7] avec en fait a=data[0] et b=data[1] et ainsi de suite?

(Même si c’est le cas, je ne sais toujours pas comment transformer mon dictionnaire data en ta matrice data !)

Quant à la fonction update_centers yes je bloque:

1. Pour associer chaque vecteur au centre (lui-même vecteur) le plus proche, j’ai donc besoin de calculer, pour chaque vecteur, sa distance aux K centres et de prendre le min (argmin) des K valeurs de distance obtenues je suppose? Ca donnerait un truc du genre, avec mettons K=3 centres

def associer(X, mu):

on a mu=[mu1,mu2,mu3]

1
2
3
4
5

groupe0=[]
groupe1=[]
groupe2=[]
for x in X:
    meilleurmu=min(np.linalg.norm(x-mu[i]),

J’ai pas fini la formule car je ne sais pas l’écrire mais tu vois l’idée: pour chaque x je veux qu’il me trouve le meilleur mu donc un certain mu[i], puis qu’il m’envoie le x correspondant dans le groupei.

1. Après je calcule le barycentre de ces 3 listes et je réitère l’étape 1.

EDIT: Désolé, je ne savais pas que les hashtags rendaient comme ça !

Le plus simple est de ne travailler qu’avec des tableaux numpy :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

>>> import numpy as np
>>> data = [
...     [1, 8, 6, 7],
...     [1.1, 8.3, 5.7, 7],
...     [0.9, 8.2, 5.9, 7.2],
...     [1.3, 7.8, 6.3, 6.9],
... ]
>>> data = np.array(data)
>>> data
array([[1. , 8. , 6. , 7. ],
       [1.1, 8.3, 5.7, 7. ],
       [0.9, 8.2, 5.9, 7.2],
       [1.3, 7.8, 6.3, 6.9]])
>>> a = data[0]
>>> a
array([1., 8., 6., 7.])

(Même si c’est le cas, je ne sais toujours pas comment transformer mon dictionnaire data en ta matrice data !)

Il ressemble à quoi ton dictionnaire de départ ?

Quant à la fonction update_centers yes je bloque

Supposons que les centres sont dans la matrice centers (cf. mon exemple plus haut). Chaque centre est identifié par son indice dans cette matrice. Il te faut donc, pour chaque vecteur, déterminer l’indice du centre le plus proche. Tu obtiens donc une liste de $N$ valeurs (pour chaque vecteur, un centre associé) :

1
2
3
4

vectors_to_centers = []
for vector in data:
    distances = [dist(vector, c) for c in centers]
    vectors_to_centers.append(np.argmin(distances))

Ou, en plus court :

1
2
3
4

vectors_to_centers = np.array([
    np.argmin([dist(vector, c) for c in centers])
    for vector in data
])

Regarde ce que tu obtiens avec les données artificielles ci-dessus pour comprendre ce qu’il se passe.

Comme vectors_to_centers est un tableau numpy, tu peux facilement récupérer les indices des vecteurs associés à un centre particulier (np.where) puis récupérer les vecteurs en question à partir de ces indices (https://docs.scipy.org/doc/numpy-1.13.0/user/basics.indexing.html#index-arrays).