도트플롯에서 2단계 유사성을 반영한 문서 모사 판별

Abstract

대부분의 존재하는 모사 판별 시스템은 유사성 측정을 위해 원본 문서와 대상 문서 사이의 단어 빈도를 비교한다. 그러나 이 접근 방법은 단어가 출현한 위치를 무시하기 때문에 순서화된 매치에 대한 정보가 포함되지 않는다. 문서의 모사 판별을 위한 다른 몇몇 접근 방법은 동적 프로그래밍 기법에 기초한 지역 정렬 방식을 사용한다. 이는 단어 출현 순서에 민감한 방식을 기초로 하여 유사성을 계산하고 지역적 최적화 정렬에 유용하게 사용되어 왔다. 그러나 문서 모사 판별을 위해서는 지역적 유사성의 모든 가능성을 측정할 수 있는 전역적인 접근 방법이 필요하다. 본 논문에서는 문서 모사 판별을 위해 도트플롯 기술과 동적 프로그래밍 기법을 조합한 접근 방법을 사용한다. 이 방법은 정보 검색 분야에서 선형적 문서 분할을 위해 사용된 바 있다. 이를 이용하여 모사 의심 위치를 찾을 목적으로 최적 유사성 측정을 가지고 도트플롯 공간 분할을 수행하는 동적 프로그래밍 알고리즘을 제안한다. 제안된 알고리즘은 도트플롯 공간 내에 존재하는 대각선 질감의 비율과 분할 공간의 크기 비율의 두 가지 요소를 조합하는 분할 비용 함수의 전역적인 최대화에 의해 동작한다. 이 두 가지 요소 중 대각선 질감의 비율 요소는 단어의 삽입, 삭제 및 위치 이동을 통해 표면적인 변화를 가한 모사 정보를 포함한 순서화된 모사 부분들의 유사성 정도를 가리킨다. 분할 공간의 크기 비율 요소는 두 비교 문서의 도트플롯 전체 공간 크기에 비례하여 분할 공간 크기가 얼마만큼 차지하는가에 대한 정보를 반영한다. 그러므로 도트플롯 전체 공간이 이 두 가지 요소에 의한 분할 비용 함수의 값이 최대화되는 부분으로 분할된다면 비교되는 두 문서에서 모사가 실제로 이루어진 부분을 찾아내는 것이 가능한 것이다. 이 전역적인 최대화를 위해 동적 프로그래밍 기법을 사용한다. 실험에는 학생들의 리포트에서 빈번하게 사용되는 모사의 다양한 패턴을 가진 문서들을 사용한다. 실험적 결과에는 위의 두 가지 요소를 조합한 전역적인 유사성이 모사 정도를 탐지하고 그것의 위치를 찾아내는 데에 매우 효과적이라는 것을 보인다.; Most of the existing plagiarism detection systems compare word frequency between original text and target text for the similarity measure. These approaches, however, do not include information about ordered matches because they ignore the position of word appearance. Some other approaches for detecting plagiarism use a local alignment method based on dynamic programming technique as the similarity measure. They compute the similarity based on order sensitive method and are useful to the locally optimal alignment. On the other hand, to detect plagiarism, we need the method globally to measure all possibility of local similarity. In this paper, we use the approach that combines dotplots technique and dynamic programming. This method was presented for linear text segmentation in the information retrieval area. We propose a dynamic programming algorithm which performs dotplot space segmentation with optimal similarity measure for finding the position of plagiarism. The proposed algorithm operates by global maximization of a segmentation cost function which incorporates two factors, diagonal textures and within-segment word similarity. Diagonal textures indicate the degree of similarity between ordered plagiarisms which include information about the plagiarism through insertion, deletion, and modification. In addition to, within-segment word similarity reflects the possibility of the plagiarism that the position of words is changed within a segment. For the evaluation of our measure, we use documents with various patterns of plagiarism which is frequently used in reports of students. Experimental results show that our global similarity incorporating of two factors is very effective in detecting plagiarism and finding its position.