Cerca i Anàlisi d'Informació Massiva

Crèdits
6
Tipus
Complementària d'especialitat (Sistemes d'informació)
Requisits
Departament
CS
Mail
caim@cs.upc.edu
La quantitat d'informació emmagatzemada digitalment en moltes organitzacions, o col·lectivament en la web, és avui dia prou gran perquè trobar allò que es busca sigui generalment complicat. El camp conegut com a "Information Retrieval" tracta dels mètodes per organitzar informació i permetre després als usuaris trobar-la de manera còmoda i eficient. Cobrirem les tècniques bàsiques de cerca de documentació textual basada en paraules clau. Examinarem després el cas de la cerca en la web, on la presència d'hiperenllaços pot usar-se no sols per dirigir la cerca sinó per valorar l'interès de cada pàgina - és el cas del conegut algorisme PageRank. Veurem l'extensió d'aquestes tècniques al cas de les xarxes socials on el graf d'interaccions entre usuaris proporciona molta informació de què pot interessar a cadascun. Finalment, estudiarem maneres en què aquestes tècniques permeten explotar la informació per a les finalitats d'una organització en concret.

Professorat

Responsable

Altres

Hores setmanals

Teoria
1.5
Problemes
0.5
Laboratori
2
Aprenentatge dirigit
0
Aprenentatge autònom
6

Competències

Competències Tècniques de cada especialitat

Especialitat sistemes d'informació

  • CSI2 - Integrar solucions de Tecnologies de la Informació i les Comunicacions, i processos empresarials per a satisfer les necessitats d'informació de les organitzacions, permetent que assoleixin els seus objectius de forma efectiva.
    • CSI2.3 - Demostrar coneixement i capacitat d'aplicació dels sistemes d'extracció i de gestió del coneixement.
    • CSI2.6 - Demostrar coneixement i capacitat d'aplicació dels sistemes d'ajuda a la presa de decisions i de bussines intelligence.

    • Especialitat computació

  • CCO2 - Desenvolupar de forma efectiva i eficient els algorismes i el software apropiats per a resoldre problemes complexos de computació.
    • CCO2.5 - Implementar software de cerca d'informació (information retrieval).

    • Competències Transversals

    Aprenentatge autònom

  • G7 [Avaluable] - Detectar carències en el coneixement propi i superar-les mitjançant la reflexió crítica i l'elecció de la millor actuació per ampliar aquest coneixement. Capacitat per a l'aprenentatge de nous mètodes i tecnologies, i versatilitat per a adaptar-se a noves situacions.
    • G7.3 - Aprenentatge autònom: capacitat de planificació i organització del treball personal. Aplicar els coneixements adquirits a la realització d'una tasca en funció de la pertinença i de la importància, decidir la manera de dur-la a terme i el temps que se li ha de dedicar, i seleccionar les fonts d'informació més adients. Identificar la importància d'establir i mantenir contactes amb els companys d'estudis, amb el professorat i amb els professionals (networking). Identificar fòrums d'informació sobre enginyeria TIC, els seus avenços i el seu impacte en la societat (IEEE, associacions, etc.).

    • Objectius

    1. Conèixer els problemes associats a l'emmagatzemament i recuperació de la informació, sobretot de tipus textual.
      Competències relacionades: CCO2.5,
    2. Entendre que l'efectivitat en la cerca i recuperació de la informació està molt relacionada amb l'organització i descripció d'aquesta informació.
      Competències relacionades: CCO2.5, G7.3,
    3. Conèixer i entendre l'estructura, arquitectura i funcionament de la web, i els elements relacionats amb ella: índexos, cercadors, crawlers, entre altres.
      Competències relacionades: CSI2.3, G7.3,
    4. Conèixer i entendre els paràmetres de descripció de xarxes complexes, així com els algorismes principals d'anàlisi de la seva estructura.
      Competències relacionades: CSI2.3, CSI2.6, G7.3,
    5. Reconèixer les oportunitats d'ús de la informació massiva per als fins d'una organització, i triar els mètodes, eines i procediments més adients.
      Competències relacionades: CSI2.6, G7.3,
    6. Poder decidir les tècniques de recuperació de la informació que poden ser efectives en un sistema d'informació concret, sobretot de tipus textual.
      Competències relacionades: CSI2.3, CSI2.6, CCO2.5, G7.3,
    7. Poder avaluar l'efectivitat i utilitat, d'acord amb diversos criteris, d'un sistema de recuperació de la informació.
      Competències relacionades: CSI2.3, CSI2.6, CCO2.5, G7.3,
    8. Poder implementar les principals tècniques vistes a l'assignatura
      Competències relacionades: CCO2.5, G7.3,
      Subcompetences
      • Poder implementar les tècniques bàsiques (algorismes i estuctures de dades) de recuperació de la informació.
      • Poder implementar els algorismes bàsics d'anàlisi de xarxes.
    9. Saber utilitzar, adaptar i extendre software obert.
      Competències relacionades: G7.3,
      Subcompetences
      • Per exemple: Lucene, base de dades DEX, WIRE crawler, entre altres.

    Continguts

    1. Introducció
      Necessitat de les tècniques de cerca i anàlisi d'informació massiva. Cerca i anàlisi vs. bases de dades. Procés de recuperació de la informació. Preprocés i anàlisi lèxica.
    2. Models de recuperació de la informació
      Definició formal i conceptes bàsics: Models abstractes de documents i llenguatges d'interrogació. Model booleà. Model vectorial. Latent Semantic Indexing.
    3. Implementació: Indexació i cerques
      Fitxers invertits i fitxers de signatures. Compressió d'índexos. Exemple: Implementació eficient de la regla del cosinus amb mesura tf-idf. Exemple: Lucene.
    4. Avaluació en recuperació de la informació
      Recall i precisió. Altres mesures de rendiment. Col·leccions de referència. "Relevance feedback" i "query expansion".
    5. Cerca a internet
      Ranking i relevància per a models web. Algorisme PageRank. Crawling. Arquitectura de un sistema simple de cerca a la web.
    6. Arquitectura de sistemes pera la gestió d'informació massiva
      Escalabilitat, alt rendiment i tolerància a fallides: el cas de cercadors web massius. Arquitectures distribuïdes. Exemple: Hadoop.
    7. Anàlisi de xarxes
      Paràmetres descriptius i característiques de les xarxes: grau, diàmetre, xarxes "small-world", entre altres. Algorismes sobre xarxes: clustering, detecció de comunitats i de nodes influents, reputació, entre altres.
    8. Sistemes d'informació basats en l'explotació d'informació massiva. Combinació amb altres tecnologies.
      "Search Engine Optimization". Utilització de tècniques de recuperació de la informació en combinació amb Mineria de Dades i Aprenentatge. Sistemes de recomanació.

    Activitats

    Activitat Acte avaluatiu


    Introducció i Models de Recuperació de la Informació

    2 hores de teoria, 2 de problemes i 4 de laboratori sobre els continguts "Introducció" i "Models de recuperació de la informació". Vegeu descripcions a la Metodologia Docent.
    Objectius: 1 2 6
    Continguts:
    Teoria
    4h
    Problemes
    2h
    Laboratori
    6h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    13.5h

    Implementació i avaluació

    2 hores de teoria, 2 de problemes i 4 de laboratori sobre els continguts "Implementació" i "Avaluació". Vegeu descripcions a la Metodologia Docent.
    Objectius: 2 7 8 9
    Continguts:
    Teoria
    2.5h
    Problemes
    1h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    6.5h

    Cerca a la web

    2 hores de teoria, 2 de problemes i 4 de laboratori sobre el contingut "Cerca a la web". Vegeu descripcions a la Metodologia docent.
    Objectius: 3 5 9
    Continguts:
    Teoria
    2.5h
    Problemes
    1h
    Laboratori
    6h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    12.5h

    Primer examen parcial

    Examen parcial de la primera part de l'assignatura.
    Objectius: 1 2 3 5 6 7
    Setmana: 9
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Arquitectura de sistemes de cerca a la web

    2 hores de teoria i 6 de laboratori sobre els contingut "Arquitectura". Vegeu descripcions a la Metodologia Docent.
    Objectius: 3 6 8 9
    Teoria
    3.5h
    Problemes
    1.5h
    Laboratori
    6h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    12.5h

    Anàlisi de xarxes

    4 hores de teoria i 6 de laboratori sobre els contingut "Anàlisi de xarxes". Vegeu descripcions a la Metodologia Docent.
    Objectius: 4 6 7 8 9
    Continguts:
    Teoria
    3.5h
    Problemes
    1.5h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    12.5h

    Sistemes d'informació basats en anàlisi d'informació massiva

    Classes de teoria, problemes i laboratori sobre aquest contingut. L'èmfasi és en la discussió de casos pràctics a classe de problemes. Vegeu descripcions a la Metodologia docent.
    Objectius: 5 6 7 9
    Continguts:
    Teoria
    1.5h
    Problemes
    0.5h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    12.5h

    Segon examen parcial o examen final

    L'estudiant tria entre fer un examen de la segona meitat del curs, o bé un examen de tot el curs.
    Objectius: 1 2 3 4 5 6 7 8 9
    Setmana: 15 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Metodologia docent

    - Classes de teoria. Abans de cada classe, l'estudiant haurà d'haver llegit els apunts o materials del tema a desenvolupar, anunciat amb temps. L'estudiant tindrà també a la seva disposició un qüestionari de preguntes bàsiques del tema, per comprovar si el grau de comprensió que ha assolit. A la classe, el professor exposarà els punts principals, donant per suposat que l'estudiant ha fet la feina indicada i intentat respondre el qüestionari, i es discutiran en comú els dubtes que puguin haver trobat els estudiants.

    - Classes de problemes. Professors i estudiants comentaran i compararan les solucions dels problemes que el professor haurà indicat amb temps suficient abans de cada classe. Les discussions poden fer-se en comú entre tota la classe o particularment entre el professor i un alumne. El professor donarà per suposat que els estudiants han passat un temps raonable intentant resoldre aquests exercicis, i prioritzarà l'atenció a aquells que ho hagin fet així.

    - Classes de laboratori: Abans de cada classe, l'estudiant haurà d'haver llegit el guió de la feina pràctica a desenvolupar en la sessió. Durant la classe, l'estudiant durà a terme la feina indicada en el guió amb el guiatge del professor. En moltes de les sessions, el guió contindrà feina que, probablement, calgui acabar com a treball personal després de la sessió de laboratori. Per a la majoria de sessions de laboratori caldrà redactar un informe curt de la feina feta o lliurar aquesta feina (p.ex., fitxers de resultats i programes escrits).

    - Treball personal: Així doncs, cada tipus d'activitat presencial implica una certa quantitat de treball personal abans o després. Addicionalment, algun tema o temes de l'assignatura poden no tenir classes de teoria o d'exercicis associats, i els estudiants hauran d'estudiar-lo pel seu compte, i usar les sessions d'activitats dirigides si ho desitgen per avaluar que han fet el progrés suficient.

    Donat que l'assignatura apareix a dues especialitats diferents, podran proposar-se activitats (a teoria, problemes i laboratori) lleugerament diferents per als estudiants d'ambdues especialitats, vetllant perquè no hi hagi greuges comparatius pel que fa a dificultat o càrrega de treball.

    Mètode d'avaluació

    L'assignatura comprendrà els següents actes avaluatius:

    - Informes de les activitats de laboratori, que caldrà haver lliurat dins d'un termini indicat per a cada sessió (orientativament, 2 setmanes). A partir d'una mitjana ponderada de les notes d'aquests informes, es calcularà una nota de laboratori, L.

    - Un primer examen parcial, fet cap a meitat del curs, de la matèria vista fins llavors. Sigui P1 la nota obtinguda en aquest examen.

    - Un examen final, enfocat a la segona meitat del curs, però on pot entrar qualsevol part de l'assignatura. Sigui P2 la nota obtinguda en aquest examen.


    Les tres notes L, P1 i P2 són entre 0 i 10. La nota final de l'assignatura serà la mitjana de les tres notes.

    Pel que fa a la nota de la competència associada a Aprenentatge Autònom, es calcularà una nota numèrica així:

    - Per a l'i-èssim informe de laboratori a lliurar, el valor Ri valdrà 1 si l'informe ha estat lliurat dins del termini establert i (a criteri del professor) denota un esforç raonable de resolució de la feina corresponent, i 0 en cas contrari. Sigui Rsum la suma de tots els Ri (que pot arribar a ser k si es demanen k informes).

    - Algunes de les preguntes dels exàmens finals o parcials, marcades especialment, versaran total o parcialment sobre temes que l'estudiant haurà de preparar pel seu compte, amb poca o cap cobertura a classe de teoria i problemes, que s'hauran indicat durant el curs. Sigui E la mitjana ponderada d'aquestes preguntes en els exàmens aplicables a l'estudiant, i escalada a l'interval [0,1].

    Sigui S el valor de (Rsum/k+E)/2, que serà entre 0 i 1.

    La nota de la competència serà:
    - D si S és inferior a 0.5
    - C si S és entre 0.5 i 0.599
    - B si S és entre 0.6 i 0.799
    - A si S és 0.8 o més.

    Bibliografia

    Bàsic

    Web links

    Capacitats prèvies

    Genèricament, les que s'adquireixen a les assignatures del grau que són requisits d'aquesta.

    Específicament:

    - Usar amb comodidat els conceptes bàsics d'àlgebra lineal, matemàtica discreta, probabilitat i estadística.

    - Programar amb comoditat en llenguatges orientats a objectes, incloent herència entre classes.

    - Conèixer les principals estructures de dades per a l'accés eficient a informació i les seves implementacions (llistes, hashing, arbres, grafs, heaps). Ser capaç d'usar-les per a construir programes eficients. Poder analitzar el temps d'execució i memòria usat per un algorisme de dificultat mitjana. Tenir una certa idea de la diferència en temps d'accés entre memòria principal i memòria secundària.

    - Conèixer els elements principals d'una base de dades relacional i de llenguatges d'accés tipus SQL.