Skip to content
CampusPrep
AD-502 · Machine Learning/Quick Revision Short Notes

Machine Learning (AD-502) - Unit 2 Short Notes

How unit 2 is examined

Clustering groups unlabelled data by similarity; marks come from BIRCH (14-mark short note), hierarchical clustering with DIANA, GMM with EM, and applications.

Types of Clustering Method

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>Clustering is an unsupervised learning task that groups unlabelled data points so that points in the same cluster are highly similar and points in different clusters are dissimilar.</mark>

Key points.

  1. Clustering is unsupervised: no labels or target are given, and the algorithm discovers the structure from the data alone.
  2. Classification is supervised, learns from labelled examples and predicts a known discrete class; clustering has no labels and its groups are discovered, not predefined.
  3. Regression is supervised and predicts a continuous value; clustering predicts no value, it only assigns group membership.
  4. Partitioning clustering (K-means, K-medoids) splits the data into K non-overlapping groups, with K fixed in advance, by iteratively minimising distance to the cluster centre; it suits spherical clusters.
  5. Distribution model-based clustering assumes each cluster is a probability distribution, usually Gaussian, and gives each point a probability of belonging to each cluster (GMM with EM).
  6. Hierarchical clustering builds a tree of nested clusters (a dendrogram) that can be cut at any level, so K need not be fixed.
  7. Fuzzy clustering (fuzzy C-means) lets a point belong to several clusters with a membership degree between 0 and 1, the memberships of a point summing to 1.

Hierarchical types. Agglomerative is bottom-up: every point starts as its own cluster and the two closest clusters are merged repeatedly, using a linkage (single = minimum distance, complete = maximum, average = mean) until one cluster remains. Divisive is top-down: DIANA (Divisive Analysis) starts with one cluster of all points and splits it repeatedly.

DIANA steps.

Step 1: Put all points in one cluster.
Step 2: Pick the cluster with the largest diameter (largest pairwise distance).
Step 3: Find its most dissimilar point (largest average distance to the others); it starts a splinter group.
Step 4: Move every point that is closer to the splinter group than to the rest into it.
Step 5: Repeat steps 2-4 until every point is a singleton or the desired K is reached.
Basis Agglomerative Divisive (DIANA)
Direction Bottom-up, merge Top-down, split
Start n singleton clusters One cluster of all points
Cost About $O(n^2 \log n)$ Higher, up to exponential if all splits are checked
Decisions Local merges Global view, better top-level splits
Use Very common Rare

Advantages of hierarchical clustering: no K needed and the dendrogram is informative. Limitations: merges or splits cannot be undone, it is slow for large data and sensitive to noise.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-01" viewBox="0 0 376 134" width="376" height="134" role="img" aria-label="Dendrogram idea - agglomerative reads it bottom-up, DIANA reads it top-down"><style>#dsfig-u2-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-01 .t{fill:#16181D;font-weight:500}#dsfig-u2-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-01 .dot{fill:#16181D}#dsfig-u2-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-01 .ah{fill:#454C5A}#dsfig-u2-01 .ah.hi{fill:#2340B8}#dsfig-u2-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-01 .e{stroke:#B1B7C3}html.dark #dsfig-u2-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-01 .t{fill:#E6E8ED}html.dark #dsfig-u2-01 .t.inv{fill:#0F1115}html.dark #dsfig-u2-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-01 .dot{fill:#E6E8ED}html.dark #dsfig-u2-01 .ann{fill:#8FA3FF}html.dark #dsfig-u2-01 .lbl{fill:#858D9C}html.dark #dsfig-u2-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-01 .ah{fill:#B1B7C3}html.dark #dsfig-u2-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="176" y1="39" x2="68" y2="103"/><line class="e" x1="176" y1="39" x2="284" y2="103"/><rect class="n" x="127" y="24" width="98" height="30" rx="8"/><text class="t" x="176" y="39" dy=".35em" text-anchor="middle">All points</text><rect class="n" x="38.5" y="88" width="59" height="30" rx="8"/><text class="t" x="68" y="103" dy=".35em" text-anchor="middle">A B C</text><circle class="n" cx="284" cy="103" r="17"/><text class="t" x="284" y="103" dy=".35em" text-anchor="middle">D E</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Dendrogram idea - agglomerative reads it bottom-up, DIANA reads it top-down</figcaption></figure>

Answer frame. For hierarchical/DIANA: open with the definition and the two types; draw the dendrogram; give agglomerative steps, then DIANA steps, then the comparison and limitations; close with "DIANA is the top-down counterpart of agglomerative clustering". For clustering vs classification/regression: open with the definition in the box, then give the supervised versus unsupervised points, and close with one example (customer segments).

Asked: [8 marks] (Nov 2022, Nov 2023) What is Hierarchical Clustering? Explain DIANA clustering method. Describe hierarchical clustering and its ability to create hierarchical structures of clusters. How does agglomerative hierarchical clustering work? Asked: [7 marks] (Nov 2023) Explain the concept of clustering in machine learning. How does it differ from other tasks like classification and regression? Pitfall: Do not call DIANA agglomerative; it is divisive and splits by diameter.

Birch Algorithm

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) is a hierarchical clustering algorithm for very large numeric datasets that summarises the data into a height-balanced Clustering Feature (CF) tree in a single scan, and then clusters the summaries.</mark>

Clustering Feature. A CF summarises a sub-cluster of $N$ points as a triple:

$$CF = (N,\ LS,\ SS),\quad LS=\sum_{i=1}^{N} x_i,\quad SS=\sum_{i=1}^{N} x_i^2$$

Centroid $=LS/N$; radius $R=\sqrt{SS/N-(LS/N)^2}$. CFs are additive: $CF_1+CF_2=(N_1+N_2,\ LS_1+LS_2,\ SS_1+SS_2)$, so merging needs no raw points.

Example. Points (1,2), (2,3), (3,4): $N=3$, $LS=(6,9)$, $SS=1+4+4+9+9+16=43$. Centroid $=(2,3)$; $R=\sqrt{43/3-(4+9)}=\sqrt{1.33}\approx 1.15$.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-02" viewBox="0 0 238 134" width="238" height="134" role="img" aria-label="CF tree - non-leaf nodes hold CFs of children (branching factor B); leaves hold sub-clusters within threshold T"><style>#dsfig-u2-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-02 .t{fill:#16181D;font-weight:500}#dsfig-u2-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-02 .dot{fill:#16181D}#dsfig-u2-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-02 .ah{fill:#454C5A}#dsfig-u2-02 .ah.hi{fill:#2340B8}#dsfig-u2-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-02 .e{stroke:#B1B7C3}html.dark #dsfig-u2-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-02 .t{fill:#E6E8ED}html.dark #dsfig-u2-02 .t.inv{fill:#0F1115}html.dark #dsfig-u2-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-02 .dot{fill:#E6E8ED}html.dark #dsfig-u2-02 .ann{fill:#8FA3FF}html.dark #dsfig-u2-02 .lbl{fill:#858D9C}html.dark #dsfig-u2-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-02 .ah{fill:#B1B7C3}html.dark #dsfig-u2-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="107" y1="39" x2="45" y2="103"/><line class="e" x1="107" y1="39" x2="169" y2="103"/><rect class="n" x="81" y="24" width="52" height="30" rx="8"/><text class="t" x="107" y="39" dy=".35em" text-anchor="middle">Root</text><circle class="n" cx="45" cy="103" r="17"/><text class="t" x="45" y="103" dy=".35em" text-anchor="middle">CF1</text><circle class="n" cx="169" cy="103" r="17"/><text class="t" x="169" y="103" dy=".35em" text-anchor="middle">CF2</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">CF tree - non-leaf nodes hold CFs of children (branching factor B); leaves hold sub-clusters within threshold T</figcaption></figure>

Key points.

  1. The CF tree is height-balanced and controlled by two parameters: the branching factor $B$ (maximum children per non-leaf node) and the threshold $T$ (maximum radius or diameter of a leaf sub-cluster).
  2. Each point is inserted by descending from the root to the closest leaf entry, using centroid distance.
  3. If the leaf entry can absorb the point and stay within $T$, its CF is updated; otherwise a new entry is made, and a node that overflows $B$ is split, the split propagating upwards.
  4. BIRCH needs only one scan of the data and memory proportional to the tree, giving linear time $O(n)$.
  5. If memory runs out, $T$ is increased and the tree is rebuilt smaller.
  6. It handles outliers by treating sparse leaf entries as noise.

Steps.

Step 1: Scan the data and build the initial CF tree in memory.
Step 2: (Optional) Condense by rebuilding the tree with a larger T.
Step 3: Apply a global clustering (agglomerative or K-means) on the leaf CFs.
Step 4: (Optional) Refine: reassign every point to its nearest final centroid.

Advantages and limitations. Fast, scalable, incremental, and outlier-aware. It works only on numeric data, suits spherical clusters of similar size because it uses radius and diameter, and depends on $T$.

Answer frame. Open with the boxed definition; draw the CF tree; give the CF triple and its additivity, then the four phases, then B and T; close with advantages and limitations. In the 14-mark "any two" question, pick BIRCH plus one other and give each half the space.

Asked: [14 marks] (Nov 2022) Write a short note on any two of the following: a) BIRCH Algorithm b) Confusion Matrix c) Data Augmentation d) Stacking

CURE Algorithm

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>CURE (Clustering Using Representatives) is a hierarchical clustering algorithm that represents each cluster by several well-scattered representative points shrunk toward the centroid.</mark>

Key points.

  1. Each cluster keeps $c$ scattered points instead of one centroid, so it can capture non-spherical shapes and unequal sizes.
  2. The representatives are shrunk toward the centroid by a factor $\alpha$: $p' = p + \alpha\,(\text{centroid} - p)$; shrinking damps the effect of outliers.
  3. Clusters with the closest pair of representatives are merged repeatedly, as in agglomerative clustering.
  4. For large data it clusters a random sample, partitions it, and then labels the remaining points by the nearest representative.

Gaussian Mixture Models and Expectation Maximization

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>A Gaussian Mixture Model assumes the data come from a weighted mixture of K Gaussian distributions, and Expectation Maximization (EM) is the iterative algorithm that estimates their parameters and gives each point a soft cluster membership.</mark>

Formula.

$$p(x)=\sum_{k=1}^{K}\pi_k\,\mathcal{N}(x\mid\mu_k,\Sigma_k),\qquad \sum_k \pi_k=1$$

Parameters per component: mean $\mu_k$, covariance $\Sigma_k$, and mixing coefficient $\pi_k$.

Key points.

  1. Distribution model-based clustering treats every cluster as a probability distribution, so a cluster is described by its parameters and not just a centre.
  2. A GMM is a mixture of Gaussians with weights, and it can model elliptical clusters of different size through the covariance.
  3. The parameters cannot be found directly because the cluster labels are hidden (latent), so EM alternates two steps.
  4. E-step: compute the responsibility of each component for each point, $\gamma_{ik}=\dfrac{\pi_k\mathcal{N}(x_i\mid\mu_k,\Sigma_k)}{\sum_j \pi_j\mathcal{N}(x_i\mid\mu_j,\Sigma_j)}$.
  5. M-step: update $\mu_k=\dfrac{\sum_i\gamma_{ik}x_i}{\sum_i\gamma_{ik}}$, $\Sigma_k$ as the weighted covariance, and $\pi_k=\dfrac{1}{n}\sum_i\gamma_{ik}$.
  6. The steps repeat until the log-likelihood stops improving; each iteration never decreases it, but it may converge to a local optimum, so initialisation (often K-means) matters.
  7. Importance of EM: it gives soft clustering with probabilities, it copes with missing data and hidden variables, and it rests on a probabilistic model; K-means is the special case with equal spherical clusters and hard assignment.

Answer frame. Open with "clustering is unsupervised grouping of similar points" and then define GMM; write the mixture formula; develop E-step, M-step, stopping rule in that order; close with the importance points (soft clustering, missing data, probabilistic basis).

Asked: [7 marks] (Nov 2022, Nov 2023) What is clustering? Discuss the importance of Expectation Maximization clustering method. Explain the concept of distribution model-based clustering. What are Gaussian Mixture Models (GMMs), and how are they used in this context?

Parameters estimations – MLE, MAP

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>MLE chooses the parameters that maximise the likelihood of the observed data, while MAP maximises the posterior, which adds a prior belief about the parameters.</mark>

Key points.

  1. MLE: $\hat\theta_{MLE}=\arg\max_\theta P(D\mid\theta)$, usually done on the log-likelihood.
  2. MAP: $\hat\theta_{MAP}=\arg\max_\theta P(D\mid\theta)P(\theta)$, from Bayes' rule since the posterior is proportional to likelihood times prior.
  3. MAP equals MLE when the prior is uniform, and with much data the prior matters less.
  4. MAP reduces overfitting on small data, and a Gaussian prior gives L2 regularisation.

Applications of Clustering

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>Clustering finds natural groups in unlabelled data, which suits any domain where labels are missing or costly.</mark>

Key points.

  1. Marketing: customer segmentation groups buyers by behaviour for targeted offers.
  2. Biology: genes and species are grouped by similarity, for example gene-expression analysis.
  3. Image processing: segmentation and colour quantisation group pixels.
  4. Documents: news and web pages are grouped by topic, and search results are organised.
  5. Anomaly detection: points far from every cluster are flagged as fraud or intrusion.
  6. Recommendation and social networks: similar users or communities are found.

Asked: [6 marks] (Nov 2022) Discuss different application areas where Clustering is used?

Last-minute revision

  • Clustering is unsupervised: no labels, groups are discovered.
  • Partitioning fixes K; hierarchical builds a dendrogram; GMM gives probabilities; fuzzy gives membership degrees.
  • Agglomerative is bottom-up merge; DIANA is top-down split by largest diameter.
  • $CF=(N,LS,SS)$; centroid $LS/N$; CFs add.
  • BIRCH has parameters B and T, one scan, linear time, numeric data only.
  • CURE uses scattered representatives shrunk by $\alpha$.
  • GMM: $p(x)=\sum\pi_k\mathcal{N}(x\mid\mu_k,\Sigma_k)$.
  • EM: E-step responsibilities, M-step updates, repeat till likelihood converges.
  • MLE maximises $P(D\mid\theta)$; MAP maximises $P(D\mid\theta)P(\theta)$.

Memory hooks

  • BIRCH: "N, LS, SS" and the tree is balanced with B and T.
  • DIANA splits Down; agglomerative Adds up.
  • EM: Expect (soft assign), then Maximise (update).
  • MAP is MLE plus a Prior.

Coverage checklist

  • Types of Clustering Method: Partitioning Clustering, Distribution Model-Based Clustering, Hierarchical Clustering, Fuzzy Clustering: 8-mark hierarchical/DIANA, 7-mark clustering vs classification/regression.
  • Birch Algorithm: 14-mark short note.
  • CURE Algorithm: not asked recently.
  • Gaussian Mixture Models and Expectation Maximization: 7-mark EM/GMM.
  • Parameters estimations – MLE, MAP: not asked recently.
  • Applications of Clustering: 6-mark applications.
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in