[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.

• Extraction d'informations très polyvalente possible
• Comme les données des enseignants ne sont pas nécessaires, le coût de création est faible.
• Peut également être appliqué au prétraitement pour la création de données d'enseignants

WHAT

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

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

• Comparez la page avec chaque source d'informations pour calculer la distance.
• Obtenez ceux qui sont proches les uns des autres.

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

• Calcul de la distance

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

Arbre normal

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.

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.

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.

Les arborescences cibles pour ce traitement sont les suivantes.

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.

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.

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

anc：a, a sib：*, *, e

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

• La liste est combinée avec une conque.
• L'élément le plus ancien est supprimé par le traitement par décalage et l'élément donné par l'argument est ajouté.

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

• Récupère les éléments du profil et renvoie «False» si au moins un de chaque élément ne correspond pas

    
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