Contact
Puisque ce glossaire est ordonné par ordre alphabétique, « bonne partition » arrive en premier et c’est une bonne chose pour comprendre ce que l’on cherche à faire dans les graphes.
Nous cherchons à créer des partitions des graphes que l’on manipule pour mettre en valeur des communautés d’intérêt. Ces partitions sont donc l’information essentielle à extraire du graphe. Pour obtenir ces partitions, nous utilisons différentes techniques dans le domaine, tantôt basées sur des optimisation de critère, tantôt basées sur des modèles à priori, tantôt basées sur des réseaux de neurones. Mais dans tous ces cas, on obtient des partitions différentes du graphe, toutes intéressantes et pertinentes. Il n’y a pas de meilleure partition dans l’absolu, lorsque l’on dit que l’on cherche la meilleure partition cela signifie que « l’on cherche la partition qui satisfait le mieux la méthode utilisée ».
Une chaine de Markov est simplement une façon de faire des tirages aléatoires successifs. Le nom de « chaine » fait référence aux tirages successifs et le nom Markov fait référence aux contraintes sur la manière de tirer aléatoirement.
En effet, le mathématicien Andreï Markov (1856-1922) a étudié des tirages successifs où les probabilités pour le tirage à venir ne dépend que de l’instant actuel et plus du tout du passé. Ces chaines sont à la fois très simples et très utiles pour modéliser de nombreuses situations réelles. On pourra notamment citer les modèles de sélections naturels, de physique statistique ou encore le modèle épidémiologique SIR (sain-infecté-rétabli) dont on a pu parler en 2020 avec le COVID (et ce modèle reste d’actualité!).
En data science, « Cluster » est un mot signifiant « groupe ». La tache qui consiste à faire des groupes s’appelle le clustering. Les clusters dans des graphes sont souvent appelés « communautés ».
Il est a noter que le mot « Cluster » apparait également en chimie, physique, informatique et épidémiologie notamment. Dans tous ces cas, son sens s’approche de la notion de « regroupement » comme dans le cas de cluster de calcul ou clusters de COVID.
Signifie « cluster » dans un graphe. Voir « cluster » pour plus de détails.
Un graphe est un objet conceptuel très utile pour modéliser tout ce qui a à voir avec des relations entre objet.
On peut faire par exemple un graphe des vêtements (les objets considérés) où deux vêtements seront dit « en relation » s’ils font partie d’un même panier client. Ainsi, après quelques jours, on pourra avoir un graphe avec des noeuds (ici les vêtements) reliés par des arêtes s’ils sont en relation et faire du clustering de vêtement. Si des clusters se distinguent dans ce graphe, c’est que certains vêtements font partie d’une même famille de vêtement souvent achetés ensemble et constituent aussi un style donné dans le stock du magasin.
C’est une méthode générale pour approcher des distributions de probabilités compliquées. En l’occurrence, l’algorithme de LumenAI recourt à cette technique pour tirer aléatoirement de nouvelles partitions du graphe.
La tache consistant à tirer aléatoirement des partitions du graphe peut ne pas paraitre compliqué mais en réalité il y a un nombre inimaginablement grand de partitions différentes. La plupart ne sont pas pertinentes, il est alors nécessaire d’avoir une technique plus astucieuse qu’une simple recherche aléatoire naïve.
Pour plus de détail sur l’algorithme de Metropolis-Hastings, voir ici.
La modularité est le nom donné à une formule applicable à n’importe quel graphe partitionné en clusters. La formule est disponible en ligne mais son détail nous importe peu. L’essentiel à retenir est que la modularité est un critère pour juger la pertinence d’une partition d’un graphe. En l’occurrence, plus une partition est associée à une grande modularité (avec un maximum de 1 tout de même!), plus la partition est jugée pertinente.
La « pertinence » dont il est question n’est pas absolue. En effet, il existe différentes procédures pour obtenir des partitions « pertinentes ». On peut nommer: la maximisation de la permanence (un autre critère), les algorithmes de minimisation de coupe d’arêtes, la maximisation de vraisemblance de modèles, les algorithmes relationnels comme PageRank, etc.
Toutes ces techniques donnent un point de vue différent sur le graphe étudié. Dans notre cas à LumenAI, nous avons choisi d’optimiser la modularité car cela s’adaptait bien au cadre « online » et que cela permettait de créer une version Online de l’algorithme de Louvain (2008), un algorithme particulièrement efficace pour les gros graphes.
Ce terme est la version anglaise de « temps réel ». On peut également rencontrer « à la volée », « en ligne » ou « dynamique ».
Son contraire serait « offline » et il n’y a pas vraiment de terminologie franco-francaise utilisée par les statisticiens pour dire « offline ».
En informatique, l’optimisation est un domaine à part entière dans lequel on développe des techniques de calcul. De manière générale, rechercher un optimum avec ou sans contraintes s’appelle « optimiser ».
Dans le langage courant on dit souvent « optimiser » dans le sens « d’améliorer », et en effet ce sens est adapté quand on cherche à « améliorer » (disons, maximiser) la valeur d’un critère.
En l’occurrence, l’algorithme de LumenAI optimise un critère appelé « modularité »: Nous utilisons une méthode du type Metropolis-Hastings pour rechercher, de proche en proche, quelles partitions du graphe maximisent la modularité.
Une partition est une subdivision de tous les éléments d’un ensemble en sous-groupes disjoints. Par exemple, {1,2,3,4,5} peut être partitionné en trois les trois sous-groupes suivants: {1}, {2}, {3,4,5}.
Dans le cas de l’algorithme de LumenAI, la partition d’un graphe signifie regrouper les noeuds du graphe en différents groupes. Ces groupes sont appelés « clusters » ou « communautés ».
Pour obtenir ces partitions, on procède à une optimisation de la « modularité ». L’algorithme explore en temps réel les partitions du graphe, de proche en proche, en privilégiant les partitions qui font croitre la modularité.
Cette terminologie est utilisé pour distinguer les algorithmes qui ne sont pas « en temps réel ». Il y a deux catégories, les algorithmes « online » et « offline ».
On parle d’algorithme online s’il peut fonctionne en parallèle de l’acquisition de données de sorte que le corpus de données évolue pendant l’exécution de l’algorithme. C’est le cas de l’algorithme de LumenAI qui fait évoluer les communautés dans le graphes en même temps que le graphe grandit.
A l’inverse, un algorithme offline est un algorithme qui fonctionne après l’acquisition des données: d’abord on acquière, ensuite on exploite, si bien que l’algorithme dispose d’un corpus de données fixe pendant son exécution. Cette manière de faire laisse une plus grande latitude dans les méthodes d’exploration.
Les procédures online sont plutôt méconnues et sûrement minoritaire en statistique exploratoire. Pourtant le concept est omniprésent: internet peut être vu en exécution permanente, les antivirus fonctionnent en tache de fond pendant l’utilisation de l’ordinateur, nos téléphones ne sont presque plus éteints et nos cerveaux n’attendent pas que la balle tombe par terre pour la rattraper.