Exercices corrigés de SNT : les données structurées et leur traitement

a) 412 peut être une population en milliers d'habitants, un prix en dollars, une altitude en mètres, un nombre de trajets, un identifiant de station. On ne peut pas trancher parce qu'il manque le DESCRIPTEUR, c'est-à-dire le nom de la grandeur que la valeur mesure, et l'unité qui l'accompagne. C'est la première leçon du chapitre : une valeur sans descripteur n'est pas une donnée, c'est un caractère.

b) La donnée est la valeur mesurée ou enregistrée, par exemple le contenu de l'image, c'est-à-dire les pixels. Le descripteur est le nom qui dit ce que la valeur représente, par exemple « date de prise de vue » ou « latitude ». La métadonnée est une donnée qui décrit une autre donnée : pour une photographie, la date, l'heure, le modèle de l'appareil, l'ouverture, la position GPS. Le contenu est la photo ; tout le reste, qui parle de la photo, est métadonnée.

c) Structuré : le tableur de notes et le fichier CSV de relevés météo, où chaque valeur occupe une case identifiée par une ligne et une colonne. Semi-structuré : la page web, qui porte des balises et donc une organisation, sans que celle-ci impose un tableau régulier. Non structuré : la lettre de motivation et l'enregistrement audio, où aucun modèle ne dit à l'avance ce que contient telle partie du document. Le critère n'est pas « est-ce lisible par un ordinateur », c'est « le modèle d'organisation est-il explicite et régulier ».

d) Parce que les métadonnées sont systématiques, uniformes et immédiatement exploitables par un programme, alors que le contenu demande une interprétation. Lire dix mille messages coûte cher ; lire les métadonnées de dix mille messages, qui a écrit à qui, quand et depuis où, se fait en une seconde et reconstitue un emploi du temps, un cercle de relations et des déplacements. Exemple concret : sans ouvrir une seule photo, les métadonnées de position d'un album révèlent l'adresse du domicile, celle de l'établissement scolaire et les horaires habituels de trajet.

e) Le fichier contient $8 \times 15\ 000 = 120\ 000$ valeurs de données. Il compte $15\ 000 + 1 = 15\ 001$ lignes, la ligne supplémentaire étant celle des descripteurs. L'erreur classique est de compter la ligne d'en-tête parmi les enregistrements, ce qui fausse ensuite toutes les moyennes d'un facteur $15\ 001 / 15\ 000$, écart petit mais qui suffit à faire échouer une comparaison.

a) Il y a 4 descripteurs, nom, ville, population et superficie, et 3 enregistrements, la première ligne étant l'en-tête et non une donnée. La superficie du deuxième enregistrement, celui de Québec, vaut $454{,}3$. Attention : le deuxième enregistrement n'est pas la deuxième ligne du fichier, c'est la troisième. Compter les enregistrements à partir de la ligne d'en-tête est l'erreur qui coûte le plus de points sur ce chapitre.

b) En français, la virgule est le séparateur DÉCIMAL : la superficie $431{,}5$ contiendrait alors une virgule, et le lecteur du fichier croirait voir deux champs au lieu d'un. La ligne prendrait 5 champs au lieu de 4 et le fichier deviendrait incohérent. Deux solutions en pratique : utiliser un autre séparateur de champ, point-virgule ou tabulation, ce que font tous les tableurs francophones ; ou bien encadrer chaque valeur de guillemets, le lecteur sachant alors qu'une virgule entre guillemets appartient à la valeur.

c) La ligne s'écrit avec des guillemets autour du champ qui contient le séparateur, s'il s'agissait d'une virgule. Ici le séparateur est le point-virgule et le nom ne contient qu'une virgule : la ligne "Saint-Jean-sur-Richelieu, Québec";Québec;95114;79.0 est déjà correcte sans guillemets. La règle générale à retenir : on encadre de guillemets tout champ contenant le séparateur, un saut de ligne ou un guillemet, et un guillemet à l'intérieur d'un champ se double.

d) C'est un problème d'ENCODAGE. Le fichier est écrit en UTF-8, où le caractère « é » occupe deux octets, mais il est relu comme s'il était écrit en Latin-1, où chaque octet vaut un caractère : les deux octets sont donc affichés comme deux caractères, Ã et ©. La correction consiste à rouvrir le fichier en déclarant l'encodage UTF-8, jamais à retaper les accents à la main, ce qui ne ferait que déplacer le problème au prochain échange.

e) Avantages : c'est un fichier texte, donc lisible et modifiable par n'importe quel programme, sans logiciel propriétaire ; il est très compact et se traite ligne par ligne, ce qui permet de manipuler des fichiers plus gros que la mémoire disponible. Limites : il ne contient AUCUN type, tout est du texte, si bien que 007 et 7 se confondent selon le lecteur ; et il ne porte ni formule, ni mise en forme, ni feuilles multiples, ni contrainte d'intégrité. Le CSV échange des valeurs, il ne conserve pas un document.

a) Deux lignes satisfont le filtre : Mont-Royal et Laurier. Projetées sur station et vélos, elles donnent Mont-Royal 17 et Laurier 9. Une sélection garde des lignes entières, une projection ne garde que certaines colonnes : ici on fait les deux à la suite, et l'ordre n'a pas d'importance sur le résultat.

b) Ligne par ligne. Berri : 31 bornes, donc plus de 25, et 12 vélos, donc au moins 10 : elle passe. Rosemont : 23 bornes, ce n'est pas plus de 25, éliminée. Beaubien : 19 bornes, éliminée. Papineau : 27 bornes mais 0 vélo, éliminée. Mont-Royal : 35 bornes et 17 vélos, elle passe. Laurier : 23 bornes, éliminée. Il reste donc 2 stations, Berri et Mont-Royal. Le piège est le ET : il faut que les DEUX conditions soient vraies, alors qu'une lecture rapide retient les lignes qui en satisfont une.

c) Berri : $12 / 31 \approx 0{,}39$. Rosemont : $23 / 23 = 1{,}00$. Beaubien : $4 / 19 \approx 0{,}21$. Papineau : $0 / 27 = 0{,}00$. Mont-Royal : $17 / 35 \approx 0{,}49$. Laurier : $9 / 23 \approx 0{,}39$. La plus vide est Papineau, avec un taux nul : aucun vélo disponible. Rosemont est au contraire pleine, aucune borne libre, ce qui est un problème symétrique pour l'usager qui veut déposer un vélo.

d) Un filtre agit sur les LIGNES : il en garde certaines et en jette d'autres, sans jamais toucher au nombre de colonnes. Une projection agit sur les COLONNES : elle garde toutes les lignes mais réduit le nombre de champs de chacune. C'est la projection qui peut faire apparaître des doublons, car deux lignes qui différaient seulement par une colonne supprimée deviennent identiques. Ici, projeter sur le seul arrondissement transforme six lignes distinctes en six lignes dont trois valeurs seulement sont différentes.

e) La liste est Ville-Marie, Rosemont, Le Plateau, soit trois arrondissements. Ce n'est pas une simple projection parce que la projection sur la colonne arrondissement donnerait six lignes, avec des répétitions. Il faut y ajouter une opération de DÉDOUBLONNAGE, qui ne conserve qu'un exemplaire de chaque valeur distincte. Projection et élimination des doublons sont deux opérations différentes, et les confondre est une erreur fréquente quand on passe ensuite au langage SQL.

a) Les nombres de vélos sont Papineau 0, Beaubien 4, Laurier 9, Berri 12, Mont-Royal 17, Rosemont 23. Le tri croissant donne donc S21, S12, S18, S03, S05, S07.

b) Arrondissements dans l'ordre alphabétique : Le Plateau, Rosemont, Ville-Marie. Dans Le Plateau, bornes décroissantes : Mont-Royal 35 puis Laurier 23, soit S05, S18. Dans Rosemont : Rosemont 23 puis Beaubien 19, soit S07, S12. Dans Ville-Marie : Berri 31 puis Papineau 27, soit S03, S21. Le résultat complet est S05, S18, S07, S12, S03, S21.

c) « À arrondissement égal » signifie que la deuxième clé ne départage que les lignes dont la première clé donne le même résultat : elle n'intervient jamais entre deux arrondissements différents. L'ordre des clés change le résultat parce qu'un tri est un ordre TOTAL construit par priorité : la première clé décide, la seconde n'a la parole qu'en cas d'égalité. Deux filtres, eux, sont deux conditions qui doivent être vraies simultanément, et l'intersection de deux ensembles ne dépend pas de l'ordre dans lequel on la calcule. Priorité pour un tri, conjonction pour un filtre.

d) Si le tri est stable, on trie d'abord par la clé la MOINS prioritaire, ici les bornes décroissantes, puis par la clé la plus prioritaire, ici l'arrondissement. Lors du second tri, deux lignes de même arrondissement gardent l'ordre que le premier tri leur avait donné, c'est-à-dire l'ordre par bornes décroissantes : le résultat est exactement le tri à deux clés. Sans stabilité, le second tri pourrait mélanger les lignes de même arrondissement et détruire le travail du premier. C'est la seule raison pour laquelle la stabilité est une propriété recherchée.

e) Avec $n = 20\ 000$ : le premier fait de l'ordre de $20\ 000^{2} = 400\ 000\ 000$ opérations, soit quatre cents millions. Le second fait de l'ordre de $20\ 000 \times \log_{2}(20\ 000) \approx 20\ 000 \times 14{,}29 \approx 285\ 754$ opérations. Le rapport vaut environ $1\ 400$ : le second est mille quatre cents fois plus rapide. Sur un million de lignes, le rapport dépasserait cinquante mille. C'est pourquoi aucun outil sérieux n'utilise un tri quadratique au-delà de quelques centaines de lignes.

a) Un octet vaut 8 bits. Un kibioctet vaut $2^{10} = 1\ 024$ octets. La raison est que les adresses mémoire sont binaires : ajouter un fil d'adresse double la capacité, si bien que les tailles naturelles d'un ordinateur sont les puissances de 2, jamais les puissances de 10. Le préfixe kilo, qui vaut 1 000, a longtemps été employé abusivement ; les préfixes kibi, mébi et gibi ont été créés pour lever l'ambiguïté. L'écart n'est pas négligeable : il atteint déjà 10 pour cent au niveau du gibioctet.

b) Un relevé occupe $4 \times 8 = 32$ octets. En une heure il y a $60 / 5 = 12$ relevés, donc $12 \times 24 = 288$ par jour et $288 \times 365 = 105\ 120$ par an. Le volume annuel d'une station vaut $105\ 120 \times 32 = 3\ 363\ 840$ octets, soit $3\ 363\ 840 / 1\ 048\ 576 \approx 3{,}21$ Mio. Passer par le nombre de relevés avant de multiplier par la taille évite l'erreur la plus fréquente, qui est de multiplier des durées par des octets sans repasser par un dénombrement.

c) Pour 1 200 stations : $3\ 363\ 840 \times 1\ 200 = 4\ 036\ 608\ 000$ octets. En gibioctets, $4\ 036\ 608\ 000 / 1\ 073\ 741\ 824 \approx 3{,}76$ Gio par an. L'ordre de grandeur est instructif : un réseau complet de stations météo produit en un an moins qu'un seul film en haute définition.

d) La liaison porte 200 Mbit/s, soit $200 / 8 = 25$ Mo/s en mégaoctets décimaux, c'est-à-dire $25\ 000\ 000$ octets par seconde. Le transfert dure $4\ 036\ 608\ 000 / 25\ 000\ 000 \approx 161{,}5$ secondes, soit environ 2 minutes et 41 secondes. Le piège est la division par 8 : un débit s'annonce en bits, un volume se compte en octets, et oublier la conversion multiplie le temps annoncé par huit.

e) Dix ans en trois copies représentent $4\ 036\ 608\ 000 \times 10 \times 3 = 121\ 098\ 240\ 000$ octets, soit $121\ 098\ 240\ 000 / 1\ 099\ 511\ 627\ 776 \approx 0{,}11$ Tio. Trois copies parce qu'une seule copie n'est pas une sauvegarde : un disque tombe en panne, un centre de données brûle, une erreur humaine efface. La règle usuelle est trois copies, sur deux supports différents, dont une hors site. Le coût du stockage est ici dérisoire au regard du coût d'une perte définitive de dix ans de mesures.

a) Ville-Marie : 2 stations, $31 + 27 = 58$ bornes, $418 + 236 = 654$ trajets. Rosemont : 2 stations, $23 + 19 = 42$ bornes, $184 + 97 = 281$ trajets. Le Plateau : 2 stations, $35 + 23 = 58$ bornes, $512 + 271 = 783$ trajets. Total de la ville : 6 stations, 158 bornes, 1 718 trajets.

b) Ville-Marie : $654 / 58 \approx 11{,}28$ trajets par borne. Rosemont : $281 / 42 \approx 6{,}69$. Le Plateau : $783 / 58 \approx 13{,}50$. Le Plateau est donc le plus intensément utilisé rapporté à sa capacité.

c) Première façon, la moyenne des trois valeurs : $(11{,}28 + 6{,}69 + 13{,}50) / 3 \approx 10{,}49$. Seconde façon, le total sur le total : $1\ 718 / 158 \approx 10{,}87$. Les deux résultats ne coïncident pas. Le correct est le second, $10{,}87$, parce que la question porte sur la ville entière : chaque borne doit peser autant qu'une autre. La première façon donne le même poids à Rosemont, qui n'a que 42 bornes, qu'au Plateau, qui en a 58, et sous-estime donc le résultat. La coïncidence n'aurait lieu que si les trois arrondissements avaient exactement le même nombre de bornes.

d) Règle : une moyenne de rapports n'est pas le rapport des sommes. Pour agréger un rapport sur plusieurs groupes, on somme séparément les numérateurs et les dénominateurs, puis on divise une seule fois. Formulée autrement, on ne moyenne jamais des moyennes sans les pondérer par leurs effectifs, et le poids est toujours le DÉNOMINATEUR de la grandeur moyennée.

e) Parce que « fréquenté » n'est pas une grandeur, c'est un mot. Avec l'indicateur « nombre total de trajets », la réponse est Le Plateau, avec 783 trajets. Avec l'indicateur « trajets par borne », la réponse est encore Le Plateau. Mais avec l'indicateur « trajets par station », Ville-Marie donne $654 / 2 = 327$ et Le Plateau $783 / 2 = 391{,}5$ : Le Plateau encore. En revanche avec l'indicateur « croissance », qui demanderait une seconde journée, la réponse pourrait être tout autre. La leçon est de toujours écrire l'indicateur avant de conclure : une conclusion sans indicateur explicite n'est pas défendable.

a) Première raison, éviter la redondance : le nom, l'adresse et l'arrondissement d'une station ne changent pas, alors qu'un relevé arrive toutes les heures. Les réunir obligerait à recopier le nom de la station des milliers de fois, ce qui gaspille de l'espace et surtout multiplie les occasions d'incohérence si un nom est corrigé à un seul endroit. Seconde raison, la séparation des responsabilités : la table des stations est mise à jour par le service qui installe le matériel, celle des relevés par le système automatique, et chacun peut travailler sans bloquer l'autre.

b) Berri porte le code S03 et le relevé S03 vaut 377 : Berri, 377 trajets. Rosemont porte S07 et le relevé S07 vaut 412 : Rosemont, 412. Beaubien porte S12 et le relevé S12 vaut 290 : Beaubien, 290. Papineau porte S21, absent de la table de droite. Le point à retenir : la correspondance se fait par la VALEUR de la clé, jamais par la position de la ligne, et les deux tables ne sont d'ailleurs pas dans le même ordre.

c) Papineau, code S21, n'a pas de relevé ; et le relevé S05, qui vaut 158, ne correspond à aucune station de la table de gauche. Si l'on veut une fusion qui ne garde que les correspondances, ces deux lignes disparaissent et le résultat compte 3 lignes. Si l'on veut garder toutes les stations, Papineau est conservée avec un nombre de trajets marqué comme manquant, et le résultat compte 4 lignes. Le choix n'est pas technique mais métier : perdre Papineau, c'est perdre l'information qu'une station n'a produit aucun relevé, ce qui est peut-être exactement la panne que l'on cherche.

d) La fusion apparierait la ligne Beaubien avec CHACUNE des deux lignes S12 : Beaubien apparaîtrait deux fois dans le résultat, et la fusion produirait 4 lignes au lieu de 3 pour les correspondances. Les totaux calculés ensuite seraient faussés par un doublon invisible. Avant toute fusion, il faut donc vérifier que la clé est UNIQUE dans au moins une des deux tables, ce qu'on fait en comparant le nombre de lignes au nombre de valeurs distinctes de la clé.

e) Dans le meilleur des cas, chaque relevé trouve exactement une station et chaque clé est unique : la fusion produit alors 3 900 lignes, c'est-à-dire le minimum des deux effectifs, et 100 stations restent sans relevé. Comparer le nombre de lignes obtenu à ce nombre attendu est le premier contrôle à faire parce qu'il détecte d'un coup les deux accidents classiques : moins de lignes que prévu signale des clés qui ne se correspondent pas, souvent à cause d'espaces ou de majuscules ; plus de lignes que prévu signale des doublons de clé, donc des totaux gonflés.

1) FAUX, dès que le fichier porte une ligne de descripteurs, ce qui est le cas habituel. Énoncé correct : un fichier CSV de 500 lignes dont la première est l'en-tête contient 499 enregistrements. Le réflexe à prendre est de compter les enregistrements en soustrayant la ligne d'en-tête, et de vérifier ce nombre avant tout calcul de moyenne.

2) FAUX, sauf si tous les arrondissements ont exactement le même nombre de bornes. Une moyenne de rapports n'est pas le rapport des sommes. Énoncé correct : le taux de la ville s'obtient en divisant le total des vélos par le total des bornes ; la moyenne des taux, elle, donne à un petit arrondissement le même poids qu'à un grand.

3) FAUX. Retirer les noms ne suffit pas : le croisement de quelques attributs, code postal, date de naissance et sexe, suffit à isoler une personne dans une population, comme le montre l'exercice 9. Énoncé correct : la suppression des identifiants directs réduit le risque sans le supprimer ; une anonymisation sérieuse doit garantir qu'aucune combinaison d'attributs ne désigne un groupe trop petit.

4) FAUX. Dans un tri à plusieurs clés, la première clé décide et la seconde ne départage que les égalités : échanger les deux clés donne un ordre différent. Énoncé correct : l'ordre des clés d'un tri change le résultat, contrairement à l'ordre de deux filtres, qui n'est qu'une intersection de conditions.

5) FAUX, à cause de la confusion entre bits et octets. Un gigaoctet vaut 8 gigabits, donc le transfert prend environ 8 secondes, sans même compter les en-têtes de protocole et les pertes. Énoncé correct : sur une liaison à 1 Gbit/s, un fichier de 1 Go demande au minimum 8 secondes. Toujours convertir le débit en octets avant de diviser.

a) La première barre dit qu'en connaissant seulement le code postal, on ne distingue rien : les 21 400 personnes du jeu de données partagent ce seul attribut, ou plutôt une personne se confond avec beaucoup d'autres. La dernière dit qu'en ajoutant la profession au code postal, à la date de naissance et au sexe, il ne reste plus qu'UNE personne par profil : l'individu est identifié de façon certaine. Conclusion imposée : un jeu de données sans nom n'est pas un jeu de données anonyme, puisque la combinaison d'attributs banals suffit à désigner une personne unique.

b) Un quasi-identifiant est un attribut qui, pris seul, ne désigne personne, mais qui combiné à d'autres réduit très vite le nombre de personnes possibles. La date de naissance est particulièrement efficace parce qu'elle prend environ $365 \times 100 = 36\ 500$ valeurs différentes réparties de façon presque uniforme : à elle seule, elle divise une population par plusieurs dizaines de milliers, alors qu'un attribut comme le sexe ne la divise que par deux.

c) Il reste 31 personnes par profil sur 21 400, soit $31 / 21\ 400 \approx 0{,}00145$, environ $0{,}145$ pour cent de la population. Le nombre de profils distincts vaut environ $21\ 400 / 31 \approx 690$. Autrement dit, trois attributs anodins ont découpé la population en près de sept cents groupes.

d) Les données ouvertes sont des données publiées librement, gratuitement, dans un format exploitable par une machine, et réutilisables sans restriction, y compris commerciale. Bénéfices concrets : elles permettent à n'importe qui de vérifier une politique publique, par exemple la répartition réelle des stations de vélos entre quartiers ; et elles permettent la création de services que l'administration n'aurait pas produits elle-même, comme une application d'itinéraires. La précaution principale est le contrôle de la ré-identification : avant publication, il faut vérifier qu'aucune combinaison d'attributs ne réduit un groupe à quelques individus.

e) La règle exige au moins 11 personnes par profil. Les étapes à 21 400, à 62 et à 31 la respectent ; l'étape à 1 ne la respecte pas. Il faut donc soit ne pas publier l'attribut de profession, soit le publier sous une forme moins précise, par exemple un secteur d'activité au lieu d'un métier, soit regrouper les lignes concernées jusqu'à atteindre le seuil. La bonne réponse n'est presque jamais de supprimer les lignes trop rares, ce qui biaiserait le jeu de données : c'est de réduire la précision de l'attribut fautif.

a) Le total vaut $4\ 120 + 1\ 880 + 2\ 240 + 3\ 060 + 4\ 560 + 1\ 140 = 17\ 000$ trajets. Tranche 18-21 h : $4\ 560 / 17\ 000 \approx 0{,}2682$, soit $26{,}8$ pour cent. Tranche 6-9 h : $4\ 120 / 17\ 000 \approx 0{,}2424$, soit $24{,}2$ pour cent. À elles deux, les six heures de pointe portent $51{,}1$ pour cent des trajets de la journée, alors qu'elles ne représentent qu'un quart du temps.

b) Dans l'ordre : PROJETER le jeu brut sur la seule colonne de l'heure de départ, puisque ni la durée ni les stations n'interviennent ; CALCULER pour chaque ligne la tranche horaire à laquelle elle appartient, ce qui ajoute une colonne dérivée ; GROUPER les lignes par tranche ; puis AGRÉGER chaque groupe par un comptage. C'est la chaîne projection, calcul, regroupement, agrégation, qui est le squelette de presque tout traitement de données en table.

c) La journée représente $17\ 000 \times 14 = 238\ 000$ minutes de vélo. En heures, $238\ 000 / 60 \approx 3\ 966{,}7$ heures ; en jours de 24 heures, $3\ 966{,}7 / 24 \approx 165{,}3$ jours. Autrement dit, en une seule journée, le réseau produit l'équivalent de plus de cinq mois de pédalage continu.

d) Il faut, pour chaque station et pour la tranche du matin, compter les départs ET les arrivées, puis calculer la différence départs moins arrivées : c'est le SOLDE. Une station se vide quand ce solde est nettement positif. Le piège de celui qui ne compte que les départs est de désigner les stations les plus actives au lieu des stations qui se vident : une station qui enregistre 300 départs et 295 arrivées est très utilisée mais parfaitement équilibrée, alors qu'une station à 40 départs et 3 arrivées se vide vraiment. Un flux se mesure toujours par un bilan, jamais par un seul sens.

e) Le fichier de la journée pèse $17\ 000 \times 62 = 1\ 054\ 000$ octets, soit environ $1\ 054\ 000 / 1\ 048\ 576 \approx 1{,}005$ Mio. Sur 365 jours, $1\ 054\ 000 \times 365 = 384\ 710\ 000$ octets, soit $384\ 710\ 000 / 1\ 048\ 576 \approx 366{,}9$ Mio. Le diagramme, lui, tient en six nombres. Conclusion : l'agrégation divise le volume par un facteur énorme, ici plus de cinquante mille, et c'est ce qui rend une donnée exploitable, communicable et publiable. Mais elle est IRRÉVERSIBLE : à partir des six nombres, on ne peut plus répondre à la question de la station qui se vide. On agrège pour décider, on conserve le brut pour pouvoir poser les questions suivantes.