[논문]주성분 분석과 퍼지 연관을 이용한 문서군집 방법

박선; 안동언

doi:10.3745/kipstb.2010.17b.2.177

주성분 분석과 퍼지 연관을 이용한 문서군집 방법
Document Clustering Method using PCA and Fuzzy Association 원문보기

정보처리학회논문지. The KIPS transactions. Part B. Part B, v.17B no.2, 2010년, pp.177 - 182

박선 (전북대학교 전기전자정보인력양성사업단) , 안동언 (전북대학교 전기전자컴퓨터공학부)

초록
AI-Helper

본 논문은 주성분 분석과 퍼지 연관을 이용한 새로운 문서군집 방법을 제안한다. 제안된 방법은 주성분 분석의 의미특징을 이용하여 군집 레이블과 군집의 대표 용어들을 선택하기 때문에 문서군집의 내부구조를 더 잘 표현할 수 있다. 또한 퍼지연관 값을 이용한 군집은 문서군집에 유사하지 않은 문서를 더 잘 구분함으로써 문서군집의 성능을 높일 수 있다. 실험결과 제안방법을 적용한 문서군집방법이 다른 문서군집 방법에 비하여 좋은 성능을 보인다.

Abstract ▼ AI-Helper

This paper proposes a new document clustering method using PCA and fuzzy association. The proposed method can represent an inherent structure of document clusters better since it select the cluster label and terms of representing cluster by semantic features based on PCA. Also it can improve the quality of document clustering because the clustered documents by using fuzzy association values distinguish well dissimilar documents in clusters. The experimental results demonstrate that the proposed method achieves better performance than other document clustering methods.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 논문은 주성분 분석과 퍼지 연관을 이용하여 문서를 군집하는 새로운 문서군집방법을 제안하였다. 제안 방법은 주성분 분석을 사용하여 군집을 대표할 수 있는 몇 개의 대표 용어들로 선택함으로서 군집의 고차원적인 특성으로부터 몇몇 의미 특징을 갖는 용어로 저차원화함으로서 군집을 효율적으로 표현하였으며, 군집의 대표 용어와 가장 높은 연관관계를 갖는 용어를 포함하는 문서들로 군집함으로써 문서군집의 정확도를 높였다.
본 논문은 주성분분석과 퍼지연관을 이용하여 문서를 군집하는 새로운 문서군집 방법을 제안한다. 주성분분석(PCA, Principal Component Analysis)은 다차원적인 변수들을 축소, 요약하는 차원의 단순화와 더불어 일반적으로 서로 상관되어 있는 반응변수들 간의 복잡한 구조를 분석하는데 주로 이용되는 방법이다[1, 7].
Xu 이외 저자들은 비음수 행렬 분해(NMF, Non-negative Matrix Factorization)의 의미특징을 이용하여 문서를 군집하는 방법을 제안하였다[15]. 본 논문의 저자들은 이전에 비음수 행렬 분해와 군집의 정제방법을 이용한 문서군집 방법을 제안하였다. 이 방법은 비음수행렬 분해의 유사한 문서집합을 구분 하지 못하는 문제를 해결하기 위하여서 군집 후, 군집내의 유사도를 이용하여 재 군집하는 방법을 제안하였다[12].
본장에서는 제안방법과 유사한 의미특징이나 군집의 레이블을 이용한 문서군집에 대한 기존연구에 대하여 알아본다. Ji외 저자들이 제안한 문서 군집방법으로 문서 군집 분석에 군집의 구성원에 대한 사전지식을 통합한 준지도 문서 군집 모델을 제안하였다.

제안 방법

본장에서는 제안방법과 유사한 의미특징이나 군집의 레이블을 이용한 문서군집에 대한 기존연구에 대하여 알아본다. Ji외 저자들이 제안한 문서 군집방법으로 문서 군집 분석에 군집의 구성원에 대한 사전지식을 통합한 준지도 문서 군집 모델을 제안하였다. 이들의 방법은 사용자가 분류를 원하는 클러스터를 사전 지식으로 지정하고, 사전 지식을 군집의 비용 함수에 적용하여 문서를 군집한다[6].
식(5)를 이용하여 퍼지 연관 용어 상관 행렬과 대표 용어들로부터 퍼지 포함 관계를 계산하다. 계산된 퍼지 포함관계를 이용하여 문서를 군집한다. 즉, 퍼지 포함관계 μ_i,j 가 최고값을 가지면, d_i 문서를 C_j 군집에 할당한다.
본 논문의 실험은 서로 다른 다섯 가지 문서군집방법과 제안방법간의 성능을 비교하였다. 성능 비교에서는 문서군 집의 성능평가에 주로 사용되는 방법으로 군집의 개수를 2에서 10까지 증가하면서 NMI를 비교 하였다.
본 논문의 실험은 서로 다른 다섯 가지 문서군집방법과 제안방법간의 성능을 비교하였다. 성능 비교에서는 문서군 집의 성능평가에 주로 사용되는 방법으로 군집의 개수를 2에서 10까지 증가하면서 NMI를 비교 하였다. <표 7>은 각각의 문서군집 방법 간의 비교 실험의 평균 NMI 결과이고, (그림 2)는 <표 7>을 도식화한 결과이다.
이 논문에서 제안한 문서군집 과정은 다음 (그림 1)과 같이 전처리, 군집 대표용어 추출, 문서군집으로 구성된다. 전처리단계에서는 문서집합을 전처리하여 용어-문서 빈도행렬을 구성한다.
본 논문은 주성분 분석과 퍼지 연관을 이용하여 문서를 군집하는 새로운 문서군집방법을 제안하였다. 제안 방법은 주성분 분석을 사용하여 군집을 대표할 수 있는 몇 개의 대표 용어들로 선택함으로서 군집의 고차원적인 특성으로부터 몇몇 의미 특징을 갖는 용어로 저차원화함으로서 군집을 효율적으로 표현하였으며, 군집의 대표 용어와 가장 높은 연관관계를 갖는 용어를 포함하는 문서들로 군집함으로써 문서군집의 정확도를 높였다. 또한, 군집을 대표할 수 있는 군집 레이블을 추출함으로써 사용자는 쉽게 문서군집의 특성을 파악할 수 있다.
퍼지 연관(Fuzzy Association)은 퍼지집합 이론을 사용하여 정보검색 과정의 모호성을 정형화하는 방법으로, 문서집합의 용어들이나 다른 색인어들 간의 관계를 인식할 수 있다[9, 16]. 제안 방법은 주성분분석을 이용하여 군집의 레이블과 군집의 대표 용어들을 선택하고, 선택한 대표 용어들과 문서에 포함된 용어의 퍼지 연관 관계를 이용하여 문서를 군집한다.

대상 데이터

제안방법에 대한 실험은 문서군집의 표준 성능평가 자료인 20 Newsgroups 문서자료[2] 중 일부를 무작위로 추출하여 실험하였다. 20 Newsgroups 평가자료는 뉴스 그룹이 20개가 있으며, 20개의 뉴스 그룹에는 총 20000 개의 문서를 포함하고 있다.

이론/모형

본 논문의 성능평가는 문서군집의 표준 평가척도 중 하나인 식(7)의 NMI(normalize mutual information)를 사용한다[11, 14, 15]. NMI의 상호정보이득은 두 개의 문서군집 C와 C’가 주어질 때 이들 간의 상호정보 MI(C,C’)로 다음 식(6)과 같이 정의된다.
전처리 단계는 주어진 문서집합으로부터 불용어 제거, 어근추출, 용어빈도 벡터를 생성한다[5, 9]. 불용어 제거는 Rijsbergen의 불용어 목록[5]을 이용하고, 어근추출은 Porter 의 어근추출 알고리즘[5]을 이용한다. 용어빈도 벡터 생성에 사용되는 벡터 T_j = [ t_1j, t_2j, … , t_nj ]^T는 j번째 문서의 용어빈도이다.

성능/효과

첫째, 주성분 분석을 사용하여 군집을 대표할 수 있는 몇 개의 대표 용어들을 이용함으로서 고차원의 특징을 갖는 문서군집에 효율적이다. 둘째, 대표 용어와 문서내의 용어들 간의 퍼지 연관 관계를 사용하고, 이것은 군집에 더욱 관련 있는 용어를 포함한 문서들로 군집함으로써 문서군집의 정확도를 높일 수 있다. 마지막으로, 군집을 대표할 수 있는 군집 레이블을 추출함으로써 사용자는 쉽게 군집에 포함된 문서 집합의 특성을 파악할 수 있다.
(그림 2)에서 NMF군집방법이 KM군집방법보다 성능이 좋은 것은 KM에서의 단순한 유사도를 이용한 군집보다 NMF를 이용하여 자료의 내부구조를 반영하여 군집하는 것이 더 정확도에 영향을 미치는 것을 알 수 있다. 또한 군집의 하위 공간 구조의 속성을 사용하는 ASI나 군집의 전역 및 지역적 정규화 특성을 사용하는 CRGL보다는 군집의 내부 구조와 군집간의 유사도를 사용하는 RNMF가 좋은 군집 결과를 나타냄을 알 수 있다. 특히, FPCA는 군집의 각각의 특성을 나타내는 대표용어와 군집에 포함되는 문서의 용어들 간의 연관관계를 고려함으로써 가장 좋은 성능을 보인 것으로 생각된다.
둘째, 대표 용어와 문서내의 용어들 간의 퍼지 연관 관계를 사용하고, 이것은 군집에 더욱 관련 있는 용어를 포함한 문서들로 군집함으로써 문서군집의 정확도를 높일 수 있다. 마지막으로, 군집을 대표할 수 있는 군집 레이블을 추출함으로써 사용자는 쉽게 군집에 포함된 문서 집합의 특성을 파악할 수 있다.
또한, 군집을 대표할 수 있는 군집 레이블을 추출함으로써 사용자는 쉽게 문서군집의 특성을 파악할 수 있다. 실험결과 제안방법의 FPCA의 평균 NMI가 KM군집 방법에 비하여서는 26.46%가, NMF군집 방법보다는 18.89%가, ASI군집 방법보다는 17.78%가, CRGL 군집 방법보다는 7.39%가, RNMF군집 방법보다는 2.98%가 각각 높음으로서 다른 문서군집 방법에 비하해서 더 좋은 성능을 나타냄을 알 수 있다.
제안된 방법은 다음과 같은 장점을 갖는다. 첫째, 주성분 분석을 사용하여 군집을 대표할 수 있는 몇 개의 대표 용어들을 이용함으로서 고차원의 특징을 갖는 문서군집에 효율적이다. 둘째, 대표 용어와 문서내의 용어들 간의 퍼지 연관 관계를 사용하고, 이것은 군집에 더욱 관련 있는 용어를 포함한 문서들로 군집함으로써 문서군집의 정확도를 높일 수 있다.

후속연구

앞으로 제안 방법의 성능 향상을 위하여 용어에 대한 가중치를 계산할 수 있는 다양한 정책과 비음수 행렬 분해를 이용한 군집방법에 적용할 수 있는 방법에 대하여 연구가 진행 되어야 할 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	문서군집은 무엇인가?	문서군집은 군집 알고리즘을 사용하여서 문서집합으로부터 유사한 특성을 가진 문서들의 그룹을 발견하는 것이다. 문서군집은 자료를 분석하는 중요한 기술로 자료의 조직화, 웹 검색결과의 브라우징, 다중문서 요약 등 다양한 정보검색 응용분야에 활용되는 중요한 방법[4, 10]으로, 정보통신 및 개인화 단말기의 발전으로 중요성이 더욱 부각되고 있다.
	전통적인 군집방법의 대부분이 고차원의 객체들을 군집하는 것에 비효율적인 이유는 무엇인가?	전통적인 군집방법은 분할기반 방법, 계층적 기반 방법, 밀도기반 방법, 격자 기반 방법으로 분류 할 수 있다. 이들 대부분의 방법들은 거리 기반의 목적 함수를 사용하기 때문에 고차원의 객체들을 군집하는 것에는 비효율적이다. 이중에서 대표적인 군집방법으로는, 군집을 생성하는 방법에 따라서 k개의 군집을 임의로 정하여 군집을 확장해가는 비계층적 방법인 Kmeans와 군집간의 결합 방법에 의한 계층적 군집방법인 직접 군집방법이 있다[4, 8].
	문서의 범주화는 무엇인가?	근래의 정보 검색 분야에는 사용자의 요구사항을 만족시키기 위하여 다양한 정보를 효율적으로 처리할 수 있는 문서의 범주화에 대해서 많은 연구가 있다. 문서의 범주화는 대량의 문서들을 각각의 문서의 특성 및 주제에 맞게 분류 하는 것으로, 사전에 학습이 필요한 지도학습방법인 문서분류와 학습이 필요 없는 비지도학습 방법의 문서군집으로 구분할 수 있다[4].

참고문헌 (17)

이창범, 김민수, 이기호, 이귀상, 박혁로. “주성분 분석을 이용한 문서 주제어 추출”, 정보과학회논문지 : 소프트웨어 및 응용 제 29권 제 10호, 2002.
The 20 newsgroups data set. http://people.csail.mit.edu/jrennie/20Newsgroups/, 2009.
S. Basu, A.Banerjee, R. Mooney, “Semi-supervised Clustering by Seeding,” Proceeding of International Conference on Machine Learning (ICML), pp.19-26, 2002.
S. Chakrabarti, “mining the web: Discovering Knowledge from Hypertext Data,” Morgan Kaufmann Publishers, 2003.
W. B. Frankes, B. Y. Ricardo, “Information Retrieval : Data Structure & Algorithms,” Prentice-Hall, 1992.
X. Ji, W. Xu, S. Zhu, “Document Clustering with Prior Knowledge”, Proceeding of Special Interest Group on Information Retrieval (SIGIR), pp.405-412, 2006.
R. A. Johnson, D. W. Wichern, Applied Multivariate Statistical Analysis 5th ed., Prentice hall, 2007.
J. Han, M. Kamber, “Second Edition Data Mining Concepts and Techniques,” Morgan Kaufman, 2006.
C. Haruechaiyasak, M. L. Shyu, S. C. Chen, "Web Document Classification Based on Fuzzy Association," In proceedings of the 25th Annual International Computer Software and Applications Conference (COMPSAC'02), 2002.
Y. Huang, T. M. Mitchell, “Text Clustering with Extended User Feedback”, Proceeding of Special Interest Group on Information Retrieval (SIGIR), pp.413-420, 2006.
T. Li, S. Ma, M. Ogihara, "Document Clustering via Adaptive Subspace Iteration," In proceeding of SIGIR'04, pp.218-225, 2004.
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.

상세보기
B. Y. Ricardo, R. N. Berthier, “Moden Information Retrieval,” ACM Press, 1999.
F. Wang, C. Zhang, "Regularized Clustering for Documents," In proceeding of ACM SIGIR'07, 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.
L. A. Zadeh, "Fuzzy Sets, in Dubois, D., Prade, H. and Yager, R. R. editiors, Readings in Fuzzy Sets for Intelligent Systems," Morgan Kaufmann Publiishers, 1993.
H. J. Zeng, Q. C. He, Z. Chen, W. Y. Ma, J. Ma, “Learning to Cluster Web Search Results,” Proceeding of Special Interest Group on Information Retrieval (SIGIR), 210-217, 2004.

저자의 다른 논문 :

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

연합인증