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
.128013it3a;dv,n2SR5wbcy14: f-up08)_9eklohrP=[s6(]/mg7050g0F0c0e0b0H0O0v0q0H0e0O0O0M010c0b0z010406050O0y0T0T0e0K0r040l0I0H0y0:0I0j050S0`0|0~100^0z04051g191j0S1g0^0g0b0h0(0*0,0.0*0j0U0y0e0U0F0x0z0r0c0J170v0J0b0U0J0H1L0J0c0?050Z0p0H0F1s0+0-011K1M1O1M0c1U1W1S0c0K1h1G0(130O0z0e0j0.0k011Y1u010w0#0F0j0e0T0F1S1@1_1~1!211W24260?0a0v0L0K0I0z0I0O0b160j0v0X1=0K0K0F0q2r19290j1h0S1G2E1.1:1/1T0g2b1v0b0j232o1S1p1r0)1Z2O2Q0j0I2U1S0z2x1h2C2E2+0_1^2s2W1 2!0K0}0H1S0e1J2x0w0.030D0D0q2#0F1O2Z0I0x0P0x0s0?0s190e2,2/0@2.2a2;1!2?2^2`2|0F2~01303234362R390x1|040k3f3h1_3j2C2N013o0e2_1h2{0J2}2 31330X3y2!3A0d0?0d3F2B3i0^3J3m0.3M3O053Q3S3u3U3x2P3z3a0t0?0t3%1a3)3k2:1t3n0I2@3N3q3R3s3T3w3W3_3Y3a0n0?0n3 2+3*2/3K3.493=3v3V354f383a0P0?0P4l413+443-463p3P3r3t4t3^373A0V0?0V4C3H4n3l4F3L4H484J4a4L3@4e4O3a0B0?0B4T2D4V432X4Y473/3;4b3?4d4v4*0x0E0?0E4/2E2(0F2E2U2H0g1:2M3,014u2T1q1h562*3i3(3H054u5l2a0b0g0.312C3A3c4J5t5v4}3X4x3b1}2f0F5C4u5E5y1S0S3g423K0q5z030v0m0Y0I0y0K2Q0v0H02030d0E0f2P1p0q1X0T2P2t0F0%0h3N0F5!0%0g5)5+0f0y5$1O0O0c0F5n4:695r2s5B015w2/3A3C3:0v6e4(4~3`3B5H255J6f5D4w6i5O5Q4E4?0G0?0X0w6b5R5e0o0?0v6G6A2=0w0?5.5=18405o6N1!0=040Q6M4o5e0j0?0H6#4W4?6Y0u6b6L6W0.6Y0N6+4=2=0p0?0w0H0I0e0c6_3K6Y0R0C6:6H4X0I0?0x020U0c0f786=3L6|042P726U2D796-0?6/7p3j7v5R6m0D5x3a3!5A5u6u5L6w7C6r265K4N6p7D3F0v7R6;6$4X6(7m0j0g6S7i7U4?7b040M7#6,1 5=0?0A6b0^7x3J7z7B0x3|7E7M4)6p3|0v5I7}6o4g7`6y047S7T7,3n0?6S0b7+6`1!7(7*7v8a8h3-6)735e6@8q4X7.047:7?7$1 757;737^6h4h3q7z7H4 4i816s835M8G2E3g897r1 6C040w468g4p6Q8!5e0I6J7X8%7V7l0K1_1B8t7s6Z8=7-0b3d8^6X0?0i8,4?0j7l2e8|6?0?6!8y8b8o046*998n016Y0C0C7u4m8D7F6g1_3A4z7|7G7N854z8M7L9t7~9v87898T7j8W0b6F8l8U8c9c959g0?6^9e8#7m9N8B9J7j7(020H7g902=8d2P8f9R8r7t8C9R8E9p3a4Q9s6n8P0x4Q9x6t9^7I9`9C9Da29K9b6R2P9$8i0?8k2+8m9S9*9l9/9n7A8F0x4,9@6v4 4,9|8O9 am7Qa29Da43L9(0jaf3iad8(aaa89b9d2-7j8s9+7V8$aN8?0R9.aK4o9:0j3A51an8J6p51ar9z845FaZav7Ray8W2x0c5!6Tacay7Wa6a@417x0S5q1k2)1959190c5bb52K2F0e1V57b35i7=0X0Z0#0O04.

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
.128013Cit3a;dv,n2.S5éwb*cy14q: f-up08)_j9eklNohxrP=[sà6(]/mg7050h0K0d0f0c0M0V0z0t0M0f0V0V0T010d0c0D010406050V0C0#0#0f0R0u040n0O0M0C0{0O0k050!12141618100D04051o1h1r0!1o100h0c0i0:0=0@0_0=0k0$0C0f0$0K0B0D0u0d0P1f0z0P0c0$0P0M1T0P0d0~050+0r0M0K1A0?0^011S1U1W1U0d1$1(1!0d0R1p1O0:1b0V0D0f0k0_0l011*1C010A0-0K0k0f0#0K1!1 21261,291(2c2e0~0a0z0S0R0O0D0O0V0c1e0k0z0)1}0R0R0K0t2z1h2h0k1p0!1O2M1_1{1`1#0h2j1D0c0k2b2w1!1x1z0;1+2W2Y0k0O2$1!0D2F1p2K2M2?11202A2(272,0R150M1!0f1R2F0A0_030H0H0t2-0K1W2+0O0B0%0B0v0~0z0v1h0f2@2`0 2_2i2|1,2~3032340K3601383a3c3e2Z3h0B24040z0l3o3q213s2K2V013x0f311p330P3537393b0)3H2,3J0e3l0e3P2J3r103T3v0_3W3Y053!3$3D3(3G2X3I3i0w3l0w3;1i3?3t2{1B3w0O2 3X3z3#3B3%3F3*433,3i0o3l0o492?3@2`3U3{4j3 3E3)3d4p3g3i0X3l0X4v4b3^4e3`4g3y3Z3A3C4D423f3J0%3l0%4M3R4x3u4P3V4R4i4T4k4V414o4Y3i0F3l0F4%2L4)4d2)4,4h3|3~4l404n4F4@0B0J3l0J4|3S4y3_514S3}4U4m4E3+4H3j0E0~0v0E5e1s2;1h2$2P0h1{2U5h4E2#1y1p2:0K2=3r3=3R054E5L2i0c0h0_392K3J3k4T5T5V575o5Y252n0K5$5n4G5)2M3p4c3U0t5Z030z0b1f0V1_0C2y0/1(0/3v0K0/2b0z1+1T2c0k0d690:0P0f0x0C1)0c0R0c6233650z2F2:0p0V2b0d0p1)200R0z0=0z0#0O0u2b2Y6D330D1c0/2:0O0t0P0K5N4}6V5R2A5#015W2`3J3L5k6!4=58443K5*2d5,6#5%5/3i6)0!5=4O500L0~0)0A6X5?5h0q3l736}2}0A0~3b0k5~0R0C2H3a4e785g4+0}040Y0G6X0z744+0O0~0B020$0d0g7s7u6~0t0~0N1f6U4a5O791,7o0y6X107L2L5?6+0H5X3i3.5!5U6?5.593.0z5+5-4X6.7!3P0z7=7t7N0_6 040A4g7D7^3V0~0c7~7m500O76042X834*500k0r0~0R211J7l8b277o0Y8j4 2}0~8d8o3U7o0G7Q7T3s8y7V7$6$213J467#7-4?6.467+6;8I6-4q0B8G7;7?8U7E8q041x5~210t668a8p1,7w040T8(8u0~0U8t5h0#0c0~5u8A7 7o0Z8.5h8+0s8 4+0k0~0L7R8t7W7Y0B4s8H7%7.8Q4s8M2e8O5(4r1!6{3M8U7?8W1,7`7|0R938c0~0I9y2786811g8y7@842}8e048g1F7K2^8|0~8n8{9J3w968=7n0~8w989U5S8C7X6%4I3z7W7(6.4J9j6=6,9m0B4J5;9q9r9r9t3`0~0Q0#9Y507o0j9C9W040ua39H9 018+8-ad7 95042e210Va48l8:apa99B9%8)0_8}9$9Q4y9a9+3h9-9)9/8Q4!9=9l6^aE9{9}9}aeak8Z0+0k8$aoav8/048;aY5hakauaA8k7O0~8~ai9V0_aga8a08Y6oaU8$asax9Sa|80040Qa 7oa#a*awb082a$9Z040Za7a/a+a@0ub3arba9z88bjbcbe2?9Ibgb0a2bobq3rbsb7akabbo7r8y7Sb60zaC8E4^aFaL594_aK9f8J8Q4_9{bG5M3TbJ0k3J5b9e9@aM5bbQb(59b$8TaQaj810ta?af0~ahbraR9F0h8@9GbH5h8ma aSa_8#8%blaq04bEbrbz5@5_bI0k1x8$2B1)6E6r0W6L6j3d1(6L0z0A1(0C6C666e1+6R0c6zazbXaB9)9b5tbMbR8P5pcLb+6@59cLaOaPb|04b?c9a,a!c4b=boa.c17v0~0mc%040f0D0D2b0hbo9Tc+bmb9c{caccbyce5Ecg0f0I0O1dcl6D02030e0J0g2Xcj1)2C6Ecw0Kcy0zcpcn4e9P4b8A0!5Q5w5K5y5H1h0d5BdB2S2N0f1%dy0!5z7S0)0+0-0V04.

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
.128013it3a;dv,n2S5wbcy14: f-up08)_jeklNohxrP=[s6(]/mg7050g0E0c0e0b0G0P0u0p0G0e0P0P0N010c0b0y010406050P0x0U0U0e0L0q040l0I0G0x0;0I0j050T0{0}0 110_0y04051h1a1k0T1h0_0g0b0h0)0+0-0/0+0j0V0x0e0V0E0w0y0q0c0J180u0J0b0V0J0G1M0J0c0@050!0o0G0E1t0,0.011L1N1P1N0c1V1X1T0c0L1i1H0)140P0y0e0j0/0k011Z1v010v0$0E0j0e0U0E1T1^1`1 1#221X25270@0a0u0M0L0I0y0I0P0b170j0u0Y1?0L0L0E0p2s1a2a0j1i0T1H2F1/1;1:1U0g2c1w0b0j242p1T1q1s0*1!2P2R0j0I2V1T0y2y1i2D2F2,0`1_2t2X202#0L0~0G1T0e1K2y0v0/030C0C0p2$0E1P2!0I0w0A0w0r0@0r1a0e2-2:0^2/2b2=1#2@2_2{2}0E2 01313335372S3a0w1}040k3g3i1`3k2D2O013p0e2`1i2|0J2~3032340Y3z2#3B0d0@0d3G2C3j0_3K3n0/3N3P053R3T3v3V3y2Q3A3b0s0@0s3(1b3*3l2;1u3o0I2^3O3r3S3t3U3x3X3`3Z3b0m0@0m402,3+2:3L3/4a3?3w3W364g393b0Q0@0Q4m423,453.473q3Q3s3u4u3_383B0W0@0W4D3I1l2*1a2V2I0g1;2N3-014v2U1r1i2)0E2+3j3)4V4v4:2b0b0g0/322D3B3d4K4`4|4e4w4P3b3d0u2g0E534v3Y4y3c1T0T3h433L0F0@0Y0v4=2E5k4(0n0@0u5q4^442Y3M0v0@0p3O0p0C271`0P5x5s4G010?040R0B5x5w4F5A0I0@0w020V0c0f5T5M5A0F0p0@0H180E5L5V205P0t5x0_414V3K52014}2:3B3D3;0u5~3^4f563C1~5a5c4O3{6a2F3h0u6j5U4p4(5m040v475(5=3o0@0b6s6m5N0I5u042Q6x3m5N0j0o0@0L1`1C5;6y5A5P0R6N6F5A0j0@0F6S5z5?0@0B5^5{2E5`2.5}4{5 0C4~3b3#516-67556f3#59265b6.5d4x3!5h6i6k755)2?0@6H0p6E6Z1#5X040N7c4q6I042f6Y3L6Q7n4(6V047b6(5y7o0@0O7q6G6v7A6P0@0S5S7v6*4;6,536:0w3}6?6d686f3}6|277R6_4h7O730475766t0/6o0b5p7v6l6T78047a7i4(7f5!5$7@5N0U0b0@0z7D6!046%4n7n666/614i3r8870694j7V6~6^5e3B4j6h7$7%8p776u041c0K7|5W0@7h7.8r3.7k1c821#7p7v8B3M0@8v8I7)5O7y8F3.0@0D8R8P040S8w206o6q0L8Z8s8U8A8O6A6v198+6O7;7u6+8;8G8Q8N8^8S6C8V5P7G5_876@891`3B4A7Q6 6e7Z4A8h7X8k4z7#8p8q8O7s1c0q8(0/7f8z2,7/7d8C0@8E8{7:8_5Q8V7s9o9z9v8W7z9G4q8T8 7F9p018#6r8:9A8}8*9t8J8-6C8/9X9l5D9N049J8@9U8K8~9K4(907H869K887N4R998j713b4R9e9a7S7Z9{3G9j7%8J7s5I0j5K9:5N5P9+7K8|9.6wae7E8X9P9r9Pag9D9x0|8M9$aj7f0T9P7s7?am830iaBau0U9Fax9-azaH7=0o8?ai9-90928I0T4@4W4/4Y4,1a0c4#a%2L2G0e1Wa!0T4Z5`0Y0!0$0P04.

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