[PYTHON] Comment obtenir uniquement les données nécessaires du groupe de données structurées à l'aide d'une méthode polyvalente

WHY

La demande d'acquérir uniquement des informations arbitraires à partir de données structurées (HTML, Json, XML) est également requise pour la détection des anomalies, le chlorler et l'analyse des données. Il existe également une méthode de réglage manuel ou d'acquisition par apprentissage automatique avec un enseignant, mais la méthode introduite cette fois-ci est une méthode consistant à se concentrer sur la structure de données structurées, à calculer la différence dans la structure et à n'acquérir que des informations arbitraires. J'aimerais présenter_______

Les points suivants peuvent être atteints par cette méthode.

WHAT

Cette section décrit la procédure spécifique.

--Préparez la source d'informations (HTML, JSON, etc.) que vous souhaitez obtenir.

Voici la procédure. Pour le calcul de la distance, décrivez à partir de Tree Edit Distance, qui est intuitivement facile à comprendre, puis décrivez PQ Edit Distance, qui est une méthode de calcul approximative.

"PQ Edit Distance" est utile lorsque vous traitez avec une grande quantité de données ou lorsque vous souhaitez faire une comparaison en se concentrant sur la différence structurelle globale, et "Tree Edit Distance" est bon lorsque vous souhaitez comparer des éléments individuels et lorsque vous souhaitez gérer une petite quantité de données.

Dans l'environnement de l'auteur, il y a une différence d'environ 100 fois dans le temps de calcul, donc lorsque vous traitez avec une grande quantité de données (cela dépend de l'environnement, cela ne peut pas être dit sans condition), sélectionnez "PQ Edit Distance".

Tree Edit Distance

Les données structurées fonctionnent bien avec les structures arborescentes. À ce stade, la distance de modification de l'arbre vient immédiatement à l'esprit. Tree Edit Distance est une méthode principalement utilisée pour calculer la distance entre les structures arborescentes.

Trois opérations sont nécessaires lors de la conversion des données structurelles en une structure arborescente et de la mesure de la différence dans la structure.

ajouter à

ファイル名

Effacer

ファイル名

Remplacer

ファイル名

Tout d'abord, supposons un tableau simple S et réfléchissez comme suit.

gamma est le coût de remplacement H comme premier élément T pour le reste des éléments

Opération d'en haut Remplacement: le coût de remplacement entre les premiers éléments et les éléments restants est également calculé de manière récursive et la valeur totale de la distance est renvoyée. Supprimer: renvoie la somme des distances en calculant récursivement le coût de suppression du premier élément et le coût du tableau à comparer avec les éléments restants. Insertion: Le coût supplémentaire entre les premiers éléments et le calcul de coût autre que le coût supplémentaire du tableau à comparer avec le tableau d'origine sont effectués de manière récursive et la valeur totale de la distance est renvoyée

Cela se fait récursivement car d est à l'intérieur.

d(S_1, S_2) = min(\gamma(H(S_1),H(S_2)) + d(T(S_1),T(S_2)), \\
                  \gamma(H(S_1),\vec{0}) + d(T(S_1),S_2), \\
                  \gamma(\vec{0},H(S_2)) + d(S_1,T(S_2)), 
)

Ensuite, considérez l'arbre. Dans le cas d'un arbre, vous pouvez le considérer comme une racine et des nœuds enfants, mais s'il y a plusieurs nœuds enfants, plusieurs arbres seront créés lorsque la racine est supprimée, et la description ci-dessus ne peut pas être faite. Considérez un arbre comme une collection d'arbres ordonnés. Si vous supprimez le nœud racine, vous pouvez le décomposer dans la forêt du nœud enfant de l'arborescence la plus à droite et dans les autres forêts.

Remplacement: La valeur totale du calcul du coût de la distance de remplacement de l'arbre le plus à droite, le calcul de la distance de la forêt du nœud enfant de l'arbre le plus à droite et le calcul de la distance des autres forêts. Supprimer: La valeur totale du calcul du coût de la distance de suppression de l'arbre le plus à droite et la distance entre la forêt du nœud enfant de l'arbre le plus à droite après suppression et la forêt à comparer avec les autres forêts. Addition: La valeur totale du calcul du coût de distance supplémentaire de l'arbre le plus à droite et la distance entre la forêt d'origine et la forêt du nœud enfant de l'arbre le plus à droite à comparer et les autres forêts à comparer.

Figure

d(F_1, F_2) = min(\gamma(R(F_1),R(F_2)) + d(C(F_1),C(F_2))+ d(L(F_1),L(F_2)), \\
                  \gamma(R(F_1),\vec{0}) + d(L(F_1) + C(F_1),F_2), \\
                  \gamma(\vec{0},R(F_2)) + d(F_1, L(F_2) + C(F_2)),
)

Lors de la comparaison et du calcul de tous les nœuds, le coût de calcul de «O (n ^ 2)» est encouru. Même si le coût de la distance est mémorisé et calculé par la méthode de planification dynamique, le coût de calcul de la distance sera élevé. Par conséquent, il est envisageable d'utiliser une méthode approximative sans effectuer un calcul de distance strict.

PQ Edit Distance

PQ Edit Distance est une méthode dans laquelle le coût de calcul converge à ʻO (nlogn) et l'espace de calcul est également supprimé en ʻO (n). n est le nombre de nœuds dans l'arborescence.

La distance d'édition PQ crée ce qu'on appelle un profil à partir d'une structure arborescente sans tenir compte des opérations de remplacement, d'insertion et de suppression. Ce profil couvre les modèles que la structure arborescente peut prendre et constitue une méthode pour mesurer le degré de correspondance des modèles. La création du profil dépend des paramètres P et Q.

Il y a deux parties essentielles.

--Création d'un profil PQ

Pour créer des profils PQ, pq-gram traite les arbres et les sous-arbres avec une structure spéciale.

Arbre normal

Screen Shot 2016-11-29 at 3.12.28 PM.png

Arbres manipulés par PQ (P: 2, Q: 3)

Étant donné que les valeurs de P et Q dépendent de la structure de l'arbre, les valeurs de P et Q sont actuellement réglées manuellement pour sélectionner la meilleure. Je voudrais savoir si cela peut être réglé automatiquement.

Screen Shot 2016-11-29 at 3.11.07 PM.png

Créez un profil en effectuant un traitement récursif sur les racines et les feuilles comme indiqué ci-dessous.

Définition 6: Définissez la distance pq gramme comme suit

\Delta^{p,q}(\vec{T_1}, \vec{T_2}) = 1 - 2\frac{P^{p,q}(\vec{T_1}) \cap P^{p,q}(\vec{T_2})}{P^{p,q}(\vec{T_1}) \cup P^{p,q}(\vec{T_2})}

La raison du doublement est que le taux de correspondance maximum est la moitié de la somme des deux arbres.

Différence par rapport à la distance d'édition d'arbre

Dans le cas de PQ, la différence est saisie par la distance entre les profils. C'est une approximation, mais elle présente certains avantages par rapport à la distance d'édition d'arbre.

Screen Shot 2016-11-28 at 3.41.56 PM.png

Dans la figure, dans le cas de Tree Edit Distance, la distance d'édition est de 2 pour T'et T ''. C'est parce que T'a pas assez d'éléments "g" et "k", et T "n'a pas assez d'éléments" c "et" e ", donc la distance d'édition est de 2 par rapport à T. Cependant, T'et T '' ont une structure très différente. Il n'est pas très bon de traiter cette distance de la même manière. Dans le cas de PQ, la différence est claire. Il s'agit de la différence entre Tree Edit Distance, qui ne mesure que les différences individuelles, et PQ Edit Distance, qui mesure la différence globale.

HOW

Nous allons introduire l'algorithme en utilisant la définition ci-dessus et présenter un exemple d'implémentation.

algorithme

Pensez à l'appliquer à l'arborescence suivante.

Préparez d'abord deux registres à décalage.

anc: p (pour le nœud parent) sib: q (pour les nœuds enfants)

Le traitement du registre consiste à retirer l'ancien et à insérer le nouveau.

Exemple

shift((a,b,c),x) return (b,c,x)

Créez un pq-gramme en combinant anc et sib.

Sur cette base, le profil de PQ gramme est renvoyé.

et démissionner la fratrie se déplace de gauche à droite

Le flux de l'algorithme spécifique est illustré dans la figure.

Screen Shot 2016-11-28 at 12.49.25 PM.png

Les arborescences cibles pour ce traitement sont les suivantes.

Screen Shot 2016-11-28 at 1.05.23 PM.png

Ce que vous voulez faire dans ce processus est de créer un profil. Le traitement de profil peut être décrit de manière récursive, c'est donc comme suit.

pg-GRAM-PROFILE(T, p, q)
    P: empty relation with schema(labels)
    anc: shift register of size p (filled with *)
    P = PROFILE(T, p, q, P, root(T), anc)
    return P

Initialisez d'abord le profil. Remplissez anc avec "*". Passez l'arborescence pour laquelle vous souhaitez créer un profil pour cette fois, les valeurs p et q définies, le profil, le nœud racine de l'arborescence et anc à la fonction PROFIL.

PROFILE(T, p, q, P, r, anc)
    anc:= shift(anc, l(r))
    sib: shift register of size q (filled with *)
    if r is a leaf then
        P := P U (anc ○ sib)
    else
        for each child c (from left to right) of r do
            sib := shift(sib, l(c))
            P := P U (anc ○ sib)
            P := PROFILE(T, p, q, P, c, anc)
        for k := 1 to q-1
            sib := shift(sib, *)
            P := P U (anc ○ sib)
    return P

Insérez l'étiquette r dans anc. (R est le nœud racine au début, et le nœud change en raison du traitement récursif) Initialisez sib. Si r est une feuille, créez un ensemble de profils qui concaténent anc et sib Si ce n'est pas le cas, le traitement est effectué pour chaque nœud enfant du nœud. Dans le cas du premier traitement, le traitement est effectué pour chaque nœud enfant (a, b, c) avec a comme nœud racine.

Screen Shot 2016-11-28 at 1.34.19 PM.png

Le premier anc est fixé avec *, a Insérez le second dans sib t *, *, a. La partie à laquelle nous prêtons attention ici est la partie suivante. Concaténez anc et sib pour créer *, a, *, *, a et ajoutez-le à PROFILE pour créer un ensemble de somme.

ファイル名

Puisqu'il s'agit d'un processus récursif, s'il existe un nœud enfant, nous nous concentrerons sur la partie suivante.

Screen Shot 2016-11-28 at 2.41.11 PM.png

Lors du traitement de ʻe avec anc comme ʻa, a

anc:a, a sib:*, *, e

Screen Shot 2016-11-28 at 2.42.24 PM.png

Lorsque anc est traité comme «a, e»

anc:a, e sib:*, *, *

Puisqu'il atteint enfin les feuilles, ajoutez la somme définie jusqu'à présent. Répétez cette opération de manière récursive pour créer un profil PQ.

Mesurez la distance de l'arborescence entre ce profil et la distance définie précédemment.

Les valeurs de p et q sont des hyperparamètres et dépendent de la structure arborescente. Il est nécessaire de définir les paramètres les plus appropriés en fonction de la structure de l'arbre.

Méthode de mise en œuvre

--Création d'un nœud pour les données de l'arborescence --Shift Register pour l'édition --PROFILE pour l'édition du calcul de distance

Ceci peut être réalisé avec une méthode de mise en œuvre simple.

Création d'un nœud pour les données de l'arborescence

Il est nécessaire de convertir les données structurées en une structure arborescente et de la gérer. Je l'ai créé simplement avec le code ci-dessous

Processus d'initialisation pour définir une étiquette sur le nœud Traitement pour ajouter des nœuds enfants à Node


class NodePQ(object):

    def __init__(self, label):
        self.label = label
        self.children = list()

    def addkid(self, node, before=False):
        if before:
            self.children.insert(0, node)
        else:
            self.children.append(node)
        return node

Registre à décalage pour l'édition

Entrez la description de «Shift Register».

--Préparer une liste initialisée avec * pour la taille de l'argument

class ShiftRegister(object):

    def __init__(self, size):
        self.register = list()
        for i in range(size):
            self.register.append("*")

    def concatenate(self, reg):
        temp = list(self.register)
        temp.extend(reg.register)
        return temp

    def shift(self, el):
        self.register.pop(0)
        self.register.append(el)

PROFILE

C'est la partie qui crée anc et sib et crée récursivement PROFILE.

--Définissez ShiftRegister pour les ancêtres dans la partie d'initialisation. --Créer PROFILE en utilisant les ancêtres définis. --Trier le PROFIL créé


class ProfilePQ(object):

    def __init__(self, root, p=2, q=3):
        super(ProfilePQ, self).__init__()
        ancestors = ShiftRegister(p)
        self.list = list()

        self.profile(root, p, q, ancestors)
        self.sort()

Cette partie est un processus important pour la distance PQ.

--Définit l'étiquette racine donnée dans l'argument aux ancêtres. --Définissez les registres à décalage pour la taille q dans les frères et sœurs. --Lorsque le nombre d'enfants devient 0, concatène les ancêtres et les frères et sœurs pour créer un profil. --Ajoutez un élément aux frères et sœurs pour l'enfant de root et cliquez sur. Ce processus est effectué de manière récursive jusqu'à ce qu'il n'y ait pas d'enfants. --Lorsque vous allez vers le plus jeune enfant, indiquez les frères et sœurs en dessous avec "*"

    def profile(self, root, p, q, ancestors):
        ancestors.shift(root.label)
        siblings = ShiftRegister(q)

        if(len(root.children) == 0):
            self.append(ancestors.concatenate(siblings))
        else:
            for child in root.children:
                siblings.shift(child.label)
                self.append(ancestors.concatenate(siblings))
                self.profile(child, p, q, copy.deepcopy(ancestors))
            for i in range(q-1):
                siblings.shift("*")
                self.append(ancestors.concatenate(siblings))

Ce sera la partie calcul de la distance. Cette ʻedit_distance est utilisée pour calculer la distance entre PROFILE et l'autre donnée en argument. Nous calculons le taux de correspondance des éléments Node créés dans ʻintersection.


    def edit_distance(self, other):
        with Bench():
            union = len(self) + len(other)
            return 1.0 - 2.0*(self.intersection(other)/union)

    def intersection(self, other):
        intersect = 0.0
        i = j = 0
        while i < len(self) and j < len(other):
            intersect += self.gram_edit_distance(self[i], other[j])
            if self[i] == other[j]:
                i += 1
                j += 1
            elif self[i] < other[j]:
                i += 1
            else:
                j += 1
        return intersect

    def gram_edit_distance(self, gram1, gram2):
        distance = 0.0
        if gram1 == gram2:
            distance = 1.0
        return distance

C'est la fin de l'implémentation, mais vous devez la tester pour vous assurer qu'elle fonctionne correctement.

À propos du test

Le processus suivant vérifie si les profils sont égaux.

--Vérifiez la longueur et renvoyez False si elles sont différentes ou False si le premier élément est différent

    
def checkProfileEquality(self, profile1, profile2):
        if len(profile1) != len(profile2) or len(profile1[0]) != len(profile2[0]):
            return False
        for gram1 in profile1:
            contains = False
            for gram2 in profile2:
                if gram1 == gram2:
                    contains = True
                    break
            if contains == False:
                return False
        return True

Paramètres initiaux pour p et q. Réglage de la valeur aléatoire

    def setUp(self):
        self.p = 2
        self.q = 3
        num_random = 10
        self.trees = list()
        self.profiles = list()

Créer un arbre pour les tests


        # Construct one-node trees
        self.small_tree1 = NodePQ("a")
        self.small_tree2 = NodePQ("b")
        self.trees.append(self.small_tree1)
        self.trees.append(self.small_tree2)

        self.small_profile1 = [['*','a','*','*','*']]
        self.small_profile2 = [['*','b','*','*','*']]

Créez un arbre aléatoire et créez un profil à partir de cet arbre.

        # Construct a few randomly generated trees
        for i in range(0, num_random):
            depth = random.randint(1, 10)
            width = random.randint(1, 5)
            self.trees.append(randtree(depth=depth, width=width, repeat=4))

        # Generate Profiles
        for tree1 in self.trees:
            self.profiles.append(ProfilePQ(tree1, self.p, self.q))

Créez un arbre aléatoire par le processus suivant.

def randtree(depth=2, alpha='abcdefghijklmnopqrstuvwxyz', width=2, repeat=2):
    labels = [''.join(x) for x in itertools.product(alpha, repeat=repeat)]
    random.shuffle(labels)
    labels = (x for x in labels)
    root = NodePQ("root")
    p = [root]
    c = list()
    for x in range(depth-1):
        for y in p:
            for z in range(random.randint(1,1+width)):
                n = NodePQ(next(labels))
                y.addkid(n)
                c.append(n)
        p = c
        c = list()
    return root

Je calcule si le calcul de la distance est correct

    def testProfileCreation(self):
        small_tree1_equality = self.checkProfileEquality(self.profiles[0], self.small_profile1)
        small_tree2_equality = self.checkProfileEquality(self.profiles[1], self.small_profile2)

        self.assertEqual(small_tree1_equality, True)
        self.assertEqual(small_tree2_equality, True)

On vérifie si le calcul est correct même si la distance entre A et B et l'opposé de la distance entre B et A sont inversées.


def testSymmetry(self):
        """x.edit_distance(y) should be the same as y.edit_distance(x)"""
        for profile1 in self.profiles:
            for profile2 in self.profiles:
                self.assertEqual(profile1.edit_distance(profile2), profile2.edit_distance(profile1))

Vérifiez si le calcul de la distance est compris entre 0 et 1

    def testEditDistanceBoundaries(self):
        for profile1 in self.profiles:
            for profile2 in self.profiles:
                self.assertTrue(profile1.edit_distance(profile2) <= 1.0 and profile1.edit_distance(profile2) >= 0

Résumé

L'avantage de cette méthode est qu'elle peut être utilisée universellement pour les données structurées. Puisqu'il s'agit d'une méthode qui peut être utilisée s'il existe un ensemble de données pouvant être converti en une structure arborescente telle que HTML, json, XML, etc., elle dispose d'un large éventail d'applications telles que l'extraction des données nécessaires et la détection d'anomalies, nous apprécierions donc que vous puissiez l'essayer.

référence

Tree Edit Distance et application au traitement du langage naturel Approximate Matching of Hierarc hical Data Using pq -Grams

Recommended Posts

Comment obtenir uniquement les données nécessaires du groupe de données structurées à l'aide d'une méthode polyvalente
Comment obtenir des abonnés et des abonnés de Python à l'aide de l'API Mastodon
Comment diviser et traiter une trame de données à l'aide de la fonction groupby
Comment obtenir la valeur du magasin de paramètres dans lambda (en utilisant python)
Comment obtenir un exemple de rapport à partir d'une valeur de hachage à l'aide de l'API de Virus Total
[Environnement de développement] Comment créer un ensemble de données proche de la base de données de production
Comment obtenir le nom du bloc-notes que vous utilisez actuellement dans Google Colab
Utilisez PIL en Python pour extraire uniquement les données souhaitées d'Exif
[Introduction à Python] Comment obtenir l'index des données avec l'instruction for
Comment écrire une interface graphique à l'aide de la commande maya
Comment configurer un environnement Python à l'aide de pyenv
Comment publier un ticket depuis l'API Shogun
Comment utiliser la méthode __call__ dans la classe Python
Comment transloquer un tableau à deux dimensions en utilisant uniquement python [Note]
J'ai essayé "Comment obtenir une méthode décorée en Python"
Comment générer une requête à l'aide de l'opérateur IN dans Django
Comment obtenir la dernière (dernière) valeur d'une liste en Python
Comment représenter la distribution de la composition bactérienne à partir des données d'analyse Qiime2 dans un diagramme de moustaches
Comment obtenir la température du thermo-hygromètre SwitchBot à l'aide de Raspberry Pi
Comment obtenir une liste de liens à partir d'une page de wikipedia
[Introduction à Python] Comment obtenir des données avec la fonction listdir
J'ai essayé d'obtenir rapidement des données d'AS / 400 en utilisant pypyodbc
[Apprentissage de Django avec la lame du diable] Comment obtenir un ensemble de requêtes pour une référence avant / arrière
Comment obtenir et définir le nom du serveur NTP par DHCP
Comment obtenir toutes les valeurs possibles dans une expression régulière
Comment obtenir une chaîne à partir d'un argument de ligne de commande en python
[Python] Comment obtenir et modifier les lignes / colonnes / valeurs d'une table.
Comment utiliser la reconnaissance visuelle pour obtenir l'ID de ligne d'une fille
Comment enregistrer une partie d'une longue vidéo en utilisant OpenCV
Comment obtenir les coordonnées de sommet d'une entité dans ArcPy
Comment extraire la chaîne de caractères souhaitée à partir d'une ligne 4 commandes
Comment mettre à jour une source de données de classeur packagée Tableau à l'aide de Python
Utilisez ScraperWiki pour obtenir régulièrement des données de votre site Web
Comment obtenir un ingénieur de la trentaine
Trouvez tous les modèles pour extraire un nombre spécifique de l'ensemble
J'ai essayé d'obtenir rapidement des données d'AS / 400 en utilisant pypyodbc Préparation 1
Comment obtenir la version Python
Obtenez des données de Twitter avec Tweepy
Comment créer un ensemble de données d'image de visage utilisé dans l'apprentissage automatique (3: Génération d'images de visage à partir d'images candidates, partie 1)
Que faire si vous obtenez un avertissement "Mauvaise plateforme Python" lors de l'utilisation de Python avec l'EDI NetBeans
[Python] Qu'est-ce qu'un argument formel? Comment définir la valeur initiale
Fiche d'apprentissage (4e jour) #Comment obtenir le chemin absolu à partir du chemin relatif
Je souhaite envoyer un signal uniquement du sous-thread au thread principal
Essayez d'obtenir l'état de la surface de la route en utilisant de grandes données de gestion de la surface de la route
Pour trouver le nom de la vue avec l'espace de noms à partir de l'URL (path_info) dans Django
Comment réparer la population initiale avec un algorithme génétique utilisant DEAP
Si vous souhaitez créer une application TODO (distribuée) en utilisant uniquement Python-Extension 1
Obtenez le titre de la chanson à partir du titre de la vidéo que vous avez chanté
Comment créer une application à partir du cloud à l'aide du framework Web Django
Comment enregistrer une seule donnée sur l'écran de gestion de Django
Comment créer un clone depuis Github
Comment dessiner un graphique avec Matplotlib
Comment configurer SVM à l'aide d'Optuna
Comment régler l'heure du serveur sur l'heure japonaise
Comment installer un package à l'aide d'un référentiel
Comment obtenir stacktrace en python
Comment obtenir une sortie colorée sur la console
Comment faire fonctionner Linux depuis la console
Comment créer un ensemble de données d'image de visage utilisé dans l'apprentissage automatique (1: Acquérir des images de candidats à l'aide du service API Web)
Comment créer un référentiel à partir d'un média
Comment accéder à la banque de données de l'extérieur