Comment implémenter K-means en Python ?

Version imprimable

Bonjour,

J'essaie d'implémenter le K-means pour un exemple simple.
a = (1,1)
b = (2,1)
c = (4,4)
d = (5,4)

Je suis à l'étape 2: j'ai calculé la distance euclidienne et j'ai déterminé la distance minimale. J'ai ensuite déterminé quels sont les points les plus proches des centres. MAIS le problème c'est que ma boucle n'est pas bien faite, ça ne marche que pour K=2 càd 2 clusters au début.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 # Calculer la distance euclidienne(centres_initiaux, points_restants) liste_distances = [] print("Distance Euclidienne :") for c in centres_initiaux: for pt in points_restants: distance_euclidienne = round(sqrt( (c[0]-pt[0])**2 + (c[1]-pt[1])**2 ),2) # c[0] pt[0], c[1] pt[1] print("de(",c,",",pt, ") = ", distance_euclidienne) liste_distances.append(distance_euclidienne) # Déterminer la distance minimale i = 0 while i < K: if liste_distances[i] < liste_distances[i+2]: # de(i) print(points_restants[i],"est plus proche de ",centres_initiaux[i]) # centre 0 else: print(points_restants[i],"est plus proche de ",centres_initiaux[1]) # centre 1 i = i+1
Je n'arrive pas à savoir comment changer cette boucle.
Merci

17/10/2016, 19h52
dividee
Bonjour,

Le problème c'est que tu tapes les distances entre les points et les centres des clusters dans une liste, alors que tu as besoin par après de retrouver quel distance correspond à quel point et à quel centre. Ces informations se trouvent certes encodées dans l'indice de la liste mais il faut jongler avec de l'arithmétique sur les indices pour les retrouver. C'est compliqué...

Tu as besoin d'un résultat pour chaque point, donc ce serait plus facile en faisant une boucle extérieure sur les points, plutôt que sur les centres.
Quand tu as inversé tes boucles, tu peux te rendre comptes que tu n'as pas besoin de garder toutes les distances calculées dans une liste, tu peux calculer le centre le plus proche directement à l'intérieur de la boucle.

Pour calculer le centre le plus proche pour un nombre quelconque de clusters, tu auras besoin de la fonction min. Il y a en particulier un argument de cette fonction qui peut bien t'aider, c'est l'argument key qui indique comment comparer les éléments: min(sequence, key=f) retourne l'élément de sequence pour lequel la fonction f est minimum.

Donc cela donne (en transformant distance_euclidienne en une fonction):
Code:

1 2 3 for pt in points_restants: centre_le_plus_proche = min(centres_initiaux, key=lambda c: distance_euclidienne(pt,c)) print(pt, "est plus proche de", centre_le_plus_proche)
19/10/2016, 17h09
geeka

Merci beaucoup!
J'ai échanger les boucles, ça marche mieux :D

Après, j'ai une erreur sur :
centre_le_plus_proche = min(centres_initiaux, key=lambda c: distance_euclidienne(pt,c))
TypeError: 'float' object is not callable
19/10/2016, 22h37
dividee
Comme je l'ai écrit, c'est en transformant distance_euclidienne en une fonction:
Code:

1 2 def distance_euclienne(pt1, pt2): ....

Merci beaucoup.
J'ai corrigé ça, du coup j'ai une distance euclidienne minimale calculée pour tout K.:D
Il me reste un souci (enfin plusieurs :oops:), dans mon code actuel, j'ajoutais les centres à chaque ajout de la valeur de K, ça converge mais tout le code doit être modifié à chaque fois.
Maintenant, avec la modification, j'ai une distance minimale bien faite, l'étape suivante est de déterminer les classes. Je trouve un souci :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
for pt in points_restants:  # MAJ
         for c in centres_initiaux:
                                centre = [c]
                                def distance_euclidienne(pt,c) :
                                    return round(sqrt( (c[0]-pt[0])**2  +  (c[1]-pt[1])**2 ),2)
 
                                centre_le_plus_proche = min(centres_initiaux, key=lambda c: distance_euclidienne(pt,c))
                                j = 1
                                while (centre_le_plus_proche == c):
                                    print(pt, "est plus proche de", centre_le_plus_proche)
                                    centre.append(pt)
                                    print("CLASSE ",j,": ",centre)
                                    print("---------------------------")
                                    break
                                    j = j+1

Le résultat :
CLASSE 1 : [(3.0, 2.0), (4.0, 4.0)]
---------------------------
CLASSE 1 : [(3.0, 2.0), (5.0, 4.0)]
---------------------------

Ce que je dois avoir :
CLASSE 1 : [(3.0, 2.0), (4.0, 4.0), (5.0, 4.0)]

Normalement, avec append je ne dois pas écraser les valeurs.

20/10/2016, 17h51
wiztricks
Citation:

Envoyé par geeka

Normalement, avec append je ne dois pas écraser les valeurs.

Il faut apprendre à debugger votre code(*).
Par exemple en ajoutant des "print":
Code:

1 2 3 4 5 for pt in points_restants: # MAJ print (pt) for c in centres_initiaux: print('centre', c) centre = [c]
vous allez réaliser que votre boucle est mal construite.
(*) il existe des modules externes qui calculent déjà k-means. Le k-mean que vous écrivez, c'est pour vous entraîner à programmer. Et apprendre à débugger fait partie de l'exercice.

- W
21/10/2016, 15h38
geeka

Avec les prints, je vois bien où ça bug merci :D
En fait :

Citation:

Centres initiaux : [(3.0, 2.0), (1.0, 1.0), (2.0, 1.0)]
centres_initiaux MAJ [(3.0, 2.0), (1.0, 1.0), (2.0, 1.0)]
(4.0, 4.0)
centre (3.0, 2.0)
CLASSE 1 [(3.0, 2.0), (4.0, 4.0)]
centre (1.0, 1.0)
CLASSE 2 [(1.0, 1.0)]
centre (2.0, 1.0)
CLASSE 3 [(2.0, 1.0)]
(5.0, 4.0)
centre (3.0, 2.0)
CLASSE 1 [(3.0, 2.0), (4.0, 4.0), (5.0, 4.0)]
centre (1.0, 1.0)
CLASSE 2 [(1.0, 1.0)]
centre (2.0, 1.0)
CLASSE 3 [(2.0, 1.0)]
-------------------------------------- REPEAT----------------------
GC : [(4.0, 3.33), (1.0, 1.0), (2.0, 1.0)]
centres_initiaux MAJ [(4.0, 3.33), (1.0, 1.0), (2.0, 1.0)]
(4.0, 4.0)
centre (4.0, 3.33)
CLASSE 1 [(4.0, 3.33), (4.0, 4.0)]
centre (1.0, 1.0)
CLASSE 2 [(1.0, 1.0)]
centre (2.0, 1.0)
CLASSE 3 [(2.0, 1.0)]
(5.0, 4.0)
centre (4.0, 3.33)
CLASSE 1 [(4.0, 3.33), (4.0, 4.0), (5.0, 4.0)]
centre (1.0, 1.0)
CLASSE 2 [(1.0, 1.0)]
centre (2.0, 1.0)
CLASSE 3 [(2.0, 1.0)]
(3.0, 2.0)
centre (4.0, 3.33)
CLASSE 1 [(4.0, 3.33)]
centre (1.0, 1.0)
CLASSE 2 [(1.0, 1.0)]
centre (2.0, 1.0)
CLASSE 3 [(2.0, 1.0), (4.0, 4.0), (5.0, 4.0), (3.0, 2.0)]

Après Repeat, je ne comprends pas pourquoi la classe 1 se vide et pourquoi ses valeurs vont dans la classe 3.
Vous pouvez voir les valeurs GC qui sont en fait les centres de gravité des classes. Avant Repeat c'est correct, après Repeat la classe 1 change soudainement de valeurs :calim2:
J'ai calculé ça à la main, la boucle pt donne bien les points restants, le problème est nouveau de la classe 1 qui donne ses valeurs à classe 3.
21/10/2016, 17h19
wiztricks

Citation:

Envoyé par geeka

Vous pouvez voir les valeurs GC qui sont en fait les centres de gravité des classes. Avant Repeat c'est correct, après Repeat la classe 1 change soudainement de valeurs :calim2:

Ce "REPEAT" dit surtout que vous n'exécutez pas votre code dans un environnement standard mais depuis un IDE qui redémarre votre code dans un contexte que lui seul connaît. Le plus simple dans ces cas là est de lancer votre programme depuis une console avec la commande "$ python (ou python3) script.py".

- W
21/10/2016, 17h49
geeka

J'exécute le code depuis l'IDLE de Python.
J'ai essayé en console, je ne vois pas ce que ça m'apporte, j'ai la ligne qui ressort et c'est tout. Pas de résultats visibles.
21/10/2016, 19h27
wiztricks

Citation:

Envoyé par geeka

J'exécute le code depuis l'IDLE de Python.
J'ai essayé en console, je ne vois pas ce que ça m'apporte, j'ai la ligne qui ressort et c'est tout. Pas de résultats visibles.

Un test valide (ou pas) une hypothèse.... Et si le comportement que vous constatez en lançant votre code depuis la console est identique à celui que vous constatez depuis IDLE, c'est que le message REPEAT vient de votre programme.
Et si vous voulez "comprendre" son comportement étrange, il va falloir relire les instructions que vous avez écrites et ajouter encore des "print" pour comprendre si elles font vraiment ce que vous pensez. Vous pouvez aussi le poster en espérant qu'une âme courageuse ait le temps d'y jeter un oeil.

- W

Merci pour le conseil sur les print!
J'ai trouvé la ligne qui pause problème. Le problème se situe au niveau du TEMP. J'utilise une liste temp pour sauvegarder les points les plus proches du centre, si je l'enlève, j'écrase le point le plus proche déjà trouvé.
Là y a un problème. C'est par hasard que j'ai pensé à faire un temp mais finalement à un moment donné ça devient faux peut-être parce qu'il ne supporte pas de garder en mémoire des valeurs de classes différentes. Je ne vois absolument pas comment faire.

Code:

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
 
                               centre_le_plus_proche = min(centres_initiaux, key=lambda c: distance_euclidienne(pt,c))
 
                                if (centre_le_plus_proche == c ):
                                    print(pt, "est plus proche de", centre_le_plus_proche)
 
                                    temp.append(pt)
                                    print("TEMP--------",temp)
                                    centre+= temp
 
 
                                    print("CLASSE ",ij," ",centre)
 
                                    ij = ij+1
 
                                    gc1 = []
                                    coord_x_centre = []
                                    coord_y_centre = []
 
                                    i = 0
                                    while i <= len(centre)-1:
                                        coord_x_centre.append(centre[i][0])
 
                                        coord_y_centre.append(centre[i][1])
                                        i = i+1
 
                                    # Calculer le g
                                    gc1 = [(round(sum(coord_x_centre)/len(centre),2), round(sum(coord_y_centre)/len(centre),2))]
 
                                    liste_gc += (gc1)
 
 
                                else:
 
                                    print("CLASSE ",ij," ",centre)
 
 
                                    ij = ij+1
 
                                    gc2 = []
                                    coord_x_centre = []
                                    coord_y_centre = []
 
                                    i = 0
                                    while i <= len(centre)-1:
                                        coord_x_centre.append(centre[i][0])
 
                                        coord_y_centre.append(centre[i][1])
                                        i = i+1
                                    # Calculer le g
                                    gc2 = [(round(sum(coord_x_centre)/len(centre),2), round(sum(coord_y_centre)/len(centre),2))]
 
                                    liste_gc +=(gc2)
 
    # ETAPE 4 : Répéter jusqu'à ci = ci+1
 
    print ("-------------------------------------- REPEAT----------------------")
    print("GC : ",liste_gc) 
 
    centres_initiaux = liste_gc  # MAJ

Merci