L’apprentissage automatique par la pratique – 2nde partie
Comme introduit dans la première partie de ce billet, l’objectif de ce tutoriel consiste à utiliser le jeu de données Enron rendu public suite à l’affaire éponyme pour mieux comprendre ce qu’est la mise en cluster ou le « clustering » en anglais et quelle approche doit-on adopter pour tirer parti de celui-ci.
Pour cela, concrètement, nous voulons connaitre ce dont on parle dans ce jeu de données. Nous voulons le comprendre et idéalement détecter l’influence de chaque personne.
Une première introduction au “clustering”
Le clustering en anglais signifie « l’action de regrouper ». Un cluster est un groupe. La faculté de synthétiser chez l’homme est très développée. Ainsi, typiquement lorsque vous lisez article d’un journal, vous allez être à même de dire une fois l’avoir lu si cet article parle des « élections municipales et d’éventuelles primaires associées » ou, plus précisément, si cet article parle d’un parti politique en particulier, et ainsi de suite. Eh bien, le clustering en apprentissage automatique est la possibilité à un ordinateur/système de faire la même chose.
Mais alors comment une machine peut-elle savoir de quoi parle-t-on sans aucun apport humain extérieur ? Car oui, le clustering est un domaine de l’apprentissage non-supervisé comme abordé précédemment dans le billet Apprentissage automatique (Machine Learning) sur ce même blog.
Le regroupement des informations
Le processus de clustering est assez simple en soit, à savoir organiser une collection donnée d’éléments en groupes d’éléments similaires. Dans l’exemple avec les articles de journaux, nous aurions pu organiser les articles politiques ensembles, les articles sportifs, les articles faits divers, etc.
Il est aussi nécessaire de spécifier quelque chose d’important, à partir de quand un article ne fait plus parti d’un groupe, et en échafaude/commence un nouveau ? Pour l’exemple, si un article explique les avancées de la science dans l’analyse du génome touchant aussi bien l’informatique que la biologie, il serait peut être judicieux de créer un groupe nommé « bio-informatique ». Cette frontière qui spécifie quand est-ce qu’il convient de créer un nouveau groupe est très subjective et dépendra bien évidemment du besoin final.
Alors regrouper une collection d’éléments impliques 3 choses :
- Un algorithme : ce sera la méthode utilisée pour grouper les articles (ou les mèls) ensembles.
- Une notion de similarité ainsi que de dis-similarité : le fait de savoir comment un article est similaire à un autre, une mesure au sens mathématique du terme, une métrique.
- Une condition d’arrêt : le point à partir duquel un article n’appartient plus à un groupe en particulier, et en crée un nouveau.
Les concepts mathématiques nécessaires : similarité et distance
Pour visualiser un cluster, les auteurs de l’ouvrage de référence Mahout In Action mentionné précédemment expliquent que le cercle est figure la plus adéquate comme un cluster (= un groupe), conceptuellement parlant, est défini par :
- Un centre - centroid en anglais, parfois appelé moyenne ou mean comme dans KMeans -
- Ainsi qu’un rayon, comme un cercle.
Le clustering est basé sur des concepts mathématiques. Ainsi, retournons un instant au lycée lorsque nous faisions de la géométrie dans le plan.
Prenons un plan composé de deux dimensions x et y.
Nous avons quatre points A, B, C, et D avec les coordonnées respectives de (xA, yA), (xB, yB), (xC, yC) et (xD, yD).
Sur la figure ci-dessus, vous avez un exemple de clustering. Les points du plan sont regroupés en deux groupes : Cluster 1 et Cluster 2.
Le calcul de similarité utilisé ici est simple : nous avons choisi la distance euclidienne comme métrique. Cette métrique est la plus simple de toutes ; elle est aussi la plus intuitive. Par exemple, la distance euclidienne entre le point A et le B pourrait être mesuré par une règle. Néanmoins, Pythagore a fourni un théorème pour cela :
Sur la figure précédente, le segment rouge représente la distance entre le point A et le point B. Une fois que nous avons calculé les distances entre chaque point (AB, AC, AD, BC, BD, CD), l’algorithme de clustering range automatiquement les points « proches » (ou similaire) dans le même groupe.
La notion de vecteur
Un vecteur en mathématique est différent du vecteur en physique :
- Le premier représente un point sous forme de coordonnées, il a autant de coordonnées que le plan possède de dimension. Ainsi, en 3D, un vecteur aura 3 coordonnées : x, y, z.
- Le second est objet définissant un point de départ, une direction, et une longueur. Il représente une force comme la gravité ou le frottement.
Pour ce qui du clustering, la notion de vecteur utilisée est celle mathématique. Dans l’exemple précédent, le plan de dimensions x et y possédait quatre vecteurs, A, B, C et D.
La notion de poids est par ailleurs très importante : le poids est associé à une dimension. Le point A, sur l’abscisse a un poids de 7 et en ordonnée a un poids de 8.
Le poids correspond tout simplement à la valeur du vecteur (= du point) dans une dimension. Nous verrons par la suite dans ce billet comment se traduit un vecteur dans nos algorithmes de lustering. On le représente à l’aide d’un tableau (=Array) ayant autant de colonnes pour représenter les dimensions.
Exemple : Vector [x = 7 , y = 8 ]
Le poids des mots : transformer du texte en vecteur mathématique ?
Maintenant que nous avons vu ce qu’était un vecteur (=un point dans un plan) et une métrique de similarité (=une distance), nous allons aborder un aspect plus avancé qui provient du domaine de l’exploration/ fouille de données.
Comment peut-on représenter du texte en une visualisation mathématique, ce qui permettrait par la suite de calculer plus facilement une distance entre différents textes et ainsi déterminer s’ils sont similaires ou peu similaires.
Les techniques présentées sont complémentaires. Elles sont issues de l’étude des langages.
La sélection des caractéristiques (feature selection)
Le processus de sélection des caractéristiques qui composent un objet constitue la première étape. Ce processus indique quelles caractéristiques sont comparables et les retranscrit sous forme de nombre.
Prenons l’exemple d’un humain. Quelle caractéristiques peut-on retenir/sélectionner pour décrire un humain ? Selon toute vraisemblablement sa taille, sa couleur de cheveux, son âge, son sexe, etc.
Il y aurait certes de fort nombreuses caractéristiques, mais nous souhaitons les grouper pour notre propos en utilisant seulement trois de ces caractéristiques.
Un vecteur Humain sera alors représenté de la forme suivante :
Michel [taille : 1,75 ; couleur_cheveux : Châtain ; sexe : Masculin]
Sauf que les valeurs « châtain » et « F » ne sont pas des nombres. Il faut donc les transformer ! Admettons un instant qu’il n’y ait que quatre couleurs de cheveux : Blond(1), Châtain(2), Roux(3) et Brun(4). Les salons de coiffure ne seront certainement pas d’accord avec cette assertion…
Valorisons ensuite les deux sexes par Féminin(1) et Masculin(2)
Si vous remarquez bien, nous avons associé un nombre à un type de couleur ou à un sexe ; ce qui en résulte constitue donc deux dictionnaires et un vecteur entièrement composé de nombres :
Dictionnaire_1 (couleur de cheveux) = {Blond, Châtain, Roux, Brun}
Dictionnaire_2 (Sexe) = {F, M}
Michel [taille : 1,75 ; couleur_cheveux : 2 ; sexe : 2]
La selection des caractéristiques Texte avec VSM
Pour un document de type texte comme avec nos mèls de l’affaire Enron, la technique communément utilisé se nomme VSM pour Vector Space Model.
Imaginez un ensemble - une collection ne possédant qu’une seule fois un élément, sans doublon donc - constitué de tous les mots présents au moins une fois dans le corpus de documents que vous voulez analyser. Chaque mot présent dans l’ensemble est accessible à un indice précis.
Le vecteur d’un document sera alors constitué d’autant de dimensions qu’il y a de mots différents dans ce document et le poids associé sera le nombre de fois qu’apparait ce mot dans le document. Ainsi, par exemple, si le mot « chocolat » est au sein de l’ensemble à l’indice 367, et que ce mot apparait dans l’article de cuisine « techniques avancées pour faire un moelleux au chocolat », le mot « chocolat » correspondra à la 367ème dimension du vecteur représentant l’article.
Les dimensions des documents texte peuvent être de très grande largeur - imaginez un livre de 1500 pages, ou une encyclopédie, etc. -, il est commun de partir du principe que les vecteurs textes sont capables d’avoir des dimensions infinies.
La vectorisation avec TF-IDF
La valeur d’une dimension d’un vecteur est généralement le nombre d’occurrences du mot dans le document (un wordcount).
Connu sous le nom de « Term Frequency (TF) weighting », littéralement la pondération par la fréquence des termes, ce type de vectorisation stocke le nombre de fois qu’un mot apparaît dans un document. Le problème avec cette méthode réside essentiellement dans la pondération de certains mots : les, de, cela, par, la, je, si, etc. par exemple en français.
Lorsqu’on analyse un texte, les mots les plus fréquents sont des mots n’apportant aucune signification ou spécification. On appelle ces mots des mots vides ou « stop words » en anglais. Le souci quand on calcule la distance entre deux documents vectorisés par la méthode TF réside donc dans le fait qu’ils seront probablement très similaires à cause du poids important qu’auront ces mots vides dans le calcul.
Fort heureusement, il y existe une parade, un ajout à cette méthode qui permet de supprimer l’effet des mots vides : TF-IDF
Vous l’avez peut-être déjà deviné :), il s’agit de la combinaison de deux méthodes, Term Frequency (TF) et Inverse Term’s Document Frequency (TDF). La première méthode, TF, est multipliée par la deuxième, mais à quoi correspond celle-ci ?
La méthode Document Frequency est la fréquence d’apparition d’un mot, dans tout le corpus de documents. Multiplier le nombre de fois qu’un mot apparait dans un document par l’inverse du nombre du nombre de fois qu’il apparait dans tous les documents diminue la pondération des mots fréquemment utilisés dans la langue courante considérée.
Ainsi, la méthode TF-IDF permet de pondérer fortement les mots qui apparaissent beaucoup seulement dans un seul document (les sujets ou « topics »), et pondérer faiblement les mots qui polluent la signification du texte.
L’équation d’IDF ressemble à cela :
Où N est le nombre de documents et DF est l’occurrence du mot en question dans tout le corpus de documents
Le poids (W) d’un mot est donc de la forme suivante :
Cependant, une astuce pour donner un peu plus d’importance à TF consiste à passer IDF dans la fonction Logarithme. Cela permet de stabiliser un résultat d’IDF trop élevé, typiquement cela arrive lorsque que le corpus de texte est très grand (600 000 par exemple pour le jeu de données Enron qui nous sert d’illustration).
L’équation finale du calcul du poids d’un mot dans un document est donc la suivante :
La collocation N-Gramme
A ce stade, il convient néanmoins de remarquer que la méthode précédente ne prend pas en compte un aspect particulièrement important, à savoir la combinaison de mots.
En effet, TF-IDF ne se concentre que sur le poids des mots, mais nous sommes capables en tant qu’humain de savoir reconnaitre une expression. L’exemple de Coca Cola est flagrant. Nous savons que le mot Coca et le mot Cola font en réalité partie d’une même expression (une marque) qui a beaucoup plus de sens que si nous avions les deux mots séparés. Cela implique que certaines dimensions sont liées à d’autres. Apache Mahout apporte une solution pour donner plus de poids aux mots constituant une expression particulière. Il s’agir de la collocation.
Un groupe de mots faisant une partie d’une chaine de caractère est appelé N-Gramme (comme abordé dans un précédent billet avec les chaines de Markov). Un seul mot constitue un uni-gramme, un groupe de deux mots comme Coca Cola un bi-gramme, une combinaison de 3 mots un trigramme, etc.
La lettre N de N-Gramme correspond au nombre de mots constituant la combinaison. Ainsi, si nous constituons les bi-grammes d’une phrase « pour le meilleur et pour le pire», cela fera :
Pour le
le meilleur
meilleur et
et pour
pour le
le pire
A l’évidence, certains de ces bi-grammes forment de bonnes combinaisons (« le meilleur » et « le pire »), d’autres non (« pour le », « et pour », etc.).
Mahout résout le problème grâce à un calcul statistique appliqué sur les N-Grammes dont le résultat est appelé LLR (Log Likelihood Ratio). Cette probabilité est calculée selon une fonction de vraisemblance appliquée à notre chaine de Markov.
Mahout va calculer de lui-même quelles sont les combinaisons de N-Grammes les plus probables et ne garder que les plus significatives. Par-contre il est de notre ressort de dire à Mahout à partir de quelle valeur un N-Gramme devient « significatif », et oui !
La normalisation P-Norm
A ce stade de notre exploration, voici ce que nous avons réussi à ajouter au calcul du poids d’un mot :
- Sélectionner tous les mots d’un texte pour en constituer un vecteur avec, pour chaque mot, une dimension et poids associés (le nombre de fois que ce mot apparait)
- Minimiser l’impact des mots vides et maximiser la détection des mots par lesquels on exprime le sujet (« topic words ») grâce à TF-IDF.
- Favoriser les combinaisons de mots formant des expressions de langue courante grâce à la collocation n-gramme et le calcul de vraisemblance.
Il nous manque encore toutefois quelque chose d’important, surtout dans un corpus comme celui que nous nous apprêtons à analyser (des mèls).
Il est courant dans un jeu de données de type documents divers de trouver des documents beaucoup plus longs que la moyenne, et d’autres plutôt courts. Ainsi, sur la base de notre approche de calcul précédente, les documents longs seront davantage similaires à beaucoup d’autres documents plus petits car ils posséderont probablement beaucoup de mots en commun. On se retrouvera avec une poignée de documents similaires à la majorité des autres documents du corpus, et avec aucun moyen de les regrouper correctement : ce que nous ne souhaitons pas, sic.
Il s’avère donc nécessaire de « normaliser » la taille des documents, l’objectif étant de minimiser l’impact des gros documents sur le calcul du poids des mots et d’augmenter celui des petits documents. Typiquement dans notre corpus de mèls, certains mèls sont de tailles très grandes (threads de plusieurs messages) alors que d’autres sont beaucoup plus concis.
La normalisation est intrinsèquement liée à la notion de mesure de distance abordée précédemment. Nous verrons par la suite qu’il existe plusieurs mesures différentes : nous n’avons abordé jusqu’à présent que la distance euclidienne.
La normalisation proposée par Mahout est mise en œuvre par ce qui est appelé dans le domaine de la statistique P-Norm où P est un nombre rationnel supérieur à 0, ainsi que la norme du vecteur.
La valeur de P à choisir dépend du type de mesure de distance que nous utilisons pour calculer la similarité. Ainsi, si nous utilisons la distance euclidienne comme mesure, une normalisation avec P = 2 apporte de meilleurs résultats de clustering.
Le clustering avec l’algorithme K-moyennes (KMeans)
Comme nous l’avons abordé dans un précédent billet, l’algorithme des K-moyennes (KMeans) fait partie de ces algorithmes incontournables. Il existe depuis plus 50 ans. Il est simple à comprendre et à implémenter. Pour ces raisons, il fût l’un des premiers algorithmes à être implémenté dans Mahout. Il est aussi simple qu’il est efficace.
Cet algorithme demande un paramètre fourni par l’utilisateur en entrée, le nombre de clusters (=groupe) K. Cette principale caractéristique en fait aussi du coup son principal défaut. Néanmoins, la qualité du résultat n’en est pas plus affectée et sa rapidité par rapport à d’autres algorithmes en fait l’algorithme de clustering le plus utilisé.
Dans la pratique, K ne correspond pas au nombre de clusters que l’algorithme devra trouver et dans lequel les mèls seront rangés mais plutôt au nombre de centres (c’est-à-dire le point central du cluster). Vous allez nous dire que cela revient sensiblement à la même chose, et c’est pourquoi nous faisons ici ce raccourci, mais cela me permet d’aborder la suite ;)
Les principes de fonctionnement
En effet, comme expliqué précédemment, un cluster peut être représenté par un cercle composé d’un point central et d’un rayon.
Les K centres
Nous cherchons à regrouper N points. L’algorithme va commencer avec K points centraux qui définissent les centres de chaque cluster auxquels seront assignés les N points à la fin.
A la première étape, les N points sont associés à ces différents centres (spécifiés au départ ou choisis au hasard), puis l’étape suivante consiste à recalculer les centres par rapport à la moyenne de tous les points du cluster. On appelle cela Espérance-Maximisation (EM) comme abordé dans un précédent billet.
La première phase Espérance consiste à trouver les points qui sont associés au cluster en calculant la distance entre le centre du cluster et ces points.
Avec la seconde phase Maximisation, le centre du cluster est recalculé par rapport à la moyenne des points du cluster.
Les X iterations
On recommence ensuite jusqu’à ce que les centres se stabilisent, indiquant qu’ils sont arrivés à des valeurs optimales pour représenter les N points de départ. Lorsqu’on utilise l’algorithme KMeans dans Mahout, il est nécessaire de lui fournir le nombre d’itération qu’il va devoir réaliser.
Ce nombre est représenté par la variable X. Néanmoins, si les centres sont arrivés à un stade stable - c’est-à-dire que la moyenne des clusters ne change plus beaucoup d’une itération à l’autre - l’algorithme s’arrêtera automatiquement.
Il existe une classe proposée dans Mahout qui se charge de donner des centres de façon aléatoire, RandomSeed, mais nous allons voir une autre technique pour trouver le nombre optimale de clusters, K, et la position de départ des centres.
Canopy, un algorithme de clustering complémentaire
Canopy est un second algorithme de clustering, il est très performant mais également plutôt grossier. Il est donc très souvent utilisé en complément de KMeans.
Sa différence dans le paramétrage est qu’à l’inverse de KMeans, il ne demande pas de connaitre le nombre de clusters qu’il devra trouver. Il demande à la place un seuil ou threshold, qui correspond à une limite.
En réalité il y a deux barrières, une barrière basse et une barrière haute. On peut comparer cela aux limites mathématiques, ces limites définissent si un point appartient à un cluster, elles définissent plus précisément la valeur minimale de la distance qu’un point doit avoir pour être pris en compte et la valeur maximale.
Si l’on exécute cet algorithme, le résultat est grossier, mais ce ne sera pas ce qui nous intéresse car il y a aussi les centres de nos clusters stockés dans un dossier, que l’on peut ensuite insérer directement lors du lancement de KMeans sur le jeu de données.
Pour résumé, Canopy nous aidera à calculer, de façon peu coûteuse en termes de ressources et donc de temps, le nombre de centres idéal pour le jeu de données ainsi fourni et leurs positions grossières ; ce qui fera gagner à KMeans aussi en nombre d’itérations.
Fuzzy KMeans, une variant intéressante
Fuzzy KMeans est comme son nom l’indique une variante de KMeans « flou ». Reprenons notre explication précédente pour visualiser un cluster comme un cercle possédant un centre et un rayon, et dans lequel des points sont associés comme ils sont considérés à l’intérieur de ce cercle.
Avec Fuzzy KMeans, un point n’est plus strictement associé à un seul cluster, mais peut être associé à plusieurs.
Nous en avons donc terminé avec la « théorie » relative à l’approche à adopter pour l’analyse de notre jeu de données Enron. Il est donc temps de passer à la mise en œuvre concrète du programme qui se chargera de cette analyse en tant que telle.
C’est l’objet de la troisième et dernière partie de ce billet.