Clustering is a basic tool used in data analysis, pattern recognition and machine learning for finding groups in data. K-means is still the most popular algorithm in clustering. But is it good enough? How to decide how many clusters? What if the data is non-numerical like categorical, graph, text or more complex objects like GPS trajectories? Outliers, noise and missing values also degrade the clustering performance so how to deal with these problems? Besides these problems, clustering problem is like other optimization problems. It consists of the following three main design problems: (1) define distance function suitable for the data, (2) select cost function to measure goodness of the clusters, (3) design algorithm to optimize for the cost function.
Course will be arranged as a series of (1) Youtube video lectures; (2) exercises every Friday; (3) Series of mini-exams (to be implemented later) or classical 4 hour offline exam. Students will also be required to implement clustering program that will be gradually extended during the exercises. Suitable programming languages are Python, C, C++, C#, Java, JavaScript, R, Matlab, PHP, Go, Ruby.
Lecturer: Pasi Fränti
Course assistant: Jimi Tuononen
Start-up lecture Tuesday 16.1. at 14-16 Teams
Video lectures (~28h): Youtube
Exercises (7 or 8): Tuesday 10-12: Teams
16.1. Introduction to clustering (START-UP lecture on-line)
Exercise sessions:
23.1. Introduction to clustering and terminology
30.1. K-means, Fast k-means, Random swap
6.2. Graph clustering, Mumford-Shah k-means
13.2. Cost functions, text clustering, clustering of web pages
20.2. Clustering evaluation, outlier detection
27.2. Number of clusters, location-based data
5.3. Divisive clustering, Genetic algorithm
12.3. Either "Density peaks, case study" or "Agglomerative clustering (on-line + discussion)"
The date indicates that the topic will be discussed on that day's exercise session. The given material (video and powerpoint) and exercises should be studied before that day.
Exercise 1
Exercise 2
Exercise 3
Exercise 4
Exercise 5
Exercise 6
Exercise 7
Submit your exercises in Elearn (key: "clustering")
Design & Analysis of Algorithms
15.3. 12-16, Room M100 (Joensuu), Room MD100 (Kuopio)
26.4. 12-16, Room M100 (Joensuu), Room MD100 (Kuopio)
Clustering data
Software
Clusterator
Animator
Lectures Notes and material from 2014