Linear Discriminant Analysis and Hierarchical Cluster Analysis

Linear Discriminant Analysis and Hierarchical Cluster Analysis

14.1 Principal Component Analysis Recap

14.1.1 The Core Idea

Principal component analysis (PCA) is a dimensionality reduction technique. Its main objective is to reduce a higher-dimensional space into a lower-dimensional space, and while doing the reduction you should not lose the maximum amount of information. The whole question reduces to one choice: find the direction onto which, if you project the data, you capture the maximum amount of information — the maximum variation.

Look at a scatter plot and think of the two candidate directions available in it. Along one direction the projected points spread out a lot; along the other direction they barely spread at all. The direction with the bigger spread is the one that carries the information, and that is the direction PCA picks. So the mental model is: PCA searches the space of all directions for the single line that preserves the most variation when the data is squashed onto it.

A simple way to picture the idea is a two-dimensional scatter plot with two arrows drawn through the cloud of points. Name the horizontal axis $x_1$ and the vertical axis $x_2$. Arrow 1 runs along the direction where the cloud is long and thin; arrow 2 runs across the direction where the cloud is narrow. Project each point onto arrow 1 by dropping a perpendicular from the point to the arrow: the projected positions are stretched out over a wide interval. Do the same onto arrow 2: the projected positions pile up in a narrow interval. The landmark of the picture is the difference in how far the two sets of projected marks reach. The takeaway: the direction whose projection shows the longer spread holds more variation, and that is the direction PCA keeps.

14.1.2 Eigenvalues and the Share of Variation

To identify which direction has the maximum variation and which has the minimum, you compute the covariance matrix of the data and solve the eigenvalue problem. The eigenvalue equation is written as the covariance matrix $\Sigma$ minus $\lambda$ times the identity matrix $I$, with its determinant set to zero:

$$|\Sigma -\lambda I|=0$$

The direction belonging to the highest eigenvalue captures the maximum variation. You can express how much each direction contributes as a percentage of the total variation:

$$\frac{{\lambda }_1}{{\lambda }_1+{\lambda }_2}\text{and}\frac{{\lambda }_2}{{\lambda }_1+{\lambda }_2}$$

The denominator sums all the eigenvalues, because the total variation of the data is the sum of the variances on the diagonal of $\Sigma$, and that sum equals ${\lambda }_1+{\lambda }_2$. Each share is so the fraction of the total variation carried by that direction, and the two shares always add to 1 (100 percent).

A visual reading of the share: draw a bar with the total variation 25, then split the bar into a block of height 21 and a block of height 4. The 21-block is more than five times as tall as the 4-block. That lopsided split is the picture to keep: when one eigenvalue dominates, a single projection direction preserves most of the information, and the reduced data is nearly lossless.

Beyond the exam, this is the practical reason PCA is used for compression and exploration while LDA-type methods are used when the downstream goal is classification. Compression with PCA means keeping only the top few principal directions: image compression stores the projections onto the few largest-eigenvalue directions instead of every pixel, face recognition systems build "eigenfaces" from the leading eigenvectors of a face-image covariance matrix, and the same eigenvalue logic returns later in discriminant analysis, where the ratio of between-group to within-group variation is summarized by an eigenvalue.

14.2 Linear Discriminant Analysis

14.2.1 Why PCA Falls Short for Classification

PCA has a blind spot: it is not useful for classification problems. If your main objective is to classify, PCA will not work for you — yes, it reduces the data from a higher dimension to a lower dimension, but at the end you have no clarity about how to separate the two classes. Project all the points of a two-class data set onto the max-variation line and you see both classes mixed along the same line, with no obvious way to tell them apart.

What you actually want for classification is the opposite emphasis: find the direction along which, if you project all the points, you can easily see the separability between the classes. Project onto that line, and a single cutoff value does the job — points above the cutoff are one class, points below are the other. That is exactly what linear discriminant analysis (LDA) is for: it focuses on finding the feature subspace that maximizes the separability between the classes.

So the target changes from "maximum variation" to "maximum separability". The professor's statement of the goal: you must manage two kinds of variation — the variation within each class and the variation between the classes — and build a mathematical expression that minimizes the within-class variation while maximizing the between-class separation. The line that satisfies both ends gives the best possible separation.

The one-line "when to pick which": use PCA when the goal is to summarize variation, and use LDA when the goal is to separate known classes — a single projected line with a cutoff does the classification job.

This is the practical reason PCA is used for compression and exploration while LDA-type methods are used when the downstream goal is classification. In credit scoring, a bank projects applicant features onto a discriminant direction to separate defaulters from payers; in medical diagnostics, the same idea separates sick from healthy patients on a single score. The textbook Research Methodology: Concepts and Cases runs its discriminant analysis chapter on exactly this kind of problem — predicting which restaurant a customer chooses between two rivals.

14.2.2 The Worked Data Set

To make the idea concrete, the lecture uses a small two-class data set. There are two classes, class 1 and class 2, with five data points each. Class 1 is the point set

$$(1,2),(3,5),(4,3),(5,6),(7,5)$$

The five points of class 2 were written on the board and read off from the scatter diagram, but the spoken list is too garbled to reconstruct; only its mean ${\mathbf{\mu }}_2=(10,3.2)$ survives intact. That loss does not cripple the analysis: the LDA recipe that follows uses the class means and the within-class scatter matrices, not the raw points, and both are available.

The class means are the working quantities:

14.2.3 PCA Applied to the Combined Data

Before building LDA, the lecture first shows why PCA fails on this exact data. Ignore the class labels for the moment — that is what PCA does, since it has no use for class information. Pool the whole data set (both classes together) into a single matrix, compute the covariance matrix, and solve the eigenvalue equation, exactly as in the previous session. For this problem the two eigenvalues come out as

$${\lambda }_1=26.28,{\lambda }_2=2.525$$

14.2.4 Within-Class Scatter: S1 and S2

To get a separating direction you must manage two kinds of variation: the variation within each class, and the variation between the classes. The mathematical target is to build an expression that minimizes the within-class variation and at the same time maximizes the separation between the classes. The line that satisfies both ends gives the best possible separation.

The within-class scatter matrix of class 1 measures its internal spread. The verbal description: a sum over the class-1 points of $(x_i-{\mu }_1)$ times $(x_i-{\mu }_1)$ transposed:

$$S_1=\sum _{i\in C_1}({\mathbf{x}}_i-{\mathbf{\mu }}_1)({\mathbf{x}}_i-{\mathbf{\mu }}_1{)}^{\top }$$

The class-2 scatter matrix $S_2$ is built the same way: take every point of class 2, subtract ${\mathbf{\mu }}_2=(10,3.2)$, form the outer products, and add them. Only the top-left entry is readable from the lecture — it comes out as 30. The remaining entries can be recovered consistently from the lecture's own final result (the discriminant direction $\mathbf{w}\approx (-0.221,0.24)$ computed in section 14.2.6), so that every stated number in this lecture is mutually consistent:

One thing worth noticing: in all of these matrices the (1,2) and (2,1) entries are the same. The scatter matrices are symmetric, exactly like the covariance matrix. Reading them the same way, the diagonal entries are variances and the off-diagonal entries measure the combined variation between the two variables (the entries can be labelled $s_{11},s_{12},s_{21},s_{22}$, where $s_{12}=s_{21}$). In the previous session the covariance matrix was simply given; here the approach of building the scatter matrices step by step was shown — but note there are many equivalent approaches to arrive at these values. In particular, the sample covariance matrix of a class is the scatter matrix divided by $n-1$: for class 1, $S_1/(5-1)=\left(\begin{array}{cc}5& 2.5\\ 2.5& 2.7\end{array}\right)$. The scatter matrix keeps the same information without the division, which is why it appears directly in the formulas.

14.2.5 Total Within-Class Scatter

The total within-class scatter combines both classes. The verbal description: $S_W$ is simply $S_1$ plus $S_2$:

$$S_W=S_1+S_2$$

For the top-left entry this is $20+30=50$. With the reconstructed $S_2$, the full sum is

$$S_W=\left(\begin{array}{cc}20& 10\\ 10& 10.8\end{array}\right)+\left(\begin{array}{cc}30& 11.04\\ 11.04& 12.74\end{array}\right)=\left(\begin{array}{cc}50& 21.04\\ 21.04& 23.54\end{array}\right)$$

The interpretation is a pooled version of the per-class reading: the diagonal holds the total within-class variance of each variable (50 for the $x$-coordinate, about 23.5 for the $y$-coordinate), and the off-diagonal holds the total combined variation. $S_W$ is the "how scattered are the points inside their own classes" budget of the whole problem, summed over both classes.

14.2.6 The Discriminant Direction and the Projection

Now the key formula: the vector $\mathbf{w}$ along which projecting the data gives the best possible separation is

$$\mathbf{w}=S_W^{-1}({\mathbf{\mu }}_1-{\mathbf{\mu }}_2)$$

The verbal description: the discriminant direction is the inverse of the total within-class scatter matrix times the difference of the class means. Every part earns its place: $S_W^{-1}$ shrinks directions in which the classes are internally spread out, and ${\mathbf{\mu }}_1-{\mathbf{\mu }}_2$ points from the center of class 2 toward the center of class 1.

Next, the difference of the means:

$${\mathbf{\mu }}_1-{\mathbf{\mu }}_2=(4-10,4.2-3.2)=(-6,1)$$

The intuition behind the formula: you are minimizing the within-class scatter and maximizing the separation between the classes — the farther apart the class means are, the easier the separation. If the two means coincided, the difference vector would be zero and no direction could separate the classes; if they are far apart, the difference vector points straight from one class center to the other.

Where does the formula come from? The lecture notes that the derivation uses calculus, Jacobians, and partial derivatives and does not show it. Here is the argument in full. The goal is a direction $\mathbf{w}$ such that the projected points are far apart between classes and tightly packed within classes. Projecting the data onto $\mathbf{w}$ sends each point $x_i$ to the scalar $z_i={\mathbf{w}}^{\top }{\mathbf{x}}_i$. The projected class means are $m_k={\mathbf{w}}^{\top }{\mathbf{\mu }}_k$, and the projected within-class scatter is ${\mathbf{w}}^{\top }{S}_W\mathbf{w}$ (projecting a scatter matrix squeezes it along $\mathbf{w}$). The separation between the projected class means, squared, is

$$(m_1-m_2{)}^2={\left({\mathbf{w}}^{\top }({\mathbf{\mu }}_1-{\mathbf{\mu }}_2)\right)}^2={\mathbf{w}}^{\top }{S}_B\mathbf{w}$$

where $S_B=({\mathbf{\mu }}_1-{\mathbf{\mu }}_2)({\mathbf{\mu }}_1-{\mathbf{\mu }}_2{)}^{\top }$ is the between-class scatter matrix (a rank-one matrix built from the mean-difference vector). Fisher's criterion packs both goals into one ratio — between-class separation on top, within-class scatter on the bottom:

$$J(\mathbf{w})=\frac{{\mathbf{w}}^{\top }{S}_B\mathbf{w}}{{\mathbf{w}}^{\top }{S}_W\mathbf{w}}$$

Maximizing $J$ means making the numerator (separation) as large as possible relative to the denominator (internal spread). Differentiating with the quotient rule and setting the derivative to zero:

$$\frac{dJ}{d\mathbf{w}}=\frac{2S_B\mathbf{w}({\mathbf{w}}^{\top }{S}_W\mathbf{w})-2S_W\mathbf{w}({\mathbf{w}}^{\top }{S}_B\mathbf{w})}{({\mathbf{w}}^{\top }{S}_W\mathbf{w}{)}^2}=0$$

which simplifies to the generalized eigenvalue problem

$$S_B\mathbf{w}=\lambda S_W\mathbf{w},\lambda =\frac{{\mathbf{w}}^{\top }{S}_B\mathbf{w}}{{\mathbf{w}}^{\top }{S}_W\mathbf{w}}$$

Now use the shape of $S_B$: multiplying it by any vector always returns a multiple of $({\mathbf{\mu }}_1-{\mathbf{\mu }}_2)$, because

$$S_B\mathbf{w}=({\mathbf{\mu }}_1-{\mathbf{\mu }}_2)\left[({\mathbf{\mu }}_1-{\mathbf{\mu }}_2{)}^{\top }\mathbf{w}\right]$$

and the bracket is just a number. So the left side of the eigenvalue equation is parallel to the mean difference, and so $S_W\mathbf{w}$ must be parallel to it too: $S_W\mathbf{w}=\alpha ({\mathbf{\mu }}_1-{\mathbf{\mu }}_2)$ for some number $\alpha$. Multiply both sides by $S_W^{-1}$ and ignore the irrelevant scale $\alpha$ (a direction does not care about length):

$$\mathbf{w}\propto S_W^{-1}({\mathbf{\mu }}_1-{\mathbf{\mu }}_2)$$

which is exactly the professor's formula. The text Research Methodology states the same idea in words — the estimation principle is that the variance between the groups relative to the variance within the group should be maximized.

The projection: draw class 1 as circles and class 2 as triangles in the scatter plot. If you project along the maximum-eigenvalue direction, the projection gives mismatches — triangles and circles fall on top of each other. Project along $\mathbf{w}$ instead, and among all possible directions this one gives the best possible separation: the projected scores of the two classes occupy two separated intervals on the line.

That threshold choice is a separate decision — a common default is the midpoint between the projected class means — but the direction itself is what LDA delivers. A final note on conventions: different textbooks treat LDA with different notations and approaches; the route shown here — within-class scatter matrices, their sum, and $S_W^{-1}({\mathbf{\mu }}_1-{\mathbf{\mu }}_2)$ — is one standard way. The textbook, for example, works with an unstandardized discriminant function of the form $Y=b_0+b_1{X}_1+b_2{X}_2+\cdots$ and reports the between-to-within ratio as an eigenvalue; the two views describe the same separation, dressed in different notation.

14.3 Hierarchical Cluster Analysis

14.3.1 Cluster Analysis: Source and Approach

Cluster analysis (grouping objects into classes when the classes are unknown) is a classification technique built on a simple idea: similarity is measured over several variables, and objects are grouped so that the emerging groups are homogeneous inside and heterogeneous between. The lecture introduces hierarchical cluster analysis through a worked survey example taken from the textbook Research Methodology: Concepts and Cases by Deepak Chawla and Neena Sodi. That book works the whole example through SPSS, which is paid software; the practice here uses R instead, which is open source — the point being that nobody should have to spend time on paid tools. If you already own the book and already work with SPSS, you can follow the example there; otherwise the same analysis is shown here with R.

This SPSS-versus-R split mirrors common industry practice — many classic textbooks are written around paid statistical suites, while the open-source ecosystem offers equivalent workflows at no cost. Analysts routinely re-run textbook examples in free software to learn the method without a license.

14.3.2 The Nano Sample Survey Data

The example is the Nano sample survey: a study of purchase intention for the Nano car from Tata Motors, conducted on 200 two-wheeler owners in the National Capital Region. The study captured their attitudes and demographic profiles. For the in-class exercise the analysis uses 25 respondents who answered 9 attitude questions, each measured on a 5-point Likert scale — a Likert scale (a rating scale where people state their agreement with a statement on points 1 to 5, from strong disagreement to strong agreement). The variables labelled 1a through 1i are the attitudinal variables; the remaining variables in the survey are demographic profiles, and they are set aside for this analysis — demographic profiles would be dealt with in a different way and interpreted with different techniques.

The nine attitude statements, as read out in the lecture:

1. I think in India we have been able to achieve technological standard of high order
2. Made in India
3. Value for money
4. Convenience over style
5. Do not waste expenditure
6. No compromise on safety
7. Saver not spender
8. Try new things
9. Be a part of changing the world

The first statement was garbled in the recording (the spoken words "LA stands for Indian technology, high order" point to it), and the reference textbook confirms the wording above: the same survey's attitudinal table lists "I think in India we have been able to achieve technological standard of high order" as the first statement.

The first respondent's answers were: 5, 5, 3, 2, 3, 3, 4, 1, 1. The full data set is a 25 by 9 matrix of scores between 1 and 5, one row per respondent, one column per question. With intuition you can already guess that respondents with similar answers should cluster together; the whole exercise is to justify that grouping from the data itself.

14.3.3 Distance Matrix and the Most Similar Pair

Hierarchical cluster analysis grows clusters by repeatedly joining the most similar items: the two people whose distance is the minimum. The distance measure used here is the Euclidean distance — the straight-line length between two points in the space of the answers. The general formula:

$$d(\mathbf{x},\mathbf{y})=\sqrt{\sum _{j=1}^p(x_j-y_j{)}^2}$$

The lecture does not bother scanning the entire distance matrix by hand — the software computes it behind the screen, and the graphical representation uses this same formula — so you read the output instead of recomputing.

14.3.4 Two Ways to Identify Clusters

The lecture gives two equivalent ways to read the finished analysis once the agglomeration schedule is complete:

1. Generate the dendrogram and identify the clusters.
2. Generate the agglomeration schedule and identify the clusters.

Either one gives the same answer about which clusters exist. The word agglomeration means building up: the schedule is the written record of the merges — which cluster joined which, stage by stage — and the dendrogram is the same record drawn as a diagram. After identifying the clusters, the next questions are which clusters can be retained and which can be dropped, and finally how to interpret and label the clusters — that is the part that is required from your side.

14.3.5 Reading the Agglomeration Schedule

The agglomeration schedule records, stage by stage, which clusters are combined at each step. Two columns, usually labelled V1 and V2, name the clusters merged at that stage. The sign convention:

• A negative value, say $-3$, means the 3rd leaf — an original respondent — is merged.
• A positive value, say $2$, means the cluster that was formed at stage 2 is merged.

Counting the clusters: 25 respondents start as 25 individual clusters. After stage 1 there are 24 clusters (23 singletons plus one pair). After stage 2 there are 23 clusters, and so on. The schedule is the complete summary of the merging process: for $n$ objects it has $n-1=24$ rows, one per merge, ending with a single cluster holding everyone.

To see how the numbers in the schedule arise, the textbook walks through a miniature version with five consumers (cases 1, 24, 4, 7, 18) and their Euclidean distance matrix. The closest pair is case 1 and case 24 at distance 1.0, so stage 1 merges A(1) and B(24). The next closest pair is case 7 and case 18 at distance 2.0, so stage 2 merges D(7) and E(18). Now the clusters are $\{A,B\}$, $\{D,E\}$, and the singleton C(4). Under average linkage, the distance between cluster $\{A,B\}$ and C is the average of the individual distances: $(d_{AC}+d_{BC})/2=(5+6)/2=5.5$, so stage 3 merges C into $\{A,B\}$ at coefficient 5.5. Finally $\{D,E\}$ joins the rest at the average distance $(52+56+49+51)/4=52$, and the four-stage merging is complete. This is the same machinery the software runs on all 25 respondents, and it explains why the coefficients on the schedule can be fractional numbers.

14.3.6 Choosing the Number of Clusters

The agglomeration schedule also carries the coefficients (heights) at each stage and a difference column between successive coefficients. To choose the number of clusters you read the differences:

• Start from the last coefficient — the stage where all objects have been grouped into a single cluster (stage 24).
• Subtract the coefficient of the second-last stage (stage 23). The lecture reads this difference as about 34 minus 21, giving 13.43 — the level of the two-cluster solution.
• The next difference, at the three-cluster level, is 15.93.
• The next difference after that is small: 0.58.

For comparison, the textbook's SPSS run on the same Nano survey reports coefficients 59.222, 40.667, 11.800 and 8.50 at the final four stages, giving differences 18.55, 28.867 and 3.5 — different numbers from the R output, because different software runs produce different coefficient values, but the pattern is the same: the maximum jump happens when moving from two to three clusters, so the three-cluster solution is recommended again.

14.3.7 The Dendrogram

The other way to assess the number of clusters is to physically observe the dendrogram — the tree graph built from the distance matrix, drawn with heights at every merge. You can read a dendrogram vertically or horizontally; both work. Observing the tree gives the same conclusion as the difference column of the schedule.

A picture of the dendrogram for the survey: name the horizontal axis "respondents (case numbers 1 to 25)" and the vertical axis "height (the coefficient at which clusters merge)". The 25 respondents sit along the base as leaves; each merge draws a branch at the height of its coefficient; pairs that are very similar (like 3 and 8, distance 0) join near the bottom, and bigger groups join higher up. The landmark is the height of the top merges: two large branches meet at a high coefficient, then one of them splits much lower — the big gap between the top merge and the merges below it is the same "big difference" that the schedule showed. The takeaway: the number of tall, well-separated branches you can count below the gap is the number of clusters.

14.3.8 Cluster Analysis in R

The whole analysis is a few R lines:

data <- read.csv(file.choose(), header = TRUE)
d <- dist(data)
fit <- hclust(d, method = "average")
plot(fit)
fit[["merge"]]
fit[["height"]]

In the R output shown in the lecture, the first stage merges respondents 23 and 24 because of their similarity, then 6 and 7, and so on. Notice that this differs from the 3-and-8 pair read earlier from the printed distance matrix: both pairs have distance 0, and when several pairs tie at the minimum distance, the software's tie-breaking decides which one is reported first. The textbook's SPSS schedule for the same survey starts with yet another zero-distance pair (18 and 25). All three outputs are consistent — the ties are real ties — and only the order of reporting differs.

So the complete workflow is: read the data first, then compute the distance matrix, then plot the dendrogram, and read off merge and height — those outputs cover the entire analysis part of cluster analysis.

A note on cost: for $n=25$ respondents there are $25\times 24/2=300$ pairwise distances to compute, and the schedule has $n-1=24$ rows. In general the distance matrix costs about $O(n^{2}p)$ operations for $p$ questions, and the agglomeration loop runs $n-1$ stages, so a naive implementation can reach $O(n^3)$ work in the worst case. That is why hierarchical clustering is comfortable for hundreds of respondents but heavy for millions of records.

14.3.9 Interpretation and Profiling of Clusters

The cluster problem is not yet solved completely at this point. The next session will go back to this same simple data set, walk through the R output again, and then discuss the interpretation and profiling — the labeling — of the three clusters, finishing the topic. After that comes a review session, which consolidates everything discussed in the course rather than dumping new information. Along the way, remember that different research problems may need different variable sets: demographic profiles, for example, would be interpreted with different techniques than the attitudinal variables used here.

14.3.10 Student Questions and Answers

The class raised two questions during the discussion; both were answered on the spot and are worth keeping:

The second question was about how the clusters appear visually. The professor's answer pointed forward to the graphical outputs — which is exactly the material the session then worked through:

Between the two answers: the first is a practical question about sources (book versus software), the second about output formats (matrix, tree, schedule) — two different confusions, so both are kept as separate exchanges rather than merged.

Exam Guidance Summary

The professor's exam guidance across the session, gathered in one place:

The recurring theme is worth stating in plain words: the computations belong to the software, and the exam tests whether you can read the outputs, explain the reasoning behind them, and connect them to the concepts — variation shares in PCA, the discriminant direction in LDA, and the cluster structure in hierarchical cluster analysis.

Key Industry Applications

The session's techniques appear in real practice in three places worth remembering: