Partitionnement via k-means avec Oracle
Depuis le site web de l’Assemblée Nationale, il est possible d’accéder aux résultats des tous les scrutins législatifs. On peut aussi visualiser le détail des votes par députés.
Les scrutins solennels sont les plus intéressants car tous les députés sont invités à voter et la participation y est relativement importante. Avec un peu de web-scrapping, on peut récupérer les résultats pour les analyser.
Dans ce billet, j’ai entreprit de vérifier s’il était possible de réaliser un partitionnement de ces données via un algorithme d’apprentissage non-supervisé.
En effet, on devrait observer une relative homogénéité des votes au sein d’un groupe parlementaire (en raison des consignes de vote). Cet aspect devrait donc permettre à un algorithme de partitionnement comme le k-means de diviser la population en sous-ensembles correspondants aux groupes parlementaires.
Oracle met à disposition une version améliorée de cet algorithme. Néanmoins, le détail des améliorations n’est pas documenté et le nombre de variable sur lesquelles il est possible de jouer reste limité. A noter que l’utilisation du package DBMS_DATA_MINING nécessite la licence Oracle Advanced Analytics.
Pour mener à bien mes tests (sans être pénalisé par l’absentéisme parlementaire!), je me suis intéressé aux seuls scrutins solennels ayant enregistré plus de 75% de participation. J’ai aussi exclu les députés n’ayant pas participé à au moins 85% de ces votes. Enfin, j’ai éliminé les « non-inscrits » (et ceux ayant changé d’étiquette en cours de route) car ils sont par définition difficile à classer!
Je parviens à une matrice de votes de 497 députés (sur 577) lors de 96 scrutins solennels (sur 98 survenus jusqu’à présent dans la 14ème législature): kmeans-votes-assemblee.csv
Le codage utilisé est -1 (contre), 1 (pour) et 0 (abstention). Les valeurs manquantes correspondent aux absences.
Ultérieurement, lors de la mise en forme des données, les absences seront assimilées aux abstentions. C’est un parti pris discutable mais il faut bien faire des choix!
Préparation des données
Les données ont été préalablement chargées dans la table votes_part:
SQL> desc votes_part
Name Null? Type
----------------------------------------- -------- ----------------------------
DEPUTE VARCHAR2(300)
PARTI VARCHAR2(300)
S1062 NUMBER
S1070 NUMBER
...
S991 NUMBER
S994 NUMBER
S995 NUMBER
SQL> SELECT COUNT (*)
2 FROM user_tab_columns
3 WHERE table_name = 'VOTES_PART';
COUNT(*)
----------
98
SQL>
L’algorithme k-means reposant sur un calcul de distance, il n’est pas adapté aux cas des variables nominales. Dans notre cas, il nous faut donc passer par une étape de conversion du résultat de chaque vote en plusieurs variables indicatrices (« dummy variable « ).
Par exemple, pour le scrutin 1062 dont le résultat dans VOTES_PART est stocké dans le champ S1062, on va produire deux nouveaux champs S1062O et S1062N (O et N pour Oui ou Non). Ces derniers s’interprétant par rapport à une référence implicite qui est l’abstention (ou l’absence).
Ainsi on pourra avoir les cas de figures suivant:
| Vote | Pour | Contre | Abstention (ou absence) |
| Codage initial | S1062=1 | S1062=0 | S1062=-1 (ou NULL) |
| Codage avec variables indicatrices | S10620=1
S1062N=0 |
S10620=0
S1062N=1 |
S10620=0
S1062N=0 |
La mise en oeuvre de cette transformation est réalisée par l’intermédiaire d’une vue. Comme le nombre de champs à prendre en compte est important, j’utilise un bloc PL/SQL pour générer dynamiquement le code de la vue:
SQL> DECLARE
2 l_v_ddl CLOB := 'CREATE OR REPLACE VIEW V_VOTES_PART as SELECT ';
3 BEGIN
4 FOR rec
5 IN (SELECT ROWNUM rn, col
6 FROM (SELECT column_name col
7 FROM user_tab_columns
8 WHERE table_name = 'VOTES_PART'
9 AND column_name NOT LIKE 'S%'
10 UNION ALL
11 SELECT 'case('
12 || column_name
13 || ') when 1 then 1 else 0 end '
14 || column_name
15 || 'O, case('
16 || column_name
17 || ') when -1 then 1 else 0 end '
18 || column_name
19 || 'N'
20 FROM user_tab_columns
21 WHERE table_name = 'VOTES_PART' AND column_name LIKE 'S%'))
22 LOOP
23 l_v_ddl := l_v_ddl || CASE WHEN rec.rn != 1 THEN ',' END || rec.col;
24 END LOOP;
25
26 l_v_ddl := l_v_ddl || ' FROM VOTES_PART';
27
28 EXECUTE IMMEDIATE l_v_ddl;
29 END;
30 /
PL/SQL procedure successfully completed.
SQL> SELECT COUNT (*)
2 FROM user_tab_columns
3 WHERE table_name = 'V_VOTES_PART';
COUNT(*)
----------
194
SQL> desc V_VOTES_PART
Name Null? Type
----------------------------------------- -------- ----------------------------
DEPUTE VARCHAR2(300)
PARTI VARCHAR2(300)
S1062O NUMBER
S1062N NUMBER
S1070O NUMBER
S1070N NUMBER
...
S991N NUMBER
S994O NUMBER
S994N NUMBER
S995O NUMBER
S995N NUMBER
SQL>
La vue contient 194 champs (2*96+2).
Mise en place de la table de paramétrage du modèle
Le critère principal est le nombre de clusters que l’on souhaite obtenir après partitionnement (clus_num_clusters). Dans le cas présent, si on fait abstraction des « non-inscrits », il existe 6 groupes parlementaires représentés à l’Assemblée. On va donc réaliser un partitionnement de la population en 6 clusters:
SQL> CREATE TABLE assemblee_clu_settings 2 ( 3 setting_name VARCHAR2 (30 BYTE), 4 setting_value VARCHAR2 (30 BYTE) 5 ); Table created. SQL> BEGIN 2 -- Utilisation d'un bloc PLSQL anonyme pour pouvoir référencer 3 -- les constantes du package DBMS_DATA_MINING 4 5 INSERT INTO assemblee_clu_settings (setting_name, setting_value) 6 VALUES (DBMS_DATA_MINING.algo_name, DBMS_DATA_MINING.algo_kmeans); 7 8 INSERT INTO assemblee_clu_settings (setting_name, setting_value) 9 VALUES (DBMS_DATA_MINING.prep_auto, DBMS_DATA_MINING.prep_auto_off); 10 11 INSERT INTO assemblee_clu_settings (setting_name, setting_value) 12 VALUES (DBMS_DATA_MINING.clus_num_clusters, 6); 13 14 COMMIT; 15 END; 16 / PL/SQL procedure successfully completed. SQL>
Création du modèle
On exclut les champs DEPUTE et PARTI de l’analyse. Seuls les résultats des scrutins (SxxxO et SxxxN) sont pris en compte:
SQL> SET TIMING ON; SQL> DECLARE 2 l_xform DBMS_DATA_MINING_TRANSFORM.transform_list; 3 BEGIN 4 DBMS_DATA_MINING_TRANSFORM.set_transform (l_xform, 5 'DEPUTE', 6 NULL, 7 NULL, 8 NULL); 9 DBMS_DATA_MINING_TRANSFORM.set_transform (l_xform, 10 'PARTI', 11 NULL, 12 NULL, 13 NULL); 14 DBMS_DATA_MINING.create_model ( 15 model_name => 'ASSEMBLEE_KMEANS_MODEL', 16 mining_function => DBMS_DATA_MINING.clustering, 17 data_table_name => 'V_VOTES_PART', 18 case_id_column_name => NULL, 19 target_column_name => NULL, 20 settings_table_name => 'ASSEMBLEE_CLU_SETTINGS', 21 xform_list => l_xform); 22 END; 23 / PL/SQL procedure successfully completed. Elapsed: 00:00:11.59 SQL>
La fonction CLUSTER_ID permet de déterminer le groupe auquel le modèle de partitionnement affecte les données:
SQL> SELECT CLUSTER_ID (assemblee_kmeans_model USING *) clust, COUNT (*) nb
2 FROM v_votes_part
3 GROUP BY CLUSTER_ID (assemblee_kmeans_model USING *)
4 ORDER BY 1;
CLUST NB
---------- ----------
2 283
4 167
6 22
8 8
10 10
11 7
6 rows selected.
SQL>
On peut ensuite croiser le résultat de ce partitionnement avec l’appartenance réelle des députés aux groupes parlementaires:
SQL> column PARTI format a55
SQL> set lines 120
SQL> set NUMF 999999
SQL> SELECT *
2 FROM (SELECT a.parti, CLUSTER_ID (assemblee_kmeans_model USING *) cls
3 FROM v_votes_part a) PIVOT (COUNT (*)
4 AS cnt
5 FOR (cls)
6 IN ('2' AS p1,
7 '4' AS p2,
8 '6' AS p3,
9 '8' AS p4,
10 '10' AS p5,
11 '11' AS p6));
PARTI P1_CNT P2_CNT P3_CNT P4_CNT P5_CNT P6_CNT
------------------------------------------------------- ------- ------- ------- ------- ------- -------
Groupe Les Républicains 0 167 0 0 10 7
Groupe radical, républicain, démocrate et progressiste 13 0 0 0 0 0
Groupe écologiste 16 0 0 0 0 0
Groupe socialiste, républicain et citoyen 254 0 0 0 0 0
Groupe de l'union des démocrates et indépendants 0 0 22 0 0 0
Groupe de la gauche démocrate et républicaine 0 0 0 8 0 0
6 lignes sélectionnées.
SQL>
On constate que la performance du partitionnement est variable en fonction du groupe considéré.
Les partitions P3 et P4 recouvrent de manière claire un groupe parlementaire (respectivement « Groupe de l’union des démocrates et indépendants » et « Groupe de la gauche démocrate et républicaine »). En revanche, les partitions P2, P5 et P6 correspondent à un éclatement des membres du groupe « Les Républicains ». Enfin le groupe P1 correspond à un panachage d’un bloc de gauche comprenant les écologistes, les radicaux et les socialistes.
L’algorithme k-means étant itératif on peut augmenter la limite d’itération (passage du défaut 3 à 10) pour voir si cela permet de parvenir à une meilleure classification:
SQL> BEGIN 2 INSERT INTO assemblee_clu_settings (setting_name, setting_value) 3 VALUES (DBMS_DATA_MINING.kmns_iterations, 10); 4 5 COMMIT; 6 END; 7 / Procédure PL/SQL terminée avec succès. SQL>
On reconstruit le modèle pour tenir compte du nouveau nombre d’itérations:
SQL> BEGIN 2 DBMS_DATA_MINING.drop_model (model_name => 'ASSEMBLEE_KMEANS_MODEL'); 3 END; 4 / Procédure PL/SQL terminée avec succès. SQL> SET TIMING ON; SQL> DECLARE 2 l_xform DBMS_DATA_MINING_TRANSFORM.transform_list; 3 BEGIN 4 DBMS_DATA_MINING_TRANSFORM.set_transform (l_xform, 5 'DEPUTE', 6 NULL, 7 NULL, 8 NULL); 9 DBMS_DATA_MINING_TRANSFORM.set_transform (l_xform, 10 'PARTI', 11 NULL, 12 NULL, 13 NULL); 14 DBMS_DATA_MINING.create_model ( 15 model_name => 'ASSEMBLEE_KMEANS_MODEL', 16 mining_function => DBMS_DATA_MINING.clustering, 17 data_table_name => 'V_VOTES_PART', 18 case_id_column_name => NULL, 19 target_column_name => NULL, 20 settings_table_name => 'ASSEMBLEE_CLU_SETTINGS', 21 xform_list => l_xform); 22 END; 23 / Procédure PL/SQL terminée avec succès. Ecoulé : 00 :00 :08.75 SQL>
Le résultat du partitionnement est sensiblement amélioré:
SQL> SELECT DISTINCT CLUSTER_ID (assemblee_kmeans_model USING *) clust
2 FROM v_votes_part
3 ORDER BY 1;
CLUST
-------
4
6
8
9
10
11
6 lignes sélectionnées.
SQL>
SQL> SELECT *
2 FROM (SELECT a.parti, CLUSTER_ID (assemblee_kmeans_model USING *) cls
3 FROM v_votes_part a) PIVOT (COUNT (*)
4 AS cnt
5 FOR (cls)
6 IN ('4' AS p1,
7 '6' AS p2,
8 '8' AS p3,
9 '9' AS p4,
10 '10' AS p5,
11 '11' AS p6));
PARTI P1_CNT P2_CNT P3_CNT P4_CNT P5_CNT P6_CNT
------------------------------------------------------- ------- ------- ------- ------- ------- -------
Groupe Les Républicains 184 0 0 0 0 0
Groupe radical, républicain, démocrate et progressiste 0 0 0 0 1 12
Groupe écologiste 0 0 0 0 0 16
Groupe socialiste, républicain et citoyen 0 0 0 0 247 7
Groupe de l'union des démocrates et indépendants 0 0 11 11 0 0
Groupe de la gauche démocrate et républicaine 0 8 0 0 0 0
6 lignes sélectionnées.
SQL>
On a désormais 3 partitions qui recoupent (quasi-exactement) des groupes parlementaires:
- P1 contient 100% des membres du « Groupe Les Républicains »
- P2 contient 100% des membres du « Groupe de la gauche démocrate et républicaine »
- P5 contient 97% des membres du « Groupe Socialiste, républicain et citoyen » (la partition contient aussi un unique député des radicaux de gauche)
En revanche, les membres du « Groupe de l’union des démocrates et indépendants » sont désormais divisés dans deux partitions P3 et P4. Ils ne sont néanmoins pas mélangés avec des députes d’autres tendances.
Enfin, la partition P6 contient un panachage de députés de gauche: « Groupe écologiste », « Groupe radical, républicain, démocrate et progressiste » et 7 membres du « Groupe socialiste, républicain et citoyen » (des frondeurs?).
Cela sous-entend que pour ces derniers, l’algorithme mesure une « distance » moins importante entre leurs votes qu’entre ceux des individus des partitions P3 et P4 (regroupant pourtant des membres d’un même groupe parlementaire).
Une interprétation serait de dire que le « Groupe de l’union des démocrates et indépendants » contient deux « tendances » dont les positions divergent de manière récurrente.
On peut maintenant tenter d’ajouter une nouvelle partition dans le modèle afin de voir si cela permet à l’algorithme d’aboutir à une distinction entre les individus de la partition P6:
SQL> BEGIN 2 UPDATE assemblee_clu_settings 3 SET setting_value = 7 4 WHERE setting_name = DBMS_DATA_MINING.clus_num_clusters; 5 6 COMMIT; 7 END; 8 / Procédure PL/SQL terminée avec succès. SQL>
On reconstruit le modèle pour tenir compte du nouveau nombre de clusters:
SQL> BEGIN
2 DBMS_DATA_MINING.drop_model (model_name => 'ASSEMBLEE_KMEANS_MODEL');
3 END;
4 /
Procédure PL/SQL terminée avec succès.
SQL> SET TIMING ON;
SQL> DECLARE
2 l_xform DBMS_DATA_MINING_TRANSFORM.transform_list;
3 BEGIN
4 DBMS_DATA_MINING_TRANSFORM.set_transform (l_xform,
5 'DEPUTE',
6 NULL,
7 NULL,
8 NULL);
9 DBMS_DATA_MINING_TRANSFORM.set_transform (l_xform,
10 'PARTI',
11 NULL,
12 NULL,
13 NULL);
14 DBMS_DATA_MINING.create_model (
15 model_name => 'ASSEMBLEE_KMEANS_MODEL',
16 mining_function => DBMS_DATA_MINING.clustering,
17 data_table_name => 'V_VOTES_PART',
18 case_id_column_name => NULL,
19 target_column_name => NULL,
20 settings_table_name => 'ASSEMBLEE_CLU_SETTINGS',
21 xform_list => l_xform);
22 END;
23 /
Procédure PL/SQL terminée avec succès.
Ecoulé : 00 :00 :10.68
SQL> SET TIMING OFF;
SQL> SELECT DISTINCT CLUSTER_ID (assemblee_kmeans_model USING *) clust
2 FROM v_votes_part
3 ORDER BY 1;
CLUST
-------
4
6
8
9
10
12
13
7 lignes sélectionnées.
SQL>
On peut constater que l’ajout d’une partition a permis à l’algorithme de parvenir à la différentiation des membres du « Groupe écologiste » (P7) et des membres du « Groupe radical, républicain, démocrate et progressiste » (P6):
SQL> SELECT *
2 FROM (SELECT a.parti, CLUSTER_ID (assemblee_kmeans_model USING *) cls
3 FROM v_votes_part a) PIVOT (COUNT (*)
4 AS cnt
5 FOR (cls)
6 IN ('4' AS p1,
7 '6' AS p2,
8 '8' AS p3,
9 '9' AS p4,
10 '10' AS p5,
11 '12' AS p6,
12 '13' AS p7));
PARTI P1_CNT P2_CNT P3_CNT P4_CNT P5_CNT P6_CNT P7_CNT
------------------------------------------------------- ------- ------- ------- ------- ------- ------- -------
Groupe Les Républicains 184 0 0 0 0 0 0
Groupe radical, républicain, démocrate et progressiste 0 0 0 0 1 11 1
Groupe écologiste 0 0 0 0 0 0 16
Groupe socialiste, républicain et citoyen 0 0 0 0 249 3 2
Groupe de l'union des démocrates et indépendants 0 0 11 11 0 0 0
Groupe de la gauche démocrate et républicaine 0 8 0 0 0 0 0
6 lignes sélectionnées.
SQL>
Ce résultat est très intéressant car à l’exception de la séparation en deux des membres du « Groupe de l’union des démocrates et indépendants » et de 5 parlementaires mal-classés, la très large majorité des députés peuvent être groupés dans leur famille politique en fonction de leur votes. Les consignes paraissent donc plutôt bien respectées!