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

Créditos
6
Tipos
Complementaria de especialidad (Sistemas de Información)
Requisitos
Departamento
CS
Mail
caim@cs.upc.edu
La cantidad de información almacenada digitalmente en muchas organizaciones, o colectivamente en la web, es hoy en día lo suficientemente grande para que encontrar lo que se busca sea generalmente complicado. El campo conocido como "Information Retrieval" trata de los métodos para organizar información y permitir después a los usuarios encontrarla 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 ¿ es el caso del conocido algoritmo PageRank. Veremos la extensión de estas técnicas en el caso de las redes sociales donde el grafo de interacciones entre usuarios proporciona mucha información de lo que puede interesar a cada uno. Por último, estudiaremos algoritmos aleatorios eficientes para flujos de datos masivos.

Profesorado

Responsable

  • David Garcia Soriano (david.garcia.soriano@upc.edu)
  • Marta Arias Vicente (marias@cs.upc.edu)

Horas semanales

Teoría
1.5
Problemas
0.5
Laboratorio
2
Aprendizaje dirigido
0
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 [Avaluable] - 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 las 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. Búsqueda en grandes volúmenes de datos
      Ranking y relevancia para modelos web. Algoritmo PageRank. Crawling. Arquitectura de un sistema simple de búsqueda en la web. Técnicas basadas en tablas de hashing sensibles a la proximidad (LSH).
    3. 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. Archivos invertidos y archivos de firmas. Compresión de índices. Ejemplo: Implementación eficiente de la regla del coseno con medida tf-idf.Recall y precisión. Otras medidas de rendimiento. Colecciones de referencia. "Relevance feedback" y "query expansion".
    4. 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.
    5. 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.
    6. Algoritmos para datos masivos
      Resúmenes (sketches) y flujos de datos (streaming). Muestreo (sampling). Se verán algoritmos como RESERVOIR SAMPLING, count-min sketch, hyper-log-log, etc.

    Actividades

    Actividad Acto evaluativo


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


    Objetivos: 1 2 6
    Contenidos:
    Teoría
    4.5h
    Problemas
    3h
    Laboratorio
    10h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    16h

    Búsqueda en grandes volúmenes de datos


    Objetivos: 3 5 9
    Contenidos:
    Teoría
    3.5h
    Problemas
    1h
    Laboratorio
    6h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    12.5h

    Primer examen parcial

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

    Arquitectura de sistemas de búsqueda en la web


    Objetivos: 3 6 8 9
    Contenidos:
    Teoría
    4h
    Problemas
    1h
    Laboratorio
    4h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    8.5h

    Análisis de redes


    Objetivos: 4 6 7 8 9
    Contenidos:
    Teoría
    3.5h
    Problemas
    1.5h
    Laboratorio
    4h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    12.5h

    Algoritmos para datos masivos


    Objetivos: 5 8
    Contenidos:
    Teoría
    2h
    Problemas
    1h
    Laboratorio
    4h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    12h

    Segundo examen parcial o examen final


    Objetivos: 1 2 3 4 5 6 7 8 9
    Semana: 15 (Fuera de horario lectivo)
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Primera prueba de laboratorio


    Objetivos: 1 2 3 4 5 6 7 8 9
    Semana: 6
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    Segunda prueba de laboratorio


    Objetivos: 1 2 3 4 5 6 7 8 9
    Semana: 14
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    0h

    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.

    Método de evaluación

    La asignatura comprenderá los siguientes actos evaluativos:

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

    - Un segundo examen parcial, enfocado en la segunda mitad del curso, pero donde puede entrar cualquier parte de la asignatura. Sea P2 la nota obtenida en este examen.

    - Dos pruebas presenciales de laboratorio. Sea L la nota media obtenida de estas dos pruebas.

    Las tres notas L, P1 y P2 son entre 0 y 10.
    La nota final de la asignatura será el resultado de la fórmula 20% L+40% P1+40% P2.

    Por lo que respecta a la nota de la competencia asociada a Aprendizaje Autónomo, se calculará una nota numérica así:

    - Algunas de las preguntas de las pruebas presenciales evaluatorias, 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 S la media de estas preguntas en los exámenes aplicables al estudiante, y escalada en el intervalo [0,1].

    La nota de la competencia será:
    - D si S es inferior a 0.3
    - C si S es entre 0.3 y 0.499
    - B si S es entre 0.5 y 0.699
    - A si S es 0.7 o más.

    Bibliografía

    Básico

    Complementario

    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.