패턴인식 개론 Ch.12 선형 판별 분석법 (LDA).

Presentation on theme: "패턴인식 개론 Ch.12 선형 판별 분석법 (LDA)."— Presentation transcript:

1 패턴인식 개론 Ch.12 선형 판별 분석법 (LDA)

2 선형판별분석에 의한 차원 축소 주성분 분석법(PCA)은 데이터의 최적 표현의 견지에서 데이터를 축소하는 방법인데 반하여
선형판별 분석법(LDA)은 데이터의 최적 분류의 견지에서 데이터를 축소하는 방법이라고 할 수 있다.  (목적) 가능한 클래스간의 분별 정보를 최대한 유지시키면서 차원을 축소시키는 것 D-차원 표본 데이터 집합 X={x(1, x(2,..., x(N} 가 주어진 경우, ω1 클래스에 속하는 것이 N1개 이고, ω2 클래스에 속하는 것이 N2개 일 때, x를 임의의 선을 따라서 사영하여 스칼라 y를 얻고자 한다. 가능한 모든 선들 중에서 이러한 스칼라 값들의 분리를 최대화하는 것을 선택한다. (2차원의 경우를 예를 들면 다음과 같다.)

3 선형판별분석법이란? 크다  ---------------------------  작다
선형판별분석법(LDA)은 특징 공간상에서 클래스 분리를 최대화하는 주축으로 사상시켜 선형 부공간으로 차원을 축소하는 방법. 선형판별분석법(LDA)에서는 클래스간 분산(between-class scatter)과 클래스내 분산(within-class scatter) 의 비율을 최대화하는 방식으로 데이터에 대한 특징 벡터의 차원을 축소한다. 판별하기 용이한 분포 판별하기 어려운 분포 클래스간 분산 (between-class Scatter) 크다   작다 클래스내 분산 (within-class Scatter)

4 선형판별분석법이란?

5 2진 분류에 적용된 LDA 어느 사영을 취하는 것이 좋을 것인가?  좋은 사영을 찾기 위해서는 사영들 간의 분리 정도를 측정할 수 있어야 한다. 선형변환에 의한 사영  평균을 기준 척도로 하면, 각 클래스들의 x 와 y 에서의 평균백터는 다음과 같다. 사영된 데이터들의 중심(평균)간의 거리를 목적 함수로 선택하면, 평균만을 고려하면, 클래스 안에서의 표준편차가 고려되지 않으므로 좋은 척도가 아니다.

6 2진 분류에 적용된 LDA Fisher 에 의해서 제안된 방법은 클래스내(within-class)의 스캐터로 정규화한 평균들 간의 차이로 표현된 함수를 최대화시키는 것이다. 각 클래스들에 대하여 스캐터 (공분산과 같은 개념)는 다음과 같이 주어지며 사영 표본들의 클래스내 분산(within-class scatter)  Fisher의 선형판별은 다음의 목적함수를 최대화 하는 선형함수 wTx 에 해당한다. 최대 최소 따라서, Fisher의 선형판별식은 동일한 클래스의 표본들은 인접하게 사영이 취해지고, 동시에 클래스 간의 사영은 중심이 가능한 멀리 떨어지게 하는 변환행렬(w)를 찾아내는 것이다. 어떻게 변환행렬(w)에 대한 함수로 표현되는 위의 목적함수 J(w)를 최대화하는 변환 행렬 w을 찾을 것인가?

7 Fisher’s Linear Discriminant
최적의 사영 w 를 구하기 위해서는 J(w) 를 w 에 대한 함수로 표현해야 한다. 다차원 특징 공간에서 스캐터(scatter) 행렬은 사영 상에서 분산과 동일한 형태 클래스내 스캐터(within-class scatter) 행렬  사영된 y의 스캐터를 특징벡터 x의 스캐터 행렬의 함수로 다음과 같이 표현된다. 따라서

8 Fisher’s Linear Discriminant
마찬가지로 사영된 평균들의 간의 차이 (분산)를 원래의 특징공간에서의 평균들 간의 차이 (분산)으로 다음과 같이 동일한 형태로 표현된다. 클래스간 스캐터(between-class scatter) 행렬 SB 와 SW로 표현된 Fisher의 기준  이 목적함수를 최대로 하는 변환행렬 w 를 어떻게 찾을 것인가? dJ(w)/dw = 0 J(w)의 최대값을 찾기 위해서는 w 에 대하여 미분한 식을 0 으로 놓고, 이를 만족하는 w 를 구하면 된다. J(w) w

9 Fisher’s Linear Discriminant
J(w) 의 최대값을 찾기 위해서는 w 에 대하여 미분한 식을 0으로 놓고, 이를 만족하는 w 를 구하면 된다. 로 나누고 2 를 제거하면,

10 Fisher’s Linear Discriminant
일반화한 고유값 문제 ( )의 또 다른 해법으로 는 같은 방향의 벡터이므로 Ronald Aylmer Fisher ( ) 벡터 w 의 크기는 중요하지 않으므로 이를 무시하면  Fisher's Linear Discriminant(1936)

11 LDA Example 다음의 2차원 데이타에 대한 선형판별사영을 구하라.
X1 = (x1,x2) = {(4,1),(2,4),(2,3),(3,6),(4,4)} X2 = (x1,x2) = {(9,10),(6,8),(9,5),(8,7),(10,8)} Solution : 클래스들의 분산 및 평균 클래스간의 분산과 클래스내의 분산은 각간 다음과 같다. 일반화된 고유값 문제의 해로 LDA 사영을 구하면 또는 직접

12 C-클래스 분류에 적용된 LDA Fisher의 LDA는 C-클래스 문제로 자연스럽게 일반화 될 수 있다.
y 로의 단일 사영 대신에, (C-1)개의 사영벡터 wi 에 의한 (C-1) 개의 사영 [y1,y2,...,yc-1]을 구하게 되며, 이때의 사영벡터들은 사영행렬 W=[w1|w2|...|wc-1] 의 열들로 정렬된다. 클래스내 분산(within-class scatter) 의 일반화는 클래스간 분산(between-class scatter) 의 일반화는 는 총 스캐터 행렬이라 한다.

13 C-클래스 분류에 적용된 LDA 사영된 표본들에 대한 평균벡터와 스캐터행렬 :
를 최대화하는 최적의 사영행렬 W*는 위의 에 대하여 일반화된 고유값 문제에서의 가장 큰 고유값들과 관련된 고유벡터들을 열로 하는 행렬이 된다.

14 LDA의 두가지 접근법과 한계 클래스-종속 변환 : 이 접근법은 클래스간 분산과 각각의 클래스내 분산의 비율을 최대화 하는 방법이다. 이 변환의 주된 목적은, 적절한 클래스 분류 능력을 가지도록 (클래스간 분산과 클래스내 분산의) 비율을 최대화하는 변환법이다. 해당 클래스의 변환 행렬을 클래스마다 지정하여야 하므로 2클래스 분류에서는 두 개의 최적화된 변환 행렬을 사용하게 된다. 즉 의 고유값 문제를 푼다 클래스-독립 변환 : 이 접근법은 클래스간 분산과 전체의 클래스내 분산 비율을 최대화하는 방법이다. 이 방법은 데이터 집합을 변환하기 위해서 하나의 최적화된 변환 행렬을 사용하며, 모든 자료는 그들의 해당하는 클래스와 상관 없이 같은 변환을 사용한다. 이러한 종류의 LDA에서는 각각의 클래스는 모든 다른 클래스에 대하여 분리된 클래스로 간주된다. 즉 의 고유값 문제를 푼다 클래스-종속 변환 클래스-독립 변환

15 LDA의 두가지 접근법과 한계 LDA의 한계

16 LDA의 알고리즘 선형판별분석(클래스-종속)에 의한 변환행렬 구성 및 분류 방법
1. 클래스간 분산(between-class scatter) SB 를 구한다. 2. 각각의 클래스내 분산 (within-class scatter) SWi 를 구한다. ( )  클래스-독립의 경우. 3. 각각의 에 대한 고유값 분석을 수행한다. i-클래스의 고유치들 중에서 q 개의 가장 큰 고유값 에 해당하는 고유벡터 를 선택하여 이를 열로 하는 i-클래스의 변환행렬 Wi 를 구성한다. 4. 각각의 훈련자료들을 변환한다. 5. 임의의 시험자료들을 변환하여(using WiT), 변환된 훈련자료의 평균과 비교하여 클래스를 결정한다.

17 LDA vs PCA 냄새감지문제에서의 PCA와 LDA의 효용성 실험. - 다섯 종류의 커피빈을 화학가스감지기에 실험하였다. 각각의 커피에 대하여 45회 실험을 한 후에 가스감지반응을 처리하여 60차원의 특징벡터를 얻어 냈다. 3차원 분산플롯결과는 LDA 가 PCA보다 클래스판별에 뛰어나다는 것을 명확히 보여주고 있다.

18 MATLAB 실습