PAICyT 2007-2008

Métodos locales de agrupamiento de datos

Vigencia07/2007-07/2008
PatrocinadorUANL / PAICyT
ClaveCA1475-07
Monto65,000 M.N.
LGAC Modelado y optimización de sistemas adaptativos de información

Documentos

Resumen

Importancia y relevancia del proyecto

En los problemas de los campos de bioinformática y minería de datos es común que una instancia típica del problema está estructurado en una manera no uniforme: está compuesto de subproblemas más altamente restringidas que el problema completo. En muchos casos prácticos, las propiedades de interés están relacionados solamente a uno o dos subproblemas densos, por lo cual no es necesario utilizar los datos completos para ofrecer una solución satisfactoria.

En este trabajo planteamos el problema de la identificación de subproblemas "independientes" y "interesantes" de problemas del mundo real, es decir, el problema de agrupamiento (inglés: clustering). El trabajo inicia por definir buenas medidas estructurales para la identificación de subproblemas. La teoría de grafos ofrece herramientas poderosas para tales definiciones. Existen varios métodos de agrupamiento global de grafos, que dividen el grafo entero en subgrafos según ciertos criterios. Lo que interesa a nosotros es poder identificar solamente el subproblema o los subproblemas relevantes desde el punto de vista de una pregunta de naturaleza local. Ya existen algunas ideas iniciales sobre el agrupamiento local, pero hace falta trabajo rigoroso en el desarrollo de algoritmos de agrupamiento local que sirvan para problemas del mundo real. En las aplicaciones, los datos suelen ser complejos, aunque los algoritmos existentes no prestan mucha atención a las posibilidades incorporar tal complejidad a través de ponderación y dirección los grafos.

Nuesto enfoque está en problemas del tipo de optimización combinatorial, donde por lo general se busca por configuraciones que cumplen con ciertos requisitos: las rutas de entrega más cortas o las ubicaciones más adecuadas para centros de distribución, etcétera. El problema general de agrupamiento, como muchos de optimización combinatorial, es NP-difícil. Sin entrar en detalles técnicos, no se cree que puedan existir algoritmos exactos de solución con tiempo de ejecución que aumente no más rápido que polinomialmente con el tamaño del problema. Con procesar solamente subproblemas, podemos recudir el tamaño del problema. Este efecto combinado con la aplicación de algoritmos de aproximación ya ofrece una solución viable tal para datos de tamaño masivo como para datos sujetos a cambios y actualizaciones frecuentes. El reto está en explotar efectivamente la estructura no uniforme de la representación de los datos en la forma de un grafo y ejecutar computaciones locales en paralelo en una sistema multiprocesadora.

Metodología propuesta

El desarrollo e implementación de algoritmos locales de agrupamiento de grafos de tamaño masivo que sean capaces de ofrecer soluciones de alta calidad rápidamente será el enfoque principal del trabajo propuesto. La hipótesis de la propuesta es que el problema en estudio puede ser resuelto de manera eficiente, es decir, desde un enfoque de la aplicación de métodos para optimizar medidas locales matemáticamente fundadas. Los detalles de la metodología se exponen en el protocolo del proyecto. En resumen, en este trabajo se pretende llevar a cabo investigación sobre el agrupamiento local, relevante en el campo de minería de datos y biotecnología. Aplicamos el algébra de grafos y técnicas avanzadas de optimización combinatorial para desarrollar eficientes métodos de solución; es aquí donde yace la contribución científica del trabajo propuesto. El trabajo involucra un componente computacional significativo por el tamaño de las instancias estudiadas. Hasta donde se tiene conocimiento, el problema de agrupamiento local aquí planteado todavía es un campo abierto con muchas aplicaciones potenciales de gran impacto y poco trabajo existente.

Participantes

Productos

  1. Informe técnico en arXiv.org
  2. Artículo publicado en CosRev de Elsevier 2007
  3. Artículo publicado en Ciencia UANL 2009
  4. Presentación de póster en ENOAN 2008, Ing. Cantú
  5. Presentación de póster en ENOAN 2008, Lic. Avalos
  6. Ponencia en ILAS 2008, Dra. Schaeffer

Actualizada la última vez el 5 de octubre del 2010.
URL: http://elisa.dyndns-web.com/~elisa/research/projects/paicyt/paicyt2007.html