Web Mining

Laurea Magistrale in Computer Science
Academic year 2009-2010, second semester

Previous academic years: [ (2008/2009) ] [ (2007/2008) ]

Draft version of notes

The draft version of notes which will become a new book in the next weeks is available here (please observe that not all course topics are covered).

Students are very welcome to contribute by:

identifying errors
suggesting quotations to put in the different chapters
suggesting specific applications of interest
...

All contributions will be duly aknowledged in the final version of the book (which will be available for free to students from our web site).

Teachers

Mauro Brunato - E-mail brunato@disi.unitn.it
Roberto Battiti - E-mail battiti@disi.unitn.it

For email messages concerning the course requirements (e.g., assignments hand-in) please refer to Umut Avci.

Schedule

Monday 1600-1800, room 104
Thursday 0830-1030, room 22

Every student in the course is kindly asked to send a mail to Umut Avci containing name and matricola number. Every mail exchanged for purposes related to the course must be sent from the students' email account (name.surname@studenti.unitn.it) and contaning [webmining] in the subject.

Program

Web crawling
Web page indexing
Information retrieval
Unsupervised learning: clustering
PageRank and HITS
Search engine attack and defense strategies

See the detailed program below

Exam

Exams will consist of a written test (exercises) and an oral test (discussion of theory and, optionally, lab assignments).

Lab assignments

Assignments are optional (i.e., you can skip them) and personal (no collaboration); if done (in a satisfactory way), they will be the basis of the oral examination; otherwise, the oral will consist of questions about any part of the course program.

To hand in an assignment, your email should contain:

URL of requested document or targzipped source code (NOT attached to the email, but available in the student's web space);
Instructions for compilation and execution.
Name of the student.

Assigned/ Due	Subject	Selected contributions
2010-02-25 2010-03-01	Data collection and plotting [Assessments]	Mattia Avancini: Concrete slump test Nicola Dorigatti: Vinho verde quality Ivan Leonardi: Iris analysis and clustering Enrico Sartori: Glass identification

Bibliography

Official Textbook

OUMEN

HAKRABARTI

Mining the Web - Discovering knowledge from hypertext data

Course notes

Document retrieval and indexing (updated to 2010-03-11)
Clustering (updated to 2010-03-01)

Draft of the notes book

2010-03-11 version.

(Detailed) Program

February 15, 2010: Web crawlers
Crawling: parallel page fetching, DNS prefetching, two-level hashing for URLs, robots exclusion file.
February 18, 2010: Web crawlers, indexing
Crawling: robot traps, structure of a crawler.
Indexing: batch indexing and updates, index compression techniques.
Evaluating the performance of a retrieval system: Recall and precision.
February 22 - March 8, 2010: Similarity and clustering
Vector-space model (VSM): document and query representation. Proximity measures in TFIDF-space.
Introduction to clustering, agglomerative clustering.
Clustering by quantization error minimization: the "hard" and "soft" k-means algorithms.
Geometric embedding: Kohonen's Self Organizing Maps (SOMs).
Clustering and visualization via embeddings: Multidimensional scaling, projection and subspaces. Singular value decomposition. Latent Semantic Indexing.
Generative models for document distributions: the binary and multinomial model. Mixture models.
The Expectation-Maximization algorithm.
Introduction to collaborative filtering. Probabilistic models (Gibbs sampling) for the estimation of collaborative filtering parameters.
March 4-11, 2010: Document indexing and retrieval
Precision-recall tradeoff, relevance feedback (Rocchio's method, probabilistic feedback, Bayesian belief networks).
Mixed topics: text spamming, use of text in referring hyperlinks. Phrase queries: testing the independence of two terms.

(Future) Program

Mid March - April: Web search and information retrieval
Performance evaluation: recall-precision plots, interpolated precision, Break Even Point (BEP), F-measure. Relevance feedback in VSM, Rocchio's method. Probabilistic model of retrieval.
Probabilistic Relevance Feedback: Odds ratio and Bayesian Inference Networks.
Advanced Issues: spamming, internal tag structure and hyperlinking.
Maximum likelihood parameter estimates; the likelihood ratio test for term distribution dependence.
Approximate term matching.
The Jaccard similarity index, straightforward calculation, probabilistic definition, approximation by means of a randomized algorithm based on permutations.
May
Social network analysis: Introduction to PageRank and HITS.
The MapReduce framework.

Page maintained by Mauro Brunato