(Removing all content from page)
 
(32 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
[[Category:slecture]]
 
−
[[Category:ECE662Spring2014Boutin]]
 
−
[[Category:ECE]]
 
−
[[Category:ECE662]]
 
−
[[Category:pattern recognition]] 
 
  
−
<center><font size= 4>
 
−
Basics and Examples of Principal Component Analysis (PCA)
 
−
</font size>
 
−
 
−
A [https://www.projectrhea.org/learning/slectures.php slecture] by Sujin Jang
 
−
 
−
Partly based on the [[2014_Spring_ECE_662_Boutin|ECE662 Spring 2014 lecture]] material of [[user:mboutin|Prof. Mireille Boutin]].
 
−
</center>
 
−
----
 
−
----
 
−
 
−
== '''Introduction''' ==
 
−
Principal Component Analysis (PCA) is one of famous techniqeus for dimension reduction, feature extraction, and data visualization. In general, PCA is defined by a transformation of a high dimensional vector space into a low dimensional space. Let's consider visualization of 10-dim data. It is barely possible to effectively show the shape of such high dimensional data distribution. PCA provides an efficient way to reduce the dimensionalty (i.e., from 10 to 2), so it is much easier to visualize the shape of data distribution. PCA is also useful in the modeling of robust classifier where considerably small number of high dimensional training data is provided. By reducing the dimensions of learning data sets, PCA provides an effective and efficient method for data description and classification.
 
−
 
−
This lecture is designed to provide a mathematical background of PCA and its applications. First, fundamentals of linear algebra is introduced that will be used in PCA. Technical procedure of PCA will be provided to aid understanding of practical implementation of PCA. Based on the procedure, several examples of PCA will be given in dimension reduction.
 
−
 
−
----
 
−
=='''Eigenvectors, Eigenvalues, and Singular Vector Decompositoin'''==
 
−
To understand mechanism of PCA, it is important to understand some important concepts in linear algebra. In this lecture, we will briefly discuss eigenvectors and eigenvalues of a matrix. Also singular vector decomposition (SVD) will be examined in the extraction of principal components.
 
−
 
−
=== <font size="2">Eigenvectors and Eigenvalues </font>===
 
−
Let define a n-by-n matrix A and a non-zero vector <math>\vec{x}\in\mathbb{R}^{n}</math>. If there exists a scalar value <math>\lambda</math> which satisfies the vector equation
 
−
 
−
<center><math>A\vec{x}=\lambda\vec{x},</math></center>
 
−
 
−
we define <math>\lambda</math> as an eigenvalue of the matrix A, and the corresponding non-zero vector <math>\vec{x}</math> is called an eigenvector of the matrix A. To determine eigenvalues and eigenvectors a characteristic equation
 
−
 
−
<center><math>D(\lambda)=det\left(A-\lambda I\right)</math></center>
 
−
 
−
is used. Here is an example of determining eigenvectors and eigenvalues where the matrix A is given by
 
−
 
−
<center><math>
 
−
A=\left[\begin{matrix}-5 & 2\\
 
−
2 & -2
 
−
\end{matrix}\right].
 
−
</math></center>
 
−
 
−
Then the characteristic equation is given by
 
−
 
−
<center><math>
 
−
D(\lambda)=\left(-5-\lambda\right)\left(-2-\lambda\right)-4=\lambda^{2}+7\lambda+6=0.
 
−
</math></center>
 
−
 
−
By solving the quadratic equation for <math>\lambda</math>, we will have two eigenvalues <math>\lambda_{1}=-1</math> and <math>\lambda_{2}=-6</math>. By substituting <math>\lambda's</math> into the vector equation, we can obtain corresponding eigenvectors;
 
−
 
−
<center><math>
 
−
\lambda_{1}:\;\left(A-\lambda_{1}I\right)\vec{x}=0\Rightarrow\begin{cases}
 
−
-4x_{1}+2x_{2} & =0\\
 
−
2x_{1}-x_{2} & =0
 
−
\end{cases}
 
−
\Rightarrow\vec{x}_{1}=\left[\begin{matrix}1\\
 
−
2
 
−
\end{matrix}\right]
 
−
</math></center>
 
−
 
−
<center><math>
 
−
\lambda_{2}:\;\left(A-\lambda_{2}I\right)\vec{x}=0\Rightarrow\begin{cases}
 
−
x_{1}+2x_{2} & =0\\
 
−
2x_{1}+4x_{2} & =0
 
−
\end{cases}
 
−
\Rightarrow\vec{x}_{2}=\left[\begin{matrix}2\\
 
−
-1
 
−
\end{matrix}\right]
 
−
</math></center>
 
−
 
−
=== <font size="2">Singular Vector Decomposition (SVD)</font>===
 
−
In the implementation of PCA, singular vector decomposition (SVD) is used to extract principal components (eiegenvectors) from a given data set. Given a n-by-m matrix A, a singular vector decomposition of A is expressed as:
 
−
 
−
<center><math>
 
−
A=U\Sigma V^{T}
 
−
</math></center>
 
−
 
−
where <math>U\in\mathbb{R}^{n\times n},\;\Sigma\in\mathbb{R}^{n\times m},\; V\in\mathbb{R}^{m\times m}</math>. The matrix U and V are orthogonal matrices, and consist of left and right singular vectors respectively. The matrix <math>\Sigma</math> is diagonal and consists of non-negative singular values <math>\sigma_{i}</math>. The singular values are placed in <math>\Sigma</math> in descending order such as
 
−
 
−
<center><math>
 
−
\sigma_{1}\geq\sigma_{2}\geq\cdots\geq\sigma_{p}\geq0\; where\; p=min\left(n,m\right).
 
−
</math></center>
 
−
 
−
----
 
−
== '''Technical Procedure of PCA''' ==
 
−
In this section, a brief procedural description of PCA is provided. More detailed theoretical background is directed to BOOK. Assume that we are given by a m-by-n data matrix X consists of n number of m-dim vectors <math>\vec{x}_{i}\in\mathbb{R}^{m}</math>.
 
−
 
−
=== <font size="2">Step 1: Compute mean and covariance of data matrix</font>===
 
−
The covariance matrix of X is called <math>S\in\mathbb{R}^{m\times m}</math> and defined by
 
−
 
−
<center><math>
 
−
S=\frac{1}{n}\sum_{i=1}^{n}\left(\vec{x}_{i}-\bar{x}\right)\left(\vec{x}_{i}-\bar{x}\right)^{T}
 
−
</math></center>
 
−
 
−
where <math>\bar{x}\in\mathbb{R}^{m}</math> is the mean of each row in X and defined by
 
−
 
−
<center><math>
 
−
\bar{x}=\frac{1}{n}\sum_{i=1}^{n}\vec{x}_{i}.
 
−
</math></center>
 
−
 
−
=== <font size="2">Step 2: SVD</font>===
 
−
Singular vector decomposition of S is implemented to extract principal components and directions:
 
−
 
−
<center><math>
 
−
S=U\Sigma V^{T}
 
−
</math></center>
 
−
 
−
where <math>U\in\mathbb{R}^{n\times n},\;\Sigma\in\mathbb{R}^{n\times m},\; V\in\mathbb{R}^{m\times m}</math>. In the implementation, we use the matrix <math>V=\left[u_{1}u_{2}\cdots u_{m}\right]</math> where a vector <math>u_{i}\in\mathbb{R}^{m}</math> represents a principal component direction.
 
−
 
−
=== <font size="2">Step 3: Projection</font>===
 
−
The data matrix X can be projected into a new matrix <math>Y\in\mathbb{R}^{k\times m}</math> by multiplying a matrix <math>P^{T}</math>
 
−
 
−
<center><math>
 
−
Y=P^{T}X
 
−
</math></center>
 
−
 
−
where <math>P=\left[\begin{matrix}u_{1}u_{2}\cdots u_{k}\end{matrix}\right],\; k\leq m</math>. Proper number of principal components k should be selected in prior to perform projection of data matrix.
 
−
----
 
−
== '''Examples''' ==
 
−
----
 
−
==[[slecture_title_of_slecture_review|Questions and comments]]==
 
−
 
−
If you have any questions, comments, etc. please post them on [[PCA_Theory_Examples_Comment|this page]].
 
−
----
 
−
[[2014_Spring_ECE_662_Boutin|Back to ECE662, Spring 2014]]
 

Latest revision as of 11:46, 13 May 2014

Retrieved from "https://www.projectrhea.org/rhea/index.php?title=Sujin_Test&oldid=65880"
Shortcuts
Help Main Wiki Page Random Page Special Pages Log in
Search

Alumni Liaison

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett