질적 분류2 - 스트링 인식기

특징 벡터가 가변 길이의 스트링으로 표현되는 응용

궤적을 동서남북으로 표현, DNA

 

스트링의 거리 계산 방법이 필요한 이유

거리를 정의하면 k-NN이나 군집화 등에 적용 가능

거리 정의하더라도 SVM, 신경망에는 적용 불가능

Levenshtein 거리 계산은 최적화 문제이다

edit distance가 작은 방향으로 움직임

최소 비용의 변환을 찾고 동적 프로그래밍 기법을 적용

 

동적 프로그래밍

2차원 배열 D에 그때까지 최적 거리 기록해 나감

D[j][i] 는 x1,x2,,,,xi를 y1,y2,,,yj로 변환하는데 드는 최소 비용을 가짐

D[r][c]가 갑을 가짐

 

Levenshtein 거리 계산 알고리즘

초기화, 전방 계산, 역 추적의 세 단계

 

Levenshtein 거리 특징

교정 연산마다 비용을 다르게 할 수 있음

삽입과 삭제 비용이 같으면 대칭

대치만 사용하면 해밍 거리가 되고, 삽입과 삭제만 사용하면 최장 공통 부분 스트링 문제가 됨

계산 복잡도 theta(rc)