[PYTHON] So erhalten Sie mit einer vielseitigen Methode nur die erforderlichen Daten aus der strukturierten Datengruppe

WHY

Die Anforderung, nur beliebige Informationen aus strukturierten Daten (HTML, Json, XML) zu erfassen, ist auch für die Erkennung von Anomalien, die Chlorierung und die Datenanalyse erforderlich. Es gibt auch Methoden zum manuellen Einstellen und Erfassen durch maschinelles Lernen mit einem Lehrer. Die diesmal eingeführte Methode ist jedoch eine Methode, um sich auf die Struktur strukturierter Daten zu konzentrieren, den Unterschied in der Struktur zu berechnen und nur beliebige Informationen zu erfassen. Ich möchte _______ vorstellen

Die folgenden Punkte können mit dieser Methode erreicht werden.

• Sehr vielseitige Informationsextraktion ist möglich
• Da keine Lehrerdaten erforderlich sind, sind die Erstellungskosten niedrig.
• Kann auch auf die Vorverarbeitung zur Erstellung von Lehrerdaten angewendet werden

WHAT

Dieser Abschnitt beschreibt das spezifische Verfahren.

• Bereiten Sie die Informationsquelle (HTML, JSON usw.) vor, die Sie erhalten möchten.
• Vergleichen Sie die Seite mit jeder Informationsquelle, um die Entfernung zu berechnen.
• Holen Sie sich diejenigen, die nahe beieinander sind.

Dies ist das Verfahren. Beschreiben Sie für die Entfernungsberechnung die intuitiv leicht verständliche Baumbearbeitungsentfernung und anschließend die PQ-Bearbeitungsentfernung, eine ungefähre Berechnungsmethode.

"PQ Edit Distance" ist gut, wenn Sie mit einer großen Datenmenge arbeiten oder wenn Sie einen Vergleich durchführen möchten, der sich auf den gesamten strukturellen Unterschied konzentriert, und "Tree Edit Distance" ist gut, wenn Sie einzelne Elemente vergleichen möchten und wenn Sie eine kleine Datenmenge verarbeiten möchten.

In der Umgebung des Autors gibt es einen etwa 100-fachen Unterschied in der Berechnungszeit. Wenn Sie also mit einer großen Datenmenge arbeiten (dies hängt von der Umgebung ab und kann nicht unbedingt gesagt werden), wird "PQ Edit Distance" ausgewählt.

Tree Edit Distance

Strukturierte Daten funktionieren gut mit Baumstrukturen. Zu diesem Zeitpunkt fällt Ihnen sofort die Baumbearbeitungsentfernung ein. Baumbearbeitungsabstand ist eine Methode, die hauptsächlich zur Berechnung des Abstands zwischen Baumstrukturen verwendet wird.

Es sind drei Operationen erforderlich, um Strukturdaten in eine Baumstruktur zu konvertieren und den Unterschied in der Struktur zu messen.

hinzufügen

Löschen

Ersetzen

Nehmen Sie zunächst ein einfaches Array S an und denken Sie wie folgt.

Gamma sind die Wiederbeschaffungskosten H als erstes Element T für den Rest der Elemente

Bedienung von oben Ersatz: Die Wiederbeschaffungskosten zwischen den ersten Elementen und den verbleibenden Elementen werden ebenfalls rekursiv berechnet und der Gesamtwert der Entfernung wird zurückgegeben. Löschen: Gibt die Summe der Abstände zurück, indem die Kosten für das Löschen des ersten Elements und die Kosten des zu vergleichenden Arrays mit den übrigen Elementen rekursiv berechnet werden. Einfügen: Die zusätzlichen Kosten zwischen den ersten Elementen und der Kostenberechnung außer den zusätzlichen Kosten des Arrays, die mit dem ursprünglichen Array verglichen werden sollen, werden rekursiv durchgeführt und der Gesamtwert der Entfernung wird zurückgegeben.

Es wird rekursiv gemacht, weil d drin ist.

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)), 
)

Als nächstes betrachten wir den Baum. Im Fall eines Baums sollten Sie über den Stammknoten und den untergeordneten Knoten nachdenken. Wenn jedoch mehrere untergeordnete Knoten vorhanden sind, werden beim Entfernen des Stamms mehrere Bäume erstellt, und die obige Beschreibung kann nicht vorgenommen werden. Stellen Sie sich einen Baum als eine Sammlung geordneter Bäume vor. Wenn Sie den Stammknoten löschen, können Sie ihn in die Gesamtstruktur des untergeordneten Knotens des Baums ganz rechts und in die anderen Gesamtstrukturen zerlegen.

Ersatz: Der Gesamtwert der Berechnung der Ersatzentfernungskosten für den Baum ganz rechts, der Berechnung der Waldentfernung des untergeordneten Knotens des Baums ganz rechts und der Entfernungsberechnung der anderen Wälder. Löschen: Der Gesamtwert der Berechnung der Löschentfernungskosten des Baums ganz rechts und der Entfernung zwischen der Gesamtstruktur des untergeordneten Knotens des Baums ganz rechts nach dem Löschen und der Gesamtstruktur, die mit anderen Gesamtstrukturen verglichen werden soll Addition: Der Gesamtwert der Berechnung der zusätzlichen Entfernungskosten für den Baum ganz rechts und die Entfernung zwischen dem ursprünglichen Wald und dem Wald des untergeordneten Knotens des zu vergleichenden Baums ganz rechts und den anderen zu vergleichenden Wäldern.

Zahl

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)),
)

Beim Vergleichen und Berechnen aller Knoten fallen Berechnungskosten von "O (n ^ 2)" an. Selbst wenn die Entfernungskosten durch die dynamische Planungsmethode gespeichert und berechnet werden, sind die Entfernungsberechnungskosten hoch. Daher ist es denkbar, eine ungefähre Methode zu verwenden, ohne eine strikte Entfernungsberechnung durchzuführen.

PQ Edit Distance

PQ Edit Distance ist eine Methode, bei der die Berechnungskosten bei "O (nlogn)" konvergieren und der Berechnungsraum ebenfalls auf "O (n)" unterdrückt wird. n ist die Anzahl der Knoten im Baum.

PQ Edit Distance erstellt aus einer Baumstruktur ein sogenanntes Profil, ohne die Ersetzungs-, Einfüge- und Löschvorgänge zu berücksichtigen. Dieses Profil deckt die Muster ab, die die Baumstruktur annehmen kann, und ist eine Methode zum Messen des Übereinstimmungsgrades der Muster. Die Profilerstellung hängt von den P- und Q-Parametern ab.

Es gibt zwei wesentliche Teile.

--Erstellen eines PQ-Profils

• Entfernungsberechnung

Zum Erstellen von PQ-Profilen behandelt pq-gram Bäume und Teilbäume mit einer speziellen Struktur.

Normaler Baum

Von PQ behandelte Bäume (P: 2, Q: 3)

Da die Werte von P und Q von der Struktur des Baums abhängen, werden die Werte von P und Q derzeit manuell abgestimmt, um den besten auszuwählen. Ich würde gerne wissen, ob dies automatisch eingestellt werden kann.

Erstellen Sie ein Profil, indem Sie die Wurzeln und Blätter wie unten gezeigt rekursiv verarbeiten.

Definition 6: Definieren Sie den pq-Gramm-Abstand wie folgt

\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})}

Der Grund für die Verdoppelung ist, dass die maximale Übereinstimmungsrate die Hälfte der Summe der beiden Bäume beträgt.

Unterschied zur Baumbearbeitungsentfernung

Bei PQ wird der Unterschied durch den Abstand zwischen den Profilen erfasst. Dies ist eine Annäherung, hat jedoch einige Vorteile gegenüber der Baumbearbeitungsentfernung.

In der Abbildung beträgt im Fall der Baumbearbeitungsentfernung die Bearbeitungsentfernung sowohl für T'als auch für T '' 2. Dies liegt daran, dass T'h nicht genug "g" - und "k" -Elemente hat und T "nicht genug" c "- und" e "-Elemente hat, so dass der Bearbeitungsabstand 2 im Vergleich zu T beträgt. T'und T '' sind jedoch in ihrer Struktur sehr unterschiedlich. Es ist nicht sehr gut, diesen Abstand als gleich zu behandeln. Im Fall von PQ ist der Unterschied klar. Dies ist der Unterschied zwischen dem Baumbearbeitungsabstand, der nur einzelne Unterschiede misst, und dem PQ-Bearbeitungsabstand, der den Gesamtunterschied misst.

HOW

Wir werden den Algorithmus unter Verwendung der obigen Definition einführen und ein Implementierungsbeispiel vorstellen.

Algorithmus

Erwägen Sie, es auf die folgende Baumstruktur anzuwenden.

Bereiten Sie zunächst zwei Schieberegister vor.

anc: p (für übergeordneten Knoten) sib: q (für untergeordnete Knoten)

Die Registerverarbeitung besteht darin, die alte herauszunehmen und die neue einzufügen.

Beispiel

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

Erstellen Sie ein pq-Gramm, indem Sie anc und sib kombinieren.

Basierend auf diesen wird das Profil des PQ-Gramms zurückgegeben.

anc Schritt zurück Geschwister wechselt von links nach rechts

Der Ablauf des spezifischen Algorithmus ist in der Abbildung dargestellt.

Die Zielbäume für diese Verarbeitung sind wie folgt.

In diesem Prozess möchten Sie ein Profil erstellen. Die Profilverarbeitung kann rekursiv beschrieben werden.

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

Initialisieren Sie zuerst das Profil. Füllen Sie anc mit "*". Übergeben Sie den Baum, für den Sie ein Profil für diese Zeit erstellen möchten, die festgelegten p- und q-Werte, das Profil, den Stammknoten des Baums und anc an die Funktion PROFILE.

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

Setzen Sie das Etikett r in anc ein. (R ist zunächst der Wurzelknoten, und der Knoten ändert sich aufgrund der rekursiven Verarbeitung.) Initialisiere sib. Wenn r ein Blatt ist, erstellen Sie eine Summe von Profilen, die anc und sib verketten Ist dies nicht der Fall, wird die Verarbeitung für jeden untergeordneten Knoten des Knotens durchgeführt. Bei der ersten Verarbeitung wird die Verarbeitung für jeden untergeordneten Knoten (a, b, c) mit a als Wurzelknoten durchgeführt.

Der erste Anc wird mit *, a festgelegt Fügen Sie die Sekunde in sib t *, *, a ein. Der Teil, auf den wir hier achten, ist der folgende Teil. Verketten Sie anc und sib, um *, a, *, *, a zu erstellen, und fügen Sie es zu PROFILE hinzu, um einen Summensatz zu erstellen.

Da es sich um einen rekursiven Prozess handelt, konzentrieren wir uns bei einem untergeordneten Knoten auf den folgenden Teil.

Bei der Verarbeitung für e mit anc als a, a

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

Bei der Verarbeitung von anc als "a, e"

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

Da es endlich die Blätter erreicht, addieren Sie die bisher festgelegte Summe. Wiederholen Sie diesen Vorgang rekursiv, um ein PQ-Profil zu erstellen.

Messen Sie den Abstand der Baumstruktur zwischen diesem Profil und dem zuvor definierten Abstand.

Die Werte von p und q sind Hyperparameter und hängen von der Baumstruktur ab. Es ist notwendig, die am besten geeigneten Parameter entsprechend der Struktur des Baums einzustellen.

Implementierungsmethode

--Erstellen eines Knotens für Baumstrukturdaten

• Shift Register zur Bearbeitung --PROFILE zum Bearbeiten der Entfernungsberechnung

Dies kann mit einer einfachen Implementierungsmethode erreicht werden.

Erstellen eines Knotens für Baumstrukturdaten

Es ist notwendig, die strukturierten Daten in eine Baumstruktur zu konvertieren und damit umzugehen. Ich habe es einfach mit dem folgenden Code erstellt

Initialisierungsprozess zum Festlegen einer Beschriftung für den Knoten Verarbeitung zum Hinzufügen untergeordneter Knoten zum Knoten

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

Schichtregister zur Bearbeitung

Geben Sie die Beschreibung von "Schieberegister" ein.

• Bereiten Sie eine mit * initialisierte Liste für die Größe des Arguments vor
• Die Liste wird mit einer Muschel kombiniert.
• Das älteste Element wird durch Verschiebungsverarbeitung entfernt und das durch das Argument angegebene Element hinzugefügt.

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

Es ist der Teil, der anc und sib erstellt und rekursiv PROFILE erstellt.

--Stellen Sie ShiftRegister für Vorfahren im Initialisierungsteil ein. --Erstellen Sie ein PROFIL mit den festgelegten Vorfahren.

• Sortieren Sie das erstellte PROFIL

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()

Dieser Teil ist ein wichtiger Prozess für die PQ-Entfernung.

• Legt die im Argument für Vorfahren angegebene Stammbezeichnung fest.
• Schieberegister für q Größe bei Geschwistern einstellen.
• Wenn die Anzahl der Kinder 0 wird, verketten Sie Vorfahren und Geschwister, um ein Profil zu erstellen.
• Fügen Sie Geschwistern ein Element für das Kind von root hinzu und klicken Sie auf. Dieser Vorgang wird rekursiv ausgeführt, bis keine Kinder mehr vorhanden sind.
• Wenn Sie zum jüngsten Kind gehen, füllen Sie die Geschwister darunter mit "*" aus.

    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))

Es wird der Teil der Entfernungsberechnung sein. Diese edit_distance berechnet den Abstand zwischen PROFILE und dem anderen als Argument. Wir berechnen die Übereinstimmungsrate der durch "Schnittmenge" erstellten Knotenelemente.

    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

Dies ist das Ende der Implementierung, aber Sie müssen sie testen, um sicherzustellen, dass sie ordnungsgemäß funktioniert.

Über Test

Der folgende Prozess prüft, ob die Profile gleich sind.

--Überprüfen Sie die Länge und geben Sie "False" zurück, wenn es anders ist, oder "False", wenn das erste Element anders ist

• Holen Sie sich Elemente aus dem Profil und geben Sie "False" zurück, wenn nicht jedes Element mit mindestens einem übereinstimmt

    
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

Grundeinstellungen für p und q. Zufällige Werteinstellung

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

Erstellen Sie einen Baum zum Testen

        # 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','*','*','*']]

Erstellen Sie einen zufälligen Baum und erstellen Sie ein Profil aus diesem Baum.

        # 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))

Erstellen Sie einen zufälligen Baum wie folgt.

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

Ich berechne, ob die Entfernungsberechnung korrekt ist

    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)

Wir prüfen, ob die Berechnung korrekt ist, auch wenn der Abstand zwischen A und B und das Gegenteil des Abstandes zwischen B und A umgekehrt sind.

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))

Überprüfen Sie, ob die Entfernungsberechnung zwischen 0 und 1 liegt

    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

Zusammenfassung

Der Vorteil dieser Methode ist, dass sie universell für strukturierte Daten verwendet werden kann. Da es sich um eine Methode handelt, die verwendet werden kann, wenn ein Datensatz in eine Baumstruktur wie HTML, JSON, XML usw. konvertiert werden kann, verfügt sie über eine breite Palette von Anwendungen, z. B. das Extrahieren der erforderlichen Daten und die Erkennung von Anomalien. Wir würden uns freuen, wenn Sie es versuchen könnten.

Referenz

Tree Edit Distance und Anwendung auf die Verarbeitung natürlicher Sprache Approximate Matching of Hierarc hical Data Using pq -Grams