자연어처리 (NLP) - 해밍 거리 (Hamming Distance)

122회 컴퓨터 시스템 응용 1교시 4번 해밍거리

 

 

자연어 처리에서 Feature의 Vectorization을 수행할 때, Clustering시 데이터 간의 형태적 유사성(* 단어간 거리)를 계산하여 유사도를 평가할 때 사용하는 알고리즘 중 해밍 거리가 있습니다.

이 외에 유클리디안 거리, 코사인 유사도, 자가드 계수, 마할라노비스 거리, 피어슨 상관계수, 레벤슈타인 거리 등을 사용합니다.

위의 알고리즘의 경우는 순수하게 문자 벡터의 형태만 고려하기 때문에, 문자 벡터간 의미적 유사성(거리)을 고려하려면 Word2Vec, FastText, Glove, LSA 등을 사용해야합니다.

 

*단어간 거리

1. 형태적 거리 : 오탈자 교정 등에 이용되며, 해밍거리, 코사인 유사도, TF-IDF 등을 통한 벡터로 학습

2. 의미적 거리 : Word Embedding 등을 통한 벡터로 학습

ex. Word2Vec : 단어 간 의미적 유사성(거리)을 벡터로 표현

 

어쨌거나....

 

해밍 거리: 두 문장 간의 편집 거리를 측정하기 위한 문자열 메트릭

=> 같은 길이를 가진 2개의 문자열에서 한 문자열을 다른 문자열로 바꾸기 위해 몇 개의 글자를 바꿔주어야 하는지에 대한 계산 방식입니다.

보통은 네트워크 통신에서 전송시 오류 비트(BER, BER2)를 통해 몇 글자가 오류가 났는지 측정하는 방식으로 사용됩니다.

 

 

 

문자열에서 비교를 해보자면

예1) '가나다라마' 와 '가다다라라' 는 바꿔줘야 할 문자가 '다' 와 '라' 이므로 해밍 거리는 2입니다.

예2) 'toned' 과 'roses' 는 바꿔줘야 할 문자가 'r', 'n', 's' 이므로 해밍 거리는 3입니다.

 

직접적인 활용은 보통 KNN에서 차원 축소 후 해당 벡터의 가까운 이웃을 찾을때 빠른 속도로 인해 많이 사용합니다.

 

그런데, 해밍 거리를 사용하려면 두 문자열의 길이가 동일해야하는 제약이 존재합니다.

이를 개선한 방식이 *레벤슈타인 거리입니다. 한국어에서 단어의 유사성을 체크해서 오탈자를 수정하는데 많이 사용되는 기법입니다. (레벤슈타인 거리는 두 문자열의 길이가 동일하지 않아도 되요.)

*레벤슈타인 거리 : string s1 을 s2 로 변환하는 최소 횟수를 두 string 간의 거리로 정의

 

더 자세한 정보는 https://lovit.github.io/nlp/2018/08/28/levenshtein_hangle/ 여기를 참고하시면 좋습니다.