Science Des Données Et Bases De Données
Noyaux d'arbres: quantification de la similitude entre les données structurées en arborescence
À réseau ou graphique 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 bords . Les nœuds et les arêtes d'un graphique 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, ses réseaux sociaux, ses réseaux sémantiques, ses réseaux biologiques, ses réseaux de citations de littérature scientifique, etc.
À 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 examinerons l'analyse de la structure des liens dans les arbres. En particulier, nous nous concentrerons sur les noyaux d'arbres, une méthode pour comparer les graphiques d'arbres les uns aux autres, 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 classification et l'analyse des données .
Classification non supervisée des données structurées
Classification est un élément important apprentissage automatique et l'analyse des données . En général, la classification peut être supervisé ou non supervisé . 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 classes correctes 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 mesure de leur similitude.
La classification non supervisée peut être combinée à la théorie des graphes pour identifier des groupes de réseaux d'arbres similaires. Les 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é sous la forme d'un arbre dont les sommets sont associés à des états de recherche, et les arêtes représentent des étapes d'inférence. Également, données semi-structurées , tels que les documents HTML et XML, peuvent être modélisés sous forme d'arbres ordonnés et étiquetés.
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 à l'autre.
La malédiction de la dimensionnalité
La plupart des algorithmes de classification exigent que les données soient transformées en forme vectorisée , représentant les valeurs des données Caractéristiques dans le espace caractéristique , afin que les données puissent être analysées dans l'espace des fonctionnalités à 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 d'entités) peut être assez élevée, car l'espace d'entités 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 capables 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 ré . Supposer que X contient un ensemble de points uniformément répartis. Si le nombre de dimensions de X augmente, le nombre de points nécessaires pour conserver 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 rares. En général, un ensemble de données clairsemé ne donne pas suffisamment d'informations pour créer un bon classificateur car les corrélations entre les éléments de données sont trop faibles pour être détectées par les algorithmes.
Chaque espace d'entités ci-dessus contient huit points de données. Sur l’espace unidimensionnel, il est facile d’identifier un groupe de cinq points à gauche et 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 des données structurées est appropriée lorsque des informations sur le domaine peuvent être utilisées efficacement pour sélectionner un ensemble gérable de caractéristiques. Lorsque ces informations ne sont pas disponibles, il est souhaitable d’utiliser des techniques permettant de traiter directement des données structurées, sans effectuer d’opérations dans l’espace vectoriel.
Méthodes du noyau
Méthodes du noyau éviter la nécessité de convertir les données sous forme vectorielle. La seule information dont ils ont besoin est une mesure de la similitude 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 le fonction noyau . Les méthodes du noyau recherchent des relations linéaires dans l'espace des fonctionnalités. Sur le plan fonctionnel, ils équivalent à prendre le produit scalaire de deux points de données dans l'espace des fonctionnalités, et en fait, la conception des fonctionnalités peut encore être une étape utile dans la conception des fonctions du noyau. Cependant, les méthodes des méthodes du noyau évitent d’agir directement sur l’espace des fonctionnalités, car on peut montrer qu’il est possible de remplacer le produit scalaire par une fonction du noyau, tant que la fonction du noyau est un symétrique , positif semi-défini fonction qui peut prendre comme entrées les données dans leur espace d'origine.
L'avantage d'utiliser les fonctions du noyau est donc qu'un immense espace de fonctionnalités peut être analysé avec une complexité de calcul non dépendante de la taille de l'espace de fonctionnalités, mais de la complexité de la fonction du noyau, ce qui signifie que les méthodes du noyau ne subissent pas 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 dans les données en générant un matrice du 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 jeu de données d'exemples avec un grand espace d'entités doit être analysé.
applications de rencontres les plus populaires 2017
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 fonctionnalités, les données sont représentées via des comparaisons par paires dans une matrice de noyau À , et toutes les analyses pertinentes peuvent être effectuées sur la matrice du noyau.
De nombreuses méthodes d'exploration de données peuvent être noyées. Pour classer les instances de données structurées en arborescence avec des méthodes de noyau, comme avec soutenir les machines vectorielles , il suffit de définir une fonction noyau valide (symétrique positive définie) k: T × T → R , également appelé noyau d'arbre . Dans la conception de noyaux d'arbres pratiquement utiles, on exigerait qu'ils soient calculables en temps polynomial sur la taille de l'arbre, et qu'ils soient capables de détecter graphes isomorphes . Ces noyaux d'arbres sont appelés Achevée noyaux d'arbres.
Noyaux d'arbres
Maintenant, introduisons quelques noyaux d'arbres utiles pour mesurer la similitude 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 brève introduction aux noyaux de chaînes, qui nous aidera à introduire une autre méthode de noyau basée sur la conversion d'arbres en chaînes.
Définissons sur uneOui(s) comme le nombre d'occurrences d'une sous-chaîne Oui dans une chaîne s , avec |s| dénotant la longueur de la chaîne. Le noyau de chaîne que nous allons décrire ici est défini comme:
Àchaîne(Sun, S2) =Σs∈Fsur unes(Sun)sur unes(S2)danss
Où F est l'ensemble des sous-chaînes qui se produisent dans les deux Sun et S2 , et le paramètre danss sert de paramètre de pondération (par exemple, pour souligner 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 d’une 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:
Laisser T désignent l'un des arbres cibles, et étiquette (ns) l'étiquette de chaîne du nœud ns dans T . jour (ns) désigne la représentation sous forme de chaîne du sous-arbre de T enraciné à ns . Donc si nracine est le nœud racine de T , jour (nracine) est la représentation sous forme de chaîne de l'arbre entier T .
Ensuite, laissez chaîne (T) = balise (nracine) dénotent la représentation sous forme de chaîne de T . Nous appliquerons récursivement les étapes suivantes de manière ascendante pour obtenir chaîne (T) :
- Si le nœud ns est une feuille, laissez jour (ns) = '[' + Libellé (ns) + ']' (où + voici l'opérateur de concaténation de chaîne).
- Si le nœud ns n'est pas une feuille et a c les enfants nun, n2,…, Nc , Trier jour (nun), jour (n2), ..., jour (nc) dans l'ordre lexical pour obtenir jour (nun*), jour (n2 *), ..., jour (nc *) , et laissez jour (ns) = '[' + Libellé (ns) + jour (nun*) + jour (n2 *) + ... + jour (nc *) + ']' .
La figure ci-dessous montre un exemple de cette conversion d'arbre en chaîne. Le résultat est une chaîne commençant par un délimiteur d'ouverture tel que «[» et se terminant par son homologue de fermeture, «]», 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, Tun et T2 , pour obtenir deux chaînes Sun et S2 . À partir de là, nous pouvons simplement appliquer le noyau de chaîne décrit ci-dessus.
Le noyau de l'arbre entre Tun et T2 via deux cordes Sun et S2 peut maintenant être donné comme:
Àarbre(Tun, T2) = Kchaîne(chaîne (Tun), chaîne (T2)) = Kchaîne(Sun, S2) =Σs∈Fsur unes(Sun)sur unes(S2)danss
Dans la plupart des applications, le paramètre de poids devient dans|s| , pondération d'une sous-chaîne en fonction de sa longueur |s| . Méthodes de pondération typiques pour dans|s| sont:
- pondération constante ( dans|s|= 1 )
- à -la pondération spectrale ( dans|s|= 1 si |s|= k , et dans|s|= 0 autrement)
- pondération exponentielle ( dans|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 pour compter le nombre de fois où ils se produisent Sun et S2 . Cette étape supplémentaire de recherche de sous-chaînes communes est un problème bien étudié et peut être accomplie en OU(|Sun|+|S2|) , employant arbres de suffixe ou 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 |Sun|= O (|Tun|) et |S2|= O (|T2|) . Ainsi, la complexité de calcul du calcul de la fonction noyau est OU(|Tun|+|T2|) , qui est linéaire.
Noyau d'arbre basé sur les sous-chemins
Le noyau d'arbre ci-dessus a utilisé une approche horizontale, ou 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 sur les arbres directement dans leur forme originale.
Cette section définira un noyau arborescent qui opère sur les structures verticales dans les arbres, permettant au noyau d'opérer directement sur l'arbre.
Une sous-section d'un chemin allant de la racine à l'une des feuilles s'appelle un sous-chemin , et un ensemble de sous-chemins est l'ensemble de tous les sous-chemins inclus dans l'arborescence:
Supposons que nous voulons définir un noyau d'arbre K (Tun, T2) entre deux arbres Tun et T2 . En utilisant l'ensemble de sous-chemins, nous pouvons définir ce noyau d'arbre comme:
K (Tun, T2) =Σp∈Psur unep(Tun)sur unep(T2)dans|p|
Où sur unep(T) est le nombre de fois où le sous-chemin p se produit 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 Tun et T2 . dans|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, il existe des algorithmes plus efficaces utilisant des arbres de suffixes ou des tableaux de suffixes, ou une extension de l'algorithme de tri rapide multikey, qui peut atteindre un temps linéaireithmique ( OU(|Tun|Journal|T2|) ) 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 Dans cet exemple, nous avons utilisé le paramètre de pondération w|s| dans|p|= 1 . Cela donne à tous les sous-chemins une pondération égale. Cependant, il existe de nombreux cas d'utilisation à -la pondération du spectre, ou une certaine valeur de poids attribuée dynamiquement, est appropriée.
Sites Web miniers
Avant de conclure, examinons brièvement une application concrète de la classification des arbres: 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 catégorisées assez efficacement à l'aide d'arbres en raison des similitudes dans la façon dont les pages Web pour des services similaires sont structurées.
Comment fait-on cela? Les documents HTML ont une structure logique imbriquée, 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:
Jetons un œil à un code permettant 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 Belle soupe , pour extraire des données du Web et manipuler des documents.
Appel html_to_dom_tree(soup.find('body')) renverra un objet graphique NetworkX enraciné à l'élément de la page Web.
Supposons que nous souhaitons 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'arborescence de sous-chemins donné dans la section précédente. Avec ces mesures de similitude, 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 similitude les uns avec les autres.
Conclusion
Dans cet article, nous avons présenté des méthodes pour comparer les éléments de données structurés en arborescence les uns aux autres et montré comment appliquer les méthodes du noyau aux arbres pour obtenir une mesure quantifiable de leur similitude. Les méthodes de noyau se sont avérées être un excellent choix pour fonctionner 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 opèrent sur la matrice du noyau.
Les arborescences 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 démontré dans l'exemple de construction d'arbres à partir de HTML, ces techniques nous permettent d'effectuer une analyse significative dans ces domaines.
