Synetic College Logo
Unit 4 of 4 · M.Sc IT Sem 4

Unit 4: Classification and clustering

Data Warehousing and Data Mining notes · PTU syllabus (PGCA1941)

3 min read10 topics10 exam questions
On this page
  1. Unit summary
  2. Bayesian classification
  3. Classification by back-propagation
  4. k-Nearest Neighbour
  5. Support Vector Machine
  6. Prediction: linear and multiple regression
  7. Types of data in clustering
  8. Partitioning methods: K-Means and K-Medoids
  9. Hierarchical agglomerative clustering
  10. Density-based clustering: DBSCAN
  11. Implementation with Weka or Python
  12. Key terms
  13. Quick revision
  14. Important questions

Unit summary

Classification and clustering are the workhorses of data mining. This unit covers Bayesian classification, back-propagation, k-nearest neighbour, support vector machines, linear and multiple regression, clustering data types, K-Means and K-Medoids, hierarchical agglomerative clustering, DBSCAN and implementation in Weka or Python.

After this unit you can

  • Apply Bayes theorem and Naive Bayes
  • Explain back-propagation, k-NN and SVM classifiers
  • Use linear and multiple regression for prediction
  • Apply K-Means, K-Medoids, hierarchical clustering and DBSCAN

PTU syllabus topics

  • Bayesian classification (Bayes theorem, Bayesian belief networks, Naive Bayes)
  • classification by back-propagation
  • k-Nearest Neighbour
  • Support Vector Machine
  • linear and multiple regression prediction
  • clustering data types
  • partitioning methods (K-Means, K-Medoids)
  • hierarchical agglomerative methods
  • DBSCAN
  • using Weka/Python for implementation
ComparisonClassification and clustering methods
Type
Key idea

Naive Bayes

Classification

Bayes' theorem with independent features

k-NN

Classification

Vote of the k nearest neighbours

SVM

Classification

Maximum-margin boundary

K-means

Clustering

Assign to nearest centroid, update

DBSCAN

Clustering

Dense regions; finds noise

1

Topic 1

Bayesian classification

Key formulasBayes theorem

  • P(C given X) = P(X given C) × P(C) / P(X)

    Posterior from likelihood and prior

  • Naive Bayes: P(X given C) = P(x1 given C) × P(x2 given C) × …

    Assumes attributes independent given the class

  • Laplace correction: add 1 to each count

    Avoids zero probabilities

Example

Training: 9 "buys = yes", 5 "no". For X = (age youth, income medium): P(youth given yes) = 2/9, P(medium given yes) = 4/9 → score yes = 9/14 × 2/9 × 4/9 = 0.063; P(youth given no) = 3/5, P(medium given no) = 2/5 → score no = 5/14 × 3/5 × 2/5 = 0.086 → predict "no".

  • Bayesian belief network: a directed acyclic graph of variables with conditional probability tables; it relaxes the independence assumption (e.g., Smoker → Lung cancer → X-ray result).
2

Topic 2

Classification by back-propagation

ProcessBack-propagation
  1. 1

    Initialise weights randomly

  2. 2

    Forward pass — compute outputs layer by layer with sigmoid

  3. 3

    Compute error at output (target − output)

  4. 4

    Propagate error backward to hidden layers

  5. 5

    Update weights: w = w + learning rate × error × input

  6. 6

    Repeat for epochs until error is small

  • Strengths: handles noisy and complex data. Weaknesses: long training, "black box".
3

Topic 3

k-Nearest Neighbour

Processk-NN
  1. 1Choose k (e.g., 3 or 5, odd for two classes)
  2. 2Compute distance to every training record — Euclidean √Σ(xi − yi)²
  3. 3Pick the k nearest
  4. 4Majority vote (classification) or average (prediction)
  • Lazy learner: no training; slow at prediction; normalise attributes first.
4

Topic 4

Support Vector Machine

  • Finds the maximum-margin hyperplane separating classes; the closest points are support vectors.
  • Kernel trick (polynomial, RBF) maps data to higher dimensions for non-linear boundaries; soft margin (C parameter) tolerates some errors.
5

Topic 5

Prediction: linear and multiple regression

Key formulasRegression

  • y = a + bx

    Simple linear regression

  • b = Σ(x − x̄)(y − ȳ) / Σ(x − x̄)²

    Slope by least squares

  • a = ȳ − b x̄

    Intercept

  • y = b0 + b1x1 + b2x2 + … + bnxn

    Multiple regression

Example

Years of experience x = 1, 3, 5; salary y (lakh) = 3, 5, 7: x̄ = 3, ȳ = 5, b = (4+0+4)/(4+0+4) = 1, a = 5 − 3 = 2 → y = 2 + x; for 6 years, predicted salary ₹8 lakh.

6

Topic 6

Types of data in clustering

Key termsData types and distances
Interval-scaled
Euclidean, Manhattan distance after standardising
Binary
Simple matching or Jaccard coefficient
Nominal
Proportion of mismatches
Ordinal
Convert ranks to 0–1 then treat as interval
Mixed types
Weighted combination
7

Topic 7

Partitioning methods: K-Means and K-Medoids

ProcessK-Means
  1. 1Choose k
  2. 2Pick k initial centroids
  3. 3Assign each point to the nearest centroid
  4. 4Recompute each centroid as the cluster mean
  5. 5Repeat until assignments stop changing

Example

Points 2, 4, 10, 12, 3, 20, 30, 11, 25 with k = 2, centroids 2 and 4: after iterations the clusters settle at {2, 3, 4, 10, 11, 12} (mean 7) and {20, 25, 30} (mean 25).

ComparisonK-Means vs K-Medoids
K-Means
K-Medoids (PAM)

Centre

Mean (may not be a real point)

Medoid — an actual data point

Outliers

Sensitive

Robust

Cost

Fast

Slower (swap-based)

8

Topic 8

Hierarchical agglomerative clustering

ProcessAgglomerative (bottom-up)
  1. 1Start with each point as its own cluster
  2. 2Merge the two closest clusters
  3. 3Update distances — single link (min), complete link (max), average link
  4. 4Repeat until one cluster remains
  5. 5Cut the dendrogram at the desired level
  • Divisive (top-down) is the reverse. A dendrogram shows the merge order.
9

Topic 9

Density-based clustering: DBSCAN

Key termsDBSCAN
Eps
Neighbourhood radius
MinPts
Minimum points to form a dense region
Core point
Has at least MinPts within Eps
Border point
Within Eps of a core point but not core itself
Noise
Neither core nor border
  • Advantages: finds arbitrary-shaped clusters, no need to fix k, marks outliers.
10

Topic 10

Implementation with Weka or Python

pythonfrom sklearn.cluster import KMeans, DBSCAN
from sklearn.naive_bayes import GaussianNB
from sklearn.datasets import load_iris
X, y = load_iris(return_X_y=True)
print(GaussianNB().fit(X, y).score(X, y))
print(KMeans(n_clusters=3, n_init=10).fit(X).labels_[:10])
print(DBSCAN(eps=0.5, min_samples=5).fit(X).labels_[:10])
  • Weka: Explorer → Preprocess (load ARFF or CSV) → Classify (NaiveBayes, IBk, SMO, J48) → Cluster (SimpleKMeans, DBSCAN) → Associate (Apriori).

Key terms

Naive Bayes
Classifier assuming attribute independence
Support vectors
Training points closest to the separating hyperplane
Medoid
Most centrally located actual point in a cluster
Dendrogram
Tree diagram of hierarchical clustering
Core point
DBSCAN point with at least MinPts neighbours within Eps

Quick revision

  • Bayes theorem, Naive Bayes, belief networks.
  • Back-propagation; k-NN; SVM with kernels.
  • Linear and multiple regression formulas.
  • Clustering data types; K-Means vs K-Medoids; agglomerative; DBSCAN; Weka and Python.

Important exam questions

Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).

Short-answer questions

  1. Q1.State Bayes theorem.
  2. Q2.What is a Bayesian belief network?
  3. Q3.Why is k-NN called a lazy learner?
  4. Q4.What is the kernel trick?
  5. Q5.Distinguish K-Means and K-Medoids.
  6. Q6.Define core, border and noise points in DBSCAN.

Long-answer questions

  1. Q1.Explain Naive Bayes classification with an example.
  2. Q2.Explain back-propagation, k-NN and SVM classifiers.
  3. Q3.Explain K-Means clustering with an example.
  4. Q4.Explain hierarchical and density-based clustering.

Stuck on this unit?

Message SBS on WhatsApp for help with Data Warehousing and Data Mining, or to ask about studying M.Sc IT at Synetic.

WhatsApp us