PRESENTACIÓN
DEL GRUPO DE
INVESTIGACIÓN
UNIVERSIDAD DE
CANTABRIA
Ángel Cobo
Departamento de Matemática Aplicada
y Ciencias de la Computación
Facultad de Ciencias Económicas y
Empresariales
Universidad de Cantabria
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
La Universidad de Cantabria
 Fundada en 1972
 12 centros
– 34 titulaciones de primer y segundo ciclo
– 12000 alumnos y 1500 profesores e
investigadores
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Un estudio reciente sitúa a la
UC entre las 6 universidades
más destacadas en cuanto a
producción científica y
destaca su papel dinamizador
de la innovación regional
Actividad investigadora
de la UC
SCIENCES
10%
BIOLOGICAL &
MEDICAL
SCIENCES
17%
SOCIAL
SCIENCES
5%
HUMANITIES
5%
ENGINEERING
63%
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Proyección internacional
 Más de 180 convenios Erasmus
 Convenios de intercambio con 10 universidades
USA/Canada/Australia
 Programas de dobles titulaciones
 Diplomas en inglés
 Programas con Latinoamérica:
– Alban
– Alfa
– Fundación Carolina
– AECI
– Unitwin
– 43 convenios bilaterales
– Programa UC - universidades tecnológicas
México
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Grupo G9 de Universidades

Asociación de 9 universidades españolas

UC es miembro fundador
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Estructura del grupo
investigador participante en
la red Eureka
 Dos departamentos
implicados:
– Departamento de Matemática
Aplicada y Ciencias de la
Computación
• Área de matemática aplicada
– Departamento de
Administración de Empresas
• Área de informática de gestión
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
 Colaboración previa entre los
departamentos:
– Actividades de investigación
– Actividad docente en la Fac. Ciencias
Económicas y Empresariales
– Cursos monográficos
– Programas de postgrado
• Máster en Empresa y Tecnologías de la Información
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Líneas de investigación de los
integrantes del grupo:
 Inteligencia Artificial
 Modelización mediante ecuaciones







funcionales
Técnicas metaheurísticas
Modelos bioinspirados
Técnicas de minería de texto
Sistemas de información en la
gestión empresarial
Sistemas de gestión documental
Aplicaciones y herramientas de la
Web 2.0.
Desarrollo de aplicaciones Web con
tecnologías open source.
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Posibles aportaciones a la red
 Participación en las tareas del proyecto:
– IC: creadores de sistemas híbridos
matemáticamente fundamentados que
ayuden a la creación y explotación de
ontologías.
– CA: Creadores de algoritmos
– CS: Creadores de sistemas
computacionales
 Modelización mediante ecuaciones
funcionales
 Utilización de técnicas de Swarm Intelligence
 Desarrollo de algoritmos para la resolución
de problemas de minería de texto
 Desarrollo de aplicaciones en entornos Web
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Modelización mediante
ecuaciones funcionales
 Poderosa herramienta para la modelización
b
a
Área de un rectángulo: F(a,b)
b1
a
b2
F(a,b1+b2) = F(a,b1) + F(a,b2)
b
a1
a2
F(a1+a2,b) = F(a1,b) + F(a2,b)
F (a, b)  c  a  b
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
 Redes funcionales:
– Generalización de las
redes neuronales
– Deducir la topología de
la red a partir de las
propiedades del
problema
– Simplificación de la red
mediante sistemas de
ecuaciones funcionales
– Diferentes funciones
nodales
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Swarm Intelligence
 Hace referencia a diversas técnicas
utilizadas en el ámbito de la
Inteligencia Artificial
 Se basan en la idea de que grupos
de agentes extremadamente
sencillos y poco o nada organizados
pueden exhibir un comportamiento
complejo, incluso inteligente,
utilizando reglas y mecanismos de
comunicación local simples.
 Un colectivo de agentes sociales
pueden llevar a cabo actuaciones
de nivel complejo y formar sistemas
descentralizados y autoorganizativos.
 Ejemplos:
– ACO (Ant Colony Optimization)
– PSO (Particle Swarm Optimization)
– Ant clustering
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Optimización
basada en colonias
de hormigas (ACO)
 Metaheurística inspirada en el
comportamiento de las hormigas
– Una colonia de "hormigas artificiales" coopera
en la búsqueda de buenas soluciones de
problemas de optimización discreta.
 ACO ha sido utilizada con éxito en una
amplia variedad de problemas de
optimización combinatoria
– Problema del viajante (TSP) (Dorigo, 1992).
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Hormigas artificiales
 Una hormiga artificial es un procedimiento de
construcción estocástica que construye una
solución de manera incremental, añadiendo
paso a paso componentes oportunamente
elegidas.
 La hormiga artificial usa...
– información heurística que proviene de un
conocimiento a priori del problema
– memoria de la evolución del proceso de
búsqueda desde su inicio (rastros de feromona).
 En cada iteración, una nueva población de
posibles soluciones es construida por un
conjunto de hormigas artificiales
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Implementación de “hormigas
artificiales”
 Mientras una hormiga “real” deposita en sus viajes una




sustancia química (feromona), las hormigas artificiales
modifican determinados valores numéricos en función de la
información acumulada hasta el momento.
La concentración de feromona depositada, (el valor numérico
asociado) será proporcional a la calidad de la solución
encontrada.
Se debe implementar un proceso de evaporación artificial
que haga disminuir la cantidad de feromona de las peores
soluciones.
Uso de reglas probabilísticas para la construcción de nuevas
soluciones
Se puede contar también con un “agente externo” con una
visión global de la situación, lo que le permite influir en el
comportamiento de las hormigas depositando una cantidad
adicional de feromona.
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Utilización de ACO para el
problema del viajante
 Un conjunto de hormigas
artificiales recorren el grafo
correspondiente, yendo de una
ciudad a otra.
 En cada iteración t del
algoritmo, m hormigas
establecen distintas rutas en n
etapas
 En cada paso, la hormiga
decide a qué nodo dirigirse de
entre los que no han sido
visitados, según una regla
probabilística
1
2
5
4
3
6
7
8
9
10
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
 La tabla de decisión del nodo i: probabilidad con la
que la hormiga k-ésima decide moverse desde el
nodo i al j durante la iteración t

 

 ij ( t )   ij 


 is ( t )   is 
 
k
p ij ( t )  
k
s

N

i

 0

  
si
si
k
j  Ni
k
j  Ni
Nik : conjunto de nodos vecinos de i
no visitados todavía por la hormiga k.
ij : concentración de feromona de la arista que une los nodos i y j
ij : información heurística (ij=1/dij, siendo dij la distancia entre los
nodos i y j),
 y  : parámetros que determinan la importancia relativa de la
feromona con respecto a la información heurística
Ni : conjunto de nodos vecinos de i.
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
 Actualización
de la concentración de feromona
aplicada a todas las aristas:
 ij ( t )  (1  r ) ij ( t )    ij ( t )
m
k
  ij ( t )     ( t )
ij
k 1
donde r es un coeficiente
de evaporación, 0<r <=1
1 / Lk ( t ) si ( i , j )  T k ( t )

k
  (t )  
ij
k

si ( i , j )  T ( t )
0
cantidad de feromona que la
hormiga k deposita en cada
arco que ha utilizado.
Tk(t) : ruta realizada por la hormiga k-ésima en la iteración t
Lk(t) : longitud de la ruta
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Trabajos realizados con ACO
 Resolución de problemas
de distribución en planta
– Distribución de áreas en
plantas industriales
 Diseño de un algoritmo
de clustering:
– Creación de grupos de objetos
relacionados
– Asignación de cada objeto a un
grupo (cluster) buscando:
• Alto grado de asociación entre
sí dentro de cada cluster
(minimización distancia intracluster)
• Diferenciación con los objetos
de otros clusters (maximización
distancia inter-clusters)
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Algoritmos de Ant Clustering
 Inspirados en la forma en la que
las hormigas organizan sus
nidos:
– Agrupamiento de larvas
– Organización de cadáveres
– Colocación de alimentos
 Las hormigas exploran el
espacio recogiendo y colocando
objetos.
 Trabajos pioneros:
– Deneubourg (1990)
– Lumer y Faieta (1994)
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
EXPERIMENTO:
Agrupamiento real de 1500 cadáveres
de hormigas colocados aleatoriamente
en una colonia de hormigas Messor
Sancta.
Estado
inicial
Tras 2
horas
Tras 6
horas
Tras 26
horas
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Funcionamiento del algoritmo
básico
 El proceso se
desarrolla sobre una
rejilla bidimensional
toroidal
 Los objetos son
“colocados”
aleatoriamente
– Proyección sobre el plano
– Un máximo de un objeto
por celda
 Un conjunto de hormigas exploran la rejilla
realizando las siguientes acciones:
– Recoger objetos
– Colocar objetos
– Realizar desplazamientos
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
 Similitud de un objeto con los del entorno:
f (d i ) 
1

2

d jE ( d i )
Sim ( d i , d j )

 Probabilidad de recoger el objeto:

Precoger


k

( d i )   

k

f
(
d
)
i 

2
 Probabilidad de colocar el objeto:
Pcolocar

f (d i ) 

( d i )   

k

f
(
d
)
i 

2
 3
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
PSO: Introducción
 Heurística inspirada en los patrones de comportamiento social
de organismos vivos que viven e interactúan en grupo:
– Colonias de insectos
– Bandadas de pájaros
– Bancos de peces
 Algoritmos de modelización de agrupaciones de vuelo en
bandadas de pájaros
– Algoritmo de F. Heppner
– Comportamientos observados:
• Volar a la misma velocidad que sus vecinos.
• Volar cerca de sus vecinos pero sin colisionar con ellos
• Volar en la misma dirección que el pájaro de la cabeza de la
bandada.
• Vuelo en torno a áreas de atracción y reproducción de
comportamientos
 Kennedy, J., y Eberhart, R. (1995). Particle Swarm
Optimization. Proceedings of the 1995 International
Conference on Neural Networks, New York, IEEE Press.
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Características de los
algoritmos PSO
 Métodos basados en poblaciones en los que
“individuos” (partículas) interactúan localmente con
sus vecinos conduciendo a un comportamiento
dinámico global de búsqueda.
 Las partículas “vuelan” sobre el espacio de
soluciones y “aterrizan” sobre la mejor solución.
 Incorpora ciertas características probabilísticas en el
movimiento de las partículas.
 Balance entre:
– Exploración: búsqueda de una buena solución.
– Explotación: aprovechamiento del éxito de búsqueda de
otra partícula.
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
 Cada partícula pasa sus coordenadas a una
función de mide su ajuste.
 Ninguna necesidad de regularidad de la función
objetivo
– Aceptan funciones discontinuas
– No hay necesidad de gradientes
 Cada partícula tiene asociadas en cada momento:
– Una posición
– Una velocidad (dirección y magnitud de desplazamiento)
– Memoria:
• Su mejor posición previa
• La mejor posición encontrada por la población hasta el
momento
 Las partículas ajustan sus posiciones y
velocidades en función de las buenas posiciones
encontradas.
Pi (t+1) = Pi(t) + Vi (t+1)
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Algoritmo PSO local básico
1.
2.
3.
4.
5.
6.
Inicialización aleatoria de posiciones P1,P2,...,PN y velocidades
V1,V2,...,VN de las partículas.
Identificación del conjunto de partículas vecinas Vecindarioi
para cada partícula Pi
Evaluación del ajuste de cada partícula:
F(P1), F(P2),..., F(PN)
Actualización de posiciones en las que cada partícula tuvo su
mejor ajuste:
P1best, P2best,..., PNbest
Actualización de mejor posición en el vecindario de cada
partícula:
Pilocal = Max(Pkbest | Pk en Vecindarioi)
Actualización de velocidades:
Vi = Vi + *Rnd(0,1)*(Pibest - Pi) +  *Rnd(0,1)*(Pilocal - Pi)
Rnd(0,1) = generador de números aleatorios entre 0 y 1
7.
8.
Actualización de posiciones
Pi = Pi + Vi
Si no se cumple la condición de terminación ir al Paso 3
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Componentes de la velocidad
Vi = Vi + *Rnd(0,1)*(Pibest - Pi) +  *Rnd(0,1)*(Pilocal - Pi)
Mejor del vecindario
P(t+1)
i
Componente social
Componente
de inercia
P(t)
i
Componente cognitiva
cognitiva
Mejor personal
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Es recomendable la existencia de
solapamientos entre los vecindarios
de las partículas
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
 Componente de inercia:
– Memoriza dirección previa
– Previene de cambios de dirección
drásticos
 Componente cognitiva:
– Orienta a la partícula hacia su mejor
solución en el pasado
– También conocida como “nostalgia” de la
partícula (Kennedy & Eberhart)
 Componente social:
– Orienta la partícula hacia la mejor
posición encontrada en su vecindario
– “Envidia”
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Trabajos realizados con PSO
Bezier Surf Fit, Degree-u= 3, Degree-v= 3
 Parametrizaciones en
problemas de ajuste de
nubes de puntos
20
P 116
10
0
P1616
P1 1
P16 1
 Aplicaciones a problemas
de clustering (k-PSO)
-10
0
10
x
0
-10
y
10
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Minería de Texto
 Descubrimiento y extracción de información
nueva de forma automática a partir de
colecciones de documentos textuales.
 Tareas de la minería de Texto
– Recuperación de la Información
• Búsqueda de documentos relevantes
– Clasificación
• Decidir y asignar cada documento a una de entre varias
categorías predefinidas.
– Clustering o agrupamiento
• Encontrar grupos de documentos relacionados con un
alto grado de similitud entre ellos y a su vez con un alto
grado de disimilitud con los documentos de otros
grupos.
 Enfoque multilingüe
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Recursos Lingüísticos
 Tesauro Eurovoc
– Tesauro Multilingüe de la Comunidad Europea.
– Eurovoc 4.2: 21 idiomas oficiales de la Unión Europea.
– 6.645 descriptores, 127 microtesauros, 21 campos
temáticos.
• Política, relaciones internaciones, economía, comercio,
finanzas, negocios y competencia, empleo y trabajo,
producción, tecnología e investigación, energía e
industria.
 Glosario Económico Multilingüe del FMI
– Más de 11,500 registros de términos, palabras, frases y
organizaciones que comúnmente se encuentran en
documentos del FMI.
– Completado con 7.112 términos de un diccionario españolinglés de negocios.
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Trabajos realizados
 Representación
vectorial de
documentos
económicos
 Estudios sobre medidas
de similitud
 Implementación de
algoritmos bioinspirados
 Desarrollo de una
aplicación Web de
gestión documental
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
TALLER EUROPEO DE LA
RED IBEROAMERICANA DE DESCUBRIMIENTO
DE CONOCIMIENTO
Granada, 7-9 de Julio de 2008
Manos
a la
obra !!!
Descargar

Teoría de la decisión