Lecture

K-Means: Implementation and Analysis

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

PHYS-467: Machine learning for physicists

Machine learning and data analysis are becoming increasingly central in sciences including physics. In this course, fundamental principles and methods of machine learning will be introduced and practised. ...

Description

This lecture focuses on the implementation and analysis of the K-Means algorithm. The instructor guides the students through generating Gaussian clusters, plotting them in a two-dimensional space, and implementing K-Means from scratch. The lecture covers how to assign points to clusters based on distances, compute the cost function, and update centroids iteratively. The instructor explains the importance of clever centroid initialization and demonstrates how noise affects the algorithm's performance. Additionally, the lecture showcases the comparison between the algorithm's computed centroids and the true means as noise levels increase, highlighting the algorithm's limitations in noisy data.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Instructor

Lenka Zdeborová

Lenka Zdeborová is a Professor of Physics and of Computer Science in École Polytechnique Fédérale de Lausanne where she leads the Statistical Physics of Computation Laboratory. She received a PhD in physics from University Paris-Sud and from Charles University in Prague in 2008. She spent two years in the Los Alamos National Laboratory as the Director's Postdoctoral Fellow. Between 2010 and 2020 she was a researcher at CNRS working in the Institute of Theoretical Physics in CEA Saclay, France. In 2014, she was awarded the CNRS bronze medal, in 2016 Philippe Meyer prize in theoretical physics and an ERC Starting Grant, in 2018 the Irène Joliot-Curie prize, in 2021 the Gibbs lectureship of AMS. She is an editorial board member for Journal of Physics A, Physical Review E, Physical Review X, SIMODS, Machine Learning: Science and Technology, and Information and Inference. Lenka's expertise is in applications of concepts from statistical physics, such as advanced mean field methods, replica method and related message-passing algorithms, to problems in machine learning, signal processing, inference and optimization. She enjoys erasing the boundaries between theoretical physics, mathematics and computer science.

Official source

Related concepts (18)

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.

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.

Noise control

Noise control or noise mitigation is a set of strategies to reduce noise pollution or to reduce the impact of that noise, whether outdoors or indoors. The main areas of noise mitigation or abatement are: transportation noise control, architectural design, urban planning through zoning codes, and occupational noise control. Roadway noise and aircraft noise are the most pervasive sources of environmental noise.

Noise pollution

Noise pollution, or sound pollution, is the propagation of noise or sound with ranging impacts on the activity of human or animal life, most of which are harmful to a degree. The source of outdoor noise worldwide is mainly caused by machines, transport and propagation systems. Poor urban planning may give rise to noise disintegration or pollution, side-by-side industrial and residential buildings can result in noise pollution in the residential areas.

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.

Related lectures (64)

Clustering & Density Estimation

Covers dimensionality reduction, PCA, clustering techniques, and density estimation methods.

Dimensionality Reduction: PCA and LDA

Covers dimensionality reduction techniques like PCA and LDA, clustering methods, density estimation, and data representation.

Unsupervised Behavior Clustering

Explores unsupervised behavior clustering and dimensionality reduction techniques, covering algorithms like K-Means, DBSCAN, and Gaussian Mixture Model.

Unsupervised Learning: Dimensionality Reduction and Clustering

Covers unsupervised learning, focusing on dimensionality reduction and clustering, explaining how it helps find patterns in data without labels.

K-Means Clustering: Image Compression