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

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

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

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

6.1.1 원리 결정 트리의 표현 트리 또는 이진 트리 사용 이진 트리의 구현 2018-12-01

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

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

6.1.2 노드에서의 질문 예제 6.1 불순도 측정 2018-12-01

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

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

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

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

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

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

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

2018-12-01

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

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

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

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

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

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

6.3.2 Levenshtein 거리 최적 원리에 따른 순환식 2018-12-01

6.3.2 Levenshtein 거리 예제 6.5 Levenshtein 거리 계산 x=revgniaton, y=recognition 몇 가지 계산 예 2018-12-01

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

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

6.3.3 Damerau-Levenshtein 거리 전방 계산 2018-12-01

6.3.3 Damerau-Levenshtein 거리 역 추적 2018-12-01