Baumkerne: Quantifizierung der Ähnlichkeit zwischen baumstrukturierten Daten

Ein Netzwerk oder Graph ist eine Art strukturierter Daten in Form von Knoten , deren Beziehungen durch Links oder Kanten beschrieben werden. Knoten und Kanten in einem Diagramm können mehrere Attribute haben, die numerisch oder kategorisch oder sogar komplexer sein können.

Heutzutage ist eine riesige Datenmenge in Form von Netzwerken oder Graphen verfügbar. Beispielsweise das World Wide Web mit seinen Webseiten und Hyperlinks, soziale Netzwerke, semantische Netzwerke, biologische Netzwerke, Zitiernetzwerke für wissenschaftliche Literatur und so weiter.

Ein Baum ist eine spezielle Art von Diagramm und eignet sich natürlich zur Darstellung vieler Arten von Daten. Die Analyse von Bäumen ist ein wichtiges Gebiet in der Computer- und Datenwissenschaft. In diesem Artikel betrachten wir die Analyse der Linkstruktur in Bäumen. Insbesondere werden wir uns auf Baumkerne konzentrieren, eine Methode zum Vergleichen von Baumgraphen miteinander, die es uns ermöglicht, quantifizierbare Messungen ihrer Ähnlichkeiten oder Unterschiede zu erhalten. Dies ist ein wichtiger Prozess für viele moderne Anwendungen wie Klassifizierung und Datenanalyse.

Unüberwachte Klassifizierung strukturierter Daten

Die Klassifizierung ist ein wichtiger Bestandteil des maschinellen Lernens und der Datenanalyse. Im Allgemeinen kann die Klassifizierung entweder überwacht oder nicht überwacht werden. Bei der überwachten Klassifikation sind die Klassen bereits bekannt, und aus Trainingsdaten wird ein Klassifikationsmodell konstruiert, in dem die korrekten Klassen bereits angegeben sind. Im Gegensatz dazu versucht die unüberwachte Klassifizierung, Klassen zu identifizieren, wo keine bekannt sind, und gruppiert Daten in Kategorien, basierend auf einem Maß ihrer Ähnlichkeit.

Unüberwachte Klassifizierung kann mit Graphentheorie kombiniert werden, um Gruppen ähnlicher Baumnetzwerke zu identifizieren. Baumdatenstrukturen werden verwendet, um Objekte aus mehreren Domänen zu modellieren. Bei der Verarbeitung natürlicher Sprache (NLP) werden zum Beispiel Analysebäume als geordnete, gekennzeichnete Bäume modelliert. Beim automatisierten Schließen werden viele Probleme durch Suchen gelöst, wobei der Suchraum als Baum dargestellt wird, dessen Scheitelpunkte Suchzuständen zugeordnet sind und Kanten Folgerungsschritte darstellen. Auch halbstrukturierte Daten wie HTML- und XML-Dokumente können als geordnete, beschriftete Bäume modelliert werden.

Diese Bereiche können sinnvollerweise durch unüberwachte Klassifikationstechniken analysiert werden. In NLP kann die Klassifizierung verwendet werden, um eine Reihe von Sätzen automatisch in Fragen, Befehle und Aussagen zu gruppieren. Ebenso können Gruppen ähnlicher Websites identifiziert werden, indem Klassifizierungsmethoden auf ihre HTML-Quelle angewendet werden. In jedem dieser Fälle brauchen wir nur eine Möglichkeit zu messen, wie „ähnlich“ zwei Bäume einander sind.

Der Fluch der Dimensionalität

Die meisten Klassifizierungsalgorithmen erfordern, dass Daten in eine vektorisierte Form umgewandelt werden, die die Werte der Merkmale der Daten im Merkmalsraum darstellt , sodass die Daten im Merkmalsraum unter Verwendung linearer Algebra analysiert werden können. In strukturierten oder halbstrukturierten Daten wie Bäumen kann die Dimensionalität der resultierenden Vektoren (d. h. die Anzahl der Merkmale im Merkmalsraum) ziemlich hoch sein, da der Merkmalsraum Informationen über die Struktur bewahren muss.

Dies kann ein erheblicher Nachteil sein, wenn man bedenkt, dass viele Klassifizierungstechniken nicht in der Lage sind, effektiv mit der Dimensionalität der Eingabe zu skalieren. Mit anderen Worten, ihre Klassifikationskraft nimmt mit zunehmender Dimensionalität der Eingabe ab. Dieses Problem ist als Fluch der Dimensionalität bekannt.

Um eine Vorstellung von dem Grund für diese Leistungsverschlechterung zu bekommen, betrachten Sie einen Raum X der Dimension d . Angenommen, X enthält eine Menge gleichmäßig verteilter Punkte. Wenn die Anzahl der Dimensionen von X zunimmt, muss die Anzahl der Punkte, die erforderlich sind, um die gleiche Dichte beizubehalten, exponentiell zunehmen. Mit anderen Worten, je größer die Dimensionen der Eingabe sind, desto wahrscheinlicher ist es, dass diese Daten spärlich sind. Im Allgemeinen liefert ein spärlicher Datensatz nicht genügend Informationen, um einen guten Klassifikator zu erstellen, da Korrelationen zwischen Datenelementen zu schwach sind, um von Algorithmen erkannt zu werden.

Jeder obige Merkmalsraum enthält acht Datenpunkte. Auf dem eindimensionalen Raum ist es einfach, eine Gruppe von fünf Punkten auf der linken Seite und drei auf der rechten Seite zu identifizieren. Das Ausdehnen dieser Punkte über eine größere Anzahl von Merkmalen (dh Dimensionen) macht es schwieriger, diese Gruppen zu finden. In realen Anwendungen können Merkmalsräume leicht Hunderte von Dimensionen haben.

Eine vektorisierte Darstellung für strukturierte Daten ist geeignet, wenn Informationen über die Domäne effektiv verwendet werden können, um einen überschaubaren Satz von Merkmalen auszuwählen. Wenn solche Informationen nicht verfügbar sind, ist es wünschenswert, Techniken zu verwenden, die strukturierte Daten direkt verarbeiten können, ohne Operationen im Vektorraum durchzuführen.

Kernel-Methoden

Kernel-Methoden vermeiden die Notwendigkeit, Daten in Vektorform umzuwandeln. Die einzige Information, die sie benötigen, ist ein Maß für die Ähnlichkeit jedes Paars von Elementen in einem Datensatz. Diese Messung wird Kernel genannt, und die Funktion zu ihrer Bestimmung wird Kernelfunktion genannt . Kernmethoden suchen nach linearen Beziehungen im Merkmalsraum. Funktional sind sie äquivalent dazu, das Skalarprodukt von zwei Datenpunkten im Merkmalsraum zu nehmen, und tatsächlich kann das Merkmalsdesign immer noch ein nützlicher Schritt beim Kernel-Funktionsdesign sein. Kernmethoden vermeiden es jedoch, direkt im Merkmalsraum zu arbeiten, da gezeigt werden kann, dass es möglich ist, das Skalarprodukt durch eine Kernfunktion zu ersetzen, solange die Kernfunktion eine symmetrische, positiv semidefinite Funktion ist, die die Daten als Eingaben verwenden kann in seinem ursprünglichen Raum.

Der Vorteil der Verwendung von Kernel-Funktionen besteht somit darin, dass ein riesiger Merkmalsraum mit einer Rechenkomplexität analysiert werden kann, die nicht von der Größe des Merkmalsraums, sondern von der Komplexität der Kernel-Funktion abhängt, was bedeutet, dass Kernel-Methoden nicht unter dem Fluch leiden der Dimensionalität.

Wenn wir einen endlichen Datensatz betrachten, der aus n Beispielen besteht, können wir eine vollständige Darstellung der Ähnlichkeiten innerhalb der Daten erhalten, indem wir eine Kernel-Matrix erzeugen, deren Größe immer n × n ist. Diese Matrix ist unabhängig von der Größe jedes einzelnen Beispiels. Diese Eigenschaft ist nützlich, wenn ein kleiner Datensatz von Beispielen mit einem großen Merkmalsraum analysiert werden soll.

Im Allgemeinen basieren Kernel-Methoden auf einer anderen Antwort auf die Frage der Datenrepräsentation. Anstatt die Eingabepunkte in einen Merkmalsraum abzubilden, werden die Daten über paarweise Vergleiche in einer Kernmatrix K dargestellt, und alle relevanten Analysen können über die Kernmatrix durchgeführt werden.

Viele Data-Mining-Methoden können kernelisiert werden. Um baumstrukturierte Dateninstanzen mit Kernel-Methoden zu klassifizieren, beispielsweise mit Support Vector Machines, reicht es aus, eine gültige (symmetrisch positiv definite) Kernelfunktion k : T × T → R , auch als Baumkern bezeichnet, zu definieren. Beim Entwurf praktisch nützlicher Baumkerne würde man verlangen, dass sie in Polynomialzeit über die Größe des Baums berechenbar sind und in der Lage sind, isomorphe Graphen zu erkennen. Solche Baumkerne werden vollständige Baumkerne genannt.

Baumkerne

Lassen Sie uns nun einige nützliche Baumkerne zum Messen der Ähnlichkeit von Bäumen vorstellen. Die Hauptidee besteht darin, den Kern für jedes Baumpaar im Datensatz zu berechnen, um eine Kernmatrix zu erstellen, die dann zum Klassifizieren von Baumgruppen verwendet werden kann.

String-Kernel

Zuerst beginnen wir mit einer kurzen Einführung in String-Kernel, die uns helfen wird, eine andere Kernel-Methode vorzustellen, die auf der Umwandlung von Bäumen in Strings basiert.

Definieren wir num y (s) als die Anzahl der Vorkommen eines Teilstrings y in einem String s mit | s | bezeichnet die Länge der Saite. Der String-Kernel, den wir hier beschreiben werden, ist definiert als:

K -String (S 1 , S 2 ) = Σ s∈F num s (S 1 )num s (S 2 )w s

Wobei F der Satz von Teilketten ist, die sowohl in S 1 als auch in S 2 vorkommen, und der Parameter w s als ein Gewichtungsparameter dient (zum Beispiel, um wichtige Teilketten zu betonen). Wie wir sehen können, gibt dieser Kernel einem Paar von Strings einen höheren Wert, wenn sie viele gemeinsame Teilstrings teilen.

Baumkern basierend auf der Umwandlung von Bäumen in Strings

Wir können diesen String-Kernel verwenden, um einen Baumkern zu bauen. Die Idee hinter diesem Kernel besteht darin, zwei Bäume auf systematische Weise in zwei Strings umzuwandeln, die die Struktur des Baums kodieren, und dann den obigen String-Kernel darauf anzuwenden.

Wir wandeln die beiden Bäume wie folgt in zwei Strings um:

T bezeichne einen der Zielbäume, und label(n s ) sei die Zeichenkette des Knotens n s in T . tag(n s ) bezeichnet die String-Darstellung des Teilbaums von T mit Wurzel bei n s . Wenn also n root der Wurzelknoten von T ist, ist tag(n root ) die Zeichenfolgendarstellung des gesamten Baums T .

Als Nächstes bezeichne string(T) = tag(n root ) die Stringdarstellung von T . Wir werden die folgenden Schritte rekursiv von unten nach oben anwenden, um string(T) zu erhalten:

• Wenn der Knoten n s ein Blatt ist, setze tag(n s ) = „[“ + label(n s ) + „]“ (wobei + hier der String-Verkettungsoperator ist).
• Wenn der Knoten n s kein Blatt ist und c Kinder n 1 , n 2 , … , n c hat, sortiere tag(n 1 ), tag(n 2 ), … , tag(n c ) in lexikalischer Reihenfolge, um tag zu erhalten (n 1* ), tag(n 2* ), … , tag(n c* ) , und setze tag(n s ) = „[“ + label(n s ) + tag(n 1* ) + tag(n 2* ) + … + tag(n c* ) + „]“ .

Die folgende Abbildung zeigt ein Beispiel für diese Baum-zu-String-Konvertierung. Das Ergebnis ist eine Zeichenfolge, die mit einem öffnenden Trennzeichen wie „[“ beginnt und mit seinem schließenden Gegenstück „]“ endet, wobei jedes verschachtelte Trennzeichenpaar einem Teilbaum entspricht, der an einem bestimmten Knoten verwurzelt ist.

Nun können wir die obige Umwandlung auf zwei Bäume T 1 und T 2 anwenden, um zwei Zeichenketten S 1 und S 2 zu erhalten. Von dort aus können wir einfach den oben beschriebenen String-Kernel anwenden.

Der Baumkern zwischen T 1 und T 2 über zwei Strings S 1 und S 2 kann nun angegeben werden als:

K Baum (T 1 , T 2 ) = K String ( String(T 1 ), String(T 2 ) ) = K String (S 1 , S 2 ) = Σ s∈F num s (S 1 )num s (S 2 ) ws

In den meisten Anwendungen wird der Gewichtungsparameter zu w | s | , Gewichtung einer Teilzeichenfolge basierend auf ihrer Länge | s | . Typische Gewichtungsmethoden für w | s | sind:

• konstante Gewichtung ( w | s | = 1 )
• k -Spektrum-Gewichtung ( w | s | = 1 , wenn | s | = k , und w | s | = 0 sonst)
• Exponentialgewichtung ( w | s | = λ | s | wobei 0 ≤ λ ≤ 1 eine Abklingrate ist)

Um den Kernel zu berechnen, reicht es aus, alle gemeinsamen Teilstrings F zu bestimmen und zu zählen, wie oft sie in S 1 und S 2 vorkommen. Dieser zusätzliche Schritt des Auffindens gemeinsamer Teilketten ist ein gut untersuchtes Problem und kann in O( | S 1 | + | S 2 | ) unter Verwendung von Suffixbäumen oder Suffixarrays durchgeführt werden. Wenn wir davon ausgehen, dass die maximale Anzahl von Buchstaben (z. B. Bits, Bytes oder Zeichen), die zur Beschreibung des Labels eines Knotens benötigt werden, konstant ist, sind die Längen der konvertierten Zeichenfolgen | S1 | = O( | T 1 | ) und | S2 | = O( | T 2 | ) . Die Berechnungskomplexität zum Berechnen der Kernfunktion ist also O( | T 1 | + | T 2 | ) , was linear ist.

Baumkern basierend auf Unterpfaden

Der obige Baumkern verwendete einen horizontalen oder Breite-zuerst-Ansatz, um Bäume in Strings umzuwandeln. Obwohl dieser Ansatz recht einfach ist, bedeutet diese Konvertierung, dass er nicht direkt auf den Bäumen in ihrer ursprünglichen Form arbeiten kann.

Dieser Abschnitt wird einen Baumkern definieren, der auf den vertikalen Strukturen in Bäumen operiert, was es dem Kern ermöglicht, direkt auf dem Baum zu operieren.

Ein Unterabschnitt eines Pfads von der Wurzel zu einem der Blätter wird als Unterpfad bezeichnet, und eine Unterpfadmenge ist die Menge aller im Baum enthaltenen Unterpfade:

Nehmen wir an, wir wollen einen Baumkern K(T 1 , T 2 ) zwischen zwei Bäumen T 1 und T 2 definieren. Durch die Verwendung des Unterpfadsatzes können wir diesen Baumkern wie folgt definieren:

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

Wobei num p (T) die Häufigkeit ist, mit der der Teilpfad p im Baum T auftritt, | p | die Anzahl der Knoten im Teilpfad p ist und P die Menge aller Teilpfade in T 1 und T 2 ist. w | p | ist das Gewicht, ähnlich dem im vorherigen Abschnitt eingeführten.

Hier präsentieren wir eine einfache Implementierung dieses Kernels mit einer Tiefensuche. Obwohl dieser Algorithmus in quadratischer Zeit ausgeführt wird, existieren effizientere Algorithmen, die Suffixbäume oder Suffixarrays verwenden, oder eine Erweiterung des Multikey-Quicksort-Algorithmus, der im Durchschnitt eine linearithmische Zeit ( O( | T 1 | log | T 2 | ) ) erreichen kann:

 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

In diesem Beispiel haben wir den Gewichtungsparameter w | verwendet s | w | p | = 1 . Dadurch werden alle Teilpfade gleich gewichtet. Es gibt jedoch viele Fälle, in denen die Verwendung einer k -Spektrum-Gewichtung oder eines dynamisch zugewiesenen Gewichtungswerts angemessen ist.

Bergbau-Websites

Bevor wir zum Abschluss kommen, werfen wir einen kurzen Blick auf eine reale Anwendung der Baumklassifizierung: die Kategorisierung von Websites. In vielen Data-Mining-Kontexten ist es von Vorteil zu wissen, von welcher „Art“ von Website einige Daten stammen. Es stellt sich heraus, dass Seiten von verschiedenen Websites aufgrund von Ähnlichkeiten in der Strukturierung von Webseiten für ähnliche Dienste mithilfe von Bäumen recht effektiv kategorisiert werden können.

Wie machen wir das? HTML-Dokumente haben eine logisch verschachtelte Struktur, die einem Baum sehr ähnlich ist. Jedes Dokument enthält ein Stammelement, in dem zusätzliche Elemente verschachtelt sind. Verschachtelte Elemente in einem HTML-Tag sind logisch äquivalent zu untergeordneten Knoten dieses Tags:

Schauen wir uns einen Code an, der ein HTML-Dokument in einen Baum umwandeln kann:

 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

Dadurch wird eine Baumdatenstruktur erzeugt, die etwa so aussehen könnte:

Die obige Implementierung nutzt einige hilfreiche Python-Bibliotheken: NetworkX zum Arbeiten mit komplexen Diagrammstrukturen und Beautiful Soup zum Abrufen von Daten aus dem Web und Bearbeiten von Dokumenten.

Der Aufruf html_to_dom_tree(soup.find("body")) gibt ein NetworkX-Grafikobjekt zurück, das im <body> -Element der Webseite verwurzelt ist.

Angenommen, wir möchten Gruppen in einem Satz von 1.000 Website-Homepages finden. Indem wir jede Homepage auf diese Weise in einen Baum umwandeln, können wir sie vergleichen, indem wir beispielsweise den im vorherigen Abschnitt angegebenen Unterpfad-Baumkern verwenden. Mit diesen Ähnlichkeitsmessungen konnten wir beispielsweise feststellen, dass E-Commerce-Websites, Nachrichtenseiten, Blogs und Bildungsseiten leicht anhand ihrer Ähnlichkeit zueinander identifiziert werden können.

Fazit

In diesem Artikel haben wir Methoden zum Vergleichen von baumstrukturierten Datenelementen miteinander vorgestellt und gezeigt, wie man Kernel-Methoden auf Bäume anwendet, um eine quantifizierbare Messung ihrer Ähnlichkeit zu erhalten. Kernmethoden haben sich als ausgezeichnete Wahl erwiesen, wenn in hochdimensionalen Räumen gearbeitet wird, eine häufige Situation bei der Arbeit mit Baumstrukturen. Diese Techniken bilden die Grundlage für die weitere Analyse großer Baumgruppen unter Verwendung gut untersuchter Methoden, die über die Kernel-Matrix arbeiten.

Baumstrukturen werden in vielen Real-Word-Bereichen wie XML- und HTML-Dokumenten, chemischen Verbindungen, Verarbeitung natürlicher Sprache oder bestimmten Arten von Benutzerverhalten angetroffen. Wie am Beispiel der Konstruktion von Bäumen aus HTML demonstriert, befähigen uns diese Techniken, sinnvolle Analysen in diesen Bereichen durchzuführen.