집단지성을 이용한 스팸 문서 필터 만들기 Part 1: 베이지언 룰을 이용한 스팸 필터 구현

연재순서
1회(2008년 1월): 베이지언(Bayesian) 룰을 이용한 스팸 필터 구현
2회: 스팸 필터 개선하기

집단지성이란?

최근 집단지성(collective intelligence)이라는 거창한 말로 웹을 설명하는 사람이 많아졌다. 이는 개인이 차세대 웹에서 중요한 의미로 대두되고 자신의 활동 여하에 따라 자신을 웹에 부각할 수 있는 미디어의 다양화에 따른 것이다.
그럼 그렇게 부각되는 집단지성의 정확한 의미는 무엇일까? 이는 많은 개개인으로부터 협동과 경쟁에 의해 생성되는 지능(intelligence)이라고 위키백과에 정의되어 있다. 이 개념을 실체화하기 위해 인공지능(artificial intelligence), 기계학습(machine learning)이라는 학문 분야에서 이미 수십 년간 연구를 하고 있다.
실제 위키백과나 구글은 이런 집단지성의 힘으로 인해 각자의 사업 영역에서 가장 큰 성공을 거두었다. 위키백과는 사전을 공개해 많은 사람의 지성을 흡수할 수 있게끔 만들어 세상에서 가장 정확하고 풍부한 사전 데이터를 포함하고 있고, 구글은 사람들이 링크를 많이 건 문서를 좋은 문서로 검색 상위에 올라가게끔 함으로써 최상의 검색 품질을 만들어 최근 가장 성공한 기업으로 미디어의 주목을 받고 있다.

스팸 문서 필터링

룰 베이스 스팸 문서 필터링의 문제점

룰 베이스(rule-based) 문서 필터링은 한 사람이 스팸에 나올 만한 경우에 대해 정리하고 이것을 어떠한 룰로 정하면서 시작된다.
이런 작업을 사람이 하는 건 ‘혼을 빨아먹는(soul sucking)’ 작업이라는 표현으로 이야기할 정도로 스팸 세계는 복잡하다. 또한 이것의 큰 단점 한 가지는 스팸의 정도를 가늠하기 힘들다는 것이다(단지 True와 False의 문제이기 때문이다). 예를 들어 “특정 문서의 모든 문자가 대문자로 강조되어 나오기 때문에 스팸이다”라는 규칙을 만들었는데 만약 특별히 대문자로 강조해 정상 문서를 만들었을 경우 잘못 판단하게 될 것이다. 또한 이런 간단한 룰은 굉장히 명백해 스패머가 간단하게 우회할 수 있다.
그리고 요즘 스팸 경향을 보면 복합적인 스팸 성향들을 효과적으로 결합해 필터를 구성해야 하는 필요성이 대두될 정도로 스팸이 나날이 교활해지고 있다. 이런 복잡한 작업을 일일이 할 정도로 우리 개발자들의 시간이 넉넉하지 않다는 게 문제다.
일단 룰 베이스 필터를 설명해보겠다. 단적인 예를 들면 ‘sex’라는 낱말이 들어있는 문서를 스팸이라고 한다면 아래와 같은 모조(pseudo) 코드가 들어갈 것이다.

  

if “sex” in doc
    return SPAM
 

그런데 ‘sex’라는 낱말이 들어간 모든 문서가 스팸일 수는 없을 것이다. 예를 들어 ‘sex discriminate(성차별)’을 이야기하는 문서일 경우는 어떨까? 이런 문서의 경우 아래와 같은 코드로 예외 상황을 변경하게 될 것이다.

  

if “sex” in doc
    if “discriminate” in doc
        return HAM
    else 
return SPAM
 

스팸이 발달할수록 위와 같은 if else 코드나 데이터 추가가 기하급수적으로 늘어난다. 룰 베이스의 가장 어려운 부분은 저런 복합적인 스팸 속성들을 사람이 직접 뽑아야 한다는 사실과 시간이 갈수록 이해, 유지보수하기 힘든 코드로 진화(?)된다는 사실이다.

위로

집단지성을 이용한 스팸 필터링

위와 같은 스팸 필터링의 문제점을 인식해서 처음 나온 집단지성 알고리즘이 폴 그레이엄(Paul Graham)의 베이지언 스팸 필터 알고리즘이다. 폴 그레이엄은 2002년 룰 베이스 스팸 필터를 만들다가 이런 작업이 ‘혼을 빼놓는’ 일임을 깨닫고 스패머 입장에서 스팸을 어떻게 보내면 효율적으로 보낼 수 있을지를 고민했다.
이 알고리즘은 이것이 나오기 전의 룰 베이스 알고리즘과는 확연히 다른 방법으로 스팸을 필터링해 당시 획기적인 방법으로 각광을 받았다. 기존 접근 방법에서 탈피해 학습(learning)과 테스트(test)라는 과정을 거쳐 현 시점에 가장 적합한 스팸 필터를 만들 수 있었다. 게다가 처리 퍼포먼스도 상대적으로 좋다.
위의 룰 베이스 방법이 그저 스팸(Spam)인지 햄(Ham)인지를 판단하는 0과 1의 문제였다면, 학습을 통해 나오는 데이터는 “스팸일 확률이 과연 얼마인가?”에 대한 결과를 도출하여 나름대로 임계값을 정해 스팸 필터의 정확도를 튜닝할 수 있다는 장점이 있다(예. 90% 이상이면 스팸이다). 그럼 이런 결과를 얻기 위해 어떤 데이터를 얻어야 하나 생각해 보자.
먼저 룰 베이스 방법에서 문서의 스팸성을 판단하는 데 낱말이 가장 큰 영향을 미칠 것이라 생각할 수 있다. 그렇다면 학습 기반 방법에서도 판단 기준을 정할 수 있는 것으로 낱말을 생각할 수 있는데 문서가 낱말의 집합이니 문서의 스팸성을 판단하는 데 낱말의 스팸성을 먼저 가늠해 보자(물론 낱말 말고도 다른 여러 가지 속성을 선택할 수 있다).

위로

구현

학습 과정

가장 먼저 필요한 데이터는 특정 문서 집합을 스팸, 햄으로 분류한 문서 집합이다. 이런 데이터는 일반적으로 사람이 분류한 결과를 쓴다. 우리가 수만 건의 문서를 분류하기는 사실상 힘든 문제니 필자가 간단한 덧글 수준의 스팸 판정 데이터를 첨부하겠다. 그 문서 집합을 배경으로 아래와 같은 데이터를 뽑아 보자

사실 위 정보를 구하기 위한 과정이 학습 과정이다. 이 정보를 저장하기 위해 아래와 같은 전역 해시 테이블(hash table) 두 개와 변수 두 개를 정의한다(세미콜론(;)은 주석이다).

  

define HamDic (make-hash-table 'equal)) ;IH 
(define SpamDic (make-hash-table 'equal)) ;SH
(define Hamcnt  0) ;TI
(define Spamcnt 0) ;TS
 

이 전역변수를 이용해 아래와 같은 학습 모듈을 작성한다.

  

;Training module 
(define (Training trainingset)
  
  (define i (open-input-file trainingset))
  
  
  (define ERROR_CNT 0)

  (define re-white (pregexp "\\W+"))
  
  (define re-extract-doc-from-file (pregexp "<comment:(.+)><spam:(.+)>"))
  
  ;라인으로 들어온 낱말을 파싱하고 사전에 넣는 모듈 
  (define (parsingLine line)
    (if (boolean? line)
        (set! ERROR_CNT (+ 1 ERROR_CNT))
        (if (equal? (list-ref line 2) SPAM)
            (begin 
              (set! Spamcnt (+ Spamcnt 1))
              (makeDic (map string-downcase (pregexp-split re-white (car (cdr line)))) SpamDic)
              )
            (begin 
              (set! Hamcnt (+ Hamcnt 1))
              (makeDic (map string-downcase (pregexp-split re-white (car (cdr line)))) HamDic)   
              )
            )
        )
    )
  
  
  ;각각 키워드 스팸 낱말 사전을 만드는 함수 
  (define (makeDic keywordlist Dic)
    (let ((keylist '()))
      (begin
(set! keylist (delete-duplicates keywordlist))
        (for-each (lambda (i) (begin
                                (if (= -1 (hash-table-get Dic i -1))
                                   (hash-table-put! Dic i 1)
                                   (hash-table-put! Dic i (+ 1 (hash-table-get Dic i)))
                                   )
                               ) 
                    ) keylist ) 
        )
      )
    )
  
  ;파일을 라인별로 읽어 들이는 함수 
  (define (read-lines iport)
    (let loop ((i 0)(line (read-line iport))) 
      (if (eof-object? line)
          (close-input-port iport)
          (begin
            (parsingLine (pregexp-match re-extract-doc-from-file line)) ;t
            (loop (+ i 1) (read-line iport)) 
            )
          )
      )
    )
  
  (begin 
    (read-lines i)
    (printf "~nTotal HAM : ~a, Total SPAM : ~a, Total Doc : ~a SpamDic : ~a HamDic : ~a Error count : ~a.~n" 
            Hamcnt 
            Spamcnt 
            (+ Hamcnt Spamcnt)
            (hash-table-count SpamDic)
            (hash-table-count HamDic)
            ERROR_CNT
            )
    )
  )

 

코드는 복잡해 보이는데 아래 순서를 차근히 보면서 함수를 매칭해 보면 간단하다는 사실을 알 수 있다.

위로

스팸성 테스트

폴 그레이엄은 위 정보와 아래 같은 식으로 특정 낱말의 스팸 확률을 구했다(이 식이 어떻게 유도되는지 알고 싶으면 http://www.freesearch.pe.kr/732를 참고하길 바란다).

‘sex’라는 낱말의 스팸 스코어를 알고 싶다면 학습 과정에서 만든 위 네 개의 변수를 가지고 어떻게 해야 할까?

새로 입력되는 문서에 대해 파싱하고 위 과정을 거치면 문서 내 각 낱말의 스팸 스코어가 나올 것이다.
그럼 위에서 나온 스코어들의 리스트를 가지고 문서의 스코어를 구하려면 어떻게 해야 할까? 일단 아래와 같이 위의 스코어를 내림차순 정렬하여 term 스코어 테이블을 만들어야 한다. 예를 들어 “sex school cat ipod buy”라는 문서가 입력되었다고 하자.

문서 길이는 다 다를 것이니 이 중에서 스코어가 가장 높은 두 개의 텀만 뽑아 문서의 스팸 스코어를 계산하자. 낱말의 스팸 스코어들의 집합으로 문서의 스코어를 구하는 식은 아래와 같다.

따라서 위 테이블을 이용한 문서의 스팸 스코어는 아래와 같이 계산된다.

위 문서는 약 93%의 스팸성이 있다. 아래 코드는 스팸 키워드 하나를 입력 받아 위 (1)식을 이용, 낱말 하나의 스팸 확률을 구하는 식이다.

  

(define (calc-word-spam-score keyword)
    (let ((b 0) (g 0))
      (if (> threshHapaxes (+ (hash-table-get SpamDic keyword 0) (hash-table-get HamDic keyword 0)))
          (cons keyword valueHapaxes)
          (begin 
            (set! b (/ (hash-table-get SpamDic keyword 0) Spamcnt))
            (set! g (/ (hash-table-get HamDic keyword 0) Hamcnt)) 
            ;(printf "keyword : ~a :score : ~a.\n" keyword (/ b (+ b g)))
            (cons keyword (/ b (+ b g)))
            )
          )
      )
    )
 

위에서 보이는 valueHapaxes 변수는 키워드가 우리가 학습시킨 학습 세트에 없는 낱말이거나 거의 출현하지 않은 낱말일 경우 기본 확률 수치를 준다. 이 value가 없으면 어떤 해당 확률이 0이 되어버려 아래 확률곱을 할 때 0으로 나눠주는 상황이 발생한다. 일반적으로 0.4를 주는데, 이 값은 충분히 바꿀 수 있다. 또 아래 코드는 (2)번식을 구체화한 함수다.

  

(define (calc-combine-probability topTable)
    (let ((C 1)(B 1)) 
      (begin
       (set! C (apply * (map (lambda (x) (cdr x)) topTable)))
       (set! B (apply * (map (lambda (x) (- 1.0 (cdr x))) topTable)))
       (/ C (+ C B))
       )
      )
    )
 

위로

스팸 신고가 필요한 이유

이메일 클라이언트를 사용하다 보면 ‘스팸 신고’ 버튼이 있다. 최근 구글의 지메일에는 이 스팸 신고 버튼을 눌러 달라고 UCC로 호소를 할 정도로 이메일 클라이언트에서 이 기능은 효율적인 스팸 필터링에 중요한 부분이다.
그럼 스팸 신고 기능이 왜 그렇게 필요할까? 바로 스팸 필터를 학습시키는 데 필요하기 때문이다. 스팸 신고가 들어왔을 때 스팸 본문을 파싱해 필터링에 필요한 텀(우리가 위에서 추출한) 추출 및 메일 발송 주소 등 많은 스팸 정보를 뽑아 클라이언트가 가지고 있는 필터를 강화하는 학습을 시킨다. 그렇게 함으로써 비슷한 패턴의 스팸을 자동으로 걸러낼 수 있다.

위로

소셜 북마크
	mar.gar.in
	Digg
	del.icio.us
	Slashdot

다음 과제는 성능 개선

첨부한 소스파일은 DrScheme에서 바로 실행할 수 있다. 직접 돌려보고 데이터를 보면서 현재의 초보적인 스팸 필터에 어떤 문제가 있는지 확인해 보는 작업도 개인적으로 의미 있을 거라 생각한다. 실행을 위해 언어 설정을 아래와 같이 해주면 된다.

  

-	choose language/PLT/Textual (Mzscheme, include R5RS)
 

다음 회에는 이번 회에서 작성한 기본적인 필터를 기반으로 성능 개선을 위해 해야 할 몇몇 작업에 대해 소개해 보겠다.

위로

참고 자료

1. Ending Spam
2. SICP
3. 위키백과의 “Collective Intelligence” 해설
4. A plan for Spam

필자 소개

		전희원 gogamza@freesearch.pe.kr Yahoo! Korea에서 웹 검색을 담당하고 있다. 웹 검색을 하면서 검색 영역의 방대함을 깨달았고 특히 문서 분류 및 스팸 처리 등 마이닝 영역에 매우 관심이 많다. 검색, 마이닝 관련 블로그를 운영하고 있다.

developerWorks에 소개되었으면 하고 바라던 주제가 있으시거나, 관심 있는 기술에 대한 전문가의 지식과 견해가 궁금하시다면 Developer CoD 코너에 원하는 주제를 신청해주세요. 해당 분야 전문가를 필자로 섭외해, 여러분이 원하는 주제에 대한 맞춤형 컨텐츠를 제작해드립니다.

developer CoD 신청양식 다운로드

[지난 Developer CoD 보기]