[논문]군집 주제의 유의어와 유사도를 이용한 문서군집 향상 방법

박선; 김경준; 이진석; 이성로

[국내논문] 군집 주제의 유의어와 유사도를 이용한 문서군집 향상 방법
Enhancing Document Clustering Method using Synonym of Cluster Topic and Similarity 원문보기

電子工學會論文誌. Journal of the Institute of Electronics Engineers of Korea. SP, 신호처리, v.48 no.5 = no.341, 2011년, pp.30 - 38

박선 (목포대학교 정보산업연구소) , 김경준 (한국과학기술원 전산학과) , 이진석 (정보통신산업진흥원) , 이성로 (목포대학교 정보전자공학과)

초록
AI-Helper

본 논문은 군집 주제의 유의어와 유사도를 이용하여 문서군집의 성능을 향상시키는 방법을 제안한다. 제안된 방법은 비음수 행렬분해의 의미특징을 이용하여 군집 주제(topic)의 용어들을 선택함으로서 문서 군집 집합의 내부구조를 잘 표현할 수 있으며, 군집 주제의 용어들에 워드넷의 유의어를 사용하여서 확장함으로써 문서를 용어집합(BOW, bag-of-words)으로 표현하는 문제를 해결할 수 있다. 또한 확장된 군집 주제의 용어와 문서집합에 코사인 유사도를 이용하여서 군집의 주제에 적합한 문서를 잘 군집하여서 성능을 높일 수 있다. 실험결과 제안방법을 적용한 문서군집방법이 다른 문서군집 방법에 비하여 좋은 성능을 보인다.

Abstract ▼ AI-Helper

This paper proposes a new enhancing document clustering method using a synonym of cluster topic and the similarity. The proposed method can well represent the inherent structure of document cluster set by means of selecting terms of cluster topic based on the semantic features by NMF. It can solve the problem of "bags of words" by using of expanding the terms of cluster topics which uses the synonyms of WordNet. Also, it can improve the quality of document clustering which uses the cosine similarity between the expanded cluster topic terms and document set to well cluster document with respect to the appropriation cluster. The experimental results demonstrate that the proposed method achieves better performance than other document clustering methods.

주제어

AI 본문요약
AI-Helper

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

문제 정의

여기서 KM은 전통적인 분할 기반의 군집방법으로 Kmeans를 이용한 방법이다. 본 논문에서는 기존 방법과의 비교 기준을 세우기 위하여서 사용되었다. 나머지 NMF, ASI, CLGR, RNMF, FPCA, FNMF, SNMF등은 의미특징을 이용한 방법으로 RNMF, FPCA, FNMF는 이전에 저자들이 제안한 방법이다.
본 논문에서는 의미특징 방법의 제한 사항을 극복하기 위하여서 군집 주제의 유의어와 코사인 유사도를 이용한 문서군집의 성능 향상 방법을 제안한다. 제안 방법은 다음과 같다.
본 논문은 군집 주제의 유의어와 유사도를 이용하여서 문서군집의 결과를 향상시키는 방법을 제안하였다. 제안 방법은 비음수행렬분해를 이용하여서 문서집합의 주제를 잘 표현 할 수 있는 군집 주제의 용어들을 추출하였으며, 비음수행렬의 의미특징이 문서집합의 내부 구조만을 반영하여서 특정 자료 집합에 군집이 제한되는 것을 극복하기 위하여, 워드넷의 유의어를 사용하여 군집 주제의 용어집합을 확장하였다.
Xu이외 저자들은 비음수 행렬 분해(NMF, Non-negative Matrix Factorization)의 의미특징을 이용하여 문서를 군집하는 방법을 제안하였다^[9]. 본 논문의 저자들은 이전에 문서군집을 위한 세 가지 방법을 제안하였다. 제안방법으로는 의미특징과 군집의 응집도를 이용한 방법^[10～11], 의미특징과 퍼지관계를 이용한 방법^[12], 마지막으로 주성분 분석과 퍼지연관을 이용한 방법^[13]이 있다.

제안 방법

제안 방법은 비음수행렬분해를 이용하여서 문서집합의 주제를 잘 표현 할 수 있는 군집 주제의 용어들을 추출하였으며, 비음수행렬의 의미특징이 문서집합의 내부 구조만을 반영하여서 특정 자료 집합에 군집이 제한되는 것을 극복하기 위하여, 워드넷의 유의어를 사용하여 군집 주제의 용어집합을 확장하였다. 또한, 군집 주제 용어와 확장된 용어 집합에 유사도를 이용하여서 문서 집합으로부터 군집의 주제를 잘 반영한 문서를 분류하였다. 20 Newsgroups 문서자료를 이용하여서 성능평가한 결과, 제안방법인 SNMF의 평균 NMI가 KM군집 방법에 비하여서는 16.
확장된 군집 주제의 용어들은 의미특징이 원본 문서집합의 문서구성에 제한받는 문제를 극복할 수 있다. 마지막으로 확장된 군집 주제의 용어들과 원본 문서들 간에 코사인 유사도를 이용하여서 문서를 군집한다. 군집 주제를 잘 반영 할 수 있는 문서들을 코사인 유사도를 이용하여서 군집함으로써 군집의 성능을 향상 시킬 수 있다.
본 논문에서 제안한 문서군집 과정은 다음 그림 3과 같이 전처리, 군집 주제의 용어 추출, 문서군집으로 구성된다. 전처리단계에서는 문서집합을 전처리하여서 용어-문서 빈도행렬을 구성한다.
본 논문의 실험은 서로 다른 일곱 가지 문서군집방법과 제안방법간의 성능을 비교 평가 하였다. 평가방법은 20 Newsgroups 문자서료로 부터 임의로 추출된 10개의 군집문서를 이용하여서 군집하고, 군집결과를 실제 20 Newgroups에 분류되어 있는 문서와 NMI를 비교하였다.
평가방법은 20 Newsgroups 문자서료로 부터 임의로 추출된 10개의 군집문서를 이용하여서 군집하고, 군집결과를 실제 20 Newgroups에 분류되어 있는 문서와 NMI를 비교하였다. 비교방법으로는 군집의 개수를 2에서 10까지 증가시키며 각각 50번 반복하여서 각각의 군집에 평균을 계산하여서 평가하였다.
군집의 대표 용어를 이용하여 문서를 군집할 때, 대표용어와 일치하는 용어들로 구성된 문서들은 잘 군집되나, 대표 용어가 나타내는 군집의 주제를 포함하고 있으면서 다른 용어들로 구성된 문서들은 좋은 군집 결과가 나오지 않는 문제를 가지고 있다. 이러한 문제를 해결하기 위하여 본 논문에서는 워드넷을 이용하여 대표 용어들을 유의어 집단으로 확장한다. 확장방법은 대표 용어를 워드넷을 이용하여서 명사에 대한 유의어를 검색하고, 이 유의어 집합을 대표용어에 추가하여서 확장된 군집주제의 용어 집합 ER^p를 구성한다.
그러나 의미특징들은 문서집합의 내부의 구조특성만을 이용하기 때문에 실제로 문서들이 같은 주제를 포함하고 있으면서 다른 형태로 표현하는 경우 잘 구분할 수 없는 문제를 가지고 있다. 이러한 문제를 해결하기 위하여서 본 논문에서는 영어 어휘사전이 워드넷을 이용하여서 군집주제 용어를 유의어로 확장하여 사용한다. 용어를 유의어로 확장하면, 같은 주제를 다르게 표현하더라도 유사한 용어로 나타내기 때문에 쉽게 이를 구분할 수 있다.
그러나 일반 적으로 문서집합에 구성된 문서의 특성들을 보면 군집에 나타내는 주제에 일치하면서 동음이의어(homonym)나 이음동의어(유의어,synonym)으로 구성되어 있어서 유사도를 이용하여 구별할 수 없는 경우가 있다. 이러한 이유에서 본 논문에서는 군집의 대표 용어 집합과의 유사도가 0인 문서가 있다면 확장된 군집의 대표 용어집합 ER과 유사도를 계산하여 군집한다. 다음은 본 논문에서 유사도 계산에 사용되는 코사인 유사도 csin()이다^[5].
이번 장에서는 비음수행렬분해의 개념과 알고리즘에 대하여 알아보고, 다음 장에서 비음수행렬분해를 이용하여서 군집 주제의 중요 용어를 추출하는 제안방법에 대하여 알아본다.
본 논문은 군집 주제의 유의어와 유사도를 이용하여서 문서군집의 결과를 향상시키는 방법을 제안하였다. 제안 방법은 비음수행렬분해를 이용하여서 문서집합의 주제를 잘 표현 할 수 있는 군집 주제의 용어들을 추출하였으며, 비음수행렬의 의미특징이 문서집합의 내부 구조만을 반영하여서 특정 자료 집합에 군집이 제한되는 것을 극복하기 위하여, 워드넷의 유의어를 사용하여 군집 주제의 용어집합을 확장하였다. 또한, 군집 주제 용어와 확장된 용어 집합에 유사도를 이용하여서 문서 집합으로부터 군집의 주제를 잘 반영한 문서를 분류하였다.
본 논문의 실험은 서로 다른 일곱 가지 문서군집방법과 제안방법간의 성능을 비교 평가 하였다. 평가방법은 20 Newsgroups 문자서료로 부터 임의로 추출된 10개의 군집문서를 이용하여서 군집하고, 군집결과를 실제 20 Newgroups에 분류되어 있는 문서와 NMI를 비교하였다. 비교방법으로는 군집의 개수를 2에서 10까지 증가시키며 각각 50번 반복하여서 각각의 군집에 평균을 계산하여서 평가하였다.
평가에 사용된 비교방법들은 직접 구현하였으며, 다음 그림 4와 같이 KM^[3～4], NMF^[9], ASI^[7], CLGR^[8], RNMF^[10～11], FPCA^[13], FNMF^[12], SNMF등의 문서군집방법을 비교 평가 하였다. 여기서 KM은 전통적인 분할 기반의 군집방법으로 Kmeans를 이용한 방법이다.
설정된 군집의 개수를 이용하여서 비음 수행렬분해 한다. 행렬분해 된 의미특징행렬 W를 이용하여 군집의 주제를 잘 설명할 수 있는 용어들을 추출한다. 즉, 행렬 W의 열벡터는 군집의 주제에 대응되며, 행벡터는 군집을 구성하는 문서들의 용어에 대응된다.

대상 데이터

본 논문에서는 문서군집의 성능평가를 위하여 20 Newsgroups문서자료 중 일부를 무작위로 추출하여 사용하였다. 다음 표 6은 평가에 사용된 평가 자료의 특성표이다.
본 논문의 평가자료는 20 Newsgroups문서자료^[17]를 이용하였다. 20 Newsgroups문서자료는 문서군집 및 분류의 표준 성능평가 자료로 많이 사용하는 자료이다.

이론/모형

여기서 ER^p는 p번째 군집에서 확장된 군집의 대표 용어 집합 ER이다. 본 논문에서는 명사의 유의어를 검색할 때에 워드넷에서 기본적으로 지원하는 추정 용어 빈도 순위만(the ordered by estimated frequency of noun)을 사용한다. 명사에 대한 추정 용어 빈도 순위만을 사용하는 이유는, 동사나 다른 형태소에 대한 유의어를 대표 용어에 추가할 경우, 대표용어가 포함하는 군집의 주제를 너무 많이 벋어나기 때문에 군집의 성능을 오히려 저하 시킨다.
본 논문에서는 성능평가 방법의 척도(measure)로는 식(9)의 NMI(normalize mutual information)를 사용한다^[7～9]. NMI는 문서군집의 성능평가에 많이 사용되는 척도로 거의 표준 평가척도 중 하나이다.
불용어 제거는 Rijsbergen의 불용어 목록^[15]을 이용하여서 목록에서 정의하고 있는 무의미한 용어들을 제거한다. 어근추출은 Porter의 어근추출 알고리즘^[15]을 이용하여서 영어의 파생어들을 가장 중심이 되는 용어인 어근으로 변환한다. 용어-문서 빈도 행렬의 용어빈도 벡터 생성에 사용되는 벡터 T_i = [ t_1i, t_2i, … , t_ni]^T는 i번째 문장의 용어빈도이다.

성능/효과

또한, 군집 주제 용어와 확장된 용어 집합에 유사도를 이용하여서 문서 집합으로부터 군집의 주제를 잘 반영한 문서를 분류하였다. 20 Newsgroups 문서자료를 이용하여서 성능평가한 결과, 제안방법인 SNMF의 평균 NMI가 KM군집 방법에 비하여서는 16.29%가, NMF군집 방법보다는 13.10%가, ASI군집 방법보다는 12.56%가, CRGL군집 방법보다는 7.29%가, RNMF군집 방법보다는 4..73%가, FPCA군집 방법보다는 2.88%가, FNMF군집 방법보다는 2.06%가 각각 높음으로서 다른 문서군집 방법에 비하해서 더 좋은 성능을 나타냄을 알 수 있다. 앞으로 제안 방법의 성능 향상을 위하여 용어에 대한 가중치를 계산할 수 있는 다양한 정책과 다양한 종류의 행렬분해 방법에 적용할 수 있는 방법에 대한 연구가진행 되어야할 것이다.

후속연구

06%가 각각 높음으로서 다른 문서군집 방법에 비하해서 더 좋은 성능을 나타냄을 알 수 있다. 앞으로 제안 방법의 성능 향상을 위하여 용어에 대한 가중치를 계산할 수 있는 다양한 정책과 다양한 종류의 행렬분해 방법에 적용할 수 있는 방법에 대한 연구가진행 되어야할 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	문서군집은 어떠한 기술로서 사용됩니까?	문서군집은 정보검색, 문서요약, 자동문서 조직, 주제 추출, 정보 필터링 등에 효율적인 기반 기술로서 많이 사용된다. 특히 트위터, 패이스북, 블로그, 온라인 뉴스 등의 많은 문자자료들이 급속도로 늘어남에 따라서 더욱 많은 관심이 집중되고 있다[1～2].
	일반적인 군집방법은 어떻게 분류됩니까?	일반적인 군집방법은 분할기반 방법, 계층적 기반 방법, 밀도기반 방법, 격자 기반 방법으로 분류 할 수 있다. 이들 중 문서 군집에서 자주 사용되는 방법으로는 분할기반 방법과 계층적 기반 방법이 있다.
	분할기반 방법과 계층적 기반 방법을 설명하시오.	이들 중 문서 군집에서 자주 사용되는 방법으로는 분할기반 방법과 계층적 기반 방법이 있다. 분할기반 방법은 k개의 초기 군집을 생성한 다음, 군집의 성능을 향상시키기 위하여 반복적으로 군집의 객체들을 제배치하는 방법이다. 계층적 기반 방법은 주어진 자료 집합을 계층적 트리형태로 군집하는 방법이다. 그러나 이러한 군집방법들은 대부분 거리 기반의 목적 함수를 사용하기 때문에 고차원의 객체들을 군집해야하는 문서 군집에는 비효율적이다[2～4].

참고문헌 (17)

S. Basu, A.Banerjee, R. Mooney, "Semi-supervised Clustering by Seeding", Proceeding of International Conference on Machine Learning (ICML), pp. 19-26, 2002.
X. Hu, X. Zhang, C. Lu, E. K. Park, X. Zhou, "Exploiting Wikipedia as External Knowledge for Document Clustering," In proceeding of 15th ACM SIGKDD Conference On Knowledge Discover and Data Mining (KDD'09), Paris, Fance, Jun. 2009. pp. 389-396
S. Chakrabarti, "mining the web: Discovering Knowledge from Hypertext Data", Morgan Kaufmann Publishers, 2003.
J. Han, M. Kamber, "Second Edition Data Mining Concepts and Techniques", Morgan Kaufman, 2006.
B. Y. Ricardo, R. N. Berthier, "Moden Information Retrieval", ACM Press, 1999.
D. D. Lee, H. S. Seung, "Learning the parts of objects by non-negative matrix factorization," Nature, 401, pp. 788-791, Oct. 1999.

상세보기
T. Li, S. Ma, M. Ogihara, "Document Clustering via Adaptive Subspace Iteration", In proceeding of SIGIR'04, pp. 218-225, 2004.
F. Wang, C. Zhang, "Regularized Clustering for Documents", In proceeding of ACM SIGIR'07, pp. 95-102, 2007.
W. Xu, X. Liu, Y. Gon, "Document Clustering Based On Non-negative Matrix Factorization", Proceeding of Special Interest Group on Information Retrieval (SIGIR), pp. 267-274, 2003.
S. Park, D. U. An, B. R. Char, C. W. Kim, "Document Clustering with Cluster Refinement and Non-negative Matrix Factorization", In proceeding of ICONIP'09, pp. 281-288, 2009.
박선, 김철원, "비음수 행렬 분해와 군집의 응집도를 이용한 문서군집", 한국해양정보통신학회 논문지, 제13권 제12호, 2603-2608쪽, 2009년.

원문보기 상세보기
박선, 김경준, "비음수 행렬 분해와 퍼지 관계를 이용한 문서군집", 한국항행학회 논문지, 제14권 제2호, 239-246쪽, 2010년.

원문보기 상세보기
박선, 안동언, "주성분 분석과 퍼지 연관을 이용한 문서군집 방법", 한국정보처리학회 논문지, 제17-B권, 제2호, 177-182쪽, 2010년.
한경한, 남경완, "한국어 정보 처리 입문 : 컴퓨터가 우리말을 이해하려면", 커뮤니케이션북스, 2007년.
W. B. Frankes, B. Y. Ricardo, "Information Retrieval : Data Structure & Algorithms", Prentice-Hall, 1992.
G. Miller, "WordNet: A lexical database for english", CACM, vol. 38(11), 1995, pp.39-41.
The 20 newsgroups data set. http://people.csail.mit.edu/jrennie/20Newsgroups/, 2011.

저자의 다른 논문 :

LOADING...

표제어: 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

연합인증