31-12-2017, 06:35 PM
Hum, je ne pense pas que cela fasse sens de prendre autant de dimensions que d'élèves... Si le collège fait 600 élèves, ça va être hard niveau temps de calcul... Et mathématiquement, le nombre de caractéristiques de chaque élève dépend maintenant du nombre total d'élèves... Pas sûr que cela permette d'avoir un algorithme rapide et efficace.
En temps normal (= dans un K-moyenne avec D dimensions et N élèves, le nombre de dimensions n'étant pas dépendant du nombre d'élèves), chaque nouvel élève rajoute K calculs de distances en dimension D, 1 calcul de minimum sur ces K distances, et 1 élément de somme dans le calcul des nouvelles moyennes. Ca fait donc, en gros (K*D+2) opérations, donc, une constante (vis à vis de N) qui est, en plus, faible (vis à vis de N).
En prenant autant de dimensions que d'élèves, cela fait alors (K*N+2) opérations de calcul supplémentaire, *mais également* 1 nouvelle dimension dans *chaque* calcul de distance entre chaque autre élève et chaque moyenne... soient N élèves * K moyennes * 1 nouvelle dimension dans le calcul de leur distance à ces moyennes = N*K... Donc on se retrouve, en gros, à rajouter (2*K*N) calculs à chaque nouvel élève inséré (tu flaires le côté au mieux polynomial et au pire exponentiel du calcul?! =P ).
Bref, cela me semble être un mauvais modèle.
Les K-moyennes, en effet, n'ont pas nativement la propriété d'avoir des groupes "équilibrés" en terme de nombre d'éléments, et comme on part d'une configuration aléatoire, il *faut* réitéré le calcul un certain nombre de fois (avec des positions de départ différentes) puis comparer les résultats pour ne conserver que le meilleur (car, en gros, si on n'a pas eu de bol, notre configuration initiale était à chier, mais ce problème, on le retrouve dans tous les algos d'optimisation de ce style, qui marche par convergence).
Pour le premier problème, il suffit de calculer d'abord toutes les distances entre chaque point et chaque moyenne (donc, [nb élèves]*[nb classes] calculs de distances), les trier de la plus petit à la plus grande, et associer chaque élève à sa classe la plus proche, dans l'ordre ainsi construit. Et dès qu'une classe est pleine, on n'ajoute plus d'élève dedans (on ignore les distances entre les élèves et cette classe pleine). C'est une façon d'appliquer l'idée générale de "partitionnement progressif" (élément par élément) alors que la K-moyenne présenté dans le Wiki partitionne "tout d'un coup".
Pour le 2nd soucis, il suffit de relancer l'algo, et de garder la configuration de classes trouvées que si celle-ci a un meilleur score que la précédent (score qui se calcul, par exemple, par la moyenne de la somme des carrés des distances entre chaque élève et la moyenne de sa classe).
Un autre modèle qui peut exploiter les K-moyennes, en revanche, serait celui des "ressorts": tu places tes élèves dans un espace à 3 dimensions (là, le nb de dimensions est totalement arbitraire!). Chaque paire d'élèves que tu veux voir ensemble/pas ensemble est liée par un petit ressort, de raideur k (ou par une force d'attraction ou de répulsion, c'est similaire). Plus deux élèves doivent être ensemble, plus la raideur du ressort tend à les rapprocher (ou, plus simplement, la force est fortement attractive). Inversement si les élèves ne doivent pas être ensembles.
Tu places alors tes élèves au hasard dans l'espace de dimension 3, et tu laisses agir les différentes forces (là, y'a des moteurs physiques qui peuvent certainement le faire, sinon, c'est pas du calcul bien compliqué, c'est juste du différentiel, faut simplement faire gaffe quand deux élèves sont très très proches; t'as même pas besoin de gérer les accélérations/les vitesses, juste le déplacement élémentaire entre deux itérations DT).
Tu obtiens donc une configuration spatiale (3D) de tes élèves, où ceux qui doivent être ensemble sont proches, et ceux qui ne doivent pas l'être sont loin. Libre à toi alors de lancer une K-moyennes là-dessus, ou de te faire une représentation graphique du résultat pour juger humainement (et arbitrairement) du découpage.
En temps normal (= dans un K-moyenne avec D dimensions et N élèves, le nombre de dimensions n'étant pas dépendant du nombre d'élèves), chaque nouvel élève rajoute K calculs de distances en dimension D, 1 calcul de minimum sur ces K distances, et 1 élément de somme dans le calcul des nouvelles moyennes. Ca fait donc, en gros (K*D+2) opérations, donc, une constante (vis à vis de N) qui est, en plus, faible (vis à vis de N).
En prenant autant de dimensions que d'élèves, cela fait alors (K*N+2) opérations de calcul supplémentaire, *mais également* 1 nouvelle dimension dans *chaque* calcul de distance entre chaque autre élève et chaque moyenne... soient N élèves * K moyennes * 1 nouvelle dimension dans le calcul de leur distance à ces moyennes = N*K... Donc on se retrouve, en gros, à rajouter (2*K*N) calculs à chaque nouvel élève inséré (tu flaires le côté au mieux polynomial et au pire exponentiel du calcul?! =P ).
Bref, cela me semble être un mauvais modèle.
Les K-moyennes, en effet, n'ont pas nativement la propriété d'avoir des groupes "équilibrés" en terme de nombre d'éléments, et comme on part d'une configuration aléatoire, il *faut* réitéré le calcul un certain nombre de fois (avec des positions de départ différentes) puis comparer les résultats pour ne conserver que le meilleur (car, en gros, si on n'a pas eu de bol, notre configuration initiale était à chier, mais ce problème, on le retrouve dans tous les algos d'optimisation de ce style, qui marche par convergence).
Pour le premier problème, il suffit de calculer d'abord toutes les distances entre chaque point et chaque moyenne (donc, [nb élèves]*[nb classes] calculs de distances), les trier de la plus petit à la plus grande, et associer chaque élève à sa classe la plus proche, dans l'ordre ainsi construit. Et dès qu'une classe est pleine, on n'ajoute plus d'élève dedans (on ignore les distances entre les élèves et cette classe pleine). C'est une façon d'appliquer l'idée générale de "partitionnement progressif" (élément par élément) alors que la K-moyenne présenté dans le Wiki partitionne "tout d'un coup".
Pour le 2nd soucis, il suffit de relancer l'algo, et de garder la configuration de classes trouvées que si celle-ci a un meilleur score que la précédent (score qui se calcul, par exemple, par la moyenne de la somme des carrés des distances entre chaque élève et la moyenne de sa classe).
Un autre modèle qui peut exploiter les K-moyennes, en revanche, serait celui des "ressorts": tu places tes élèves dans un espace à 3 dimensions (là, le nb de dimensions est totalement arbitraire!). Chaque paire d'élèves que tu veux voir ensemble/pas ensemble est liée par un petit ressort, de raideur k (ou par une force d'attraction ou de répulsion, c'est similaire). Plus deux élèves doivent être ensemble, plus la raideur du ressort tend à les rapprocher (ou, plus simplement, la force est fortement attractive). Inversement si les élèves ne doivent pas être ensembles.
Tu places alors tes élèves au hasard dans l'espace de dimension 3, et tu laisses agir les différentes forces (là, y'a des moteurs physiques qui peuvent certainement le faire, sinon, c'est pas du calcul bien compliqué, c'est juste du différentiel, faut simplement faire gaffe quand deux élèves sont très très proches; t'as même pas besoin de gérer les accélérations/les vitesses, juste le déplacement élémentaire entre deux itérations DT).
Tu obtiens donc une configuration spatiale (3D) de tes élèves, où ceux qui doivent être ensemble sont proches, et ceux qui ne doivent pas l'être sont loin. Libre à toi alors de lancer une K-moyennes là-dessus, ou de te faire une représentation graphique du résultat pour juger humainement (et arbitrairement) du découpage.