Jądra drzew: ilościowe określanie podobieństwa danych o strukturze drzewa

Sieć lub wykres to rodzaj uporządkowanych danych w postaci węzłów , a relacje między nimi są opisane przez łącza lub krawędzie . Węzły i krawędzie grafu mogą mieć kilka atrybutów, które mogą być liczbowe lub kategoryczne, a nawet bardziej złożone.

Dziś ogromna ilość danych jest dostępna w postaci sieci lub wykresów. Na przykład sieć WWW z jej stronami internetowymi i hiperłączami, sieciami społecznościowymi, sieciami semantycznymi, sieciami biologicznymi, sieciami cytowania literatury naukowej i tak dalej.

Drzewo to specjalny rodzaj wykresu, który naturalnie nadaje się do reprezentowania wielu typów danych. Analiza drzew jest ważną dziedziną informatyki i nauki o danych. W tym artykule przyjrzymy się analizie struktury linków w drzewach. W szczególności skupimy się na jądrach drzew, metodzie porównywania ze sobą grafów drzew, która pozwala nam uzyskać wymierne pomiary ich podobieństw lub różnic. Jest to ważny proces dla wielu nowoczesnych aplikacji, takich jak klasyfikacja i analiza danych.

Nienadzorowana klasyfikacja danych strukturalnych

Klasyfikacja jest ważnym komponentem uczenia maszynowego i analizy danych. Ogólnie klasyfikacja może być nadzorowana lub nienadzorowana . W klasyfikacji nadzorowanej klasy są już znane, a model klasyfikacji konstruowany jest z danych uczących, w których podane są już poprawne klasy. Natomiast klasyfikacja nienadzorowana próbuje zidentyfikować klasy, których nie są znane, grupując dane w kategorie w oparciu o pewną miarę ich podobieństwa.

Nienadzorowaną klasyfikację można połączyć z teorią grafów w celu zidentyfikowania grup podobnych sieci drzew. Drzewne struktury danych są wykorzystywane do modelowania obiektów z kilku domen. Na przykład w przetwarzaniu języka naturalnego (NLP) drzewa analizy są modelowane jako uporządkowane, oznaczone drzewami. W zautomatyzowanym wnioskowaniu wiele problemów rozwiązuje się przez wyszukiwanie, w którym przestrzeń poszukiwań jest reprezentowana jako drzewo, którego wierzchołki są skojarzone ze stanami wyszukiwania, a krawędzie reprezentują kroki wnioskowania. Ponadto dane częściowo ustrukturyzowane, takie jak dokumenty HTML i XML, można modelować jako uporządkowane drzewa z etykietami.

Domeny te mogą być użytecznie analizowane za pomocą nienadzorowanych technik klasyfikacji. W NLP klasyfikacja może być używana do automatycznego grupowania zbioru zdań w pytania, polecenia i stwierdzenia. Podobnie grupy podobnych witryn można zidentyfikować, stosując metody klasyfikacji do ich źródła HTML. W każdym z tych przypadków wystarczy nam sposób na zmierzenie, jak „podobne” są do siebie dwa drzewa.

Klątwa Wymiarowości

Większość algorytmów klasyfikacji wymaga przekształcenia danych do postaci wektorowej, reprezentującej wartości cech danych w przestrzeni cech , tak aby dane mogły być analizowane w przestrzeni cech przy użyciu algebry liniowej. W danych ustrukturyzowanych lub częściowo ustrukturyzowanych, takich jak drzewa, wymiarowość wektorów wynikowych (tj. liczba cech w przestrzeni cech) może być dość wysoka, ponieważ przestrzeń cech musi zachowywać informacje o strukturze.

Może to być poważną wadą, biorąc pod uwagę, że wiele technik klasyfikacji nie jest w stanie skutecznie skalować z wymiarowością danych wejściowych. Innymi słowy, ich moc klasyfikacyjna maleje wraz ze wzrostem wymiarowości wejścia. Ten problem jest znany jako przekleństwo wymiarowości.

Aby zorientować się w przyczynie tego pogorszenia wydajności, rozważ przestrzeń X o wymiarze d . Załóżmy, że X zawiera zbiór punktów równomiernie rozłożonych. Jeśli liczba wymiarów X wzrasta, liczba punktów niezbędnych do zachowania tej samej gęstości musi rosnąć wykładniczo. Innymi słowy, im więcej wymiarów danych wejściowych, tym większe prawdopodobieństwo, że dane są rzadkie. Ogólnie rzecz biorąc, rzadki zbiór danych nie zapewnia wystarczającej ilości informacji do zbudowania dobrego klasyfikatora, ponieważ korelacje między elementami danych są zbyt słabe, aby algorytmy mogły je wykryć.

Każdy obszar funkcji powyżej zawiera osiem punktów danych. Na przestrzeni jednowymiarowej łatwo zidentyfikować grupę pięciu punktów po lewej i trzech po prawej. Rozciągnięcie tych punktów na większą liczbę cech (tj. wymiarów) utrudnia znalezienie tych grup. W rzeczywistych zastosowaniach przestrzenie funkcji mogą z łatwością mieć setki wymiarów.

Wektorowa reprezentacja danych strukturalnych jest odpowiednia, gdy informacje o domenie można skutecznie wykorzystać do wybrania łatwego do zarządzania zestawu funkcji. Gdy takie informacje nie są dostępne, warto skorzystać z technik, które mogą bezpośrednio obsługiwać dane strukturalne, bez wykonywania operacji w przestrzeni wektorowej.

Metody jądra

Metody jądra pozwalają uniknąć konwersji danych do postaci wektorowej. Jedyną informacją, jakiej potrzebują, jest pomiar podobieństwa każdej pary elementów w zbiorze danych. Ten pomiar nazywa się jądrem , a funkcja jego określania nazywa się funkcją jądra . Metody jądra poszukują relacji liniowych w przestrzeni cech. Funkcjonalnie są one równoważne z iloczynem skalarnym dwóch punktów danych w przestrzeni cech i rzeczywiście projektowanie cech może nadal być użytecznym krokiem w projektowaniu funkcji jądra. Jednak metody metod jądra unikają bezpośredniego działania na przestrzeni cech, ponieważ można wykazać, że możliwe jest zastąpienie iloczynu skalarnego funkcją jądra, o ile funkcja jądra jest symetryczną, dodatnią funkcją półokreśloną, która może przyjmować jako dane wejściowe w swojej pierwotnej przestrzeni.

Zaletą korzystania z funkcji jądra jest zatem to, że ogromna przestrzeń cech może być analizowana ze złożonością obliczeniową niezależną od wielkości przestrzeni cech, ale od złożoności funkcji jądra, co oznacza, że ​​metody jądra nie są narażone na przekleństwo wymiarowości.

Jeśli rozważymy skończony zbiór danych złożony z n przykładów, możemy uzyskać pełną reprezentację podobieństw w danych, generując macierz jądra, której rozmiar jest zawsze n × n . Ta macierz jest niezależna od wielkości każdego indywidualnego przykładu. Ta właściwość jest przydatna, gdy ma być analizowany mały zbiór przykładów z dużą przestrzenią funkcji.

Ogólnie rzecz biorąc, metody jądra opierają się na innej odpowiedzi na pytanie o reprezentację danych. Zamiast mapowania punktów wejściowych do przestrzeni cech, dane są reprezentowane przez porównania parami w macierzy jądra K , a wszystkie istotne analizy można przeprowadzić na macierzy jądra.

Wiele metod eksploracji danych można poddać kernelowi. Aby sklasyfikować instancje danych o strukturze drzewa za pomocą metod jądra, takich jak maszyny wektorów nośnych, wystarczy zdefiniować prawidłową (symetryczną dodatnio określoną) funkcję jądra k : T × T → R , zwaną także jądrem drzewa . Przy projektowaniu praktycznie użytecznych jąder drzew wymagałoby się, aby były one obliczalne w czasie wielomianowym na wielkości drzewa i byłyby w stanie wykrywać grafy izomorficzne. Takie jądra drzewa nazywane są kompletnymi jądrami drzewa.

Jądra drzew

Teraz przedstawmy kilka przydatnych jąder drzew do mierzenia podobieństwa drzew. Główną ideą jest obliczenie jądra dla każdej pary drzew w zbiorze danych w celu zbudowania macierzy jądra, która może być następnie wykorzystana do klasyfikacji zbiorów drzew.

Jądro ciągów

Najpierw zaczniemy od krótkiego wprowadzenia do jądra łańcuchowego, które pomoże nam wprowadzić inną metodę jądra, która opiera się na konwersji drzew na łańcuchy.

Zdefiniujmy liczbę y (s) jako liczbę wystąpień podłańcucha y w ciągu s , przy czym | s | oznaczający długość sznurka. Jądro napisowe, które tutaj opiszemy, jest zdefiniowane jako:

K string (S 1 , S 2 ) = Σ s∈F liczba s (S 1 )liczba s (S 2 )w s

Gdzie F jest zbiorem podciągów występujących zarówno w S 1 , jak i S 2 , a parametr w s służy jako parametr wagi (na przykład w celu podkreślenia ważnych podciągów). Jak widać, to jądro nadaje wyższą wartość parze łańcuchów, gdy mają one wiele wspólnych podciągów.

Jądro drzewa oparte na konwersji drzew na ciągi

Możemy użyć tego jądra łańcuchowego do zbudowania jądra drzewa. Ideą tego jądra jest przekształcenie dwóch drzew w dwa łańcuchy w systematyczny sposób, który koduje strukturę drzewa, a następnie zastosowanie do nich powyższego jądra łańcuchowego.

Konwertujemy dwa drzewa w dwa ciągi w następujący sposób:

Niech T oznacza jedno z drzew docelowych, a label(ns ) etykietę łańcuchową węzła n s w T . tag(n s ) oznacza łańcuchową reprezentację poddrzewa T zakorzenionego w n s . Zatem jeśli n root jest węzłem głównym T , tag(n root ) jest ciągiem reprezentującym całe drzewo T .

Następnie niech string(T) = tag(n root ) oznacza łańcuchową reprezentację T . Aby otrzymać string(T) , zastosujemy rekurencyjnie następujące kroki w sposób oddolny:

• Jeśli węzeł n s jest liściem, niech tag(n s ) = „[” + label(n s ) + „]” (gdzie + to operator konkatenacji ciągów).
• Jeśli węzeł n s nie jest liściem i ma c dzieci n 1 , n 2 , … , n c , sortuj tag(n 1 ), tag(n 2 ), … , tag(n c ) w kolejności leksykalnej, aby uzyskać tag (n 1* ), tag(n 2* ), … , tag(n c* ) i niech tag(n s ) = „[” + label(n s ) + tag(n 1* ) + tag(n 2* ) + … + tag(n c* ) + „]” .

Poniższy rysunek przedstawia przykład konwersji drzewa na łańcuch. Wynikiem jest łańcuch rozpoczynający się ogranicznikiem otwierającym, takim jak „[” i kończący się jego odpowiednikiem zamykającym, „]”, z każdą zagnieżdżoną parą ograniczników odpowiadającą poddrzewie zakorzenionemu w określonym węźle.

Teraz możemy zastosować powyższą konwersję do dwóch drzew, T 1 i T 2 , aby otrzymać dwa łańcuchy S 1 i S 2 . Stamtąd możemy po prostu zastosować jądro łańcuchowe opisane powyżej.

Jądro drzewa między T 1 i T 2 poprzez dwa łańcuchy S 1 i S 2 można teraz podać jako:

Drzewo K (T 1 , T 2 ) = K string ( string(T 1 ), string(T 2 ) ) = K string (S 1 , S 2 ) = Σ s∈F liczba s (S 1 )liczba ( S 2 ) w s

W większości zastosowań parametr wagi staje się w | s | , ważenie podciągu na podstawie jego długości | s | . Typowe metody ważenia dla w | s | są:

• stałe ważenie ( w | s | = 1 )
• ważenie widma k ( w | s | = 1 jeśli | s | = k , oraz w | s | = 0 w przeciwnym razie)
• ważenie wykładnicze ( w | s | = λ | s | gdzie 0 ≤ λ ≤ 1 to szybkość zanikania)

Aby obliczyć jądro, wystarczy określić wszystkie wspólne podciągi F i policzyć, ile razy występują w S 1 i S 2 . Ten dodatkowy krok polegający na znalezieniu wspólnych podciągów jest dobrze zbadanym problemem i można go wykonać w O( | S 1 | + | S 2 | ) , używając drzew sufiksów lub tablic sufiksów. Jeśli założymy, że maksymalna liczba liter (na przykład bitów, bajtów lub znaków) potrzebnych do opisania etykiety węzła jest stała, długości konwertowanych ciągów są | S 1 | = O( | T 1 | ) i | S 2 | = O( | T 2 | ) . Zatem złożoność obliczeniowa obliczania funkcji jądra wynosi O( | T 1 | + | T 2 | ) , co jest liniowe.

Jądro drzewa oparte na podścieżkach

Jądro drzewa powyżej używało podejścia poziomego lub wszerz do konwersji drzew na łańcuchy. Chociaż to podejście jest dość proste, ta konwersja oznacza, że ​​nie może działać bezpośrednio na drzewach w ich oryginalnej formie.

Ta sekcja zdefiniuje jądro drzewa, które operuje na pionowych strukturach w drzewach, pozwalając jądru operować bezpośrednio na drzewie.

Podsekcja ścieżki od korzenia do jednego z liści nazywana jest podścieżką , a zbiór podścieżek to zbiór wszystkich podścieżek zawartych w drzewie:

Załóżmy, że chcemy zdefiniować jądro drzewa K(T 1 , T 2 ) pomiędzy dwoma drzewami T 1 i T 2 . Używając zestawu podścieżek, możemy zdefiniować to jądro drzewa jako:

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

Gdzie num p (T) to liczba wystąpień podścieżki p w drzewie T , | p | to liczba węzłów w podścieżce p , a P to zbiór wszystkich podścieżek w T 1 i T 2 . w | p | to waga, podobna do wprowadzonej w poprzedniej sekcji.

Tutaj przedstawiamy prostą implementację tego jądra przy użyciu wyszukiwania w głąb. Chociaż ten algorytm działa w czasie kwadratowym, istnieją bardziej wydajne algorytmy przy użyciu drzew sufiksów lub tablic sufiksów lub rozszerzenia wielokluczowego algorytmu szybkiego sortowania, który może osiągnąć średnio czas liniowo-rytmiczny ( O( | T 1 | log | T 2 | ) ):

 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

W tym przykładzie użyliśmy parametru ważenia w | s | w | p | = 1 . Dzięki temu wszystkie podścieżki mają równą wagę. Jednak istnieje wiele przypadków, w których użycie ważenia k -spektrum lub jakiejś dynamicznie przypisanej wartości wagi jest właściwe.

Strony górnicze

Zanim zakończymy, spójrzmy pokrótce na jedno rzeczywiste zastosowanie klasyfikacji drzew: kategoryzacja stron internetowych. W wielu kontekstach eksploracji danych warto wiedzieć, z jakiego „typu” strony internetowej pochodzą niektóre dane. Okazuje się, że strony z różnych witryn można dość skutecznie kategoryzować za pomocą drzew, ze względu na podobieństwa w strukturze stron internetowych podobnych usług.

Jak to zrobimy? Dokumenty HTML mają logiczną strukturę zagnieżdżoną, która bardzo przypomina drzewo. Każdy dokument zawiera jeden element główny, w którym zagnieżdżone są dodatkowe elementy. Elementy zagnieżdżone w znaczniku HTML są logicznie równoważne węzłom podrzędnym tego znacznika:

Rzućmy okiem na kod, który może przekonwertować dokument HTML na drzewo:

 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

Spowoduje to utworzenie struktury drzewa danych, która może wyglądać mniej więcej tak:

Powyższa implementacja wykorzystuje kilka pomocnych bibliotek Pythona: NetworkX do pracy ze złożonymi strukturami wykresów oraz Beautiful Soup do pobierania danych z sieci i manipulowania dokumentami.

Wywołanie html_to_dom_tree(soup.find("body")) zwróci obiekt wykresu NetworkX zakorzeniony w elemencie <body> strony internetowej.

Załóżmy, że chcemy znaleźć grupy w zestawie 1000 stron głównych witryn. Konwertując każdą stronę główną w drzewo takie jak to, możemy je porównać, na przykład używając jądra drzewa podścieżek podanego w poprzedniej sekcji. Dzięki tym pomiarom podobieństwa możemy stwierdzić, że na przykład witryny handlu elektronicznego, witryny z wiadomościami, blogi i witryny edukacyjne można łatwo zidentyfikować na podstawie ich wzajemnego podobieństwa.

Wniosek

W tym artykule przedstawiliśmy metody porównywania ze sobą elementów danych o strukturze drzewa i pokazaliśmy, jak zastosować metody jądra do drzew, aby uzyskać wymierny pomiar ich podobieństwa. Metody jądra okazały się doskonałym wyborem podczas pracy w przestrzeniach wielowymiarowych, co jest częstą sytuacją przy pracy ze strukturami drzewiastymi. Techniki te przygotowują grunt pod dalszą analizę dużych zbiorów drzew przy użyciu dobrze zbadanych metod operujących na macierzy jądra.

Struktury drzewiaste są spotykane w wielu rzeczywistych obszarach, takich jak dokumenty XML i HTML, związki chemiczne, przetwarzanie języka naturalnego lub niektóre typy zachowań użytkowników. Jak pokazano na przykładzie konstruowania drzew z HTML, techniki te umożliwiają nam przeprowadzanie sensownej analizy w tych domenach.