Gyanrush
Start freeOpen Gyanrush
Start freeOpen Gyanrush
  1. LPU MCA Semester 1
  2. CAB107
  3. Unit 5

CAB107 · Unit 5: Artificial intelligence techniques

K-Means, hierarchical clustering, DBSCAN and PCA

10 practice questions · in the ETE syllabus

Practise this topicPractise this topic

Key points

  • K-Means needs K and finds compact clusters
  • DBSCAN finds arbitrary shapes and marks noise
  • Core, border and noise points depend on eps and minPts
  • PCA keeps maximum variance and needs scaled features

Clustering groups unlabelled points by similarity. K-Means needs the number of clusters K in advance; it assigns each point to the nearest centroid and recomputes centroids until they stabilise, tending to give compact, roughly spherical clusters. Hierarchical clustering builds a tree (dendrogram) of merges, and cutting it at a height gives the clusters.

DBSCAN groups points by density using eps (neighbourhood radius) and minPts. A core point has at least minPts points within eps, counting itself; a border point is within eps of a core point but is not core; the rest are noise. It finds clusters of arbitrary shape and needs no preset cluster count.

Worked example: points 1, 2, 3, 10 with eps = 1.5 and minPts = 3. Only point 2 has three points within 1.5, so it is the single core point; points 1 and 3 are border points and 10 is noise.

PCA (principal component analysis) reduces the number of dimensions while keeping as much variance as possible, by projecting onto orthogonal directions of maximum variance. It is unsupervised.

from sklearn.decomposition import PCA
Z = PCA(n_components=2).fit_transform(X_scaled)

K-Means and PCA depend on distances or variance, so features with large ranges would dominate unless scaled.

Exam trap: the K in K-Means is the number of clusters; the k in k-NN is the number of neighbours.

Try two questions

Question 1 · Tier 2, Understand

What advantage does DBSCAN have over K-Means?

  1. It gives exactly K compact spherical clusters, where K is chosen beforehand by the analyst
  2. It needs class labels for every point so that it can learn the shape of each cluster in advance
  3. It finds clusters of arbitrary shape and marks sparse points as noise, without a preset cluster count
  4. It cannot be applied to two-dimensional data, because it needs at least three dimensions to measure density
Show the answer

C. DBSCAN groups dense regions using eps and minPts.

Why not A: That describes K-Means.

Why not B: DBSCAN is unsupervised.

Why not D: It works on two-dimensional data and higher.

Question 2 · Tier 3, Apply

One-dimensional points 1, 2, 3, 10, 11, 12 are clustered with K-Means using initial centroids 1 and 10. What are the centroids after one full iteration?

  1. 2 and 11
  2. 1 and 10
  3. 6 and 6
  4. 3 and 12
Show the answer

A. Points 1, 2, 3 join the first centroid and 10, 11, 12 the second; the means are 2 and 11.

Why not B: These are the starting centroids, which update after assignment.

Why not C: 6 is the mean of all points and would arise with one cluster.

Why not D: These are the largest members of each group, not their means.