[논문]주성분 분석과 k 평균 알고리즘을 이용한 문서군집 방법

김우생; 김수영

doi:10.6109/jkiice.2014.18.3.625

주성분 분석과 k 평균 알고리즘을 이용한 문서군집 방법
Document Clustering Technique by K-means Algorithm and PCA 원문보기

한국정보통신학회논문지 = Journal of the Korea Institute of Information and Communication Engineering, v.18 no.3, 2014년, pp.625 - 630

김우생 (Department of Computer Software, Kwangwoon University) , 김수영 (Department of Computer Engineering, Handong Global University)

초록
AI-Helper

컴퓨터의 발전과 인터넷의 급속한 발전으로 정보의 양이 폭발적으로 증가하게 되었고 이러한 방대한 양의 정보들은 대부분 문서 형태로 관리되기 때문에, 이들을 효과적으로 검색하고 처리하는 방법의 연구가 필요하다. 문서 군집은 문서간의 유사도를 바탕으로 서로 연관된 문서들을 군집화하여 대용량의 문서들을 자동으로 분류하고 검색하고 처리하는데 효율과 정확성을 증대시킨다. 본 논문은 특징 벡터 공간 상의 벡터들로 표현되는 문서들을 K 평균 알고리즘으로 군집화할 때, 주성분 분석을 사용하여 초기 시드점들을 선정함으로써 군집의 효율을 높이는 방법을 제안한다. 실험 결과를 통하여 제안하는 기법이 기존의 K 평균 알고리즘보다 좋은 결과를 얻을 수 있음을 보였다.

Abstract ▼ AI-Helper

The amount of information is increasing rapidly with the development of the internet and the computer. Since these enormous information is managed by the document forms, it is necessary to search and process them efficiently. The document clustering technique which clusters the related documents through the similarity between the documents help to classify, search, and process the large amount of documents automatically. This paper proposes a method to find the initial seed points through principal component analysis when the documents represented by vectors in the feature vector space are clustered by K-means algorithm in order to increase clustering performance. The experiment shows that our method has a better performance than the traditional K-means algorithm.

주제어

AI 본문요약
AI-Helper

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

문제 정의

주성분 분석(PCA: Principal Component Analysis)은 다차원적인 변수들을 축소 하는 차원의 단순화와 더불어 일반적으로 서로 상관되어 있는 반응 변수들 간의 복잡한 구조를 분석하는데 주로 이용된다[2,3]. 따라서 본 논문은 특징 벡터 공간 상의 문서들을 K 평균 알고리즘으로 군집화할 때, 주성분 분석을 사용하여 적절한 시드점을 구하는 방법을 제안한다. 실험 결과를 통하여 제안하는 방법이 기존 K 평균 기법보다 더 좋은 결과를 얻음을보였다.
기존의 K 평균 알고리즘은 무작위로 시드점을 선택하기 때문에, 잘못된 시드점을 선택하는 경우 성능이 좋지 않았다. 따라서 본 연구에서는 주성분 분석을 적용하여 적절한 시드 점을 찾아 효율적으로 군집화하는 방법을 제안하였다. 실험을 통해 무작위 K 평균 알고리즘보다 주성분 분석으로 적절한 시드점을 통한 K 평균 알고리즘이 더 좋은 군집화 성능을 얻음을 보였다.
문서들에 대한 군집화는 유사한 문서들의 그룹을 만들어 특정한 카테고리 안에서 검색과 처리를 용이하게 하고, 체계적인 문서 관리와 문서 저장을 위해서도 효율적이다. 또한 군집화 된 데이터들은 데이터들 간에 일종의 경향 또는 규칙성을 보이고 심지어 주목할 가치가 있는 관련 지식을 보여 주기까지 한다.
예를 들어, 표 1의 경우 A2, B1, C2 문서를 3개의 시드점으로 선택하면 무작위 시드점으로 K 평균 알고리즘을 수행하는 것보다 좋은 결과를 얻을 수 있다. 본 연구에서는 주성분 분석을 통해 이러한 적절한 시드점을 구하는 방법을 제안한다.

제안 방법

따라서 본 논문에서는 주성분 분석을 통하여 n 차원 상의 벡터들을 1차원 상의 점들로 변환한후, 서로 간에 거리가 떨어진 m개의 점들을 찾는 방법을 사용한다. 1차원 상의 점들 가운데 서로 간에 거리가 떨어진 m개의 점들을 찾기 위해, 본 연구에서는 모든 점들을 정렬한 후 m 균등 분할하여 각 분할의 중심이 되는 m개의 점을 구한다. 예를 들어, 표 1의 10차원 특징 벡터 공간 상의 8개 문서 벡터들을 주성분 분석을 통해 1차원 상의 8개 점들로 변환하면 -4.
주성분 분석은 고차원 입력 벡터를 저차원의 벡터로 표현할 수 있다. 따라서 본 논문에서는 주성분 분석을 통하여 n 차원 상의 벡터들을 1차원 상의 점들로 변환한후, 서로 간에 거리가 떨어진 m개의 점들을 찾는 방법을 사용한다. 1차원 상의 점들 가운데 서로 간에 거리가 떨어진 m개의 점들을 찾기 위해, 본 연구에서는 모든 점들을 정렬한 후 m 균등 분할하여 각 분할의 중심이 되는 m개의 점을 구한다.
본 논문에서 제안한 문서 군집 과정은 그림 1과 같이 전처리, 시드점 추출, 문서 군집으로 구성된다. 전처리 단계에서는 문서 집합을 전처리하여 문서-단어 행렬을 구성한다.
[7]은 K 평균과 비음수 행렬 분해를 이용하여 주제 기반의 다중 문서를 요약하는 방법을 제안하였다. 비음수 행렬 분해를 이용해 가중치가 부여된 용어문장 행렬을 의미 특징 행렬과 비음수 변수 행렬로 분해 함으로써 직관적으로 이해할 수 있는 의미적 특징을 추출하고, 주제와 의미 특징간의 유사도에 가중치를 부여해 유사도는 높으나 실제 의미 없는 문장이 추출되는 것을 막았다. 또한 K 평균 군집을 이용해 문장에 포함된 잡음을 제거하여 문서의 의미가 요약에 편향되게 반영하는 것을 피했다.
[8]은 비음수 행렬분해와 군집의 정제 방법을 이용한 문서 군집을 제안하였다. 이 방법에서는 비음수 행렬 분해의 유사한 문서 집합을 구분하지 못하는 문제를 해결하기 위해 군집 후, 군집 내의 유사도를 이용하여 재 군집하는 방법을 제안하였다. [9]는 SVD (Singular Value Decomposition)를 사용하여 단어와 문서에서 의미가 있는 레이블을 추출하여 군집화하는 방법을 제안하였다.
[6]는 주성분 분석과 비정칙치 분해를 이용해 문서를 요약하는 방법을 제안하였다. 주성분 분석과 비정칙 분해를 사용해 문장 벡터와 주제어 벡터를 획득한 후, 추출된 주제어와 문장 간의 거리가 가장 짧은 문장들을 중요 문장으로 추출하여 문서 요약으로 사용하였다. [7]은 K 평균과 비음수 행렬 분해를 이용하여 주제 기반의 다중 문서를 요약하는 방법을 제안하였다.
[4]는 주성분 분석과 퍼지 연관을 이용하여 문서를 군집화 하였다. 주성분 분석을 사용하여 군집을 대표할 수 있는 몇 개의 대표 용어들을 선택함으로써 군집의 고차원적인 특성으로부터 몇몇 의미 특징을 갖는 용어들로 군집을 효율적으로 표현하였으며, 군집의 대표 용어와 가장 높은 연관 관계를 갖는 용어를 포함하는 문서들로 군집함으로써 문서 군집의 정확도를 높였다. [5]는 문서의 내용을 대표할 수있는 주제어를 추출하기 위해 주성분 분석을 사용하였다.
[5]는 문서의 내용을 대표할 수있는 주제어를 추출하기 위해 주성분 분석을 사용하였다. 주성분 분석의 고유값과 고유벡터를 이용하여 문서 자체 내의 단어의 흐름을 파악한 후 주제어를 추출하는 방법을 사용하였다. [6]는 주성분 분석과 비정칙치 분해를 이용해 문서를 요약하는 방법을 제안하였다.

대상 데이터

본 연구에서는 제안하는 방법의 군집 성공률을 측정하기 위해 20 Newsgroups 문서 자료[12] 중 일부를 사용하였다. 20 Newsgroups은 20개의 다양한 주제로 구성되어 있으나, 이 들 중 종교, 컴퓨터 윈도우, 우주 과학, 오토바이, 스포츠 야구, 자동차, 의학, 총기, 정치의 9개 뉴스 그룹을 선택하고, 각 뉴스 그룹의 100개의 문서 들 중에서 무작위로 50개씩의 문서를 사용하였다. 문서 전처리를 통한 문서 단어 행렬에서 단어의 가중치로는 단어-역문헌 빈도수(TF-IDF)를 사용하였다.
본 연구에서는 제안하는 방법의 군집 성공률을 측정하기 위해 20 Newsgroups 문서 자료[12] 중 일부를 사용하였다. 20 Newsgroups은 20개의 다양한 주제로 구성되어 있으나, 이 들 중 종교, 컴퓨터 윈도우, 우주 과학, 오토바이, 스포츠 야구, 자동차, 의학, 총기, 정치의 9개 뉴스 그룹을 선택하고, 각 뉴스 그룹의 100개의 문서 들 중에서 무작위로 50개씩의 문서를 사용하였다.

데이터처리

전처리 단계에서는 문서 집합을 전처리하여 문서-단어 행렬을 구성한다. 문서-단어 행렬에 대응하는 특징 벡터들에주성분 분석을 통한 시드점들을 찾은 후 K 평균 알고리즘을 적용하여 문서들을 군집화한다.

이론/모형

, 1, 0, 0)의 벡터로 표현된다. 따라서본 논문에서는 이러한 특징 벡터 공간 상의 문서들을 K 평균 알고리즘을 사용하여 군집화한다. 일반적인 K 평균 알고리즘에서는 시드점이라고 불리는 초기의 K 개 패턴 즉 벡터들이 무작위로 선택되지만, 군집 구조에 관한 어떤 지식을 사용해 적절한 시드점을 구할 수 있다면 더 나은 성능을 얻을 수 있다[2,3].
20 Newsgroups은 20개의 다양한 주제로 구성되어 있으나, 이 들 중 종교, 컴퓨터 윈도우, 우주 과학, 오토바이, 스포츠 야구, 자동차, 의학, 총기, 정치의 9개 뉴스 그룹을 선택하고, 각 뉴스 그룹의 100개의 문서 들 중에서 무작위로 50개씩의 문서를 사용하였다. 문서 전처리를 통한 문서 단어 행렬에서 단어의 가중치로는 단어-역문헌 빈도수(TF-IDF)를 사용하였다. 표 3은 형성되는 군집의 수를 다르게 했을 때 주성분 분석을 통해 적절한 시드점을 찾는 비율과 K 평균 알고리즘의 수행 결과를 보여준다.
전처리 단계는 주어진 문서 집합으로부터 불용어 제거, 어간 추출, 단어의 가중치 등을 생성한다. 어간 추출은 Porter의 어간 추출 알고리즘을 이용한다[10]. 문서군집화에서 단어의 가중치는 많은 변형이 존재하지만 대부분 문서 내 단어 빈도수(TF: Term Frequency)와 역 문헌 빈도수(IDF: Inverse Document Frequency)의 조합에 기반한다[11].

성능/효과

이것은 각 군집의 크기가 비슷할 때 주성분을 적용하여 문서 벡터들을 1차원 상의 점들을 변환하여 균등 분할하면, 주제와 상관없는 문서 데이터들이 있는 경우를 제외하고는 각 그룹의 시드점을 제대로 찾을 수 있기 때문이다. 군집 성공 비율은 주성분 분석 기법의 시드점들을 사용한 K 평균 알고리즘이 무작위 시드점들을 사용한 K 평균 알고리즘보다 좋은 것을 알 수 있으며, 방법 2는 방법 1보다 좀 더 적절한 시드점을 찾기 때문에 군집 성공률도 보다 좋은 것을 알 수 있다.
비음수 행렬 분해를 이용해 가중치가 부여된 용어문장 행렬을 의미 특징 행렬과 비음수 변수 행렬로 분해 함으로써 직관적으로 이해할 수 있는 의미적 특징을 추출하고, 주제와 의미 특징간의 유사도에 가중치를 부여해 유사도는 높으나 실제 의미 없는 문장이 추출되는 것을 막았다. 또한 K 평균 군집을 이용해 문장에 포함된 잡음을 제거하여 문서의 의미가 요약에 편향되게 반영하는 것을 피했다. [8]은 비음수 행렬분해와 군집의 정제 방법을 이용한 문서 군집을 제안하였다.
따라서 본 논문은 특징 벡터 공간 상의 문서들을 K 평균 알고리즘으로 군집화할 때, 주성분 분석을 사용하여 적절한 시드점을 구하는 방법을 제안한다. 실험 결과를 통하여 제안하는 방법이 기존 K 평균 기법보다 더 좋은 결과를 얻음을보였다.
따라서 본 연구에서는 주성분 분석을 적용하여 적절한 시드 점을 찾아 효율적으로 군집화하는 방법을 제안하였다. 실험을 통해 무작위 K 평균 알고리즘보다 주성분 분석으로 적절한 시드점을 통한 K 평균 알고리즘이 더 좋은 군집화 성능을 얻음을 보였다. 추후 과제로는 군집 크기의 변이가 큰 경우에도 적절한 시드점을 찾는 연구가 필요하다.

후속연구

실험을 통해 무작위 K 평균 알고리즘보다 주성분 분석으로 적절한 시드점을 통한 K 평균 알고리즘이 더 좋은 군집화 성능을 얻음을 보였다. 추후 과제로는 군집 크기의 변이가 큰 경우에도 적절한 시드점을 찾는 연구가 필요하다.

질의응답

핵심어	질문	논문에서 추출한 답변
	군집 방법은 크게 무엇으로 나눌 수 있는가?	군집 방법은 크게 확률 모형에 기초한 방법과 확률 모형을 가정하지 않은 방법으로 나눌 수 있다[1,2]. 확률모형에 기초한 방법론 중에서 대표적인 방법은 가우스 혼합모형이며, 확률 모형을 가정하지 않은 방법론중 대표적인 방법은 계층 군집법과 K 평균 군집법이다.
	K 평균 군집법의 장단점은 무엇인가?	확률모형에 기초한 방법론 중에서 대표적인 방법은 가우스 혼합모형이며, 확률 모형을 가정하지 않은 방법론중 대표적인 방법은 계층 군집법과 K 평균 군집법이다. K 평균 군집법은 계층적 군집법에 비하여 계산량이 적고 대용량 데이터를 빠르게 처리할 수 있는 장점이 있 으나, 군집의 수를 사전에 알아야 하며 무작위로 초기 시드점을 선택하는 문제점이 있다.
	본 논문에서 기존의 K평균 알고리즘의 어떤 문제점 때문에 주성분 분석을 적용하여 적절한 시드 점을 찾아 효율적으로 군집화하는 방법이 제안되었는가?	단어들을 포함하는 문서는 특징 벡터 공간 상의 벡터로 표현할 수 있기에 K 평균 알고리즘을 사용하여 문서들을 군집화할 수 있다. 기존의 K 평균 알고리즘은 무작위로 시드점을 선택하기 때문에, 잘못된 시드점을 선택하는 경우 성능이 좋지 않았다. 따라서 본 연구에서는 주성분 분석을 적용하여 적절한 시드 점을 찾아 효율적으로 군집화하는 방법을 제안하였다.

참고문헌 (12)

C. Park, Y. Kim, J. Kim, J. Song, and H. Choi, Data Mining using R, Kyowoosa, 2011.
H. Park, and K. Lee, Pattern Recognition and Machine Learning from Basic to Application, Leehan Pub., 2011.
L. Oh, Pattern Recognition, Kyobo Book Centre, 2010.
S. Park, D. An, "Document Clustering Method using PCA and Fuzzy Association," Journal of Korea Information Processing Society B, 2010.
C. Lee, M. Kim, K. Lee, G. Lee, H. Park, "Document Thematic words Extraction using Principal Component Analysis," Journal of the Korea Society of Computer and Information B, 2002.
C. Lee, M. Kim, J. Paik, H. Park, "Text Summarization using PCA and SVD," Journal of Korea Information Processing Society B, 2003.
S. Park, J. Lee, "Topic-basied Multi-document Summarization Using Non-negative Matrix Factorization and K-means," Journal of the Korea Society of Computer and Information B, 2008.
S. Park, D. U. An, B. R. Char, and C. W. Kim, "Document Clustering with Cluster Refinement and Non-negative Matrix Factorization," In Proceeding of ICONIP'09, 2009.
S. Osinski and D. Weiss, "Conceptua Clustering using lingo algorithm: Evaluation on open directory project data," in Proc. IIPWM04, 2004.
The Porter Stemming Algorithm. Available: http://tartarus.org/-martin/PorterStemmer/
B. Lee, Information Retrieval, Green Pub. 2012.
http://qwone.com/-jason/20Newsgroups/

저자의 다른 논문 :

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

연합인증

주성분 분석과 k 평균 알고리즘을 이용한 문서군집 방법
Document Clustering Technique by K-means Algorithm and PCA 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

제안 방법

대상 데이터

데이터처리

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (12)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

주성분 분석과 k 평균 알고리즘을 이용한 문서군집 방법 Document Clustering Technique by K-means Algorithm and PCA 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

대상 데이터

데이터처리

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (12)

이 논문을 인용한 문헌

저자의 다른 논문 :

김우생 (35)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

주성분 분석과 k 평균 알고리즘을 이용한 문서군집 방법
Document Clustering Technique by K-means Algorithm and PCA 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper