본 논문에서는 TextRank 알고리즘을 이용한 문서 범주화 방법에 대해 기술한다. TextRank 알고리즘은 그래프 기반의 순위화 알고리즘이다. 문서에서 나타나는 각각의 단어를 노드로, 단어들 사이의 동시출현성을 이용하여 간선을 만들면 문서로부터 그래프를 생성할 수 있다. TextRank 알고리즘을 이용하여 생성된 그래프로부터 중요도가 높은 단어를 선택하고, 그 단어와 인접한 단어를 묶어 하나의 자질로 사용하여 문서 분류를 수행하였다. 동시출현 자질(인접한 단어 쌍)은 단어 하나가 갖는 의미를 보다 명확하게 만들어주므로 문서 분류에 좋은 자질로 사용될 수 있을 것이라 가정하였다. 문서 분류기로는 지지 벡터 기계, 베이지언 분류기, 최대 엔트로피 모델, k-NN 분류기 등을 사용하였다. 20 Newsgroups 문서 집합을 사용한 실험에서 모든 분류기에서 제안된 방법을 사용했을 때, 문서 분류 성능이 향상된 결과를 확인할 수 있었다.
본 논문에서는 TextRank 알고리즘을 이용한 문서 범주화 방법에 대해 기술한다. TextRank 알고리즘은 그래프 기반의 순위화 알고리즘이다. 문서에서 나타나는 각각의 단어를 노드로, 단어들 사이의 동시출현성을 이용하여 간선을 만들면 문서로부터 그래프를 생성할 수 있다. TextRank 알고리즘을 이용하여 생성된 그래프로부터 중요도가 높은 단어를 선택하고, 그 단어와 인접한 단어를 묶어 하나의 자질로 사용하여 문서 분류를 수행하였다. 동시출현 자질(인접한 단어 쌍)은 단어 하나가 갖는 의미를 보다 명확하게 만들어주므로 문서 분류에 좋은 자질로 사용될 수 있을 것이라 가정하였다. 문서 분류기로는 지지 벡터 기계, 베이지언 분류기, 최대 엔트로피 모델, k-NN 분류기 등을 사용하였다. 20 Newsgroups 문서 집합을 사용한 실험에서 모든 분류기에서 제안된 방법을 사용했을 때, 문서 분류 성능이 향상된 결과를 확인할 수 있었다.
We describe a new method for text categorization using TextRank algorithm. Text categorization is a problem that over one pre-defined categories are assigned to a text document. TextRank algorithm is a graph-based ranking algorithm. If we consider that each word is a vertex, and co-occurrence of two...
We describe a new method for text categorization using TextRank algorithm. Text categorization is a problem that over one pre-defined categories are assigned to a text document. TextRank algorithm is a graph-based ranking algorithm. If we consider that each word is a vertex, and co-occurrence of two adjacent words is a edge, we can get a graph from a document. After that, we find important words using TextRank algorithm from the graph and make feature which are pairs of words which are each important word and a word adjacent to the important word. We use classifiers: SVM, Na$\ddot{i}$ve Bayesian classifier, Maximum Entropy Model, and k-NN classifier. We use non-cross-posted version of 20 Newsgroups data set. In consequence, we had an improved performance in whole classifiers, and the result tells that is a possibility of TextRank algorithm in text categorization.
We describe a new method for text categorization using TextRank algorithm. Text categorization is a problem that over one pre-defined categories are assigned to a text document. TextRank algorithm is a graph-based ranking algorithm. If we consider that each word is a vertex, and co-occurrence of two adjacent words is a edge, we can get a graph from a document. After that, we find important words using TextRank algorithm from the graph and make feature which are pairs of words which are each important word and a word adjacent to the important word. We use classifiers: SVM, Na$\ddot{i}$ve Bayesian classifier, Maximum Entropy Model, and k-NN classifier. We use non-cross-posted version of 20 Newsgroups data set. In consequence, we had an improved performance in whole classifiers, and the result tells that is a possibility of TextRank algorithm in text categorization.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
또한 영어 품사 태거 대신에 한국어 품사 태거를 적용하면 어렵지 않게 제안 시스템의 방법론을 한국어 문서 분류에 사용할 수 있다. 따라서 향후, 제안 시스템을 한국어 문서 분류에 적용해보고, 가능성을 알아보고자 한다.
본 논문에서는 TextRank 알고리즘을 통해 단어의 중요도를 계산하고, 중요한 단어와 인접한 단어의 쌍을 자질로 사용하는 동시출현 자질을 제안하였다. 실험을 통해 단일단어 자질에 비해 동시출현 자질이 문서 범주화의 성능 향상에 기여한다는 사실을 확인할 수 있었다.
가설 설정
이 때, 만약 "나무”라는 단어 앞에 “사과”라는 단어가 있다면, “사과 나무”가 되어 의미를 명확하게 할 수 있다. 이와 같이 복합어나 단어 사이에 수식 관계가 존재하는 경우, 서로 인접한 단어를 함께 자질로 사용하는 것이 문서 범주화에 도움이 될 수 있을 것이라는 가설로부터 동시출현 자질을 사용하였다. 그러나 인접한 단어 쌍 전체를 자질로 사용하지는 않고, 자질 선택 방법으로 TextRank 알고리즘⑻을 사용하였다.
제안 방법
NB는 베이지언 분류기, ME는 최대 엔트로피 모델을 의미한다. Baseline 시스템은 제안 시스템과 동일한 실험 환경에서 단일 단어 자질을 사용하여 문서를 분류하여 성능을 측정하였다. 그리고 *가 표기된 시스템은 교차 게재 문서를 포함하여 성능을 평가한 시스템이다.
[8]에서는 단어의 인접성을 가상의 연결 고리로 만들어 키워드 추출에 사용하였다. 또한 문장의 유사도를 연결 고리로 하여 중요문장 추출에 사용하였다. 실험을 통해 TextRank 알고리즘을 자연어 처리 분야에 적용할 수 있다는 가능성을 보여주고 있다.
또한 실험을 통해 Baseline과의 성능을 비교한 결과를 분석하고, 나아가 기존 연구와의 성능을 비교한 결과를 정리한다.
그러나 인접한 단어 쌍 전체를 자질로 사용하지는 않고, 자질 선택 방법으로 TextRank 알고리즘⑻을 사용하였다. 문서로부터 Text-Rank 알고리즘을 통해 중요도가 높은 단어를 추출하고, 그 단어와 인접한 단어의 쌍을 하나의 자질로 사용하였다. TextRank 알고리즘 외에 일반적으로 문서 범주화 시스템에서 사용하는 통계기반 자질 선택 방법은 사용하지 않았다.
PageRank 알고리즘은 그래프 기반의 순위화 알고리즘이다. 수집된 인터넷 문서 각각을 그래프의 노드, 문서 내부의 링크 정보를 간선으로 가정하여 방향성이 있는 그래프를 만들어 문서의 중요도를 계산한다. 이와 달리 TextRank 알고리즘은 한 문서에서 출현한 단어나 문장 등을 노드로 간주하고 방향성이 없는 그래프를 생성한다.
제안 시스템에서 문서로부터 TextRank 알고리즘을 이용하여 중요한 단어를 추출하고, 그 단어와 인접한 단어 쌍을 결합하여 동시출현 자질을 생성하여 문서 분류에 사용한다. 카이 제곱 통계량과 같은 통계적 기법에 기반한 자질 선택 방법은 사용하지 않는다.
TextRank 알고리즘 외에 일반적으로 문서 범주화 시스템에서 사용하는 통계기반 자질 선택 방법은 사용하지 않았다. 제안된 시스템의 성능 평가에는 20 News groups 문서 집합[9]과 지지 벡터 기계, 베이지언 분류기, 최대 엔트로피 모델 k-NN 분류기를 사용하였다.
카이 제곱 통계량과 같은 통계적 기법에 기반한 자질 선택 방법은 사용하지 않는다. 추출된 자질을 Bow Toolkit[13]에서 제공하는 지지 벡터 기계, 베이지언 분류기, 최대 엔트로피 모델 k-NN 분류기를 사용하여 문서를 분류하고 성능을 평가하였다. 지지 벡터 기계의 커널으로는 선형 커널(Linear kernel)을 사용하였다.
대상 데이터
20 Newsgroups 문서 집합은 총 20개의 범주, 19, 997 문서로 구성되어 있다. 그 중에서 약 500개의 문서는 두 개 이상의 범주에 할당되어 있다.
20 Newsgroups 문서 집합을 실험 데이터로 사용하였다. 20 Newsgroups 문서 집합은 총 20개의 범주, 19, 997 문서로 구성되어 있다.
그 중에서 약 500개의 문서는 두 개 이상의 범주에 할당되어 있다. 본 논문에서는 이러한 교차 개제 문서(Cross-posted Document) 분류를 위한 방법을 고려하지 않았으므로, 교차 개제 문서를 제외하고 남은 18, 846 문서만 실험에 사용하였다. 문서 집합을 임의로 4둥분하여 그 중 하나(25%; 4, 718 문서)를 실험 문서 집합으로 사용하였고, 나머지(75%; 14, 128 문서)를 학습 문서 집합으로 사용하였으며, 4단 교차 검증 방법(4-fold cross-validation)-^-^ 실험을 진행하였다.
데이터처리
본 논문에서는 이러한 교차 개제 문서(Cross-posted Document) 분류를 위한 방법을 고려하지 않았으므로, 교차 개제 문서를 제외하고 남은 18, 846 문서만 실험에 사용하였다. 문서 집합을 임의로 4둥분하여 그 중 하나(25%; 4, 718 문서)를 실험 문서 집합으로 사용하였고, 나머지(75%; 14, 128 문서)를 학습 문서 집합으로 사용하였으며, 4단 교차 검증 방법(4-fold cross-validation)-^-^ 실험을 진행하였다. 각 문서에는 많은 헤더 정보가 삽입되어 있는데, 제목과 본문 내용을 제외한 나머지는 제거하였다.
이론/모형
이와 같이 복합어나 단어 사이에 수식 관계가 존재하는 경우, 서로 인접한 단어를 함께 자질로 사용하는 것이 문서 범주화에 도움이 될 수 있을 것이라는 가설로부터 동시출현 자질을 사용하였다. 그러나 인접한 단어 쌍 전체를 자질로 사용하지는 않고, 자질 선택 방법으로 TextRank 알고리즘⑻을 사용하였다. 문서로부터 Text-Rank 알고리즘을 통해 중요도가 높은 단어를 추출하고, 그 단어와 인접한 단어의 쌍을 하나의 자질로 사용하였다.
단어는 명사, 동사, 형용사로 제한하였고, 제목에 나타난 단어에 가중치를 부여하였다. 자질 선택 방법으로는 카이 제곱 통계량과 Topic Signature를 사용하였다. Reuters-21578 문서 집합[11]을 이용한 실험에서 단일단어 자질보다 동시출현 자질을 사용하는 경우에 성능이 크게 향상되는 결과를 보였다.
추출된 자질을 Bow Toolkit[13]에서 제공하는 지지 벡터 기계, 베이지언 분류기, 최대 엔트로피 모델 k-NN 분류기를 사용하여 문서를 분류하고 성능을 평가하였다. 지지 벡터 기계의 커널으로는 선형 커널(Linear kernel)을 사용하였다.
성능/효과
범주화의 성능을 높이고자 하였다[16-20]. 그러나 제안 시스템은 자질 선택 방법의 개선을 통해 성능 향상을 꾀하였다. 표 3의 결과를 통해 자질 선택 방법의 개선을 통해 문서 범주화의 성능을 향상시킬 수 있음을 확인할 수 있다.
5% 이상의 성능 향상이 이루어졌다. 그리고 본 논문과 같이 중복 범주 문서를 제외한 기존 시스템[16]과 비교했을 때보다 높은 성능을 보이고 있다. 또한 중복 범주 문서를 포함한 기존 시스템들에 비해서도 2% 이상 높은 성능을 보여주고 있다.
표 3의 결과를 통해 자질 선택 방법의 개선을 통해 문서 범주화의 성능을 향상시킬 수 있음을 확인할 수 있다. 단일 단어 자질을 사용한 Baseline 시스템보다 모든 분류기에서 1.5% 이상의 성능 향상이 이루어졌다. 그리고 본 논문과 같이 중복 범주 문서를 제외한 기존 시스템[16]과 비교했을 때보다 높은 성능을 보이고 있다.
Reuters-21578 문서 집합[11]을 이용한 실험에서 단일단어 자질보다 동시출현 자질을 사용하는 경우에 성능이 크게 향상되는 결과를 보였다. 또한 Topic Signature를 사용한 자질 선택이 카이 제곱 통계량을 사용한 것에 비해 높은 성능을 보여, Topic Signature 라는 자질 선택 방법에 대한 가능성도 보여주었다.
실험을 통해 단일단어 자질에 비해 동시출현 자질이 문서 범주화의 성능 향상에 기여한다는 사실을 확인할 수 있었다. 또한 기존의 시스템들과 비교 결과를 통해서 문서 분류 방법의 개선도 좋지만, 제안 시스템처럼 자질 선택 방법의 개선을 통해서도 성능 향상을 할 수 있다는 사실도 확인할 수 있었다. 이 결과는 앞으로의 연구에도 기여할 수 있을 것이다’
또한 중복 범주 문서를 포함한 기존 시스템들에 비해서도 2% 이상 높은 성능을 보여주고 있다. 물론 중복 범주 문서의 포함 여부 때문에 직접적으로 정확하게 성능 비교를 할 수는 없으나, 충분히 제안 시스템이 가능성이 있다는 사실을 말해주는 결과이다.
또한 문장의 유사도를 연결 고리로 하여 중요문장 추출에 사용하였다. 실험을 통해 TextRank 알고리즘을 자연어 처리 분야에 적용할 수 있다는 가능성을 보여주고 있다.
사용하는 동시출현 자질을 제안하였다. 실험을 통해 단일단어 자질에 비해 동시출현 자질이 문서 범주화의 성능 향상에 기여한다는 사실을 확인할 수 있었다. 또한 기존의 시스템들과 비교 결과를 통해서 문서 분류 방법의 개선도 좋지만, 제안 시스템처럼 자질 선택 방법의 개선을 통해서도 성능 향상을 할 수 있다는 사실도 확인할 수 있었다.
후속연구
자질의 수가 증가하면 시스템의 계산 비용 또한 증가하는 문제가 발생할 수 밖에 없다. 따라서 불필요한 자질을 제거하는 방법에 대한 연구가 필요할 것이다. 또한 영어 품사 태거 대신에 한국어 품사 태거를 적용하면 어렵지 않게 제안 시스템의 방법론을 한국어 문서 분류에 사용할 수 있다.
참고문헌 (20)
Y. Yang and J. O. Pederson, "A comparative study on feature selection in text categorization," Proc. of the 14th International Conference on Machine Learning, pp.412-420, 1997.
C. Y. Lin and E. Hovy, "The Automated Acquisition of Topic Signatures for Text Summarization," Proc. of the 18th International Conference on Computation Linguistics, pp.495-500, 2000.
D. D. Lewis, "Naive (bayes) at forty: The independence assumption in information retrieval," Proc. of the 10th European Conference on Machine Learning, pp.4-15, 1998.
A. K. McCallum and K. Nigram, "A Comparison of Event Models for Naive Bayes Text Classification," Proc. of the AAAI-98 Workshop on Learning for Text Categorization, pp.41-48, 1998.
T. Joachims, "Text Categorization with Support Vector Machines: Learning with Many Relevant Features," Proc. of the 10th European Conference on Machine Learning, pp.137-142, 1998.
Y. Yang, "Expert netword: Effective and efficient learning from human decisions in text categorization and retrieval," Proc. of the 17th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp.13-22, 1994.
K. Nigam, J. Lafferty, and A. K. McCallum, "Using Maximum Entropy for Text Categorization," Proc. of the IJCAI-99 Workshop on Machine Learning for Information Filtering, pp.61-67, 1999.
R. Mihalcea and P. Tarau, "TextRank: Bringing Order into Texts," Proc. of the Conference on Empirical Methods in Natural Language Processing 2004, pp.404-411, 2004.
K. Lang, "The 20 Newsgroups data set," http://people.csail.mit.edu/~jrennie/20Newsgroups
W. Bae, Y. Han, and J. Cha, "Text Categorization using Topic Signature and Co-occurrence Features," Proc. of the KIISE Korea Computer Congress 2008, vol.35, no.1, pp.262-267, 2008. (in Korean)
D. D. Lewis, "The Reuters-21578 data set," http://www.daviddlewis.com/resources/testcollections/reut ers21578
S. Brin and L. Page, "The Anatomy of a Large-Scale Hypertextual Web Search Engine," Computer Networks and ISDN Systems, vol.30, pp.107-117, 1998.
A. K. McCallum, "Bow: A toolkit for statistical language modeling, text retrieval, classification and clustering," http://www.cs.cmu.edu/~mccallum/bow/, 1996.
K. Pearson, "On the theory of contingency and its relation to association and normal correlation," In Karl Pearson's early statistical papers, Cambridge: Cambridge University Press, pp.443-475, 1904/1948.
Y. Yang, "An evaluation of statistical approach to text categorization," Information Retrieval, vol.1, no.1-2, pp.69-90, 1996.
A. Gliozzo and C. Strapparava, "Domain Kernels for Text Categorization," Proc. of the 9th Conference on Computational Natural Language Learning, pp.56-63, 2005.
S. Tan, "Using Error-Correcting Output Codes with Model-Refinement to Boost Centroid Text Classifier," Proc. of the ACL 2007 Demo and Poster Sessions, pp.81-84, 2007.
R. Bekkerman, R. El-Yaniv, N. Tishby, and Y. Winter, "On feature distributional clustering for text categorization," Proc. of 24th Annual International ACM SIGIR Conference, pp.146-153, 2001.
Y. Yoon, C. Lee, and G. G. Lee, "Hierarchical text categorization using support vector machine," Proc. of the 15th Human and Cognitive Language Technology, pp.1-8, 2003. (in Korean)
Y. Yoon and G. G. Lee, "Efficient implementation of associative classifiers for document classification," Information Processing and Management, vol.43, pp.393-405, 2007.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.