@asalber

QOM - Quick Ontology Mapping.

, and . International Semantic Web Conference, volume 3298 of Lecture Notes in Computer Science, page 683-697. Springer, (2004)

Abstract

QOM es un sistema especialmente diseñado para obtener correspondencias entre ontologías de manera rápida y de hecho su complejidad es O(nlogn). El algoritmo sigue el clásico proceso iterativo por etapas: 1- Selección de características, 2- reducción del espacio de búsqueda, 3- Cálculo de similitudes entre entidades, 4- Agregación de similitudes, 5- Intrepretación y selección de correspondendias, 6- Iteración. 1- Selección de características. Entre las características que se consideran están los identificadores de las entidades y las primitivas RDF/S y OWL, características derivadas y agregadas e incluso características específicas del dominio. 2- Reducción del espacio de búsqueda. Esta es la etapa más crucial para ganar eficiencia. En cada iteración se selecciona una agenda de pares de entidades de entre todos los candidatos mediante un algoritmo de programación dinámica. La selección de la agenda de pares se realiza de acuerdo a diversos criterios: Aleatorio (se selecciona un porcentaje fijo), según etiquetas (se seleccionan pares cuyas etiquetas son suficientemente parecidas), propagación de correspondencias (seleccionando en la siguiente iteración las entidades vecinas de otras entre las que se ha establecido una correspondencia), o una combinación de ambas. 3- Para el cálculo de similitudes se utilizan funciones de similitud como la distancia de edición entre cadenas, y escalado multidimensional para ver hasta que punto dos conjuntos de entidades son iguales (por ejemplo los conjuntos de superconceptos de dos conceptos), aunque para ganar eficiencia no explora todo el árbol sino los conceptos más cercanos. 4- La agregación de similitudes se realiza mediante una media ponderada, pero antes las similitudes se transforman mediante una función sigmoidal para enfatizar las similitudes altas y desenfatizar las bajas (1/(1+exp(-5(x-0.5)). 5- La selección de correspondencias se realiza mediante un umbral para descartar los pares con similitud irrelevante y después se fuerza la biyectividad de la correspondencia. Después se utiliza un algoritmo voraz que va realizando correspondencias 1-1 empezando por los pares más similares. 6- En la primera iteración sólo se utilizan las funciones de similitud léxicas aplicadas a las etiquetas de las entidades. En las siguientes iteraciones se utilizan también funciones de similitud entre conjuntos para explotar las relaciones estructurales. Suponiendo que las ontologías tienen un porcentaje fijo de entidades con etiquetas similares regularmente distribuidas en la estructura de la ontología, estas se detectarían en la primera iteración y en las siguientes se iría moviendo la agenda para detectar el resto. Esto supone un número fijo de iteraciones, que es independiente del tamaño de la ontología. El algoritmo mejora en rapidez a GLUE y Anchor-Prompt con valores similares de la medida-F.

Links and resources

Tags

community

  • @asalber
  • @staab
  • @mchaves
  • @dblp
  • @sebastian
@asalber's tags highlighted