Lecture

Clustering Algorithms: K-Means vs Spectral Clustering

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

CS-421: Machine learning for behavioral data

Computer environments such as educational games, interactive simulations, and web services provide large amounts of data, which can be analyzed and serve as a basis for adaptation. This course will cover the core methods of user modeling and personalizatio ...

Description

This lecture covers two main clustering algorithms: K-Means and Spectral Clustering. K-Means is a popular method for partitioning data into clusters based on Euclidean distance, while Spectral Clustering is more flexible and does not assume specific cluster shapes. The lecture discusses the importance of choosing the right number of clusters and the optimal initialization for K-Means, as well as the selection of the similarity measure and number of clusters for Spectral Clustering. Practical examples include clustering students based on their effort and proactivity in a flipped classroom setting.

Official source

Ontological neighbourhood

Information engineering

Machine learning: Unsupervised learning

Related concepts (32)

Cluster analysis

Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense) to each other than to those in other groups (clusters). It is a main task of exploratory data analysis, and a common technique for statistical data analysis, used in many fields, including pattern recognition, , information retrieval, bioinformatics, data compression, computer graphics and machine learning.

K-means clustering

k-means clustering is a method of vector quantization, originally from signal processing, that aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean (cluster centers or cluster centroid), serving as a prototype of the cluster. This results in a partitioning of the data space into Voronoi cells. k-means clustering minimizes within-cluster variances (squared Euclidean distances), but not regular Euclidean distances, which would be the more difficult Weber problem: the mean optimizes squared errors, whereas only the geometric median minimizes Euclidean distances.

Hierarchical clustering

In data mining and statistics, hierarchical clustering (also called hierarchical cluster analysis or HCA) is a method of cluster analysis that seeks to build a hierarchy of clusters. Strategies for hierarchical clustering generally fall into two categories: Agglomerative: This is a "bottom-up" approach: Each observation starts in its own cluster, and pairs of clusters are merged as one moves up the hierarchy. Divisive: This is a "top-down" approach: All observations start in one cluster, and splits are performed recursively as one moves down the hierarchy.

Determining the number of clusters in a data set

Determining the number of clusters in a data set, a quantity often labelled k as in the k-means algorithm, is a frequent problem in data clustering, and is a distinct issue from the process of actually solving the clustering problem. For a certain class of clustering algorithms (in particular k-means, k-medoids and expectation–maximization algorithm), there is a parameter commonly referred to as k that specifies the number of clusters to detect.

Open cluster

An open cluster is a type of star cluster made of tens to a few thousand stars that were formed from the same giant molecular cloud and have roughly the same age. More than 1,100 open clusters have been discovered within the Milky Way galaxy, and many more are thought to exist. They are loosely bound by mutual gravitational attraction and become disrupted by close encounters with other clusters and clouds of gas as they orbit the Galactic Center.

Related lectures (64)

Time Series Clustering

Covers clustering time series data using dynamic time warping, string metrics, and Markov models.

Supervised Learning Overview

Covers CNNs, RNNs, SVMs, and supervised learning methods, emphasizing the importance of tuning regularization and making informed decisions in machine learning.

Clustering: Unsupervised Learning

Explores clustering in high-dimensional space, covering methods like hierarchical clustering, K-means, and DBSCAN.

Unsupervised Learning: Clustering Methods

Covers unsupervised learning focusing on clustering methods and the challenges faced in clustering algorithms like K-means and DBSCAN.

Clustering & Density Estimation