The Hong Kong University of Science and Technology · FACULTY OF COMPUTER SCIENCE

MAIE5421 Chap.6 Clustering and Association Rule Learning

- one subject, every graph, every model, every mark
8 Chapters5-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 6 of 10 · MAIE5421

Clustering and Association Rule Learning

Learning without labels

Unsupervised learning finds patterns in data that carries no labels. The lecture groups it into clustering, which partitions samples into groups whose members are more similar to each other than to members of other groups; association rule learning, which discovers items that tend to occur together; and dimensionality reduction, which compresses the number of variables.

Clustering has a direct vision use in image segmentation, where pixels with similar colour or texture are grouped into regions.

Judging a clustering

A good clustering is compact inside each cluster and well separated between clusters. Inertia measures compactness as the total distance from points to their own cluster's centroid, and smaller is better.

The Dunn index measures both at once, dividing the smallest distance between clusters by the largest distance within a cluster, and larger is better.

K-Means and hierarchical clustering

K-Means fixes the number of clusters in advance, picks starting centroids, and alternates between assigning each point to its nearest centroid and moving each centroid to the mean of its points, stopping when the centroids settle, when no labels change or after a maximum number of iterations.

Too few clusters underfit and too many overfit, and the elbow of a curve of the evaluation metric against k is the usual guide. Hierarchical clustering avoids choosing k up front.

The agglomerative version merges the two closest clusters repeatedly, using single, complete, average or centroid linkage to measure the distance between groups, and records the merges in a dendrogram; the divisive version starts from one cluster and splits.

Normalising features before measuring distance

Because clustering compares distances, features on very different scales distort the result, and the lecture teaches min-max scaling and standardisation, applied to each attribute separately.

Association rules and the Apriori algorithm

Association rules are scored by support, how often an itemset appears; confidence, the conditional probability of the consequent given the antecedent; and lift, which compares that confidence with the consequent's overall frequency.

The Apriori algorithm finds frequent itemsets level by level, pruning any candidate with an infrequent subset, and the lecture stresses that the rules it finds describe co-occurrence, not causation.

In this chapter

What this chapter covers

  • 01

    Clustering, association rules and dimensionality reduction

  • 02

    Compactness, separation, inertia and the Dunn index

  • 03

    The K-Means assignment and update loop

  • 04

    Stopping criteria and the elbow curve for choosing k

  • 05

    Agglomerative and divisive hierarchical clustering

  • 06

    Single, complete, average and centroid linkage

  • 07

    Min-max scaling and standardisation

  • 08

    Support, confidence, lift and the Apriori algorithm

Worked example · free

Build a single-linkage dendrogram and compare complete linkage

Q [7 marks]. AskSia-authored practice. Five one-dimensional values, 1, 2, 4, 8 and 9, are clustered agglomeratively. List the merges and their heights under single linkage, say where the third merge would happen under complete linkage, and give the clusters obtained by cutting the single-linkage tree at height 3. The marks shown are an AskSia study allocation and are not the University's marking scheme.
A single-linkage dendrogram of five values.A single-linkage dendrogram of five values. Each horizontal bar is drawn at the distance at which two clusters merge, and cutting the tree at a distance of 3 leaves the two clusters {1, 2, 4} and {8, 9}.02412489Merge distancecut at 3
A single-linkage dendrogram of five values. Each horizontal bar is drawn at the distance at which two clusters merge, and cutting the tree at a distance of 3 leaves the two clusters {1, 2, 4} and {8, 9}.
  • 2Closest pairs first: {1, 2} and {8, 9} merge at distance 1.
  • 2Single linkage: {1, 2} joins 4 at distance 2, the gap from 2 to 4.
  • 2Final merge at 4, the gap between 4 and 8; under complete linkage the third merge is at 3, the distance from 1 to 4.
  • 1A cut at height 3 crosses the tree below the final merge, leaving {1, 2, 4} and {8, 9}.
Under single linkage the merges happen at heights 1, 1, 2 and 4, so the dendrogram has two low joins, a join of 4 onto {1, 2} at 2 and a final join at 4. Complete linkage measures the farthest pair instead, so 4 joins {1, 2} at height 3 and the final merge rises to 8, the distance from 1 to 9. Cutting the single-linkage tree at 3 leaves two clusters, {1, 2, 4} and {8, 9}, without ever having to choose the number of clusters in advance.
Sia tip — Write down which pair of members defines each merge distance. Single linkage uses the nearest pair, complete linkage the farthest, and confusing them changes every height above the first merge.
Glossary

Key terms

Clustering
Partitioning a dataset into groups so that members of the same group are more similar to each other than to members of other groups.
Centroid
The mean position of the points in a cluster, which K-Means recomputes at every update step.
Inertia
The total distance from each point to the centroid of its cluster, a measure of compactness for which smaller is better.
Dunn Index
The smallest distance between clusters divided by the largest distance within a cluster, for which larger is better.
Elbow Curve
A plot of a clustering metric against the number of clusters, read at the point where improvement levels off.
Dendrogram
The tree diagram produced by hierarchical clustering, whose merge heights record the distances at which clusters join.
Lift
The confidence of an association rule divided by the frequency of its consequent, where a value above 1 indicates positive association.
Apriori Property
The rule that every subset of a frequent itemset is frequent, so any superset of an infrequent itemset can be pruned.
FAQ

Clustering and Association Rule Learning FAQ

How do I choose k for K-Means?

Run K-Means for a range of k and plot an evaluation metric such as inertia against k. The metric keeps improving as k grows, so look for the elbow, the point after which the improvement becomes small. The lecture warns that too small a k underfits by merging real groups, while too large a k overfits by giving noise and outliers clusters of their own.

Why must data be normalised before clustering?

Because clustering compares distances, and a feature measured on a large scale swamps one measured on a small scale. Weight in kilograms and height in centimetres span different ranges, so without scaling one of them would decide almost every distance. Min-max scaling or standardisation, applied to each attribute separately, gives the features equal importance.

Does a strong association rule mean one item causes the other?

No. The lecture states plainly that association rule learning does not find causality. A rule with high support and confidence says that items appear together often, which is useful for placement or recommendation, but both could be driven by a third factor. Lift helps to separate a genuine association from a consequent that is simply common everywhere.

Study strategy

Assessment move

Run K-Means by hand on six one-dimensional points until it stops, then change one starting centroid and run it again to see whether the result changes. Do the same for Apriori on a handful of short transactions, writing every candidate itemset with its support count. Both algorithms are easy to follow and easy to slip on, and a written trace is the only reliable check.

Working through Clustering and Association Rule Learning in MAIE5421? Sia is AskSia’s AI Computer Science tutor — ask any MAIE5421 Clustering and Association Rule Learning question and get a clear, step-by-step explanation grounded in how MAIE5421 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.

A+Everything unlocked
Unlocks this Bible + all 13 of your subjects at The Hong Kong University of Science and Technology, plus 1,000+ more Bibles across the AskSia library.
Sia - your MAIE5421 tutor, unlimited, worked the way the exam marks it
The full 5-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works