Cerca i Anàlisi d'Informació Massiva

Esteu aquí

Inici » Estudis » Graus » Grau en Enginyeria Informàtica » Pla d'estudis » Assignatures » Cerca i Anàlisi d'Informació Massiva
Crèdits
6
Tipus
Complementària d'especialitat (Sistemes d'informació)
Requisits
  • Prerequisit: BD
  • Prerequisit: PE
  • Corequisit: PROP
Departament
CS
Web
http://www.cs.upc.edu/~caim/
Mail
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

  • Ramon Ferrer Cancho ( )

Altres

  • Albert Calvo Ibañez ( )
  • Ignasi Gómez Sebastià ( )
  • Javier Béjar Alonso ( )
  • Jose Luis Balcázar Navarro ( )
  • Marta Arias Vicente ( )

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
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
8h

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
3h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
12h

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 avaluatoris:

- Informes de les activitats de laboratori, que caldrà haver lliurat dins 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.

- En el dia designat dins del període d'exàmens, l'estudiant triarà entre dues opcions exclusives: 1) fer un segon examen parcial de la matèria no coberta pel primer parcial (que, si és el cas, dóna una nota P2) o 2) fer un examen final de tota la matèria (que, si és el cas, dóna una nota F). No hi ha cap requisit de nota mínima a P1 a l'hora de fer aquesta tria.

Les quatre notes L, P1, P2 i F són entre 0 i 10. La nota final de l'assignatura serà:

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

Triar fer l'examen final implica P2 = 0. Triar el segon parcial implica F = 0. 
No presentar-se el dia de l'examen final / segon parcial implica que l'estudiant ha triat segon parcial.

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àsica:

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.