연관규칙 성능부양에 기반한 대용량 문서 분류

Abstract

연관규칙을 이용한 분류에서, 많은 단어를 가진 규칙은 단어패턴과 범주 사이의연관을 보다 정확하게 표현할수 있다. 그러나, 생성되는 다단어 규칙의 수가지수적으로 증가하기 때문에 다단어 규칙을 추출하는 작업은 매우 많은 시간을필요로 한다. 따라서, 과거 연구에서 대부분의 연관 분류기는 규칙에 들어가는단어수를 줄임으로써 생성되는 규칙의 수를 줄여 왔고, 테스트 문서들을 분류하는최종 분류기에 보다 적은 수의 고신뢰도 규칙들을 포함시켜 왔다.우리는 분류기의 학습에 있어서 다른 접근방법을 제안하는데, 적어도 임의선택보다는 정확도가 뛰어난 저신뢰도 규칙들을 될수 있으면 많이 포함시키는것이다. 우리가 새로이 고안한 성능부양 알고리듬을 적용하여, 많은 수의 초기생성된 규칙들로부터 적은 수의 규칙들을 선별하여서 최종 분류기를 구성한다.그렇게 생성된 최종 분류기는 학습 에러및 일반화 에러에 있어 매우 향상된 성능을보여준다.분류기의 성능을 극대화하기 위해, 우리의 방법은 최소 지지도와 최소 신뢰도 문턱을낮춤으로써 아주 많은 수의 연관 규칙을 캐내는데, 이는 시험 문서들에 대한처리도를 향상시킨다. 우리는 또한 규칙 추출과 성능부양 과정에 있어서 계산효율성을 증진시키는 두개의 새로운 알고리듬을 제안한다. 잘 알려진 성능평가용데이타와 대용량 문서집합을 가지고 철저한 실험을 통해, 우리의 방법론은 계산효율성뿐 아니라 분류 정확도에 있어서 뛰어난 성과를 나타낸다.

In the associative classification, high-order rules can represent more exactly the association between pattern and class label. But mining high-order rules is very time consuming because the number of generated rules grows exponentially. Thus, most of associative classifiers in the previous studies have decreased the number of generated rules by reducing the number of features or lowering the order of rules, and have selected a small number of high-confidence rules for the final hypotheses for test instances. We propose an alternative approach in which the training of the classifier starts with as many rules as possible including those which have low confidence values but are better than random guessing. Controlled by our new boosting algorithm, a smaller number of rules are selected from that large number of generated rules and make up a final classifier. The resulting final classifier shows a greatly improved performance for both the training error and the generalization error. To maximize the classifier performance, our approach mines a huge number of association rules by lowering the minimum support and the minimum confidence thresholds, which helps to raise the coverage for test instances. We also propose two new algorithms to enhance the computational efficiency during the processes of rule generation and boosting. By conducting thorough experiments using well-known benchmark databases and large-scale text corpora, our method achieves outstanding classification accuracy and computational efficiency as well.