Download presentation
Presentation is loading. Please wait.
1
9장. 특징 선택 오일석, 패턴인식, 교보문고, 2008. © 오일석, 전북대학교 컴퓨터공학
2
들어가는 말 특징 선택 원래 특징 벡터 xorg=(x1,x2,…,xD)에서 쓸모없거나 중복성이 강한 특징을 찾아 제거하는 작업
차원을 낮추어 주므로 계산 속도 향상 그리고 일반화 능력 증대 효과
3
부류내 분산은 작고 부류간 분산은 크게 해줄수록 좋은 특징 벡터
9.1 특징의 분별력 직관적 이해 부류내 분산과 부류간 분산 부류내 분산within-class variance: 같은 부류에 속하는 샘플이 얼마나 퍼져있는지 척도 부류간 분산between-class variance: 서로 다른 부류의 분포가 얼마나 떨어져 있는지 척도 부류내 분산은 작고 부류간 분산은 크게 해줄수록 좋은 특징 벡터
4
9.1.1 직관적 이해
5
9.1.2 분별력 측정 다이버전스 훈련 샘플의 거리 분류기 성능
6
9.1.2 분별력 측정 다이버전스 거리 측정은 어떻게 하나? KL 다이버전스 활용 (부록 A)
확률 분포 간의 거리를 이용 (거리를 멀게 해주는 특징일수록 좋다.) 거리 측정은 어떻게 하나? KL 다이버전스 활용 (부록 A) 현실적 문제: 확률 분포를 알 때 적용 가능 확률 추정이 안고 있는 차원의 저주 같은 문제를 이어받는다. 2 부류 M 부류
7
9.1.2 분별력 측정 훈련 샘플의 거리 훈련 집합에 있는 샘플을 가지고 직접 측정 (현실 적용이 쉽다.)
xik는 부류 ωi의 k 번째 샘플 dist(xik, xjm)은 두 샘플 간의 거리
8
9.1.2 분별력 측정
9
9.1.2 분별력 측정 분류기 성능
10
9.2 특징 선택 문제의 이해 간단한 두 가지 예 실제 상황에서는 이런 직관을 사용하기 힘들다.
개와 고양이를 분류하는데 눈의 개수와 같은 특징은 쓸모 없다. 그림 9.5: 두 특징은 매우 높은 중복성 하나만 있어도 된다. 실제 상황에서는 이런 직관을 사용하기 힘들다. 효과적인 알고리즘이 필요하다.
11
9.2 특징 선택 문제의 이해 특징 선택 문제 조합적 최적화 문제 Θ(2d)의 계산 복잡도. 방대한 탐색 공간
12
9.2 특징 선택 문제의 이해 임의 탐색 알고리즘 아무 생각 없이 여기 저기 뒤져보는 순진한 알고리즘
13
9.2 특징 선택 문제의 이해 개별 특징 평가 알고리즘 특징들 간의 상관 관계를 전혀 고려하지 않음
특징의 중복성 (그림 9.5)을 무시
14
9.3 전역 탐색 알고리즘
15
낱낱 탐색 알고리즘exhaustive search algorithm
9.3 전역 탐색 알고리즘 낱낱 탐색 알고리즘exhaustive search algorithm 모든 해를 다 살피는 매우 우직한 알고리즘 (d가 큰 경우 비현실적)
16
한정 분기 알고리즘branch and bound algorithm
9.3 전역 탐색 알고리즘 한정 분기 알고리즘branch and bound algorithm 탐색 과정에서 가능성 없는 영역을 배제하여 계산 효율 얻음 단조성 조건을 만족하는 경우에 적용 가능
17
9.3 전역 탐색 알고리즘
18
9.4 순차 탐색 알고리즘
19
SFS 알고리즘sequential forward search algorithm
9.4 순차 탐색 알고리즘 SFS 알고리즘sequential forward search algorithm 한번에 하나씩 특징을 추가해 나가는 방식
20
9.4 순차 탐색 알고리즘
21
PTA 알고리즘plus-p-take-away-q algorithm
9.4 순차 탐색 알고리즘 PTA 알고리즘plus-p-take-away-q algorithm p 개의 특징을 추가하고 r 개를 제거하는 연산을 반복
22
모든 순차 탐색 알고리즘은 욕심greedy 알고리즘이다. 이를 극복하기 위한 통계적 탐색 알고리즘
9.5 통계적 탐색 연산을 가진 알고리즘 모든 순차 탐색 알고리즘은 욕심greedy 알고리즘이다. 전역 최적점이 아니라 지역 최적점에 빠질 가능성 이를 극복하기 위한 통계적 탐색 알고리즘 시뮬레이티드 어닐링 유전 알고리즘 11장에서 자세히 다룸
Similar presentations
