Reconhecimento de Padrões (RPD-0041)�

Prof. André E. Lazzaretti

lazzaretti@utfpr.edu.br

https://sites.google.com/site/andrelazzaretti/graduate-courses/reconhecimento-de-padrões-cpgei/cronograma-2025

Lecture 7 - Compressing Data via Dimensionality Reduction

Introduction

Sequential feature selection algorithms

• There are two main categories of dimensionality reduction techniques: feature selection and feature extraction.
• Via feature selection, we select a subset of the original features, whereas in feature extraction, we derive information from the feature set to construct a new feature subspace.
• Sequential feature selection algorithms are a family of greedy search algorithms that are used to reduce an initial d-dimensional feature space to a k-dimensional feature subspace where k<d.

Sequential Backward Selection

• SBS sequentially removes features from the full feature subset until the new feature subspace contains the desired number of features:�

Sequential Forward Selection

SBS in Python

• Implementation from scratch (code).
• kNN with SBS
• Other feature selection methods with scikit-learn

Feature Extraction

• An alternative approach to feature selection for dimensionality reduction is feature extraction.
• Information content of a dataset by transforming it onto a new feature subspace of lower dimensionality than the original one.
• Topics:
• Principal Component Analysis (PCA) for unsupervised data compression.
• Linear Discriminant Analysis (LDA) as a supervised dimensionality�reduction technique for maximizing class separability.
• Nonlinear dimensionality reduction via Kernel Principal Component�Analysis (KPCA).

​

https://lvdmaaten.github.io/publications/papers/TR_Dimensionality_Reduction_Review_2009.pdf

Principal Component Analysis (PCA)

• Unsupervised linear transformation;
• PCA aims to find the directions of maximum variance in high-dimensional data and projects it onto a new subspace with equal or fewer dimensions than the original one;
• Orthogonal axes (principal components) of the new subspace can be interpreted as the directions of maximum variance.

PCA – general idea (math)

• We construct a d×k –dimensional transformation matrix W that allows us to map a sample vector x onto a new k–dimensional feature subspace that has fewer dimensions than the original d–dimensional feature space:

PCA – general idea (algorithm)

PCA – general idea (algorithm)

PCA – general idea (algorithm)

Eigendecomposition

Total and explained variance

Feature Transformation

PCA using Python

• PCA with wine dataset with step-by-step (codes).

​

Linear Discriminant Analysis (LDA)

• The goal in LDA is to find the feature subspace that optimizes class separability.

Linear Discriminant Analysis (LDA)

LDA: details

• Mean:

​

• Within-class scatter matrix:

​

• Individual scatter matrices:

​

• Covariance matrix:

​

• Between-class scatter matrix:

​

​

LDA: algorithm

LDA using Python

• LDA with wine dataset with step-by-step (codes).

​

Nonlinear case

Kernel Functions and PCA

• We perform a nonlinear mapping via kernel PCA that transforms the data onto a higher-dimensional space.
• We then use standard PCA in this higher-dimensional space to project the data back onto a lower-dimensional space where the samples can be separated by a linear classifier.
• However, one downside of this approach is that it is computationally very expensive, and this is where we use the kernel trick.

From PCA to kernel PCA

• Covariance matrix:

Kernel PCA

Kernel PCA using Python

• Kernel PCA step-by-step (codes).

​

Visualizing data with t-SNE

https://www.youtube.com/watch?v=NEaUSP4YerM