[논문]Okapi BM25 단어 가중치법 적용을 통한 문서 범주화의 성능 향상

이용훈; 이상범

doi:10.5762/kais.2010.11.12.5089

Okapi BM25 단어 가중치법 적용을 통한 문서 범주화의 성능 향상
A Research on Enhancement of Text Categorization Performance by using Okapi BM25 Word Weight Method 원문보기

한국산학기술학회논문지 = Journal of the Korea Academia-Industrial cooperation Society, v.11 no.12, 2010년, pp.5089 - 5096

초록
AI-Helper

문서 범주화는 정보검색 시스템의 중요한 기능중의 하나로 문서들을 어떤 기준에 의해 그룹화를 하는 것을 말한다. 범주화의 일반적인 방법은 대상 문서에서 중요한 단어들을 추출하고 가중치를 부여한 후에 분류 알고리즘에 따라 문서를 분류한다. 따라서 성능과 정확성은 분류 알고리즘에 의해 결정됨으로 알고리즘의 효율성이 중요하다. 본 논문에서는 단어 가중치 계산 방법을 개선하여 문서분류 성능을 향상시키는 것을 소개하였다. Okapi BM25 단어 가중치법은 일반적인 정보검색분야에서 사용되어 검색 결과에 좋은 결과를 보여주고 있다. 이를 적용하여 문서 범주화에서도 좋은 성능을 보이는지를 실험하였다. 비교한 단어 가중치법에는 가장 일반적인 TF-IDF법와 문서분류에 최적화된 가중치법 TF-ICF법, 그리고 문서요약에서 많이 사용되는 TF-ISF법을 이용하여 4가지 가중치법에 따라 결과를 측정하였다. 실험에 사용한 문서로는 Reuter-21578 문서를 사용하였으며 분류기 알고리즘으로는 Support Vector Machine(SVM)와 K-Nearest Neighbor(KNN)알고리즘을 사용하여 실험하였다. 사용된 가중치법 중 Okapi BM25 법이 가장 좋은 성능을 보였다.

Abstract ▼ AI-Helper

Text categorization is one of important features in information searching system which classifies documents according to some criteria. The general method of categorization performs the classification of the target documents by eliciting important index words and providing the weight on them. Therefore, the effectiveness of algorithm is so important since performance and correctness of text categorization totally depends on such algorithm. In this paper, an enhanced method for text categorization by improving word weighting technique is introduced. A method called Okapi BM25 has been proved its effectiveness from some information retrieval engines. We applied Okapi BM25 and showed its good performance in the categorization. Various other words weights methods are compared: TF-IDF, TF-ICF and TF-ISF. The target documents used for this experiment is Reuter-21578, and SVM and KNN algorithms are used. Finally, modified Okapi BM25 shows the most excellent performance.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 문서 범주화의 성능을 높이는 방법에 대해서 논하였다. 대부분의 문서 범주화의 연구는 자질축소 방법과 분류기 알고리즘의 특성에 따른 분류기 선택 문제로 연구되고 있다.
본 논문에서는 문서에서 자질의 가중치에 따른 문서 분류의 성능에 관하여 논의한다. Okapi BM25 단어 가중치법은 정보검색분야에서 사용되어 지는 가중치 법으로써 검색 결과에 좋은 성능을 보이는 방법이다.
대부분의 문서 범주화의 연구는 자질축소 방법과 분류기 알고리즘의 특성에 따른 분류기 선택 문제로 연구되고 있다. 본 논문에서는 범주화에 있어서 가장 근본적인 문제라고 할 수 있는 문서의 자질을 어떻게 더 잘 표현하는가에 대한 문제에 대하여 연구하였다. Okapi BM25 단어 가중치법은 정보검색분야에서 사용되며 검색 결과에 좋은 결과를 보이는 방법이며 문서 범주화에서도 더 나은 성능을 보이는지를 실험하였다.
본 논문은 [5]에서 연구한 단어 가중치법에 따른 범주화의 성능을 평가하는 방법과 유사하다 정보검색에서 질의어 가중치로 사용한 Okapi BM25법은 검색 결과에 좋은 성능을 보였으며 이 가중치법이 문서를 표현하는데 더 적합한 방법이라면 범주화 실험에서도 좋은 성능을 보일 것이라고 판단하여 실험해 보고자 하였다.
본 실험에서 분류 범주에 더 높은 가중치를 부여하는 법을 소개한 [5]논문의 TF-ICF 가중치법 보다. 정보검색에서 질의어에 가중치를 부여하는 Okapi BM25 가중치법이 더 좋은 성능을 보이는 것으로 나타났다.
학습문서에서만 추출된 단어의 수는 수십에서 수만까지 추출되어지며 많은 자질의 수는 분류과정에서 많은 시간비용을 요하게 된다. 자질선택을 통하여 단어 중에 중요한 내용어를 선택하여 자질의 개수를 줄이는 동시에 문서분류의 성능 저하 없이 분류 할 수 있는 방법이 자질 선택의 목적이다. 문서범주화에서 사용하는 유명한 자질 선택 방법은 카이제곱 통계량과 정보 획득량이 있다[3].

제안 방법

본 논문에서는 범주화에 있어서 가장 근본적인 문제라고 할 수 있는 문서의 자질을 어떻게 더 잘 표현하는가에 대한 문제에 대하여 연구하였다. Okapi BM25 단어 가중치법은 정보검색분야에서 사용되며 검색 결과에 좋은 결과를 보이는 방법이며 문서 범주화에서도 더 나은 성능을 보이는지를 실험하였다. 비교한 단어 가중치법에는 가장 일반적인 TF-IDF법와 문서분류에 최적화된 가중치법 TF-ICF법, 문서요약에서 많이 사용되는 TF-ISF법을 이용하여 4가지 가중치법에 따라 결과를 측정하였으며 Okapi BM25 법이 가장 좋은 성능을 보였다.
Okapi BM25와 같이 문서에서 중요한 단어를 찾는 법을 단어출현빈도와 역문헌빈도를 적절한 혼합한 방법과 파라미터를 설정함으로써 새로운 단어 가중치법이 적용되었다.
실험에서 사용한 파라미터로는 C값을 10으로 설정했으며 커널함수로는 가우시안 RBF 함수를 사용하였다. 먼저 학습문서 1000개의 대해서 학습을 시킨 후 테스터문서 500개 대해서 결과를 측정하였다.
본 논문에서 제안하는 정보검색분야에서 사용된 좋은 단어 가중치법을 문서 범주화에서도 적용하여 범주화 결과에 좋은 성능을 보이는지를 위한 방법으로 Okapi BM25법을 문서 범주화에서 적용해 보았다.
본 실험에서는 F-측정률을 가지고 실험 결과를 표현하였다.
이 가중치 법을 문서 범주화에 적용해 보고 더 나은 성능을 보이는 지를 실험하였다. 비교한 단어 가중치법에는 가장 일반적인 TF-IDF법와 문서분류에 최적화된 가중치법 TF-ICF 법, 문서요약에서 많이 사용되는 TF-ISF법을 이용하여 4가지 가중치법에 따라 결과를 측정하였다. 논문의 구성은 다음과 같다.
Okapi BM25 단어 가중치법은 정보검색분야에서 사용되어 지는 가중치 법으로써 검색 결과에 좋은 성능을 보이는 방법이다. 이 가중치 법을 문서 범주화에 적용해 보고 더 나은 성능을 보이는 지를 실험하였다. 비교한 단어 가중치법에는 가장 일반적인 TF-IDF법와 문서분류에 최적화된 가중치법 TF-ICF 법, 문서요약에서 많이 사용되는 TF-ISF법을 이용하여 4가지 가중치법에 따라 결과를 측정하였다.
자질선택의 개수에 따른 4가지 가중치법에 대한 실험 결과를 측정하였다.

대상 데이터

실험 문서로 사용한 Reuter-21578 말뭉치는 1987년 Reuter 뉴스 통신에서 사용했던 문서를 모아 놓은 것으로 범주화 실험에서 많이 사용되어지는 말뭉치이다[11]. Reuter-21578문서 중 가장 많은 문서를 포함하는 10개의 클래스를 선택했다. 표 1은 선택한 클래스 종류와 문서들의 개수를 나타내고 있다.
Reuter-21578문서에서 10개의 클래스를 선정 후 학습 문서 1000개와 테스트 문서 500개를 구성하였다. 자질선택 방법으로는 카이제곱 정보량을 사용하였으며 4가지 가중치법을 사용하였다.
각 클래스당 문서 수는 학습문서 100개, 테스트 문서 50개로 총 150개의 문서이며 500개의 클래스가 없는 문서를 추가하였다. 이는 잡음 데이터를 주기 위해서 추가하였다.
문서에서 불용어 목록표에 해당하는 단어들을 제거하며 제거 후에는 스테밍 처리를 한 후 최종적으로 단어들을 저장한다. 본 실험에서 전처리 과정 후 자질로 선정되는 단어의 수는 9331개로 추출되었다.
이는 잡음 데이터를 주기 위해서 추가하였다. 총 2000개의 문서에 대해서 실험하며 이중 500개가 테스트 문서로 사용되었다.

데이터처리

91 버전을 사용하였다[15]. 실험에서 사용한 파라미터로는 C값을 10으로 설정했으며 커널함수로는 가우시안 RBF 함수를 사용하였다. 먼저 학습문서 1000개의 대해서 학습을 시킨 후 테스터문서 500개 대해서 결과를 측정하였다.
Reuter-21578문서에서 10개의 클래스를 선정 후 학습 문서 1000개와 테스트 문서 500개를 구성하였다. 자질선택 방법으로는 카이제곱 정보량을 사용하였으며 4가지 가중치법을 사용하였다. 이후 KNN알고리즘과 SVM알고리즘을 이용하여 문서를 분류한 결과는 표 4와 표 5과 같다.

이론/모형

분류기를 이용한 분류 학습과 테스트는 KNN알고리즘과 SVM알고리즘을 이용하여 실험하였다. KNN알고리즘에서 k 값은 30으로 실험 결과를 측정하였으며 유사도 측정 방법으로는 코사인유사도를 사용하였다.
SVM 분류기는 타이완국립대학에서 개발한 LIBSVM 2.91 버전을 사용하였다[15]. 실험에서 사용한 파라미터로는 C값을 10으로 설정했으며 커널함수로는 가우시안 RBF 함수를 사용하였다.
본 실험에서 자질선택 방법은 카이제곱 정보량을 사용하여 실험하였다. 계산된 정보량 후 실험에서 사용될 단어들을 고르는 방법으로는 식(12)을 사용 하였다.
자질축소 과정이 끝나면 단어들을 가중치를 부여하는 과정을 거치게 된다. 본 실험에서는 TF-IDF, TF-ICF, TF-ISF 그리고 Okapi BM25 가중치법을 4가지를 사용하였다. 여기서 Okapi BM25 가중치의 파라미터 값으로 k 파라미터에 2를 설정하였으며 b 파라미터에는 0.
분류기를 이용한 분류 학습과 테스트는 KNN알고리즘과 SVM알고리즘을 이용하여 실험하였다. KNN알고리즘에서 k 값은 30으로 실험 결과를 측정하였으며 유사도 측정 방법으로는 코사인유사도를 사용하였다.
영어의 경우 'computing', 'computed', 'computational' 또는 'computer'와 같이 하나의 어원에서 여러 가지 어미에 따라 품사가 달라지는 단어들이 존재한다. 이러한 단어들의 어원을 복구하는 작업을 스테밍 처리라 하며 본 실험에서는 Porter Stemmer 알고리즘이 있다[13]. 표 3은 불용어 목록표이다.

성능/효과

표 5은 비교적 분류 결과가 비슷하게 나왔으나 근소한 차이로 Okapi BM25가중치 값이 가장 좋은 성능을 보이는 보였다. KNN알고리즘을 이용하고 자질선택의 개수가 250, 500개 일 때 Okapi BM25의 가중치법이 0.90을 나타내며 실험 과정에서 가장 좋은 분류 결과를 보였다.
TF-ICF법은 TF-IDF법를 변형한 방법으로 역문헌빈도수를 역범주빈도치로 계산하여 범주화 성능을 개선한 것이라면 본 연구는 포아송 모델-2를 기반으로 한 확률모델을 적용한 Okapi BM25 방법이 범주화에 적용한 것이며 기존 연구보다 좋은 성능을 나타냈다.
전체적인 실험 결과의 성능은 Okapi BM25, TF-ICF, TF-IDF, TF-ISF순으로 이어진다. 가장 성능이 낮게 나온 TF-ISF 가중치법은 외부영향이 아닌 한문서의 내부적영향만을 가중치법으로 사용하기에 문서 분류를 위한 가중치법으로 적합하지 않으며 가장 낮은 성능 결과가 나타났다.
Okapi BM25 단어 가중치법은 정보검색분야에서 사용되며 검색 결과에 좋은 결과를 보이는 방법이며 문서 범주화에서도 더 나은 성능을 보이는지를 실험하였다. 비교한 단어 가중치법에는 가장 일반적인 TF-IDF법와 문서분류에 최적화된 가중치법 TF-ICF법, 문서요약에서 많이 사용되는 TF-ISF법을 이용하여 4가지 가중치법에 따라 결과를 측정하였으며 Okapi BM25 법이 가장 좋은 성능을 보였다.
전체적인 실험 결과의 성능은 Okapi BM25, TF-ICF, TF-IDF, TF-ISF순으로 이어진다. 가장 성능이 낮게 나온 TF-ISF 가중치법은 외부영향이 아닌 한문서의 내부적영향만을 가중치법으로 사용하기에 문서 분류를 위한 가중치법으로 적합하지 않으며 가장 낮은 성능 결과가 나타났다.
본 실험에서 분류 범주에 더 높은 가중치를 부여하는 법을 소개한 [5]논문의 TF-ICF 가중치법 보다. 정보검색에서 질의어에 가중치를 부여하는 Okapi BM25 가중치법이 더 좋은 성능을 보이는 것으로 나타났다.
표 5은 비교적 분류 결과가 비슷하게 나왔으나 근소한 차이로 Okapi BM25가중치 값이 가장 좋은 성능을 보이는 보였다. KNN알고리즘을 이용하고 자질선택의 개수가 250, 500개 일 때 Okapi BM25의 가중치법이 0.

후속연구

앞으로의 향후 과제로는 4가지 단어 가중치법을 이용하여 많은 다른 분류기에 적용해 보는 실험을 통해서 실험 결과의 정당성을 높여야 할 것이며 또한 많은 데이터 문서를 사용해서 증명하는 것도 필요할 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	자질선택이란 무엇인가?	자질선택이란 문서 분류 과정에서 자질의 개수를 축소하여 분류과정에서 발생하는 계산량을 줄이기 위한 방법이다. 학습문서에서만 추출된 단어의 수는 수십에서 수만까지 추출되어지며 많은 자질의 수는 분류과정에서 많은 시간비용을 요하게 된다.
	역범주 빈도 가중치법은 소수의 범주에 나온 자질과, 여러 범주에 고르게 나오는 자질에 대해 어떻게 가중치를 주는가?	역범주 빈도 가중치법은 문서 간의 분리도가 높은 자질에 더 높은 가중치를 부여하는 방법이다. 즉 소수의 범주에 많이 나온 자질에 대해서는 더 높은 가중치를 주고, 여러 범주에 고르게 나오는 자질에 대해서는 낮은 가중치를 주는 방법이다[5]. 가중치 값은 단어빈도수(TF)와 역범주 빈도수(ICF)를 곱한 값으로 표현되며 ICF값은 아래의 식과 같다.
	일반적으로 자동화 문서 범주화는 학습 문서로부터 무엇을 먼저 추출하는가?	일반적으로 자동화 문서 범주화는 학습 문서로부터 자질을 먼저 추출하고 추출된 자질에 따라 범주화에 대한 정보가 분류기 알고리즘에 의해 학습된다. 학습된 정보를 토대로 테스트 문서에 대한 범주가 결정된다.

참고문헌 (16)

Sebastiani. "Machine learning in automated text categorization." Techinical report, Consigilo Nazionale delle Rieche, Italy. 1999.
T.Mitchell. "Machine Learning." MCGraw Hill, NY, US, 1996.
Yang, Y. and J. O. Pderson. "A comparative study on feature selection in text categorization." Proceedings of the 14th International Conference on Machine Learning. 1997.
Gerard Salton and Michael J. McGill. "Introduction to Modern Information Retrieval." McGraw-Hill Book Company, New York, 1983.
조광제, 김준태. "역카테고리 빈도에 의한 계층적 분류체계에서의 문서의 자동분류." 한국정보과학회 봄학술발표논문집(B), 507-510. 1997.
Larocca Neto, Joel. "A Text Mining Tool for Document Clustering and Text Summarization.", Proceedings of The Text Mining Tool for Document Clustering and Text Summarization Fourth International Conference on The Practical Application of Knowledge Discovery and Data Mining, 41-56.Manchester, UK. Apr, 2000.
Osuna, E., Freund R., and Girosi, F. "Training support vector machines: An application to face detection", Proceedings of Compuer Vision and Pattern Recognition, pp. 130-136, 1997.
Dasarathy, Belur V. "Nearest Neighbor(NN) Norms: NN Pattern Classificatioin Techniques." McGraw-Hill Computer Science Series, CA: IEEE Computer Society Press. 1991.
리청화, "BPNN의 효율적인 개선방법 및 개념에 기초한 문서분류 시스템 응용" 전북대학교 대학원 박사논문. 2009
정은경, "문서 범주화 효율성 제고를 위한 정보원평가에 관한 연구 ", 한국정보관리학회, 제24권, 제4호, pp. 305-321, 12월, 2007.
David D. Lewis. "Distribution 1.0 readme file (v1.2) for reuters-21578", AT&T Labs - Research, 1997.
GSalton, "Automatic Information Organization and Retrieval." New York:McGraw-Hill, 1968.
M. F. Porter. "An algorithm for suffix stripping." Program, Vol. 14 no.3 130-137. 1980.

상세보기
Stephen E. Robertson, Steve Walker, Susan Jones, Micheline Hancock-Beaulieu, and Mike Gatford. (1994) "Okapi at TREC-3". In Proceedings of the Third Text REtrieval Conference (TREC 1994).
Chin-Chung Chang and Chih-Jen Lin, LIBSVM: a library for SVM, URL : http://www.csie.ntu.edu.tw/-cjlin/libsvm
D.D.Lewis, "Evaluating text categorization", in Proceedings of the Speech and Natural Language Workshop, 1991.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증