Algorithme des K-moyennes

L'algorithme des k-moyennes

L'algorithme des k-moyennes (k-means) est une algorithme de classification non supervisé. On ne connait pas les classes de l'échantillon et on cherche répartir dans k-classes différentes les éléments.

L'idée est de trouver quels sont les amas (clusters), en cherchant à minimiser les sommes des distances des éléments au centre de la classe (ou amas) à laquelle ils ont été affectés.

Pour cela on procède par itération successives, avec deux étapes à chaques itérations:

  • Assigner chaque Ă©lĂ©ment Ă  une classe, reprĂ©sentĂ©e par le centre duqel il est le plus proche.
  • AmĂ©liorer la position des centre en calculant le barycentre de tous les Ă©lĂ©ments de sa classe, caculĂ©s Ă  l'Ă©tape prĂ©cĂ©dente.

Les itérations s'arrêtent quand les centres sont stabilisés.

Voici une version de cet algorithme sur les 150 iris desquels on a retiré la classe.

Importation des bibliothèques⚓︎

Python
1
import numpy.random as rd  # pour le générateur aléatoire

numpy.random permet l'accès à des fonctions de tirages suivant des loi de probabiltés, comme ici la loi uniforme qui va nous permettre d'obtenir des flottants d'un intervalle \([a,b]\).

Chargement des données⚓︎

Python
1
2
3
4
5
6
# récupération des données sans les classes
with open("iris.csv", "r") as f:
    f.readline()  # Ignorer l'en-tĂŞte
    contenu = f.readlines()
    x = [float(ligne.split(',')[0]) for ligne in contenu]
    y = [float(ligne.split(',')[1]) for ligne in contenu]

Cette partie est ici pour rappel, les lsites x et y seront incluses dans les codes qui suivent.

Recherche des valeurs maximales⚓︎

Python
1
2
3
4
5
k = 3  # nombre de classes supposés
xmin, xmax = min(x), max(x)
ymin, ymax = min(y), max(y)
nb = len(x)
assert nb == len(y)
  • k : Indique le nombre de classes souhaitĂ©es (ici, 3).
  • xmin, xmax, ymin, ymax : DĂ©terminent les valeurs minimales et maximales des coordonnĂ©es x et y.
  • nb : Nombre d'iris (doit ĂŞtre Ă©gal pour x et y).

Génération de moyennes aléatoires⚓︎

Python
1
2
3
4
# Génération de k moyennes aléatoires
means = [[0, 0] for _ in range(k)]
for i in range(k):
    means[i] = rd.uniform(xmin, xmax), rd.uniform(ymin, ymax)

Cette partie crée k moyennes initiales d'une manière aléatoire à l'intérieur des limites trouvées pour x et y.

Initialisation des classes vides⚓︎

Python
1
2
3
# Initialisation des classes vides
c = [[] for _ in range(k)]
precc = [[] for _ in range(k)]  # sert pour stocker la version précédente des classes

Calcul de la distance⚓︎

Python
1
2
3
# calcule de la distance au carré
def distance(x1: float, y1: float, x2: float, y2: float) -> float:
    return (x1 - x2) ** 2 + (y1 - y2) ** 2

Pour rappel

Retourner l'indice minimum⚓︎

On va avoir besoin d'une fonction qui retourne l'indice minimum d'un liste.

Code à compléter

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein Ă©cran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5
.128013oP;f 8lkg5:,bry2a1h3tvw=u6e[(Sn9]_s-c)7imR/4p0d050V0B0v0r0O0h0J0f0L0h0r0J0J0y010v0O0T010406050J0z0P0P0r0o0p040E0b0h0z0:0b0F050R0`0|0~100^0T04051g191j0R1g0^0V0O0w0(0*0,0.0*0F0j0z0r0j0B0K0T0p0v0t170f0t0O0j0t0h1L0t0v0?050Z0n0h0B1s0+0-011K1M1O1M0v1U1W1S0v0o1h1G0(130J0T0r0F0.0q011Y1u010e0#0B0F0r0P0B1S1@1_1~1!211W24260?0a0f0c0o0b0T0b0J0O160F0f0X1=0o0o0B0L2r19290F1h0R1G2E1.1:1/1T0V2b1v0O0F232o1S1p1r0)1Z2O2Q0F0b2U1S0T2x1h2C2E2+0_1^2s2W1 2!0o0}0h1S0r1J2x0e0.030I0I0L2#0B1O2Z0b0K0A0K0s0?0s190r2,2/0@2.2a2;1!2?2^2`2|0B2~01303234362R390K1|040q3f3h1_3j2C2N013o0r2_1h2{0t2}2 31330X3y2!3A0u0?0u3F2B3i0^3J3m0.3M3O053Q3S3u3U3x2P3z3a0S0?0S3%1a3)3k2:1t3n0b2@3N3q3R3s3T3w3W3_3Y3a0k0?0k3 2+3*2/3K3.493=3v3V354f383a0A0?0A4l413+443-463p3P3r3t4t3^373A0N0?0N4C3H4n3l4F3L4H484J4a4L3@4e4O3a0g0?0g4T2D4V432X4Y473/3;4b3?4d4v4*0K0G0?0G4/2E2(0B2E2U2H0V1:2M3,014u2T1q1h562*3i3(3H054u5l2a0O0V0.312C3A3c4J5t5v4}3X4x3b1}2f0B5C4u5E5y1S0R3g423K0L5z030f0Q0Y0b0z0o2Q0f0h002P1p0L1X0P2P2t0B0%0w3N0B5!0%0V000z5$1O0J0v0B5n4:635r2s5B015w2/3A3C3:0f684(4~3`3B5H255J695D4w6c5O5Q4E4?0i0?0X0e655R5e0x0?0f6A6u2=0e0?5*5.18405o6H1!0=040D6G4o5e0F0?0h6V4W4?6S0l656F6Q0.6S0C6#4=2=0n0?0e0h0b0r0v6:3K6S0H0M6*6B4X0b0?0K020j0v0d726,3L6?042P6|6O2D736%0?6)7j3j7p5R6g0I5x3a3!5A5u6o5L6q7w6l265K4N6j7x3F0f7L6+6W4X6Y7g0F0V6M7c7O4?75040y7V6$1 5.0?0U650^7r3J7t7v0K3|7y7G4)6j3|0f5I7@6i4g7;6s047M7N7$3n0?6M0O7#6;1!7Y7!7p848b3-6Z6}5e6.8k4X7(047*7-7W1 6 7+6}7/6b4h3q7t7B4 4i7{6m7}5M8A2E3g837l1 6w040e468a4p6K8U5e0b6D7R8X7P7f0o1_1B8n7m6T8,7%0O3d8/6R0?0m8$4?0F7f2e8?6-0?6U8s858i046!938h016S0M0M7o4m8x7z6a1_3A4z7?7A7H7 4z8G7F9n7^9p81838N7d8Q0O6z8f8O86968 9a0?6/988V7g9H8v9D7d7Y020h7a8`2=872P899L8l7n8w9L8y9j3a4Q9m6h8J0K4Q9r6n9/7C9;9w9x9|9E956L2P9W8c0?8e2+8g9M9!9f9)9h7u8z0K4,9.6p4 4,9?8I9_ag7K9|9x9~3L9Y0Fa93ia78Ya4a295972-7d8m9#7P8WaH8-0H9(aE4o9*0F3A51ah8D6j51al9t7~5FaTap7Las8Q2x0v5!6Na6as7Qa0a.417r0R5q1k2)1959190v5ba 2K2F0r1V57a}5i7,0X0Z0#0J04.

Construction des classes⚓︎

Première des deux étapes de chaque itération, associé à chaque élément i (ici un iris représenté par le couple (x[i],y[i]) à la classe de même indice que le centre dont il est le plus proche.

Code à compléter.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein Ă©cran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5
.128013oP;f 8lkg5:Nj,bry2a1CĂ©h3tvw=u6e[(*SĂ n9]x_s-c)7iqm./4p0d050%0F0z0t0V0h0Q0f0S0h0t0Q0Q0C010z0V0#010406050Q0D0X0X0t0q0r040J0b0h0D0{0b0L050Z12141618100#04051o1h1r0Z1o100%0V0A0:0=0@0_0=0L0j0D0t0j0F0R0#0r0z0x1f0f0x0V0j0x0h1T0x0z0~050+0p0h0F1A0?0^011S1U1W1U0z1$1(1!0z0q1p1O0:1b0Q0#0t0L0_0s011*1C010e0-0F0L0t0X0F1!1 21261,291(2c2e0~0a0f0c0q0b0#0b0Q0V1e0L0f0)1}0q0q0F0S2z1h2h0L1p0Z1O2M1_1{1`1#0%2j1D0V0L2b2w1!1x1z0;1+2W2Y0L0b2$1!0#2F1p2K2M2?11202A2(272,0q150h1!0t1R2F0e0_030P0P0S2-0F1W2+0b0R0U0R0u0~0f0u1h0t2@2`0 2_2i2|1,2~3032340F3601383a3c3e2Z3h0R24040f0s3o3q213s2K2V013x0t311p330x3537393b0)3H2,3J0y3l0y3P2J3r103T3v0_3W3Y053!3$3D3(3G2X3I3i0!3l0!3;1i3?3t2{1B3w0b2 3X3z3#3B3%3F3*433,3i0k3l0k492?3@2`3U3{4j3 3E3)3d4p3g3i0E3l0E4v4b3^4e3`4g3y3Z3A3C4D423f3J0U3l0U4M3R4x3u4P3V4R4i4T4k4V414o4Y3i0g3l0g4%2L4)4d2)4,4h3|3~4l404n4F4@0R0M3l0M4|3S4y3_514S3}4U4m4E3+4H3j0$0~0u0$5e1s2;1h2$2P0%1{2U5h4E2#1y1p2:0F2=3r3=3R054E5L2i0V0%0_392K3J3k4T5T5V575o5Y252n0F5$5n4G5)2M3p4c3U0S5Z030f0v1f0Q1_0D2y0/1(0/3v0F0/2b0f1+1T2c0L0z690:0x0t0W0D1)0V0q0V6233650f2F2:0w0Q2b0z0w1)200q0f0=0f0X0b0r2b2Y6D330#1c0/2:0b0S0x0F5N4}6V5R2A5#015W2`3J3L5k6!4=58443K5*2d5,6#5%5/3i6)0Z5=4O500i0~0)0e6X5?5h0B3l736}2}0e0~3b0L5~0q0D2H3a4e785g4+0}040H0T6X0f744+0b0~0R020j0z0d7s7u6~0S0~0m1f6U4a5O791,7o0l6X107L2L5?6+0P5X3i3.5!5U6?5.593.0f5+5-4X6.7!3P0f7=7t7N0_6 040e4g7D7^3V0~0V7~7m500b76042X834*500L0p0~0q211J7l8b277o0H8j4 2}0~8d8o3U7o0T7Q7T3s8y7V7$6$213J467#7-4?6.467+6;8I6-4q0R8G7;7?8U7E8q041x5~210S668a8p1,7w040C8(8u0~0G8t5h0X0V0~5u8A7 7o0N8.5h8+0I8 4+0L0~0i7R8t7W7Y0R4s8H7%7.8Q4s8M2e8O5(4r1!6{3M8U7?8W1,7`7|0q938c0~0n9y2786811g8y7@842}8e048g1F7K2^8|0~8n8{9J3w968=7n0~8w989U5S8C7X6%4I3z7W7(6.4J9j6=6,9m0R4J5;9q9r9r9t3`0~0O0X9Y507o0o9C9W040ra39H9 018+8-ad7 95042e210Qa48l8:apa99B9%8)0_8}9$9Q4y9a9+3h9-9)9/8Q4!9=9l6^aE9{9}9}aeak8Z0+0L8$aoav8/048;aY5hakauaA8k7O0~8~ai9V0_aga8a08Y6oaU8$asax9Sa|80040Oa 7oa#a*awb082a$9Z040Na7a/a+a@0rb3arba9z88bjbcbe2?9Ibgb0a2bobq3rbsb7akabbo7r8y7Sb60faC8E4^aFaL594_aK9f8J8Q4_9{bG5M3TbJ0L3J5b9e9@aM5bbQb(59b$8TaQaj810Sa?af0~ahbraR9F0%8@9GbH5h8ma aSa_8#8%blaq04bEbrbz5@5_bI0L1x8$2B1)6E6r0K6L6j3d1(6L0f0e1(0D6C666e1+6R0V6zazbXaB9)9b5tbMbR8P5pcLb+6@59cLaOaPb|04b?c9a,a!c4b=boa.c17v0~0Yc%040t0#0#2b0%bo9Tc+bmb9c{caccbyce5Ecg0t0n0b1dcl6D002Xcj1)2C6Ecw0Fcy0fcpcn4e9P4b8A0Z5Q5w5K5y5H1h0z5Bdx2S2N0t1%du0Z5z7S0)0+0-0Q04.

Calcul des nouvelles moyennes (centres de classes)⚓︎

Deuxième étape, une fois les classes établies, on en calcule les barycentres qui deviennent les nouveaux centres.

A compléter.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein Ă©cran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5
.128013oP;f 8lkg5:Nj,bry2a1h3tvw=u6e[(Sn]x_s-c)7im/4p0d050W0D0x0t0Q0h0L0f0N0h0t0L0L0A010x0Q0U010406050L0B0R0R0t0q0r040G0b0h0B0;0b0H050S0{0}0 110_0U04051h1a1k0S1h0_0W0Q0y0)0+0-0/0+0H0j0B0t0j0D0M0U0r0x0v180f0v0Q0j0v0h1M0v0x0@050!0p0h0D1t0,0.011L1N1P1N0x1V1X1T0x0q1i1H0)140L0U0t0H0/0s011Z1v010e0$0D0H0t0R0D1T1^1`1 1#221X25270@0a0f0c0q0b0U0b0L0Q170H0f0Y1?0q0q0D0N2s1a2a0H1i0S1H2F1/1;1:1U0W2c1w0Q0H242p1T1q1s0*1!2P2R0H0b2V1T0U2y1i2D2F2,0`1_2t2X202#0q0~0h1T0t1K2y0e0/030K0K0N2$0D1P2!0b0M0g0M0u0@0u1a0t2-2:0^2/2b2=1#2@2_2{2}0D2 01313335372S3a0M1}040s3g3i1`3k2D2O013p0t2`1i2|0v2~3032340Y3z2#3B0w0@0w3G2C3j0_3K3n0/3N3P053R3T3v3V3y2Q3A3b0T0@0T3(1b3*3l2;1u3o0b2^3O3r3S3t3U3x3X3`3Z3b0k0@0k402,3+2:3L3/4a3?3w3W364g393b0C0@0C4m423,453.473q3Q3s3u4u3_383B0P0@0P4D3I1l2*1a2V2I0W1;2N3-014v2U1r1i2)0D2+3j3)4V4v4:2b0Q0W0/322D3B3d4K4`4|4e4w4P3b3d0f2g0D534v3Y4y3c1T0S3h433L0i0@0Y0e4=2E5k4(0z0@0f5q4^442Y3M0e0@0N3O0N0K271`0L5x5s4G010?040F0O5x5w4F5A0b0@0M020j0x0d5T5M5A0i0N0@0m180D5L5V205P0l5x0_414V3K52014}2:3B3D3;0f5~3^4f563C1~5a5c4O3{6a2F3h0f6j5U4p4(5m040e475(5=3o0@0Q6s6m5N0b5u042Q6x3m5N0H0p0@0q1`1C5;6y5A5P0F6N6F5A0H0@0i6S5z5?0@0O5^5{2E5`2.5}4{5 0K4~3b3#516-67556f3#59265b6.5d4x3!5h6i6k755)2?0@6H0N6E6Z1#5X040A7c4q6I042f6Y3L6Q7n4(6V047b6(5y7o0@0E7q6G6v7A6P0@0I5S7v6*4;6,536:0M3}6?6d686f3}6|277R6_4h7O730475766t0/6o0Q5p7v6l6T78047a7i4(7f5!5$7@5N0R0Q0@0V7D6!046%4n7n666/614i3r8870694j7V6~6^5e3B4j6h7$7%8p776u041c0J7|5W0@7h7.8r3.7k1c821#7p7v8B3M0@8v8I7)5O7y8F3.0@0n8R8P040I8w206o6q0q8Z8s8U8A8O6A6v198+6O7;7u6+8;8G8Q8N8^8S6C8V5P7G5_876@891`3B4A7Q6 6e7Z4A8h7X8k4z7#8p8q8O7s1c0r8(0/7f8z2,7/7d8C0@8E8{7:8_5Q8V7s9o9z9v8W7z9G4q8T8 7F9p018#6r8:9A8}8*9t8J8-6C8/9X9l5D9N049J8@9U8K8~9K4(907H869K887N4R998j713b4R9e9a7S7Z9{3G9j7%8J7s5I0H5K9:5N5P9+7K8|9.6wae7E8X9P9r9Pag9D9x0|8M9$aj7f0S9P7s7?am830oaBau0R9Fax9-azaH7=0p8?ai9-90928I0S4@4W4/4Y4,1a0x4#a%2L2G0t1Wa!0S4Z5`0Y0!0$0L04.

Réinitialiser les classes⚓︎

Une fonction pour vider les classes avant la prochaine itération.

Python
1
2
3
def empty_class() -> None:
    for i in range(k):
        c[i] = []

Cette fonction vide les classes pour préparer la prochaine itération.

Exécution principale⚓︎

Et on assemble le tout.

Les itérations : calculs des classes, calculs des moyennes, vidage des classes continue en boucle jusqu'à ce que les k-moyennes ne changent plus.

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
construct_class()
for i in range(k):
    print(c[i])
    print(means[i])

cont = True
while cont:
    means_prec = means.copy()
    empty_class()
    construct_class()
    calc_means()  # nouvelles moyennes
    # vérification si les centres évoluent
    cont = False
    for i in range(k):
        if means_prec[i] != means[i]:
            cont = True  # besoin de continuer