질적 분류 예시
분류기 모식도
1. 결정트리
결정트리에서의 4가지 고려사항
이진트리구현의 2가지 방법
1. 배열로 표현
2. linked list
결정트리 노드의 특성
1. left node와 right node를 합치면 부모노드가 됨
2. left node와 right node의 조건에서 중복되는 건 없음
노드 분기를 위한 질문 개수
d 개의 특징이 있고 그들이 평균 n 개의 값을 가진다면 dn 개의 후보 질문
2번과 같이 imbalace하게 분기하는 질문을 만들게 되면
트리의 깊이가 깊어져 비효율적임
3가지 불순도 측정기준
불순도가 감소하는 방향으로 질문을 구성해야함
엔트로피가 최대가 되는 방향으로 질문을 구성해야함
(즉, 엔트로피가 최대가 되고, 거기에 음수값이 붙으므로)
불순도 계산 예시 풀어보기
질문을 선택할 때 사용하는 기준 2가지
불순도 감소량 or 투잉기준이 최대인 질문을 취함
노란색 영역은 각각의 sample이 발생할 확률로
두 확률이 비슷하다면 0이 되어 최소가 됨
즉, 발생확률이 매우 다를 질문을 취해야함
(불순도 감소량 예제 계산해보기)
결정트리의 학습과정
8번라인을 보면 greedy한 학습과정임을 알 수 있음
결정 트리의 특성
특징 값에 대한 제약이 적다.
- 계량, 비계량, 혼합 특징을 모 두 다룰 수 있다.
- 특징 전처리 불필요
분류 결과가 ‘해석 가능’하다. (explainable)
인식 작업이 매우 빠르다.
가지치기(pruning)
- 사전 가지치기
- 사후 가지치기 (일반적으로 사용함)
불안정성이 좋지 않음(신규 데이터가 들어왔을 때 안정적이지 않음)
결정 트리 학습은 욕심 알고리즘
손실 특징(missing feature)을 다루기 쉽다.
- 대리 분기(surrogate split)
missing value가 발생했을 때, backup query를 대신사용하면 됨
** decision tree의 training과정을 tree growing이라고 함
2. 스트링 인식기
스트링의 거리 계산 방법 필요
거리 정의하면 k-NN이나 군집화 등에 적용 가능
거리 정의하더라도 SVM, 신경망에는 적용 불가능
왜: SVM에서는 feature의 개수 차원이 정해져있어야 하기 때문에(설명 다시듣기)
교정 거리 edit distance
위와 같이 간단한 경우는 해밍distance를 쓸 수 있지만
난이도가 복잡한 경우는 아래와 같은 방법을 사용함
(text처럼 많이 추가되고 삭제되는 경우 비추천)
삽입, 삭제, 대치 등의 연산 비용에 따라 측정하는 거리
Levenshtein 거리와 그것의 여러 변종들
예) x=revgniaton, y=recognition둘간의 거리는 5번의 edit distance임
Levenshtein 거리 계산방법
가장 마지막이 최소 edit distace(Levenshtein활용)임 = 4
Levenshtein 거리 계산 알고리즘 세 단계
1. 초기화
2. 전방 계산
3. 역 추적: 교정 연산 목록을 찾음
최적원리
위의 식을 만족하여 cost를 가장 작게하는 값을 가져감
Levenshtein 거리 몇 가지 특성
교정 연산마다 비용을 다르게 할 수 있다.
삽입과 삭제 비용이 같으면 대칭이다.
대치만 사용하면 해밍 거리가 되고, (문자길이가 같은경우)
삽입과 삭제만 사용하면 최장 공통 부분 스트링 문제가 된다.
계산 복잡도 Θ(rc) : 길이가 C인 string을 r인스트링으로 대체하는 것이기 때문에
위의 matrix의 사이즈인 r*c가 복잡도임
→ 연산할 양이 상대적으로 많음
Levenshtein 거리의 확장
교환 연산 추가
예) x=pattren, y=pattern은 교환 연산 하나로 x를 y로 교정
철자 교정 등에 유용
