Data Mining and Warehousing (AD-603 (A)) Unit 5 Notes

How unit 5 is examined

This unit covers clustering (hierarchical, partitional, BIRCH, DBSCAN, CURE) and association rule mining (Apriori, FP-growth); the marks sit on Apriori and rule selection, FP-growth, BIRCH and hierarchical clustering issues.

Hierarchical algorithms

<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>Hierarchical clustering builds a tree of nested clusters called a dendrogram, either bottom-up (agglomerative) by merging the closest clusters or top-down (divisive) by splitting a cluster, without fixing the number of clusters in advance.</mark>

Key points.

Agglomerative clustering starts with every object as its own cluster and repeatedly merges the two closest clusters until one remains; divisive clustering does the reverse.
Linkage decides the inter-cluster distance: single link uses the minimum pair distance, complete link the maximum, average link the mean, and centroid link the distance between centroids.
Single link suffers from the chaining effect and handles arbitrary shapes; complete link is compact but sensitive to outliers.
Scalability is the main issue: the algorithm needs an $O(n^2)$ distance matrix and about $O(n^2)$ to $O(n^3)$ time, so it is unsuitable for large databases (BIRCH and CURE address this).
Merges and splits are irreversible, so an early bad decision can never be corrected.
Termination needs a criterion: stop at a desired number of clusters $k$, or cut the dendrogram at a distance threshold.
It is sensitive to noise and outliers, and there is no global objective function.

Answer frame. Open with the definition and the two types; then develop key issues 4, 2, 5, 6, 7 with the remedy for each (BIRCH/CURE for scale, a threshold or $k$ to terminate); close by saying the method suits small data needing a taxonomy.

Asked: [7 marks] (May 2023) What are key issues in hierarchical clustering? Explain.

Partitional algorithms

Definition. Partitional clustering divides $n$ objects directly into $k$ non-overlapping clusters, with $k$ given in advance, by optimising a criterion such as the squared error.

Key points.

K-means picks $k$ initial centres, assigns each object to the nearest centre, recomputes each centre as the cluster mean, and repeats until assignments stop changing.
It minimises $E=\sum_{i=1}^{k}\sum_{x\in C_i}\lVert x-m_i\rVert^2$, where $m_i$ is the mean of cluster $C_i$.
Its cost is $O(nkt)$ for $t$ iterations, which is efficient, but it depends on the initial centres, needs $k$, finds only spherical clusters and is hurt by outliers.
K-medoids (PAM) uses an actual object as the centre, so it resists outliers better but costs more.

Clustering large databases: BIRCH, DBSCAN, CURE

Definition. <mark>BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) clusters very large data in a single scan by summarising it into a height-balanced Clustering Feature tree (CF-tree) held in memory.</mark>

Key points.

A Clustering Feature is the triple $CF=(N, LS, SS)$: the number of points, their linear sum and their squared sum.
From a CF the centroid $LS/N$, the radius and the diameter are computed, and two CFs merge by simply adding their triples (additivity).
The CF-tree has a branching factor $B$ (children per non-leaf node) and a threshold $T$ (maximum radius of a leaf entry); a new point descends to the closest leaf entry and is absorbed if the radius stays within $T$, otherwise it makes a new entry and a full node splits.
Phase 1 scans the database and builds the initial CF-tree in memory, rebuilding with a larger $T$ if memory runs out.
Phase 2 (optional) condenses the tree into a smaller one by removing outliers and merging crowded sub-clusters.
Phase 3 applies a global clustering algorithm (such as agglomerative or k-means) to the leaf CFs, and Phase 4 (optional) refines by reassigning every point to the nearest centroid.
It is linear, $O(n)$, needs one scan and little memory, but it suits only spherical clusters of similar size because it uses radius and diameter.

Answer frame. Open with the full form and the one-scan idea; draw a small CF-tree (root, non-leaf, leaf entries carrying CF triples); then develop points 1-3 and the four phases; close with scalability and the spherical-cluster limitation.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-01" viewBox="0 0 252 194" width="252" height="194" role="img" aria-label="CF-tree, each entry holds (N, LS, SS); leaves hold sub-clusters"><style>#dsfig-u5-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-01 .t{fill:#16181D;font-weight:500}#dsfig-u5-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-01 .dot{fill:#16181D}#dsfig-u5-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-01 .ah{fill:#454C5A}#dsfig-u5-01 .ah.hi{fill:#2340B8}#dsfig-u5-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-01 .e{stroke:#B1B7C3}html.dark #dsfig-u5-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-01 .t{fill:#E6E8ED}html.dark #dsfig-u5-01 .t.inv{fill:#0F1115}html.dark #dsfig-u5-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-01 .dot{fill:#E6E8ED}html.dark #dsfig-u5-01 .ann{fill:#8FA3FF}html.dark #dsfig-u5-01 .lbl{fill:#858D9C}html.dark #dsfig-u5-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-01 .ah{fill:#B1B7C3}html.dark #dsfig-u5-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah7" 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="ahh7" 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="114" y1="37" x2="114" y2="101"/><line class="e" x1="114" y1="101" x2="60" y2="165"/><line class="e" x1="114" y1="101" x2="168" y2="165"/><rect class="n" x="88" y="22" width="52" height="30" rx="8"/><text class="t" x="114" y="37" dy=".35em" text-anchor="middle">Root</text><rect class="n" x="76" y="86" width="76" height="30" rx="3"/><text class="t" x="95" y="101" dy=".35em" text-anchor="middle">CF1</text><line class="kd" x1="114" y1="86" x2="114" y2="116"/><text class="t" x="133" y="101" dy=".35em" text-anchor="middle">CF2</text><rect class="n" x="14" y="150" width="92" height="30" rx="3"/><text class="t" x="37" y="165" dy=".35em" text-anchor="middle">CF11</text><line class="kd" x1="60" y1="150" x2="60" y2="180"/><text class="t" x="83" y="165" dy=".35em" text-anchor="middle">CF12</text><rect class="n" x="122" y="150" width="92" height="30" rx="3"/><text class="t" x="145" y="165" dy=".35em" text-anchor="middle">CF21</text><line class="kd" x1="168" y1="150" x2="168" y2="180"/><text class="t" x="191" y="165" dy=".35em" text-anchor="middle">CF22</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">CF-tree, each entry holds (N, LS, SS); leaves hold sub-clusters</figcaption></figure>

Asked: [7 marks] (Jun 2025) Explain the BIRCH scalable Algorithm.

DBSCAN

Definition. DBSCAN is a density-based algorithm that grows clusters from dense regions: a cluster is a maximal set of density-connected points, and points in sparse regions are noise.

Key points.

It has two parameters: $Eps$, the neighbourhood radius, and $MinPts$, the minimum points within $Eps$ for a point to be dense.
A core point has at least $MinPts$ points in its $Eps$-neighbourhood, a border point lies in a core point's neighbourhood but is not core itself, and every other point is noise.
A cluster is grown by taking a core point and adding all points density-reachable from it.
It finds arbitrary-shaped clusters, detects noise and needs no $k$, but it struggles with varying densities; time is $O(n\log n)$ with a spatial index.

CURE algorithms

Definition. CURE (Clustering Using REpresentatives) is a hierarchical algorithm for large databases that represents each cluster by several well-scattered points shrunk towards the centre.

Key points.

It draws a random sample, partitions it, and clusters each partition to save time and memory.
Each cluster keeps $c$ well-scattered representative points, which are moved towards the centroid by a shrinking factor $\alpha$.
The two clusters with the closest representatives are merged repeatedly, so non-spherical shapes are found and outliers are damped by the shrinking.
Remaining points are labelled by the nearest representative.

Association rules: Apriori and FP-growth

Definition. <mark>An association rule $A\Rightarrow B$ says that transactions containing itemset $A$ tend to contain itemset $B$; it is strong when it meets minimum support and minimum confidence.</mark>

Formula. $$support(A\Rightarrow B)=\frac{\text{transactions with }A\cup B}{\text{total transactions}},\quad confidence=\frac{support(A\cup B)}{support(A)},\quad lift=\frac{confidence}{support(B)}$$

Key points.

Apriori uses the property that every subset of a frequent itemset must be frequent, so a candidate with an infrequent subset is pruned without counting.
It works level-wise: find frequent 1-itemsets $L_1$, join $L_{k-1}$ with itself to form candidates $C_k$, prune, scan the database to count, and repeat until no candidates remain.
Apriori makes the most cost when the data is dense with long frequent patterns, or when the support threshold is low: if there are 100 frequent items, it generates $\binom{100}{2}=4950$ candidate pairs and about $2^{100}$ subsets overall.
In such a dataset almost every candidate turns out frequent, so the subset check prunes nothing while still costing time, and each level needs a full database scan, so the check only adds cost; an example is a database where every transaction holds the same 30 items, giving $2^{30}-1$ frequent itemsets.
A large rule set is filtered first by minimum support and confidence, since these remove rare and unreliable rules.
Confidence can mislead, so lift is used: lift above 1 means positive correlation, 1 means independence and below 1 negative correlation; rules with lift near 1 are dropped.
Further pruning uses constraints and templates (only rules with chosen items or forms), interestingness measures and removal of redundant rules.
Mining only closed itemsets (no superset with equal support) or maximal itemsets (no frequent superset) shrinks the output greatly without losing the frequent-pattern information.

Answer frame. For the Apriori-cost question: open with the Apriori principle and pruning; give the dense long-pattern example with numbers; then explain candidate overhead and repeated scans; close that FP-growth avoids this. For the useful-rules question: open with the problem of rule explosion; then develop points 5-8 in order; close that the user keeps a small set of strong, interesting rules.

Pitfall: Do not say Apriori always reduces cost; it does so only when many candidates are pruned.

Asked: [7 marks] (May 2024) Describe example of data set for which Apriori check would actually increase the cost. Asked: [7 marks] (Jun 2025) For a transactional database, we can get a large number of association rules. How can we get useful association rules from such a large set?

FP-growth algorithms

Definition. <mark>FP-growth mines frequent itemsets without candidate generation by compressing the database into a Frequent Pattern tree (FP-tree) and recursively mining conditional trees.</mark>

Steps.

Step 1: Scan the database and find the support of each item; drop items below minimum support.
Step 2: Sort the frequent items of each transaction in descending support order.
Step 3: Insert each sorted transaction into the FP-tree, sharing common prefixes and increasing counts.
Step 4: For each item, from the least frequent, collect its conditional pattern base (prefix paths).
Step 5: Build its conditional FP-tree and generate the frequent patterns by joining with the item.

Example. Nine transactions, minimum support count 2: T1 {I1,I2,I5}; T2 {I2,I4}; T3 {I2,I3}; T4 {I1,I2,I4}; T5 {I1,I3}; T6 {I2,I3}; T7 {I1,I3}; T8 {I1,I2,I3,I5}; T9 {I1,I2,I3}. Counts: I2=7, I1=6, I3=6, I4=2, I5=2, so the order is I2, I1, I3, I4, I5.

Item	Conditional pattern base	Conditional FP-tree	Frequent patterns
I5	{I2,I1:1}, {I2,I1,I3:1}	I2:2, I1:2	{I2,I5:2}, {I1,I5:2}, {I2,I1,I5:2}
I4	{I2,I1:1}, {I2:1}	I2:2	{I2,I4:2}
I3	{I2,I1:2}, {I2:2}, {I1:2}	I2:4, I1:2 and I1:2	{I2,I3:4}, {I1,I3:4}, {I2,I1,I3:2}
I1	{I2:4}	I2:4	{I2,I1:4}

Answer frame. Open with the definition of frequent pattern mining and the FP-tree; write the five steps; draw the FP-tree from the sorted transactions with a header table; show the table above; close that FP-growth needs two scans and no candidates, so it beats Apriori on dense data.

Asked: [7 marks] (May 2023) Illustrate FP-growth algorithm with a suitable example.

Last-minute revision

Hierarchical clustering: agglomerative (bottom-up) or divisive (top-down), shown as a dendrogram.
Hierarchical issues: $O(n^2)$ scalability, linkage choice, irreversible merges, termination criterion.
K-means minimises squared error $E=\sum\sum\lVert x-m_i\rVert^2$ and needs $k$.
BIRCH uses $CF=(N,LS,SS)$ in a height-balanced CF-tree with $B$ and $T$; one scan, four phases.
DBSCAN has $Eps$ and $MinPts$; core, border and noise points.
CURE uses $c$ scattered representatives shrunk by factor $\alpha$, with sampling.
Support = $P(A\cup B)$; confidence = $support(A\cup B)/support(A)$; lift = confidence/$support(B)$.
Apriori property: every subset of a frequent itemset is frequent.
Apriori costs most on dense data with long patterns and low support.
Useful rules come from support, confidence, lift, constraints, closed and maximal itemsets.
FP-growth: two scans, FP-tree, conditional pattern base, no candidates.

Memory hooks

BIRCH: "N, LS, SS" - Number, Linear Sum, Squared Sum.
DBSCAN: core is crowded, border is at the edge, noise is alone.
CURE: scatter, then shrink.
Apriori is level by level with candidates; FP-growth is a tree with no candidates.
Lift above 1 lifts the rule; equal to 1 means nothing.

Coverage checklist

Hierarchical algorithms: May 2023 key issues in hierarchical clustering.
Partitional algorithms: no past question.
Clustering large databases – BIRCH, DBSCAN, CURE algorithms: Jun 2025 BIRCH.
DBSCAN: no past question.
CURE algorithms: no past question.
Association rules: Parallel and distributed algorithms such as Apriori and FP growth algorithms: May 2024 Apriori cost, Jun 2025 useful rules.
FP growth algorithms: May 2023 FP-growth illustration.

Account

Data Mining and Warehousing (AD-603 (A)) - Unit 5 Short Notes

How unit 5 is examined

Hierarchical algorithms

Partitional algorithms

Clustering large databases: BIRCH, DBSCAN, CURE

DBSCAN

CURE algorithms

Association rules: Apriori and FP-growth

FP-growth algorithms

Last-minute revision

Memory hooks

Coverage checklist