인터넷의 활용도가 높아짐에 따라, 스팸메일이 전체 메일에서 차지하는 비중이 점점 커지게 되었다. 전체 인터넷 자원에서 필요에 의해 사용되는 메일의 기능보다, 주로 광고나 악성코드 등의 전파를 위한 목적으로 사용되는 메일의 비중이 점점 커지고 있으며, 이를 방지하기 위한 컴퓨터 및 네트워크, 인적자원의 소모가 매우 심각해지고 있다. 이를 해결하기 위해 스팸 메일 필터링에 대한 연구가 활발히 진행되어 왔으며, 현재는 문맥상의 의미는 없지만 가독상에서 의미를 해석할 수 있는 문장에 대한 연구가 활발히 이루어지고 있다. 이러한 방식의 메일은 기존의 어휘를 분석하거나 문서 분류 기법 등을 이용한 스팸 메일을 필터링 방법을 통해 분류하기 어렵다. 본 연구는 이와 같은 어려움을 해결하기 위해 메일의 제목에 대한 N-GRAM 색인화를 통해 베이지안 및 SVM 을 이용하여 스팸 메일을 필터링 하는 방법을 제안한다.
인터넷의 활용도가 높아짐에 따라, 스팸메일이 전체 메일에서 차지하는 비중이 점점 커지게 되었다. 전체 인터넷 자원에서 필요에 의해 사용되는 메일의 기능보다, 주로 광고나 악성코드 등의 전파를 위한 목적으로 사용되는 메일의 비중이 점점 커지고 있으며, 이를 방지하기 위한 컴퓨터 및 네트워크, 인적자원의 소모가 매우 심각해지고 있다. 이를 해결하기 위해 스팸 메일 필터링에 대한 연구가 활발히 진행되어 왔으며, 현재는 문맥상의 의미는 없지만 가독상에서 의미를 해석할 수 있는 문장에 대한 연구가 활발히 이루어지고 있다. 이러한 방식의 메일은 기존의 어휘를 분석하거나 문서 분류 기법 등을 이용한 스팸 메일을 필터링 방법을 통해 분류하기 어렵다. 본 연구는 이와 같은 어려움을 해결하기 위해 메일의 제목에 대한 N-GRAM 색인화를 통해 베이지안 및 SVM 을 이용하여 스팸 메일을 필터링 하는 방법을 제안한다.
As the use of the internet increases, the distribution of spam mail has also vastly increased. The email's main use was for the exchange of information, however, currently it is being more frequently used for advertisement and malware distribution. This is a serious problem because it consumes a lar...
As the use of the internet increases, the distribution of spam mail has also vastly increased. The email's main use was for the exchange of information, however, currently it is being more frequently used for advertisement and malware distribution. This is a serious problem because it consumes a large amount of the limited internet resources. Furthermore, an extensive amount of computer, network and human resources are consumed to prevent it. As a result much research is being done to prevent and filter spam. Currently, research is being done on readable sentences which do not use proper grammar. This type of spam can not be classified by previous vocabulary analysis or document classification methods. This paper proposes a method to filter spam by using the subject of the mail and N-GRAM for indexing and Bayesian, SVM algorithms for classification.
As the use of the internet increases, the distribution of spam mail has also vastly increased. The email's main use was for the exchange of information, however, currently it is being more frequently used for advertisement and malware distribution. This is a serious problem because it consumes a large amount of the limited internet resources. Furthermore, an extensive amount of computer, network and human resources are consumed to prevent it. As a result much research is being done to prevent and filter spam. Currently, research is being done on readable sentences which do not use proper grammar. This type of spam can not be classified by previous vocabulary analysis or document classification methods. This paper proposes a method to filter spam by using the subject of the mail and N-GRAM for indexing and Bayesian, SVM algorithms for classification.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 데이터마이닝에서 발생할 수 있는 프라이버시 침해 분쟁을 최소화하기 위해 메일의 헤더부분만을 사용하며, 그 중에서도 메일의 목적이 가장 많이 드러나는 메일 제목에 대해 N-GRAM 색인화를 사용하여, 분류를 위한 특징을 도출한다. 그러나 메일 제목이 없는 등, 메일 제목만으로 특징을 도출할 수 없는 상황이 발생할 수 있다.
따라서 기존의 어휘 분석 방법이나 문서 분류 기법 등을 이용한 스팸 메일을 필터링 방법은 위와 같은 가독상의 해석 문제를 해결하기 어렵고, 파괴된 문장을 복원하기 위해 추가적인 단어 인식 및 매칭 과정이 필요 하다[3-6]. 본 논문에서는 이러한 추가적인 과정 없이 메일의 제목에 대한 N-GRAM 색인화와 받는 사람 ID 리스 트에 대한 Levenshtein distance[7]를 사용하여 ID 간의 유사도를 사용하는 것을 제안한다.
본 논문에서는 최근 들어 점점 심각한 보안 문제로 부각되고 있는 스팸 메일 필터링을 위한 연구를 수행하였다. 스팸 메일이 한 번에 여러 사람에게 전송된다는 특성을 적용하기 위해 받는 사람 ID 리스트에 대한 Levenshtein distance을 통해 ID의 유사도를 측정하였다.
제안 방법
스팸 메일 필터링을 위해 SVM 분류기를 사용한 연구 사례로는 서정우의 연구가 있다[15]. N-GRAM을적용하여 생성된 색인어와 메일 제목에서 사용되는 단어의 빈도수를 조사하고, 그 중 빈도수가 높은 단어 m 개를 추출하여 생성한 단어 사전을 검색하여 데이터 그룹을 생성하고, SVM을 통해 스팸 메일을 분류하였다. 이 연구에서 실험을 위해 도출한 데이터 셋의 특징은, 단어사전과 N-GRAM 색인어를 검색하여, 단어사전과의 일치 여부를 표현하는 2진 결과 값을 갖는다.
그리고 N이 2라고 가정 후, 메일 제목에 대한 N-GRAM 색인화를 하여 유사도 평가 값과 병합 후 스팸 메일 분류 실험을 실행한다. N이 2일 때의 스팸 메일 분류 실험이 끝나면 N을 3으로 증가 시키고 메일 제목에 대한 N-GRAM 색인화를 다시 실행하여, 앞서 구한 받는 사람 리스트의 유사도 측정 결과와 병합 후 다시 스팸 메일 분류 실험을 진행한다. 이와 같은 단계를 반복해서 실행한다.
강승식이 제안한 방법은 메일 주소의 유효성검사와 정보 검색 및 문서 분류에서 주로 사용되는 tf*idf를 각단어의 가중치로 사용한 나이브 베이지안 분류자에 의해 메일 제목과 본문 내용에 대해 각각 스팸 메일 확률을 계산하는 방법을 적용하였다. 이 때, 메일 제목과 내용에 사용되는 동일한 단어에 대한 중요도를 차별화함으로써 필터링을 시행하였다.
공미경, 이경순이 제안한 방법의 경우, 보내는 사람에 대한 블랙 리스트 및 화이트 리스트 기반의 메일 필터링을 우선적으로 실시한 후, 최대 엔트로피 모델을 통해 도출되는 스팸성 자질과 URL 자질 확률을 곱하여 스팸 메일을 분류하는 방법을 제안하였다[16]. 이 논문에서 스팸성 자질은 스팸메일에 빈번하게 나타나는 특징이나 스패머들이 인위적으로 메일에 삽입하는 패턴들을 숫자와 관련된 자질, 비정상적으로 변형된 자질, 강조의 목적으로 사용된 자질 등으로 나누어 검사한다.
받는 사람 리스트 유사도 측정은 단 한번만 실행하여, 학습 데이터 셋을 위한 유사도 평가 값을 도출한다. 그리고 N이 2라고 가정 후, 메일 제목에 대한 N-GRAM 색인화를 하여 유사도 평가 값과 병합 후 스팸 메일 분류 실험을 실행한다. N이 2일 때의 스팸 메일 분류 실험이 끝나면 N을 3으로 증가 시키고 메일 제목에 대한 N-GRAM 색인화를 다시 실행하여, 앞서 구한 받는 사람 리스트의 유사도 측정 결과와 병합 후 다시 스팸 메일 분류 실험을 진행한다.
뉴스레터에 등록된 메일과 스팸 메일은 받는 사람의 필요에 의해 메일링 리스트에 가입하여, 주기적으로 혹은 사용자 기호에 맞는 정보 제공을 목적으로 하기 때문에 사용자가 원치 않는 불특정 다수의 인물에게 보내 지는 스팸 메일과 차이가 있어 정상 메일로 분류하였다.
단계 2 : 수집된 메일에서 각 메일마다 받는 사람의 ID 리스트를 추출하여 받는 사람 리스트의수, 받는 사람 ID의 수, 받는 사람 HOST의수, Levenshtein distance 등을 추출하여, 각 메일 데이터에 대한 데이터 셋을 생성 한다.
단계 4 : 동일한 학습 데이터에 대해 단계 2와 단계 3의 결과로 생성된 받는 사람 리스트의 유사도 측정값과 메일 제목에 대한 N-GRAM 색인화 값들을 병합 최종의 학습 데이터 셋을 생성한다. 또한 같은 특징 벡터에 대한 실험 데이터 셋도 생성하여 최종 분류 실험을 진행한다.
스팸 메일이 한 번에 여러 사람에게 전송된다는 특성을 적용하기 위해 받는 사람 ID 리스트에 대한 Levenshtein distance을 통해 ID의 유사도를 측정하였다. 또한 문법적으로 파괴된 문장이 가독 상에서 해석될수 있고, 스팸 메일들이 이러한 방법을 통해 기존의 스팸 메일 필터링 알고리즘을 회피하기 때문에, 이를 해결 하기 위해 단어 사전 및 어휘 분석을 제외한 모든 메일 제목에 대해 N-GRAM 색인화를 수행하여, 스팸메일 필터링에 적용하는 방법을 제안하였다.
그러나 베이지안 및 SVM을 사용한 분류 실험 모두 최대의 분류율을 가질 때, FN이 15% ~ 30% 사이로 나타나는 것을 확인하였다. 본 논문의 실험에서는 사용자가 메일링 리스트에 등록하여 발송된 쇼핑 및 뉴스, 기타 정보 메일을 정상 메일로 분류하여 학습 데이터를 생성하였는데, 실험을 통해 정상 메일로 잘못 분류된 스팸메일의 대부분이 메일링 리스트에 의해 발송된 메일과 비슷한 메일 제목을 가지고 있었다. 이런 메일에 대한 분류는 White List 기반의 분류나 서로 다른 특징을 가지는 특징을 추출 및 생성해내는 방법이 필요하다.
서로 다른 성격을 가지는 분류기에 대해 미치는 영향을 알아보기 위해 베이지안 분류기와 SVM 분류기에 대해 실험하였다. 실험 결과로 베이지안 분류기에 대한 결과로 N이 최소일 때 분류율이 가장 높게 나타났다.
스팸 메일 분류 실험을 위해서 베이지안 분류기와 SVM을 사용하였다. SVM 실험에서는 C-SVM을 사용하였으며, Radial kernel을 사용하였다.
스팸 메일 분류를 위한 전처리는 앞서 제안하는 방법과 같이 이루어지며, 최종적으로 도출된 학습 데이터 셋의 특징 벡터는 [표 2]와 같으며, 도출된 특징 벡터에 대한 실험 데이터의 특징을 도출한 결과로 얻어진 실험 데이터 셋과 학습 데이터 셋을 이용하여 스팸 메일 분류 실험을 진행한다.
본 논문에서는 최근 들어 점점 심각한 보안 문제로 부각되고 있는 스팸 메일 필터링을 위한 연구를 수행하였다. 스팸 메일이 한 번에 여러 사람에게 전송된다는 특성을 적용하기 위해 받는 사람 ID 리스트에 대한 Levenshtein distance을 통해 ID의 유사도를 측정하였다. 또한 문법적으로 파괴된 문장이 가독 상에서 해석될수 있고, 스팸 메일들이 이러한 방법을 통해 기존의 스팸 메일 필터링 알고리즘을 회피하기 때문에, 이를 해결 하기 위해 단어 사전 및 어휘 분석을 제외한 모든 메일 제목에 대해 N-GRAM 색인화를 수행하여, 스팸메일 필터링에 적용하는 방법을 제안하였다.
공미경, 이경순이 제안한 방법의 경우, 보내는 사람에 대한 블랙 리스트 및 화이트 리스트 기반의 메일 필터링을 우선적으로 실시한 후, 최대 엔트로피 모델을 통해 도출되는 스팸성 자질과 URL 자질 확률을 곱하여 스팸 메일을 분류하는 방법을 제안하였다[16]. 이 논문에서 스팸성 자질은 스팸메일에 빈번하게 나타나는 특징이나 스패머들이 인위적으로 메일에 삽입하는 패턴들을 숫자와 관련된 자질, 비정상적으로 변형된 자질, 강조의 목적으로 사용된 자질 등으로 나누어 검사한다. 또한, 비정상적으로 생성된 URL을 검사하여 스팸성 자질을 테스트 한다.
강승식이 제안한 방법은 메일 주소의 유효성검사와 정보 검색 및 문서 분류에서 주로 사용되는 tf*idf를 각단어의 가중치로 사용한 나이브 베이지안 분류자에 의해 메일 제목과 본문 내용에 대해 각각 스팸 메일 확률을 계산하는 방법을 적용하였다. 이 때, 메일 제목과 내용에 사용되는 동일한 단어에 대한 중요도를 차별화함으로써 필터링을 시행하였다. 이 방법 역시 단순 나이브 베이지안을 적용한 메일 분류에 비해 높은 성능을 보였다[14].
메일 필터링에 사용한 방법은 가중 치를 이용한 베이지안 분류이며, 메일을 파싱하여 토큰의 특징을 저장하고, 해당 클래스에서 특징이 갖가지는 빈도수에 의해 가중치가 정의된다. 이 방법은 단순한 베이지안 분류기에 의한 필터링 보다 우수한 성능을 보였으며, 분류기에 의한 필터링 후에 지능형 에이전트 시스 템을 통해 사용자의 행동을 관찰하여, 최종 메일 분류에 따른 분류 모델의 재학습 방법을 시행하였다. 이 방법을 이용하여 시간이 경과함에 따라 메일의 학습 데이터가 많아질수록 점점 필터링 성능이 향상되었다.
N-GRAM을적용하여 생성된 색인어와 메일 제목에서 사용되는 단어의 빈도수를 조사하고, 그 중 빈도수가 높은 단어 m 개를 추출하여 생성한 단어 사전을 검색하여 데이터 그룹을 생성하고, SVM을 통해 스팸 메일을 분류하였다. 이 연구에서 실험을 위해 도출한 데이터 셋의 특징은, 단어사전과 N-GRAM 색인어를 검색하여, 단어사전과의 일치 여부를 표현하는 2진 결과 값을 갖는다. 앞서 언급한 언어 파괴에 관련된 문제는 다루지 않고 있으며, 파괴된 문자열에 대한 복구 및 인식 과정 역시 존재하지 않는다.
대상 데이터
실험에 사용된 데이터는 10명이 국내외 대형 포탈 사이트와 교내 메일 서버에서 일주일 가량 수집한 것으로 [표 5]와 같으며, 총 2061개의 메일을 학습 데이터 셋 70%, 실험 데이터 셋 30%로 나누어 사용하였다.
이론/모형
베이지안 분류기는 Weka 3.5.7[11]을 사용하였으며, LibSVM 2.8[18]을 사용하여 SVM 분류 실험을 진행하였다.
성능/효과
그러나 두 실험 결과 모두 분류율이 최상일 때, 스팸 메일을 정상 메일로 분류하는 False-Negative(FN)가 15%~30% 사이로 나타나는 것을 확인할 수 있다. 잘못 분류된 스팸 메일 대부분은 정상 메일로 분류한 메일링 리스트에 등록된 쇼핑 및 뉴스, 정보 관련 메일과 유사한 제목을 가지고 있었다.
그러나 베이지안 및 SVM을 사용한 분류 실험 모두 최대의 분류율을 가질 때, FN이 15% ~ 30% 사이로 나타나는 것을 확인하였다. 본 논문의 실험에서는 사용자가 메일링 리스트에 등록하여 발송된 쇼핑 및 뉴스, 기타 정보 메일을 정상 메일로 분류하여 학습 데이터를 생성하였는데, 실험을 통해 정상 메일로 잘못 분류된 스팸메일의 대부분이 메일링 리스트에 의해 발송된 메일과 비슷한 메일 제목을 가지고 있었다.
신뢰할 수 있는 스팸 메일 필터링 시스템을 위해서는 이 값이 최소가 되도록 해야하기 때문에, FP가최소로 나타나는 N이 7일 때의 데이터 셋을 이용한다면, 분류율 감소 및 FN 증가는 피할 수 없게된다. 반면, SVM을 사용하였을 때는 N에 관계없이 FP가 전혀 나타나지 않았으며, N이 가장 작을 때 가장 높은 분류율을 가지는 것을 알 수 있다.
[표 6]은 본 논문에서 제안하는 방법에 의하여, 추출된 데이터를 사용한 베이지안 분류기를 사용한 결과와 해당 confusion matrix를 나타낸 것이다. 베이지안 결정 이론을 적용하여 스팸 필터링을 실시한 결과 N이 2일때, 스팸과 정상을 가장 정확하게 분류하였다. 그러나 스팸 메일 필터링에서는 스팸 메일을 정상 메일로 분류하는 것 보다, 정상 메일을 스팸 메일로 분류하는 것이 매우 치명적으로 작용하게 된다.
본 논문에서 제안한 제목에 대한 N-GRAM 색인화의 결과로 매우 많은 개수의 특징 변수를 얻게 된다. 본 논문에서 사용한 데이터 셋의 N-GRAM 색인화 결과로 최소 5,000 여 개에서 최대 58,000 여 개의 특징을 도출하였다. 따라서 최종의 데이터 셋을 도출하고, 분류하는데 많은 시간과 비용이 소비된다.
본 논문에서 제안한 제목에 대한 N-GRAM 색인화의 결과로 매우 많은 개수의 특징 변수를 얻게 된다. 본 논문에서 사용한 데이터 셋의 N-GRAM 색인화 결과로 최소 5,000 여 개에서 최대 58,000 여 개의 특징을 도출하였다.
서로 다른 성격을 가지는 분류기에 대해 미치는 영향을 알아보기 위해 베이지안 분류기와 SVM 분류기에 대해 실험하였다. 실험 결과로 베이지안 분류기에 대한 결과로 N이 최소일 때 분류율이 가장 높게 나타났다. 그러나 스팸 메일에서 치명적으로 작용할 수 있는 요소인 FP가 분류율이 최고일 때, FP도 최소로 나타나지는 않았다.
후속연구
따라서 최종의 데이터 셋을 도출하고, 분류하는데 많은 시간과 비용이 소비된다. 향후에는 NGRAM의 색인화 결과로 얻어지는 특징 변수를 최소화 하면서 분류율을 최대화 할 수 있는 방안에 대한 연구가 필요하다.
질의응답
핵심어
질문
논문에서 추출한 답변
Support Vector Machine은 어떤 특징을 갖는가?
Support Vector Machine(SVM)은 패턴을 고차원 특징 공간으로 사상시킬 수 있다는 점과 대역적으로 최적의 식별이 가능한 특징을 가진다. SVM은 각 클래스를 구분하는 최적 분리 경계면을 구하기 위해 분리 경계면과 가장 분리 경계면에 인접한 점(Support Vector)과의 거리를 최대화한다[8].
Levenshtein distance는 무엇인가?
Levenshtein distance는 edit distance라고도 하는데, 서로 다른 두 시퀀스 사이에 차이를 측정하는 척도이다. 특히 두 문자열 사이의 유사도를 측정하는 척도로 이용되며, 검색 엔진 및 입력된 단어 정정 방법 등에서 단어사이의 유사도를 계산하는 척도로 사용된다[7]. Levenshtein Distance는 하나의 문자열이 또 다른 문자열로 변환되는 과정을 생각할 때, 이루어 질 수 있는 연산은 삽입, 수정, 삭제 등이 있다.
Support Vector Machine은 각 클래스를 구분하는 최적 분리 경계면을 구하기 위해 어떤 거리를 최대화 하는가?
Support Vector Machine(SVM)은 패턴을 고차원 특징 공간으로 사상시킬 수 있다는 점과 대역적으로 최적의 식별이 가능한 특징을 가진다. SVM은 각 클래스를 구분하는 최적 분리 경계면을 구하기 위해 분리 경계면과 가장 분리 경계면에 인접한 점(Support Vector)과의 거리를 최대화한다[8]. 이때 최적의 분리 경계면을 f(x) = wTx + b = 0로 놓으면, Support Vector와 f(x)의 거리를 #로 나타낼 수 있다.
참고문헌 (18)
A. Bratko, "FIGHTING SPAM WITH DATA COMPRESSION MODELS", Virus bulletin, http://www.virusbtn.com, pp. s1-s4, Mar 2006
G. V. Cormark, "Email Spam Filtering: A Systematic Review", Foundations and Trends in Information Retrieval, 1(4), pp. 335-455, 2008
H. Lee, A.Y. Ng, "Spam deobfuscation using a Hidden Markov Model", Proceedings of the Second Conference on Email and Anti-Spam (CEAS05), July 2005
I. Cid, L. R. Janerio, J. R. Mendez, D. Glez- Pena, F. Fdez-Riverola, "The Impact of Noise in Spam Filtering: A Case Study", Advances in Data Mining. Medical Applications, E- Commerece, Marketing, and Theoretical Aspects, 8th Industrial Conference (ICDM 2008), Springer-verleg, LNCS 5077, pp. 228-241, 2008
S. Cucerzan, E. Brill, "Spelling correction as an iterative process that exploits the collective knowledge of web users", In Proceedings of Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 293-300, 2004
V. Freschi, A. Seraghiti, A. Boliolo, "Filtering Obfuscated Email Spam by means of Phonetic String Matching", 28th European Conference on IR Research (ECIR 2006), Springer-verleg, LNCS 3936, pp. 505-509, 2006
V. I. Levenshtein, "Binary codes capable of correcting deletions, insertions, and reversals.", Soviet Physics Doklady, 10(8), pp. 707-710, 1966
S. Theodoridis, K. Koutroumbas, Pattern recognition 3/E, Academic press, pp. 13-116, 2006
V. Kumar, M. Steinbach, P. N. Tan, Introduction to Data Mining, Addison-Wesley, 2005
R. O. Duda, D. G. Stork, P. E. Hart, Pattern Classification 2/E, Wiley-Interscience, 2000
I. H. Witten, E. Frank, Data Mining: Practical machine learning tools and techniques 2/E, Morgan Kaufmann, 2005
한학용, 패턴인식 개론: MATLAB 실습을 통한 입체적 학습, 한빛미디어, 2005
김현준, 정재은, 조근식, "가중치가 부여된 베이지안 분류자를 이용한 스팸 메일 필터링 시스템", 한국정보과학회논문지 : 소프트웨어 및 응용, 31(8), pp. 1092-1100, 2004
강승식, "메일 주소 유효성과 제목-내용 가중치 기법에 의한 스팸 메일 필터링", 한국멀티미디어학회논문지, 9(2), pp. 255-263, 2006
※ AI-Helper는 부적절한 답변을 할 수 있습니다.