—

Data Mining

Clustering and K-Means

Published: 2026-08-05

Level: postgraduate

Audience: Postgraduate students in Data Mining

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Clustering basics — definition, similarity by distance, hard and soft clustering, clustering applications — covered in Lecture 2 (Clustering and Clustering Applications)
Supervised versus unsupervised learning — only X versus pairs (X, Y) — covered in Lectures 5 and 6 (Supervised and Unsupervised Learning)
The four attribute types — nominal, ordinal, interval, ratio — covered in Lecture 3 (Data and Data Preprocessing)
Euclidean distance and the curse of dimensionality — covered in Lecture 9 (K-Nearest Neighbor and Ensemble Methods)
Outliers versus noise — covered in Lecture 4 (Outlier Analysis and Noise Handling)

This session opens the clustering module (module six). It starts with a fast recap of the last class — supervised learning and the idea of a decision boundary — and then moves into the heart of the module: what clustering is, why it is a genuinely hard and subjective problem, the full taxonomy of clustering types and cluster types, the requirements a good clustering algorithm should satisfy, and a first deep pass over the K-means algorithm with its four steps and its convergence behavior.

The module is organized in a deliberate order. First come the abstract concepts: the definition of a cluster, the many ways to slice the clustering space (hard versus soft, flat versus hierarchical, and so on), the kinds of clusters that can come out of an algorithm, and the properties a good clustering algorithm should have. Only after these concepts are in place does the course look at five concrete algorithms: K-means (the classic distance-based method), agglomerative hierarchical clustering, divisive hierarchical clustering, DBSCAN (the density-based method), and a grid-based algorithm. The same module later links each algorithm to the kind of problem it suits best.

Why this order matters: clustering is a subjective job. If you do not know the different ways clustering can be done, you will not be able to choose the right algorithm for a dataset — and you will not be able to tell which performance measure applies to which algorithm. The abstract view is the foundation; the algorithms are the building blocks on top of it.

13.1 From Supervised to Unsupervised Learning

13.1.1 Supervised Learning Recap

Everything seen so far in the course was supervised learning. In supervised learning, a training data set is given to us, and it includes two things: the data points $X$ and the corresponding label. The data set is a sequence of pairs: data point $X_{1}$ with its label $Y_{1}$ , another data point $X_{2}$ with label $Y_{2}$ , $X_{3}$ with $Y_{3}$ , and so on. Each data set row is a point plus its class label.

The supervised setup: a training set of pairs ${(X_{1}, Y_{1}), (X_{2}, Y_{2}), \dots, (X_{n}, Y_{n})}$ , where $X_{i}$ is a data point (for example, a student's marks, or an image) and $Y_{i}$ is its class label (for example, "pass" or "fail"). The label is the answer: someone looked at each $X_{i}$ and told the algorithm which class it belongs to. That labeled answer is exactly what makes learning "supervised" — the learning has a teacher.

If we project all these points into a two-dimensional vector space, the goal is to come up with a classification boundary that separates the two classes. This boundary is called the decision boundary, and it can be built using decision trees, SVM, neural networks, ensembles, and similar tools.

Picture the visualization: the horizontal axis is feature one, the vertical axis is feature two. Points of class one cluster in one region, points of class two in another. The decision boundary is the curve (or line, or zig-zag) drawn between them — every point on one side of the boundary is predicted as class one, every point on the other side as class two. Whatever tool we use — a decision tree's split rules, an SVM's maximum-margin line, a neural network's learned weights, an ensemble that averages several models — the output is the same kind of object: a boundary that separates labeled classes.

13.1.2 Unsupervised Learning

What we start now is different: unsupervised learning. The data set is not the same — in unsupervised learning we are given only $X$ . The data comes as $X_{1}, X_{2}, X_{3}, X_{4}$ , and so on: unlabeled data. And the task is to find patterns and structures in the data, without any label telling us the "right answer".

The key shift: supervised learning gets both $X$ and $Y$ , and the job is to predict $Y$ from $X$ . Unsupervised learning gets only $X$ — no labels at all — and the job is to discover something interesting about the data itself: patterns, groups, structure. There is no teacher, no correct answer waiting to be checked.

Clustering is one type of unsupervised learning, and the clustering aim is to find patterns and structures in the data. A pattern you can see in a typical clustering diagram: a handful of points are very close to each other, another handful are close to each other, and the groups sit far apart. If distance is a measure of similarity, then the points inside one group are more similar to each other than they are to any point from another group.

An everyday picture helps: imagine you are handed a huge mixed pile of photographs and told to sort them into stacks "by what they look like", with no captions on any photo. You will naturally put similar-looking pictures together — the sunset photos form one pile, the group selfies another. That act of sorting with no labels is exactly the clustering mindset: no answer key exists; the groups emerge from how similar the items are.

13.2 What Is Clustering

13.2.1 The Definition

Given a set of data points, we want to find groups, or clusters, in that data. The full definition has two parts. First: data points in one group or cluster are more similar to one another — the points are homogeneous in nature, meaning very much the same as each other. Second: data points in separate groups or clusters are less similar to one another.

The first and most important part: clustering does not need the class label. We just have data points $x_{1}, x_{2}, x_{3}, \dots$ , and the job is to find groups. In a two-dimensional vector space, by looking at distances we can say "these points are close to each other, these are close, these are close" — three groups, A, B, and C — and almost all the points of cluster A are very similar to each other, likewise for B and C, while a point from A and a point from B are dissimilar from each other.

The formal idea: given a set of $n$ data points $x_{1}, x_{2}, \dots, x_{n}$ in some space, partition them into $k$ groups (clusters) such that:

High intra-cluster similarity — points inside the same cluster are much alike (homogeneous within the group).
Low inter-cluster similarity — points from different clusters are unlike each other (heterogeneous between groups).

There is no label anywhere in this description — the input is only the points.

The idea of clustering is to find natural groups in the data. Natural groups can be derived based on distance, based on density, or based on some other measure — we are going to see all of these. What counts as "natural" is not fixed: the same data can hold different natural groupings depending on which measure of similarity we pick, and that flexibility is both the power and the difficulty of clustering (Section 13.4).

13.2.2 High Intra-Cluster Similarity, Low Inter-Cluster Similarity

The basic aim of clustering, stated as a maxim: clustering organizes data into clusters such that high intra-cluster similarity is there — points inside one cluster should be similar to each other, and this similarity must be maximized — and low inter-cluster similarity is there — if you take two points from two different clusters, there should be less similarity between them.

The word intra means inside, and the word inter means between. So intra-cluster similarity is the cohesiveness within a cluster, and inter-cluster similarity is the distinctiveness between clusters.

Scope — where this maxim comes from and where it stops: the maxim tells us what a good clustering looks like, but it does not tell us how to measure "similar". Distance is one measure, density another, graph edges another (Section 13.7.5). The maxim is the goal; choosing a similarity measure is a design decision the user must make — and different choices produce different groupings of the same data. The professor's summary: "You have to find patterns and structures, hidden patterns and structures in the data. You have to define similarity measures as well as how you are going to implement it."

13.2.3 Distance as a Similarity Measure

Suppose we choose similarity based on distance. If the distance is small, we say those two points are similar to each other; if the distance is far, we say they are very dissimilar. Distance is one measure — there are other measures too, and we look into all of them later.

Worked micro-example — four points on a line. Take points at positions 1, 2, 8, and 9 on a number line, and use distance as the similarity measure.

Distance between 1 and 2: $∣ 1 - 2 ∣ = 1$ — small distance, so these two are similar.
Distance between 8 and 9: $∣ 8 - 9 ∣ = 1$ — small distance, so these two are similar.
Distance between 2 and 8: $∣ 2 - 8 ∣ = 6$ — large distance, so a point from the left pair and a point from the right pair are dissimilar.

Natural groups fall out by eye: ${1, 2}$ is one cluster, ${8, 9}$ another. The two clusters have high intra-cluster similarity (distance 1) and low inter-cluster similarity (distance 6). Sense-check: if distance were replaced by a different measure — say, "both points are odd" — the groups would be completely different ( ${1, 9}$ versus ${2, 8}$ ), which is exactly why the choice of measure matters.

13.3 Clustering versus Classification

13.3.1 The Two Paradigms

The two paradigms differ in a stark way.

Clustering is unsupervised learning: we do not need training data with labels. Only the points $X_{1}, X_{2}, X_{3}$ are given, there is no class label, and we use statistical concepts to do similarity computation.
Classification is supervised learning: we need data points with class labels, and we want to build a model — that is the point of classification. We build the model because we want to do prediction for unseen samples. Using whatever classifier we choose, we build the model and then do prediction for unknown samples.

So clustering is for extracting patterns in the data, while classification is about prediction for unseen or unknown samples.

Dimension	Clustering	Classification
Learning type	Unsupervised	Supervised
Input	Unlabeled points $X_{1}, X_{2}, \dots, X_{n}$	Labeled pairs $(X_{i}, Y_{i})$
Goal	Find groups / patterns in the data	Build a model that predicts labels
Output	Clusters (assignments of points to groups)	Predicted class label for each new point
Evaluation	Performance measures of cluster quality (e.g., homogeneity)	Accuracy and similar metrics against known labels

13.3.2 What Each One Is For

Clustering extracts patterns; classification predicts. This difference is why the two problems are set up so differently: clustering starts with unlabeled points and ends with groups, while classification starts with labeled points, builds a model, and ends with predictions on new data.

When to pick which: use classification when a label exists (or can be created) and you want to predict it for future data — "will this customer default?" Use clustering when there is no label and you want to understand the structure of the data itself — "what kinds of customers exist at all?" The two can work together: clustering can create labels that classification later learns from (Section 13.5.3).

13.4 Why Clustering Is Hard: Subjectivity

Clustering is an extremely hard problem — and you will understand why. It is very subjective in nature. We can use clustering for a lot of applications, but it remains subjective. In classification, the end of the day is a predicted class label or a regression value, and you have performance measures like accuracy to score the result. Clustering is different: you have to define what sort of groups you want to extract, and there can be various groups. If I have thousands of students, there is no common notion of how many groups there are or what type of groups I should see. As a user, I have to tell the algorithm which sort of groups I need, and the clustering algorithm should be able to give me that.

The problem in one sentence: classification has an answer key (the labels), so you can measure how right you were. Clustering has no answer key — the "right" grouping depends on what the user wants to see, and the user has to communicate that to the algorithm (for example, by passing the number of clusters $k$ ).

13.4.1 The Grouping-Students Example

Take a university campus with roughly 4,000 students. How can we group them?

Group by department: computer science students fall into one group, electronics students into another, mechanical students into another, and so on.
Group by hostel: the campus has roughly 15 hostels, so students can be grouped by which hostel they stay in — hostel one, hostel two, hostel three, and so on.
Group by club: students can be grouped by which club they are enrolled in — the robotics club, the dance club, and so on.

Same 4,000 students, three completely different groupings, and none of them is "wrong". Grouping is very subjective. If I have 4,000 students, there is no common notion of how many groups there are or what type of groups I want to see.

Worked example — one campus, three valid answers. The same data set (4,000 students, each with attributes like department, hostel, club) can be clustered in (at least) three defensible ways:

By department → a handful of large groups (computer science, electronics, mechanical, ...). Useful if the goal is academic administration.
By hostel → roughly 15 groups, one per hostel. Useful if the goal is residential planning.
By club → many smaller groups (robotics, dance, ...). Useful if the goal is extracurricular planning.

Each clustering is internally consistent: within each group, students share the chosen attribute; across groups, they differ on it. Yet no single clustering is "the correct one". Conclusion: the answer depends on what the user wants, not on the data alone. Sense-check: add a fourth attribute (age) and you get a fourth perfectly good clustering — the point is not which is right, but that the user must choose the similarity notion.

13.4.2 The Two-Images Example

The same point can be seen with two pictures. Ask: are these two images similar in terms of their eyes? Yes — both images have two eyes, so they are similar in that notion. Are they similar based on their hair? Yes — very similar in terms of hair. But ask whether they are similar based on the species they belong to, and they are different. The same set of data points, or images, can be similar or dissimilar depending on the similarity notion you choose. That is why clustering is an extremely hard problem and very subjective in nature. Researchers have given a lot of parameters and a lot of metrics to quantify things, and we see them one by one.

Worked example — the same two images, judged twice. Two photographs, compared on three different notions of similarity:

Similarity by "has two eyes": both have two eyes → similar (yes).
Similarity by "hair": both have similar hair → similar (yes).
Similarity by "species": they are different species → dissimilar (no).

Same pair of objects, opposite verdicts, all of them correct under their own measure. The similarity notion is not a fact about the data; it is a choice made by the analyst. Sense-check: this is why clustering output can never be declared right or wrong without stating the measure — the measure decides the groups.

13.4.3 The "How Many Clusters?" Demo

The professor put a data set on screen and asked everyone to type into the chat box how many clusters they could visualize. Answers came back as two, three, four, and six. That is the point: someone would visualize two clusters, someone four. Nobody is right and nobody is wrong — all of you might be correct, all of you might be wrong. Clustering is subjective to what sort of pattern you want to identify in the data.

Q: How many clusters do you think are there in this dataset?

A: The answers in the chat box ranged from two to six (three, six, two, four were all suggested). There is no predefined correct answer: clustering is very subjective, based on how the dataset looks and what sort of patterns you want to derive from it. The idea is not who is right — it is that you do not have a free, predefined mechanism that takes any set of data points and automatically finds "the" clusters. Clustering does not work like that.

13.4.4 Fundamental Questions in Clustering

Whenever a clustering problem is given, a few questions come up again and again:

How many clusters are in the dataset?
What is the size of each cluster in my dataset?
If a cluster is given, can I subdivide it — can I further divide that cluster?
Can I combine two or more clusters — given three clusters, can I combine the second and third?
How are there any outliers, and how do we handle outliers?

These are the questions the clustering problem has to deal with.

Scope — what these questions reveal: each question is a knob the user turns, not a fact the data hands over. "How many clusters?" maps to the parameter $k$ in K-means. "Can I subdivide?" and "Can I combine?" map to the split/merge operations of hierarchical clustering. "Outliers?" maps to whether the algorithm can ignore stray points (DBSCAN can; K-means cannot easily). The whole field of clustering measures exists to answer these subjective questions with numbers instead of eyeballing — the metrics we meet later (like homogeneity) are how we quantify the answers.

13.5 Applications of Clustering

13.5.1 Document Clustering: Google News

Real-world: One of the classic applications is document clustering, and the canonical real system is Google News. Suppose around 1,000 news articles are published on a given day across various newspapers, and you want to group them. Google News actually solves this problem: it clusters similar news into one group. Open Google News on any day and the first group of articles is about one story, the second group about another story — for example, one cluster of articles about the chaos happening at a location, another cluster of articles about the JEE Mains results. Given 1,000 news articles, the system groups them into different groups. Why is this useful? If you are interested in JEE Mains, you want to read all the articles related to it — you do not want to visit different news sites and search. Google News has combined them and put all related articles in one place. It is a huge application.

Worked example — one day of news, 1,000 articles. Pretend the day's articles cover three stories: story A (chaos at a location, covered by 400 articles), story B (JEE Mains results, 350 articles), and story C (everything else, 250 articles).

Articles are represented as points (for example, by the words they contain — document clustering usually works on word-based features).
Clustering groups the 400 A-articles into one cluster, the 350 B-articles into another, and splits or scatters the leftovers.
The result: a reader interested in JEE Mains opens one cluster and finds all 350 relevant articles in one place — no need to visit every news site and search.

The cluster, not the individual article, is the unit of reading. Sense-check: the same idea powers news aggregation, research paper grouping, and email triage — wherever many documents must be organized with no labels available.

13.5.2 Market Segmentation: The iPhone Example

Real-world: Another classic application is market segmentation. Suppose you want to launch a new iPhone. The target customer, in principle, is the whole world — but if you are spending money on marketing, you want to spend on the people most likely to buy the smartphone. Represent all the people in the world as points in a two-dimensional space; cluster the points, and the group of people most likely to buy the iPhone is your target segment. You market your product hugely to them compared with the general world. Selected marketing of this kind is done by finding target segments, and target segments can be found by clustering. Clustering has applications in market segmentation, search engines, and many other fields.

Worked example — who gets the ad? Represent each person as a point whose coordinates are attributes like age and disposable income (or many more dimensions). Cluster the population:

Cluster 1: young professionals with high disposable income — the group most likely to buy a premium phone.
Cluster 2: budget-conscious students — less likely to buy at full price.
Cluster 3: people with no smartphone — possible future buyers but not the immediate target.

Marketing money goes mostly to cluster 1: the same spend buys far more sales per rupee than spraying the same budget across all clusters. Clustering turns "everyone" into "the right few". Sense-check: if the attributes were different (say, brand loyalty instead of income), the segments would shift — the analyst chooses the attributes that define a promising segment.

13.5.3 Labeling Data for Classification

Real-world: Clustering is also used to help classification. Sometimes we are given unlabeled data points, and we find groups; then we can label all the points in one group as label one and all the points in another group as label two. Remember how class labels are normally got in classification: someone looks at each $X$ and manually assigns the class label $Y$ . Sometimes clustering can do this labeling instead. This is application-specific, not general — for a specific application, we can use clustering to label the data.

Labeling via clustering: when labels are missing, run clustering first, then attach labels to the groups instead of to individual points: all points in group one get label one, all points in group two get label two. One label per cluster replaces thousands of manual labels. This is application-specific — it only works when the natural clusters really do correspond to the classes you care about — but where it works, it turns an unsupervised step into the data-creation step of a supervised pipeline.

13.5.4 Dimensionality Reduction and Data Reduction

Real-world: Clustering is similar in notion to PCA and other dimensionality reduction methods. Think about it: clustering says all these points are very similar to each other, so we can put a center point in the middle — call it a centroid — and say that this centroid represents the entire group of points. For cluster two, centroid $μ_{2}$ represents all the points in cluster $C_{2}$ , and centroid $μ_{1}$ represents all the points in cluster $C_{1}$ . One representative per cluster instead of thousands of points — that is data reduction, and sometimes dimensionality reduction. So clustering can be used for data reduction.

The compression view: if a dataset has one million points and clustering finds $k = 50$ clusters, the data can be summarized by the 50 centroids $μ_{1}, μ_{2}, \dots, μ_{50}$ — each centroid stands in for its roughly 20,000 members. Storage and processing then work on 50 representatives instead of one million points. PCA also compresses data by finding a smaller set of directions that represent the whole — clustering compresses by finding a small set of representative points. Same goal (fewer numbers stand for the data), different mechanism.

13.6 The Roadmap: Five Clustering Algorithms

13.6.1 The Five Algorithms

Before the algorithms, the plan of the module: first the abstract concepts of clustering (all the mechanisms), then five specific clustering algorithms, and then we can link which clustering algorithm can be used for which category of problem. The five algorithms the course works through are: K-means (the classic distance-based example), agglomerative hierarchical clustering, divisive hierarchical clustering, DBSCAN (the density-based example), and one grid-based algorithm. CURE and BIRCH also appear as comparison algorithms — the same module compares them against the five to see where each one wins and loses.

The five-algorithm map (each algorithm is built for a different notion of "cluster", which is exactly what the taxonomy of Sections 13.7 and 13.8 prepares us to appreciate):

Algorithm	Type	What "similar" means	Number of clusters
K-means	Distance-based (center-based)	Closeness to a centroid	User passes $k$
Agglomerative hierarchical	Hierarchical (merge up)	Closeness of clusters (starts from single points)	Read off the tree
Divisive hierarchical	Hierarchical (split down)	Splitting a big cluster into smaller ones	Read off the tree
DBSCAN	Density-based	Dense regions separated by low density	Found automatically
Grid-based algorithm	Grid-based	Quantizing space into cells, then grouping cells	Depends on the method

This matches the standard textbook taxonomy of clustering methods: partitioning methods (K-means), hierarchical methods (agglomerative and divisive), density-based methods (DBSCAN), and grid-based methods — with CURE and BIRCH as well-known representatives of the more advanced family that scales clustering to very large data.

13.6.2 Why the Abstract View Comes First

One key study point made before diving in: these abstract concepts are extremely important. Clustering is a very subjective job; if you do not know what ways you can use to do clustering, most likely you will not do the clustering. If you only learn K-means, you will not be able to differentiate between K-means and DBSCAN — which dataset K-means suits, which dataset DBSCAN suits, what the performance measures of each are. The two extract different types of patterns and have different performance measures. That is why the abstract view comes first, then the five algorithms one by one in the next few classes.

Scope — why learning one algorithm is not enough: K-means finds center-shaped clusters; DBSCAN finds density-shaped clusters; hierarchical methods build a tree of merges or splits. A dataset with a crescent-shaped cluster defeats K-means but suits DBSCAN (Section 13.10.3). If you only know K-means, you will run it on data it cannot cluster and blame the data. The abstract concepts — types of clustering, types of clusters, requirements — are what let you look at a dataset and choose the right tool.

13.7 Types of Clustering

There are several independent ways to slice the clustering space, and each slicing answers a different design question.

A frame for this whole section: every clustering algorithm is the answer to six questions. (1) May a point belong to several clusters? (2) Is the output one level or a tree of levels? (3) What measure defines "similar"? (4) Do steps run one after another or in parallel? (5) How many measures are used? (6) Does the algorithm need all the data at once? The six subsections below answer these six questions — and Section 13.11.3 will answer all of them for K-means specifically.

13.7.1 Hard versus Soft (Fuzzy) Clustering

The first notion is separation of clusters. Hard clustering says one point can only belong to one cluster in the dataset. It is a division of data objects into non-overlapping subsets of clusters, such that each data point lies in exactly one subset. Soft clustering says one point can be associated with more than one cluster: there can be a cluster like this and a cluster like that, and the point in the middle can belong to both $C_{1}$ and $C_{2}$ . Fuzzy clustering falls under the broad area of soft clustering. Hard clustering and exclusive clustering are synonyms; soft clustering and non-exclusive clustering are synonyms.

Hard versus soft, formally: in hard (exclusive) clustering the clusters form a partition — every point is in exactly one cluster, and no two clusters overlap. In soft (non-exclusive) clustering a point may carry membership in more than one cluster; fuzzy clustering goes further and attaches a membership weight or probability to each point–cluster pair, with the weights for one point summing to 1 (for example, 0.8 for $C_{1}$ and 0.2 for $C_{2}$ ).

An everyday picture: hard clustering is like a student who is registered in exactly one department. Soft clustering is like a student-employee who belongs to two worlds at once — a student by day, an employee in the lab — and fuzzy clustering says "70% student, 30% employee" rather than forcing a single yes/no.

13.7.2 Degree of Soft Clustering and Strength of Association

When we talk about soft clustering, two further notions appear.

Degree of clustering: a single point can belong to how many clusters? If we define the degree as two, each point in the dataset can belong to at most two clusters; if the degree is five, each point can belong to at most five clusters.

Strength of association: a point can belong to one cluster in a stronger way than to another cluster. Take a point sitting in the middle between two clusters; it is much closer to $C_{1}$ , so its strength of association with $C_{1}$ is higher than its strength of association with $C_{2}$ . One point can belong to one cluster with higher strength and to another cluster with lower strength.

Worked example — degree and strength together. Take a point $p$ sitting between clusters $C_{1}$ and $C_{2}$ .

Degree = 2: $p$ may belong to at most two clusters — here, it uses both memberships: $C_{1}$ and $C_{2}$ .
Strength of association: $p$ is much closer to $C_{1}$ 's center (distance 1) than to $C_{2}$ 's center (distance 9). So $p$ 's strength with $C_{1}$ is high (say 0.9) and with $C_{2}$ is low (0.1).

*Degree says how many; strength says how strongly.* Sense-check: raising the degree to 5 would let $p$ join three more clusters — but its strength there would be near zero, so in practice the extra memberships add nothing. This is why soft clustering is often converted back to hard clustering in practice: take the single strongest membership.

13.7.3 Single-Level (Flat) versus Hierarchical Partitioning

The second notion is how we partition the dataset. Flat clustering (single-level) partitions the space into disjoint sets — given the data points, we partition the vector space into separate, non-overlapping regions. Hierarchical clustering organizes the clusters themselves into a hierarchy, where bigger clusters contain smaller clusters.

Flat versus hierarchical: flat (single-level, partitional) clustering produces one set of clusters — every point is in exactly one region, and there are no nested levels. Hierarchical clustering produces a tree of clusters: a small cluster can sit inside a bigger cluster, which sits inside an even bigger one. The same point then belongs to several nested clusters at once — not as soft membership, but as "contained in a smaller group that is contained in a larger group". K-means is flat; agglomerative and divisive methods are hierarchical.

13.7.4 Agglomerative versus Divisive Clustering: The Cities Example

Within hierarchical clustering there are two directions. Agglomerative: initially we treat all the data points as one big cluster, then divide that cluster into two or more smaller clusters, then further divide, like a tree, until the bottom, where each leaf is a single point. Divisive: the reverse — initially each point is its own separate cluster, and we combine clusters based on a similarity notion until, at the end, one big cluster contains all the data points.

The professor's example: take six city names — Jodhpur, Jaipur, Bhopal, Indore, Kanpur, Lucknow — as data points. Cluster them by state: Jodhpur and Jaipur belong to Rajasthan; Bhopal and Indore belong to Madhya Pradesh; Kanpur and Lucknow belong to Uttar Pradesh. Now cluster by country: all six fall into one cluster called India. Look at the hierarchy we have built: at the top, every point is an individual cluster; then by one similarity notion a few points combine into clusters; then bigger clusters form. Jaipur belongs to its own singleton cluster, Jaipur belongs to the Rajasthan cluster, Jaipur belongs to the India cluster, Jaipur belongs to the Asia cluster. Same for Lucknow: the UP cluster, the India cluster, the Asia cluster. That is a hierarchy of clusters.

Worked example — six cities, a hierarchy, two directions. The data points: Jodhpur, Jaipur, Bhopal, Indore, Kanpur, Lucknow.

State-level grouping: \{Jodhpur, Jaipur\} = Rajasthan; \{Bhopal, Indore\} = Madhya Pradesh; \{Kanpur, Lucknow\} = Uttar Pradesh.
Country-level grouping: all six = India.
Continent-level grouping: India = Asia.

The hierarchy (nested clusters, bottom-up):

Level 0: six singletons — \{Jodhpur\}, \{Jaipur\}, \{Bhopal\}, \{Indore\}, \{Kanpur\}, \{Lucknow\}.
Level 1: three state clusters — \{Jodhpur, Jaipur\}, \{Bhopal, Indore\}, \{Kanpur, Lucknow\}.
Level 2: one country cluster — \{all six\} = India.
Level 3: one continent cluster — \{India\} = Asia (contains the level-2 cluster).

Jaipur lives in four clusters at once: the singleton \{Jaipur\}, the Rajasthan cluster, the India cluster, and the Asia cluster — each one a bigger container. This is hierarchical clustering: a tree of nested clusters. And the two directions to build the same tree: divisive starts at the top with one giant cluster (Asia) and splits down (India → states → singletons); agglomerative starts at the bottom with singletons and merges up (singletons → states → India → Asia). Both directions produce the same nested structure. Sense-check: towards the end of divisive, every leaf is a single point; towards the end of agglomerative, one big cluster holds everything — they meet in the middle.

13.7.5 Similarity Measures: Distance-, Density-, and Graph-Based

The third notion is what "similar" means. Similarity can be defined based on distance: two points close to each other are similar, two points far apart are dissimilar — K-means is a distance-based clustering algorithm. Similarity can be defined based on density or continuity — DBSCAN, discussed later, is a density-based clustering algorithm. There are also graph-based clustering algorithms: we project all the points into a space, make a graph out of it, and define similarity based on graph edges — we see a variant of this in bisecting K-means, which is a continuity-based algorithm. So there are different ways of defining similarity; these are examples, not an exhaustive list.

Three similarity notions:

Distance-based: small distance means similar; large distance means dissimilar. This is the natural measure for points in a vector space (K-means uses it).
Density-based: similarity is about neighborhood density — points that sit in a dense region belong together even if the region is stretched or curved (DBSCAN uses this).
Graph-based (contiguity): build a graph with points as nodes and edges between nearby points; two points are similar if a chain of edges connects them (bisecting K-means relates to this continuity idea).

These are not an exhaustive list — the professor stresses the examples, because the choice of measure is what makes one dataset clusterable by one algorithm and not another.

13.7.6 Sequential versus Simultaneous Algorithms

The fourth notion is the mode of operation. If all the steps of a clustering algorithm must be done one by one, in a sequential fashion, it is a sequential algorithm — K-means is sequential. If some steps can be performed at the same time, in parallel, it is a simultaneous algorithm. Two algorithms discussed later — BIRCH and CURE — are simultaneous in nature; an exercise for students is to identify which of them is actually simultaneous. Why does parallelism matter? With one billion points, all traditional algorithms become extremely slow; they are not designed for that scale. For simultaneous processing you might partition the data, cluster the smaller partitions, and combine them at the end.

Q: Simultaneous means parallel processing?

A: Yes. In some clustering algorithms, if there are four steps, we can do some of the steps in parallel — all the steps need not be done sequentially. The point of doing it is higher processing speed, and sometimes it is a requirement: traditional algorithms cannot handle huge amounts of data, so you retune the dataset or retune the algorithm — partition the data, cluster the smaller partitions, and combine them towards the end.

13.7.7 Monolithic versus Polythetic

The fifth notion is how many similarity measures are used. Monolithic (monothetic) clustering is based on one similarity notion — you cluster the data points using a single measure. Polythetic clustering uses multiple measures to define similarity.

Monolithic versus polythetic: monolithic (also written monothetic) clustering makes all its decisions with one similarity measure — one distance function for every pair of points. Polythetic clustering combines several measures — for example, distance on numeric attributes plus a separate matching score on categorical attributes — and decides similarity from all of them together. One measure is simpler; several measures capture richer notions of "alike" at the cost of more design choices.

13.7.8 Exclusive versus Non-exclusive and Fuzzy versus Non-fuzzy

Exclusive versus non-exclusive is a synonym of hard versus soft clustering, already seen. Fuzzy versus non-fuzzy is the associated distinction: read the material and tell which sort of algorithm is fuzzy and which is non-exclusive.

Scope — two pairs, not one: "exclusive / non-exclusive" and "fuzzy / non-fuzzy" are related but not identical. Exclusive = a point belongs to exactly one cluster (a partition). Non-exclusive = a point may belong to several clusters. Fuzzy = membership comes with a weight or probability that sums to 1 across clusters. The practice task assigned in class is to map these two axes onto the algorithms: fuzzy c-means is fuzzy and soft; plain K-means is non-fuzzy and exclusive. Read the material and decide which algorithm is fuzzy and which is non-exclusive — the two terms are examinable distinctions, not interchangeable words.

13.7.9 Partial versus Not Partial: Does the Algorithm Need All the Data?

The last notion is about data requirements. Sometimes the dataset is huge — billions of points. Some clustering algorithms need all the data points at one go to do the clustering; they are incapable of working with a partial view. K-means has this issue: it needs to load all the points into memory to do the processing. Give it a million points and it slows down drastically; it needs the complete data to form the clusters. Other algorithms can cluster with only partial data at one go — give them a partial view of the data and they still cluster. That is the notion of partial clustering.

Complete versus partial clustering (two meanings): "Partial" here is about data availability, not group membership. A complete-data algorithm (K-means is one) wants every point in memory before it starts — its centroids depend on all points, so a partial view would give a skewed answer. A partial-data algorithm can consume points as they arrive, or work on a subset, and still produce clusters; this is the property that makes streaming-scale clustering possible for billion-point data. (In some textbooks the terms also appear with the other meaning — "complete clustering assigns every object to some cluster, partial clustering may leave outliers unassigned" — so keep the two readings apart: the professor's usage here is about data requirements.)

13.8 Types of Clusters

Now we ask: what do the clusters themselves look like? There are several types of clusters we can get out of a clustering algorithm.

13.8.1 Center-Based Clusters: Centroid versus Medoid

A center-based cluster is a set of objects such that a point in the cluster is closer to the center of its cluster than to the center of any other cluster. Take a point and four colored clusters — blue, green, yellow, red. The point belongs to the blue cluster because it is closer to the blue center than to the green, yellow, or red centers. The center of the cluster is called the centroid. There is another way of finding the center, called the medoid.

The difference between centroid and medoid: a centroid can be an artificial point. Given a cluster of points, compute the center as the summation of the points divided by the number of points:

$μ = \frac{1}{n} i = 1 \sum n x_{i}$

where $x_{i} \in R^{d}$ is each data point in the cluster and $n$ is the number of points in the cluster. The professor's verbal description: "I can do the summation of points and divide by number of points. So that will give me the center."

Now this center might be an actual point of the dataset or an imaginary point. If the coordinate of the center coincides with a real data point, that point is called a medoid — it might not be the exact center, but it is the point closest to the imaginary center. If there is no real point at the center and we want to consider all the points, it is called a centroid. In other words: if the center is an imaginary point, it is a centroid; if we want only real points and assign the center as the nearest real point to the centroid, it is a medoid. K-means uses centroids; a variant of the algorithm can be built around medoids.

Centroid versus medoid — the decision table:

	Centroid	Medoid
What it is	The average of the points: $μ = \frac{1}{n} \sum_{i = 1}^{n} x_{i}$	An actual data point of the cluster
Can it be imaginary?	Yes — usually no real point sits exactly at the average	No — by definition it must be a real point
How it is chosen	Arithmetic mean of all points	The real point nearest to the (imaginary) centroid
Used by	K-means	K-medoid variants
Needs	Coordinates that can be averaged (numeric data)	Only a proximity measure between pairs of points

Worked example — same cluster, two centers. Take the cluster with three points $(1, 1)$ , $(2, 3)$ , $(6, 2)$ in $R^{2}$ .

Centroid: $μ = (\frac{1 + 2 + 6}{3}, \frac{1 + 3 + 2}{3}) = (3, 2)$ .
Check: is $(3, 2)$ one of the three points? No — $(1, 1)$ , $(2, 3)$ , $(6, 2)$ are the data points. So the centroid is an imaginary point that happens to represent the cluster.
Medoid: the real point closest to $(3, 2)$ . Distances: to $(2, 3)$ : $(3 - 2)^{2} + (2 - 3)^{2} = 2 \approx 1.41$ ; to $(6, 2)$ : $(3 - 6)^{2} + 0^{2} = 3$ ; to $(1, 1)$ : $4 + 1 = 5 \approx 2.24$ . The nearest real point is $(2, 3)$ .

Centroid = (3,2) (imaginary); medoid = (2,3) (real). Sense-check: the medoid is not the geometric center — it is the closest real stand-in for the center, which is why medoid-based clustering is less sensitive to outliers: a medoid is always an actual observation, never a value pulled toward a stray point.

13.8.2 Well-Separated Clusters

A well-separated cluster is a set of data points such that any point in the cluster is closer to every other point in its cluster than to any single point outside the cluster. Take a point in the blue cluster: it is closer to all the points of the blue cluster than to even a single point in the green cluster. That is why blue and green are called well-separated clusters. The definition is short but strong — every other point, not just the center.

Well-separated, formally: for every point $p$ in cluster $C$ and every other point $q$ in $C$ , and every point $r$ outside $C$ : $dist (p, q) < dist (p, r)$ . Every point must be closer to every member of its own cluster than to any outsider. This is the strictest cluster definition — it is satisfied only when the natural groups in the data sit far apart, and such clusters may have any shape, not just globular ones. This is the idealistic textbook definition; most real datasets are messier.

13.8.3 Continuous Clusters

A continuous cluster is a set of points such that a point in the cluster is closer to one or more points in its cluster than to any other point not in the cluster. Contrast with the well-separated case: there, the standard was every other point; here, it is one or more points. This changes the geometry completely — a cluster can grow like a line or a curve, point by point, where each new point is only near one or two existing points. The professor flags that one clustering algorithm grows exactly like this, in a line or curve fashion, and it produces continuous clusters.

The "train of points" picture: imagine a curved snake of points. A point at the snake's head is far from the tail — it is not close to every other member — yet it is close to its immediate neighbors. Under the well-separated definition the snake is not one cluster; under the continuous (contiguity) definition it is: each point just needs some neighbor in the cluster. The standard name in the literature for this family is contiguity-based clusters, and the chain-growth behavior belongs to a class of graph-based clustering algorithms.

13.8.4 Density-Based Clusters

A density-based cluster is a dense region of points separated from other dense regions by a region of low density. In the vector space, density is high in one patch, low in between, high in another patch. Based on the density we group the points: this becomes one cluster and that becomes another cluster. The way density changes in the vector space dictates the clustering — low density here, high density there, low density again. DBSCAN is the algorithm that does exactly this, covered later.

Density-based clusters, formally: a cluster is a dense region of points that is surrounded by a region of low density. The clustering is dictated by how density varies in space — high density here, low density between, high density there. The key payoff: density-based clusters can be arbitrary in shape (a crescent, a ring, an S-curve), and the low-density gaps mark the boundaries. DBSCAN is the canonical algorithm: it finds dense regions and flags the sparse leftovers as noise.

13.8.5 Conceptual Clusters and Objective-Function Clusters

Two more notions: a shared property or conceptual cluster is one where two clusters share some common property between themselves. And clusters can be formed based on an objective function: we define an objective function and want to minimize or maximize it; based on whether we are using a global objective or a local objective — global optima or local optima — we form the clusters.

Conceptual clusters: a shared-property (conceptual) cluster is a set of objects that all share some general property — the property can be "closest to the same centroid" (which subsumes center-based clusters) or something much more specific, like "all points inside this triangle" or "all points lying on this spiral". Finding such clusters needs a precise concept of the cluster's shape. Objective-function clusters: the clustering is the solution to an optimization problem — define a score over all clusterings (for example, total SSE) and keep the clustering that minimizes or maximizes it. The catch is global versus local: a greedy procedure may settle at a local optimum that is worse than the global one — a behavior we will see firsthand with K-means (Section 13.12.4).

13.8.6 Graph-Based (Contiguity) Clusters

One more cluster type completes the picture — the graph-based cluster, which the professor's taxonomy pointed to in Section 13.7.5 when it discussed similarity by graph edges. Represent the data as a graph: each data point is a node, and an edge connects two points when they are close enough (within a chosen distance threshold). A cluster is then a connected component — a group of nodes linked to each other, with no link to any node outside the group. This gives the same "chain" geometry as continuous clusters: a curve of points stays one cluster because each point links to its neighbor, even though the ends are far apart. The known weakness: a stray bridge of points between two dense groups can merge them into one cluster, because the bridge provides the chain. Contiguity-based notions like this are the standard view behind the single-link family of hierarchical clustering.

Whatever the type, the bottom line repeats: the clusters you form should have high intra-cluster similarity (cohesiveness between the data points inside the cluster) and low inter-cluster similarity (distinctive nature between clusters).

One-line takeaway: a cluster is a useful group — and "useful" comes in many shapes: center-based (a centroid or medoid), well-separated (every point closer to its own members), continuous (chains), density-based (dense patches), conceptual (shared property), or graph-based (connected components). Whichever type you produce, the yardstick stays the same: high intra-cluster similarity, low inter-cluster similarity.

13.9 Measuring Cluster Quality

13.9.1 Similarity and Performance Measures

Once we form clusters, how do we measure whether they are good or bad? Quality is very subjective, but there are measures. Just as accuracy and similar metrics measure classification, there are different performance measures for clustering. One way of defining cluster quality is the similarity measure — we can use a distance measure, and so on. More measures of this kind are covered as the algorithms are discussed.

Quality is subjective, but measurable: classification has accuracy — one number comparing predicted labels with true labels. Clustering has no true labels to compare against, so quality must be judged differently. The most direct quantity is a similarity measure: decide how similar points within a cluster should be (for example, by distance) and score the clustering by that. A first concrete example — and the one K-means itself optimizes — is the sum of squared error (SSE): add up, over all points, the squared distance from each point to its own centroid. Lower SSE means points sit tighter around their centers, so the clustering is "better" by that measure. The coming classes add more measures: homogeneity (how uniform the clusters are), and others tied to each specific algorithm.

13.9.2 When Measures Matter

The professor notes: if you have a two-dimensional dataset you can visualize clusters directly, but most of the time you will not have visualization — that is when performance measures tell you about the quality of the cluster.

Scope — when the numbers matter more than your eyes: in two dimensions you can plot the points and judge the clusters by eye. But real data is often 10-, 50-, or 1,000-dimensional — there is no plot you can look at. In exactly those situations the performance measures take over: a number like SSE (or, later, homogeneity) is the only "look" you get at the quality of the clusters. The rule of thumb: visualization when you can, measures when you cannot — and in high dimensions you almost always cannot.

13.10 Requirements of a Clustering Algorithm

These are the properties to look for in a clustering algorithm — and the checklist to use if you ever design your own.

The eight-point checklist a good clustering algorithm should satisfy: (1) scalable, (2) handles different attribute types, (3) discovers clusters of arbitrary shape, (4) needs minimal input parameters, (5) handles noise and outliers, (6) insensitive to input order, (7) handles high dimensionality, (8) supports constraints, interpretability, usability. No real algorithm scores full marks on all eight — the point of the checklist is to know each algorithm's weak spots before you choose it.

13.10.1 Scalability

The clustering solution should be scalable: give me 100 points and the algorithm should handle it, give me one billion points and the algorithm should still handle it. Frankly: a single algorithm that handles both is rare. If the input is one billion points, design and optimize the algorithm for huge amounts of data; if the input is always in the thousands, design a different clustering. Always aim to build a scalable solution, but for extraordinarily huge data you need different ways of handling it.

Scope — the honest version: scalability means the algorithm's cost grows gently with the number of points $n$ , not explosively. K-means grows roughly linearly in $n$ (Section 13.11.4), which is why it can handle large sets at all. But even linear growth fails at the billion scale in one sitting — that is why simultaneous and partial-data algorithms (Sections 13.7.6 and 13.7.9) exist: partition the data, cluster the parts, combine. Design for the size you actually have; a solution tuned for thousands of points will not magically survive a billion.

13.10.2 Handling Different Attribute Types

The algorithm should handle different types of attributes — the four types seen earlier in the course: nominal, ratio, interval, and ordinal. The question to answer per algorithm: how will K-means handle a nominal attribute plus a ratio attribute together? For clustering algorithms that represent data categorically or nominally, we discuss how to handle it when we reach each algorithm.

Attribute types versus algorithm type: the four attribute scales from earlier in the course are nominal (categories with no order — "red", "blue"), ordinal (ordered categories — "small", "medium", "large"), interval (ordered numbers with no true zero — temperature in °C), and ratio (numbers with a true zero — income, age). A centroid is an average, and averages only make sense on numeric (interval/ratio) attributes — averaging "red" and "blue" gives nothing. So K-means cannot take nominal attributes directly; algorithms for categorical data (like the k-modes variant, which replaces the mean with the most frequent value) exist for exactly this gap. The rule per algorithm: check which attribute types its notion of "center" and "distance" can handle.

13.10.3 Discovering Clusters of Arbitrary Shape

This one is very, very important. Center-based clustering always produces a convex cluster — think of it as a circular cluster: there is a center, and the points around it belong to the cluster, so the boundary of the cluster is some convex shape. Sometimes you need arbitrary-shape clusters. Picture the data set with a red cluster that wraps like a crescent around a blue cluster, or two clusters that are visually obvious as separate regions: if we use center-based clustering on such data, a center forms for the red region, but to capture the blue cluster a centroid lands in the middle of the red crescent and the whole region becomes one cluster — essentially wrong. You can see with your own eyes that these are two separate clusters, but center-based clustering drags one inside the other. So center-based clustering does not work when the boundary is not convex; you need a different measure. This is the motivation for density-based and other methods.

The crescent failure, step by step: imagine a red crescent wrapping around a blue disc. A center-based algorithm places one centroid in the red arc and must place a second centroid somewhere to cover the blue points — but any point "inside" the crescent (including the blue region) is closer to a red arc centroid than to anything else, so the blue disc gets absorbed into the red cluster. The algorithm happily converges with one giant concave blob where the eye sees two clusters. Why it happens: center-based clusters are built by closeness to a center, and closeness-to-a-center always yields convex (globular) regions; a crescent is non-convex, so no center-based assignment can trace it. The fix: use a similarity notion that does not rely on a center — density-based methods (DBSCAN) follow the dense patches wherever they wind.

13.10.4 Minimal Input Parameters

The fewer input parameters the better. K-means requires you to pass the value of $k$ — how many partitions you want to make in the dataset. That is an input parameter, and the ideal is to minimize the input parameters the algorithm needs. Ideally you should try to calculate as many things from the data as you can.

Parameter parsimony: every parameter the user must supply is a chance to make the wrong choice. K-means forces the user to supply $k$ (the number of clusters) — a genuinely subjective number, as Section 13.4's chat-box demo showed. DBSCAN instead discovers the number of clusters from the data (it needs other parameters, like the density threshold, but not $k$ ). The ideal algorithm computes what it can from the data and asks the user only for what it truly cannot infer. When you design your own algorithm, the same principle applies: fewer knobs means fewer ways for the user to make a mistake.

13.10.5 Handling Noise and Outliers

Some clustering algorithms handle outliers easily; some are very vulnerable to them. K-means is very vulnerable to outliers — if there are a lot of outliers, the cluster center will move. If the data is noisy and you still want to run K-means, you have to do pre-processing first: remove the outliers, then cluster. Only then does K-means work. DBSCAN, on the other hand, can very easily find outliers in the dataset. When designing your own algorithm, make sure it is decently able to handle outliers.

Why K-means breaks on outliers — the numbers: K-means minimizes the sum of squared errors, and squaring punishes big distances disproportionately. A point that is 10 units from its centroid contributes $1 0^{2} = 100$ to the SSE — while ten normal points at distance 1 contribute only $10 \times 1 = 10$ combined. One outlier can end up dominating the whole objective, and the centroid moves toward it to reduce that giant squared term, distorting the cluster center. In contrast, DBSCAN labels sparse low-density points as noise and simply leaves them out of clusters — it finds outliers as part of its job. Practical rule for noisy data: clean the outliers first (or use a method that tolerates them), not after.

13.10.6 Insensitivity to the Order of Input Records

Given data points $x_{1}, x_{2}, \dots, x_{n}$ , any clustering algorithm processes one point at a time — assigns $x_{1}$ to some cluster, $x_{2}$ to another, and so on, possibly iterating. The question: if we change the order — $x_{5}, x_{2}, x_{1}, x_{55}, \dots$ — does the algorithm give a different output? Some algorithms change their output when the order changes, because of how they process the data; one algorithm discussed in a couple of classes is heavily dependent on the order of the input. Other algorithms handle order robustly. Insensitivity to input order is a desirable property.

Order-dependence, and why it appears: an algorithm that updates its model after every single point (incremental updating) lets each point influence the state before the next point arrives — so the sequence of arrivals matters and different orderings can land at different results. An algorithm that first reads all points and only then updates (batch updating, like standard K-means) cannot care about order: the same complete data produces the same first assignment no matter the sequence. The classic fix for incremental algorithms is to shuffle the input, so no particular order gets an unfair influence — but the property you want in a designed algorithm is genuine order-insensitivity.

13.10.7 Handling High Dimensionality

If the vector space is 50-dimensional and we use a distance-based clustering, we have to compute the distance between two points $x_{1}$ and $x_{2}$ , which costs work per dimension. The Euclidean distance in $d$ dimensions:

$d (x_{1}, x_{2}) = i = 1 \sum d (x_{1 i} - x_{2 i})^{2}$

where $x_{1}, x_{2} \in R^{d}$ are two points, $x_{1 i}$ is the $i$ -th coordinate of $x_{1}$ , $x_{2 i}$ the $i$ -th coordinate of $x_{2}$ , and $d$ is the number of dimensions. The professor's verbal description: "It will be under root of x2 minus x1, dimension one, dimension two, dimension three, dimension n ... I have to do all this computation before I find the distance." With huge numbers of dimensions this computation load genuinely impacts performance. Some clustering algorithms, K-means among them, perform badly on high-dimensional data; other algorithms handle high dimensionality well.

Scope — two separate costs of high dimensions: first, the arithmetic cost — every distance in $d$ dimensions needs $d$ subtractions, $d$ squarings, $d$ additions, and one square root, and K-means computes a distance from every point to every centroid every iteration, so the total cost scales with $d$ . Second, a deeper problem called the curse of dimensionality: as $d$ grows, all pairwise distances start to look alike — the notion of "nearest point" itself weakens, and distance-based clustering loses its sharpness. So high-dimensional data is expensive and conceptually harder to cluster by distance; dimensionality reduction (PCA, Section 13.5.4) is a standard preprocessing step for exactly this reason.

13.10.8 Constraints, Interpretability, Usability

The remaining properties: the clustering algorithm should be able to incorporate user-specific constraints; the clusters it produces should be interpretable; and the algorithm should be usable — these are the features to want in a clustering algorithm so it can be used for different purposes.

The final three requirements: constraints — the user often knows things the data does not show ("these two points must never be split", "this cluster must have at least 10 members"); a good algorithm can honor such must-link and cannot-link constraints (constrained variants of K-means exist for exactly this). Interpretability — the clusters must be understandable to a human, not just mathematically optimal; a centroid is interpretable ("the average customer"), a 100-dimension boundary is not. Usability — the algorithm should be practical: few knobs, sensible defaults, reasonable run time, and results you can explain to a stakeholder. Together these three decide whether an algorithm survives contact with a real problem.

13.11 K-Means Clustering: Overview

13.11.1 History

K-means is about 70 years old: it was proposed in 1957, and an extended, better version by the same author appeared around 1982. Both are research papers and both can be found — one paper from 1957 and another from around 1980.

The history, reconciled: the standard attribution is to Stuart Lloyd, whose work on "least squares quantization" was written as a Bell Laboratories technical report in 1957 and finally published as a journal paper in 1982. Independently, E. W. Forgy proposed a closely related method around the same time, which is why the algorithm is also called the Lloyd-Forgy algorithm (or Lloyd's algorithm). So the professor's dates — 1957 for the original proposal and about 1982 for the extended, published version — match the record exactly: one paper from 1957, another from 1982. In other words, K-means has been the workhorse of clustering for nearly seventy years and is still one of the most widely used clustering algorithms.

13.11.2 Problem Setup: Input, Output, Objective

Given a set of $n$ data points, K-means partitions the $n$ points into $k$ disjoint sets, based on the objective of minimizing the sum of squared error. The input to the algorithm: the data points $x_{1}$ to $x_{n}$ , which live in a $d$ -dimensional vector space, and the value of $k$ — how many partitions we want. The output: the cluster assignment of all $n$ points into $k$ clusters. It is hard clustering, so each point is assigned to exactly one cluster.

The objective function is to minimize the sum of squared error (SSE):

$SSE = j = 1 \sum k x \in C_{j} \sum ∥ x - μ_{j} ∥^{2}$

where $C_{j}$ is the $j$ -th cluster, $μ_{j}$ is the centroid of $C_{j}$ , and $∥ x - μ_{j} ∥$ is the distance from a point $x$ to its centroid. The professor stated the objective only as "minimize sum of square error" and deferred the detail ("I'm going to talk about what is sum of square error") — the standard form is exactly the double sum above: for each cluster $C_{j}$ (summing over $j = 1$ to $k$ ), for each point $x$ in that cluster, take the squared Euclidean distance to the cluster's centroid $μ_{j}$ , and add it all up. The inner term $∥ x - μ_{j} ∥^{2}$ is the squared distance — that squaring is what makes outliers hurt so much (Section 13.10.5). Textbooks also call the same quantity the scatter.

Inputs, outputs, objective — at a glance:

Input: $n$ points $x_{1}, \dots, x_{n} \in R^{d}$ and the integer $k$ (number of clusters desired).
Output: an assignment of every point to exactly one of $k$ clusters (hard, flat partitioning).
Objective: minimize $SSE = \sum_{j = 1}^{k} \sum_{x \in C_{j}} ∥ x - μ_{j} ∥^{2}$ — points should sit as close as possible to their own cluster's centroid.

Having to pass $k$ might sound absurd — give me the data points and the algorithm should give me clusters — but for K-means you must tell the algorithm to partition into five clusters, or six, or two. The same dataset from earlier: if $k = 2$ is passed, K-means partitions into two clusters; $k = 4$ gives four clusters; $k = 6$ gives six. It is very subjective, and the result depends on that choice; but as a user you should also visualize what sort of data you want to extract from the clustering algorithm. It is a hard task, but still a very powerful algorithm.

13.11.3 K-Means Properties at a Glance

Linking back to the taxonomy of section 13.7: the partition criteria of K-means is single-level or flat — it partitions the vector space into disjoint sets. The separation of clusters is hard clustering — each point belongs to only one cluster. The similarity measure is distance-based — close points go into one cluster, far points into another. The mode of operation is sequential — all steps run one by one.

Taxonomy axis (Section 13.7)	K-means answer
Hard versus soft	Hard — every point in exactly one cluster
Flat versus hierarchical	Flat (single-level) — one set of disjoint clusters, no nesting
Similarity measure	Distance-based — Euclidean distance to the nearest centroid
Sequential versus simultaneous	Sequential — steps run one after another
Monolithic versus polythetic	Monolithic — a single distance measure drives everything
Complete versus partial data	Needs all the data at once — it cannot cluster a partial view

13.11.4 Time and Space Complexity

Two costs worth knowing before running K-means. Space: the algorithm only stores the data points and the $k$ centroids — about $O ((n + k) d)$ memory, where $n$ is the number of points and $d$ the number of attributes. Time: each iteration computes a distance from every point to every centroid — that is $n \times k$ distances per iteration, each costing $d$ arithmetic operations — so one iteration costs $O (nk d)$ , and with $I$ iterations the total is $O (I \cdot n \cdot k \cdot d)$ . The encouraging part is the $I$ : most of the movement happens in the first few iterations, so $I$ is typically small. The result: K-means is roughly linear in the number of points $n$ , which is why it is considered an efficient algorithm — provided $k$ is small compared with $n$ .

13.12 The K-Means Algorithm

The algorithm is a very simple four-step process: (1) initialization of centroid, (2) cluster assignment phase, (3) recomputation of centroid, (4) loop back to step 2 until convergence is complete.

Purpose — what this procedure exists for: K-means solves the optimization problem of Section 13.11.2: partition $n$ points into $k$ clusters so that the SSE is as small as possible. A brute-force search over all ways to split the points is impossibly large; K-means is the practical greedy walk toward that goal: pick centers, assign points to them, move the centers, repeat. It never guarantees the global best split — but it is simple, fast, and almost always finds a good one.

Inputs and outputs: inputs are the points $x_{1}, \dots, x_{n} \in R^{d}$ and the number of clusters $k$ ; output is the final set of centroids $μ_{1}, \dots, μ_{k}$ and the assignment of every point to exactly one of the $k$ clusters.

13.12.1 Step 1: Initialization of Centroids

The number of centroids equals the number of clusters we want to find. If $k = 5$ , there will be five clusters and five centroids. For the starting point, centroids are initialized randomly — anywhere in the vector space we place the centroids. With $k = 2$ , two centroids are initialized randomly; they can be imaginary points, since the centroid is an imaginary or real point and $μ_{1}$ can be an imaginary point.

Why random, and why that is fragile: random initialization is the simplest possible starting point — drop $k$ centroids anywhere in the space and let the loop fix them. But the starting positions matter more than they look: K-means only walks downhill in SSE, so a bad start can trap it at a local minimum (a good-but-not-best clustering), while a lucky start finds the global best. Standard defenses: run the whole algorithm several times with different random starts and keep the lowest-SSE result, or initialize smarter (for example, start centroids far apart from one another so each cluster grabs a different region).

13.12.2 Step 2: Cluster Assignment

Each point in the dataset is assigned to its nearest centroid. Take point one: compute the distance between this point and the first centroid, and between the same point and the other centroid; point one is assigned to the nearer one. If it is much closer to $μ_{1}$ , it is assigned to the $μ_{1}$ cluster. Do this exercise for all the points: point two is assigned to its nearest centroid, point three, and so on. Temporarily, we now have two clusters in the dataset, with a temporary cluster boundary. All the points — numbered one to eight in the example — belong to one of these two clusters.

Worked step — one point, two centroids. Point $p = (1, 2)$ with centroids $μ_{1} = (1, 1)$ and $μ_{2} = (4, 4)$ .

Distance to $μ_{1}$ : $(1 - 1)^{2} + (2 - 1)^{2} = 0 + 1 = 1$ .
Distance to $μ_{2}$ : $(1 - 4)^{2} + (2 - 4)^{2} = 9 + 4 = 13 \approx 3.6$ .

The nearer centroid is $μ_{1}$ , so $p$ joins cluster $C_{1}$ . Doing this for every point draws the temporary boundaries: the space is divided into regions, each region "owned" by the nearest centroid — the familiar nearest-neighbor tiling of the space. Every point inside a region is assigned to that region's centroid.

Q: What does single or flat level partition mean here?

A: The partition criteria is single (flat) versus hierarchical. In single or flat partitioning, the vector space is partitioned into disjoint sets — like drawing partition lines so each region is separate. In hierarchical clustering, one point can belong to a small cluster, and there can be a bigger cluster that includes the smaller cluster, and an even bigger cluster that includes both. K-means is flat: it gives disjoint sets, partitioning the vector space into $k$ disjoint sets.

13.12.3 Step 3: Recomputation of Centroid

After the assignment, recompute the centroid of each cluster. Cluster one has, say, four points; add all four points and divide by the number of points, four. The same for cluster two. The new centroid $μ_{1}$ lands somewhere inside cluster one, and the new $μ_{2}$ inside cluster two. The formula, where $C_{j}$ is the set of points in cluster $j$ and $∣ C_{j} ∣$ is its size:

$μ_{j} = \frac{1}{∣ C _{j} ∣} x \in C_{j} \sum x$

The professor's verbal description: "I can add all these four points and then divided by number of points, which is four." The centroid moves from its old position to the new one; the old temporary boundary is dissolved and redefined.

Why the mean is the right new center — the derivation. The objective says: keep the SSE small. Suppose we fix the current assignment (every point is in some $C_{j}$ ) and ask: which single point $μ_{j}$ would make $C_{j}$ 's contribution to the SSE smallest? That contribution is

$SSE_{j} = x \in C_{j} \sum ∥ x - μ_{j} ∥^{2} .$

Write the squared norm out coordinate by coordinate and differentiate with respect to $μ_{j}$ . For one coordinate $a$ :

$\frac{\partial SSE _{j}}{\partial μ _{j a}} = \frac{\partial}{\partial μ _{j a}} x \in C_{j} \sum (x_{a} - μ_{j a})^{2} = x \in C_{j} \sum - 2 (x_{a} - μ_{j a}) .$

Set the derivative to zero (the SSE minimum sits where the slope is flat):

$x \in C_{j} \sum - 2 (x_{a} - μ_{j a}) = 0 \Rightarrow x \in C_{j} \sum x_{a} = ∣ C_{j} ∣ \cdot μ_{j a} .$

Divide both sides by $∣ C_{j} ∣$ — the number of points in the cluster:

$μ_{j a} = \frac{1}{∣ C _{j} ∣} x \in C_{j} \sum x_{a} .$

This holds for every coordinate $a$ , so the minimizer is exactly the average:

$μ_{j} = \frac{1}{∣ C _{j} ∣} x \in C_{j} \sum x .$

That is the mean — so the recomputation step is not a guess; it is the answer to "where should the center sit to minimize this cluster's SSE?" Each step of K-means (assign to nearest centroid, then move the centroid to the mean) makes the SSE smaller, which is the engine behind convergence (Section 13.12.4).

13.12.4 Step 4: Repeat Until Convergence

Steps 2 and 3 repeat until convergence: assign each point to its nearest centroid (which may move points between clusters, so the boundary changes), recompute the centroids, and iterate. The cluster boundary is redefined again and again until convergence. Convergence itself is discussed towards the end of the K-means topic.

Worked mini-loop — why the boundary keeps moving. With centroids at (1,1) and (4,4), a point at (2,2) is closer to (1,1) (distance $2$ ) than to (4,4) (distance $8$ ), so it joins cluster one. Now suppose the recomputation moves $μ_{1}$ to (2.5, 2.5). The same point (2,2) is now distance $0.25 + 0.25 \approx 0.7$ from $μ_{1}$ — still comfortably in cluster one. But a point that sat near the old boundary can flip sides: after the centroids move, its distances change, so the next assignment step may transfer it to the other cluster. Each reassignment changes cluster memberships, each membership change moves the centroids again, and the two keep feeding each other until nobody switches. That mutual adjustment is the whole iteration.

13.12.5 Convergence: Guarantees and Local Minima

Two facts settle the convergence question. First, K-means always stops: every assignment step either keeps or strictly decreases the SSE (points move to nearer centroids, so their squared distances shrink), and every recomputation step strictly decreases the SSE (the mean is the minimizer from Section 13.12.3). The SSE cannot decrease forever — it is bounded below by zero — so after finitely many steps no point changes cluster anymore: the centroids stay put and the algorithm stops. *Second, the stopping point is only guaranteed to be a local minimum of the SSE, not the global one.* Both steps optimize locally — given the current centroids, and given the current assignment — and local moves can get stuck in a valley that is not the lowest one on the map. The practical consequences: (a) different random initializations can end at different clusterings with different SSEs; (b) the standard cure is to run K-means several times and keep the run with the smallest SSE; (c) in practice the algorithm is often stopped early — for example, when fewer than 1% of points change clusters — because most of the improvement happens in the first few iterations.

13.13 Worked Examples: K-Means in Action

13.13.1 Example 1: K = 2 on Eight Points

Setup: a dataset of green points in the plane, with $k = 2$ passed in — partition the space into two clusters.

Step 1: randomly initialize two centroids — $μ_{1}$ shown in blue and $μ_{2}$ shown in red, placed arbitrarily in the space.
Step 2 (assignment): each point is assigned to its nearest centroid. The points rendered blue are assigned to the blue centroid, the points rendered red to the red centroid. Temporarily, the blue points form the blue cluster and the red points the red cluster.
Step 3 (recompute): add all the coordinates of the points in the blue cluster and divide by the number of blue points; same for the red cluster. The blue centroid moves from here to here, the red centroid moves somewhere over there.
Step 4 (iterate): forget the temporary boundaries. Go back to step 2 and assign each point to its nearest centroid again — the assignment changes because the centroids moved. Recompute again: the centroids move again. Iterate until convergence.

At convergence, K-means has produced two stable clusters — one drawn as the "U"-shaped group and one red cluster.

Worked in full with real numbers — a stand-in for the animated demo. Eight points in the plane, two natural groups at the corners:

$A_{1} (1, 1), A_{2} (2, 1), A_{3} (1, 2), A_{4} (2, 2) and B_{1} (6, 1), B_{2} (7, 1), B_{3} (6, 2), B_{4} (7, 2)$

Step 1 — initialize: randomly place $μ_{1} = (3, 3)$ and $μ_{2} = (4, 3)$ (both off-center, on purpose).

Step 2 — assign (squared distances; the closer centroid wins):

Point	$d^{2}$ to $μ_{1} (3, 3)$	$d^{2}$ to $μ_{2} (4, 3)$	Assigned to
$A_{1} (1, 1)$	$(3 - 1)^{2} + (3 - 1)^{2} = 8$	$(4 - 1)^{2} + (3 - 1)^{2} = 13$	$μ_{1}$
$A_{2} (2, 1)$	1+4 = 5	4+4 = 8	$μ_{1}$
$A_{3} (1, 2)$	4+1 = 5	9+1 = 10	$μ_{1}$
$A_{4} (2, 2)$	1+1 = 2	4+1 = 5	$μ_{1}$
$B_{1} (6, 1)$	9+4 = 13	4+4 = 8	$μ_{2}$
$B_{2} (7, 1)$	16+4 = 20	9+4 = 13	$μ_{2}$
$B_{3} (6, 2)$	9+1 = 10	4+1 = 5	$μ_{2}$
$B_{4} (7, 2)$	16+1 = 17	9+1 = 10	$μ_{2}$

Step 3 — recompute:

$μ_{1} = (\frac{1 + 2 + 1 + 2}{4}, \frac{1 + 1 + 2 + 2}{4}) = (1.5, 1.5), μ_{2} = (\frac{6 + 7 + 6 + 7}{4}, \frac{1 + 1 + 2 + 2}{4}) = (6.5, 1.5)$

The centroids move inward toward their groups. Step 4 — iterate: re-assign. Every $A$ -point is distance $0.25 + 0.25 \approx 0.7$ from $μ_{1}$ and far more from $μ_{2}$ ; every $B$ -point is distance $\approx 0.7$ from $μ_{2}$ and far from $μ_{1}$ . No point changes cluster, so the centroids stay put — converged after two iterations, with clusters $C_{1} = {A_{1}, A_{2}, A_{3}, A_{4}}$ , $C_{2} = {B_{1}, B_{2}, B_{3}, B_{4}}$ and final SSE $= 8 \times 0.5 = 4$ .

Sense-check: the two stable clusters match what the eye sees in the data — K-means converged to the natural groupings, exactly the "U"-shaped group and the red group of the lecture demo (where the shapes happened to be a U and a blob; here they are two clean corner blocks).

13.13.2 Example 2: K = 3 Convergence

Setup: all the data points are black in color, and $k = 3$ is passed — partition the space into three clusters.

Step 1: randomly initialize three centroids — one here, one here, one here.
Step 2: assign each point to its nearest centroid.
Iterate: watch the convergence in animation — the centroid moves, the cluster boundary moves, the centroid moves, the cluster boundary moves, again and again. Each iteration shifts both the centroids and the boundaries.

After the iterations settle, there are three clusters, and K-means gives three clean clusters matching what the eye sees in the data. This is how K-means converges in each iteration.

Worked in full with real numbers — a compact twin of the animated demo. Six points in three natural pairs:

$R_{1} (0, 0), R_{2} (1, 1); S_{1} (5, 0), S_{2} (6, 1); T_{1} (0, 5), T_{2} (1, 6)$

Step 1 — initialize: three off-center centroids $μ_{1} = (2, 2)$ , $μ_{2} = (4, 2)$ , $μ_{3} = (2, 4)$ .

Step 2 — assign (squared distances):

Point	to $μ_{1} (2, 2)$	to $μ_{2} (4, 2)$	to $μ_{3} (2, 4)$	Assigned to
$R_{1} (0, 0)$	4+4 = 8	16+4 = 20	4+16 = 20	$μ_{1}$
$R_{2} (1, 1)$	1+1 = 2	9+1 = 10	1+9 = 10	$μ_{1}$
$S_{1} (5, 0)$	9+4 = 13	1+4 = 5	9+16 = 25	$μ_{2}$
$S_{2} (6, 1)$	16+1 = 17	4+1 = 5	16+9 = 25	$μ_{2}$
$T_{1} (0, 5)$	4+9 = 13	16+9 = 25	4+1 = 5	$μ_{3}$
$T_{2} (1, 6)$	1+16 = 17	9+16 = 25	1+1 = 2	$μ_{3}$

Step 3 — recompute: $μ_{1} = (0.5, 0.5)$ , $μ_{2} = (5.5, 0.5)$ , $μ_{3} = (0.5, 5.5)$ — each centroid lands inside its pair.

Step 4 — iterate: with the new centroids, each point is at distance $\approx 0.7$ from its own centroid and far from the other two. Nothing switches — converged after two iterations with three stable clusters, SSE $= 3 \times 0.5 = 1.5$ .

Sense-check: in the lecture animation the same thing happens visually — centroids shift and boundaries redraw each iteration until, after settling, the three clusters match what the eye sees in the data. The numbers here just make visible what the animation shows: assignment and recomputation feeding each other until nobody moves.

13.14 Student Questions on Clustering and K-Means

13.14.1 How Do We Decide the Value of K?

The question came up twice during the K-means walkthrough, and it is one of the most common doubts in this topic.

Q: How do we decide the value of K? It seems subjective — in the demo, people guessed two, three, four, or six clusters.

A: K is very subjective, yes, and there is no fixed rule. We will talk about deciding K in depth — a huge depth discussion — in the coming classes. For now, the basic idea: K is an input parameter, you have to pass it, and the result depends on it. We will also look at ways to choose it properly. (A hint of what "choosing it properly" will mean: since the SSE always falls as K grows, the standard idea is to compare the SSE across several candidate values of K and look for the point where adding one more cluster stops buying much improvement.)

13.14.2 Visualizing High-Dimensional Data

Q: How do we visualize data with two dimensions? Or with ten dimensions — how would we know how many clusters are there?

A: Here the vector space was two-dimensional, so we could see how many clusters there are and pass that as K — very intuitive, nothing wrong. But a lot of the time you do not have proper visualization. If you have 10-dimensional data, there are performance metrics that tell you how the cluster looks: homogeneity is one way we determine how well the clusters are. Visualization is fine, but most of the time you will not have it — at that time you use performance measures that tell you about the quality of the clusters. We will discuss this in the next class.

13.14.3 Performance Metrics for Clusters

Q: Do we have any measure of metric to check the performance measure of the cluster?

A: For K-means, yes, we do have metrics, and we are going to talk about them in the next class. Just as accuracy measures classification, there are performance measures for clustering, and we will see them once we have formed clusters. (The SSE of Section 13.11.2 is the first such quantity — the metric class is wider: homogeneity, and others, come next.)

13.14.4 Why Is K-Means Vulnerable to Outliers?

The professor asked the class to explain the claim made earlier: tell me why K-means will be very vulnerable to outliers.

Q: Can someone tell me why K-means might be very vulnerable to outliers? (The claim earlier was that outliers look significantly different and pull the result.)

A: Because K-means has the notion of a center — the centroid. If this is my cluster and there is one point that belongs to this cluster but sits far out, the cluster boundary becomes distorted, and that one outlier point forces the centroid to move away from the actual center. The centroid shifts because of this one outlier point, which might not be good for the cluster. That is exactly why K-means is very vulnerable to outliers. (The mechanism behind the shift: the centroid is a plain average, and the average is pulled by any far-away value; on top of that, the SSE objective squares the outlier's distance, giving it an outsized vote in what the algorithm optimizes — Section 13.10.5.)

Exam Guidance Summary

Evaluation components running during this period: a quiz (due at the start of May) and an assignment (due on a Friday at the start of May). Both are already open and both count; you have to finish them in time.
Assignment guidance: the same dataset is given to all students; about 60 students had already submitted by this session. Your final prediction is what gets evaluated — and it is not only the score: we look into the scores first, and once we know the scores are fine, we look into the code as well. Both code and final score are verified.

Exam note — the assignment's real grading rule: the final prediction you upload is what gets evaluated. The score is checked first; only once the scores are fine does the code get verified — so both the prediction quality and the code must hold up. The deadline is a Friday at the start of May, and the quiz due at the start of May also counts — finish both on time.

On ensembles for the assignment:

Q: Can we do more than one model for prediction in the assignment?

A: Yes, you can do that. You can use an ensemble of models — the existing ensemble or your own, built to maximize performance; no issue with that either way. The final prediction which you are going to upload is what gets evaluated. We look into the scores first, and once we know the scores are fine, we look into the code as well. Both your code and your final score will be verified.

Study emphasis for the clustering module: the abstract concepts (types of clustering, types of clusters, requirements) are extremely important, even though no specific exam question patterns were announced in this session. The professor's warning to take seriously: "If you do not know what ways you can use to do clustering, most likely you will not do the clustering." Expect to be able to differentiate between the five algorithms — which dataset suits K-means versus DBSCAN, and which performance measures apply to each.

Exam note — where the marks will live: the abstract concepts of this session (Section 13.7 types of clustering, Section 13.8 types of clusters, Section 13.10 requirements) are the examinable core of the module. Expect to compare the five algorithms: which dataset suits K-means versus DBSCAN, and which performance measure belongs to which algorithm. No question patterns were announced, but the professor's emphasis is unambiguous: the abstract view first, the algorithms on top.

Practice task assigned: read up on fuzzy versus non-fuzzy and exclusive versus non-exclusive clustering, and identify which of BIRCH and CURE is the simultaneous algorithm.
Coming classes: choosing K in depth, cluster performance metrics (including homogeneity), and the remaining half of K-means.

Key Industry Applications

Real-world: Google News performs document clustering — it groups the day's news articles into topic clusters (e.g., one cluster for a location's chaos coverage, another for JEE Mains results) so readers interested in one story find all related articles in one place. The cluster is the unit of reading: one click surfaces every article on the story.
Real-world: Market segmentation for products like a new iPhone — cluster the population and market only to the segment most likely to buy, instead of marketing to everyone. Same marketing budget, far better targeting.
Real-world: Clustering as a labeling aid — grouped points can be labeled (group one as label one, group two as label two) when class labels are not available; application-specific, not general. Where natural clusters match real classes, one label per cluster replaces thousands of manual labels.
Real-world: Data reduction and dimensionality reduction — a centroid represents an entire cluster, so the cluster summaries ( $μ_{1}, μ_{2}, \dots$ ) can stand in for thousands of points, the same notion that powers PCA. One million points become fifty centroids; downstream processing works on the fifty.
Real-world: Search engines and many other fields use clustering as one of their standard tools — organizing search results into topics, grouping similar products, and structuring unlabeled collections wherever organization without labels is needed.

DM Lecture 13 notes · Clustering and K-Means

Data Mining· postgraduate· 2026-08-05

Sections Breakdown

113.1 From Supervised to Unsupervised Learning

The supervised recap (labeled pairs and the decision boundary) and the shift to unsupervised learning, which receives only X and must find patterns on its own.

213.2 What Is Clustering

The definition of clustering: high intra-cluster similarity and low inter-cluster similarity, with distance as one example of a similarity measure.

313.3 Clustering versus Classification

How the unsupervised clustering paradigm differs from supervised classification: pattern extraction versus prediction for unseen samples.

413.4 Why Clustering Is Hard: Subjectivity

Why clustering is hard and subjective: the grouping-students example, the two-images example, the how-many-clusters demo, and the fundamental questions clustering must answer.

513.5 Applications of Clustering

Four real-world applications: document clustering (Google News), market segmentation (the iPhone example), labeling data for classification, and data reduction.

613.6 The Roadmap: Five Clustering Algorithms

The module roadmap: abstract concepts first, then K-means, agglomerative and divisive hierarchical clustering, DBSCAN, and a grid-based algorithm.

713.7 Types of Clustering

The six design axes of clustering: hard versus soft, flat versus hierarchical, agglomerative versus divisive, similarity measures, sequential versus simultaneous, and more.

813.8 Types of Clusters

The kinds of clusters an algorithm can produce: center-based (centroid versus medoid), well-separated, continuous, density-based, conceptual, and graph-based.

913.9 Measuring Cluster Quality

How cluster quality is measured: similarity and performance measures such as SSE, and why measures matter most when data cannot be visualized.

1013.10 Requirements of a Clustering Algorithm

The eight requirements of a clustering algorithm: scalability, attribute types, arbitrary shape, minimal parameters, noise handling, input order, high dimensionality, constraints.

1113.11 K-Means Clustering: Overview

K-means overview: the 1957 Lloyd history, the input-output-objective setup, the SSE objective, its taxonomy properties, and time and space complexity.

1213.12 The K-Means Algorithm

The four-step K-means algorithm: centroid initialization, cluster assignment, centroid recomputation, and iteration; convergence guarantees and local minima.

1313.13 Worked Examples: K-Means in Action

Two fully worked K-means examples: k = 2 on eight points and k = 3 on six points, each converged by hand in two iterations with SSE computed.

1413.14 Student Questions on Clustering and K-Means

Student questions and answers on choosing K, visualizing high-dimensional data, cluster performance metrics, and K-means' vulnerability to outliers.

15Exam Guidance Summary

Exam guidance: quiz and assignment deadlines, the score-then-code grading rule, and the study emphasis on the abstract clustering concepts.

16Key Industry Applications

Key industry applications: Google News document clustering, iPhone market segmentation, labeling for classification, data reduction, and search engines.

Postgraduate students in Data Mining

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

From Supervised to Unsupervised Learning

Must-know: Supervised learning gets labeled pairs (X_i, Y_i) and builds a decision boundary for prediction; unsupervised learning gets only X and finds patterns. Clustering is unsupervised.

⚠️ Top pitfall: Thinking clustering needs labels: clustering is defined precisely by having no labels and no right answer.

Self-check: What does the training set contain in supervised learning, and what is missing in unsupervised learning? (Pairs (X_i, Y_i) versus only X_i.)

Connects to: 13.2, 13.3

What Is Clustering

Must-know: Clustering = find groups with high intra-cluster similarity (homogeneous within) and low inter-cluster similarity (distinct between). No labels needed; the similarity measure is a design choice.

⚠️ Top pitfall: Assuming the similarity measure is fixed by the data: the measure (distance, density, other) is chosen by the user, and different measures give different groups.

Self-check: What two conditions define a good cluster? (High intra-cluster similarity, low inter-cluster similarity.)

Connects to: 13.1, 13.4, 13.7

Clustering versus Classification

Must-know: Clustering: unlabeled input, no model, output is groups (pattern extraction). Classification: labeled input, builds a model, output is predictions for unseen samples.

⚠️ Top pitfall: Conflating the two: classification evaluates with accuracy against known labels; clustering has no labels to score against, so quality is judged by cluster performance measures.

Self-check: Why can clustering not be evaluated by accuracy? (No class labels exist to compare against.)

Connects to: 13.1, 13.5, 13.9

Why Clustering Is Hard: Subjectivity

Must-know: Clustering is subjective: no right number of clusters exists; the user supplies the grouping notion (e.g., k). There is no automatic mechanism that finds 'the' clusters.

⚠️ Top pitfall: Expecting a definitive 'correct' clustering: two, three, four, and six clusters were all reasonable answers in the demo because similarity depends on the chosen notion.

Self-check: Why can the same 4,000 students be grouped in several valid ways? (Grouping depends on the attribute used: department, hostel, or club.)

Connects to: 13.2, 13.11

Applications of Clustering

Must-know: Four applications: document clustering (Google News), market segmentation (iPhone launch), labeling for classification (group-based labels, application-specific), data reduction (centroid stands in for the cluster, like PCA).

⚠️ Top pitfall: Thinking clustering can always create labels: label-by-cluster works only when natural clusters match real classes, so it is application-specific, not general.

Self-check: How does clustering reduce a dataset of one million points? (Replace each cluster by its centroid, leaving k representatives.)

Connects to: 13.3, 13.8, 13.10

The Roadmap: Five Clustering Algorithms

Must-know: The five algorithms: K-means (distance-based), agglomerative hierarchical, divisive hierarchical, DBSCAN (density-based), grid-based; CURE and BIRCH are comparison algorithms.

⚠️ Top pitfall: Learning only K-means: without the abstract concepts you cannot tell which dataset suits K-means versus DBSCAN, or which performance measures apply to each.

Self-check: Name the five algorithms in the module roadmap. (K-means, agglomerative, divisive, DBSCAN, grid-based.)

Connects to: 13.7, 13.8, 13.10

Types of Clustering

Must-know: K-means sits in this taxonomy as hard, flat, distance-based, sequential clustering. Agglomerative merges singletons upward; divisive splits one big cluster downward. BIRCH and CURE are simultaneous in nature.

⚠️ Top pitfall: Swapping agglomerative and divisive directions: agglomerative starts with singletons and merges; divisive starts with one cluster and splits. (The cities hierarchy is the memory anchor.)

Self-check: In agglomerative clustering, where do we start and where do we end? (Start: each point its own cluster; end: one big cluster of all points.)

Connects to: 13.8, 13.11, 13.12

Types of Clusters

Must-know: Centroid = (1/n) * sum of the cluster's points (an imaginary center, used by K-means); medoid = the real data point nearest to the centroid (used by K-medoid variants). Well-separated requires every point closer to every member; continuous requires one or more.

$μ = \frac{1}{n} i = 1 \sum n x_{i}$

⚠️ Top pitfall: Thinking the medoid is the geometric center: the medoid is the closest real point to the center, not the center itself; a centroid is usually not a real data point at all.

Self-check: For the cluster {(1,1), (2,3), (6,2)}, what is the centroid and what is the medoid? (Centroid (3,2), an imaginary point; medoid (2,3), the nearest real point.)

Connects to: 13.7, 13.11, 13.12

Measuring Cluster Quality

Must-know: Clustering quality is scored by performance measures (e.g., SSE, later homogeneity), not accuracy. Measures replace the eye when data cannot be visualized.

⚠️ Top pitfall: Judging clusters only by eye: in high dimensions there is no plot, so measures are the only quality signal.

Self-check: When do cluster performance measures matter most? (When the data cannot be visualized, e.g., 10 or more dimensions.)

Connects to: 13.11, 13.14

Requirements of a Clustering Algorithm

Must-know: Euclidean distance in d dimensions: d(x_1, x_2) = sqrt(sum over i=1..d of (x_1i - x_2i)^2). K-means: needs k as input, cannot handle nominal attributes, fails on non-convex (crescent) clusters, is very vulnerable to outliers (squared error punishes them), and works badly in high dimensions.

$d (x_{1}, x_{2}) = i = 1 \sum d (x_{1 i} - x_{2 i})^{2}$

⚠️ Top pitfall: Running center-based clustering on crescent-shaped data: the centroid lands in the middle of the crescent and merges two visually separate clusters into one; a density-based method is needed.

Self-check: Why is K-means very vulnerable to outliers? (The centroid is a mean and the SSE squares each outlier's large distance, pulling the center away from the true cluster.)

Connects to: 13.7, 13.8, 13.12

K-Means Clustering: Overview

Must-know: SSE = sum over j=1..k of sum over x in C_j of ||x - mu_j||^2. K-means input: points x_1..x_n in R^d plus k; output: hard partition into k disjoint sets. Proposed 1957 (Lloyd), published 1982.

$SSE = j = 1 \sum k x \in C_{j} \sum ∥ x - μ_{j} ∥^{2}$

⚠️ Top pitfall: Thinking k can be inferred by the algorithm: for K-means the user must pass k, and different k gives different partitions (k=2, 4, or 6 on the same data).

Self-check: What is the objective function of K-means? (Minimize SSE: the sum of squared distances from each point to its own centroid.)

Connects to: 13.7, 13.12, 13.13

The K-Means Algorithm

Must-know: The four steps: initialize centroids (random), assign each point to the nearest centroid, recompute centroid = mean of the cluster, repeat until convergence. The mean is the centroid that minimizes the cluster's SSE (derived by setting the derivative to zero).

$μ_{j} = \frac{1}{∣ C _{j} ∣} x \in C_{j} \sum x$

⚠️ Top pitfall: Believing K-means always finds the best clustering: it converges to a local minimum of SSE, so random initialization matters; run it multiple times and keep the lowest-SSE result.

Self-check: Why does recomputing the centroid as the mean reduce the SSE? (Setting the derivative of SSE_j with respect to mu_j to zero gives the mean as the minimizer.)

Connects to: 13.11, 13.13, 13.14

Worked Examples: K-Means in Action

Must-know: Assignment rule: each point joins the cluster of its nearest centroid (compare squared distances). Recomputation: new centroid = mean of the cluster's points. Iterate until no point changes cluster; the final clusters match the natural groups the eye sees.

$μ_{j} = \frac{1}{∣ C _{j} ∣} x \in C_{j} \sum x$

⚠️ Top pitfall: Forgetting that assignments can flip between iterations: moving centroids change distances, so a point near the old boundary may switch clusters at the next assignment step.

Self-check: In the k=2 example, why did no point change cluster in iteration 2? (After recomputation each point was about 0.7 units from its own centroid and far from the other, so all assignments stayed.)

Connects to: 13.12, 13.14

Student Questions on Clustering and K-Means

Must-know: K is a subjective user input with no fixed rule; choosing K properly is discussed in coming classes. Homogeneity is one performance measure for clusters. K-means is vulnerable to outliers because the centroid is a mean and the squared error gives a far point a huge influence.

⚠️ Top pitfall: Assuming visualization can always pick K: in 10-dimensional data you cannot see the clusters, so performance measures (e.g., homogeneity) tell you how good they are.

Self-check: Why does one outlier shift a K-means centroid? (The centroid is an average, and the outlier's squared distance to the centroid is large, so moving the center toward it reduces the SSE.)

Connects to: 13.9, 13.10, 13.12

Exam Guidance Summary

Must-know: Assignment rule: the final prediction is evaluated first, then the code; both are verified. Ensembles (existing or your own) are allowed. Study the abstract clustering concepts and be ready to differentiate the five algorithms (K-means versus DBSCAN, their performance measures).

⚠️ Top pitfall: Focusing only on the score: the code is verified after the scores are checked, so both the prediction and the implementation must be sound.

Self-check: What is evaluated for the assignment, in what order? (The final uploaded prediction first; once the scores are fine, the code is verified as well.)

Connects to: 13.6, 13.7, 13.8, 13.10

Key Industry Applications

Must-know: Named industry applications: Google News document clustering, iPhone market segmentation, group labeling for classification, centroid-based data reduction (like PCA), and search engines.

Self-check: How does Google News use clustering? (It groups the day's articles by story so related articles appear in one place.)

Connects to: 13.5

Previous LectureLecture 12 · Association Rule Mining: Apriori and FP-Growth

Next LectureLecture 14 · K-Means and Hierarchical Clustering

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.