Un premier exemple⚓︎
Définition des éléments étudiés⚓︎
Représentation des éléments
Pour ce TP, nous considérerons majoritairement des éléments représentés par un couple de deux nombres, comme (3.45, 5.67).
Un exemple sera un couple contenant un élément et sa catégorie, comme ((3.45, 5.67), 'avion'). L'élément est (3.45, 5.67) et la catégorie est 'avion'.
Un échantillon sera un dictionnaire où chaque catégorie est associée à une liste d'éléments.
Définition de l'exemple
Afin de tester nos fonctions, nous allons générer des exemples en partageant un carré de côté \(100\) en 4 carrés numérotés de 0 à 3. La catégorie d'un point sera le nombre associé au sous-carré. Le coin inférieur gauche servira d'origine du repère.
Les coordonnées du carré seront définis à l'aide des constantes suivantes :
xmin = 0
xmax = 100
ymin = 0
ymax = 100
xmoy = (xmax+xmin)/2
ymoy = (ymax+ymin)/2
Ces variables globales sont prédéfinies dans toutes les IDE concernant cet exemple, mais vous pouvez les modifier en les redéfinissant en début de fichier.
Exercice 1
Écrire une fonction generation_echantillon qui prend en paramètre un entier n et qui renvoie un dictionnaire correspondant à un échantillon contenant les catégories 0 à 3, avec n points pour chacune.
Vous pouvez utiliser la fonction uniform(a, b) du module random qui tire un réel au hasard compris entre a et b inclus.
Importation d'une fonction d'un module
Lorsqu'on ne veut utiliser quelques fonctions définie dans un module, on peut l'importer explicitement :
Importation de la fonction uniform
>>> from random import uniform
>>> uniform(5, 10)
8.667460396628535
>>> uniform(5, 10)
5.846308916570904
Indications pour les coordonnées de chaque catégorie
Pour déterminer les valeurs minimales et maximales pour les coordonnées de chaque catégorie, on utilise la division euclidienne, comme on le faisait pour trouver la ligne et la colonne d'une case d'un tableau à 2 dimensions à partir de l'indice de la case associée dans un tableau à 1 dimension.
On utilise le quotient de la division par 2 pour la ligne et le reste de la division par 2 pour la colonne.
Exemples d'utilisation
>>> generation_echantillon(2)
{0: [(27.762650624230396, 25.20359285195414),
(3.605324504341562, 33.4065781204959)],
1: [(69.81709501025465, 38.9218695667356),
(63.79188810839042, 24.611569414080282)],
2: [(9.432136187628027, 57.67143576793811),
(27.89754878233496, 72.72498286968712)],
3: [(69.49185092272312, 57.480508827597795),
(74.63735833708166, 77.51133144667148)]}
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
.128013 )3=9x+lwn%8gv,S."5/:rf7uemkdas p
h*10itP(_y2[46cb]o 030w0t0H0x0G0b0y0z0Q0b0x0y0y070l0H0G0A0l020B030y0s0u0u0x0p0L020j0T0b0s0-0T0d030n0@0_0{0}0=0A02031d161g0n1d0=0w0G0h0$0'0)0+0C0G0g0C0b1u0C0H0:030X0R0b0t1p0(0*0l1t1v1x1v0H1D1F1B0H0p1e0H0C0$100y0A0x0d0+0M0l1H1r0l0q0Z0t0d0x0u0t1B1!1$1*1J1-1F1:1=0:040z0I0p0T0A0T0y0G130d0z0V1Y0p0p0t0Q2a161^0d1e0n1W2n1T1V1U1C0w1`0+1x0d1/271B1m1o0%1I2x0G2z0d0T2D1B0A2g1e2l2n2R0?1#2b2F1+2K0p0`0b0:0z0E2k2V0;2U1_2X1J2Z2#2%0M2)1$2+2l2w0l2:0x2$020z062@2m0=2`2.0+2}2 0z0O332_2V2{392%0m3d353f372|0T2!2~2%0P3k2,2W1q2/3p2;300r3u363x383z3r300f3D3m3F3o3q3a083L2-3N3h020E0F3S3w2G3O3A0E2(172*3l3T3#3V0E2?3)2^3+3!2Y3H2 0E323;343v3g3_0:0E3c3}3e3,3^3P423j453?40493W3t451h2P162D2q0w1V2v3n0Q2L1?1e4m1f4k2T4i4s0V2Q3M3#0v0d0:0q240u3d0z3 3n0d4H020p1$0w0T4L454N3E4F4R0G0u260p0H4M4O3U0:0s0d0G0q3z3k4d3n0v0:0V0q4+4!2Y0q0:0g1/0t4T2a0K2h0C1$0-0b0b143d4,3#0/020J5g4 2/0:154i5n0+5j050o3k0z5y4Z4E2Y0:595b0Z5e5q2R5A471J0T0:074~5B2/0R4{0G2i5m5R5t0:0J055x5z5h1+4`024=0p5Q5L380:0Q5.3@5M0c0:2I5?3g5T4S1$535X5/0l5j5l5r5Y0l0u0G0:442T5s640:5v5%5z5'6f4R1x0y0H0t5|3n5N025P4Y5(1J5j0N0S6j6k5K5@5:02093(5J6y0+6u6w6L6m0:096a5I2*6F2{6u0a6s4-6I0u0T0L626G0l6u0D6*2{656/4P5;6=3N6u0e6^3#6a0:3:6e685u6D6k6M2|6S706W766O6#3-6S6K7a6f6Z7d5C6%6(746l684R0L7g2^6X6t5O7k5o020L6U7y6N0:6!6x6R7A6'6)67636-6|1+6;7M6+4R5=7S6Y0:0n0n7P1J6~02792^76734c6E7p637r7(2m7v6_7x7H7q0:7s7D6,7F7}7r7K7o5y765*5,805`7}0T5_025{7_7/5~4T0d617W3n7R717/5p7#5Z026i7,7-6E764R098a7^6Q7`024/4;4?8l3N8n2*8y7f8r6g020i886I7;4D637+2R0B8w8x7I7L8D7N8C7h8E8G5,4X8o6+8L7)8%7t2m7*0:8S8f7T7{8V8`8t838$8E6o6q8P6u0k8P4R0x0A0A1/0w8P65668:3g6S9i8{8T8'8M6f5u5$8v7-8N025E0d5c5H9o020N9b6@8J5i0:6C8}7X6v8T966r9w7?4F0:2g0H0s0p6V7u9y9A9C5f4c164B0t2n2O9-4l1n4n2q2t2o0x1E9:0n4m0=9}0W0Y0!02.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
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
.128013 )3=9x+lwn%8gv,S."5/:rf7uemkdas p
h*10itP(_y2[46cb]o 030w0t0H0x0G0b0y0z0Q0b0x0y0y070l0H0G0A0l020B030y0s0u0u0x0p0L020j0T0b0s0-0T0d030n0@0_0{0}0=0A02031d161g0n1d0=0w0G0h0$0'0)0+0C0G0g0C0b1u0C0H0:030X0R0b0t1p0(0*0l1t1v1x1v0H1D1F1B0H0p1e0H0C0$100y0A0x0d0+0M0l1H1r0l0q0Z0t0d0x0u0t1B1!1$1*1J1-1F1:1=0:040z0I0p0T0A0T0y0G130d0z0V1Y0p0p0t0Q2a161^0d1e0n1W2n1T1V1U1C0w1`0+1x0d1/271B1m1o0%1I2x0G2z0d0T2D1B0A2g1e2l2n2R0?1#2b2F1+2K0p0`0b0:0z0E2k2V0;2U1_2X1J2Z2#2%0M2)1$2+2l2w0l2:0x2$020z062@2m0=2`2.0+2}2 0z0O332_2V2{392%0m3d353f372|0T2!2~2%0P3k2,2W1q2/3p2;300r3u363x383z3r300f3D3m3F3o3q3a083L2-3N3h020E0F3S3w2G3O3A0E2(172*3l3T3#3V0E2?3)2^3+3!2Y3H2 0E323;343v3g3_0:0E3c3}3e3,3^3P423j453?40493W3t451h2P162D2q0w1V2v3n0Q2L1?1e4m1f4k2T4i4s0V2Q3M3#0v0d0:0q240u3d0z3 3n0d4H020p1$0w0T4L454N3E4F4R0G0u260p0H4M4O3U0:0s0d0G0q3z3k4d3n0v0:0V0q4+4!2Y0q0:0g1/0t4T2a0K2h0C1$0-0b0b143d4,3#0/020J5g4 2/0:154i5n0+5j050o3k0z5y4Z4E2Y0:595b0Z5e5q2R5A471J0T0:074~5B2/0R4{0G2i5m5R5t0:0J055x5z5h1+4`024=0p5Q5L380:0Q5.3@5M0c0:2I5?3g5T4S1$535X5/0l5j5l5r5Y0l0u0G0:442T5s640:5v5%5z5'6f4R1x0y0H0t5|3n5N025P4Y5(1J5j0N0S6j6k5K5@5:02093(5J6y0+6u6w6L6m0:096a5I2*6F2{6u0a6s4-6I0u0T0L626G0l6u0D6*2{656/4P5;6=3N6u0e6^3#6a0:3:6e685u6D6k6M2|6S706W766O6#3-6S6K7a6f6Z7d5C6%6(746l684R0L7g2^6X6t5O7k5o020L6U7y6N0:6!6x6R7A6'6)67636-6|1+6;7M6+4R5=7S6Y0:0n0n7P1J6~02792^76734c6E7p637r7(2m7v6_7x7H7q0:7s7D6,7F7}7r7K7o5y765*5,805`7}0T5_025{7_7/5~4T0d617W3n7R717/5p7#5Z026i7,7-6E764R098a7^6Q7`024/4;4?8l3N8n2*8y7f8r6g020i886I7;4D637+2R0B8w8x7I7L8D7N8C7h8E8G5,4X8o6+8L7)8%7t2m7*0:8S8f7T7{8V8`8t838$8E6o6q8P6u0k8P4R0x0A0A1/0w8P65668:3g6S9i8{8T8'8M6f5u5$8v7-8N025E0d5c5H9o020N9b6@8J5i0:6C8}7X6v8T966r9w7?4F0:2g0H0s0p6V7u9y9A9C5f4c164B0t2n2O9-4l1n4n2q2t2o0x1E9:0n4m0=9}0W0Y0!02.
Visualisation de l'échantillon
Afin d'afficher les point obtenus, vous pouvez utiliser le script suivant.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
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
Le tracé sera affiché ici
Si vous utilisez cette fonction, vous remarquerez que les unités ne sont pas les mêmes sur les deux axes. Il suffit de décommenter la première ligne de la fonction pour obtenir cette égalité, mais le rendu est un peu moins joli.
Distances⚓︎
Les 2 distances
Afin de pouvoir chercher les k plus proches voisins, il faut avoir une notion de distance. Nous allons considérer la distance euclidienne et la distance de Manhattan.
Les points seront représentés par des couples de valeurs. Il faut donc les décomposer pour calculer les distances :
Exemple de décomposition de coordonnées
>>> x, y = (20, 50)
Exercice 2
Écrire une fonction distance_euclidienne qui prend en paramètre 2 couples de réels pt1 et pt2, et qui renvoie la distance euclidienne entre les deux points.
Pour utiliser la racine carrée
La fonction sqrt du module math permet de calculer la racine carrée du nombre donné en argument.
Racine carrée
>>> from math import sqrt
>>> sqrt(398)
19.949937343260004
Exemples d'utilisation
>>> distance_euclidienne((0,0), (4,0))
4.0
>>> distance_euclidienne((1,-3), (2,7))
10.04987562112089
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
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
.128013 )3=x+lqngv,S"5/:rfuemkdas p
h*1itP(_y246cb-o 030r0o0B0s0A0a0t0u0J0a0s0t0t070h0B0A0v0h020w030t0n0p0p0s0l0F020g0M0a0n0%0M0c030j0-0/0;0?0+0v0203160 190j160+0r0A0e0V0X0Z0#0x0A0d0x0a1n0x0B0)030Q0K0a0o1i0Y0!0h1m1o1q1o0B1w1y1u0B0l170B0x0V0_0t0v0s0c0#0G0h1A1k0h0m0S0o0c0s0p0o1u1T1V1!1C1%1y1)1+0)040u0C0l0M0v0M0t0A0|0c0u0O1R0l0l0o0J230 1.0c170j1P2g1M1O1N1v0r1:0#1q0c1(201u1f1h0W1B2q0A2s0c0M2w1u0v29172e2g2K0,1U242y1#2D0l0:0a0)0z2d2O0*2N1/2Q1C2S2U0)0G2Y1V2!2e2p0h2(0s2V02062,2f0+2/2%0#2=2@0H2`2.2O2:300)0i332|352~2;0M2T2?0)0I331a2I0 2w2j0r1O2o3d0J2E1,173o183m2M102Z033u0O2J3c1j1C0q0c0)0m1}0p330u2#2P3J2 3M020:1P3R3T2:3L0)0A0p1 0l0B3#2}3V2;0)0t0b3,3a3b2$3:0q0)0O0m3.3I2z2;0m3~0A0t0Q0c0J0o0E0o0n0W0A1f1(2s3k3/430(020D4l422R0)0v0B2X3C2-3$3d4o0f413{433X4v2+4y2f4A3:4o050k3a0u4S3S4m4t02084x2M4V1C4C4E3U4G0)0F4Z2Z4U4s1C0M0)074'364u4w4R4T4M4)4X4J4!4/0#4%4K024.4F4W0F504-4}1#4;024?55574(4W4I4{4S5d3K0)290B0n0l0~5i5p2 3=3@3-555y0h4o0D4q5D4#5z4 4r584:0)0L5N5k2'0)4Y5S2:4O5X3d5f0y0y5!3:0p0A2*4@5#0)095-4N0)5I515O5L5a5(435f5R5J523;024+5|1#5Z605_0h5$5'685T0#5*5,6d5Y0)053a0 3F0o2g2H6p3n1g3p2j2m2h0s1x6s0j3o0+6C0P0R0T02.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
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
.128013 )3=x+lqngv,S"5/:rfuemkdas p
h*1itP(_y246cb-o 030r0o0B0s0A0a0t0u0J0a0s0t0t070h0B0A0v0h020w030t0n0p0p0s0l0F020g0M0a0n0%0M0c030j0-0/0;0?0+0v0203160 190j160+0r0A0e0V0X0Z0#0x0A0d0x0a1n0x0B0)030Q0K0a0o1i0Y0!0h1m1o1q1o0B1w1y1u0B0l170B0x0V0_0t0v0s0c0#0G0h1A1k0h0m0S0o0c0s0p0o1u1T1V1!1C1%1y1)1+0)040u0C0l0M0v0M0t0A0|0c0u0O1R0l0l0o0J230 1.0c170j1P2g1M1O1N1v0r1:0#1q0c1(201u1f1h0W1B2q0A2s0c0M2w1u0v29172e2g2K0,1U242y1#2D0l0:0a0)0z2d2O0*2N1/2Q1C2S2U0)0G2Y1V2!2e2p0h2(0s2V02062,2f0+2/2%0#2=2@0H2`2.2O2:300)0i332|352~2;0M2T2?0)0I331a2I0 2w2j0r1O2o3d0J2E1,173o183m2M102Z033u0O2J3c1j1C0q0c0)0m1}0p330u2#2P3J2 3M020:1P3R3T2:3L0)0A0p1 0l0B3#2}3V2;0)0t0b3,3a3b2$3:0q0)0O0m3.3I2z2;0m3~0A0t0Q0c0J0o0E0o0n0W0A1f1(2s3k3/430(020D4l422R0)0v0B2X3C2-3$3d4o0f413{433X4v2+4y2f4A3:4o050k3a0u4S3S4m4t02084x2M4V1C4C4E3U4G0)0F4Z2Z4U4s1C0M0)074'364u4w4R4T4M4)4X4J4!4/0#4%4K024.4F4W0F504-4}1#4;024?55574(4W4I4{4S5d3K0)290B0n0l0~5i5p2 3=3@3-555y0h4o0D4q5D4#5z4 4r584:0)0L5N5k2'0)4Y5S2:4O5X3d5f0y0y5!3:0p0A2*4@5#0)095-4N0)5I515O5L5a5(435f5R5J523;024+5|1#5Z605_0h5$5'685T0#5*5,6d5Y0)053a0 3F0o2g2H6p3n1g3p2j2m2h0s1x6s0j3o0+6C0P0R0T02.
Exercice 3
Écrire une fonction distance_manhattan qui prend en paramètre 2 couples de réels pt1 et pt2, et qui renvoie la distance de Manhattan entre les deux points.
Rappel sur la valeur absolue
On rappelle que la fonction abs permet de calculer la valeur absolue d'un nombre :
Valeur absolue
>>> abs(-5)
5
>>> abs(5)
5
Exemples d'utilisation
>>> distance_manhattan((0,0), (4,0))
4
>>> distance_manhattan((1,-3), (2,7))
11
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
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
.128013 )3=x+lngv,S"/:rfuemkdas p
h1itP(_y24cb-o 030p0m0y0q0x0a0r0s0F0a0q0r0r070g0y0x0t0g020u030r0l0n0n0q0j0C020f0I0a0l0Z0I0b030h0)0+0-0/0'0t0203120{150h120'0p0x0d0R0T0V0X0v0x0c0v0a1j0v0y0$030M0G0a0m1e0U0W0g1i1k1m1k0y1s1u1q0y0j130y0v0R0=0r0t0q0b0X0D0g1w1g0g0k0O0m0b0q0n0m1q1P1R1W1y1Z1u1$1'0$040s0z0j0I0t0I0r0x0^0b0s0K1N0j0j0m0F1 0{1*0b130h1L2c1I1K1J1r0p1,0X1m0b1#1|1q1b1d0S1x2m0x2o0b0I2s1q0t25132a2c2G0(1Q202u1X2z0j0,0a0$0w292K0%2J1+2M1y2O2Q0$0D2U1R2W2a2l0g2#0q2R02062(2b0'2+2Z0X2.2:0E2?2c2D0m2c2s2f0p1K2k2`0g0F2A1(1334142E2X2b2 033b0K2F2K2,0o0$0K0k2 0s3i2,0b0k3s0x0r0M0b0F0m0B0,0b0v0q1E1R3k2_1f1y0#020A3P3p390b0$0t0y2T0|2V3x393T0e3v3)3R2{3!0y2'3'2)3.2v0g3T050i2 0u0s413w3Q3`3Z02083%2I441X3+3-4b2!0$0C492V433X3/0g0I0$074e4m453;4j2)40423_2N0$083?4a4t4c0$3,3@2b4l2Y4n460C4E4k4A1y4p024r4K024M2L4O3;4R4x424!3q0$250y0l0j0`4Y4*3Y0G0$0q0G0r3W4N3`3T3V4Y4T3:474'3j4f0X4V0H4}4#4u474w574G3S0$054s4~1X4V095m5d2N4^024`4|52583{0$514F5n4g024Q5c2,5a5I3Y4h5g3o5E0X3|3 0{3m32163h0h3f2d360{2g5%4`1u331c2W5Z0L0N0P02.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
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
.128013 )3=x+lngv,S"/:rfuemkdas p
h1itP(_y24cb-o 030p0m0y0q0x0a0r0s0F0a0q0r0r070g0y0x0t0g020u030r0l0n0n0q0j0C020f0I0a0l0Z0I0b030h0)0+0-0/0'0t0203120{150h120'0p0x0d0R0T0V0X0v0x0c0v0a1j0v0y0$030M0G0a0m1e0U0W0g1i1k1m1k0y1s1u1q0y0j130y0v0R0=0r0t0q0b0X0D0g1w1g0g0k0O0m0b0q0n0m1q1P1R1W1y1Z1u1$1'0$040s0z0j0I0t0I0r0x0^0b0s0K1N0j0j0m0F1 0{1*0b130h1L2c1I1K1J1r0p1,0X1m0b1#1|1q1b1d0S1x2m0x2o0b0I2s1q0t25132a2c2G0(1Q202u1X2z0j0,0a0$0w292K0%2J1+2M1y2O2Q0$0D2U1R2W2a2l0g2#0q2R02062(2b0'2+2Z0X2.2:0E2?2c2D0m2c2s2f0p1K2k2`0g0F2A1(1334142E2X2b2 033b0K2F2K2,0o0$0K0k2 0s3i2,0b0k3s0x0r0M0b0F0m0B0,0b0v0q1E1R3k2_1f1y0#020A3P3p390b0$0t0y2T0|2V3x393T0e3v3)3R2{3!0y2'3'2)3.2v0g3T050i2 0u0s413w3Q3`3Z02083%2I441X3+3-4b2!0$0C492V433X3/0g0I0$074e4m453;4j2)40423_2N0$083?4a4t4c0$3,3@2b4l2Y4n460C4E4k4A1y4p024r4K024M2L4O3;4R4x424!3q0$250y0l0j0`4Y4*3Y0G0$0q0G0r3W4N3`3T3V4Y4T3:474'3j4f0X4V0H4}4#4u474w574G3S0$054s4~1X4V095m5d2N4^024`4|52583{0$514F5n4g024Q5c2,5a5I3Y4h5g3o5E0X3|3 0{3m32163h0h3f2d360{2g5%4`1u331c2W5Z0L0N0P02.
Recherche des k plus proches voisins⚓︎
Extraire la liste des k plus proches voisins
Afin de pouvoir trouver les k plus proches voisins, nous allons construire une liste de triplets de la forme (dist, pt, cat), où dist est la distance du point pt, de catégorie cat, avec l'élément considéré.
Pour trier la liste, vous pouvez soit utiliser liste.sort() ou l = liste.sorted().
Pour ne garder que les k premières valeurs, vous pouvez utiliser les tranches :
Exemples d'utilisation
>>> donnees = [7680, 1, 90, 99920, 5]
>>> donnees.sort()
>>> donnees[:2]
[1, 5]
>>> k = 3
>>> donnees[:k]
[1, 5, 90]
Exercice 4
Écrire la fonction k_plus_proches_voisins qui prend en paramètres un élément cible, un dictionnaire echantillon, un entier k et une fonction distance, et qui renvoie la liste des k plus proches voisins de cible selon la distance distance dans l'échantillon echantillon.
Vous pouvez parcourir les éléments de chaque catégorie et construire la liste des triplets (dist, elem, cat), la trier, puis ne garder que les k premiers résultats.
Trier des t-uplets
Lorsqu'on trie des t-uplets, on utilise l'ordre lexicographique. Pour comparer deux t-uplets, on commence par comparer les premiers éléments de chacun. S'ils sont égaux, on passe au suivant, jusqu'à arriver à la fin d'au moins un t-uplet.
Dans notre cas, il y a très peu de chance que deux points se trouvent à la même distance de la cible, mais si c'est le cas, ce sera celui qui a la plus petite valeur de x qui sera mis en premier.
Exemples d'utilisation
>>> echantillon = generation_echantillon(10)
>>> k_plus_proches_voisins((20,20), echantillon, 3, distance_euclidienne)
[(7.1846487991039165, (22.130632728353085, 13.138543700981836), 0),
(15.397111123887077, (35.01027454088991, 23.42967770620497), 0),
(17.92707320889055, (29.4015044708685, 35.2640645806142), 0)]
Pour les plus courageux
Pour ceux qui sont très motivés, on peut faire le tri des éléments à l'aide du tri par insertion, en ne rajoutant les éléments que s'il y a moins de k valeurs dans la liste ou s'il est plus petit que le dernier inséré.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
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
.128013 ;)wjn8vArf7Omkèp h1iP_y2[4ùcb-o3=9lq'Rg,S.à"5/:ueédas
0t(]6 030T0R0Y0U0o0D0V0l0w0D0U0V0V0B0M0Y0o0k0M020W030V0Q0h0h0U0d0r020J0z0D0Q0^0z090l000U0h0k050l0G0R120d0E0Q0R0V030O0 1113150}0k02031A1t1D0O1A0}0T0o0b0-0/0;0?0m0o0H0m0D1R0m0Y0{030(0x0D0R1M0:0=0M1Q1S1U1S0Y1!1$1Y0Y0d1B0Y0m0-180V0k0U090?0s0M1'1O0M0e0*0R091g0R1Y1}1 241)271$2a0h2c02040l0p0d0z0k0z0V0o1b1d0%1{0d0d0R0w2x1t2e091B0O1_2J1?1^1@1Z0T2g0?1U09292u1Y1J1L0.1(2T0o2V090z2Z1Y0k2C1B2H2J2:0~1~1d2#252)0d120D0{0n2G2@0|2?2f2_1)2{2}0{0s311 332H2S0M380U2~020A3c2I0}3f360?3i3k0u3n3e2@3g3t0{0N3w3p3y3r3h0z2|3j0{0#3D342^1N373I39020f3N3q3Q3s3S3K020a3w1E2.1t2Z2M0T1^2R3G0w2*2m0$1K1B2-0R2/323'3;0%3|353Y0M0i0{0%0e3w0l3O3z0e0{0i0q0k190V4g2r0w0m1r0q0b0z0o2v091s1u3}3X2$0M0`020Z3'4y2`0{0w0o1#0R4E3F434B0I494b3G090{2D0m1 0^0D0D1c4M424z4P4R4F374e4%3P4(0{4Q4w3d4a4+3s464s0(090w4L4?2I4S4O0{060P3D0l594^4N4z4U021U0V0Y502:5b4'250z0{0B4*5c254B0t0!585a534z45020e3I5r5m4,020w0U0Y5F4/5n070{2'5M3z4V4m4Y0*4#094.3g4B57510|5a5)5l5N1)5B5D0d5S4T4V1$0h5;430z5P025R5'5+5T024W5W4!4$5'5z5t0{0t5!5=5I5K6c54020!5%2:0W5*6n606d1J5h5_4z5o025q5 685H6r4}4 6g4:4C6E4G5I4J1$6H1)4)6y4_3h5?1m6M0?4B06496p430w0n0{010l0g2^3j0w0Q1$0l0/0l6B1 4 0l291?1%6:4I4K6^0Y6/00010A0C050S0D0S2l095L5'6m6o5)6z4`5f4|5j4x5s1)6v0K6U6R020U0k0k290T7r4B0Z4D676Q5e6B7z4;6t6I0R5@7H024=5k7h7s5J7c2=6Q6W6X7d7g7E0{5g5i7r7p7r5e0V3I7U7m5G6V0{0Z7Y6l7!7n0?5B2C0Y0Q0d5Z6P7`7s7%7l3d7R5u6k7/5,7i0i7N5w7d1t3 3{3(8k0O3+1t0Y3-8p2P2K0U4K2J3+1z418c0M2C0h0q0e0U0i0R0q0m0A0{1l1n1p1r0l8a871G331A0J0F0*0l0r0l0U0l0x0R0U0Q3;0Q0k6;1%0b3j0R7 0V0I0l1c0l7w1a0l1a0*4s0R0d6/1%2-2'4I7w6;0Q0l1?0o8}130l2'0V942x6^1d2V0l0H130T4Y0l8Q960,038j028e0O9B0l8=1$8^9y8}4i8}4l4n0,0b1q0,080Q0V1p0F0L9N0S9l7b7q8V8z6)0l9q0d0U080z1a1%0Q9p9:0b7L0l77796_9w1q0l0V8Z0D8#8%9o3;2C8:6/8'4h0U6@9:a19g6.2)0Q9_a49|7a701r704h9V9N0z4m1%9x6.0%800o94aa6:850K1I1K3g1+1T1V1X8A3g2i292b0{0c1aa97,192F673`8A2;3}9B7R5B477J374d5}4u9486527W7=7*7$7k7N7P326Z5d0{9Ha~a.8d7N565x59a+5Q48827:3h0x7$297N7C7V835e85b8b60M6v000D0Y05bs5e9D7Q6Q5{0{5Ebf8B7A7*bi5fbk7D83bJbObgbpa}bRbI55bs6v0B6xbCbo4-bH3gbE7t097yb(6dbqbV5#6a7(0{0y7r0h0o2 8fbY0{000Hbxbzb33jb88T3o7fbc5}beb$bSbL2jbla{7j5ha@aQ3G6Wb 02bvc3b.43bA7Nc802bb6Q6#6%6(1d8~709-9/9;959?9{78apba7fb16Ib:bnbg7)b;6d7u7wb,cicYcvc50Dbr7Z6ocb7L9lcxcQca7#ck7'c'6F6bc`6IbB8bb)b^b`b|0230c}6N0{8gce8BbZc402b45 cS1)cC026'9*8Dad6@aA9409aD95ao6_c=5yc@08cqb#b07R09cgbNcVbW6Gd77icUd0cobXdMbtd2dSb{b}c,6n7Rdkdm2^4n0dax8{0v0l2l1/a96:aBdt0ja99H8@5:dY5*cb071Q6Lcub202dBe15nc0c2bye51)dW020XbY5|1 b-db61dO87a_02c|dJ61e4eq3G6vb_dVd4d6et6hdadEbDe7ctej6ddgeA6Fcy7ecRdidNbUeK69eocjesdPeBdCdeela^bPb?dS5eeWem83evd3dXeSd86idydZdAeZea7ie*e$cWdUe:0?ecez32eNd|c@e#cn6hepeXe2e|f96FeC4@7Rdde`7seJf43Ebga,0RcdeDboa:4fat4j2-aw9P4p4r4t4vf04Aa`e(4H6Kcm887Ifl5e637b5X66fH6OeHc(9Cb5fQ4{5h6?fNenb9d{dFa|cle_fYc{fhc9dz835.bGf;6I7Tef5Q81f|5HfS4Z5Yc;d{7_fq0{5/de7L6Tflb*5~g27ig4fUg1fceTfbe+bS4H6fdS4B6je?f6b%027Ggg5pde6=4~f)e%dLfH5e6}e0fWfPgj7sge5^gvdR7^eOeP7s9ka?c%gLf.c_gP7ObsbQg'gB4|f#gRfR7MgVg+f$6e7.grdK06a fic@c g}b=027@f4g98B7|0'7 gnh1gAf80}9E3=2Ja%3*3^1E338n0'0)0+02.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
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
.128013 ;)wjn8vArf7Omkèp h1iP_y2[4ùcb-o3=9lq'Rg,S.à"5/:ueédas
0t(]6 030T0R0Y0U0o0D0V0l0w0D0U0V0V0B0M0Y0o0k0M020W030V0Q0h0h0U0d0r020J0z0D0Q0^0z090l000U0h0k050l0G0R120d0E0Q0R0V030O0 1113150}0k02031A1t1D0O1A0}0T0o0b0-0/0;0?0m0o0H0m0D1R0m0Y0{030(0x0D0R1M0:0=0M1Q1S1U1S0Y1!1$1Y0Y0d1B0Y0m0-180V0k0U090?0s0M1'1O0M0e0*0R091g0R1Y1}1 241)271$2a0h2c02040l0p0d0z0k0z0V0o1b1d0%1{0d0d0R0w2x1t2e091B0O1_2J1?1^1@1Z0T2g0?1U09292u1Y1J1L0.1(2T0o2V090z2Z1Y0k2C1B2H2J2:0~1~1d2#252)0d120D0{0n2G2@0|2?2f2_1)2{2}0{0s311 332H2S0M380U2~020A3c2I0}3f360?3i3k0u3n3e2@3g3t0{0N3w3p3y3r3h0z2|3j0{0#3D342^1N373I39020f3N3q3Q3s3S3K020a3w1E2.1t2Z2M0T1^2R3G0w2*2m0$1K1B2-0R2/323'3;0%3|353Y0M0i0{0%0e3w0l3O3z0e0{0i0q0k190V4g2r0w0m1r0q0b0z0o2v091s1u3}3X2$0M0`020Z3'4y2`0{0w0o1#0R4E3F434B0I494b3G090{2D0m1 0^0D0D1c4M424z4P4R4F374e4%3P4(0{4Q4w3d4a4+3s464s0(090w4L4?2I4S4O0{060P3D0l594^4N4z4U021U0V0Y502:5b4'250z0{0B4*5c254B0t0!585a534z45020e3I5r5m4,020w0U0Y5F4/5n070{2'5M3z4V4m4Y0*4#094.3g4B57510|5a5)5l5N1)5B5D0d5S4T4V1$0h5;430z5P025R5'5+5T024W5W4!4$5'5z5t0{0t5!5=5I5K6c54020!5%2:0W5*6n606d1J5h5_4z5o025q5 685H6r4}4 6g4:4C6E4G5I4J1$6H1)4)6y4_3h5?1m6M0?4B06496p430w0n0{010l0g2^3j0w0Q1$0l0/0l6B1 4 0l291?1%6:4I4K6^0Y6/00010A0C050S0D0S2l095L5'6m6o5)6z4`5f4|5j4x5s1)6v0K6U6R020U0k0k290T7r4B0Z4D676Q5e6B7z4;6t6I0R5@7H024=5k7h7s5J7c2=6Q6W6X7d7g7E0{5g5i7r7p7r5e0V3I7U7m5G6V0{0Z7Y6l7!7n0?5B2C0Y0Q0d5Z6P7`7s7%7l3d7R5u6k7/5,7i0i7N5w7d1t3 3{3(8k0O3+1t0Y3-8p2P2K0U4K2J3+1z418c0M2C0h0q0e0U0i0R0q0m0A0{1l1n1p1r0l8a871G331A0J0F0*0l0r0l0U0l0x0R0U0Q3;0Q0k6;1%0b3j0R7 0V0I0l1c0l7w1a0l1a0*4s0R0d6/1%2-2'4I7w6;0Q0l1?0o8}130l2'0V942x6^1d2V0l0H130T4Y0l8Q960,038j028e0O9B0l8=1$8^9y8}4i8}4l4n0,0b1q0,080Q0V1p0F0L9N0S9l7b7q8V8z6)0l9q0d0U080z1a1%0Q9p9:0b7L0l77796_9w1q0l0V8Z0D8#8%9o3;2C8:6/8'4h0U6@9:a19g6.2)0Q9_a49|7a701r704h9V9N0z4m1%9x6.0%800o94aa6:850K1I1K3g1+1T1V1X8A3g2i292b0{0c1aa97,192F673`8A2;3}9B7R5B477J374d5}4u9486527W7=7*7$7k7N7P326Z5d0{9Ha~a.8d7N565x59a+5Q48827:3h0x7$297N7C7V835e85b8b60M6v000D0Y05bs5e9D7Q6Q5{0{5Ebf8B7A7*bi5fbk7D83bJbObgbpa}bRbI55bs6v0B6xbCbo4-bH3gbE7t097yb(6dbqbV5#6a7(0{0y7r0h0o2 8fbY0{000Hbxbzb33jb88T3o7fbc5}beb$bSbL2jbla{7j5ha@aQ3G6Wb 02bvc3b.43bA7Nc802bb6Q6#6%6(1d8~709-9/9;959?9{78apba7fb16Ib:bnbg7)b;6d7u7wb,cicYcvc50Dbr7Z6ocb7L9lcxcQca7#ck7'c'6F6bc`6IbB8bb)b^b`b|0230c}6N0{8gce8BbZc402b45 cS1)cC026'9*8Dad6@aA9409aD95ao6_c=5yc@08cqb#b07R09cgbNcVbW6Gd77icUd0cobXdMbtd2dSb{b}c,6n7Rdkdm2^4n0dax8{0v0l2l1/a96:aBdt0ja99H8@5:dY5*cb071Q6Lcub202dBe15nc0c2bye51)dW020XbY5|1 b-db61dO87a_02c|dJ61e4eq3G6vb_dVd4d6et6hdadEbDe7ctej6ddgeA6Fcy7ecRdidNbUeK69eocjesdPeBdCdeela^bPb?dS5eeWem83evd3dXeSd86idydZdAeZea7ie*e$cWdUe:0?ecez32eNd|c@e#cn6hepeXe2e|f96FeC4@7Rdde`7seJf43Ebga,0RcdeDboa:4fat4j2-aw9P4p4r4t4vf04Aa`e(4H6Kcm887Ifl5e637b5X66fH6OeHc(9Cb5fQ4{5h6?fNenb9d{dFa|cle_fYc{fhc9dz835.bGf;6I7Tef5Q81f|5HfS4Z5Yc;d{7_fq0{5/de7L6Tflb*5~g27ig4fUg1fceTfbe+bS4H6fdS4B6je?f6b%027Ggg5pde6=4~f)e%dLfH5e6}e0fWfPgj7sge5^gvdR7^eOeP7s9ka?c%gLf.c_gP7ObsbQg'gB4|f#gRfR7MgVg+f$6e7.grdK06a fic@c g}b=027@f4g98B7|0'7 gnh1gAf80}9E3=2Ja%3*3^1E338n0'0)0+02.
Catégorisation⚓︎
Catégoriser les éléments
Une fois la liste des k plus proches voisins obtenue, il faut déterminer la catégorie majoritaire dans cette liste. Pour cela, nous allons parcourir la liste en comptant le nombre d'apparitions de chaque catégorie.
Pour compter ces apparitions, nous utiliserons un dictionnaire qui à chque catégorie associe le nombre d'éléments vus.
Exercice 5
Écrire une fonction decision qui prend en paramètre une liste de triplets (dist, elem, cat) et qui renvoie la catégorie cat majoritaire.
En cas d'égalité, la première catégorie arrivée au maximum sera considérée comme la catégorie majoritaire. Vous pourrez faire une recherche de la catégorie majoritaire pendant l'analyse de la liste, en utilisant un algorithme de recherche de maximum.
Déplier les t-uplets
Pour déplier les éléments de la liste, il faut utiliser des affectations multiples :
Exemples d'utilisation
>>> dist, elem, cat = (7.18, (22.13, 13.13), 0)
>>> dist
7.18
>>> elem
(22.13, 13.13)
>>> cat
0
Dans l'exemple suivant, les valeurs sont totalement artificielles pour simplifier l'écriture.
Exemples d'utilisation
>>> decision([(0.2,(2,2),0),(0.4,(3,1.5),1),(0.7,(4,6),0)])
0
>>> decision([(0.2,(2,2),0),(0.4,(3,1.5),1),(0.7,(4,6),2)])
0
>>> decision([(0.2,(2,2),0),(0.4,(3,1.5),1),(0.7,(4,6),1),(1.9,(9,-7),0)])
1
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
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
.128013 ;)3=9x+lwjqnN8gv,Sà"5/:rCf7uOemkèédas p
h10itP(_y2[46cb]o 030D0y0N0E0M0c0F0G0W0c0E0F0F080o0N0M0H0o020I030F0w0z0z0E0s0R020m0Z0c0w0?0Z0g030q0}0 11130{0H02031j1c1m0q1j0{0D0M0k0+0-0/0;0J0M0j0J0c1A0J0N0_030%0X0c0y1v0.0:0o1z1B1D1B0N1J1L1H0N0s1k0N0J0+160F0H0E0g0;0S0o1N1x0o0u0(0y0g0E0z0y1H1)1+1:1P1?1L1_1{0_040G0O0s0Z0H0Z0F0M190g0G0#1'0s0s0y0W2g1c1~0g1k0q1$2t1Z1#1!1I0D200;1D0g1^2d1H1s1u0,1O2D0M2F0g0Z2J1H0H2m1k2r2t2X0|1*2h2L1;2Q0s100c0_0G0K2q2#0`2!1 2%1P2(2*2,0S2/1+2;2r2C0o2_0E2+020G072}2s0{302@0;33350G0U392 2#313f2,0p3j3b3l3d320Z2)342,0V3q2=2$1w2^3v2`360v3A3c3D3e3F3x360i3J3s3L3u3w3g093R2?3T3n020K0L3Y3C2M3U3G0K2.1d2:1n2V1c2J2w0D1#2B3t0W2R1|1k3@1l3=2Z3/2~033}0#2W3S3*0A0_0#0u3j0G3B3m0u4e2n0M2e1a3j4j3t0^020P4r3K3*0g0_1D0F0N0y0Q0k0Z4o2O0F4x4b1;4u060r3q0G4T4i4y2'0_0W0E4E0j3v0M0y4L452s4V4N1P0Z0_084h4s3!0X4e0M2o4M3Z3*4u0P064S4U4?4z4Y4!0Q100a4=4W4.4:5b4-0;0A0W0_0h1a0y524T541;4d020u3v5f4}4X021s4D4|3)4O0_0l5w5D2^0_0y1L0z5C314u5G4*365q5J024Z0N5H310Z0d0_2O5Z3t4A024C4E4G4I2e0g4)2Z5c0;4u4R5S0I4U5}4,5x1P5s0M4g5S5 5I3e565Y655U0;5#5%1b6b5@32690y4$0s4'5=3:6i5_4h66310W0K0_010G0x2h0E2i0C0e0n0G0k0w0+0$4E0+4!0C6m4'5o5~5}6c6j5W4!6l4%4(5O4t0_0T6%3!696*4~0_0Y5(3T4/024;6h5g6X5X6!6n6$5S6W4u6)706i5*5X6-5E026:6_606d0_0b6;3*0z0M0_3.2X5|6U6u3t5s5L0F5n746`6s657q3T6w6y0G0t00010709054(0N0G0-0G2U0y7j0B2m0G5u4o0G0f0w7G7I051a6I4I7M0W6M1M5X6Q6#6T7p7A556Y4#6#6p466r6(785V777w7d0o4u7b2X7?1;6?6^876W7j7l7;536i62648c7569580E5a7c670o8a8b2:88615j025l2F7h895$025v8r3m6k6R6 5?7x7~828s764!7 5^6/8D5d02000j0N058X687^6}6o8U848P8N838S0N8o8q8/8s855`8^6v6x026z6B0G6D0w2h2Q0w0k0y0E6K590M0z0~8g6U6W8;8?8'8t5e8I5)6,5{6V8i0_2m0N0w0s6g8l6`9j593A0q480y2t7Q2t412u3_1c2x9O0E1K9H3?1t2;0q0#0%0(0F02.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
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
.128013 ;)3=9x+lwjqnN8gv,Sà"5/:rCf7uOemkèédas p
h10itP(_y2[46cb]o 030D0y0N0E0M0c0F0G0W0c0E0F0F080o0N0M0H0o020I030F0w0z0z0E0s0R020m0Z0c0w0?0Z0g030q0}0 11130{0H02031j1c1m0q1j0{0D0M0k0+0-0/0;0J0M0j0J0c1A0J0N0_030%0X0c0y1v0.0:0o1z1B1D1B0N1J1L1H0N0s1k0N0J0+160F0H0E0g0;0S0o1N1x0o0u0(0y0g0E0z0y1H1)1+1:1P1?1L1_1{0_040G0O0s0Z0H0Z0F0M190g0G0#1'0s0s0y0W2g1c1~0g1k0q1$2t1Z1#1!1I0D200;1D0g1^2d1H1s1u0,1O2D0M2F0g0Z2J1H0H2m1k2r2t2X0|1*2h2L1;2Q0s100c0_0G0K2q2#0`2!1 2%1P2(2*2,0S2/1+2;2r2C0o2_0E2+020G072}2s0{302@0;33350G0U392 2#313f2,0p3j3b3l3d320Z2)342,0V3q2=2$1w2^3v2`360v3A3c3D3e3F3x360i3J3s3L3u3w3g093R2?3T3n020K0L3Y3C2M3U3G0K2.1d2:1n2V1c2J2w0D1#2B3t0W2R1|1k3@1l3=2Z3/2~033}0#2W3S3*0A0_0#0u3j0G3B3m0u4e2n0M2e1a3j4j3t0^020P4r3K3*0g0_1D0F0N0y0Q0k0Z4o2O0F4x4b1;4u060r3q0G4T4i4y2'0_0W0E4E0j3v0M0y4L452s4V4N1P0Z0_084h4s3!0X4e0M2o4M3Z3*4u0P064S4U4?4z4Y4!0Q100a4=4W4.4:5b4-0;0A0W0_0h1a0y524T541;4d020u3v5f4}4X021s4D4|3)4O0_0l5w5D2^0_0y1L0z5C314u5G4*365q5J024Z0N5H310Z0d0_2O5Z3t4A024C4E4G4I2e0g4)2Z5c0;4u4R5S0I4U5}4,5x1P5s0M4g5S5 5I3e565Y655U0;5#5%1b6b5@32690y4$0s4'5=3:6i5_4h66310W0K0_010G0x2h0E2i0C0e0n0G0k0w0+0$4E0+4!0C6m4'5o5~5}6c6j5W4!6l4%4(5O4t0_0T6%3!696*4~0_0Y5(3T4/024;6h5g6X5X6!6n6$5S6W4u6)706i5*5X6-5E026:6_606d0_0b6;3*0z0M0_3.2X5|6U6u3t5s5L0F5n746`6s657q3T6w6y0G0t00010709054(0N0G0-0G2U0y7j0B2m0G5u4o0G0f0w7G7I051a6I4I7M0W6M1M5X6Q6#6T7p7A556Y4#6#6p466r6(785V777w7d0o4u7b2X7?1;6?6^876W7j7l7;536i62648c7569580E5a7c670o8a8b2:88615j025l2F7h895$025v8r3m6k6R6 5?7x7~828s764!7 5^6/8D5d02000j0N058X687^6}6o8U848P8N838S0N8o8q8/8s855`8^6v6x026z6B0G6D0w2h2Q0w0k0y0E6K590M0z0~8g6U6W8;8?8'8t5e8I5)6,5{6V8i0_2m0N0w0s6g8l6`9j593A0q480y2t7Q2t412u3_1c2x9O0E1K9H3?1t2;0q0#0%0(0F02.
Visualisation des voisins
Vous pouvez tester le résultat obtenu en choisissant différentes cibles, valeurs de k ou tailles d'échantillon.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
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
Le tracé sera affiché ici
# Tests(insensible à la casse)(Ctrl+I)