Búsqueda y Análisis de Información Masiva

Usted está aquí

Créditos
6
Tipos
Complementaria de especialidad (Sistemas de Información)
Requisitos
  • Prerrequisito: BD
  • Prerrequisito: PE
  • Correquisito: PROP
Departamento
CS
Mail
La cantidad de información almacenada digitalmente en organizaciones, o colectivamente en la web, es hoy en día suficientemente voluminosa como para que encontrar aquello que se busca sea generalmente complicado. El campo conocido como "Information Retrieval" contempla métodos para organizar la información de forma que sea posible después para los usuarios encontrar la información de forma cómoda y eficiente. Cubriremos las técnicas básicas de búsqueda de documentación textual basada en palabras clave. Examinaremos después
el caso de la búsqueda en la web, donde la presencia de hiperenlaces puede usarse no sólo para dirigir la búsqueda sino para valorar el interés de cada página -- éste es el caso del conocido algoritmo PageRank utilizado por Google. Veremos la extensión de este tipo de técnicas a redes sociales (por ejemplo Facebook o Twitter) donde el grafo de interacciones entre usuarios da mucha información sobre qué le puede interesar a cada usuario. Finalmente, estudiaremos formas posibles de explotación de este tipo de técnicas en beneficio de una organización.

Profesores

Responsable

  • Marta Arias Vicente ( )
  • Ramon Ferrer Cancho ( )

Otros

  • Javier Béjar Alonso ( )
  • Jose Luis Balcázar Navarro ( )
  • Ricard Gavaldà Mestre ( )

Horas semanales

Teoría
1.5
Problemas
0.5
Laboratorio
2
Aprendizaje dirigido
0.2
Aprendizaje autónomo
6

Competencias

Competencias Técnicas de cada especialidad

Especialidad sistemas de información

  • CSI2 - Integrar soluciones de Tecnologías de la Información y las Comunicaciones y procesos empresariales para satisfacer las necesidades de información de las organizaciones, permitiéndoles llegar a sus objetivos de forma efectiva
    • CSI2.3 - Demostrar conocimiento y capacidad de aplicación de los sistemas de extracción y de gestión del conocimiento.
    • CSI2.6 - Demostrar conocimiento y capacidad de aplicación de los sistemas de ayuda a la toma de decisiones y de bussines intelligence.

Especialidad de computación

  • CCO2 - Desarrollar de forma efectiva y eficiente los algoritmos y el software apropiados para resolver problemas complejos de computación.
    • CCO2.5 - Implementar software de búsqueda de información (information retrieval).

Competencias Transversales

Aprendizaje autónomo

  • G7 - Detectar carencias en el propio conocimiento y superarlas mediante la reflexión crítica y la elección de la mejor actuación para ampliar este conocimiento. Capacidad para el aprendizaje de nuevos métodos y tecnologías y versatilidad para adaptarse a nueves situaciones.
    • G7.3 - Aprendizaje autónomo: Capacidad de planificación y organización del trabajo personal. Aplicar los conocimientos adquiridos a la realización de una tarea en función de la pertenencia y la importancia, decidiendo la manera de llevarla a cabo y el tiempo que hay que dedicarle y seleccionando las fuentes de información más adecuadas. Identificar la importancia de establecer y mantener contactos con los compañeros de estudios, con el profesorado y con profesionales (networking). Identificar fórums de información sobre ingeniería TIC, sus avances y su impacto en la sociedad (IEEE, asociaciones, etc.).

Objetivos

  1. Conocer los problemas asociados al almacenamiento y recuperación de la información, sobre todo de tipo textual.
    Competencias relacionadas: CCO2.5,
  2. Entender que la efectividad en la búsqueda y recuperación de la información está muy relacionada con la organización y descripción de esta información.
    Competencias relacionadas: CCO2.5, G7.3,
  3. Conocer y entender la estructura, arquitectura y funcionamiento de la web, y los elementos relacionados con ella: índices, buscadores, crawlers, entre otros.
    Competencias relacionadas: CSI2.3, G7.3,
  4. Conocer y entender los parámetros de descripción de redes complejas, así como los algoritmos principales de análisis de su estructura.
    Competencias relacionadas: CSI2.3, CSI2.6, G7.3,
  5. Reconocer las oportunitades de uso de información masiva para los fines de una organización y elegir los métodos, herramientas y procedimientos más adecuados.
    Competencias relacionadas: CSI2.6, G7.3,
  6. Poder decidir las técnicas de recuperación de la información que pueden ser efectivas en un sistema de información concreto, sobre todo de tipo textual.
    Competencias relacionadas: CSI2.3, CSI2.6, CCO2.5, G7.3,
  7. Poder evaluar la efectividad y utilidad, de acuerdo con varios criterios, de un sistema de recuperación de la información.
    Competencias relacionadas: CSI2.3, CSI2.6, CCO2.5, G7.3,
  8. Poder implementar las principales técnicas vistas en la asignatura.
    Competencias relacionadas: CCO2.5, G7.3,
    Subcompetences:
    • Poder implementar las técnicas básicas (algoritmos y estructuras de datos) de recuperación de la información.
    • Poder implementar los algoritmos básicos para el análisis de redes.
  9. Saber utilizar, adaptar y extender software abierto.
    Competencias relacionadas: G7.3,
    Subcompetences:
    • Por ejemplo: Lucene, base de datos DEX, WIRE crawler, entre otros.

Contenidos

  1. Introducción
    Necesidad de técnicas de búsqueda y análisis de información masiva. Búsqueda y análisis vs. bases de datos. Proceso de recuperación de la información. Preproceso y análisis léxico.
  2. Modelos de recuperación de la información
    Definición formal y conceptos básicos: Modelos abstractos de documentos y lenguajes de interrogación. Modelo booleano. Modelo vectorial. Latent Semantic Indexing.
  3. Implementación: Indexación y búsquedas
    Ficheros inversos y ficheros de firmas. Compresión de índices. Ejemplo: Implementación eficiente de la regla del coseno con medida tf-idf. Ejemplo: Lucene.
  4. Evaluación en recuperación de la información
    Recall y precisión. Otras medidas de rendimiento. Colecciones de referencia. "Relevance feedback" y "query expansion".
  5. Búsqueda en internet
    Ranking y relevancia para modelos web. Algoritmo PageRank. Crawling. Arquitectura de un sistema simple de búsqueda en la web.
  6. Arquitectura de sistemas para la gestión de información masiva
    Escalabilidad, alto rendimento y tolerancia a fallos: el caso de buscadores web masivos. Arquitecturas distribuidas. Ejemplo: Hadoop.
  7. Análisis de redes
    Parámetros descriptivos y características de las redes: grado, diámetro, redes "small-world", entre otros. Algoritmos sobre redes: clustering, detección de comunidades y de nodos influyentes, reputación, entre otros.
  8. Sistemas de información basados en análisis de información masiva. Combination with other technologies.
    "Search Engine Optimization". Uso de técnicas de recuperación de la información en combinación con Minería de Datos y Aprendizaje. Sistemas de recomendación.

Actividades

Actividad Acto evaluativo


Introducción y modelos de recuperación de la información

2 horas de teoría, 2 de problemas y 4 de laboratorio sobre los contenidos "Introducción" y "Modelos de recuperación de la información". Véase la descripción en el apartado Metodología Docente.
Objetivos: 1 2 6
Contenidos:
Teoría
5h
Problemas
2h
Laboratorio
6h
Aprendizaje dirigido
0h
Aprendizaje autónomo
13.5h

Implementación y evaluación

2 horas de teoría, 2 de problemas y 4 de laboratorio sobre los contenidos "Implementación" y "Evaluación". Véase la descripción en el apartado Metodología Docente.
Objetivos: 2 7 8 9
Contenidos:
Teoría
3h
Problemas
2h
Laboratorio
2h
Aprendizaje dirigido
0h
Aprendizaje autónomo
6.5h

Búsqueda en la web

2 horas de teoría, 2 de problemas y 4 de laboratorio sobre el contenido "Búsqueda en la web". Véase la descripción en el apartado Metodología Docente.
Objetivos: 3 5 9
Contenidos:
Teoría
4h
Problemas
2h
Laboratorio
6h
Aprendizaje dirigido
0h
Aprendizaje autónomo
12.5h

Primer examen parcial

Examen parcial de la primera parte de la asignatura.
Objetivos: 7 1 2 3 5 6
Semana: 9
Tipo: examen de teoría
Teoría
2h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
0h

Arquitectura de sistemas de búsqueda en la web

2 horas de teoría y 6 de laboratorio sobre el contenido "Arquitectura". Véase la descripción en el apartado Metodología Docente.
Objetivos: 3 6 8 9
Teoría
4h
Problemas
2h
Laboratorio
6h
Aprendizaje dirigido
0h
Aprendizaje autónomo
12.5h

Análisis de redes

6 horas de teoría y 6 de laboratorio sobre el contenido "Análisis de redes". Véase la descripción en el apartado Metodología Docente.
Objetivos: 4 6 7 8 9
Contenidos:
Teoría
4h
Problemas
2h
Laboratorio
4h
Aprendizaje dirigido
0h
Aprendizaje autónomo
12.5h

Information systems based on massive information analysis

Clases de teoría, problemas y laboratorio sobre este contenido. El énfasis es en la discusión de casos prácticos en clase de problemas y laboratorio. ¿Véase la descripción en el apartado Metodología Docente.
Objetivos: 5 6 7 9
Contenidos:
Teoría
3h
Problemas
2h
Laboratorio
4h
Aprendizaje dirigido
0h
Aprendizaje autónomo
12.5h

Segundo examen parcial o examen final

El estudiante elige entre hacer un examen de la segunda part del curso o un examen de todo el curso.
Objetivos: 1 2 3 4 5 6 7 8 9
Semana: 15 (Fuera de horario lectivo)
Tipo: examen final
Teoría
0h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
3h
Aprendizaje autónomo
12h

Metodología docente

- Clases de teoría. Antes de cada clase, el estudiante tendrá que haber leído los apuntes o materia del tema a desarrollar, que habrá sido anunciado con tiempo. El estudiante tendrá también a su disposición un cuestionario de preguntas básicas del tema, para comprobar qué grado de comprensión se ha alcanzado. En clase, el
profesor expondrá los puntos principales, asumiendo que el estudiante ha realizado el trabajo indicado e intentado responder el cuestionario, y se discutirán en común las dudas que puedan haber surgido a los estudiantes.

- Clases de problemas. Profesores y estudiantes comentarán y compararán las soluciones de los problemas que el profesor habrá indicado con tiempo suficiente antes de cada clase. Las discusiones puede hacerse en común entre toda la clase o en particular entre el profesor y un alumno. El profesor dará por supuesto que los estudiantes han pasado un tiempo razonable intentando resolver los ejercicios, y priorizán la atención a aquellos que lo hayan hecho así.

- Clases de laboratorio. Antes de cada clase, el estudiante tendrá que haber leído el guión del trabajo práctico a desarrollar en la sesión. Durante la clase, el estudiante realizará el trabajo indicado en el guión con la supervisión del profesor. En muchas de las sesiones, el guión contendrá trabajo que, probablemente, haya que terminar en horas de trabajo personal tras la sesión de laboratorio. Para la mayoría de las sesiones de laboratorio se tendrá que redactar un informe corto del trabajo realizado y/o entregar el trabajo (p.e., ficheros de resultados y programas).

- Trabajo personal. Cada tipo de actividad presencial implica una cierta cantidad de trabajo personal antes o después. Adicionalmente, algún tema o temas de la asignatura pueden no tener clases de teoría o de ejercicios asociados, y los estudiantes deberán estudiarlo por su cuenta, y usar las sesiones de actividades dirigidas si lo desean para evaluar que han progresado suficientemente.

Dado que la asignatura aparece en dos especialidades diferentes, podrán proponerse actividades (teoría, problemas y laboratorio) ligeramente diferentes para los estudiantes de ambas especialidades, velando para que no haya agravios comparativos con respecto a dificultad o carga de trabajo.

Método de evaluación

La asignatura comprenderá los siguientes actos evaluatorios:

- Informes de las actividades de laboratorio, que deberán haberse entregado dentro del plazo indicado para cada sesión (orientativamente, 2 semanas). A partir de una media ponderada de las notas de estos informes se calculará una nota de laboratorio, L.

- Un primer examen parcial, hecho hacia la mitad del curso, de la materia vista hasta entonces. Sea P1 la nota obtenida en este examen.

- En el día designado dentro del periodo de exámenes, el estudiante elegirá entre dos opciones exclusivas: 1) hacer un segundo examen parcial de la materia no cubierta por el primer parcial (que, en su caso, da una nota P2) o 2) hacer un examen final de toda la materia (que, en su caso, da una nota F). No hay ningún requisito de nota mínima en P1 a la hora de hacer esta elección.

Las cuatro notas L, P1, P2 y F están entre 0 y 10. La nota final de la asignatura será:

0.4*L + màxim(0.3*P1+0.3*P2, 0.6*F).

En cuanto a la nota de la competencia asociada a Trabajo personal, se calculará una nota numérica de la siguiente forma:

- Para el i-ésimo informe de laboratorio a entregar, el valor Ri valdrá 1 si el informe ha sido entregado dentro del plazo establecido y (a criterio del profesor) denota un esfuerzo razonable de resolución del trabajo correspondiente, y 0 en caso contrario. Sea Rsum la suma de todos los Ri (que puede llegar a ser k si se piden k informes).

- Algunas de las preguntas de los exámenes finales o parciales, marcadas especialmente, versarán total o parcialmente sobre temas que el estudiante deberá preparar por su cuenta, con poca o ninguna cobertura en clase de teoría y problemas, que se habrán indicado durante el curso. Sea E la nota ​​media ponderada de estas preguntas en los exámenes aplicables al estudiante, escalada al intervalo [0,1].

Sea S el valor de (Rsum/k+E)/2, que será entre 0 y 1.

La nota de la competencia será:
- D si S es inferior a 0.5
- C si S es entre 0.5 y 0.599
- B si S es entre 0.6 y 0.799
- A si S es 0.8 o más.

Bibliografía

Básica:

Web links

Capacidades previas

Genéricamente, las que se adquieren en las asignaturas del grado que son requisitos de la misma.

Específicamente:

- Usar con comodidad los conceptos básicos de álgebra lineal, matemática discreta, probabilidad y estadística.

- Programar con comodidad en lenguajes orientados a objetos, incluyendo herencia entre clases.

- Conocer las principales estructuras de datos para el acceso eficiente a información y sus implementaciones (listas, hashing, árboles, grafos, heaps). Ser capaz de usarlas para construir programas eficientes. Poder analizar el tiempo de ejecución y memoria usada por un algoritmo de dificultad media. Tener una cierta idea de la diferencia en tiempo de acceso entre memoria principal y memoria secundaria.

- Conocer los elementos principales de una base de datos relacional y de lenguajes de acceso tipo SQL.