## Exercise 1 : LDA Classification

From the last assignment, we have a basc understanding of how LDA works. Here, we want to use LDA on a practical example and see how it can help us in the classification process. Besides dimensionality reduction, LDA proides us with inforation of how important the new axes are for class discrimination and it offers a great way to show us if higher dimensional data is actually linearly seperable.

We are going to work with the Statlog(Vehical Silouttes) dataset throughout this exercise. It classifies four types of vehicles(OPEL, SAAB, BUS, VAN) based on the features exgtracted from the corresponding 2D silhoutte from an image of the vehicle(but only the silhoutte metrics are present in the dataset). In total, it measures k=18 features for n = 846 observations classified assigned to one of the four classes. The dataset is also summarized in Table 1.

There are two additional files accompanied by this exercise: train.csv which contains 752 observations supposed to be used for training and test.csv which contains 94 observations extracted to test the classifier.

Our goal is to test a classifier on this dataset and to use LDA as a preprocessing step. The general idea is to reduce the dimensions with LDA and pass the resulting projections to a classifier. For the latter, we are using and SVM.

In order to use LDA here, we first need to generalize the scatter metrics to C-class problems since the approach we have discussed so far is designed for a two-class problem only. The within-class matrix is easily extended by jst adding up every covariance matrix from each class
\begin{equation} S_W = \Sigma = \sum_{i=1}^C {\Sigma}_i \end{equation}


For the between-class scatter matrix, however, we need a new concept since we now have multiple mean vectors p; (one for each class). The idea is to compare the mean from each class with the overall mean
\begin{equation} \mu = \frac{1}{C} \sum_{i=1}^C\mu_i \end{equation}

of all observations (cf. Figure 1). Mathematically, we end up with something like

\begin{equation} S_B = \sum_{i=1}^C N_i(\mu_i - \mu)(\mu_i - \mu)^T \end{equation}

where we sum up all scatter from each class to the overall mean whereby weighting each matrix with the number N; of points in the class. This incorporates a weighting process where classes with more points contribute higher to the resulting matrix.

1. [Pen and Paper] In the previous assignment, the matrix Sp had rank 1 as there was only a single linearly independent vector in Sz. We now want to clarify how this situation changes when we use the general definition of Equation 3 which includes C classes. To answer this question, we need to find the number of linearly independent vectors of Sp. Here, the main ingredients of Sg are the difference vectors p; — pt (defined as column vectors). For simplicity, we discard the other terms and factors as they do not provide new information to our vector system. Then, we can define a new matrix which contains all information.
\begin{equation} A = (\mu_1 - \mu \hspace{0.5cm} \mu_2 - \mu \hspace{0.5cm} ... \hspace{0.5cm}\mu_C - \mu) \in \mathbb{R}^{k*C} \end{equation} <br/>
What is the highest possible rank of the matrix A? Hint: look at the column vectors of A
and Equation 2.




2. [Python] Let’s start with the implementation. We first want to write a function LDA(data, labels) which performs LDA on a labelled dataset (arbitrary dimension and class size). Similar to principal component analysis (covered later), this function should return three values:

    $\hspace{0.5cm}$*The coefficients of the new coordinate system. This is a matrix with the eigenvectors in the columns.*<br/>
    $\hspace{0.5cm}$*The projections of the data points relative to the new coordinate systems.*<br/>
    $\hspace{0.5cm}$*The contribution of each new axis to the class separability. This is called the latent and corresponds to the eigenvalues.*<br/><br/>
    To compute these variables, we implement the procedure of the last assignment with the extensions to deal with multiple classes.

    a) Calculate the two scatter matrices Sy and Sz according to Equation 1 and Equation 3 by iterating over all classes and summing up the individual scatter matrices. Useful functions: np.mean, np. cov, np. outer.

      b) Set up the matrix Sy Sp. Use the (Moore-Penrose) pseudo-inverse (np.linalg.pinv) instead of the normal matrix inverse to improve the stability of your function.

      c) Calculate the eigenvalues and corresponding eigenvectors of the matrix Sj!Sg and sort the result descendingly by the eigenvalues. You can use the np. linalg.eig function but you have to do the sorting by yourself.

      d) With the help of the eigenvectors u; stored in the columns of the matrix U, compute the projections X for each data point x (stored in the rows of $X \in \mathbb{R}^{nxd}$)
      \begin{equation} \tilde{X} = X . U  =  \end{equation}

3. [Python] Write a function which loads the content of one of the *.csv files into your Python program. The last column of the array contains the class label of each observation (encoded as an integer, cf. Table 1). Store both, the data and the labels, in a Numpy array. Hint: set the data types to np. float64.

4. [Python] Training phase: use the content of the train.csv file in the following sub- tasks.

    a) The eigenvectors u; are the axes of the new coordinate system designed for class discrimination and the eigenvalues A; denote how important each axis actually is to discriminate the data. This is very useful to specify the dimension of our new feature space. Print the eigenvalues as “percentage explained”, i.e. what is the contribution of each eigenvalue relative to the available class discrimination
    \begin{equation} \tilde{\lambda}_i = |\frac{\lambda_i}{\sum_{j=1}^k \lambda_j}|\end{equation}

    b) Based on the previous result, choose the dimensionality d < C - 1 = 3 of the new feature space, ie. how many axes you want to use to describe your data in a class discriminative way.

    c) Train an SVM classifier with the d components of the projected data points x. In order to reduce the values to real numbers, you can use (here) the sum of both parts re(X) + im(x). For training, the svm object from the sk learn package with default parameters is suitable for the job (but you can experiment with different kernels if you like).

    d) Remember that in its raw form the dataset contains 18 different features. If you had to decide about the separability of the data, you would be left with a hard job since there is no direct way to visualize the data. Luckily, you chose d to be much smaller.

    Create a plot of the data you used to train the classifier, ie. the corresponding projections, as well as the resulting decision surfaces of the SVM. Figure 2 shows a possible solution and the following list contains some general recommendations:

    + Write a function as you need the same plot again later in the testing phase.

    + For the decision surfaces, it is helpful to generate a meshgrid of the relevant area and predict a label for each point in the grid. Then, the result can be visualized with the contour and contourf functions.

    + It is possible to combine multiple scatter plots. This is useful to plot all projec- tions of one class at a time.



5. [Python] Testing phase: use the content of the test . csv file in the following subtasks.

    a) Project all your test data to your d-dimensional LDA feature space.

    b) Predict labels for the test data with the help of the predict function.
    
    c) Since we also have labels for our test data, we can compare the predictions. A useful tool here is a confusion matrix where each entry cj; denotes how many observations from class i are classified to class j. The diagonal elements contain, therefore, the number of correctly classified elements for each class i. The function confusion_matrix from sklearn.metrics is suitable for this job.

    d) Plot the test projections together with the decision surfaces of the SVM (similar to the training phase).

    e) Explain why the confusion matrix is in coherence with the result of Figure 2.

a7c218908deef46d674c5d895b14d809272ae246
ipynb
Jupyter Notebook
07_lda_classification/lda_classification.ipynb
jhinga-la-la/pattern-recognition-course
7ad4f70b2c427f3c37f59f47768b90371873823c
Apache-2.0
07_lda_classification/lda_classification.ipynb
jhinga-la-la/pattern-recognition-course
7ad4f70b2c427f3c37f59f47768b90371873823c
Apache-2.0
07_lda_classification/lda_classification.ipynb
jhinga-la-la/pattern-recognition-course
7ad4f70b2c427f3c37f59f47768b90371873823c
Apache-2.0
Qwen/Qwen-72B
1. YES
2. YES