Noyaux d'arbre : quantification de la similarité entre les données structurées en arbre

Un réseau ou un graphe est un type de données structurées sous la forme de nœuds , avec des relations entre eux décrites par des liens ou des arêtes . Les nœuds et les arêtes d'un graphe peuvent avoir plusieurs attributs qui peuvent être numériques ou catégoriels, voire plus complexes.

Aujourd'hui, une quantité massive de données est disponible sous forme de réseaux ou de graphiques. Par exemple, le World Wide Web, avec ses pages web et ses hyperliens, les réseaux sociaux, les réseaux sémantiques, les réseaux biologiques, les réseaux de citation de la littérature scientifique, etc.

Un arbre est un type particulier de graphique, et est naturellement adapté pour représenter de nombreux types de données. L'analyse des arbres est un domaine important en informatique et en science des données. Dans cet article, nous allons nous intéresser à l'analyse de la structure des liens dans les arbres. En particulier, nous nous concentrerons sur les noyaux d'arbres, une méthode de comparaison des graphes d'arbres entre eux, nous permettant d'obtenir des mesures quantifiables de leurs similitudes ou différences. Il s'agit d'un processus important pour de nombreuses applications modernes telles que la classification et l'analyse de données.

Classification non supervisée des données structurées

La classification est une composante importante de l'apprentissage automatique et de l'analyse des données. En général, la classification peut être supervisée ou non supervisée . Dans la classification supervisée, les classes sont déjà connues et un modèle de classification est construit à partir de données d'apprentissage dans lesquelles les bonnes classes sont déjà données. La classification non supervisée, en revanche, tente d'identifier les classes où aucune n'est connue, en regroupant les données en catégories en fonction d'une certaine mesure de leur similitude.

La classification non supervisée peut être combinée avec la théorie des graphes pour identifier des groupes de réseaux d'arbres similaires. Des structures de données arborescentes sont utilisées pour modéliser des objets de plusieurs domaines. Dans le traitement du langage naturel (NLP), par exemple, les arbres d'analyse sont modélisés comme des arbres ordonnés et étiquetés. Dans le raisonnement automatisé, de nombreux problèmes sont résolus par la recherche, où l'espace de recherche est représenté comme un arbre dont les sommets sont associés à des états de recherche, et les arêtes représentent les étapes d'inférence. En outre, les données semi-structurées, telles que les documents HTML et XML, peuvent être modélisées sous forme d'arborescences ordonnées et étiquetées.

Ces domaines peuvent être utilement analysés par des techniques de classification non supervisées. En PNL, la classification peut être utilisée pour regrouper automatiquement un ensemble de phrases en questions, commandes et déclarations. De même, des groupes de sites Web similaires peuvent être identifiés en appliquant des méthodes de classification à leur source HTML. Dans chacun de ces cas, tout ce dont nous avons besoin est un moyen de mesurer à quel point deux arbres sont "similaires" l'un par rapport à l'autre.

La malédiction de la dimensionnalité

La plupart des algorithmes de classification exigent que les données soient transformées en une forme vectorisée, représentant les valeurs des caractéristiques des données dans l' espace des caractéristiques , afin que les données puissent être analysées dans l'espace des caractéristiques à l'aide de l'algèbre linéaire. Dans les données structurées ou semi-structurées, comme les arbres, la dimensionnalité des vecteurs résultants (c'est-à-dire le nombre d'entités dans l'espace des caractéristiques) peut être assez élevée, car l'espace des caractéristiques doit conserver les informations sur la structure.

Cela peut être un inconvénient important, étant donné que de nombreuses techniques de classification ne sont pas en mesure de s'adapter efficacement à la dimensionnalité de l'entrée. En d'autres termes, leur pouvoir de classification diminue avec une augmentation de la dimensionnalité de l'entrée. Ce problème est connu sous le nom de malédiction de la dimensionnalité.

Pour avoir une idée de la raison de cette dégradation des performances, considérons un espace X de dimension d . Supposons que X contient un ensemble de points uniformément distribués. Si le nombre de dimensions de X augmente, le nombre de points nécessaires pour garder la même densité doit augmenter de façon exponentielle. En d'autres termes, plus les dimensions de l'entrée sont nombreuses, plus il est probable que ces données soient clairsemées. En général, un jeu de données clairsemé ne donne pas suffisamment d'informations pour construire un bon classificateur car les corrélations entre les éléments de données sont trop faibles pour que les algorithmes puissent les détecter.

Chaque espace de caractéristiques ci-dessus contient huit points de données. Sur l'espace unidimensionnel, il est facile d'identifier un groupe de cinq points à gauche et de trois à droite. L'étirement de ces points sur un plus grand nombre d'entités (c'est-à-dire des dimensions) rend plus difficile la recherche de ces groupes. Dans les applications réelles, les espaces d'entités peuvent facilement avoir des centaines de dimensions.

Une représentation vectorisée pour les données structurées est appropriée lorsque les informations sur le domaine peuvent être utilisées efficacement pour sélectionner un ensemble gérable de fonctionnalités. Lorsque de telles informations ne sont pas disponibles, il est souhaitable d'utiliser des techniques capables de traiter directement des données structurées, sans effectuer d'opérations dans l'espace vectoriel.

Méthodes du noyau

Les méthodes du noyau évitent d'avoir à convertir les données sous forme vectorielle. La seule information dont ils ont besoin est une mesure de la similarité de chaque paire d'éléments dans un ensemble de données. Cette mesure s'appelle un noyau , et la fonction pour la déterminer s'appelle la fonction noyau . Les méthodes du noyau recherchent des relations linéaires dans l'espace des caractéristiques. Fonctionnellement, ils équivalent à prendre le produit scalaire de deux points de données dans l'espace des caractéristiques, et en effet la conception des caractéristiques peut toujours être une étape utile dans la conception des fonctions du noyau. Cependant, les méthodes des méthodes du noyau évitent d'opérer directement sur l'espace des caractéristiques car il peut être démontré qu'il est possible de remplacer le produit scalaire par une fonction noyau, tant que la fonction noyau est une fonction semi-définie symétrique et positive qui peut prendre comme entrées les données dans son espace d'origine.

L'avantage d'utiliser les fonctions du noyau est donc qu'un énorme espace de caractéristiques peut être analysé avec une complexité de calcul non dépendante de la taille de l'espace de caractéristiques, mais de la complexité de la fonction du noyau, ce qui signifie que les méthodes du noyau ne souffrent pas de la malédiction de dimensionnalité.

Si nous considérons un ensemble de données fini composé de n exemples, nous pouvons obtenir une représentation complète des similitudes au sein des données en générant une matrice noyau dont la taille est toujours n × n . Cette matrice est indépendante de la taille de chaque exemple individuel. Cette propriété est utile lorsqu'un petit ensemble de données d'exemples avec un grand espace de caractéristiques doit être analysé.

En général, les méthodes du noyau sont basées sur une réponse différente à la question de la représentation des données. Au lieu de mapper les points d'entrée dans un espace de caractéristiques, les données sont représentées via des comparaisons par paires dans une matrice de noyau K , et toutes les analyses pertinentes peuvent être effectuées sur la matrice de noyau.

De nombreuses méthodes de data mining peuvent être kernelisées. Pour classer les instances de données structurées en arbre avec des méthodes de noyau, comme avec les machines à vecteurs de support, il suffit de définir une fonction de noyau valide (définie positive symétrique) k : T × T → R , également appelée noyau d'arbre . Dans la conception de noyaux d'arbres pratiquement utiles, il faudrait qu'ils soient calculables en temps polynomial sur la taille de l'arbre, et qu'ils soient capables de détecter des graphes isomorphes. Ces noyaux d'arbres sont appelés noyaux d'arbres complets .

Noyaux d'arbres

Introduisons maintenant quelques noyaux d'arbres utiles pour mesurer la similarité des arbres. L'idée principale est de calculer le noyau pour chaque paire d'arbres dans l'ensemble de données afin de construire une matrice de noyau, qui peut ensuite être utilisée pour classer des ensembles d'arbres.

Noyau de chaîne

Tout d'abord, nous commencerons par une courte introduction aux noyaux de chaînes, ce qui nous aidera à introduire une autre méthode de noyau basée sur la conversion d'arbres en chaînes.

Définissons num y (s) comme le nombre d'occurrences d'une sous-chaîne y dans une chaîne s , avec | s | indiquant la longueur de la chaîne. Le noyau de chaîne que nous allons décrire ici est défini comme suit :

K chaîne (S 1 , S 2 ) = Σ s∈F num s (S 1 )num s (S 2 )w s

Où F est l'ensemble des sous-chaînes qui apparaissent à la fois dans S 1 et S 2 , et le paramètre w s sert de paramètre de pondération (par exemple, pour mettre en évidence des sous-chaînes importantes). Comme nous pouvons le voir, ce noyau donne une valeur plus élevée à une paire de chaînes lorsqu'elles partagent de nombreuses sous-chaînes communes.

Noyau d'arbre basé sur la conversion d'arbres en chaînes

Nous pouvons utiliser ce noyau de chaîne pour construire un noyau d'arbre. L'idée derrière ce noyau est de convertir deux arbres en deux chaînes de manière systématique qui encode la structure de l'arbre, puis de leur appliquer le noyau de chaîne ci-dessus.

Nous convertissons les deux arbres en deux chaînes comme suit :

Soit T l'un des arbres cibles, et label(n s ) l'étiquette de chaîne du nœud n s dans T . tag(n s ) désigne la représentation sous forme de chaîne du sous-arbre de T enraciné à n s . Donc, si n root est le nœud racine de T , tag(n root ) est la représentation sous forme de chaîne de l'arbre entier T .

Ensuite, laissez string(T) = tag(n root ) dénoter la représentation sous forme de chaîne de T . Nous allons appliquer récursivement les étapes suivantes de manière ascendante pour obtenir string(T) :

• Si le nœud n s est une feuille, soit tag(n s ) = "[" + label(n s ) + "]" (où + est ici l'opérateur de concaténation de chaînes).
• Si le nœud n s n'est pas une feuille et a c enfants n 1 , n 2 , … , n c , trier tag(n 1 ), tag(n 2 ), … , tag(n c ) dans l'ordre lexical pour obtenir tag (n 1* ), tag(n 2* ), … , tag(n c* ) , et soit tag(n s ) = "[" + label(n s ) + tag(n 1* ) + tag(n 2* ) + … + tag(n c* ) + "]" .

La figure ci-dessous montre un exemple de cette conversion arbre-chaîne. Le résultat est une chaîne commençant par un délimiteur ouvrant tel que "[" et se terminant par son homologue fermant, "]", chaque paire imbriquée de délimiteurs correspondant à un sous-arbre enraciné à un nœud particulier.

Nous pouvons maintenant appliquer la conversion ci-dessus à deux arbres, T 1 et T 2 , pour obtenir deux chaînes S 1 et S 2 . À partir de là, nous pouvons simplement appliquer le noyau de chaîne décrit ci-dessus.

Le noyau de l'arbre entre T 1 et T 2 via deux chaînes S 1 et S 2 peut maintenant être donné par :

K arbre (T 1 , T 2 ) = K chaîne ( chaîne(T 1 ), chaîne(T 2 ) ) = K chaîne (S 1 , S 2 ) = Σ s∈F num s (S 1 )num s (S 2 )w s

Dans la plupart des applications, le paramètre de poids devient w | s | , pondérant une sous-chaîne en fonction de sa longueur | s | . Méthodes de pondération typiques pour w | s | sont:

• pondération constante ( w | s | = 1 )
• pondération du spectre k ( w | s | = 1 si | s | = k , et w | s | = 0 sinon)
• pondération exponentielle ( w | s | = λ | s | où 0 ≤ λ ≤ 1 est un taux décroissant)

Pour calculer le noyau, il suffit de déterminer toutes les sous-chaînes communes F , et de compter le nombre de fois qu'elles apparaissent dans S 1 et S 2 . Cette étape supplémentaire consistant à trouver des sous-chaînes communes est un problème bien étudié et peut être accomplie en O( | S 1 | + | S 2 | ) , en utilisant des arbres de suffixes ou des tableaux de suffixes. Si nous supposons que le nombre maximum de lettres (bits, octets ou caractères, par exemple) nécessaires pour décrire l'étiquette d'un nœud est constant, les longueurs des chaînes converties sont | S 1 | = O( | T 1 | ) et | S 2 | = O( | T 2 | ) . Ainsi, la complexité de calcul du calcul de la fonction noyau est O( | T 1 | + | T 2 | ) , qui est linéaire.

Noyau d'arborescence basé sur des sous-chemins

Le noyau d'arbre ci-dessus a utilisé une approche horizontale, ou en largeur d'abord, pour convertir les arbres en chaînes. Bien que cette approche soit assez simple, cette conversion signifie qu'elle ne peut pas opérer directement sur les arbres dans leur forme d'origine.

Cette section définira un noyau d'arbre qui opère sur les structures verticales des arbres, permettant au noyau d'opérer directement sur l'arbre.

Une sous-section d'un chemin de la racine à l'une des feuilles est appelée un sous- chemin , et un ensemble de sous-chemins est l'ensemble de tous les sous-chemins inclus dans l'arbre :

Supposons que l'on veuille définir un noyau d'arbre K(T 1 , T 2 ) entre deux arbres T 1 et T 2 . En utilisant l'ensemble de sous-chemins, nous pouvons définir ce noyau d'arbre comme :

K(T 1 , T 2 ) = Σ p∈P num p (T 1 )num p (T 2 )w | p |

Où num p (T) est le nombre de fois que le sous-chemin p apparaît dans l'arbre T , | p | est le nombre de nœuds dans le sous-chemin p , et P est l'ensemble de tous les sous-chemins dans T 1 et T 2 . w | p | est le poids, similaire à celui introduit dans la section précédente.

Ici, nous présentons une implémentation simple de ce noyau en utilisant une recherche en profondeur d'abord. Bien que cet algorithme s'exécute en temps quadratique, des algorithmes plus efficaces existent en utilisant des arbres de suffixes ou des tableaux de suffixes, ou une extension de l'algorithme de tri rapide multiclé, qui peut atteindre un temps linearithmique ( O( | T 1 | log | T 2 | ) ) en moyenne :

 subpath_track = {} def generate_subpaths(path, l): if l == len(path): if tuple(path) not in subpath_track: subpath_track[tuple(path)] = 1 else: subpath_track[tuple(path)] += 1 else: index = 0 while l+index-1 < len(path): if tuple(path[index: l+index]) not in subpath_track: subpath_track[tuple(path[index: l+index])] = 1 else: subpath_track[tuple(path[index: l+index])] += 1 index += 1 generate_subpaths(path, l+1) def get_subpaths(graph, root, track, path): track[root] = True if graph.degree(root) == 1: generate_subpaths(path, 1) else: for node in graph.neighbors(root): if node not in track: get_subpaths(graph, node, track, path + [node, ]) def kernel_subpath(t1, t2, common_track): kernel_v = 0 for p in subpath_track: kernel_v += common_track[t1][p]*common_track[t2][p] return kernel_v

Dans cet exemple, nous avons utilisé le paramètre de pondération w | s | w | p | = 1 . Cela donne à tous les sous-chemins une pondération égale. Cependant, il existe de nombreux cas où l'utilisation de la pondération du spectre k , ou d'une valeur de pondération attribuée dynamiquement, est appropriée.

Sites Web miniers

Avant de conclure, examinons brièvement une application réelle de la classification arborescente : la catégorisation des sites Web. Dans de nombreux contextes d'exploration de données, il est utile de savoir de quel « type » de site Web proviennent certaines données. Il s'avère que les pages de différents sites Web peuvent être classées assez efficacement à l'aide d'arborescences en raison des similitudes dans la structure des pages Web pour des services similaires.

Comment fait-on cela? Les documents HTML ont une structure imbriquée logique, qui ressemble beaucoup à un arbre. Chaque document contient un élément racine, avec des éléments supplémentaires imbriqués à l'intérieur. Les éléments imbriqués dans une balise HTML sont logiquement équivalents aux nœuds enfants de cette balise :

Examinons un code capable de convertir un document HTML en arborescence :

 def html_to_dom_tree(root): node_id = 1 q = deque() graph = nx.Graph() q.appendleft({'element': root, "root_id": node_id}) while len(q): node = q.pop() if node and node['element'].name == "body": graph.add_node(node_id, element=node['element'].name) node_id += 1 root_id = node['root_id'] labels[root_id] = node['element'].name for t in node['element'].contents: if t and t.name: graph.add_node(node_id, element=t.name) graph.add_edge(root_id, node_id) q.appendleft({"element": t, "root_id": node_id}) node_id += 1 return graph

Cela produira une structure de données arborescente qui pourrait ressembler à ceci :

L'implémentation ci-dessus utilise quelques bibliothèques Python utiles : NetworkX, pour travailler avec des structures de graphes complexes, et Beautiful Soup, pour extraire des données du Web et manipuler des documents.

L'appel html_to_dom_tree(soup.find("body")) renverra un objet graphique NetworkX enraciné à l'élément <body> de la page Web.

Supposons que nous souhaitions rechercher des groupes dans un ensemble de 1 000 pages d'accueil de sites Web. En convertissant chaque page d'accueil en un arbre comme celui-ci, nous pouvons les comparer, par exemple en utilisant le noyau de l'arbre des sous-chemins donné dans la section précédente. Avec ces mesures de similarité, nous pourrions constater que, par exemple, les sites de commerce électronique, les sites d'actualités, les blogs et les sites éducatifs sont facilement identifiés par leur similarité les uns avec les autres.

Conclusion

Dans cet article, nous avons présenté des méthodes pour comparer des éléments de données arborescents entre eux et montré comment appliquer des méthodes de noyau aux arbres pour obtenir une mesure quantifiable de leur similarité. Les méthodes de noyau se sont révélées être un excellent choix lors de l'utilisation dans des espaces de grande dimension, une situation courante lorsque l'on travaille avec des structures arborescentes. Ces techniques préparent le terrain pour une analyse plus approfondie de grands ensembles d'arbres, en utilisant des méthodes bien étudiées qui fonctionnent sur la matrice du noyau.

Les structures arborescentes sont rencontrées dans de nombreux domaines de mots réels tels que les documents XML et HTML, les composés chimiques, le traitement du langage naturel ou certains types de comportement des utilisateurs. Comme le montre l'exemple de la construction d'arbres à partir de HTML, ces techniques nous permettent d'effectuer une analyse significative dans ces domaines.