Cluster Analysis & k-means
What clustering is and why it's useful, the eight requirements of clustering in data mining, the five families of clustering methods (partitioning, hierarchical, density-, grid- and model-based), and the k-means algorithm worked step by step.
▶Lecture videos
Click any timestamp — here or inside the notes — to jump the video to that moment. Your position is remembered.
Clustering & k-means
Good clustering, distance functions (Minkowski, Manhattan, Euclidean), and the lesson's k-means example worked through.
00:01Good clustering: high intra-class, low inter-class similarity00:47Distance functions return one number per pair01:51Minkowski distance: q = 1 Manhattan, q = 2 Euclidean02:50k-means: the four steps04:21Example: initial centres A1, A4, A704:54Iteration 1: distance table A1–A806:30New centres from the cluster means07:03Recalculate until the centres are stablek-means animation
A short silent animation of k-means assigning points and moving the centres.
Weka 2.4 – Baseline accuracy
Always compare against ZeroR, the classifier that just guesses the most popular class.
00:15Introduction: baseline accuracy00:24The diabetes data set (Pima Indians)01:34J48, Naive Bayes, IBk and PART compared03:10Is 76% good? 500 of 768 are negative03:47ZeroR: always guess the most popular class (65%)05:00Supermarket data: the baseline beats every scheme06:41Lessons: try ZeroR first, simplicity is bestWeka 2.5 – Cross-validation
The standard evaluation method: 10-fold and stratified cross-validation.
00:16Introduction: the standard way to evaluate01:02Cross-validation improves on repeated holdout02:1610-fold cross-validation: divide once into 10 folds03:17Stratified cross-validation03:51Weka runs the algorithm an 11th time on all the data04:47Rule of thumb: lots of data → percentage split; otherwise 10-foldWeka 2.6 – Cross-validation results
Cross-validation vs repeated holdout on the diabetes data: same mean, much smaller variance.
01:13Introduction: cross-validation results01:55Baseline on diabetes: 65.1%02:31J48 with 10-fold cross-validation: 73.8%, 75%, 75.5%…03:32Mean 74.5%, standard deviation 0.9%03:45Repeated holdout: mean 74.8%, standard deviation 4.6%04:28Why 10 folds and not 20?06:00Cross-validation reduces the variance of the estimate1What is cluster analysis?
Clustering is grouping a set of physical or abstract objects into classes of similar objects.
A cluster is a collection of data objects that are similar to one another within the same cluster and dissimilar to objects in other clusters.
- A cluster can be treated as one group, so clustering is also a form of data compression.
- Classification needs a costly, labelled training set. Clustering goes the reverse way: first partition the data into groups by similarity, then assign labels to the small number of groups.
- Extra advantages: it adapts to changes and helps single out the features that distinguish groups.
Classification (supervised)
Classes are known in advance; learn from labelled tuples.
Clustering (unsupervised)
No class labels; discover the groups from the data itself.
Where clustering is used
| Use | Example |
|---|---|
| Market research / business | Discover distinct customer groups from purchasing patterns |
| Pattern recognition, image processing | Group similar pixels or shapes |
| Data segmentation | Partition a large data set into similar groups |
| Outlier detection | Values "far away" from every cluster, e.g. credit card fraud, criminal activity in e-commerce |
By automated clustering we can find dense and sparse regions in the object space and so discover overall distribution patterns and correlations among attributes.
2Requirements of clustering in data mining
| Requirement | What it means |
|---|---|
| Scalability | Work on millions of objects, not just a few hundred. Clustering only a sample may give biased results |
| Ability to deal with different types of attributes | Not only numeric (interval-based) data, but binary, categorical (nominal), ordinal and mixtures |
| Discovery of clusters with arbitrary shape | Euclidean/Manhattan-based methods find spherical clusters of similar size and density; real clusters can be any shape |
| Minimal domain knowledge for input parameters | Results can be very sensitive to parameters such as k, which are hard to choose for high-dimensional data |
| Ability to deal with noisy data | Real databases have outliers and missing, unknown or erroneous values |
| Incremental clustering and insensitivity to input order | Absorb new data without starting from scratch; give the same clusters whatever the order of the records |
| High dimensionality | Handle many attributes, not just 2–3 (human eyes can only judge up to 3) |
| Constraint-based clustering | Cluster under real-world constraints, e.g. placing new ATMs while respecting rivers and highway networks |
| Interpretability and usability | Results must be understandable and usable for the application goal |
Scalable · Types of data · Arbitrary shape · Parameters (minimal) · Noise · Incremental/order · High dimensions · Constraints · Interpretable
3Types of clustering methods
| Method | Idea | Examples |
|---|---|---|
| Partitioning | Build k partitions (k ≤ n) and improve them by iterative relocation | k-means, k-medoids |
| Hierarchical | Build a hierarchical decomposition: merge bottom-up or split top-down | Chameleon, BIRCH |
| Density-based | Keep growing a cluster while the neighbourhood density exceeds a threshold | DBSCAN, OPTICS, DENCLUE |
| Grid-based | Quantise the space into a finite grid of cells and cluster the cells | STING, WaveCluster |
| Model-based | Hypothesise a model for each cluster and find the best fit | EM, COBWEB, SOM |
Partitioning methods
Given n objects, construct k partitions, each a cluster, with k ≤ n:
- Each group contains at least one object, and
- Each object belongs to exactly one group (relaxed in fuzzy partitioning).
Start from an initial partitioning, then use iterative relocation: move objects between groups so objects in the same cluster are "close" and objects in different clusters are "far apart".
Global optimality would need every possible partition, so heuristics are used:
k-means
Each cluster is represented by the mean value of its objects.
k-medoids
Each cluster is represented by one of the objects located near the centre.
Both work well for spherical clusters in small to medium databases.
Hierarchical methods
Agglomerative (bottom-up)
Start with each object as its own group; successively merge the closest groups until one group remains (or a termination condition holds).
Divisive (top-down)
Start with all objects in one cluster; successively split until each object is in its own cluster (or a termination condition holds).
Once a merge or split is done, it can never be undone. That keeps computation cheap, but erroneous decisions can't be corrected.
Two ways to improve quality:
- Careful analysis of object linkages at each step, as in Chameleon.
- First group objects into microclusters hierarchically, then macro-cluster them with another method (e.g. iterative relocation), as in BIRCH.
Density-based methods
- Distance-based methods only find spherical clusters.
- Density-based methods keep growing a cluster while the neighbourhood of a given radius contains at least a minimum number of points.
- They filter out noise (outliers) and find clusters of arbitrary shape.
- DBSCAN and its extension OPTICS grow clusters by density-based connectivity; DENCLUE analyses the distribution of density functions.
Grid-based methods
- Quantise the object space into a finite number of cells (a grid) and do all clustering on the grid.
- Main advantage: fast processing, independent of the number of objects and dependent only on the number of cells per dimension.
- STING is typical; WaveCluster uses wavelet transformation and is both grid- and density-based.
Model-based methods
- Hypothesise a model for each cluster and find the best fit of the data.
- Can build a density function of the data's spatial distribution, and can determine the number of clusters automatically using statistics, while handling noise.
| Algorithm | Approach |
|---|---|
| EM | Expectation-maximisation based on statistical modelling |
| COBWEB | Conceptual learning using probability analysis |
| SOM | Self-organising feature map: a neural network mapping high-dimensional data onto a 2-D or 3-D map (good for visualisation) |
4Clustering by k-means
The k-means algorithm takes the parameter k and partitions n objects into k clusters so that intracluster similarity is high and intercluster similarity is low. Similarity is measured against the cluster's mean: its centroid or centre of gravity.
- Randomly select k objects as the initial cluster centres
- Assign every object to the nearest centre
- Recompute each cluster's mean
- Repeat 2–3 until the assignments stop changing
Distance functions
The quality of clustering depends on the similarity measure. A distance function returns one number for the distance between two data elements, however many attributes they have. Each element joins the cluster at minimum distance 00:47.
| q | Name | 2-D form |
|---|---|---|
| 1 | Manhattan distance | |x₂ − x₁| + |y₂ − y₁| |
| 2 | Euclidean distance (the most popular) | √((x₂ − x₁)² + (y₂ − y₁)²) |
This lesson's example uses Manhattan distance.
Worked example (from the lesson)
Cluster the eight points into 3 clusters using Manhattan distance:
A1(2, 10) · A2(2, 5) · A3(8, 4) · A4(5, 8) · A5(7, 5) · A6(6, 4) · A7(1, 2) · A8(4, 9)
Initial centres: A1(2, 10), A4(5, 8), A7(1, 2).
Iteration 1: distances to the initial centres
| Point | to (2, 10) | to (5, 8) | to (1, 2) | Cluster |
|---|---|---|---|---|
| A1 (2, 10) | 0 | 5 | 9 | 1 |
| A2 (2, 5) | 5 | 6 | 4 | 3 |
| A3 (8, 4) | 12 | 7 | 9 | 2 |
| A4 (5, 8) | 5 | 0 | 10 | 2 |
| A5 (7, 5) | 10 | 5 | 9 | 2 |
| A6 (6, 4) | 10 | 5 | 7 | 2 |
| A7 (1, 2) | 9 | 10 | 0 | 3 |
| A8 (4, 9) | 3 | 2 | 10 | 2 |
New centres (means):
- Cluster 1 = {A1} → (2, 10)
- Cluster 2 = {A3, A4, A5, A6, A8} → ((8+5+7+6+4)/5, (4+8+5+4+9)/5) = (6, 6)
- Cluster 3 = {A2, A7} → ((2+1)/2, (5+2)/2) = (1.5, 3.5)
Iteration 2: distances to the new centres
| Point | to (2, 10) | to (6, 6) | to (1.5, 3.5) | Cluster |
|---|---|---|---|---|
| A1 (2, 10) | 0 | 8 | 7 | 1 |
| A2 (2, 5) | 5 | 5 | 2 | 3 |
| A3 (8, 4) | 12 | 4 | 7 | 2 |
| A4 (5, 8) | 5 | 3 | 8 | 2 |
| A5 (7, 5) | 10 | 2 | 7 | 2 |
| A6 (6, 4) | 10 | 2 | 5 | 2 |
| A7 (1, 2) | 9 | 9 | 2 | 3 |
| A8 (4, 9) | 3 | 5 | 8 | 1 |
Table 13-3 gives A8's distance to (1.5, 3.5) as 6. It's actually |4 − 1.5| + |9 − 3.5| = 2.5 + 5.5 = 8. A8 still goes to cluster 1, so the result doesn't change.
Centres after the second iteration (the question's answer):
- Cluster 1 = {A1, A8} → (3, 9.5)
- Cluster 2 = {A3, A4, A5, A6} → (6.5, 5.25)
- Cluster 3 = {A2, A7} → (1.5, 3.5)
Iteration 3: A4(5, 8) is now closer to (3, 9.5) (distance 3.5) than to (6.5, 5.25) (distance 4.25), so it moves to cluster 1. The centres become (3.67, 9), (7, 4.33) and (1.5, 3.5).
Iteration 4: no point changes cluster, so k-means has converged:
- Cluster 1 = {A1, A4, A8}
- Cluster 2 = {A3, A5, A6}
- Cluster 3 = {A2, A7}
Points A1–A8 from the lesson. Pick the three starting centres, then step through the iterations.
Strengths and weaknesses of k-means
| Strengths | Weaknesses |
|---|---|
| Simple and relatively efficient | You must choose k in advance |
| Works well for compact, spherical clusters | Result depends on the initial centres |
| Scales to small–medium data | Sensitive to noise and outliers (they pull the mean) |
| Can't find clusters of arbitrary shape |
For a k-means question, show:
- The distance table for every point against every centre
- The cluster each point joins
- The new means, with the arithmetic
- Repeat for the iterations asked, and say when it converges
5Weka: baseline accuracy and cross-validation
2.4 Baseline accuracy
On the diabetes data set (Pima Indians; tested_negative / tested_positive) with a percentage split 01:34:
| Classifier | Accuracy |
|---|---|
| J48 (trees) | 76% |
| NaiveBayes (bayes) | 77% |
| IBk (lazy) | 73% |
| PART (rules) | 74% |
| ZeroR (baseline) | 65% |
ZeroR just predicts the most popular class every time. On diabetes, 500 of 768 instances are negative, so it's right 500/768 = 65% of the time 03:47. J48's 76% is clearly above the baseline, but not by a huge amount.
On the supermarket data set, ZeroR gets about 64%, while J48, NaiveBayes and PART get about 63% and IBk only 38% 05:00. The attributes there aren't informative.
- Always try ZeroR first, before anything else.
- Simplicity is best: try simple classifiers before complex ones.
- Ask whether small differences (like 1%) are significant.
- Don't apply Weka blindly: understand your data.
2.5 Cross-validation
Evaluation options so far: an independent test set, the training set (don't!), and holdout (percentage split, possibly repeated). The fourth is cross-validation 00:52.
Divide the data once into k equal folds (usually 10). Hold out each fold in turn for testing, train on the other k − 1, then average the k results 02:16. Every instance is used once for testing and k − 1 times for training.
- Stratified cross-validation makes each fold have about the right proportion of each class. It reduces the variance further, and it's Weka's default 03:17.
- With 10-fold cross-validation, Weka runs the algorithm 11 times: once per fold, plus a final time on the whole data set to build the classifier you'd deploy 03:51.
- Lots of data (say 10,000+ instances in a two-class problem) → a percentage split, evaluated once, is fine.
- Not much data (under about 1,000) → use stratified 10-fold cross-validation.
- More classes need more data for a fair representation of each class.
2.6 Cross-validation results
J48 on diabetes, with 10 different random seeds 02:31:
| Method | Mean accuracy | Standard deviation |
|---|---|---|
| 10-fold cross-validation | 74.5% | 0.9% |
| Repeated holdout (90/10, 10 times) | 74.8% | 4.6% |
| ZeroR baseline | 65.1% |
Both give about the same mean, but cross-validation has a much smaller variance. So J48 scores about 74.5% (roughly 73.5%–75.5%), well above the 65.1% baseline 06:00.
Why 10 folds, not 20? 04:28 More folds train on more data (95% vs 90%), but each test fold gets smaller (a weaker statistical sample) and it takes twice as long. There's no perfect answer; 10-fold is the standard and Weka's default.
6Quick revision sheet
| Concept | Remember it as |
|---|---|
| Clustering | Group similar objects; high intra-, low inter-cluster similarity |
| vs classification | Unsupervised: no labels needed; label the groups afterwards |
| Uses | Customer groups, image processing, data segmentation, outlier detection (fraud) |
| Requirements | Scalable, types, arbitrary shape, few parameters, noise, incremental/order, high-D, constraints, interpretable |
| Partitioning | k groups, each ≥ 1 object, each object in exactly 1; k-means, k-medoids |
| Hierarchical | Agglomerative (bottom-up) / divisive (top-down); can't undo; Chameleon, BIRCH |
| Density-based | Grow while neighbourhood dense; arbitrary shapes, filters noise; DBSCAN, OPTICS, DENCLUE |
| Grid-based | Cells; fast, depends on number of cells; STING, WaveCluster |
| Model-based | Fit a model per cluster; EM, COBWEB, SOM |
| k-means | Pick k centres → assign to nearest → recompute means → repeat |
| Example answer | After iteration 2: (3, 9.5), (6.5, 5.25), (1.5, 3.5) |
| Distances | Minkowski: q = 1 Manhattan, q = 2 Euclidean |
| Baseline | ZeroR = always guess the majority class; diabetes 500/768 = 65% |
| Cross-validation | k folds; each tested once; average; stratified = class proportions kept |
| Weka runs | k + 1 times (folds + final model) |
| CV vs holdout | Same mean (74.5% vs 74.8%), smaller SD (0.9% vs 4.6%) |
?Self-check quiz
23 questions on this week. Answer them all, then press Check my answers. Your best and latest scores are saved and shown on the subject page.