MAIE5421 Chap.6 Clustering and Association Rule Learning
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.
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
- 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}.
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.
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.
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.