List of theory topics

These materials should not be considered final until the end of the course. Materials from previous editions can be found in other branches of the repository for the course.

There are 11 theory sessions of 2 hours each. They will all take place face-to-face. Please bring your laptop.

Before each class, there are short videos you should watch. They are up to 20 minutes in total, and watching them requires some preparation/scheduling on your part. Please set aside time in your schedule to watch these videos before coming to class, ideally on the day before.

During class, I will present the contents using slides and we will do together some exercises using Nearpod or Google Spreadsheets. Please avoid distractions: place your phone in airplane mode, close all other windows in your computer, and try to stay focused. We will pause frequently during the session to help you regain focus. In one of the sessions, a midterm exam will be taken, and at the end of the course, a final exam will be taken. The exam questions are based exclusively on the materials shown or discussed in the lectures during class.

After each session, there is some reading for you to do. These readings will be much easier after you have attended each lecture, will bring depth to what you learn in class, and will help you remember these contents better. Think of these readings as a form of continuous studying that will save you time and effort when preparing for the exams.

Session 1: Introduction

Before class

• Watch this 6-minutes presentation of the Knowledge Discovery in Databases process by Ali Soofastaei
• Take a look at the list of theory topics, practice sessions, and evaluation rules

During class

• Lecture TT01: introduction ppt/pdf
• Course overview
  • Overview of theory topics
  • Overview of practice sessions
  • Overview of evaluation rules
• Lecture TT02: data, methods, and scenarios ppt/pdf
  • Exercise: confidence of a rule
  • Exercise: which ones are data mining tasks? (pin board)
• Lecture TT03: data preparation, data types ppt/pdf
  • Exercise: compute binning (spreadsheet)

After class

• Read chapter 1 of Data Mining, The Textbook (2015)
• Read the beginning of chapter 2 (up to section 2.2 inclusive) of Data Mining, The Textbook (2015)

Optional/additional material

• Strongly recommended to help you prepare for the practice sessions: tutorials 1 and 2 of the book by Tan et al. These tutorials are an introduction to Python, which you should do unless you are very comfortable with this language, and about numpy and pandas, which will save you a ton of time in the practices.
• Read data sources and biases free book chapter of the Trustworthy Machine Learning book.

Session 2: Data cleaning

Before class

• Watch this 14-minutes talk and demo on Cleaning Data by Mike Pound; his examples use R but the same can be done in many languages.

During class

• Lecture TT04: data integration and cleaning ppt/pdf
  • Exercise: how to handle missing data
• Lecture TT05: data reduction and transformation ppt/pdf
• Lecture TT06: similarity computation on numerical data ppt/pdf
  • Exercise: compute Lp norm

After class

• Read the rest of chapter 2 (sections 2.3 and following) of Data Mining, The Textbook (2015)
• Read the beginning of chapter 3 (up to section 3.2.1) of Data Mining, The Textbook (2015)
• If the concept of dimensionality reduction still sounds pretty alien to you, watch this 12-minutes lecture on dimensionality reduction by Jure Leskovec

Optional/additional material

• Tutorials 3 and 4 of the book by Tan et al. cover issues of data exploration and data pre-processing. The latter is quite similar to our first practice session, but uses a different dataset.

Session 3: Near duplicates

Before class

• Watch this 3-minutes video on Jaccard similarity by Victor Axelsson

During class

• Lecture TT07: similarity computation beyond numerical data ppt/pdf
  • Exercise: compute Jaccard similarity
• Lecture TT08: finding near-duplicates ppt/pdf
  • Exercise: compute signature matrix
• Lecture TT09: locality-sensitive hashing ppt/pdf [SKIPPED IN 2022 – NOT TO BE INCLUDED IN EXAMS]

After class

• Read the rest of chapter 3 (section 3.2.2 and following) of Data Mining, The Textbook (2015)
• Read chapter 3 of Mining Massive Datasets

Optional/additional material

• Watch this 37-minutes lecture by Ben Langmead on Jaccard coefficient and min-hashing
• Watch Jeffrey D. Ullman, a famous computer scientist and co-author of one of the books we use in the course and of this method specifically describe this near-duplicate finding method. Two 50-minutes videos: part 1, part 2.
• See presentation TT10: locality-sensitive hashing additional materials ppt/pdf

Session 4: Itemsets

Before class

• Watch the first 8 minutes of this animated video explanation of the Apriori algorithm, for an explanation of the concepts of itemsets, support, confidence, and lift.

During class

• Lecture TT11: itemsets ppt/pdf
  • Exercise: compute itemset support (spreadsheet)
  • Exercise: compute maximal itemsets
• Lecture TT12: association rules ppt/pdf
  • Exercise: compute support, confidence, and lift of a rule

After class

• Read the rest of chapter 3 (section 3.2.2 and following) of Data Mining, The Textbook (2015)
• Read chapter 3 of Mining Massive Datasets
• Read section 6.1 of Mining Massive Datasets
  • Or read section 4.1 of Data Mining, The Textbook (2015)

Session 5: Association rules mining

Before class

• Watch the rest of the explanation of the Apriori algorithm, starting at mark 07:58.

During class

• Lecture TT13: association rules mining ppt/pdf
  • Exercise: prove confidence monotonicity
  • Exercise: execute Apriori algorithm (spreadsheet)
• Lecture TT14: speeding up association rules mining ppt/pdf
  • Exercise: indicate which items are visited in a hash tree

After class

• Read section 6.2 of Mining Massive Datasets
  • Or read section 4.2-4.4 of Data Mining, The Textbook (2015)

Optional/additional material

• See presentation TT15: extending association analysis ppt/pdf
• If you did not understand well the hash tree, watch these four videos (18 minutes in total) from the J. Academy: support counting using hash tree (part 1), support counting using hash tree (part 2), hash tree generation step by step, hash tree and support counting; if you find this easy to follow check their entire playlist on association rules mining.

Session 6: Mid-term exam (Wednesday October 25th, 2023)

Before class

Study on your own TT01-TT08, TT11-TT13, try to solve exams from past years. Ask your questions in the forum.

The exam will not include TT09, TT10 or TT14.

During class

We will have a mid-term exam, with no class after the mid-term.

Session 7: Recommender systems

Before class

• Watch the 6-minutes presentation of an introduction to recommender systems
• Watch the 17-minutes introductory lecture to recommender systems by Anand Rajaraman

During class

• Lecture TT16: recommender systems ppt/pdf
  • Exercise: content-based single-user recommendations (spreadsheet)
• Lecture TT17: interaction-based recommender systems ppt/pdf
  • Exercise: recommender based on user similarity (spreadsheet)

After class

• Read sections 9.1-9.3 of Mining Massive Datasets
• Watch the two 21-minutes lectures on content-based recommender systems and collaborative filtering by Anand Rajaraman

Session 8: Recommender systems (cont.) + Outlier analysis

Before class

• Watch the 7-minutes lecture on outlier analysis by Gourab Nath, discussing why outliers occur

During class

• We will watch this 8-minutes presentation on how recommender systems work by Art of the Problem, which describes a factorization-based (latent-factors based) method
• Lecture TT18: latent-factors based recommender systems ppt/pdf
• Lecture TT19: outliers introduction and extreme value analysis ppt/pdf
  • Exercise: outliers using z-score (spreadsheet)
• Lecture TT20: probability and clustering-based methods ppt/pdf
  • Exercise: clustering-based outlier detection (spreadsheet)

After class

• Read sections 9.4-9.5 of Mining Massive Datasets
• Read chapter 8 (except 8.5) of Data Mining, The Textbook (2015)

Optional/additional material

• If you did not understand the latent factors method, watch this 33-minutes presentation on How does Netflix recommend movies? Matrix Factorization

Session 9: Outlier analysis (cont.) + Data streams

Before class

• Watch this 14-minutes talk and demo on isolation forests in Python
• Watch this 4-minutes animation on reservoir sampling by Eric Laber

During class

• Lecture TT21: density- and isolation-based methods ppt/pdf
  • Exercise: isolation forest example
• Lecture TT22: data streams ppt/pdf
  • Exercise: sampling at a fixed rate
• Lecture TT23: reservoir sampling ppt/pdf
  • Exercise: probabilities in a reservoir sample

Note for 2022 – need to finish outlier detection on this class - isolation forest - for practice sessions to have the necessary background.

After class

• Read sections 4.1 and 4.2 of Mining Massive Datasets
• Read section 8.5 of Data Mining, The Textbook (2015)

Optional/additional material

• Read the original ICDM 2008 paper on isolation forests – do not worry if you cannot follow all the details

Session 10: Streams (cont.) + Time series mining

Before class

• Watch this 3-minutes quick presentation on bloom filters by Cube Drone

During class

• Lecture TT24: bloom filters ppt/pdf
  • We will watch this 6-minutes animation on Bloom Filters
• Lecture TT25: probabilistic counting ppt/pdf
  • Exercise: ideas for simple probabilistic counting
• Lecture TT27: time series ppt/pdf
  • Exercise: smooth a time series (spreadsheet)

Note for 2022 – need to finish probabilistic counting for practice session on probabilistic counting to have the necessary background

After class

• Read sections 4.3 and 4.4 of Mining Massive Datasets
• Read sections 14.1 and 14.2 of Data Mining, The Textbook (2015)

Optional/additional material

• See presentation TT26: moments estimation ppt/pdf

Session 11: Time series mining (cont.)

Before class

• Watch this 7-minutes talk on the moving average model and this 9-minutes talk on the autoregressive model.

During class

• Lecture TT28: time series similarity ppt/pdf
  • Example: dynamic time warping (spreadsheet)
• Lecture TT29: time series forecasting ppt/pdf
  • Example: simple auto-regressive model (spreadsheet)

Note for 2023 – need to finish forecasting for practice session on temperature prediction to have the necessary background

After class

• Read section 14.3 of Data Mining, The Textbook (2015)

Final exam (Wednesday, December 13th, 2023)

The final exam will include recommender systems, outlier analysis, data streams, and forecasting: topics TT16-TT25, TT27-TT29; it will not include topic TT26.

Notes

Note that session numbers are approximate and subject to change.

Slides available under a Creative Commons license unless specified otherwise.

Main bibliography

Data Mining, The Textbook (2015) by Charu Agrawal. ISBN 978-3-319-14142-8. Free Download

Mining of Massive Datasets SECOND EDITION (2014) by Leskovec et al. ISBN 978-1107077232. Online materials: http://www.mmds.org/. Free Download

Additional bibliography

Introduction to Data Mining SECOND EDITION (2019) by Tan et al. ISBN 978-0-13-312890-1. Online materials: https://www-users.cs.umn.edu/~kumar001/dmbook/index.php

Data Mining and Machine Learning SECOND EDITION (2020) by Zaki and Meira. ISBN 978-1108473989.

Data Mining Concepts and Techniques THIRD EDITION (2011) by Han et al. ISBN 978-0123814791.