Data Mining and Warehousing (CS-703 (B)) Unit 4 Notes

How unit 4 is examined

Classification learns from labelled data to predict a class; the marks sit in k-NN (distance-based), decision trees and rule-based classifiers, with one probabilistic question.

Statistical-based 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">Not asked since 2022</span>

Definition. Statistical classifiers use probability and regression to assign a class; supervised learning means learning a mapping from labelled training tuples to a class label, then predicting unseen tuples.

Key points.

Bayesian classifiers such as Naive Bayes choose the class with the highest posterior probability $P(C|X)$.
Regression-based classifiers fit a function to the data; logistic regression gives $P(y=1)=\frac{1}{1+e^{-(w\cdot x+b)}}$ and thresholds it at 0.5.
The main supervised techniques are decision trees, Naive Bayes, k-NN, neural networks and SVM; each is trained on labelled data and tested on held-out data.
Applications include spam filtering, credit scoring and medical diagnosis.

Asked: [7 marks] (Dec 2024) Explain various learning techniques involved in supervised learning.

Distance-based algorithms

Definition. <mark>Distance-based algorithms classify a tuple by its similarity, measured as distance, to stored training tuples; k-NN assigns the majority class among the k nearest neighbours.</mark>

Key points.

k-NN is lazy and instance-based: it builds no model at training time and simply stores the tuples.
Distance metrics: Euclidean $d=\sqrt{\sum (x_i-y_i)^2}$, Manhattan $\sum |x_i-y_i|$ and Minkowski; attributes are normalised first so that no scale dominates.
A small k is noise-sensitive and a large k blurs class boundaries; an odd k avoids ties, and k is chosen by cross-validation.
Advantages: simple, no training cost, handles multi-class problems; limitations: slow prediction, needs high memory, suffers in high dimensions and with irrelevant attributes.
Related methods: k-means clusters by distance to centroids (unsupervised), and case-based reasoning retrieves the most similar stored case.

Steps.

Step 1: Choose k and a distance metric.
Step 2: Compute the distance from the query to every training tuple.
Step 3: Pick the k tuples with the smallest distances.
Step 4: Assign the majority class among them.

Example. Query $(4,4)$, k = 3. Training: (1,1) N, (2,3) N, (6,5) Y, (7,7) Y, (5,4) Y.

Tuple	Class	Distance
(5,4)	Y	1.00
(2,3)	N	2.24
(6,5)	Y	2.24
(1,1)	N	4.24
(7,7)	Y	4.24

Nearest 3 are Y, N, Y. Answer: class Y (2 votes to 1).

Answer frame. Open with the definition; write the four steps; show the small table above as the example; then advantages, limitations and choice of k; close with "k-NN is simple but costly at prediction time". For the short note, give two lines plus k-NN and k-means as examples.

Asked: [7 marks] (Dec 2024) Explain distance-based algorithms. Asked: [7 marks] (Dec 2025) Describe the k-Nearest Neighbors (k-NN) algorithm and its role in classification. Asked: [7 marks] (Dec 2020) Write short notes: (ii) Distance based algorithms.

Decision tree-based algorithms

Definition. <mark>A decision tree is a flowchart-like tree in which each internal node tests an attribute, each branch is an outcome and each leaf holds a class label.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-01" viewBox="0 0 616 258" width="616" height="258" role="img" aria-label="Decision tree for play tennis; internal nodes are attributes, leaves are classes"><style>#dsfig-u4-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-01 .t{fill:#16181D;font-weight:500}#dsfig-u4-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-01 .dot{fill:#16181D}#dsfig-u4-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-01 .ah{fill:#454C5A}#dsfig-u4-01 .ah.hi{fill:#2340B8}#dsfig-u4-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-01 .e{stroke:#B1B7C3}html.dark #dsfig-u4-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-01 .t{fill:#E6E8ED}html.dark #dsfig-u4-01 .t.inv{fill:#0F1115}html.dark #dsfig-u4-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-01 .dot{fill:#E6E8ED}html.dark #dsfig-u4-01 .ann{fill:#8FA3FF}html.dark #dsfig-u4-01 .lbl{fill:#858D9C}html.dark #dsfig-u4-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-01 .ah{fill:#B1B7C3}html.dark #dsfig-u4-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah9" 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="ahh9" 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="294" y1="37" x2="110.8" y2="101"/><line class="e" x1="294" y1="37" x2="296" y2="101"/><line class="e" x1="294" y1="37" x2="477.3" y2="101"/><line class="e" x1="110.8" y1="101" x2="110.8" y2="165"/><line class="e" x1="110.8" y1="165" x2="55.5" y2="229"/><line class="e" x1="110.8" y1="165" x2="166" y2="229"/><line class="e" x1="477.3" y1="101" x2="477.3" y2="165"/><line class="e" x1="477.3" y1="165" x2="422" y2="229"/><line class="e" x1="477.3" y1="165" x2="532.5" y2="229"/><rect class="n" x="256.5" y="22" width="75" height="30" rx="8"/><text class="t" x="294" y="37" dy=".35em" text-anchor="middle">Outlook</text><rect class="n" x="81.3" y="86" width="59" height="30" rx="8"/><text class="t" x="110.8" y="101" dy=".35em" text-anchor="middle">Sunny</text><rect class="n" x="69.3" y="150" width="83" height="30" rx="8"/><text class="t" x="110.8" y="165" dy=".35em" text-anchor="middle">Humidity</text><rect class="n" x="14" y="214" width="83" height="30" rx="8"/><text class="t" x="55.5" y="229" dy=".35em" text-anchor="middle">High: No</text><rect class="n" x="113" y="214" width="106" height="30" rx="8"/><text class="t" x="166" y="229" dy=".35em" text-anchor="middle">Normal: Yes</text><rect class="n" x="235" y="86" width="122" height="30" rx="8"/><text class="t" x="296" y="101" dy=".35em" text-anchor="middle">Overcast: Yes</text><rect class="n" x="451.3" y="86" width="52" height="30" rx="8"/><text class="t" x="477.3" y="101" dy=".35em" text-anchor="middle">Rain</text><rect class="n" x="451.3" y="150" width="52" height="30" rx="8"/><text class="t" x="477.3" y="165" dy=".35em" text-anchor="middle">Wind</text><rect class="n" x="373" y="214" width="98" height="30" rx="8"/><text class="t" x="422" y="229" dy=".35em" text-anchor="middle">Strong: No</text><rect class="n" x="487" y="214" width="91" height="30" rx="8"/><text class="t" x="532.5" y="229" dy=".35em" text-anchor="middle">Weak: Yes</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Decision tree for play tennis; internal nodes are attributes, leaves are classes</figcaption></figure>

Key points.

Induction is top-down and greedy (ID3, C4.5, CART): the best attribute is chosen at each node and the data is split recursively until nodes are pure.
Entropy measures impurity: $Entropy(S)=-\sum p_i\log_2 p_i$.
Information gain is $Gain(S,A)=Entropy(S)-\sum \frac{|S_v|}{|S|}Entropy(S_v)$; ID3 picks the highest gain, C4.5 uses gain ratio and CART uses Gini $=1-\sum p_i^2$.
Pruning (pre-pruning stops early, post-pruning cuts subtrees) removes branches that fit noise and so prevents overfitting.
Advantages: easy to interpret and convert to rules, handles categorical and numerical data, needs no domain knowledge, tolerates missing values, is fast and scalable, and suits exploratory discovery.
Limitation: it can overfit and is unstable to small data changes.

Example. Play tennis has 9 Yes and 5 No, so $Entropy=0.940$. Splitting on Outlook (Sunny 2Y/3N, Overcast 4Y/0N, Rain 3Y/2N) gives $Gain=0.940-0.693=0.247$, the largest, so Outlook is the root. Gini of the root is 0.459.

Answer frame. Open with the definition and components; draw the tree; develop induction, splitting criteria (entropy, gain, Gini), pruning, then the example; close with advantages. For the advantages question, define induction and go straight to point 5 in full.

Asked: [7 marks] (Dec 2020) What are the advantages of Decision tree induction? Asked: [7 marks] (Dec 2024) Explain Decision tree-based algorithms.

Neural network-based algorithms

Definition. A neural network is a set of connected neurons in layers that learns weights from labelled data to classify tuples.

Key points.

A multilayer perceptron has input, hidden and output layers; each neuron outputs $f(\sum w_ix_i+b)$ with an activation function $f$.
Backpropagation computes the output error and propagates it backwards, updating weights by $w\leftarrow w-\eta\,\partial E/\partial w$.
Training needs many passes and much data, and the model is a black box, but it handles noisy data and complex boundaries well.

Rule-based algorithms

Definition. <mark>A rule-based classifier classifies tuples using a set of IF-THEN rules of the form IF condition THEN class.</mark>

Key points.

A rule has an antecedent (the condition) and a consequent (the class), for example IF age = youth AND student = yes THEN buys = yes.
Coverage is the fraction of tuples the rule satisfies, $\frac{n_{covers}}{|D|}$, and accuracy is the fraction of those it classifies correctly, $\frac{n_{correct}}{n_{covers}}$.
Rules are derived indirectly by extracting one rule per root-to-leaf path of a decision tree, or directly from data by sequential covering.
Sequential covering (AQ, CN2, RIPPER) learns one rule, removes the tuples it covers and repeats for the class until no good rule remains.
Rule pruning drops conjuncts that do not improve accuracy on validation data; RIPPER prunes with a FOIL-gain-based measure.
If several rules fire, conflict resolution uses rule ordering or size; a default rule handles tuples that no rule covers.
Association rules are also IF-THEN rules but are found by mining, not by class-directed covering.

Answer frame. Open with the IF-THEN definition and one rule; give the two derivation routes, drawing the sequential covering loop as steps; then coverage, accuracy, pruning and conflict resolution; close with the fact that rules are easy to read.

Asked: [7 marks] (Dec 2020) Write short notes: (i) Rule based algorithms. Asked: [7 marks] (Dec 2025) What are rule-based classifiers? Explain how they derive classification rules from data.

Probabilistic Classifiers

Definition. ==A probabilistic classifier outputs the posterior probability $P(C_i|X)=\frac{P(X|C_i)P(C_i)}{P(X)}$ and predicts the class with the highest value; Naive Bayes is the standard example.==

Key points.

Naive Bayes assumes attributes are conditionally independent given the class, so $P(X|C)=\prod P(x_k|C)$.
Example: with $P(spam)=0.4$ and word likelihoods multiplying to give a higher score for spam than for non-spam, the mail is labelled spam.
They are useful in uncertain environments because they cope with noisy, incomplete and overlapping data and give a confidence value with each prediction.
A zero count is fixed with Laplace smoothing.

Basis	Probabilistic	Deterministic
Output	Class with probability	Class only
Uncertainty	Modelled explicitly	Ignored
Overlapping classes	Handled by posteriors	Hard boundary
Missing values	Attribute skipped	Often problematic
Example	Naive Bayes	Decision tree, rule set

Asked: [7 marks] (Dec 2025) Define probabilistic classifiers and explain how they differ; why are they useful in uncertain environments?

Last-minute revision

Classification is supervised: labelled training data builds a model, test data checks it.
k-NN is lazy; Euclidean distance is $\sqrt{\sum (x_i-y_i)^2}$; majority vote of k neighbours.
Entropy $=-\sum p_i\log_2 p_i$; play tennis root entropy is 0.940 and Outlook gain is 0.247.
Gini $=1-\sum p_i^2$; ID3 uses gain, C4.5 gain ratio, CART Gini.
Pruning (pre and post) fights overfitting.
Rule: IF condition THEN class; coverage and accuracy measure rule quality.
Sequential covering learns one rule, removes covered tuples, repeats; RIPPER is a well-known version.
Bayes: $P(C|X)=P(X|C)P(C)/P(X)$; Naive Bayes assumes independence.
Backpropagation updates weights from the output error.

Memory hooks

k-NN: "Ask the neighbours, majority wins".
ID3 gain, C4.5 ratio, CART Gini: "I See Gini" in order G-R-Gi.
Sequential covering: "Learn, Remove, Repeat".
Naive = independent attributes.

Coverage checklist

Statistical-based algorithms: Dec 2024 supervised learning techniques.
Distance-based algorithms: Dec 2024 distance-based; Dec 2025 k-NN; Dec 2020 short note (ii).
Decision tree-based algorithms: Dec 2020 advantages; Dec 2024 decision tree algorithms.
Neural network-based algorithms: no past questions.
Rule-based algorithms: Dec 2020 short note (i); Dec 2025 rule-based classifiers.
Probabilistic Classifiers: Dec 2025 probabilistic classifiers.

Account

Data Mining and Warehousing (CS-703 (B)) - Unit 4 Short Notes

How unit 4 is examined

Statistical-based algorithms

Distance-based algorithms

Decision tree-based algorithms

Neural network-based algorithms

Rule-based algorithms

Probabilistic Classifiers

Last-minute revision

Memory hooks

Coverage checklist