Ciência De Dados E Bancos De Dados
Kernels de árvore: quantificando similaridade entre dados estruturados em árvore
PARA rede ou gráfico é um tipo de dados estruturados na forma de nós , com relacionamentos entre eles descritos por links, ou arestas . Nós e arestas em um gráfico podem ter vários atributos que podem ser numéricos ou categóricos, ou até mais complexos.
Hoje, uma grande quantidade de dados está disponível na forma de redes ou gráficos. Por exemplo, a World Wide Web, com suas páginas da web e hiperlinks, redes sociais, redes semânticas, redes biológicas, redes de citações para literatura científica e assim por diante.
PARA árvore é um tipo especial de gráfico e é naturalmente adequado para representar muitos tipos de dados. A análise de árvores é um campo importante na ciência da computação e dados. Neste artigo, veremos a análise da estrutura de links em árvores. Em particular, vamos nos concentrar nos kernels das árvores, um método para comparar gráficos de árvores entre si, permitindo-nos 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
Classificação é um componente importante aprendizado de máquina e análise de dados . Em geral, a classificação pode ser supervisionado ou não supervisionado . 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á foram dadas. A classificação não supervisionada, por outro lado, tenta identificar classes onde nenhuma é conhecida, agrupando 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 (PNL), por exemplo, as árvores de análise são modeladas como árvores ordenadas e rotuladas. No raciocínio automatizado, muitos problemas são resolvidos por pesquisa, onde o espaço de pesquisa é representado como uma árvore cujos vértices estão associados a estados de pesquisa 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 forma ú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 sentenças 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 exige que os dados sejam transformados em um forma vetorizada , representando os valores dos dados recursos no espaço de recurso , para que os dados possam ser analisados no espaço de recursos usando álgebra linear. Em dados estruturados ou semiestruturados, como árvores, a dimensionalidade dos vetores resultantes (ou seja, o número de recursos no espaço de recursos) pode ser bastante alta, uma vez que o espaço de recursos 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 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 contém 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, mais provável é 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 serem detectadas pelos algoritmos.
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. Estender esses pontos por 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 vetorial para dados estruturados é apropriada quando as informações sobre o domínio podem ser usadas de forma eficaz para selecionar um conjunto gerenciável de recursos. Quando tais informações não estão disponíveis, é desejável fazer uso de técnicas que possam lidar com dados estruturados diretamente, sem realizar operações no espaço vetorial.
Métodos de Kernel
Métodos de kernel evita a necessidade de converter dados em vetor. A única informação que eles requerem é uma medida da similaridade de cada par de itens em um conjunto de dados. Esta medição é chamada de núcleo , e a função para determiná-lo é chamada de função do 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 do recurso e, de fato, o design do recurso ainda pode ser uma etapa útil no design da função do kernel. No entanto, os métodos dos métodos do kernel evitam operar diretamente no espaço de recursos, uma vez que 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 simétrico , semidefinido positivo função que pode tomar como entradas os dados em seu espaço original.
A vantagem de usar funções do kernel é, portanto, que um grande 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 um matriz do kernel cujo tamanho é sempre n × n . Essa matriz é independente do tamanho de cada exemplo individual. Esta propriedade é útil quando um pequeno conjunto de dados de exemplos com um grande espaço de recursos deve ser analisado.
estatísticas da indústria da música nos últimos 10 anos
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 de pares em uma matriz de kernel PARA , e todas as análises relevantes podem ser realizadas na matriz do 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 apoiar máquinas de vetor , é suficiente definir uma função kernel válida (simétrica positiva definida) k: T × T → R , também conhecido como kernel da á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 que fossem capazes de detectar gráficos isomórficos . Esses grãos de árvore são chamados completo grãos de árvores.
Kernels de árvore
Agora, vamos apresentar alguns núcleos de árvore úteis para medir a similaridade das árvores. A ideia principal é calcular o kernel para cada par de árvores no conjunto de dados para construir uma matriz de kernel, que pode então ser usada para classificar conjuntos de árvores.
String Kernel
Primeiro, começaremos com uma breve introdução aos kernels de strings, que nos ajudará a apresentar outro método de kernel que é baseado na conversão de árvores em strings.
Vamos definir numY(s) como o número de ocorrências de uma substring Y em uma corda s , com |s| denotando o comprimento da corda. O kernel da string que descreveremos aqui é definido como:
PARAcorda(S1, S2) =Σs∈Fnums(S1)nums(S2)dentros
Onde F é o conjunto de substrings que ocorrem em ambos S1 e S2 , e o parâmetro dentros serve como um parâmetro de peso (por exemplo, para enfatizar substrings importantes). Como podemos ver, este kernel dá um valor mais alto a um par de strings quando eles compartilham muitas substrings comuns.
Kernel da árvore baseado na conversão de árvores em strings
Podemos usar este kernel string para construir um kernel de árvore. A ideia por trás deste kernel é converter duas árvores em duas strings de uma forma sistemática que codifica a estrutura da árvore e, em seguida, aplicar o kernel da string acima a elas.
Convertemos as duas árvores em duas strings da seguinte maneira:
Deixei T denotam uma das árvores alvo, e rótulo (ns) o rótulo da string do nó ns dentro T . dia (ns) denota a representação da string da subárvore de T enraizado em ns . Então se nraiz é o nó raiz de T , dia (nraiz) é a representação em string de toda a árvore T .
A seguir vamos string (T) = tag (nraiz) denotam a representação da string de T . Aplicaremos recursivamente as seguintes etapas de forma ascendente para obter string (T) :
- Se o nó ns é uma folha, deixa dia (ns) = “[” + Rótulo (ns) + ']' (Onde + aqui está o operador de concatenação de string).
- Se o nó ns não é uma folha e tem c crianças n1, n2, ..., nc , ordenar dia (n1), dia (n2), ..., dia (nc) em ordem lexical para obter dia (n1*), dia (n2 *), ..., dia (nc *) , e deixar dia (ns) = “[” + Rótulo (ns) + dia (n1*) + dia (n2 *) + ... + dia (nc *) + ']' .
A figura abaixo mostra um exemplo dessa conversão de árvore em string. O resultado é uma string começando com um delimitador de abertura como “[” e terminando com sua contraparte de fechamento, “]”, com cada par aninhado de delimitadores correspondendo a uma subárvore enraizada em um nó específico.
Agora podemos aplicar a conversão acima a duas árvores, T1 e T2 , para obter duas strings S1 e S2 . A partir daí, podemos simplesmente aplicar o kernel string descrito acima.
O kernel da árvore entre T1 e T2 via duas cordas S1 e S2 agora pode ser dado como:
PARAárvore(T1, T2) = Kcorda(string (T1), string (T2)) = Kcorda(S1, S2) =Σs∈Fnums(S1)nums(S2)dentros
Na maioria das aplicações, o parâmetro de peso torna-se dentro|s| , ponderando uma substring com base em seu comprimento |s| . Métodos de ponderação típicos para dentro|s| está:
- ponderação constante ( dentro|s|= 1 )
- para - ponderação do espectro ( dentro|s|= 1 E se |s|= k , e dentro|s|= 0 de outra forma)
- ponderação exponencial ( dentro|s|= λ|s| Onde 0 ≤ λ ≤ 1 é uma taxa decadente)
Para calcular o kernel, é suficiente determinar todas as substrings comuns F , e contar o número de vezes que ocorrem em S1 e S2 . Esta etapa adicional de encontrar substrings comuns é um problema bem estudado e pode ser realizado em OU(|S1|+|S2|) , empregando árvores de sufixo ou matrizes de sufixo . Se assumirmos que o número máximo de letras (bits, bytes ou caracteres, por exemplo) necessários para descrever o rótulo de um nó é constante, os comprimentos das strings convertidas são |S1|= O (|T1|) e |S2|= O (|T2|) . Portanto, a complexidade computacional de calcular a função do kernel é OU(|T1|+|T2|) , que é linear.
Kernel da árvore baseado em subcaminhos
O kernel da árvore acima usou uma abordagem horizontal, ou ampla, para converter árvores em strings. Embora essa abordagem seja bastante simples, essa conversão significa que não pode operar nas árvores diretamente 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 a uma das folhas é chamada de subcaminho , e um conjunto de subcaminho é o conjunto de todos os subcaminhos incluídos na árvore:
Vamos assumir que queremos definir um kernel de árvore K (T1, T2) entre duas árvores T1 e T2 . Usando o conjunto de subcaminhos, podemos definir este kernel de árvore como:
K (T1, T2) =Σp∈Pnump(T1)nump(T2)dentro|p|
Onde nump(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 T1 e T2 . dentro|p| é o peso, semelhante ao apresentado na seção anterior.
Aqui, apresentamos uma implementação simples deste kernel usando uma pesquisa em profundidade. Embora este algoritmo seja executado em tempo quadrático, algoritmos mais eficientes existem usando árvores de sufixo ou matrizes de sufixo, ou uma extensão do algoritmo de classificação rápida de várias chaves, que pode atingir o tempo linearítmico OU(|T1|registro|T2|) ) na 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 Neste exemplo, usamos o parâmetro de ponderação w|s| dentro|p|= 1 . Isso dá a todos os subcaminhos peso igual. No entanto, existem muitos casos ao usar para - a ponderação do espectro, ou algum valor de peso atribuído dinamicamente, é apropriado.
Sites de mineração
Antes de encerrarmos, vamos dar uma breve olhada em uma aplicação do mundo real de classificação de árvore: 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 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. Os 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 ser semelhante a esta:
A implementação acima usa algumas bibliotecas Python úteis: NetworkX , para trabalhar com estruturas de grafos complexas, e Sopa linda , para extrair dados da web e manipular documentos.
Ligando html_to_dom_tree(soup.find('body')) retornará um objeto de gráfico NetworkX com raiz no elemento da página da web.
Digamos que desejemos encontrar grupos em um conjunto de 1.000 páginas iniciais de sites. Ao converter cada página inicial em uma árvore como esta, podemos comparar cada uma, por exemplo, usando o kernel da árvore de subcaminho fornecido na seção anterior. Com essas medidas de similaridade, podemos descobrir que, por exemplo, sites de e-commerce, sites de notícias, blogs e sites educacionais são facilmente identificados por sua semelhança.
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 grande dimensão, uma situação comum ao trabalhar com estruturas de árvore. Essas técnicas preparam o terreno para análises posteriores de grandes conjuntos de árvores, usando métodos bem estudados que operam sobre a matriz do kernel.
As estruturas em árvore são encontradas em muitas áreas do mundo real, como documentos XML e HTML, compostos químicos, processamento de linguagem natural ou certos tipos de comportamento do usuário. Conforme demonstrado no exemplo da construção de árvores a partir do HTML, essas técnicas nos capacitam a realizar análises significativas nesses domínios.
