Utilización del modelado de contexto para la interpretación de patrones frecuentes

Abstract

Pattern mining consists of developing data mining algorithms to discover interesting, unexpected and useful patterns in databases. Typically, interesting patterns are associated to patterns that occur frequently on the basis of non-semantic information such as support and confidence. Identifying semantic information will allow us to construct the context model of the patterns and extract informative context indicators, representative transactions of the database as well as semantically similar frequent patterns. By exploiting the context model of patterns, we will be able to discover helpful semantic relations for many problems such as for instance customizing search results without user's specifications.

Our proposal draws upon a general approach to generate semantic annotation of frequent patterns presented by several authors of the University of Illinois at Urbana-Champaign. While their approach lies in extracting semantic relations that emerge from the frequent patterns themselves, we propose to exploit additional information from the domain dependent structured data, such as databases and ontologies, to enrich the context model and semantic similarity of patterns. Specifically, our proposal is based on extracting the graphs that represent the structural relationships of the patterns and define the context model of the patterns through the application of graph inference algorithms. This novel scheme yields enriched context models that help interpret the meanings of the pattern and further explore them at different levels of abstraction.

Our proposal is a general and domain-independent method that can be applied to any application context. Particularly, we tested our method in two datasets, the MovieLens dataset that contains the ratings of a large number of movies by a set of users (https://datahub.io/es/dataset/movielens), and a dataset that contains tourist information of the city of Valencia from a collection of tweets sent by the tourists over a period of time. The results will provide patterns with semantically rich information that will ultimately enhance the understanding and usability of these patterns. Furthermore, this approach uncovers hidden relationships within the patterns and showcases the similarity of different patterns at a higher level of abstraction allowing for a more general yet compact set of patterns.

La minería de patrones consiste en desarrollar algoritmos de minería de datos para descubrir patrones interesantes, inesperados y útiles en bases de datos. Los patrones interesantes se asocian típicamente a patrones que ocurren frecuentemente, donde la frecuencia se determina con medidas numéricas que no contienen información semántica tales como el soporte y la confianza. Identificar información semántica nos permitirá, precisamente, construir modelos de contexto de los patrones y extraer indicadores de contexto informativos, transacciones representativas de la base de datos y patrones frecuentes que son semánticamente similares. Mediante la utilización del modelo de contexto de los patrones, podremos descubrir relaciones semánticas de gran utilidad para muchos problemas como, por ejemplo, para obtener resultados personalizados cuando no se dispone de especificaciones del usuario.

Nuestra propuesta se fundamenta en un enfoque general para la generación de anotaciones semánticas presentado por varios autores de la Universidad de Illinois en Urbana-Champaign. Mientras que este enfoque consiste en extraer información semántica que emerge de los propios patrones frecuentes, nuestra propuesta se basa en explotar información adicional de los datos estructurados del dominio. Concretamente, el objetivo es obtener grafos representativos de las relaciones estructurales de los patrones y extraer el modelo de contexto de los patrones mediante la aplicación de algoritmos de inferencia para grafos. Este novedoso esquema genera modelos de contexto más expresivos que permitirán explorar los patrones a distintos niveles de abstracción así como interpretar el significado de los mismos.

Nuestra propuesta es un método general e independiente del dominio que se puede utilizar en cualquier contexto de aplicación. En particular, el método se ha probado en dos bases de datos, el conjunto de datos de MovieLens, el cual contiene las puntuaciones dadas por los usuarios a un gran número de películas (https://datahub.io/es/dataset/movielens), y un conjunto de datos que contiene información turística de la ciudad de Valencia extraída a partir de una colección de tuits publicados por turistas durante un periodo de tiempo. La aplicación de nuestro método proporciona anotaciones semánticas asociadas a los patrones que mejorarán el entendimiento y la usabilidad de dichos patrones. Además, el enfoque permite descubrir relaciones ocultas en los patrones, así como la similitud entre patrones diferentes a un mayor nivel de abstracción, permitiendo de este modo obtener un conjunto más general, a la par que compacto, de patrones.