패턴인식 개론 Ch.11 주성분 분석법( PCA ).

Presentation on theme: "패턴인식 개론 Ch.11 주성분 분석법( PCA )."— Presentation transcript:

1 패턴인식 개론 Ch.11 주성분 분석법( PCA )

2 학습목표 이 장에서는 대표적인 특징 벡터의 차원 축소 방법 중의 하나인 주성분 분석법에 관하여 공부한다.
특징 벡터의 차원 축소의 필요성과 응용 부분을 간단히 설명하고, 고유벡터와 고유값에 대하여 복습하고, 주성분 분석법을 유도과정과 함께 소개하도록 한다. 실습에서는 MATLAB을 이용하여 주성분 분석법을 실제 시뮬레이션 해봄으로써 입체적으로 이해하도록 한다. 특히, 얼굴 인식에 적용된 주성분 분석법을 상세히 설명하고, 직접 얼굴을 인식하는 시뮬레이션을 해본다.

3 차원의 저주(Curse of dimensionality)
차원의 저주 : 다변량 자료분석 시 차원이 증가함에 따라 생기는 문제들을 말함 Example : 3클래스 패턴인식 문제를 고려해보자 : 가장 간단한 접근법은 (1) 특징공간은 일정한 구역(bin)으로 나누고 (2) 각 구역에 속한 각 클래스 표본들의 비를 구하고 (3) 새로운 표본의 경우는 해당하는 구역을 찾아 그 구역에서 우세한 클래스로 선택한다. 단일 특징을 사용할 경우 아래와 같이 1차원 축을 세 부분으로 나누게 될 때 너무 많은 부분에서 클래스들이 겹치게 됨을 발견하게 된다. 두 개의 특징을 사용하게 되면 bin 의 개 수는 9개로 증가하게 되고 (1) 각 bin 마다 포함되는 표본의 개수를 일정하게 하던지 ( 표본 수가 1차원의 개 에서 2차원의 27 개로 증가) 또는 (2) 1차원의 경우와 같은 수의 표본을 유지하던지를 (매우 희박한 2차원 분산플롯) 선택을 해야 한다.

4 차원의 저주(Curse of dimensionality)
3 개의 특징을 사용하게 되면 문제는 더욱 심각하다. Bin 의 개 수는 33=27 개가 되고, (1) bin 마다 같은 표본 밀도를 유지하고 싶으면 81개의 표본이 (2) 같은 수의 표본을 사용하면 너무 많은 bin 들이 비어있게 된다. <벡터의 차원이 높아짐에 따라 생길 수 있는 문제점들> 특징이 많으면 잡음 특징들까지 포함되므로 오히려 분류에 상처를 줄 뿐이다. 특징이 많으면 패턴 분류기에 의한 학습과 인식 속도가 느려진다. 특징이 많으면 모델링에 필요한 학습 집합의 크기가 커진다. 실제로 “차원의 저주”는 주어진 표본의 크기에서 분류기의 성능을 개선하기 보다는 감소시키는 최대 특징 수 가 존재함을 의미한다. 차원의 저주를 극복하기 위해서는 (1) 사전지식을 활용하거나 (2) 타겟 함수의 smoothness를 증가시키거나 (3) 차원을 줄인다.

5 차원 축소 차원을 축소시킬 두 가지 방법 특징선택 (feature selection) : 전체 특징들로부터 부분집합을 선택함
특징추출 (feature extraction) : 기존의 특징들의 조합으로 구성된 새로운 특징들의 부분집합을 생성함. 특징추출의 문제는 주어진 특징공간 xi ∈ RN 에서 M<N 인 매핑 y=f(x): RNRM 을 찾는 것이다. 이 때 변환된 특징벡터 yi ∈ RM 는 RN의 정보 또는 구조의 대부분을 보존하고 있어야 한다. 일반적으로 최적의 매핑 y=f(x) 는 비선형 함수일 수 있지만, 이러한 비선형함수를 만들 체계적인 방법이 없으므로, 특징 추출에서는 y=Wx 와 같은 선형변환으로 국한하게 된다.

6 차원 축소 특징추출 매핑 y=f(x)의 선택은 우리가 최적화 시키고자 하는 목적에 의해서 결정되며, 크게 두 가지 방법이 있다. 신호표현(Signal Representation): 특징추출매핑의 목적이 낮은 차원공간에서 정확하게 표현하고자 함일 경우  주성분분석법 (PCA: Principal Components Analysis) 분류(Classification): 특징추출매핑의 목적이 낮은 차원에서의 클래스 구분을 증대하고자 함일 경우  선형판별분석법(LDA: Linear Discriminant Analysis)

7 고유벡터와 고유값 (Review) 고유벡터와 고유값 (2x2 example) 예1 : 예2 : 고유값 변환행렬 고유벡터
고유벡터는 정방행렬에서만 찾을 수 있다. 고유벡터에 대한 스케일 처리는 고유벡터의 방향에 영향을 미치지 않는다. 대칭행렬의 고유벡터들은 서로 직교한다.  기저 벡터로 이용할 수 있다. 고유벡터는 그 크기가 1이 되도록 정규화하여 이용한다.

8 고유벡터와 고유값 (Review) 고유벡터와 고유값 (3x3 example) 3×3 정방 대칭 행렬 3개의 열벡터를 가정
c1, c2, c3 는 고유벡터에 해당되며 이들의 단위벡터를 열로 하는 행렬 U를 가정해 보자.

9 Principal Component Analysis (PCA)  (Optional)
x를 정규직교하는 기저 벡터 [φ1, φ2, …, φN]들의 선형결합으로 표현되는 N-차원 무작위 벡터라 하자. 기저벡터 M (M<N) 개만으로 x를 표현하려 한다면, 일부 성분 [yM+1, …, yN]T 를 미리 정한 상수 bi 로 대체하면 된다. 이 때 표현 상에 오차는 다음과 같이 된다. 이러한 표현상의 오차는 크기 Δx의 평균제곱의 형태로 측정할 수 있다. 우리의 목적은 이러한 평균제곱오차를 최소화 하는 기저벡터 φi 와 상수 bi 를 찾는 것이다. N

10 Principal Component Analysis (PCA)  (Optional)
최적의 상수 bi 는 목적함수의 미분을 제로로 하는 식으로부터 구할 수 있다. 평균제곱오차는 다음과 같이 표현할 수 있다. 위의 표현을 최소화하면서 직교성을 갖는 해를 구하게 되며, 이를 위해서 라그랑제 승수 (Lagrange Multiplier) λ i 를 포함시킨다. 기저 벡터에 대한 편미분을 계산하면 따라서 φ i, λ i 는 공분산 행렬 Σx 의 고유벡터와 고유치에 해당한다. where y i = x φ I i.e. i-th 성분은 i-th 기저백터를 곱하여 얻어진다.

11 Principal Component Analysis (PCA)  (Optional)
평균제곱오차를 다음과 같이 표현할 수 있다. 이러한 크기를 최소화하기 위해서는 λ i 가 가장 작은 고유치어야 한다. 따라서, 최소한의 제곱오차로서 x를 표현하기 위해서는 가장 큰 고유치 λ i 에 해당하는 고유 벡터 φ i 들을 선택해야 한다. PCA 차원축소 N차원의 무작위 벡터 x ∈ RN 를 서로 독립인 M개 (M<N) 벡터의 선형결합으로 근사시킬 최적의 방법은 공분산 행렬 ∑x 의 가장 큰 고유치들 λ i 에 해당하는 고유벡터들 φ i 에 무작위 벡터를 사영(투영)시킴으로 이룰 수 있다.

12 주성분 분석 (a) 특징 벡터의 분포 PCA후의 주축 변환결과 주축 U1로 사영을 취하여 1차원으로 축소한 결과
평균 특징데이터 (a) 특징 벡터의 분포 PCA후의 주축 변환결과 주축 U1로 사영을 취하여 1차원으로 축소한 결과 주축 U2 로 사영을 취하여 1차원으로 축소한 결과 (b) PCA후의 주축 변환 결과 (c) 주축 u1로 사영 (d) 주축 u2로 사영

13 Principal Component Analysis (PCA)
주성분 분석법은 다차원 특징 벡터로 이루어진 데이터에 대하여 고차원의 정보를 유지하면서 저차원으로 차원을 축소하는 다변량 데이터 처리 방법 중의 하나다. 특징 데이터는 특징 벡터 차원의 수만큼 존재하는 기준 축을 기준으로 표현되며, 3차원 데이터는 3개의 기준 축을 기준으로 표현된다. 결국 차원을 축소한다는 의미는 이 기준 축의 개수를 줄이는 것으로 생각할 수 있다. 10차원 데이터를 4차원으로 축소하려면 기준 축을 10개에서 4개로 축소하면 된다는 이야기다. 따라서 다변량 데이터의 주성분에 해당하는 주축을 통계적인 방법으로 구하고, 이렇게 해서 얻은 특징 벡터 x를 주축 방향으로 사영(projection)시킴으로써 차원을 축소할 수 있는 것이다. 사영은 행렬의 내적을 이용해 쉽게 구할 수 있다. 주성분 분석은 상관(correlated)이 있는 변량들의 변동(분산)을 줄이는 차원에서 상관이 없는 변량의 집합으로 기준 축을 변환하여, 특징 벡터를 재배치하는 것을 말한다. PCA 차원축소 N차원의 무작위 벡터 x ∈ RN 를 서로 독립인 M개 (M<N) 벡터의 선형결합으로 근사시킬 최적의 방법은 공분산 행렬 ∑x 의 가장 큰 고유치들 λ i 에 해당하는 고유벡터들 φ i 에 무작위 벡터를 사영(투영)시킴으로 이룰 수 있다.

14 주성분 분석 주성분 분석을 통하여 변환행렬 구성 단계
1. N개의 D차원 자료들 xn 으로부터 공분산 행렬 (DxD)를 계산한다. (cov() in Matlab) 2. 고유값 분석을 행한다. (eig() in Matlab) 3. D개의 고유값들 중에서 가장 큰 고유값 C(<D)개를 을 선택한다. 4. 선택된 고유값과 관련된 고유벡터를 구하고 연결하여 변환 행렬 을 만든다. 5. 특징 벡터를 다음의 변환식으로 변환한다.

15 주성분 분석법의 한계 PCA는 공분산 행렬의 고유벡터를 사용하기 때문에 유니모달(unimodal) 가우시안을 따르는 자료들에 있어서 서로 독립적인 축을 찾는데 사용될 수 있다. 즉, 가우시안이 아니거나 비선형인 멀티 모달(multimodal) 패턴에는 적용하기가 곤란하다. PCA의 주요 한계는 특징벡터의 클래스 라벨을 고려하지 않기 때문에 클래스들의 구분성은 고려하지 않는다는 데 있다. PCA는 단순히 변환된 축이 최대 분산방향과 정렬되도록 좌표회전을 수행하는 것이다. 따라서 최대 분산방향이 특징 구분을 좋게 한다는 보장은 없는 것이다.

16 차원 축소의 필요성 주성분 분석 주성분 분석의 역사 특징벡터를 효과적으로 다룰 수 있다.
주성분 분석은 다변량 분석 (multivariate analysis) 분야에서는 아주 오래된 기술이다. 주성분 분석법은 통신 분야에서는 Karhunen-Loeve(카루넨 뢰베) 변환(KL-변환)으로도 알려져 있으며. 이는 다차원 특징 벡터로 이루어진 데이터에 대하여 높은 차원에서의 정보를 유지하면서 낮은 차원으로 차원을 축소시키는 다변량 데이터 처리 방법이다. 주성분분석은 1901년 Pearson에 의해서 처음 소개되었으며, 1963년 Loeve에 의해서 일반화 되기까지 여러 번의 수정을 경험했다. 차원 축소의 필요성 특징벡터를 효과적으로 다룰 수 있다. 높은 차원이 가지는 문제점들을 해결할 수 있다.

17 PCA Example (1) 다음과 같은 파라미터를 갖는 3차원 가우시안 분포인 경우를 고려해 보자.
세 쌍의 주성분 투영이 다음에 보여지고 있다. 첫 번째 투영이 가장 큰 분산을 보이게 되며, 그 다음은 차례대로 감소함을 보인다.

18 PCA Example (2) 아래의 그림은 3차원 자료를 2차원으로 투영한 경우이다. 처음에는 자료 구름의 연장 방향을 제외하고는 자료 점들의 명확한 구조가 보이지를 않으나, 적절한 회전을 하게 되면 숨겨진 구조가 드러나게 된다. 이는 3차원 자료 주위를 돌면서 가장 적절한 관찰방향을 찾는 것과 같다. PCA는 그러한 숨겨진 구조를 찾는데 도움을 준다. PCA는 주어진 자료에서의 대부분의 분산이 처음 몇 개의 차원에 표현되도록 회전을 시키는 것이다.

19 PCA Example (3) 다음과 같이 주어지는 2차원 자료에 대한 주성분을 계산하시오. X = [x1,x2] = {(1,2),(3,3),(3,5),(5,4),(5,6),(6,5),(8,7),(9,8)} Solution 공분산 행렬은 고유값(eigenvalue)은 다음과 같은 특성방정식이 0 이 되는 경우이다. 고유벡터가 이 문제의 답이며 다음과 같이 구한다.

20 MATLAB Simulation 실습 1 MATLAB을 이용한 공분산 행렬의 계산과 고유값, 고유벡터 연습
단계 1: 랜덤 발생기를 사용하여 0과 1사이의 값을 갖는 1000 x 2벡터 R1을 생성하고 x, y 좌표상에 생성된 랜덤 수를 그려 본다. 단계 2: MATLAB함수 mean으로 x와 y축의 평균이 0이 되도록 원 데이터의 집합을 재배치하고, 조정된 점들을 Rctr 이라 이름 붙인다. 새로운 그림을 열어 Rctr 의 모든 점을 그려 본다.

21 MATLAB Simulation 실습 1 MATLAB을 이용한 공분산 행렬의 계산과 고유값, 고유벡터 연습
단계 3: 원점에서 반경 0.5보다 멀리 떨어진 Rctr에 있는 점들은 제거한다. 그 결과 점의 집합을 Rcirc라고 이름 붙인다. 이제 Rcirc 내의 점들은 반지름이 0.5인 원 안에 있다. 새 그림을 열어서 Rcirc에 있는 보든 점을 그려본다.

22 MATLAB Simulation

23 MATLAB Simulation 실습 2 주성분 분석법 시뮬레이션
주성분 분석법을 통하여 2차원 데이터를 1차원으로 축소하는 과정을 시뮬레이션해 보도록 한다. 단계 1 : 데이터 설정 단계 2: MATLAB에서는 공분산 행렬에서 주성분을 바로 구하여 고유값의 크기 순으로 정렬까지 해주는 pcacov 라는 함수가 있다. 이를 이용하여 주성분을 찾아보자.

24 MATLAB Simulation 실습 2 주성분 분석법 시뮬레이션
단계 3 : 원 데이터 집합과 주성분을 곱하면 데이터들은 주성분이 주축이 되도록 회전하게 된다. 단계 4: 축 상으로 주성분이 놓여 있는 지를 확인하기 위해서 다시 주성분을 계산해 보자.

25 MATLAB Simulation 실습 2 주성분 분석법 시뮬레이션
실습 2 주성분 분석법 시뮬레이션 단계 5 : 원 데이터 집합과 주성분으로 내적을 취하면 데이터들이 주성분 상으로 사상되어 1차원 데이터로 차원이 축소된다.

26 MATLAB Simulation

27 MATLAB Simulation 단계 1: 인식후보 얼굴 벡터 집합(S )의 구성

28 MATLAB Simulation 단계 2: 이미지 정규화

29 MATLAB Simulation 단계 3: 평균 얼굴 벡터 (Ψ) 계산
단계 5: N2 ×1 벡터 Φi 에서 공분산 행렬(C) 계산

30 MATLAB Simulation 단계 6: 공분산 행렬(C)의 고유벡터/고유값 계산

31 MATLAB Simulation 단계 7: 주성분 선택
행렬 AAT 의 고유벡터 ui 의 계산은 고차 행렬이므로 계산복잡도가 높다. 그러나 행렬 ATA의 계산 복잡도는 낮다 (MxM 행렬). 우선 ATA 의 고유벡터 vi 를 계산하며, 다음과 같다. ui 와 vi 간의 관계는 다음과 같다. 따라서 AAT 와 ATA 는 같은 고유값을 갖고, 그 고유벡터는 다음과 같은 관계가 성립한다. 결국 AAT 는 N2 개의 고유값과 고유벡터를 가지며, ATA 는 M 개의 고유값과 고유벡터 를 갖는다. 그리고 ATA 의 M개의 고유값은 AAT 의 M개의 가장 큰 고유값과 관련된다. 따라서 ATA 에서 최상의 고유 벡터 M개의 계산 ( ) 하는 것은 AAT 에서 M개의 고유값과 고유벡터를 구하는 것과 같다.

32 MATLAB Simulation 단계 8: 얼굴 인식 단계
인식하고자 하는 입력 얼굴 영상의 중심에 맞추고, 학습얼굴과 같은 크기의 영상( )을 만든 후에 이 영상을 정규화 ( ) 한다. 그리고 각 고유얼굴 (ui ) 에 대하여 사영을 취해 그 성분값( )을 구한다. 사영을 취한다는 것은 내적을 의미한다. 입력되는 얼굴 영상에 대한 각 고유얼굴에 대한 각 고유얼굴 가중치( )는 다음과 같이 계산된다. 여기서 M’는 아주작은 고유값에서 얻은 고유 얼굴을 제외한 개수이므로 그 수는 M 조다 작거나 같다. 이렇게 얻은 가중치를 이용하여 입력 영상을 표현하는 고유얼굴 성분 벡터( )를 구할 수 있다. 그리고, 입력 얼굴은 성분벡터( )의 선형결합으로 입력 얼굴을 재구성할 수 도 있다. 이 값을 구하면, 후보 얼굴 영상들의 고유 얼굴상에서 가중치와 유클리디안 거리를 비교한다. 그 거리가 최소가 되는 얼굴이 가장 입력 얼굴과 유사한 얼굴이 되므로 이 영상 후보를 인식 결과로 결정한다. 만약 얼굴 검출(detection)에 적용하려면 유클리디안 거리가 일정 임계값보다 큰 경우에는 비 얼굴로 반정하고, 작은 경우에는 얼굴로 판정하면 된다.

33 MATLAB Simulation 단계 8: 얼굴 인식 단계