PCA (Principal Component Analysis)

P

rincipal

C

omponent

A

nalysis

Wanho Choi (wanochoi.com)

평균 (Average)

• _{평균 = 산술 평균 = 표본 평균} • _{통계학의 내용 중에서 가장 이해하기 쉬운 개념 중 하나.} • 개의 관측값 이 주어져 있을 때, 평균은 다음과 같이 정의한다.

µ

= X =

1

N

_i=1

X

i N

∑

X

₁

, X

₂

,

!, X

_N

(

)

N

분산 (Variance)

• _{관측값들이 평균으로부터 얼마나 흩어져 있는가?} • _{퍼져 있는 정도만 중요하기 때문에 부호는 중요하지 않다.} • _{따라서, 각 편차(=관측값-평균)의 제곱의 합의 평균으로 분산} 을 정의한다. (부호를 없애는 방법으로 절대값을 취하는 방법 과 제곱을 취하는 방법이 있는데, 절대값은 대수 연산에 있어 여러 가지 불편함이 있기 때문에 잘 사용하지 않는다.)

V

=

σ

2

=

1

N

(

X

i

−

µ

)

2 i=1 N

∑

예제: 평균과 분산

• 2학년 1반 학생들의 수학 성적 • 2학년 2반 학생들의 수학 성적 65 72 57 92 45 σ2 = 1 5 (65− 66.2) 2 + 72 − 66.2( )2 + 57 − 66.2( )2 + 92 − 66.2( )2 + 45 − 66.2( )2

{

}

= 246.96 µ = 1 5(65 + 72 + 57 + 92 + 45)= 66.2 76 58 72 65 63 σ2 = 1 5 (76− 66.8) 2 + 58 − 66.8( )2 + 72 − 66.8( )2 + 65 − 66.8( )2 + 63− 66.8( )2

{

}

= 41.36 µ = 1 5(76+ 58 + 72 + 65 + 63) = 66.8

표본공간 (Sample Space)

• _{한 번의 시행에서 일어날 수 있는 모든 결과(=사건)의 집합} • _{주사위를 던져서 나오는 숫자에 대한 표본 공간} • _{동전을 던져서 나오는 면에 대한 표본 공간} • 10문제가 나온 수학 시험 점수에 대한 표본 공간

S

= 1,2,3,4,5,6

{

}

S

= front,back

{

}

S

= 0,10,20,30,40,50,60,70,80,90,100

{

}

확률 (Probability)

• _{동일한 조건에서 같은 실험을 무수히 반복할 때 특정 결과가} 나오는 비율. • _{확률은 0과 1 사이의 값을 가진다.} • 1에 가까울수록 확률이 높다고 말하며, 이는 무한 시행시 특정 결과가 나올 확실성이 그만큼 크다는 것을 의미한다. • _{주사위를 던졌을 때 3이 나올 확률: 1/6} • _{동전을 던졌을 때 앞면이 나올 확률: 1/2}

확률변수 (Random Variable)

• _{일정한 확률을 가지고 발생하는 실험결과(사건)에 수치를 부} 여한 것. • _{확률변수와 일반변수의 차이점은 확률표본에서 관찰한 변수인} 지 아닌지에 달려있다. (stochastic vs deterministic) • _{확률변수는 대문자, 확률변수가 취하는 값은 소문자로 표기.}

P(X

= x) = p

확률분포 (Probability Distribution)

• _{확률변수 가 가지는 값과 그 값을 가질 확률과의 대응 관계} • “확률변수 = 주사위를 던졌을 때 나오는 숫자” 에 대한 확률분포는 이산균등분포

X

0 0.05 0.1 0.15 0.2 1 2 3 4 5 6

가우스 분포 (Gaussian Distribution)

• _{정규분포(normal distribution)라고도 한다.} 34.1 34.1 13.5 13.5 2.5 2.5

P(x)

=

1

σ

2

π

e

−(x−µ)2 2σ2

가우스 분포 (Gaussian Distribution)

https://www.youtube.com/watch?v=xDIyAOBa_yU • _{많은 수의 경제, 사회, 자연 현상들이 정규분포를 따른다.} • _{한국 남자의 평균키가 170cm이라는 것은, 키가 170cm에 가} 까운 사람들이 가장 많고, 이 수치에서 크게 벗어난 150cm, 또는 190cm의 사람들의 수는 기하급수적으로 적어진다는 의 미이다.

기대값 (Expectation Value)

• (각 사건이 발생할 때의 결과)×(그 사건이 일어날 확률)을 전체 사건에 대해 합한 값. • _{어떤 확률적 사건에 대한 평균의 의미를 지님.}

E(X)

=

[

x

_i

⋅ P(x

_i

)

]

i=1 N

∑

E(X)

=

µ

예제: 기대값

수익률 확률 호황 50% 10% 보통 30% 50% 불황 -10% 40% E(X) = 50 × 0.1

(

)

+ 30 × 0.5

(

)

+ −10 × 0.4

(

)

= 5 +15 − 4 = 16%

Proof)

E(aX)

= aE(X)

E(aX)=

[

ax_i ⋅ P(x_i)

]

i=1 N

∑

= a

[

x_i ⋅ P(x_i)

]

i=1 N

∑

= aE(X)

V (X) = E (X −⎡⎣ µ)2 ⎤⎦ = ⎡_⎣

(

x_i − µ

)

2 ⋅ P(x_i)⎤_⎦ i=1 N

∑

= ⎡⎣

(

x_i2 − 2µx_i + µ2

)

⋅ P(x_i)⎤⎦ i=1 N

∑

= ⎡⎣x_i2 ⋅ P(x_i)⎤⎦ i=1 N

∑

− 2µ

[

x_i ⋅ P(x_i)

]

i=1 N

∑

+ µ2 P(x_i)

[

]

i=1 N

∑

= E(X2)− 2µ2 + µ2 = E(X2)− µ2

공분산 (Covariance)

• _{서로 다른 두 확률변수의 상관관계를 나타냄.}

• _{두 확률변수의 편차의 곱.}

Cov(X,Y )

= E X − E(X)

⎡⎣

(

)

⋅ Y − E(Y )

(

)

⎤⎦

Cov(X,Y ) > 0 : X ↑⇒ Y ↑ Cov(X,Y ) < 0 : X ↑⇒ Y ↓

Cov(X,Y ) = 0 : no relationship

ex) X : height, Y : weight ex) X : age, Y : eyesight ex) X : age, Y : eye size

상관계수 (Correlation)

Cor(X,Y )

=

E

⎡⎣

(

X

− E(X)

)

⋅ Y − E(Y )

(

)

⎤⎦

σ

_X

⋅

σ

_Y

Cov(X,Y ) = E X − E(X)⎡⎣( )⋅ Y − E(Y )( )⎤⎦

= E XY − XE(Y ) −YE(X) + E(X)E(Y )

[

]

= E(XY ) − E(X)E(Y ) − E(X)E(Y ) + E(X)E(Y ) = E(XY ) − E(X)E(Y )

= E(XY ) − µ_Xµ_Y

Proof)

Cov(X,Y )

= E X − E(X)

⎡⎣

(

)

⋅ Y − E(Y )

(

)

⎤⎦

확률벡터 (Random Vector)

• Multivariate random variables

• _{각 성분이 확률변수인 벡터}

X

=

X

₁

X

₂

!

X

_K

⎡

⎣

⎢

⎢

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

⎥

⎥

x

=

x

₁

x

₂

!

x

_K

⎡

⎣

⎢

⎢

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

⎥

⎥

확률벡터의 기대값과 분산

• _{기대값 벡터} • _{공분산 행렬} ! µ = X = E X₁ X₂ " X_K ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ = E(X₁) E(X₂) " E(X_K ) ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ C(X) =

Var(X₁) Cov(X₁, X₂) ! Cov(X₁, X_K) Cov(X₂, X₁) Var(X₂) ! Cov(X₂, X_K)

! ! " !

Cov(X_K, X₁) Cov(X_K, X₂) ! Var(X_K) ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥

X =

x

₁₁

x

₁₂

⋯ x

_1n

x

₂₁

x

₂₂

⋯ x

_2n

⋮

⋮

⋮

x

_N1

x

_N2

⋯ x

_Nn English Scores (영어 점수) Math Scores (수학 점수) Physics Scores (물리 점수)

Student_1’s Report Card (1번 학생 성적표)

Student_2’s Report Card (2번 학생 성적표)

Student_N’s Report Card (2번 학생 성적표)

⋮

⋯

the 1st feature vector the 2nd feature vector

Given: data points in -dimensional space

(주어진 조건) N (=samples) n

# of students (학생수) # of subjects (과목수)

the location of the -th point: i p_i = (x_i1, x_i2, ⋯, x_in) (i = 1, 2, ⋯, N)

the -th studenti

: the -th element of the -th point

x_ij j i

We can define a data matrix of which (i, j) entry is .x_{ij j = 1, 2, ⋯, n}i = 1, 2, ⋯, N

the -th feature

vector

n

X = x₁₁ x₁₂ ⋯ x_1n x₂₁ x₂₂ ⋯ x_2n ⋮ ⋮ ⋮ x_N1 x_N2 ⋯ x_Nn = f| | ⋯ |₁ f₂ ⋯ f_n | | ⋯ | = − p₁ − − p₂ − ⋮ − p_N − f_j ∈ IRN Data matrix:

: the -th row vector

p_i i

: the -th column vector

f_j j

p_j ∈ IRn

j = 1, 2, ⋯, n i = 1, 2, ⋯, N

Pre-processing:

We are interested in the correlation between two different features. Therefore, we need to make the mean of each feature vector to 0.

(This means moving the center of the -dimensional point cloud to the origin.)n

x_ij ⟵ x_ij − 1 N N ∑ i=1 x_ij : pre-processing step

fT

afb

N (a ≠ b)

dot product

normalization factor to eliminate the dependency to N

학생수가 많아지는 것에 비례해서 correlation 값이 커지는 것을 방지

We can define a n × n matrix with 1 as the entry.

N fTi fj (i, j)

Correlation between two different features:

Covariance matrix: C(X) = 1 N XTX = 1N − f₁ − − f₂ − ⋮ − f_n − | | ⋯ | f₁ f₂ ⋯ f_n | | ⋯ | = 1 N | | ⋯ | p₁ p₂ ⋯ p_n | | ⋯ | − p₁ − − p₂ − ⋮ − p_n −

Principal axis:

The variance in the -direction:u 1 N N ∑ i (pT i u)2 = 1_N N ∑ i (pT i u)T(pTi u) = 1_N N ∑ i (uT_p i)(pTi u) = 1 N N ∑ i uT_p ipTi u = uT_(N1 N ∑ i p_ipT i ₎u = uTC(X)u

Let be the direction of maximum variance

and be a unit vector in that direction, i.e. vu ∥u∥ = 1.

: the -th point in the given data set (= the -th row vector of )

p_i i i X

: the projected point onto

pT

i u u

the modified data matrix: Y =

u₁x₁₁ u₂x₁₂ ⋯ u_nx_1n u₁x₂₁ u₂x₂₂ ⋯ u_nx_2n ⋮ ⋮ ⋮ u₁x_N1 u₂x_N2 ⋯ u_nx_Nn Lagrange’s multiplier: ℒ = uT_{C(X)u − λ(u}T_{u − 1)} ∂ℒ

∂u = 2C(X)u − 2λu = 0 ∴ C(X)u = λu The eigenvector with the largest eigenvalue is the direction of greatest variation

Covariance Body

• 개의 2차원 점들이 주어져 있을 때,

• 2차원 확률변수 에 대한 회의 시행 결과라고 볼 수 있다.

N

from “My Friend, the Covariance Body”

N

X

Covariance Body

• _{이 점들의 분포를 설명해주는 타원 (ellipse).}

Covariance Body

• _{즉, 가장 큰 분포를 가지는 축과,}

가장 작은 분포를 가지는 축을 구하는 문제.

Covariance Body

• _{만약 2차원이 아닌 차원의 점들의 분포라면,} 차원에서 존재하는 타원체(hyper ellipsoid)가 됨. http://mathground.net/ellipsoid/ 3차원 타원체

K

K

Covariance Body

• 2개의 확률변수 와 에 대한 회의 시행 결과라고 볼 수 있다.

N

X

Y

C(X)

=

x

_i2 i=1 N

∑

x

_i

y

_i i=1 N

∑

y

_i

x

_i i=1 N

∑

y

_i2 i=1 N

∑

⎡

⎣

⎢

⎢

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

⎥

⎥

공분산 행렬의 기하학적 의미

• Covariance matrix의 가장 큰 eigenvalue (타원 최대축의 길이)2 가장 큰 eigenvectors : (타원 최대축의 방향) 가장 작은 eigenvalue (타원 최소축의 길이)2 가장 작은 eigenvectors : (타원 최소축의 방향) 가 된다.

∝

∝

사실 ellipsoid는 만들기 나름이라.. eigenvalue의 크기에 비례하는 축을 가지도록 하는 타원체를 생각해도 되지만 covariance matrix의 대각선 성분을 보면 제곱의 형태이기 때문에 eigenvalue와 축의 길이 관계 또한 제곱의 형태로 해석하는 것이 아닐까..

(축의 길이를 singular value로 해석하느냐, eigenvalue로 해석하느냐의 차이일 뿐)

사실 중요한 것은 축의 길이보다는 variance가 큰 순서대로 sorting된 축의 방향을 구하는 것!

공분산 행렬과 Eigen과의 관계

PCA (Principal Component Analysis)

• The main purpose of PCA is the analysis of data to identify patterns that represent the data “well.”

• The principal components can be understood as new axes of the dataset that maximize the variance along those axes (the eigenvectors of the covariance matrix).

• In other words, PCA aims to find the axes with maximum variances along which the data is most spread.

• PCA is used for reducing dimensions from a high dimensional space into a low dimensional space.

PCA (Principal Component Analysis)

PCA

의 활용: Image Compression