의미 기반 문단 분할을 활용한 문단 기반 K-Means 클러스터링
Paragraph-based K-Means Clustering by using Meaning-based Paragraph Division
1
조회
0
다운로드
5
인용
0
참고문헌
키워드
초록
전자 문서의 수가 폭발적으로 늘어남에 따라, 문서들로부터 정보를 빠르고 정확하게 검색하는 것은 더욱더 어려워지고 있다. 이 문제를 해결하기 위해, 문서들은 다양한 방법으로 클러스터링 되는데 일반적으로 K-Means 알고리즘이 이용된다. K-Means 알고리즘은 많은 문서들을 빠르고 쉽게 클러스터링 하는데 적합하지만, 문서 클러스터링에 이용한 경우 문서가 가진 의미를 고려하여서 클러스터링 하지는 않는다. 본 연구에서는 의미를 기반으로 문서를 문단화하여 클러스터링하는 기법을 제안하다. 제안된 기법은 문장 간의 유사도를 측정하여 문서 집합 내의 문서들을 의미 기반의 문단으로 분리하고, 각 문서로부터 최대 응집도를 보이는 대표 문단을 선택한 후 이들을 이용하여 K-Means 클러스터링을 수행한다. 본 연구는 다음의 점이 기존의 연구 방법과 차이가 있다. 문장간의 유사도 측정시에 단어간의 의미 유사도를 계산하기 위해 WordNet 온톨로지를 이용했다. 그리고 문단내 포함된 단어들의 tf-idf 값들의 합을 문단의 크기로 정규화함으로써 문단의 의미 응집도를 계산하는 방법을 제시했다. 제안된 기법의 성능을 증명하기 위해 Reuter-21578 문서 집합을 이용하여 실험을 수행했다. 실험의 결과는 의미 기반 문단을 사용하는 문서 클러스터링 기법이 문서 검색의 정확성과 재현율을 향상시킴을 보였다.
Abstract
As the number of electronic documents explosively increases, it becomes more and more difficult to retrieve information from them rapidly and accurately. To solve this problem, documents are clustered in various ways and generally K-Means algorithm is used to achieve it. K-Means algorithm is adequate to cluster so many documents rapidly and easily, but it does not consider the meaning of documents on clustering. In this research, we propose a document clustering technique of using meaning-based paragraphs. The proposed technique divides documents in a document set into meaning-based paragraphs by measuring similarity between sentences, chooses representative paragraphs having the maximum coherence value from each document, and then commits K-Means algorithm depending on them. In this paper, different from existing methods, we proposed a novel similarity function between two adjacent sentences by using WordNet as a ontology to calculate the similarity between words. And we introduced a method which can be used to calculate coherence of meaning-based paragraph by normalizing the sum of tf-idf value of words in the paragraph. We conducted experiments to prove the performance of the proposed technique by using the Reuter-21578 document set. The experimental result showed the document clustering technique of using meaning-based paragraphs improves the precision and the recall of document retrieval.
참고문헌 (15)
- T. Radecki, "A model of a document-clustering-based information retrieval system with a Boolean search request formulation", pp.334~344 (1980), SIGIR
- M. Steinbach, "A comparison of document clustering techniques", KDD Workshop on Text mining (2000)
- A. Leusik, "Evaluating document clustering for interactive information retrieval", CIKM 2001, pp.33~40 (2001)
- K. S. Lee, "A document ranking model based on vector space retrieval and cluster analysis in information retrieval", Ph.D., pp.2001
- N. Y. Kim, "Document clustering analysis based on similarity calculation between cluster centroids", Proceedings of the 2002 IEIE Autumn Conference, 25(2), pp.119~122 (2002)
- 박사준, "대용량 문서 검색을 위한 의미 흐름 기반 클러스터링", 한국지식정보기술학회 논문지, 8(4), pp.37~42 (2013), 한국지식정보기술학회
- D. R. Cutting, "Scatter", Gather: A cluster-based approach to browsing large document collections, 1992, 318~329
- H. J. Jain, "Context senstive text summarization using K means clustering algorithm", IJSCE, 2(2), pp.301~304 (2012)
- A. Gelbukh, "Combining sources of evidence for recognition of relevant passages in texts", LNCS, 3563, pp.283~290 (2005)
- G. Salton, "Automatic information organization and retrieval" (1968), McGraw-Hill
- J. Spark, "A statistical interpretation of term specificity and its application in retrieval", Journal of Documentation, 28, pp.11~21 (1972)
- E. M. Voorhees, "Learning collection fusion strategies", Proceedings of the 18th ACM SIGIR Conference on Research and Development in Information Retrieval, pp.172~179 (1995)
- H. J. Jain, "Context senstive text summarization using K means clustering algorithm", IJSCE, 2(2), pp.301~304 (2012)
- A. Goswami, "Fast and exact out-of-core and distributed k-means clustering", Knowlege and Information Systems, 10, pp.17~40 (2006)
- G. Salton, "A vector space model for automatic indexing", Commun. ACM, 18(11), pp.613~620 (1975)