6 장. 질적 분류 오일석, 패턴인식, 교보문고, 2008. © 오일석, 전북대학교 컴퓨터공학.

Presentation on theme: "6 장. 질적 분류 오일석, 패턴인식, 교보문고, 2008. © 오일석, 전북대학교 컴퓨터공학."— Presentation transcript:

1 6 장. 질적 분류 오일석, 패턴인식, 교보문고, 2008. © 오일석, 전북대학교 컴퓨터공학

2 들어가는 말 세상에는 참으로 많은 데이터가 있다. 계량 데이터
점수, 매출액, GDP, BOD, 속도, 마찰계수, 토끼 개체수 등 거리 개념 있다. 5는 31보다 크다. 5는 10보다 7에 가깝다. 비계량 데이터 직업, 행정 구역, 혈액형, 성씨, PC 브랜드 등 거리 개념 없다. ‘O형은 B형보다 A형에 가깝다’는 성립 안한다.

3 들어가는 말 6장은 비계량 데이터의 분류를 다룸 질적 분류기 결정 트리 (6.1절) 스트링 인식기 (6.3절)

4 6.1.1 원리 결정 트리의 원리 몇 가지 고려 사항 스무고개와 개념이 비슷 최적 기준에 따라 자동으로 질문을 만들어야 함

5 6.1.1 원리 결정 트리의 표현 트리 또는 이진 트리 사용 이진 트리의 구현

6 6.1.2 노드에서의 질문 결정 트리의 노드 노드의 분기 질문 xi=α? 어떻게 만들 것인가?
d 개의 특징이 있고 그들이 평균 n 개의 값을 가진다면 dn 개의 후보 질문 그들 중 어느 것을 취해야 가장 유리한가?

7 6.1.2 노드에서의 질문 유리한 정도의 판단 기준은? 불순도 측정 기준 XTleft와 XTright가 동질일 수록 좋다.
엔트로피 지니 불순도 오분류 불순도 노드 T에서 ωi가 발생할 확률은

8 6.1.2 노드에서의 질문 예제 6.1 불순도 측정

9 6.1.2 노드에서의 질문 노드에서 질문 선택 불순도 감소량 또는 투잉 기준이 최대인 질문을 취함 불순도 감소량 투잉 기준

10 6.1.2 노드에서의 질문 노드에서 질문 생성 비계량인 경우 xi=α? 계량인 경우 xi<α? 이산
이산 값에 따라 α를 결정 연속 실수 범위를 구간화 하여 α 결정 또는 샘플의 값 분포를 보고 두 값의 가운데를 α로 결정

11 6.1.2 노드에서의 질문 예제 6.2 후보 질문 생성 표 6.1에서 x3의 값의 분포를 조사하면,

12 6.1.2 노드에서의 질문 예제 6.3 불순도 감소량

13 6.1.3 학습 알고리즘 결정 트리 학습 알고리즘 언제 멈출 것인가? 과적합 vs. 설익은 수렴 잎 노드의 부류 할당

14 6.1.4 특성 결정 트리의 특성 특징 값에 대한 제약이 적다. 계량, 비계량, 혼합 특징을 모두 다룰 수 있다.
특징 전처리 불필요 분류 결과가 ‘해석 가능’하다. 인식 작업이 매우 빠르다. 가지치기 사전 가지치기 사후 가지치기 불안정성 결정 트리 학습은 욕심 알고리즘 손실 특징을 다루기 쉽다. 대리 분기

15 6.2 CART, ID3, 그리고 C4.5 대표적인 결정 트리 시스템 비교 어느 것이 좋은가? 패턴 인식의 일반적인 질문
“어느 것이 다른 것을 지배하지 못하고 어느 것이 다른 것에 지배되지도 않는다.”

16

17 6.3 스트링 인식기 특징 벡터가 가변 길이의 스트링으로 표현되는 응용 스트링의 거리 계산 방법 필요
궤적을 동서남북 {E, W, S, N}으로 표현하는 경우 DNA {A, G, C, T} 온라인 글자의 체인 코드 표현 스트링의 거리 계산 방법 필요 거리 정의하면 k-NN이나 군집화 등에 적용 가능 거리 정의하더라도 SVM, 신경망에는 적용 불가능 왜?

18 6.3.1 교정 거리 스트링 간의 거리를 어떻게 정의할까? 교정 거리edit distance 예) 해밍 거리가 적절한가?
삽입, 삭제, 대치 등의 연산 비용에 따라 측정하는 거리 Levenshtein 거리와 그것의 여러 변종들

19 6.3.2 Levenshtein 거리 표기 Levenshtein 거리가 사용하는 세 가지 연산
테스트 샘플 x=x1x2…xc, 기준 샘플 y=y1y2…yr 삽입과 삭제 비용이 다른 경우 x를 y로 변환하는 비용과 y를 x로 변환하는 비용이 다르다. Levenshtein 거리가 사용하는 세 가지 연산 예) x=revgniaton, y=recognition

20 6.3.2 Levenshtein 거리 Levenshtein 거리 계산은 최적화 문제이다. 동적 프로그래밍
최소 비용의 변환을 찾아라. 동적 프로그래밍 기법 적용 동적 프로그래밍 2차원 배열 D에 그때까지의 최적 거리 기록해 나감 D[j][i]는 x1x2…xi를 y1y2..yj로 변환하는데 드는 최소 비용을 가짐 D[r][c]가 답을 가짐

21 6.3.2 Levenshtein 거리 Levenshtein 거리 계산 알고리즘 초기화, 전방 계산, 역 추적의 세 단계

22 6.3.2 Levenshtein 거리 세 단계 전방 계산이 사용하는 세가지 연산 초기화: 배열 생성
전방 계산: 순환식에 따라 거리 채워 나감 역 추적: 교정 연산 목록 찾음 전방 계산이 사용하는 세가지 연산

23 6.3.2 Levenshtein 거리 최적 원리에 따른 순환식

24 6.3.2 Levenshtein 거리 예제 6.5 Levenshtein 거리 계산
x=revgniaton, y=recognition 몇 가지 계산 예

25 6.3.2 Levenshtein 거리 몇 가지 특성 교정 연산마다 비용을 다르게 할 수 있다.
삽입과 삭제 비용이 같으면 대칭이다. 대치만 사용하면 해밍 거리가 되고, 삽입과 삭제만 사용하면 최장 공통 부분 스트링 문제가 된다. 계산 복잡도 Θ(rc)

26 6.3.3 Damerau-Levenshtein 거리
교환 연산 추가 예) x=pattren, y=pattern은 교환 연산 하나로 x를 y로 교정 철자 교정 등에 유용

27 6.3.3 Damerau-Levenshtein 거리
전방 계산

28 6.3.3 Damerau-Levenshtein 거리
역 추적