PCA, Discriminant, Cluster and Canonical Correlation Analysis
CSIR NET statistics: principal components, Fisher's linear discriminant, hierarchical and k-means clustering, and canonical correlations, with worked numbers.
- 18 min
On this page · 13 sections
Prerequisites
- Eigenvalues and the Cayley–Hamilton Theorem: eigenvalues of \( aI + bJ \) and of \( 2 \times 2 \) matrices, used in almost every PCA question.
- Quadratic Forms: Rayleigh quotient bounds, \( \max_{\lVert a \rVert = 1} a^TAa = \lambda_{\max} \).
- Multivariate Normal, Wishart and Quadratic Forms: Mahalanobis distance and the normal density.
- Partial and Multiple Correlation: canonical correlation generalises the multiple correlation.
The Hook: One Eigenvalue Problem, Four Questions
Principal Component Analysis
Let \( X \) be a random \( p \)-vector with covariance \( \Sigma \) and eigen-decomposition \( \Sigma = \sum_{j=1}^p \lambda_je_je_j^T \), \( \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_p \ge 0 \), orthonormal \( e_j \).
The \( j \)-th principal component is \( Y_j = e_j^T(X - \mu) \). The first maximises \( \operatorname{Var}(a^TX) \) over unit vectors \( a \); each later one maximises it over unit vectors orthogonal to the earlier \( e_i \). Then
$$\operatorname{Var}(Y_j) = \lambda_j, \qquad \operatorname{Cov}(Y_i, Y_j) = 0 \;(i \ne j).$$The first statement is the Rayleigh quotient: \( \max_{\lVert a \rVert = 1} a^T\Sigma a = \lambda_1 \).
| Fact | Formula |
|---|---|
| total variance is preserved | \( \sum_j\operatorname{Var}(Y_j) = \sum\lambda_j = \operatorname{tr}\Sigma = \sum\sigma_{ii} \) |
| generalised variance is preserved | \( \prod\lambda_j = \lvert\Sigma\rvert \) |
| proportion explained by first \( k \) | \( \frac{\lambda_1 + \dots + \lambda_k}{\lambda_1 + \dots + \lambda_p} \) |
| loading-to-correlation | \( \operatorname{corr}(Y_j, X_k) = \frac{e_{jk}\sqrt{\lambda_j}}{\sqrt{\sigma_{kk}}} \) |
| zero eigenvalue | \( \lambda_p = 0 \) means an exact linear relation \( e_p^T(X - \mu) = 0 \) |
Covariance or correlation matrix?
PCA is not scale invariant. Measure one variable in millimetres instead of metres and it dominates the first component. When variables are in different units, standardise first: PCA on the correlation matrix \( R \), whose total variance is \( p \).
| Correlation structure | Eigenvalues | First component |
|---|---|---|
| two variables, correlation \( \rho > 0 \) | \( 1 + \rho \), \( 1 - \rho \) | \( \frac{Z_1 + Z_2}{\sqrt{2}} \), whatever the value of \( \rho \) |
| \( p \) variables, all correlations \( \rho > 0 \) | \( 1 + (p - 1)\rho \) once, \( 1 - \rho \) (\( p - 1 \) times) | \( \frac{1}{\sqrt{p}}\sum Z_i \), explaining \( \frac{1 + (p - 1)\rho}{p} \) |
| uncorrelated | all equal to 1 | not unique (every direction) |
How many components? Common rules: keep enough for a target share of variance (say 80 to 90 per cent); look for the elbow in a scree plot of \( \lambda_j \) against \( j \); for a correlation matrix, keep components with \( \lambda_j > 1 \) (above-average variance). These are rules of thumb, not theorems.
Discriminant Analysis
Two populations \( \pi_1, \pi_2 \); classify a new \( x \) into one of them.
Fisher’s linear discriminant
Fisher sought the direction \( a \) that best separates the projected means relative to the projected spread, for a common covariance \( \Sigma \):
$$\max_a \frac{\left(a^T(\mu_1 - \mu_2)\right)^2}{a^T\Sigma a} \quad\Longrightarrow\quad \boxed{a \propto \Sigma^{-1}(\mu_1 - \mu_2)}.$$The maximum value is the squared Mahalanobis distance between the populations,
$$\Delta^2 = (\mu_1 - \mu_2)^T\Sigma^{-1}(\mu_1 - \mu_2).$$Rule (equal priors, equal costs): allocate \( x \) to \( \pi_1 \) if
$$a^Tx \ge \tfrac{1}{2}a^T(\mu_1 + \mu_2), \qquad a = \Sigma^{-1}(\mu_1 - \mu_2),$$that is, if \( x \) is closer to \( \mu_1 \) than to \( \mu_2 \) in Mahalanobis distance.
With normal populations \( N_p(\mu_i, \Sigma) \), this is the Bayes rule, and each misclassification probability is \( \Phi\left(-\frac{\Delta}{2}\right) \). With prior probabilities \( p_1, p_2 \) and misclassification costs \( c(1 \mid 2) \), \( c(2 \mid 1) \), the minimum expected cost rule allocates to \( \pi_1 \) when
$$a^Tx - \tfrac{1}{2}a^T(\mu_1 + \mu_2) \ge \ln\frac{c(1 \mid 2)\,p_2}{c(2 \mid 1)\,p_1}.$$If the covariances differ, the optimal normal rule is quadratic in \( x \) (QDA). In practice \( \mu_i \) and \( \Sigma \) are replaced by sample means and the pooled covariance \( S_{\text{pooled}} \).
Several groups. With \( g \) groups, between-group matrix \( B \) and within-group matrix \( W \), the discriminant directions are eigenvectors of \( W^{-1}B \), and there are at most \( \min(g - 1, p) \) of them with non-zero eigenvalues.
Cluster Analysis
Clustering finds groups when no labels are given (unsupervised), unlike discriminant analysis, which learns a rule from labelled data (supervised).
Distances. Euclidean \( \sqrt{\sum(x_i - y_i)^2} \); city-block \( \sum\lvert x_i - y_i \rvert \); Mahalanobis \( \sqrt{(x - y)^TS^{-1}(x - y)} \), which accounts for scale and correlation. Variables in different units should usually be standardised first.
Hierarchical (agglomerative) clustering
Start with every point as its own cluster; repeatedly merge the two closest clusters; record the merge heights in a dendrogram. Cutting the dendrogram at a height gives a partition. The linkage defines the distance between clusters \( A \) and \( B \):
| Linkage | Distance between clusters | Tendency |
|---|---|---|
| single (nearest neighbour) | \( \min d(a, b) \) | long straggly “chained” clusters |
| complete (furthest neighbour) | \( \max d(a, b) \) | compact clusters of similar diameter |
| average | mean of all \( d(a, b) \) | between the two |
| centroid | distance between cluster means | merge heights can decrease (inversions) |
| Ward | increase in total within-cluster sum of squares | compact, similar-sized clusters |
k-means
Choose \( k \). Assign each point to the nearest centre, recompute each centre as the mean of its points, and repeat until nothing changes. Each step decreases the within-cluster sum of squares
$$\text{WSS} = \sum_{c=1}^k\sum_{x \in C_c}\lVert x - \bar x_c \rVert^2,$$so the algorithm converges, but only to a local minimum that depends on the starting centres. It needs \( k \) in advance and favours roughly spherical clusters of similar size.
For 1, 2, 4, 8 with \( k = 2 \): \( \{1, 2, 4\}, \{8\} \) has \( \text{WSS} = \frac{14}{3} \approx 4.67 \); \( \{1, 2\}, \{4, 8\} \) has \( 0.5 + 8 = 8.5 \). The first is the global optimum.
Canonical Correlation Analysis
Two sets of variables, \( X \) (\( p \) of them) and \( Y \) (\( q \) of them), with
$$\operatorname{Cov}\begin{pmatrix} X \\ Y \end{pmatrix} = \begin{pmatrix} \Sigma_{11} & \Sigma_{12} \\ \Sigma_{21} & \Sigma_{22} \end{pmatrix}.$$The first pair of canonical variates \( (U_1, V_1) = (a_1^TX, b_1^TY) \) maximises \( \operatorname{corr}(a^TX, b^TY) \); the maximum \( \rho_1 \) is the first canonical correlation. The \( k \)-th pair maximises the correlation among pairs uncorrelated with all earlier \( U_i \) and \( V_i \). The squared canonical correlations \( \rho_1^2 \ge \rho_2^2 \ge \dots \) are the eigenvalues of
$$\Sigma_{11}^{-1}\Sigma_{12}\Sigma_{22}^{-1}\Sigma_{21} \quad \left(\text{equivalently, the } \rho_k \text{ are the singular values of } \Sigma_{11}^{-1/2}\Sigma_{12}\Sigma_{22}^{-1/2}\right).$$| Property | Statement |
|---|---|
| number of pairs | \( \min(p, q) \) |
| range | \( 0 \le \rho_k \le 1 \) |
| uncorrelatedness | \( \operatorname{corr}(U_i, U_j) = \operatorname{corr}(V_i, V_j) = \operatorname{corr}(U_i, V_j) = 0 \) for \( i \ne j \) |
| one variable in a set | if \( q = 1 \), \( \rho_1 \) is the multiple correlation of \( Y \) on \( X \) |
| invariance | unchanged by non-singular linear transformations of \( X \) and of \( Y \) separately (so by changes of scale) |
| dominates simple correlations | \( \rho_1 \ge \lvert\operatorname{corr}(X_i, Y_j)\rvert \) for every \( i, j \) |
| independence test | \( \Sigma_{12} = 0 \) iff all \( \rho_k = 0 \); Wilks’ \( \Lambda = \prod_k(1 - \hat\rho_k^2) \), with Bartlett’s approximation \( -\left(n - 1 - \frac{p + q + 1}{2}\right)\ln\Lambda \approx \chi^2_{pq} \) |
graph TD
A["Multivariate question"] --> B{"Labels known?"}
B -->|"no labels, reduce dimension"| C["PCA: eigenvectors of Sigma (or R)"]
B -->|"no labels, find groups"| D["Cluster analysis:
hierarchical or k-means"]
B -->|"labels known, classify"| E["Discriminant: a = Sigma^-1 (mu1 - mu2)"]
A --> F{"Two sets of variables?"}
F -->|"yes"| G["Canonical correlation:
eigenvalues of S11^-1 S12 S22^-1 S21"]Memory Tricks
- PCA: trace in, trace out. The components’ variances are the eigenvalues and add to \( \operatorname{tr}\Sigma \). Proportion \( = \frac{\lambda_1}{\operatorname{tr}\Sigma} \).
- Units matter for PCA, not for discriminant or canonical analysis. Fisher’s rule and canonical correlations are affine invariant; PCA on \( \Sigma \) is not.
- Fisher’s direction: “Sigma-inverse times the mean difference.” Then cut at the midpoint.
- Single chains, complete compacts. Single linkage uses the closest pair, complete the furthest.
- Canonical pairs: min of p and q. Discriminant functions: min of \( g - 1 \) and \( p \).
Don’t Confuse
| This | Is not this | The difference |
|---|---|---|
| PCA (unsupervised, variance) | discriminant analysis (supervised, separation) | the first component need not separate groups at all |
| discriminant analysis | cluster analysis | labels known versus labels to be found |
| PCA on \( \Sigma \) | PCA on \( R \) | different components unless all variances are equal |
| \( a \propto \mu_1 - \mu_2 \) | \( a \propto \Sigma^{-1}(\mu_1 - \mu_2) \) | the first only when \( \Sigma \propto I \) |
| canonical correlation \( \rho_1 \) | the largest simple correlation between the sets | \( \rho_1 \) is at least as large, often larger |
| k-means result | the global minimum of WSS | k-means guarantees only a local minimum |
| Euclidean distance | Mahalanobis distance | Mahalanobis rescales by \( S^{-1} \), removing units and correlation |
Common Mistakes
Practice
All questions below are original practice questions written for this page. They are not from any CSIR NET paper. In Level 3, as in Part C, one or more options may be correct.
Level 1: Foundation
- What is the variance of the \( j \)-th principal component?
- Write Fisher’s linear discriminant direction for two populations with common covariance \( \Sigma \).
- How many canonical correlations are there between a set of 4 and a set of 6 variables?
Answers
- \( \lambda_j \), the \( j \)-th largest eigenvalue of \( \Sigma \).
- \( a \propto \Sigma^{-1}(\mu_1 - \mu_2) \).
- \( \min(4, 6) = 4 \).
Level 2: Part B Style
Practice Q1. For \( \Sigma = \begin{pmatrix} 5 & 2 \\ 2 & 2 \end{pmatrix} \), the proportion of total variance explained by the first principal component is:
(a) \( \frac{5}{7} \) (b) \( \frac{6}{7} \) (c) \( \frac{5}{6} \) (d) \( \frac{1}{2} \)
Answer: (b)
Eigenvalues from trace 7 and determinant 6: 6 and 1. Proportion \( \frac{6}{7} \). Option (a) is the share of \( X_1 \)’s own variance.
Practice Q2. Four standardised variables have every pairwise correlation equal to 0.6. The largest eigenvalue of their correlation matrix is:
(a) 1.6 (b) 2.4 (c) 2.8 (d) 3.4
Answer: (c)
\( 1 + (p - 1)\rho = 1 + 3(0.6) = 2.8 \). The other three eigenvalues are \( 1 - 0.6 = 0.4 \); check: \( 2.8 + 3(0.4) = 4 = p \).
Practice Q3. Two normal populations have \( \mu_1 = (3, 1)^T \), \( \mu_2 = (1, 1)^T \) and common \( \Sigma = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix} \). The squared Mahalanobis distance between them is:
(a) 2 (b) \( \frac{4}{3} \) (c) \( \frac{8}{3} \) (d) 4
Answer: (c)
\( d = (2, 0)^T \), \( \Sigma^{-1}d = \frac{1}{3}(4, -2)^T \), \( \Delta^2 = d^T\Sigma^{-1}d = \frac{8}{3} \). Option (a) is \( \frac{\lVert d \rVert^2}{\sigma_{11}} \), which ignores the correlation; (d) is the Euclidean \( \lVert d \rVert^2 \).
Practice Q4. For the points 1, 2, 4, 8 on the real line, the height of the last merge in a complete-linkage dendrogram (Euclidean distance) is:
(a) 4 (b) 6 (c) 7 (d) 5.67
Answer: (c)
Merges: \( \{1, 2\} \) at 1; \( \{1, 2, 4\} \) at \( \max(3, 2) = 3 \) (less than \( d(4, 8) = 4 \)); then with 8 at \( \max(7, 6, 4) = 7 \). Option (a) is single linkage; (d) is average linkage.
Level 3: Part C Style
Practice Q5. Let \( X = (X_1, X_2, X_3)^T \) have the equicorrelation matrix with \( \rho = 0.5 \) as its covariance matrix (unit variances). Which statements are true about its principal components?
(a) The first principal component is \( \frac{X_1 + X_2 + X_3}{\sqrt{3}} \) (centred). (b) The first principal component explains \( \frac{2}{3} \) of the total variance. (c) The second and third principal components are uniquely determined up to sign. (d) The product of the three component variances is 0.5.
Answer: (a), (b) and (d)
The matrix is \( 0.5I + 0.5J \): eigenvalues \( 0.5 + 1.5 = 2 \) (eigenvector \( \mathbf{1} \)) and 0.5 twice.
- (a) True. The eigenvector for 2 is \( \frac{1}{\sqrt{3}}(1, 1, 1) \).
- (b) True. \( \frac{2}{3} \).
- (c) False. The eigenvalue 0.5 has a two-dimensional eigenspace (all vectors orthogonal to \( \mathbf{1} \)); any orthonormal basis of it works.
- (d) True. \( 2 \times 0.5 \times 0.5 = 0.5 = \lvert\Sigma\rvert = (1 - 0.5)^2(1 + 1) \).
Practice Q6. Two populations \( N_2(\mu_1, \Sigma) \) and \( N_2(\mu_2, \Sigma) \) have \( \mu_1 = (3, 1)^T \), \( \mu_2 = (1, 1)^T \), \( \Sigma = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix} \). Fisher’s rule with equal priors and costs is used. Which statements are true?
(a) The point \( (2, 0) \) is allocated to the first population. (b) The point \( (2, 2) \) is allocated to the first population. (c) Each misclassification probability is \( \Phi\left(-\frac{1}{2}\sqrt{8/3}\right) \approx 0.21 \). (d) If the prior probability of the first population falls to 0.2, the point \( (2, 0) \) is still allocated to it.
Answer: (a) and (c)
\( a = \left(\frac{4}{3}, -\frac{2}{3}\right) \), threshold 2.
- (a) True. \( a^Tx = \frac{8}{3} \ge 2 \).
- (b) False. \( a^Tx = \frac{8}{3} - \frac{4}{3} = \frac{4}{3} < 2 \).
- (c) True. \( \Delta^2 = \frac{8}{3} \), \( \Phi(-0.816) \approx 0.207 \).
- (d) False. The cut-off rises by \( \ln\frac{0.8}{0.2} = \ln 4 \approx 1.386 \), and \( \frac{8}{3} - 2 \approx 0.667 < 1.386 \).
Practice Q7. Let \( X = (X_1, X_2) \) and \( Y = (Y_1, Y_2) \) be standardised with \( \operatorname{Cov}(X) = \operatorname{Cov}(Y) = I \) and \( \operatorname{Cov}(X, Y) = \begin{pmatrix} 0.4 & 0.3 \\ 0.3 & 0.4 \end{pmatrix} \). Which statements are true?
(a) The first canonical correlation is 0.7. (b) The second canonical correlation is 0.3. (c) Multiplying \( X_1 \) by 100 changes the canonical correlations. (d) The first canonical correlation is at least as large as every \( \lvert\operatorname{corr}(X_i, Y_j)\rvert \).
Answer: (a) and (d)
- (a) True. Singular values of \( \Sigma_{12} \) (which is symmetric with eigenvalues \( 0.4 \pm 0.3 \)): 0.7 and 0.1.
- (b) False. It is 0.1. (0.3 is an entry of \( \Sigma_{12} \), not a canonical correlation.)
- (c) False. Canonical correlations are invariant under non-singular linear transformations within each set.
- (d) True. Taking \( a = e_i \), \( b = e_j \) is one admissible pair, so the maximum is at least \( \lvert\operatorname{corr}(X_i, Y_j)\rvert \).
Quick Revision Table
| Idea | Fact |
|---|---|
| PCs | \( Y_j = e_j^T(X - \mu) \), \( \operatorname{Var} = \lambda_j \), uncorrelated |
| Totals | \( \sum\lambda_j = \operatorname{tr}\Sigma \), \( \prod\lambda_j = \lvert\Sigma\rvert \) |
| Loading correlation | \( \operatorname{corr}(Y_j, X_k) = e_{jk}\sqrt{\lambda_j/\sigma_{kk}} \) |
| Equicorrelation | eigenvalues \( 1 + (p - 1)\rho \), \( 1 - \rho \) (\( p - 1 \) times) |
| Scale | PCA depends on units; use \( R \) for mixed units |
| Fisher LDF | \( a = \Sigma^{-1}(\mu_1 - \mu_2) \); cut at \( \frac{1}{2}a^T(\mu_1 + \mu_2) \) |
| Mahalanobis | \( \Delta^2 = (\mu_1 - \mu_2)^T\Sigma^{-1}(\mu_1 - \mu_2) \); error \( \Phi(-\Delta/2) \) |
| Priors and costs | shift the cut-off by \( \ln\frac{c(1 \mid 2)p_2}{c(2 \mid 1)p_1} \) |
| Several groups | eigenvectors of \( W^{-1}B \); at most \( \min(g - 1, p) \) |
| Linkages | single = min, complete = max, average = mean, Ward = WSS increase |
| k-means | minimises WSS; local optimum; needs \( k \) |
| Canonical | \( \rho_k^2 \) = eigenvalues of \( \Sigma_{11}^{-1}\Sigma_{12}\Sigma_{22}^{-1}\Sigma_{21} \); \( \min(p, q) \) pairs |
| \( q = 1 \) | canonical correlation = multiple correlation |
| Wilks | \( \Lambda = \prod(1 - \hat\rho_k^2) \) |
Key Takeaways
What’s Next
- Linear Models and Multivariate Analysis Quick Revision: every formula of this chapter on one page.
- Partial and Multiple Correlation: the \( q = 1 \) case of canonical correlation.
- Quadratic Forms: the Rayleigh quotient behind PCA and Fisher’s criterion.
- Back to the Linear Models and Multivariate Analysis chapter overview.