Tree Kernels: cuantificación de la similitud entre los datos estructurados en árbol

Una red o gráfico es un tipo de datos estructurados en forma de nodos , con relaciones entre ellos descritas por enlaces o bordes . Los nodos y las aristas de un gráfico pueden tener varios atributos que pueden ser numéricos o categóricos, o incluso más complejos.

Hoy en día, una gran cantidad de datos está disponible en forma de redes o gráficos. Por ejemplo, la World Wide Web, con sus páginas web e hipervínculos, redes sociales, redes semánticas, redes biológicas, redes de citas de literatura científica, etc.

Un árbol es un tipo especial de gráfico y es naturalmente adecuado para representar muchos tipos de datos. El análisis de árboles es un campo importante en informática y ciencia de datos. En este artículo, veremos el análisis de la estructura de enlaces en árboles. En particular, nos centraremos en los núcleos de árboles, un método para comparar gráficos de árboles entre sí, lo que nos permite obtener medidas cuantificables de sus similitudes o diferencias. Este es un proceso importante para muchas aplicaciones modernas, como la clasificación y el análisis de datos.

Clasificación no supervisada de datos estructurados

La clasificación es un componente importante del aprendizaje automático y el análisis de datos. En general, la clasificación puede ser supervisada o no supervisada . En la clasificación supervisada, las clases ya se conocen y se construye un modelo de clasificación a partir de datos de entrenamiento en los que ya se dan las clases correctas. La clasificación no supervisada, por el contrario, intenta identificar clases donde no se conoce ninguna, agrupando datos en categorías en función de alguna medida de su similitud.

La clasificación no supervisada se puede combinar con la teoría de grafos para identificar grupos de redes de árboles similares. Las estructuras de datos de árbol se emplean para modelar objetos de varios dominios. En el procesamiento del lenguaje natural (NLP), por ejemplo, los árboles de análisis se modelan como árboles ordenados y etiquetados. En el razonamiento automatizado, muchos problemas se resuelven mediante la búsqueda, donde el espacio de búsqueda se representa como un árbol cuyos vértices están asociados con estados de búsqueda y los bordes representan pasos de inferencia. Además, los datos semiestructurados, como los documentos HTML y XML, se pueden modelar como árboles ordenados y etiquetados.

Estos dominios se pueden analizar de manera útil a través de técnicas de clasificación no supervisadas. En NLP, la clasificación se puede usar para agrupar automáticamente un conjunto de oraciones en preguntas, comandos y declaraciones. Asimismo, se pueden identificar grupos de sitios web similares aplicando métodos de clasificación a su fuente HTML. En cada uno de estos casos, todo lo que necesitamos es una forma de medir cuán "similares" son dos árboles entre sí.

La maldición de la dimensionalidad

La mayoría de los algoritmos de clasificación requieren que los datos se transformen en una forma vectorizada, representando los valores de las características de los datos en el espacio de características , de modo que los datos puedan analizarse en el espacio de características usando álgebra lineal. En datos estructurados o semiestructurados, como árboles, la dimensionalidad de los vectores resultantes (es decir, la cantidad de características en el espacio de características) puede ser bastante alta, ya que el espacio de características debe conservar información sobre la estructura.

Esto puede ser un inconveniente significativo, considerando que muchas técnicas de clasificación no pueden escalar de manera efectiva con la dimensionalidad de la entrada. En otras palabras, su poder de clasificación disminuye a medida que aumenta la dimensionalidad de la entrada. Este problema se conoce como la maldición de la dimensionalidad.

Para tener una idea de la razón de esta degradación del rendimiento, considere un espacio X de dimensión d . Suponga que X contiene un conjunto de puntos uniformemente distribuidos. Si aumenta el número de dimensiones de X , el número de puntos necesarios para mantener la misma densidad debe aumentar exponencialmente. En otras palabras, cuantas más dimensiones tenga la entrada, más probable es que los datos sean escasos. En general, un conjunto de datos escaso no brinda suficiente información para construir un buen clasificador porque las correlaciones entre los elementos de datos son demasiado débiles para que los algoritmos las detecten.

Cada espacio de características anterior contiene ocho puntos de datos. En el espacio unidimensional, es fácil identificar un grupo de cinco puntos a la izquierda y tres a la derecha. Estirar estos puntos sobre un mayor número de características (es decir, dimensiones) hace que sea más difícil encontrar estos grupos. En aplicaciones reales, los espacios de características pueden tener fácilmente cientos de dimensiones.

Una representación vectorizada para datos estructurados es apropiada cuando la información sobre el dominio se puede usar de manera efectiva para seleccionar un conjunto manejable de características. Cuando dicha información no está disponible, es deseable hacer uso de técnicas que puedan manejar datos estructurados directamente, sin realizar operaciones en el espacio vectorial.

Métodos del núcleo

Los métodos del núcleo evitan la necesidad de convertir los datos en forma vectorial. La única información que requieren es una medida de la similitud de cada par de elementos en un conjunto de datos. Esta medida se llama kernel , y la función para determinarla se llama función kernel . Los métodos del núcleo buscan relaciones lineales en el espacio de características. Funcionalmente, son equivalentes a tomar el producto escalar de dos puntos de datos en el espacio de funciones y, de hecho, el diseño de funciones aún puede ser un paso útil en el diseño de funciones del kernel. Sin embargo, los métodos de los métodos del kernel evitan operar directamente en el espacio de características, ya que se puede demostrar que es posible reemplazar el producto escalar con una función del kernel, siempre que la función del kernel sea una función semidefinida positiva y simétrica que pueda tomar como entrada los datos. en su espacio original.

La ventaja de usar funciones del núcleo es que se puede analizar un enorme espacio de características con una complejidad computacional que no depende del tamaño del espacio de características, sino de la complejidad de la función del núcleo, lo que significa que los métodos del núcleo no sufren la maldición. de dimensionalidad.

Si consideramos un conjunto de datos finito compuesto por n ejemplos, podemos obtener una representación completa de las similitudes dentro de los datos generando una matriz kernel cuyo tamaño es siempre n × n . Esta matriz es independiente del tamaño de cada ejemplo individual. Esta propiedad es útil cuando se va a analizar un pequeño conjunto de datos de ejemplos con un gran espacio de características.

En general, los métodos del núcleo se basan en una respuesta diferente a la cuestión de la representación de datos. En lugar de mapear los puntos de entrada en un espacio de características, los datos se representan a través de comparaciones por pares en una matriz K del kernel, y todos los análisis relevantes se pueden realizar sobre la matriz del kernel.

Muchos métodos de minería de datos se pueden kernelizar. Para clasificar instancias de datos con estructura de árbol con métodos kernel, como con máquinas de vectores de soporte, basta con definir una función kernel válida (definida positiva simétrica) k : T × T → R , también conocida como kernel de árbol . En el diseño de kernels de árboles útiles en la práctica, se requeriría que fueran computables en tiempo polinomial sobre el tamaño del árbol y que pudieran detectar gráficos isomorfos. Estos núcleos de árboles se denominan núcleos de árboles completos .

Núcleos de árbol

Ahora, introduzcamos algunos núcleos de árboles útiles para medir la similitud de los árboles. La idea principal es calcular el kernel para cada par de árboles en el conjunto de datos para construir una matriz kernel, que luego se puede usar para clasificar conjuntos de árboles.

Núcleo de cadena

Primero, comenzaremos con una breve introducción a los núcleos de cadenas, que nos ayudará a presentar otro método de núcleo que se basa en convertir árboles en cadenas.

Definamos num y (s) como el número de ocurrencias de una subcadena y en una cadena s , con | s | que denota la longitud de la cuerda. El núcleo de cadena que describiremos aquí se define como:

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

Donde F es el conjunto de subcadenas que ocurren tanto en S 1 como en S 2 , y el parámetro w s sirve como parámetro de peso (por ejemplo, para enfatizar subcadenas importantes). Como podemos ver, este kernel otorga un valor más alto a un par de cadenas cuando comparten muchas subcadenas comunes.

Tree Kernel basado en la conversión de árboles en cadenas

Podemos usar este kernel de cadena para construir un kernel de árbol. La idea detrás de este kernel es convertir dos árboles en dos cadenas de una manera sistemática que codifica la estructura del árbol y luego aplicarles el kernel de cadenas anterior.

Convertimos los dos árboles en dos cadenas de la siguiente manera:

Deje que T denote uno de los árboles objetivo y etiquete (n s ) la etiqueta de cadena del nodo n s en T . tag(n s ) denota la representación de cadena del subárbol de T con raíz en n s . Entonces, si n root es el nodo raíz de T , tag(n root ) es la representación de cadena de todo el árbol T .

A continuación, permita que string(T) = tag(n root ) denote la representación de cadena de T . Aplicaremos recursivamente los siguientes pasos de abajo hacia arriba para obtener string(T) :

• Si el nodo n s es una hoja, sea tag(n s ) = “[” + label(n s ) + “]” (donde + aquí es el operador de concatenación de cadenas).
• Si el nodo n s no es una hoja y tiene c hijos n 1 , n 2 , … , n c , ordenar etiqueta(n 1 ), etiqueta(n 2 ), … , etiqueta(n c ) en orden léxico para obtener etiqueta (n 1* ), etiqueta(n 2* ), … , etiqueta(n c* ) , y let etiqueta(n s ) = “[” + etiqueta(n s ) + etiqueta(n 1* ) + etiqueta(n 2* ) + … + etiqueta(n c* ) + “]” .

La siguiente figura muestra un ejemplo de esta conversión de árbol a cadena. El resultado es una cadena que comienza con un delimitador de apertura como "[" y termina con su contraparte de cierre, "]", con cada par anidado de delimitadores correspondientes a un subárbol con raíz en un nodo particular.

Ahora podemos aplicar la conversión anterior a dos árboles, T 1 y T 2 , para obtener dos cadenas S 1 y S 2 . A partir de ahí, podemos simplemente aplicar el kernel de cadenas descrito anteriormente.

El núcleo del árbol entre T 1 y T 2 a través de dos cadenas S 1 y S 2 ahora se puede dar como:

K árbol (T 1 , T 2 ) = K cadena ( cadena (T 1 ), cadena (T 2 ) ) = K cadena (S 1 , S 2 ) = Σ s∈F num s (S 1 )num s (S 2 )w s

En la mayoría de las aplicaciones, el parámetro de peso se convierte en w | s | , ponderando una subcadena en función de su longitud | s | . Métodos típicos de ponderación para w | s | están:

• ponderación constante ( w | s | = 1 )
• ponderación del espectro k ( w | s | = 1 si | s | = k , y w | s | = 0 en caso contrario)
• ponderación exponencial ( w | s | = λ | s | donde 0 ≤ λ ≤ 1 es una tasa decreciente)

Para calcular el kernel, es suficiente determinar todas las subcadenas comunes F y contar el número de veces que ocurren en S 1 y S 2 . Este paso adicional de encontrar subcadenas comunes es un problema bien estudiado y se puede lograr en O( | S 1 | + | S 2 | ) , empleando árboles de sufijos o matrices de sufijos. Si suponemos que el número máximo de letras (bits, bytes o caracteres, por ejemplo) necesario para describir la etiqueta de un nodo es constante, las longitudes de las cadenas convertidas son | S 1 | = O( | T 1 | ) y | S 2 | = O( | T 2 | ) . Entonces, la complejidad computacional de calcular la función kernel es O( | T 1 | + | T 2 | ) , que es lineal.

Núcleo de árbol basado en subtrayectos

El núcleo del árbol anterior utilizó un enfoque horizontal, o primero en anchura, para convertir árboles en cadenas. Si bien este enfoque es bastante simple, esta conversión significa que no puede operar en los árboles directamente en su forma original.

Esta sección definirá un kernel de árbol que opera en las estructuras verticales de los árboles, lo que permite que el kernel opere directamente en el árbol.

Una subsección de un camino desde la raíz hasta una de las hojas se llama un subcamino , y un conjunto de subcaminos es el conjunto de todos los subcaminos incluidos en el árbol:

Supongamos que queremos definir un núcleo de árbol K(T 1 , T 2 ) entre dos árboles T 1 y T 2 . Al usar el conjunto de rutas secundarias, podemos definir este kernel de árbol como:

K(T 1 , T 2 ) = Σ p∈P número pags (T 1 )número pags (T 2 )w | pag |

Donde num p (T) es el número de veces que aparece el subtrayecto p en el árbol T , | pag | es el número de nodos en el subtrayecto p , y P es el conjunto de todos los subtrayectos en T 1 y T 2 . w | pag | es el peso, similar al introducido en el apartado anterior.

Aquí, presentamos una implementación simple de este kernel utilizando una búsqueda en profundidad. Aunque este algoritmo se ejecuta en tiempo cuadrático, existen algoritmos más eficientes que utilizan árboles de sufijos o matrices de sufijos, o una extensión del algoritmo de clasificación rápida de múltiples claves, que puede lograr un tiempo lineal rítmico ( O( | T 1 | log | T 2 | ) ) en promedio:

 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

En este ejemplo, usamos el parámetro de ponderación w | s | w | pag | = 1 . Esto da a todos los subtrayectos la misma ponderación. Sin embargo, hay muchos casos en los que es apropiado utilizar la ponderación del espectro k , o algún valor de ponderación asignado dinámicamente.

Sitios web de minería

Antes de concluir, veamos brevemente una aplicación real de la clasificación de árboles: la categorización de sitios web. En muchos contextos de minería de datos, es beneficioso saber de qué "tipo" de sitio web provienen algunos datos. Resulta que las páginas de diferentes sitios web se pueden categorizar de manera bastante efectiva utilizando árboles debido a las similitudes en la forma en que se estructuran las páginas web para servicios similares.

¿Como hacemos eso? Los documentos HTML tienen una estructura anidada lógica, que se parece mucho a un árbol. Cada documento contiene un elemento raíz, con elementos adicionales anidados en su interior. Los elementos anidados en una etiqueta HTML son lógicamente equivalentes a los nodos secundarios de esa etiqueta:

Echemos un vistazo a un código que puede convertir un documento HTML en un árbol:

 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

Esto producirá una estructura de datos de árbol que podría verse así:

La implementación anterior utiliza un par de útiles bibliotecas de Python: NetworkX, para trabajar con estructuras gráficas complejas, y Beautiful Soup, para extraer datos de la web y manipular documentos.

Llamar html_to_dom_tree(soup.find("body")) devolverá un objeto de gráfico NetworkX enraizado en el elemento <body> de la página web.

Digamos que queremos encontrar grupos en un conjunto de 1000 páginas de inicio de sitios web. Al convertir cada página de inicio en un árbol como este, podemos comparar cada una, por ejemplo, usando el núcleo del árbol de subruta dado en la sección anterior. Con estas medidas de similitud, podríamos encontrar que, por ejemplo, los sitios de comercio electrónico, los sitios de noticias, los blogs y los sitios educativos se identifican fácilmente por su similitud entre sí.

Conclusión

En este artículo, presentamos métodos para comparar elementos de datos estructurados en árbol entre sí y mostramos cómo aplicar métodos kernel a árboles para obtener una medida cuantificable de su similitud. Los métodos de kernel han demostrado ser una excelente opción cuando se opera en espacios de alta dimensión, una situación común cuando se trabaja con estructuras de árbol. Estas técnicas sientan las bases para un mayor análisis de grandes conjuntos de árboles, utilizando métodos bien estudiados que operan sobre la matriz kernel.

Las estructuras de árbol se encuentran en muchas áreas de palabras reales, como documentos XML y HTML, compuestos químicos, procesamiento de lenguaje natural o ciertos tipos de comportamiento de los usuarios. Como se demuestra en el ejemplo de construcción de árboles a partir de HTML, estas técnicas nos permiten realizar análisis significativos en estos dominios.