How unit 3 is examined
This unit covers the paradigms of pattern recognition and machine learning, how patterns and classes are represented, and clustering (criterion functions, K-means, hierarchical clustering, validation); K-means, paradigms, hierarchical clustering and validation carry the marks.
Different Paradigms of Pattern Recognition
<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>Pattern classification is the task of assigning an input pattern, described by its feature vector, to one of a set of predefined classes.</mark> A paradigm is a basic approach, with its own way of representing patterns and deciding the class.
Key points.
- Statistical (decision-theoretic) paradigm represents a pattern as a feature vector and classifies it by probability or distance, for example Bayes classifier, k-NN and SVM; it suits face and character recognition.
- Syntactic (structural) paradigm represents a pattern as primitives combined by grammar rules, and classifies by parsing; it suits ECG waveforms, fingerprints and Chinese characters.
- Neural paradigm uses networks of weighted units trained on examples, so the decision function is learned; it suits speech and image recognition.
- Template matching compares the input with a stored prototype using a similarity or distance measure such as correlation; it is simple but sensitive to noise, rotation and scale.
- Machine-learning paradigms: supervised learning uses labelled data and covers classification (discrete label, e.g. spam or not spam) and regression (continuous output, e.g. house price).
- Unsupervised learning uses unlabelled data to find structure, for example clustering with K-means and dimensionality reduction with PCA.
- Reinforcement learning has an agent learn by trial and reward in an environment, for example game playing and robot control.
- Example classifiers: decision tree, naive Bayes, k-NN, SVM, logistic regression, neural network.
| Paradigm | Pattern is | Decision by |
|---|---|---|
| Statistical | feature vector | probability / distance |
| Syntactic | primitives + grammar | parsing |
| Neural | input to network | learned weights |
| Template | stored prototype | similarity |
Answer frame. Open with the definition of pattern classification; then develop points 1-4 (the four paradigms) and 5-7 (learning paradigms) with one application each; add the table; close with the classifier examples of point 8.
Asked: [7 marks] (Jun 2020, Nov 2023) What is pattern classification? What are major paradigms of machine learning? State and explain the different paradigms of pattern recognition.
Representations of Patterns and Classes
<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. A pattern is represented by a $d$-dimensional feature vector $\mathbf{x}=(x_1,\dots,x_d)^T$, and a class is represented by a prototype or model summarising its patterns.
Key points.
- Patterns can be represented as feature vectors, strings, trees or graphs, depending on whether the paradigm is statistical or syntactic.
- A class can be represented by its centroid $\mathbf{m}=\frac{1}{n}\sum_i \mathbf{x}_i$, by a few chosen prototypes, or by a probability density.
- Good features are discriminative: patterns of one class lie close together and different classes lie apart.
Unsupervised Learning & Clustering: Criterion functions for 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">Not asked since 2022</span>
Definition. Clustering groups unlabelled patterns so that members of a cluster are similar and clusters differ; a criterion function is the numeric measure that scores how good a partition is.
Key points.
- The most common criterion is the sum of squared errors $J=\sum_{j=1}^{k}\sum_{\mathbf{x}\in C_j}\lVert \mathbf{x}-\mathbf{m}_j\rVert^2$, which is to be minimised.
- Small $J$ means compact clusters, but $J$ always falls as $k$ grows, so $k$ must be fixed or chosen separately.
- Other criteria are the scatter matrices (within-class $S_W$ and between-class $S_B$), where a good partition has small $S_W$ and large $S_B$.
Clustering Techniques: Iterative square-error partitional clustering - K means
<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>K-means is an unsupervised, iterative partitional algorithm that divides $n$ unlabelled patterns into $k$ clusters by repeatedly assigning each pattern to the nearest centroid and recomputing the centroids until they stop changing.</mark> Unsupervised learning finds groups in data that has no class labels.
Techniques. Clustering techniques are partitional (K-means), hierarchical (agglomerative, divisive), density based (DBSCAN) and model based (Gaussian mixtures).
Steps.
Step 1: Choose k and pick k initial centroids.
Step 2: Assign every pattern to its nearest centroid (Euclidean distance).
Step 3: Recompute each centroid as the mean of its cluster.
Step 4: Repeat Steps 2-3 until the assignments (centroids) stop changing.
Key points.
- It minimises the squared-error criterion $J=\sum_j\sum_{\mathbf{x}\in C_j}\lVert \mathbf{x}-\mathbf{m}_j\rVert^2$, so clusters come out compact and roughly spherical.
- Convergence is guaranteed because each step never increases $J$ and the number of partitions is finite, but only to a local minimum.
- Result depends on the initial centroids, so run it several times with different starts and keep the lowest $J$.
- Limitations: $k$ must be known in advance, it is sensitive to outliers and noise, it fails for non-spherical clusters, and it works only where a mean exists (numeric data).
- Advantages: it is simple, fast (about $O(nkt)$ for $t$ iterations) and scales to large data.
Example. Data 2, 4, 10, 12, 3, 20, 30, 11, 25 with $k=2$ and initial centroids 2 and 4.
| Iteration | Cluster 1 | Cluster 2 | New means |
|---|---|---|---|
| 1 | 2, 3 | 4, 10, 12, 20, 30, 11, 25 | 2.5, 16 |
| 2 | 2, 4, 3 | 10, 12, 20, 30, 11, 25 | 3, 18 |
| 3 | 2, 4, 10, 3 | 12, 20, 30, 11, 25 | 4.75, 19.6 |
| 4 | 2, 3, 4, 10, 11, 12 | 20, 25, 30 | 7, 25 |
| 5 | same | same | 7, 25 (stop) |
Final clusters: {2, 3, 4, 10, 11, 12} with mean 7 and {20, 25, 30} with mean 25; $J=150$.
Answer frame. Open with the definition of unsupervised learning (no labels) and name K-means; give the steps; work the numerical table; close with convergence and limitations. For "enlist the techniques", list the four families first and then explain K-means.
Pitfall: Stopping after one pass; K-means stops only when the centroids stop moving.
Asked: [7 marks] (Jun 2020, Nov 2023) Discuss any unsupervised learning algorithm with an example. Enlist the clustering techniques. Explain any one technique. Asked: [14 marks] (Dec 2020) Write short note on any three: i) Clustering ii) Chi-square test iii) Forward algorithm iv) Backward algorithm v) Maximum likelihood estimation (clustering is answered by this unit; the others are in the last-minute revision below).
Hierarchical 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>Hierarchical clustering builds a nested sequence of clusters, shown as a tree called a dendrogram, without needing $k$ in advance.</mark>
Key points.
- Agglomerative (bottom-up) starts with each pattern as its own cluster and merges the two closest clusters at each step until one remains; divisive (top-down) starts with one cluster and splits it repeatedly.
- The closeness of clusters is set by the linkage: single (minimum distance between members), complete (maximum distance) and average (mean distance).
- Cutting the dendrogram at a chosen height gives the required number of clusters.
- Advantages: no need to fix $k$, and the dendrogram shows the structure; limitations: merges cannot be undone and cost is at least $O(n^2)$, so it is slow on big data.
Asked: [7 marks] (Jun 2020) What do you mean by hierarchical clustering explain?
Cluster Validation
<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>Cluster validation is the evaluation of how good and meaningful the clusters produced by an algorithm are.</mark> It is needed because every algorithm returns clusters even for random data.
Key points.
- External criteria compare the clusters with known class labels, using indices such as purity, Rand index and F-measure.
- Internal criteria use only the data, judging compactness and separation, using the silhouette coefficient, Dunn index and Davies-Bouldin index.
- Relative criteria compare results of the same algorithm under different parameters, for example different $k$, and pick the best by an index.
- Procedure: cluster for $k=2,3,\dots$, compute the index (e.g. silhouette $s=\frac{b-a}{\max(a,b)}$, where $a$ is mean distance within the cluster and $b$ to the nearest other cluster), and choose the $k$ with the best value.
Asked: [7 marks] (Nov 2023) Describe about cluster validation.
Last-minute revision
- Pattern classification assigns a pattern to one of the predefined classes.
- Paradigms: statistical, syntactic, neural, template matching.
- Learning paradigms: supervised (classification, regression), unsupervised, reinforcement.
- Criterion function: $J=\sum_j\sum_{x\in C_j}\lVert x-m_j\rVert^2$, minimised by K-means.
- K-means steps: choose k centroids, assign, recompute means, repeat till stable.
- K-means example {2,3,4,10,11,12} and {20,25,30}, means 7 and 25, $J=150$.
- Hierarchical: agglomerative bottom-up, divisive top-down, shown by a dendrogram.
- Linkage: single = min, complete = max, average = mean distance.
- Validation: external (labels), internal (compactness, separation), relative (compare parameters).
- Silhouette $s=(b-a)/\max(a,b)$, ranges from -1 to 1.
- Short-note extras: maximum likelihood estimation picks $\hat\theta$ maximising $L(\theta)=\prod_i p(x_i\mid\theta)$; chi-square test $\chi^2=\sum (O-E)^2/E$; forward selection adds features one by one, backward selection removes them one by one.
Memory hooks
- Four paradigms: "Some Students Never Tire" (Statistical, Syntactic, Neural, Template).
- K-means loop: "Assign, Average, Again".
- Linkage: single = closest friend, complete = farthest enemy.
- Validation: External = answer key, Internal = looks only, Relative = compare k.
Coverage checklist
- Different Paradigms of Pattern Recognition: pattern classification, learning paradigms, four paradigms (Q4).
- Representations of Patterns and Classes: feature vector, class prototype (no past question).
- Unsupervised Learning & Clustering: Criterion functions for clustering: squared-error criterion (no past question).
- Clustering Techniques: Iterative square -error partitional clustering – K means: unsupervised algorithm, techniques, K-means example, short note on clustering (Q1, Q3).
- hierarchical clustering: Q5.
- Cluster validation: Q2.