요즘 Text Mining Handbook을 보고 있는데, 예전에 보지 못한 알고리즘이 나와서 한번 적어본다. 처음 보는 알고리즘인데, 이미 나온지 꽤 된 많은곳에 쓰이는 알고리즘 이란다. ^^;

특정 카테고리의 문서집합에서 빈도수가 높은 컨셉을 뽑아내는 알고리즘으로 support와 Confidence라는 개념으로 이루어져 있다.

support는 주어진 룰을 포함하는 문서의 빈도수를 의미하고, confidence는 그 룰이 참이라고 생각할 수 있는 휴리스틱한 threshold를 의미한다.
따라서 Apriori알고리즘은 각 패스에서 항목집합들의 후보 항목집합을 구성한 후에 각 후보 항목집합의 발생 빈도를 계산하고, 사용자가 정의한 min support를 기준으로 항목집합들을 다시 추리게 된다. 다음 단계에서는 이들 항목집합들로부터 원소수가 하나 더 많은 항목집합을 만들어서 위의 과정을 계속 진행하게 되는 것이다.

위의 복잡한 과정을 아주 쉽게 아래의 그림으로 표현을 한걸 첨부한다. 이해하는데 크게 어려움은 없을 거라 생각한다. (위 그림과 아래 그림은 어디서 주어온 문서파일에 있던건데 기억이 안난다.)

일반적으로 문서셋에서 frequence를 추출하기 위해 일반적인 term 단위로 추출하곤 하는데, 위와 같은 방법으로 하면 term이라는 최소 단위에서 벗어나 term 집합을 최소 단위로 해서 분석해 볼 수 있다.

일반적으로 covariance하는 단어들이 같이 추출될 듯 한데, 이런것을 이용하면 분류기 학습시  feature set을 줄여서 학습할 수 있는 어떤 문서 전처리 방법이 될 수도 있을거 같다.(이건 개인적인 생각이다. )

예를 들어 내가 논문에서 오류 분석한 파일을 보자면 아래와 같은 결과 term 리스트가 나온다.
이것은 comment spam의 False Negative  분석 파일이다. 그리니까 스팸을 햄으로 처리한 comment list를 분석한 파일이다.

아래에서 보면 term 단위로 밖에 볼 수가 없고, 두 텀간에 상호 co-occurrence 가 어떻게 일어나고 있는지 보기 힘든데, 위의 알고리즘으로 분석하면 http라는 텀과 www이라는 텀의 co-occurrence 카운트가 높아서 url feature라는걸  한눈에 볼 수 있는 결과가 나올것이다. 물론 단순하게 눈으로 볼 때 찾기 쉬운 url feature말고도 다른 흥미로운 분석 결과도 볼 수 있을것이다. 내가 분석한 분석기에는 www이나 http 같은 term을 stop word 처리를 했었는데 아예 comment 내에서 url 주소가 들어갔을 경우에 대한 feature를 추가 한다면 좀더 정확도가 높아 지지 않을까 한다.(역시나 Machine Learning 실험에서 오류 분석이 필요하다는걸 이부분에서 피부로 느낄 수 있다.)

저 알고리즘을 한번 구현해볼까도 한데,  논문에 쓰일 흥미로운 오류 분석 결과가 나오지 않을까 한다.

문서집합에서 문서 상호 빈도수가 높은 feature 셋을 뽑아내는 알고리즘 by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.