Minería de secuencias
En el campo de la minería de datos y extracción de conocimiento, la minería de secuencias es un caso particular de la minería de datos estructurados. Consiste en encontrar patrones estadísticamente relevantes en colecciones de datos que están representados de forma secuencial.[1] Debido a la frecuencia con que aparecen este tipo de datos en escenarios de aplicaciones reales, esta técnica constituye uno de los métodos más populares de descubrimiento de patrones.
Los patrones frecuentes obtenidos durante el minado de secuencias, se usan en tareas de detección de dependencias funcionales, predicción de tendencias, interpretación de fenómenos y como soporte de decisiones en estrategias de producción.
Secuencias
editarLas secuencias son un importante tipo de datos, que representa una clase especial de estructura donde importa el orden que ocupan los elementos (conjunto de ítems del inglés itemset). Este orden, puede o no estar relacionado con el factor tiempo. El tamaño de una secuencia va a estar dado por la cantidad de itemsets que contenga, mientras que su longitud por la cantidad de ítems.
Ejemplos típicos de secuencias, son las secuencias genéticas como las de ADN y ARN. Un caso menos trivial es la representación de los registros de compras a partir de secuencias. Este patrón secuencial relacionaría las transacciones de un grupo de clientes a lo largo del tiempo y las asociaciones que se obtendrían al minar estos datos, mostrarían las dependencias entre los productos en el intervalo de tiempo analizado.
Técnicas de minería de secuencias
editarDesde que Agrawal y Srikant[2] presentaron su enfoque de minería de patrones secuenciales, esta se ha convertido en una de las tareas más investigadas de la minería de datos, ya que muchos problemas dentro de este campo pueden ser abordados con el minado de secuencias.
Clasificación de datos secuenciales. (Aprendizaje supervisado)
editarLa tarea de clasificación de secuencias consiste en inducir una función de selección, que genere clasificaciones para secuencias de datos a partir de secuencias de entrenamiento. Usualmente esto se obtiene mediante la composición de alguna técnica general de clasificación, con los criterios de selección adecuados. La idea es que secuencias de datos con clasificaciones similares estén estrechamente relacionadas.
Esta técnica tiene una gran aplicación en muchos escenarios como pronósticos de cambios climáticos y reconocimiento de patrones; donde se necesitan realizar predicciones de comportamientos, basándose en registros de datos históricos.
Agrupamiento de patrones secuenciales. (Aprendizaje no supervisado)
editarEl agrupamiento de secuencias se define como la tarea de separar en grupos a las secuencias de datos, de manera que las pertenecientes a un mismo grupo sean muy similares entre sí, y al mismo tiempo sean diferentes a las de otros grupos. Se usa en muchos escenarios donde no se cuenta con registros de información confiable o donde se deben realizar asociaciones a partir de la similitud entre las secuencias que se analizan.
Un ejemplo típico de aplicación de esta técnica, es en las transacciones comerciales donde sirve para identificar diferentes grupos de clientes con registros de compra similares.
También tienen un variado uso en la formación de grupos de secuencias de proteínas similares, para analizar a profundidad cada uno de ellos atendiendo a sus características particulares.
Reglas de asociación con datos secuenciales.
editarObtener reglas de asociación a partir de secuencias, se basa principalmente en el descubrimiento de patrones secuenciales frecuentes.
Un ejemplo de uso de esta técnica es la representación de operaciones de distribución y marketing, a partir de secuencias, y las asociaciones obtenidas, ayudarían a identificar los productos de mayor promoción, de acuerdo con los patrones de compra. Por ejemplo, si una pareja adquiere una nueva vivienda, en el 70% de los casos se comprarán una cama en menos de un mes.
Algoritmos de minería de secuencias frecuentes
editarLa mayoría de los algoritmos implementados para el minado de secuencias frecuentes, utilizan tres tipos diferentes de enfoques de acuerdo a la forma de realizar el conteo de frecuencia a los patrones secuenciales candidatos.
- El primer grupo de algoritmos se basan en la propiedad A priori. Esta propiedad fue introducida por Agrawal and Srikant[3] en el minado de reglas de asociación y se basa en que si un patrón es frecuente entonces cualquier subpatrón de él también será frecuente. Esto permite reducir el espacio de búsqueda en el proceso de generación de candidatos. Basado en esta estrategia se presentaron algoritmos como el AprioriAll y el AprioriSome en;[4] y el algoritmo GSP (Patrón secuencial generalizado).[5]
- El segundo grupo está formado por algoritmos que tratan de reducir el tamaño del conjunto de datos explorados, sustituyendo la fase de generación de candidatos por la realización de proyecciones y técnicas de crecimiento de patrones sobre los datos iniciales. Estos algoritmos siguen una filosofía de [divide y vencerás], actualizando recursivamente los conjuntos de secuencias frecuentes encontrados. A este grupo pertenecen algoritmos como el FreeSpan[6] y el PrefixSpan.
- El tercer grupo lo forman algoritmos que almacenan solamente las estructuras conocidas como listas de identificadores o de ocurrencias, que describen la ubicación de cada secuencia en la colección de datos. En este grupo se aplican técnicas como la transformación de los datos a formato vertical.
Aplicaciones
editarLa minería de secuencias frecuentes posee una amplia gama de aplicaciones, en distintas líneas de investigación y entornos de producción, como por ejemplo:
- Detección de Intrusos: Se ha utilizado para la detección de intrusiones, estudiando los patrones de mal uso en la seguridad de la información, encontrando patrones de acceso a los recursos, procesando los registros de ataques a la red, para así descubrir comportamientos secuenciales de intrusión y diseñar estrategias para la detección de varias etapas de ataque.
- Salud: En el sector de la salud, se usan para representar patrones de atención médica como las trayectorias de los pacientes en los centros de salud, los estados evolutivos de los pacientes, los comportamientos de los síntomas, entre otros; para descubrir patrones en las historias de los registros médicos y mejorar el nivel de diagnóstico.
- Telecomunicaciones: Se utiliza en el campo de las telecomunicaciones para predecir la futura localización de un usuario móvil, para la búsqueda de patrones de llamadas telefónicas y para los servicios basados en la localización.
- Diseño de Sitios Web: Con el amplio uso de la web en la actualidad, las tareas de diseño de sitios y servidores web, están aumentando su nivel de complejidad. Con la minería de secuencias se pueden registrar cuales son las principales rutinas de navegación de los usuarios para así proponer mejores estructuras para el diseño del sitio e identificar mejor las prioridades en las tareas de los servidores.
- Bioinformática: En la actualidad existen inmensos volúmenes de información genética que tienen una gran importancia en los campos de la medicina y la industria farmacéutica. Con la minería de secuencias frecuentes se puede determinar los genes que codifican para ciertas proteínas y llevar a cabo predicción de genes.
Véase también
editar- Minería de datos
- Aprendizaje supervisado
- Aprendizaje no supervisado
- Bioinformática
- Aprendizaje automático
- Minería de textos
- Minería de datos espacial
- Minería de procesos
- Inteligencia Empresarial
- Estadística
- Reglas de asociación
- Web mining
- Sistemas de información ejecutiva
- Sistemas de soporte a decisiones
- Minería de grafos
Referencias
editar- ↑ Mabroukeh, N. R.; Ezeife, C. I. (2010). "A taxonomy of sequential pattern mining algorithms". ACM Computing Surveys
- ↑ «Zaki MJ, Lesh N, Ogihara M (2000) PLANMINE: Sequence mining for plan failures. Artificial Intelligence Review, special issue on the Application of Data Mining». Archivado desde el original el 6 de marzo de 2016. Consultado el 20 de diciembre de 2012.
- ↑ Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association rules in large databases. In Jorge B. Bocca, Matthias Jarke, and Carlo Zaniolo, editors, Proceedings of the 20th International Conference on Very Large Data Bases, VLDB, pages 487-499, Santiago, Chile, September 1994.
- ↑ R. Agrawal, R. Srikant. Mining sequential patterns. IEEE Computer Society: In Proc. of the 11th International Conference on Data Engineering (ICDE' 95). Taipei, Taiwan, March, 1995.
- ↑ R Srikant, Agrawal R. Mining sequential patterns: Generalizations and performance improvements. In: 5th Intl. Conf. Extending Database Technology, 1996.
- ↑ «J. Han, J. Pei, B. Mortazavi-Asl, Q. Chen, U. Dayal, M.-C. Hsu. FreeSpan: Frequent patternprojected sequential pattern mining. In Proc. 2000 Int.Conf. Knowledge Discovery and Data Mining, KDD’00. Boston, MA, Aug. 2000». Archivado desde el original el 18 de enero de 2013. Consultado el 20 de diciembre de 2012.
Datos: Q1718507
