liveBook · Manning

K-means clustering

As explained in Build AI Drug Discovery Pipelines

K-means clustering partitions data into a specified number of groups by iteratively assigning points to nearby centroids and recomputing the centroids.

K-means clustering partitions compound representations into a chosen number of groups by repeatedly assigning data points to nearby centroids and recomputing those centroids. It is useful for selecting diverse samples from ultra-large libraries when hierarchical clustering is too slow or memory-intensive. section 7.2.3

Its computational profile is described using:

  • Time complexity of O(k × n × i × d), where k is the number of centroids, n the number of data points, i the number of iterations, and d the number of features. section 7.2.3
  • Memory complexity of O((n + k) × d), storing the data points and centroids rather than a full pairwise distance matrix. section 7.2.3
  • A practical alternative to agglomerative clustering for datasets containing millions of compounds, especially after dimensionality reduction. section 7.2.3

How Build AI Drug Discovery Pipelines covers it

How deep it goes
Explains centroid-distance computation and asymptotic cost, but does not provide a worked fitting or sampling implementation.
Examples
Uses an ultra-large compound library represented in a 1K-plus-dimensional space as its motivating dataset.
What it assumes
Assumes familiarity with data points, dimensions, centroids, iterations, and dimensionality reduction.
What you can do after
Evaluate clustering methods by comparing their time and memory scaling for large compound datasets.
How it connects
Connects K-means with dimensionality reduction, agglomerative clustering, Taylor-Butina clustering, and Big O notation.

Also explained in

Compare how 12 books explain K-means clustering →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Build AI Drug Discovery Pipelines. The section links point to the parts of the book it draws on.