두 문자열 간의 유사도를 계산하는 문제는 정보 검색, 오타 교정, 스팸필터링 등 다양한 분야에 응용될 수 있다. 동적 계획법 기반의 유사도 계산 방법을 통하여 한글 문자열의 유사도 계산을 위해서는 우선 음소간의 유사도에 대한 정의가 필요하다. 그러나 기존의 방법들은 수동적 설정에 의한 유사도 점수를 사용하고 있다는 한계점이 있다. 본 논문에서는 PAM(Point Accepted Mutation) 행렬과 유사한 확률 모델을 이용하여 변형 단어 집합으로부터 음소 간의 유사도를 자동적으로 계산하는 기법을 제안한다. 제안 기법은 주어진 변형 단어의 집합 내 유사한 단어 쌍을 찾아 문자열 정렬(Text Alignment)을 수행함으로써 음소 변형 규칙을 도출하고, 이로부터 각 음소 쌍의 상호 변형 빈도에 따른 유사도 점수를 계산한다. 실험 결과 특이도(Specificity) 77.2~80.4% 수준에서 불일치 여부에 따른 단순 점수 부여 방식에 비해서는 10.4~14.1%, 수동으로 음소 간 유사도를 직접 설정하는 방식에 비해서는 8.1~11.8%의 민감도(Sensitivity) 향상이 있음을 확인하였다.
두 문자열 간의 유사도를 계산하는 문제는 정보 검색, 오타 교정, 스팸 필터링 등 다양한 분야에 응용될 수 있다. 동적 계획법 기반의 유사도 계산 방법을 통하여 한글 문자열의 유사도 계산을 위해서는 우선 음소간의 유사도에 대한 정의가 필요하다. 그러나 기존의 방법들은 수동적 설정에 의한 유사도 점수를 사용하고 있다는 한계점이 있다. 본 논문에서는 PAM(Point Accepted Mutation) 행렬과 유사한 확률 모델을 이용하여 변형 단어 집합으로부터 음소 간의 유사도를 자동적으로 계산하는 기법을 제안한다. 제안 기법은 주어진 변형 단어의 집합 내 유사한 단어 쌍을 찾아 문자열 정렬(Text Alignment)을 수행함으로써 음소 변형 규칙을 도출하고, 이로부터 각 음소 쌍의 상호 변형 빈도에 따른 유사도 점수를 계산한다. 실험 결과 특이도(Specificity) 77.2~80.4% 수준에서 불일치 여부에 따른 단순 점수 부여 방식에 비해서는 10.4~14.1%, 수동으로 음소 간 유사도를 직접 설정하는 방식에 비해서는 8.1~11.8%의 민감도(Sensitivity) 향상이 있음을 확인하였다.
Determining the similarity between two strings can be applied various area such as information retrieval, spell checker and spam filtering. Similarity calculation between Korean strings based on dynamic programming methods firstly requires a definition of the similarity between phonemes. However, ex...
Determining the similarity between two strings can be applied various area such as information retrieval, spell checker and spam filtering. Similarity calculation between Korean strings based on dynamic programming methods firstly requires a definition of the similarity between phonemes. However, existing methods have a limitation that they use manually set similarity scores. In this paper, we propose a method to automatically calculate inter-phoneme similarity from a given set of variant words using a PAM-like probabilistic model. Our proposed method first finds the pairs of similar words from a given word set, and derives derivation rules from text alignment results among the similar word pairs. Then, similarity scores are calculated from the frequencies of variations between different phonemes. As an experimental result, we show an improvement of 10.1%~14.1% and 8.1%~11.8% in terms of sensitivity compared with the simple match-mismatch scoring scheme and the manually set inter-phoneme similarity scheme, respectively, with a specificity of 77.2%~80.4%.
Determining the similarity between two strings can be applied various area such as information retrieval, spell checker and spam filtering. Similarity calculation between Korean strings based on dynamic programming methods firstly requires a definition of the similarity between phonemes. However, existing methods have a limitation that they use manually set similarity scores. In this paper, we propose a method to automatically calculate inter-phoneme similarity from a given set of variant words using a PAM-like probabilistic model. Our proposed method first finds the pairs of similar words from a given word set, and derives derivation rules from text alignment results among the similar word pairs. Then, similarity scores are calculated from the frequencies of variations between different phonemes. As an experimental result, we show an improvement of 10.1%~14.1% and 8.1%~11.8% in terms of sensitivity compared with the simple match-mismatch scoring scheme and the manually set inter-phoneme similarity scheme, respectively, with a specificity of 77.2%~80.4%.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
그러나 PAM행렬에서 학습을 위하여 사용되는 유사 구간은 갭이 없는 정렬(Ungapped Alignment)를 이용하여 서로 대응시킬 수 있는 충분히 긴 길이의 서열임에 비하여, 단어 필터링 시스템에서의 문자열들은 길이가 매우 짧기 때문에 변형, 특히 삽입이나 삭제가 일어나는 경우 대응관계의 변형이 상대적으로 크게 발생한다. 따라서 본 논문에서는 PAM 행렬의 기법을 기반으로 하되 소기의 목적에 적합하도록 일정 부분 변형하여 응용하도록 한다.
본 논문에서 다룰 음소 간 유사도 점수를 계산하는 문제는 [표 3]과 같이 음소 집합 Σ와 Σ의 원소로 이루어진 문자열들의 집합 W가 주어졌을 때, 이로부터 |Σ+1|×|Σ+1| 크기의 유사도 점수 행렬 Score를 구하는 것이 목적이다.
본 논문에서는 주어진 단어 집합 내에서 자동적으로 유사 단어 및 음소 쌍을 찾아 유사도 점수를 계산하는 기법을 제안하였으며, 결론은 다음과 같다.
본 논문에서는 주어진 변형 단어들의 집합으로부터 유사 단어 쌍을 찾아내고, 해당 단어 쌍들 간의 문자열 정렬을 통하여 음소 변형 규칙을 도출하여, 음소 간의 변형 규칙의 빈도를 통하여 최종적으로 음소 간의 정량적인 유사도를 계산하는 기법을 제안한다. 생물정보학에서 흔히 사용되는 문자 간 점수 행렬인 PAM 행렬의 모델을 목적에 맞게 다소 변형하여 사용하였다.
제안 방법
1. 생물정보학에서 사용되는 PAM 행렬을 응용하여 한글 문자열 상의 음소 간 유사도 점수를 계산하는 방법을 제안하였다.
표 7. 기존 방법과의 비교. 비슷한 민감도 또는 특이도를 기준으로 비교를 했을 때 제안기법이 우수하다.
원래 PAM 행렬을 구성하는 방법[8]에서는 L = 100이 사용되었는데 이는 길이 100당 변형 확률을 의미하는 것이다. 본 논문에서는 한 단어 당 변형 확률을 구하고자 하므로, 문자열 집합 W내의 모든 문자열들의 길이의 평균값을 이용하였다. 한편 mα가 확률을 의미함에도 불구하고 L과 주어진 데이터의 특성에 따라 1이 넘는 경우가 발생하기도 하는데, 이후 최종 유사도 점수 변환 과정에서 처리하도록 한다.
본 논문에서는 주어진 변형 단어들의 집합으로부터 유사 단어 쌍을 찾아내고, 해당 단어 쌍들 간의 문자열 정렬을 통하여 음소 변형 규칙을 도출하여, 음소 간의 변형 규칙의 빈도를 통하여 최종적으로 음소 간의 정량적인 유사도를 계산하는 기법을 제안한다. 생물정보학에서 흔히 사용되는 문자 간 점수 행렬인 PAM 행렬의 모델을 목적에 맞게 다소 변형하여 사용하였다.
수집된 욕설 단어 11,871개를 이용하여 10-fold cross validation 기법에 따라 데이터를 10등분하여 9부분은 학습에, 나머지 1부분을 평가에 이용하는 실험을 교차적으로 시행하였다.
앞서 2장에서 언급하였듯이 음소 간 유사도 점수 계산을 위한 확률 모델을 기본적으로 생물정보학에서 주로 사용되는 PAM(Point Accepted Mutation) 행렬[8]을 구성하는 방법을 기반으로 하되 데이터 특성에 맞도록 다소 변형하여 적용한다.
실험을 위한 데이터는 다음과 같은 방법을 이용하여 직접 수집하였다. 참여자는 20대 남녀 10명이었으며, 각각의 사용자가 변형 욕설을 입력하면 이를 시스템이 무작위로 음소를 변형하고, 그 결과 단어에 대하여 다른 참여자들이 욕설 여부를 평가한 결과를 취합하는 방식으로 진행되었다. 평가 결과 참여자 중 7명 이상이 욕설이라고 판정을 내린 단어가 총 11,871 단어였으며, 특성은 [표 4]와 같다.
대상 데이터
또한 “이발”, “씨알”, “지발” 등과 같이 욕설에서 변형되는 과정에서 원래의 의미를 상실한 단어 1,881개 역시 성능 평가에 활용하였다.
이론/모형
성능 평가 척도로는 민감도(Sensitivity)와 특이도(Specificity)를 이용한다. 욕설 단어(TP+FN)를 욕설과 유사하다고 판정(TP)하는 비율이 민감도이며, 욕설이 아닌 단어(TN+FP)를 욕설과 유사하지 않다(TN)고 판정하는 비율이 특이도이다.
성능/효과
2. 제안 기법은 자동적으로 음소 간의 유사도 점수를 계산해주므로 기존의 수동 점수 설정에 따른 과다한 작업량, 점수의 일관성에 관한 한계점을 극복할 수 있다.
3. 특이도 77.2〜80.4% 수준에서 기본 점수 기법에 비해서는 10.4〜14.1%, 수동 설정 기법[6]에 비해서는 8.1〜11.8%의 민감도 향상을 실험적으로 확인하였다.
제안 기법의 성능은 실험 시 가장 우수한 결과(Fold 8)와 가장 저조한 결과(Fold 10)를 기술하였다. 기본 점수 방법이 84.1%의 민감도에서 불과 29.6%의 특이도를 보이는 반면 제안 기법은 해당 민감도 수치 구간에서 39.4%~42.6%의 특이도를 가지는 것을 확인하였다. 이는 수동으로 직접 음소 간 유사도를 설정한 결과(33.
평가 결과 참여자 중 7명 이상이 욕설이라고 판정을 내린 단어가 총 11,871 단어였으며, 특성은 [표 4]와 같다. 수집 방법의 특성 상 하나의 단어로부터 여러 개의 변형 단어가 파생되기 때문에 본 논문에서 제시한 가정에 부합되는 데이터임을 확인할 수 있다. 또한 “이발”, “씨알”, “지발” 등과 같이 욕설에서 변형되는 과정에서 원래의 의미를 상실한 단어 1,881개 역시 성능 평가에 활용하였다.
가로축은 민감도이며, 세로축은 특이도이다. 실선으로 표시된 것이 제안 기법의 성능이며, 기본 점수 부여 기법이나 수동으로 음소간의 유사도를 설정하는 기법에 비하여 그래프의 곡선이 우측 상단에 위치해 있어 상대적으로 우수한 성능을 보임을 확인할 수 있다.
이를 통해 상호간에 변형이 빈번하게 일어나는 “카지노”-“카ㅈ1노”보다는 일방적인 변형관계인 “카지노”-“카쥐no”에 대한 가중치가 상대적으로 적게 작용하는 결과를 얻을 수 있다.
적당한 수준의 특이도를 유지하여 실험한 경우 기본 점수 방법은 74.9%의 특이도에서 56.7%의 민감도를 보인 반면, 제안 기법은 그보다 다소 높은 특이도(77.2%〜80.4%)에서 67.1%〜70.8%의 민감도를 가짐으로서 기본 점수 방법에 비하여 10.4%〜14.1%, 수동 설정 기법(59.0%)에 비하여는 8.1%〜11.8%의 민감도 성능 향상이 있음을 확인하였다.
정렬 결과를 통하여 불일치하는 음소 쌍“ㅣ”-“ㅟ”, “ㄴ”-“n”, “ㅗ”-“o” 간의 대응 관계를 알 수 있다.
“기본 점수” 방법은 대응하는 두 음소가 일치하는 경우에는 +1점, 불일치하거나 갭(Gap)과 대응되는 경우에는 -1점을 부여하는 점수 부여 방식이고, “수동 설정”은 [6]에서 사용한 점수 부여 방식에 따라 점수를 부여하여 실험을 수행한 결과이다. 제안 기법의 성능은 실험 시 가장 우수한 결과(Fold 8)와 가장 저조한 결과(Fold 10)를 기술하였다. 기본 점수 방법이 84.
기본 점수는 Match=+1, Mismatch=Gap=-1으로 부여하고, 수동 설정은 [6]의 점수를 이용하였다. 제안 기법이 전체적으로 우수하다.
후속연구
따라서 문자의 출현 빈도와 대응 빈도 간의 관계에 대한 실험적 연구가 필요할 것으로 생각되며, 이에 기반을 둔 효과적인 갭(Gap)처리 모델을 위한 개선이 추가적으로 필요하다. 덧붙여, 유사 단어 쌍을 검출하는 단계에 있어서 군집화가 되는 유형이나 성능에 따라 유사도 계산을 위한 대상이 달라지므로 이에 대한 보다 심층적인 실험을 통한 관계 입증이 필요할 것으로 사료된다.
이로 인하여 갭(Gap)문자가 학습에 이용되었음에도 불구하고 갭(Gap) 점수를 부여하는 과정에서는 단순히 다른 음소 간 유사도 점수의 평균 점수만을 이용할 수밖에 없었다. 따라서 문자의 출현 빈도와 대응 빈도 간의 관계에 대한 실험적 연구가 필요할 것으로 생각되며, 이에 기반을 둔 효과적인 갭(Gap)처리 모델을 위한 개선이 추가적으로 필요하다. 덧붙여, 유사 단어 쌍을 검출하는 단계에 있어서 군집화가 되는 유형이나 성능에 따라 유사도 계산을 위한 대상이 달라지므로 이에 대한 보다 심층적인 실험을 통한 관계 입증이 필요할 것으로 사료된다.
질의응답
핵심어
질문
논문에서 추출한 답변
문자열의 유사도 판정 문제의 응용 예시는 무엇이 있는가?
서로 다른 문자열 간의 유사도를 판정하는 문제는 다양한 분야에서 응용될 수 있다[1]. 정보 검색 시 오타나 외래어 음역 등의 문제로 잘못 입력된 질의어를 색인된 올바른 질의어로 교정할 수 있으며, 생물정보학에서는 진화추적이나 유전자의 기능을 발견하기 위하여 서열 간의 유사성을 비교하기도 한다. 이처럼 정보와 관련된 모든 분야에서 문자열의 유사도 판정 문제는 빠질 수 없는 핵심적인 역할을 한다.
한글 문자열 간의 유사성을 판단하기 위해 해야할 것은 무엇인가?
한글은 음소 문자이기 때문에 한글로 이루어진 문자열 간의 유사성을 판단하기 위해서는 우선 음소 간의 유사도에 관한 문제가 해결되어야 한다. 특히 단어 필터링 시스템을 우회하고자 하는 악의적인 사용자는 유사한 형태의 음소를 이용하여 기존의 금지어를 교묘하게 변형해나간다.
완전 일치 탐색 기법의 문제점은 무엇인가?
기존의 완전 일치(Exact Matching) 탐색 기법으로 단어 필터링을 수행하기 위해서는 파생 형태들을 데이터베이스에 수록하여야 한다[2][3]. 그러나 현실적으로 그 경우의 수가 매우 다양하며 또한 앞으로 어떠한 형태의 신형 변종 단어가 발생할지 예측할 수 없기 때문에 불가능하다. 만약 가능하다고 가정하더라도 수많은 유사 단어들을 필터링하기 위해 아무런 전처리 없이 데이터베이스에 수집하는 것은 매우 비효율적인 방법이다. 따라서 데이터 베이스 내 금지어들 중 질의어와 가장 가까운 단어는 무엇인지, 또한 해당 단어들 간의 유사도는 어느 정도인지를 판단하는 것이 필수적이다.
참고문헌 (9)
Gonzalo Navarro, "A Guided Tour to Approximate String Matching," ACM Computing Surveys, Vol.33, No.1, pp.31-88, 2001.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.