Kernels de árvore: quantificando a semelhança entre dados estruturados em árvore

Uma rede ou grafo é um tipo de dado estruturado na forma de nós , com relacionamentos entre eles descritos por links ou arestas . Nós e arestas em um grafo podem ter vários atributos que podem ser numéricos ou categóricos, ou ainda mais complexos.

Hoje, uma enorme quantidade de dados está disponível na forma de redes ou gráficos. Por exemplo, a World Wide Web, com suas páginas e hiperlinks, redes sociais, redes semânticas, redes biológicas, redes de citação de literatura científica e assim por diante.

Uma árvore é um tipo especial de gráfico e é naturalmente adequada para representar muitos tipos de dados. A análise de árvores é um campo importante em ciência da computação e de dados. Neste artigo, veremos a análise da estrutura de links em árvores. Em particular, focaremos nos núcleos de árvores, um método para comparar gráficos de árvores entre si, permitindo obter medidas quantificáveis ​​de suas semelhanças ou diferenças. Este é um processo importante para muitas aplicações modernas, como classificação e análise de dados.

Classificação não supervisionada de dados estruturados

A classificação é um importante componente de aprendizado de máquina e análise de dados. Em geral, a classificação pode ser supervisionada ou não supervisionada . Na classificação supervisionada, as classes já são conhecidas, e um modelo de classificação é construído a partir de dados de treinamento em que as classes corretas já são dadas. A classificação não supervisionada, por outro lado, tenta identificar classes onde nenhuma é conhecida, agrupando os dados em categorias com base em alguma medida de sua similaridade.

A classificação não supervisionada pode ser combinada com a teoria dos grafos para identificar grupos de redes de árvores semelhantes. Estruturas de dados em árvore são empregadas para modelar objetos de vários domínios. No processamento de linguagem natural (NLP), por exemplo, as árvores de análise sintática são modeladas como árvores ordenadas e rotuladas. No raciocínio automatizado, muitos problemas são resolvidos por busca, onde o espaço de busca é representado como uma árvore cujos vértices estão associados a estados de busca e as arestas representam etapas de inferência. Além disso, dados semiestruturados, como documentos HTML e XML, podem ser modelados como árvores ordenadas e rotuladas.

Esses domínios podem ser analisados ​​de maneira útil por meio de técnicas de classificação não supervisionadas. Na PNL, a classificação pode ser usada para agrupar automaticamente um conjunto de frases em perguntas, comandos e declarações. Da mesma forma, grupos de sites semelhantes podem ser identificados aplicando métodos de classificação à sua fonte HTML. Em cada um desses casos, tudo o que precisamos é uma maneira de medir o quão “semelhantes” duas árvores são entre si.

A Maldição da Dimensionalidade

A maioria dos algoritmos de classificação requer que os dados sejam transformados em uma forma vetorizada, representando os valores das feições dos dados no espaço de feições, para que os dados possam ser analisados ​​no espaço de feições usando álgebra linear. Em dados estruturados ou semiestruturados, como árvores, a dimensionalidade dos vetores resultantes (ou seja, o número de feições no espaço de feições) pode ser bastante alta, pois o espaço de feições deve preservar informações sobre a estrutura.

Isso pode ser uma desvantagem significativa, considerando que muitas técnicas de classificação não são capazes de escalar efetivamente com a dimensionalidade da entrada. Em outras palavras, seu poder de classificação diminui com o aumento da dimensionalidade da entrada. Este problema é conhecido como a maldição da dimensionalidade.

Para se ter uma ideia do motivo dessa degradação de desempenho, considere um espaço X de dimensão d . Suponha que X contenha um conjunto de pontos uniformemente distribuídos. Se o número de dimensões de X aumenta, o número de pontos necessários para manter a mesma densidade deve aumentar exponencialmente. Em outras palavras, quanto mais dimensões da entrada, maior a probabilidade de que os dados sejam esparsos. Em geral, um conjunto de dados esparso não fornece informações suficientes para construir um bom classificador porque as correlações entre os elementos de dados são muito fracas para os algoritmos detectarem.

Cada espaço de recurso acima contém oito pontos de dados. No espaço unidimensional, é fácil identificar um grupo de cinco pontos à esquerda e três à direita. Esticar esses pontos em um número maior de recursos (ou seja, dimensões) torna mais difícil encontrar esses grupos. Em aplicações reais, os espaços de recursos podem facilmente ter centenas de dimensões.

Uma representação vetorizada para dados estruturados é apropriada quando as informações sobre o domínio podem ser usadas efetivamente para selecionar um conjunto gerenciável de recursos. Quando tal informação não estiver disponível, é desejável fazer uso de técnicas que possam manipular dados estruturados diretamente, sem realizar operações no espaço vetorial.

Métodos do kernel

Os métodos de kernel evitam a necessidade de converter dados em formato vetorial. A única informação que eles exigem é uma medida da similaridade de cada par de itens em um conjunto de dados. Essa medida é chamada de kernel , e a função para determiná-la é chamada de função de kernel . Os métodos de kernel procuram relações lineares no espaço de recursos. Funcionalmente, eles são equivalentes a obter o produto escalar de dois pontos de dados no espaço de recursos e, de fato, o design de recursos ainda pode ser uma etapa útil no design de funções do kernel. No entanto, os métodos dos métodos do kernel evitam operar diretamente no espaço de recursos, pois pode ser mostrado que é possível substituir o produto escalar por uma função do kernel, desde que a função do kernel seja uma função semidefinida positiva e simétrica que possa receber como entradas os dados em seu espaço original.

A vantagem de usar funções do kernel é que um enorme espaço de recursos pode ser analisado com uma complexidade computacional não dependente do tamanho do espaço de recursos, mas da complexidade da função do kernel, o que significa que os métodos do kernel não sofrem a maldição de dimensionalidade.

Se considerarmos um conjunto de dados finito composto por n exemplos, podemos obter uma representação completa das semelhanças dentro dos dados gerando uma matriz kernel cujo tamanho é sempre n × n . Esta matriz é independente do tamanho de cada exemplo individual. Essa propriedade é útil quando um pequeno conjunto de dados de exemplos com um grande espaço de recursos deve ser analisado.

Em geral, os métodos do kernel são baseados em uma resposta diferente para a questão da representação de dados. Em vez de mapear os pontos de entrada em um espaço de recursos, os dados são representados por meio de comparações em pares em uma matriz de kernel K e todas as análises relevantes podem ser realizadas sobre a matriz de kernel.

Muitos métodos de mineração de dados podem ser kernelizados. Para classificar instâncias de dados estruturados em árvore com métodos de kernel, como com máquinas de vetor de suporte, basta definir uma função de kernel válida (definida positiva simétrica) k : T × T → R , também chamada de kernel de árvore . No projeto de kernels de árvore praticamente úteis, seria necessário que eles fossem computáveis ​​em tempo polinomial sobre o tamanho da árvore e fossem capazes de detectar grafos isomórficos. Esses kernels de árvore são chamados de kernels de árvore completos .

Núcleos de árvores

Agora, vamos apresentar alguns kernels de árvore úteis para medir a similaridade de árvores. A ideia principal é calcular o kernel para cada par de árvores no conjunto de dados para construir uma matriz de kernel, que pode ser usada para classificar conjuntos de árvores.

Kernel de String

Primeiro, começaremos com uma breve introdução aos kernels de strings, o que nos ajudará a introduzir outro método de kernel baseado na conversão de árvores em strings.

Vamos definir num y (s) como o número de ocorrências de uma substring y em uma string s , com | s | denotando o comprimento da corda. O kernel de string que descreveremos aqui é definido como:

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

Onde F é o conjunto de substrings que ocorrem em S 1 e S 2 , e o parâmetro w s serve como parâmetro de peso (por exemplo, para enfatizar substrings importantes). Como podemos ver, esse kernel dá um valor mais alto a um par de strings quando elas compartilham muitas substrings comuns.

Kernel de árvore baseado na conversão de árvores em strings

Podemos usar este kernel de string para construir um kernel de árvore. A ideia por trás desse kernel é converter duas árvores em duas strings de forma sistemática que codifique a estrutura da árvore e, em seguida, aplicar o kernel de string acima a elas.

Convertemos as duas árvores em duas strings da seguinte forma:

Seja T uma das árvores alvo e rotule(n s ) o rótulo da string do nó n s em T . tag(n s ) denota a representação string da subárvore de T enraizada em n s . Portanto, se n root é o nó raiz de T , tag(n root ) é a representação em string de toda a árvore T .

Em seguida, deixe string(T) = tag(n root ) denotar a representação string de T . Vamos aplicar recursivamente os seguintes passos de baixo para cima para obter string(T) :

• Se o nó n s for uma folha, deixe tag(n s ) = “[” + label(n s ) + “]” (onde + aqui é o operador de concatenação de strings).
• Se o nó n s não for uma folha e tiver c filhos n 1 , n 2 , … , nc , ordenar tag(n 1 ), tag(n 2 ), … , tag(n c ) em ordem lexical para obter tag (n 1* ), tag(n 2* ), … , tag(n c* ) e let tag(n s ) = “[” + label(n s ) + tag(n 1* ) + tag(n 2* ) + … + etiqueta(n c* ) + “]” .

A figura abaixo mostra um exemplo dessa conversão de árvore para string. O resultado é uma string começando com um delimitador de abertura como “[” e terminando com sua contraparte de fechamento, “]”, com cada par de delimitadores aninhados correspondendo a uma subárvore enraizada em um nó específico.

Agora podemos aplicar a conversão acima a duas árvores, T 1 e T 2 , para obter duas strings S 1 e S 2 . A partir daí, podemos simplesmente aplicar o kernel de string descrito acima.

O kernel da árvore entre T 1 e T 2 através de duas strings S 1 e S 2 agora pode ser dado como:

K tree (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 ) w s

Na maioria das aplicações, o parâmetro de peso torna-se w | s | , ponderando uma substring com base em seu comprimento | s | . Métodos típicos de ponderação para w | s | está:

• ponderação constante ( w | s | = 1 )
• ponderação do espectro k ( w | s | = 1 se | s | = k , e w | s | = 0 caso contrário)
• ponderação exponencial ( w | s | = λ | s | onde 0 ≤ λ ≤ 1 é uma taxa de decaimento)

Para calcular o kernel, é suficiente determinar todas as substrings comuns F e contar o número de vezes que elas ocorrem em S 1 e S 2 . Essa etapa adicional de encontrar substrings comuns é um problema bem estudado e pode ser realizado em O( | S 1 | + | S 2 | ) , empregando árvores de sufixos ou matrizes de sufixos. Se assumirmos que o número máximo de letras (bits, bytes ou caracteres, por exemplo) necessário para descrever o rótulo de um nó é constante, os comprimentos das strings convertidas são | S 1 | = O( | T 1 | ) e | S 2 | = O( | T 2 | ) . Assim, a complexidade computacional de calcular a função kernel é O( | T 1 | + | T 2 | ) , que é linear.

Kernel de árvore baseado em subcaminhos

O kernel da árvore acima usou uma abordagem horizontal, ou em largura, para converter árvores em strings. Embora essa abordagem seja bastante simples, essa conversão significa que ela não pode operar diretamente nas árvores em sua forma original.

Esta seção definirá um kernel de árvore que opera nas estruturas verticais em árvores, permitindo que o kernel opere diretamente na árvore.

Uma subseção de um caminho da raiz até uma das folhas é chamada de subcaminho e um conjunto de subcaminhos é o conjunto de todos os subcaminhos incluídos na árvore:

Vamos supor que queremos definir um kernel de árvore K(T 1 , T 2 ) entre duas árvores T 1 e T 2 . Usando o conjunto de subcaminhos, podemos definir este kernel de árvore como:

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

Onde num p (T) é o número de vezes que o subcaminho p ocorre na árvore T , | p | é o número de nós no subcaminho p , e P é o conjunto de todos os subcaminhos em T 1 e T 2 . w | p | é o peso, semelhante ao apresentado na seção anterior.

Aqui, apresentamos uma implementação simples deste kernel usando uma busca em profundidade. Embora esse algoritmo seja executado em tempo quadrático, existem algoritmos mais eficientes usando árvores de sufixos ou matrizes de sufixos, ou uma extensão do algoritmo de classificação rápida multichave, que pode atingir tempo linearítmico ( O( | T 1 | log | T 2 | ) ) em média:

 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

Neste exemplo, usamos o parâmetro de ponderação w | s | w | p | = 1 . Isso dá a todos os subcaminhos uma ponderação igual. No entanto, há muitos casos em que o uso de ponderação de espectro k , ou algum valor de peso atribuído dinamicamente, é apropriado.

Sites de mineração

Antes de encerrarmos, vamos examinar brevemente uma aplicação real da classificação em árvore: a categorização de sites. Em muitos contextos de mineração de dados, é benéfico saber de que “tipo” de site alguns dados vêm. Acontece que as páginas de diferentes sites podem ser categorizadas de forma bastante eficaz usando árvores devido às semelhanças na forma como as páginas da Web para serviços semelhantes são estruturadas.

Como fazemos isso? Os documentos HTML têm uma estrutura lógica aninhada, que é muito parecida com uma árvore. Cada documento contém um elemento raiz, com elementos adicionais aninhados dentro. Elementos aninhados em uma tag HTML são logicamente equivalentes aos nós filhos dessa tag:

Vamos dar uma olhada em alguns códigos que podem converter um documento HTML em uma árvore:

 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

Isso produzirá uma estrutura de dados em árvore que pode se parecer com isso:

A implementação acima faz uso de algumas bibliotecas Python úteis: NetworkX, para trabalhar com estruturas gráficas complexas, e Beautiful Soup, para extrair dados da web e manipular documentos.

Chamar html_to_dom_tree(soup.find("body")) retornará um objeto de gráfico NetworkX enraizado no elemento <body> da página da web.

Digamos que queremos encontrar grupos em um conjunto de 1.000 páginas iniciais de sites. Ao converter cada página inicial em uma árvore como essa, podemos comparar cada uma delas, por exemplo, usando o kernel da árvore de subcaminho fornecido na seção anterior. Com essas medidas de similaridade, poderíamos descobrir que, por exemplo, sites de comércio eletrônico, sites de notícias, blogs e sites educacionais são facilmente identificados por sua semelhança entre si.

Conclusão

Neste artigo, apresentamos métodos para comparar elementos de dados estruturados em árvore entre si e mostramos como aplicar métodos de kernel a árvores para obter uma medida quantificável de sua similaridade. Os métodos de kernel provaram ser uma excelente escolha ao operar em espaços de alta dimensão, uma situação comum ao trabalhar com estruturas em árvore. Essas técnicas preparam o cenário para uma análise mais aprofundada de grandes conjuntos de árvores, usando métodos bem estudados que operam sobre a matriz do kernel.

Estruturas de árvore são encontradas em muitas áreas de palavras reais, como documentos XML e HTML, compostos químicos, processamento de linguagem natural ou certos tipos de comportamento de usuários. Conforme demonstrado no exemplo de construção de árvores a partir de HTML, essas técnicas nos capacitam a realizar análises significativas nesses domínios.