Algorithme de composition de groupe par affinité

[Sephi-Chan]

Bonjour,

Je suis en train de créer un outil pour aider mes collègues et moi-même à constituer les classes de notre école.

Je suis pour cela à la recherche d'algorithmes existants pour constituer des groupes, notamment par affinité (peut-être en définissant des poids entre élèves, genre ces deux là ont un poids négatif pour dire qu'ils ne doivent surtout pas être ensemble, etc.).

Est-ce que ça vous dit quelque chose ?


Merci !

[Xenos]

Salut,

du K-partionnement de mémoire, donc le principe consiste à positionner chaque élément dans un espace à N dimensions, et à regrouper les points les plus proches (en créant K partitions de cet espace multi-dimentionnel).
Dans l'idée, tu dresses N caractéristiques pour chaque élève, tu donnes une valeur à chacune de ces caractéristiques, et tu groupe les points les plus proches entre eux. Je pense qu'il doit y avoir des groupements qui peuvent se faire par "sphères".

Sinon, avec des contraintes plutôt type "lui veut aller avec lui et lui ne veut pas être avec lui", tu dois pouvoir modéliser cela à base de ressort: chaque paire d'élève se voit liée à un ressort, qui tend à les rapprocher ou à les éloigner plus ou moins. En laissant ce système de ressorts libre, il finit par converger vers un point d'équilibre, et tu peux en tirer des groupes. Ca te fait un graph complet assez lourd, mais je pense que c'est solvable très facilement en pratique (genre tu peux construire un fichier graphviz à partir de ce mécanisme de ressorts, et graphviz de l'affichera en respectant ces "forces de ressorts"; bref, ce système de ressort est utilisé par GV pour placer ses noeuds... mais c'est du 2D là).

Avec des outils plus accessibles, sinon, tu peux modéliser l'exemple précédent des ressorts en SQL ou autre (pas forcément de façon complète, c'est à dire ne créer que certaines paires d'élèves, avec un coefficient 0 pour "j'm'en fous qu'ils soient ensembles", -1 pour "surtout pas ensemble" et 1 pour "doivent être ensemble"), et faire un calcul exhaustif de toutes les combinaisons de groupes possibles, déterminant ainsi le score d'affinité de chaque groupe d'élève, le score global, et en définissant un algorithme d'ordonnancement de ces groupes (ie: je prend la combinaison de groupes pour laquelle tous les groupes ont à peu près la même affinité, et dont la somme totale des affinités est la plus élevée possible). Vu que t'as probablement moins de ~30 élèves (je dirai), c'est jouable l'exhaustif.

Edit: Quoique j'ai mal lu: j'ai cru que c'était pour faire des groupes dans la classe... Alors que c'est pour faire les classes dans l'école. Là, l'échelle ne permettra peut-être pas de faire de l'exhaustif... Et à cette échelle, les "affinités" seront dures à déterminer. Pour dire que l'affinité entre deux élèves donnés est de X sur une échelle de 0 à 1, alors je pense qu'il faut doter chacun des deux élèves de "paramètres" genre notes, préférences pour certaines matières, etc et tirer de ces notes un "niveau", puis considérer que l'affinité entre deux élèves dépend de leur niveau respectif (deux élèves de niveau similaires auront une forte affinité, deux élèves de niveaux différents en auront une faible). Cela permettra aussi d'injecter, lors de la construction de cette affinité, d'autres paramètres comme le fait que deux élèves spécifiques se détestent... Et dans le calcul exhaustif, chaque ensemble de classes peut alors se voir doté d'un "score", reflétant le fait que les classes soient équilibrées (= que les élèves de chaque classe ont une bonne affinité) mais aussi le fait que les classes n'aient pas 1 fille pour 20 garçons (ou inversement), ou qu'un élève n'ait pas un niveau trop faible/fort.

Si le calcul exhaustif n'est pas faisable, l'autre méthode issue des calculs d'optimisation consiste à partir d'une configuration aléatoire, à calculer son "score", puis à changer un élève de classe. On recalcule alors le score, et s'il est meilleur, on réitère avec cette nouvelle configuration. Si le score est moins bon, on remet l'élève à sa place initiale, et on essaie avec un autre. Si, après X essais (en évitant de refaire les mêmes si possible, mais bon, c'est pas trop grave) on n'a pas trouvé d'agencement de classes avec un meilleur score global, alors on considère que cette configuration est un "optimum local". On relance alors l'algo avec une autre position initiale aléatoire, et on réitère autant de fois qu'on veut. On prend ensuite la meilleur configuration parmi tous ces "optimum locaux".

Tiens, je vais tenter de le modéliser, pour voir

[Xenos]

Voilà à quoi j'arrive (cela requiert de créer d'abord une table d'integers pour l'initialisation des students):

Code :

DROP TABLE IF EXISTS test_students; -- List of students (temporary table for calculation)
CREATE TABLE test_students (id INT UNSIGNED NOT NULL, classroom INT UNSIGNED NULL, PRIMARY KEY (id)) ENGINE=HEAP;
DROP TABLE IF EXISTS test_students_result; -- List of students (real result you should look to)
CREATE TABLE test_students_result (id INT UNSIGNED NOT NULL, classroom INT UNSIGNED NULL, PRIMARY KEY (id)) ENGINE=HEAP;
DROP TABLE IF EXISTS test_classrooms; -- List of classrooms
CREATE TABLE test_classrooms (id INT UNSIGNED NOT NULL, globalScore DOUBLE NULL, score DOUBLE NULL, PRIMARY KEY (id)) ENGINE=HEAP;

DROP PROCEDURE IF EXISTS test_students_n_classes;
DROP PROCEDURE IF EXISTS test_eval_classrooms_scores;
DELIMITER $$
CREATE PROCEDURE test_eval_classrooms_scores(
        studentsPerClass DOUBLE)
BEGIN
    UPDATE test_classrooms AS c
    INNER JOIN (
        SELECT
                c.id,
                SUM(tr.strength)
--             AVG(tr.strength)/(0.1 + STD(tr.strength))
                    AS score
            FROM test_classrooms AS c
            INNER JOIN test_students AS f ON f.classroom = c.id
            INNER JOIN test_students AS t ON t.id > f.id AND t.classroom = c.id
            INNER JOIN test_relations AS tr ON tr.id_from = f.id AND tr.id_to = t.id
            GROUP BY c.id) AS scores ON scores.id = c.id
    SET
        -- If we do some "fake Swaps", then number of students in a classroom may differ from initial distribution, in such case, give this difference a weight
        -- The goal is to have balanced classrooms (globalScore is always negative, and the farther from balanced classroom, the more negative score)
        c.globalScore = -POW( (SELECT SUM(1) FROM test_students AS s WHERE s.classroom = c.id)-studentsPerClass,2 )*SQRT(studentsPerClass),
        c.score = scores.score + c.globalScore
            ;
END$$

CREATE PROCEDURE test_students_n_classes (
        eleves INT UNSIGNED,
        partitionnings INT UNSIGNED,
        tries INT UNSIGNED,
        iterationsPerTry INT UNSIGNED,
        fakeSwapsProportion DOUBLE)
BEGIN
    
    SET @tryScore := NULL;
    SET @tries := tries;
    WHILE (@tries > 0) DO
        -- We create a random partitionning
        SET @currentScore := NULL;
        UPDATE test_students SET classroom = FLOOR(1+RAND()*partitionnings);
        
        -- We try a change, then eval the new partitionning score, and if better, keep that change effective
        SET @iterationsPerTry := iterationsPerTry;
        WHILE (@iterationsPerTry > 0) DO
            SET @randomStud1 := FLOOR(1+RAND()*eleves);
            SET @randomClass1 := (SELECT classroom FROM test_students WHERE id = @randomStud1);
            SET @randomClass2 := (SELECT id FROM test_classrooms AS c WHERE c.id != @randomClass1 ORDER BY RAND() LIMIT 1);
            SET @randomStud2 := (SELECT id FROM test_students AS s WHERE s.classroom = @randomClass2 ORDER BY RAND() LIMIT 1);
            UPDATE test_students AS s SET classroom = @randomClass2 WHERE s.id = @randomStud1;
            IF (RAND() > fakeSwapsProportion) THEN
                UPDATE test_students AS s SET classroom = @randomClass1 WHERE s.id = @randomStud2;
            END IF;
            
            CALL test_eval_classrooms_scores(eleves/partitionnings);
            SET @newScore := (
                SELECT
                        SUM(score)
--                         AVG(score)/(0.01 + STD(score))
                    FROM test_classrooms AS t);
            IF (@newScore > @currentScore OR @currentScore IS NULL) THEN
                SET @currentScore := @newScore;
                SET @iterationsPerTry := iterationsPerTry;
            ELSE
                UPDATE test_students AS s SET classroom = @randomClass1 WHERE s.id = @randomStud1;
                UPDATE test_students AS s SET classroom = @randomClass2 WHERE s.id = @randomStud2;
                SET @iterationsPerTry := @iterationsPerTry - 1;
            END IF;
        END WHILE;
        
        IF (@currentScore > @tryScore OR @tryScore IS NULL) THEN
            TRUNCATE TABLE test_students_result;
            INSERT INTO test_students_result (SELECT * FROM test_students);
            SET @tryScore := @currentScore;
            SET @tries := tries;
        ELSE
            SET @tries := @tries - 1;
        END IF;
    END WHILE;
    COMMIT;
END$$

DELIMITER ;

-- Step 0: values
SET @eleves := 60;
SET @partitionnings := 3;
SET @tries := 20; -- Actually, it's the number of consecurive failed tries
SET @iterationsPerTry := 200; -- Actually, it's the number of consecutive failed iterations in a try
SET @fakeSwapsProportion := 0.2; -- Probability 0(=only swaps)..1(=no swap) of moving student B to class cA when swapping students A and B from classrooms cA and cB

TRUNCATE TABLE test_students;
INSERT INTO test_students (SELECT n AS id, NULL FROM integers WHERE n BETWEEN 1 AND @eleves);
TRUNCATE TABLE test_classrooms;
INSERT INTO test_classrooms (SELECT n AS id, NULL, NULL AS score FROM integers WHERE n BETWEEN 1 AND @partitionnings);

-- Step 1: each pair of student must have an "affinity score", from 0 (they "must" not be together) to 1 (they "must" be together in a class)
-- Commented out are some suggestions to try
TRUNCATE TABLE test_relations;
INSERT INTO test_relations (id_from, id_to, strength) (
    SELECT
        f.id,
        t.id,
--         IF(FLOOR(f.id / (@eleves/@partitionnings)) = FLOOR(t.id / (@eleves/@partitionnings)), 1, 0)
--         f.id / t.id
        RAND()
    FROM test_students AS f
    INNER JOIN test_students AS t ON t.id > f.id);

-- Step 2: calculate
CALL test_students_n_classes(@eleves, @partitionnings, @tries, @iterationsPerTry, @fakeSwapsProportion);

-- Step 3: results!
SELECT
    c.id,
    c.score,
    c.globalScore,
    GROUP_CONCAT(s.id ORDER BY s.id ASC) AS students,
    SUM(1) AS studentCount
FROM test_classrooms AS c
INNER JOIN test_students_result AS s ON s.classroom = c.id
GROUP BY c.id
ORDER BY studentCount;

SELECT * FROM test_relations;

Logiquement, il est possible de mettre de grosses grosses valeurs dans les "SET", de lancer le calcul dans un client, et de se connecter avec un autre client pour "auditer" la table "test_students_result", et obtenir des résultats intermédiaires pendant le calcul (qu'on peut alors laisser traîner sur plusieurs heures ou une nuit entière).

[Thêta Tau Tau]

A partir de paires -1 à +1 comme proposé par Xenos, tu peux créer une matrice nxn, où n est le nombre d'élèves, avec des 1 sur la diagonale, et pour chaque cellule en dehors de la diagonale la valeur d'affinité entre les deux élèves (en mettant 0 par défaut vu que tu vas pas rentrer toutes les paires possibles).

Ensuite cette matrice peut être utilisée dans plein d'algos de partitionnement, par ex les K-moyennes pour un des algos les plus simples.

[Xenos]

K-moyennes en effet et pas K-partitionnement (je n'étais pas tombé loin =P)
Si je vois bien comment s'en servir dans un espace à N dimensions (ie: pour chaque élève, donner N caractéristiques quantifiées et faire les calculs de norme et de moyenne dans cet espace à N dimensions correspondant, avec la norme euclidienne classique), je ne vois pas du tout comment tu t'en servirai pour une matrice de relations entre élèves?!

Avec une telle matrice, Theta, comment tu calcules la moyenne et la distance de chaque élève à cette moyenne (points-clefs des K-moyennes)?

[Thêta Tau Tau]

Pour prendre un exemple : on a 3 élèves A, B et C. On voudrait que A et B soient ensemble et que A et C ne soient pas ensemble.

On a donc la matrice suivante :

Code :

   A   B   C
A  1   1  -1
B  1   1   0
C -1   0   1

On a donc un espace en 3 dimensions, avec par exemple la position de l'élève A = (1,1,-1)

A partir de ces positions on peut faire les K-means.



Après je ne suis pas sur que les résultats soient exploitables, car d'expérience les groupes créés par K-means sont foireux 3 fois sur 4, et puis l'algo créer des groupes de taille différentes (donc ça colle pas pour faire des classes). Mais ça peut être une première étape.

[Xenos]

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.

[Thêta Tau Tau]

On n'a pas de contraintes particulières en terme de calcul ici. On n'est pas dans le web où le jeu vidéo où on veut générer une page ou une frame en quelques ms, on est dans le cas d'un calcul qu'on lance quelques fois par an.

Je fait fréquemment ce genre de calcul en génétique (avec des matrices d'apparentement entre individus par exemple), avec 600 variables, le temps de calcul n'est pas un problème (quelques secondes). A la limite avec certains algo implémentés avec les pieds on en aurait pour quelques minutes (ce qui reste acceptable pour un calcul qu'on lance une fois par an).

[Sephi-Chan]

Hm, donc rien de très exploitable directement.

Notre école compte environ 300 élèves. Dans l'idée, c'est assez simple : chaque enseignant prépare sa liste d'élèves sortants, avec une note de comportement et une note de travail (qui indique si l'élève est scolaire et autonome), et les collègues des classes qui accueillent ces nouveaux élèves se répartissent ces élèves. Pour la plupart des élèves, il n'y a rien de particulier à noter, on répartit les élèves les plus faciles, avant d'attaquer ceux un peu plus sensibles selon des critères variés (compatibilité élève/enseignant, paires à séparer, etc.).

[Xenos]

Creuse côté matlab sinon, car c'est le genre de problèmes qu'ils ont déjà résolus: N points, avec des "forces" de répulsion entre certains [élèves ne devant pas être ensemble], quelques contraintes [certains points doivent faire parti du partitionnement X, car ces élèves ont déjà été mis dans la classe X] et une répulsion avec certains partitionnement (des élèves ne devant pas être dans certaines classes), c'est classique de ce côté-là, et directement exploitable (parce que le reste, oui, il te faudra passer une soirée de code grand max).