집단지성을 이용한 스팸 문서 필터 만들기 Part 2: 스팸 필터 개선하기

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

전처리 작업

스팸 필터를 만드는 것도 중요하지만 데이터를 가지고 하는 작업에서는 데이터 정제가 필수다. 그래서 많은 데이터 마이닝 책에서 데이터를 정제하는 전처리(preprocessing) 작업을 가장 처음에 넣는다. 또한 그 데이터 전처리 작업이 마이닝 작업에서 60% 이상의 리소스를 차지한다고 언급하고 있다(참고: introduction to data mining). 먼저 전처리 작업에 대해 알아보자. 대표적인 전처리 작업들은 아래와 같다.

일단 1회 연재에서 띄어쓰기 단위로 낱말을 추출해 그것들을 소문자로 통일하는 작업을 했는데 이렇게 함으로써 ‘BOY’와 ‘boy’를 같은 낱말로 처리해 카운팅할 수 있었다. 아래 프로시저에서 사전 입력 전에 string-downcase 프로시저로 매핑한 부분을 볼 수 있을 것이다.

                
;라인으로 들어온 낱말을 파싱하고 사전에 집어 넣는 모듈 
  (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)   
              )
            )
        )
    )

불용어 제거 작업은 필자가 임의로 제작한 243건의 불용어 사전을 활용해 필터링해 보겠다. 예를 들어 ‘the’나 ‘a’ 같은 거의 대부분의 문서에서 빈번하게 출현하는 낱말을 필터링하는데, 이런 낱말들은 판정에 쓸데없는 노이즈를 강력하게 일으킬 수 있기 때문이다(별로 중요하지 않은 낱말임에도 불구하고 말이다).

소스 파일에 포함된 load-stop-word-file 프로시저는 지정된 ifile을 읽어 들여 StopWordDic이라는 List 전역변수에 저장하는 로직이다(물론 낱말 개수가 많다면 다른 자료구조를 사용해 효율성을 높일 수 있겠지만 간단하게 구현하기 위해 List를 사용했다).

위 불용어 사전을 통한 필터링 작업을 위해 1회에 만들어 둔 makeDic 프로시저를 아래와 같이 고쳐 보겠다(볼드체 부분이 바뀐 부분이다).

                
;각각 키워드 스팸 낱말 사전을 만드는 함수 
  (define (makeDic keywordlist Dic)
    (let ((keylist '()))
      (begin
        ;(set! keylist (delete-duplicates keywordlist)) 
        ;dedup and stopword process
        (set! keylist (remove stop-word? (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 ) 
        )
      )
    )

사용된 불용어 낱말 사전은 제공되는 예제 파일의 ‘english/spam.stopword’ 경로에 존재한다(한글 불용어도 몇 개 있는데 무시해도 좋다).

위에서 쓰인 stop-word? 프로시저는 아래와 같다. 함수 안에 isstopword? 프로시저를 재정의해 꼬리 재귀(tail-recursion)를 사용해 구현했다.

                
;delete term in stop-word dic
(define (stop-word? term)
  (define (isstopword? term dic)
    (if (null? dic)
        #f
        (if (equal? term (car dic))
            #t 
            (isstopword? term (cdr dic))
            )
        )
    )
  
  (isstopword? term StopWordDic)
  )

숫자 필터링은 하나의 낱말이 숫자로만 이루어졌을 경우 제거하겠다. 코드는 위의 makeDic 프로시저에서 볼드체로 되어 있는 부분을 아래와 같이 바꾸면 된다.

                
(set! keylist (remove string->number (remove stop-word? (delete-duplicates keywordlist))))

스테머는 주로 어근과 어미가 있을 때 어근을 추출하는 작업을 한다. 예를 들어 ‘fishing’, ‘fished’, ‘fish’, ‘fisher’가 입력되면 동일 어근인 ‘fish’를 추출할 수 있다.

스테밍 작업은 현재 영문으로 작업하기 때문에 영문 스테머를 사용해야 한다. 그리고 만일 한글이라면 한글 색인어 추출기를 사용해야 하는데 마땅히 공개된 추출기가 없기 때문에 국민대학교 강승식 교수의 형태소 분석기를 추천한다. 분석기를 사용해 특정 품사를 추출하는 식으로 분석 대상을 한정하면 될 것이다. 아무래도 명사 정도가 스팸 처리에서는 가장 의미 있는 품사이지 않을까 한다.

영문 스테머는 여러 종류가 있다. 대표적으로 가장 오래되었고 가장 많이 쓰였던 Porter Stemmer가 있고 최근에 나온 가장 어그레시브한 스테머로 알려진 Lovins Stemmer가 있는데 룰 개수로 따지면 Porter Stemmer에 37개 룰이 적용되어 있고 Lovins Stemmer에는 294개 룰이 존재한다. 아무래도 룰이 많은 스테머가 정확도가 높지 않을까 생각한다.

두 개의 스테머는 스킴(scheme)으로 구현된 것이 없다. 하지만 굳이 하자면 C로 구현된 스테머를 스킴용으로 래핑해 사용하는 방법이 있겠지만 이 부분은 이번 연재의 의도에 벋어나는 분야라 생략하겠다.

마지막으로 의미가 같지만 형태가 다른 낱말들을 확인하기 위해 시소러스 사전이라는 게 필요한데, 이 작업을 함으로써 효과적인 낱말 추출 작업을 할 수 있다. 이 작업에서는 사전의 완성도가 가장 큰 변수다. 다만 공개된 시소러스 사전이 없고, 만들기도 힘들기 때문에 이 부분 역시 더 정밀한 작업을 원하는 독자들을 위해 남겨두겠다.

위로

베이지언 룰 보강하기

앞서 베이지언 룰에서는 스팸을 판단하는 데 수집된 낱말 세트를 이용해 전적으로 확률 정보만을 사용해 확률을 결정했다. 매우 효과적으로 보이고 논리적으로 보이지만 이것에도 약점은 있다. 바로 드물게 나오는 낱말들에 대해 압도적으로 적거나 많은 확률을 부여한다는 것이다. 예를 들어 ‘scheme’이라는 낱말이 스팸에서 단 한번 나와서 100%의 스팸 확률을 부여 받을 때 이는 별다른 설득력이 없음을 독자들은 알 수 있을 것이다. 사람들은 ‘scheme’이라는 낱말이 스팸성이 적다고 일반적으로 인식하고 있으니 실제 사람이 판단할 때에는 큰 문제가 없지만 우리가 구현한 베이지언 필터에서는 큰 약점이 된다.
따라서 이런 문제를 해결하기 위해 Robinson은 초기 확률값과 신뢰도(degree of belief)값을 이용해 드물게 나오는 낱말에 대해 확률 보정을 하게 했다.

위 식은 N 값에 대해 임계치를 두고 적용을 하는 방법을 추천한다. 이 연재에서는 편의상 "N / TotalDocNumber < 0.1"일 때 적용하겠다.

                
;degree of belif calculation by robinson
;f(w) = ((s * x) + (n * p(w))/(s + n)
  (define (calc-degree-of-belif result)
    (let* ((keyword (car result)) (proba (cdr result)) 
                                 (n (getN keyword)))
      (if (> 0.1 (/ n (+ Hamcnt Spamcnt))) ;"(N / TotalDocNumber) < 0.1" 일때
          (set! proba (/ 
                   (+ 
                    (* initial-belif initial-proba) 
                    (* n proba )
                    )
                   (+ initial-belif n)
                   )
            )
          )
      (printf "keyword : ~a :score : ~a.\n" keyword proba)
      (cons keyword proba)
      )
    )

Fisher의 역 카이제곱 방법은 Robinsson이 스팸에 대해 리서치하는 과정에서 발견된 방법이다. 알고리즘의 이름은 Fisher가 개별 확률을 결합하는 과정에서 카이제곱(chi-square) 방법을 사용한 데서 기인하며 불확실성에 대한 민감도를 적용한 결과를 보여준다.

베이지언 룰이 굉장히 극단적인(extreme) 값의 결과를 가지고 스팸성을 판단하는데(예: 90% 이상만 스팸으로) 카이제곱 분포를 이용해 우연성에 대한 고려를 함으로써 순화된(?) 값들을 던져 준다. 따라서 이 값을 이용해 심지어는 판정 불능 영역(gray area)을 뽑아내는 작업도 할 수 있다.

식을 가만히 관찰해 보면 0~1 사이의 확률값이 곱해질수록 작아지며 그것의 log 값은 음수 영역 방향으로 급감한다. 거기에다가 -2를 곱해주면 양수로 엄청나게 큰 값이 나온다. 그런 값이 C-1함수에 입력되며 또한 degree-of-freedom 값으로 2N이 인자로 들어가는데, 이는 단순히 곱에 의해 확률 결합식 결과가 작아지는 것을 방지하기 위해서이며 이에 따라 단순히 여러 확률값의 곱에 의해 0으로 수렴한 결과보다 적은 개수의 확률식이 결합해 나오는 결과에 대해 더 많은 신뢰도를 부여하게 되어 더 납득 가능한 확률 결과값을 도출하게 된다.

또 한 가지 베이지언과 다른 점을 이야기하자면 우리가 첫 회에서 스팸 스코어에 따라 정렬한 결과를 가지고 상위 N개를 추출해 판정에 사용했지만 여기서는 스코어가 0~0.1 그리고 0.9~1 사이의 점수를 가지는 텀을 추출해 알고리즘을 적용하게 된다.

N: 판단 대상이 되는 낱말의 총 개수
F1F2…Fn: 낱말 확률들의 곱
H: C-1(-2ln(F1F2…Fn), 2N)
S: C-1(-2ln((1.0 – F1)(1.0 – F2)…(1.0 - Fn)), 2N)

그리고 역 카이제곱 함수의 결과로 도출된 값은 본질적으로 스팸에 큰 영향을 미치는 낱말들의 확률을 1에 가까운 값으로 계산하는 것이 아니고, 햄에 큰 영향을 미치는 낱말들의 확률 결합을 0에 가깝게 만들기 때문에 아래와 같은 식을 가지고 또 다른 척도를 구하는 S를 Robinson이 제안했다. 위 두 가지 식을 사용해 새로운 척도 I를 구할 수 있게 된다.

I = (1 + H - S)/2

여기서는 I 값의 판정 범위를 아래와 같이 정하겠다.

여기서 나온 C-1의 역 카이제곱 함수의 수식은 초기에 SpamBayes를 만든 Tim Peters라는 사람에 의해 간단한 함수 하나로 구현되었고 그 후 많은 언어로 구현되었다. 그에 의해 만들어진 함수를 간단하게 스킴으로 구현해 봤다.

                
;inverse chi-square function
  (define (chi2Q chi df) 
    (let* ((m (/ chi 2.0)) (sum (exp (- m))) (term sum))
      (begin
        (let loop ((i 1)) 
          (if (< i (/ df 2))
              (begin 
                (set! term (* term (/ m i)))
                (set! sum (+ sum term))
                (loop (+ i 1))
                )
              )
          )
        (cond ((< sum 1.0) sum)
            (else 1.0)
            )
        )
      )
    )

Tip: 위 함수를 초기 Robinson이 파이썬으로 구현한 식은 아래 링크에서 찾을 수 있다.
http://www.linuxjournal.com/files/linuxjournal.com/linuxjournal/articles/064/6467/6467s2.html

그리고 위 함수를 이용한 I 결합식의 구현은 아래와 같다.

                
;fisher algorithm using chi2Q
;I = (1 + H - S)/2
  (define (fisher-combine-probability topTable)
    (let ((H 0) (S 0))
      (begin
        (set! H (chi2Q 
                 (* -2 (log (accumulate *  1 (map (lambda(x)(cdr x)) topTable)))) 
                 (* 2 (length topTable)))
              )
        (set! S (chi2Q 
                 (* -2 (log (accumulate *  1 (map (lambda(x)(- 1.0 (cdr x)))  topTable)))) 
                 (* 2 (length topTable)))
              )
        (/ (+ 1 (- H S)) 2)
        )
      )
    )

이제 역카이제곱 방법을 이용해 스팸, 햄, 판정 불능 영역으로 나누어 볼 수 있으며, 스팸의 정도와 햄의 정도를 좀 더 세밀하게 관찰할 수 있게 되었다. 또한 판정 불능 영역에 걸린 데이터를 분석하거나 사람이 직접 분류하는 작업을 거쳐 다시 스팸 필터로 학습을 시키는 과정을 반복함으로써 스팸 필터 강화에 큰 도움을 받게 되었다.

아래 함수가 전체적인 흐름을 나타내는 함수인데, 괄호를 따라가서 처음 처리되는 프로시저를 거꾸로 찾아보자

                
;input doc and calc spam score 
;use fisher inverse-chi-square
  (define (doc-spam-score inputDoc)
    (fisher-combine-probability
     (filter fisher-range? (make-keyword-score-pair-list (parsing-to-list inputDoc))) 
     )
    )

* parsing-to-list: 입력된 문서를 낱말 별로 파싱, 학습시와 마찬가지로 전처리를 수행하여 쓸만한 키워드 리스트를 리턴한다.
* make-keyword-score-pair-list: 그리고 기본적인 베이지언 룰과 희소 낱말에 대해 스코어를 계산해(keyword probability) 페어의 리스트를 리턴한다.
* filter fisher-range?: fisher-range?에서 참인 결과를 리턴하는 것들만 리스트로 넘긴다(위에서 0~0.1 그리고 0.9~1 사이의 점수를 가지는 텀을 추출해 알고리즘을 적용한다고 언급했다).
* 그리고 마지막으로 fisher-combine-probability 프로시저로 대상 확률 값들을 결합해 결합 확률을 도출한다.

이렇게 문서가 입력되었을 때 어떻게 스팸 확률을 도출하는지 확인해 봤다. 대부분 커다란 알고리즘의 얼개는 이와 같다. 그런 도출된 확률값을 기반으로 원하는 수준의 임계값으로 스팸을 판정하면 된다.

위로

그 다음 작업은?

이것으로 스팸 필터의 정확도 향상을 위해 해야 될 작업들을 몇 개 정리해 봤다. 그럼 스팸 필터가 좋아졌는지 나빠졌는지 알 수 있는 방법들이 필요한데, 이것을 위해 테스트 세트라는 실험 세트가 필요하다. 물론 어떤 독자는 우리가 가지고 있는 실험 세트를 적용해 보면 되지 않겠느냐 할 수도 있지만 이미 학습기에 들어간 데이터는 앞으로 우리가 맞닥뜨릴 새로운 스팸들에 대해 어느 정도 성능이 좋아졌는지 보여주지 못한다. 그래서 테스트 세트를 따로 돌려 나온 결과를 실제 판정 결과와 비교해 에러율 같은 척도를 사용, 이전 필터와 비교해 볼 수 있겠다.

테스트 세트 준비가 선행되어야 하는 것 말고도 필터의 목적에 맞는 판정 기준을 가지고 성능을 평가할 수 있는데, 스팸 필터의 경우 햄인 문서를 스팸으로 오판할 때 발생하는 비용이 스팸을 햄으로 오판할 때 비용보다 더 크기 때문에 필터의 목적에 따라 여러 다른 척도를 적용하기도 한다. 그러한 여러 가지 평가 방법을 확인하고 싶다면 필자의 블로그를 참고해 보길 바란다.

위로

마치며

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

2회에 걸친 스팸 문서 필터링 연재를 마치면서 되도록 실용적인 내용 위주로 하고 학술적인 내용을 최대한 배제하려고 노력했지만 그 노력의 결과가 잘 나타났는지 모르겠다. 하지만 예제로 만든 스팸 필터 소스는 아마 독자들이 기계학습 기반 스팸 처리에 대해 처음 시작할 때 참고하기 좋은 소스일거라는 건 자신 있게 이야기할 수 있다.

논문을 쓰면서 만든 소스보다 더 간결하고 깔끔하게 소스를 뽑았다고 생각하는데, 이것은 아마도 스킴 언어를 쓰면서 최대한 지저분하지 않고 명확하고, 간결하게 소스를 만들어 보려고 노력한 결과인 거 같다(아마도 스킴 언어의 특징을 살리려 많이 노력한 듯 하다).

베이지언을 응용한 스팸 필터는 굉장히 제너럴한 방법으로 쓰이고 있으며, 최근에는 SVM(support vector machine)이라는 기계학습 알고리즘을 응용한 방법이 유행하고 있다. 하지만 기계학습이라는 게 알고리즘도 중요하지만 어떠한 데이터를 입력하느냐가 알고리즘보다 더 중요하다고 생각한다. 잘 분류되고, 세밀하게 전처리된 데이터는 좋은 학습에 필수 불가결한 조건이자 기계학습을 이용한 애플리케이션 활용에서 가장 어려운 부분이다.

또한 학습기에 어떤 데이터를 넣어야 성능이 좋아질지 알아볼 수 있는 데이터를 보는 있는 혜안이 필요한데, 이는 많이 학습시켜 보고 수많은 데이터를 테스트해 보는 과정을 수없이 해보면서 키울 수 있는 능력이자 이런 학습 기반 소프트웨어 유지보수와 성능 향상에 가장 필요한 감각이라 생각한다.

본 연재에서 소개한 소스코드와 데이터는 필자의 블로그에서 받을 수 있다.

위로

참고 자료
*A Statistical Approach to the Spam Problem : http://www.linuxjournal.com/article/6467
*Ending Spam : http://books.google.co.kr/books?id=kqwn8KEKYOwC

필자 소개

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

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

developer CoD 신청양식 다운로드

[지난 Developer CoD 보기]