[논문]X-means 확장을 통한 효율적인 집단 개수의 결정

허경용; 우영운

doi:10.6109/jkiice.2008.12.4.772

X-means 확장을 통한 효율적인 집단 개수의 결정
Extensions of X-means with Efficient Learning the Number of Clusters 원문보기

한국해양정보통신학회논문지 = The journal of the Korea Institute of Maritime Information & Communication Sciences, v.12 no.4, 2008년, pp.772 - 780

허경용 , 우영운 (동의대학교 멀티미디어공학과)

초록
AI-Helper

K-means는 알고리즘의 단순함과 효율적인 구현이 가능함으로 인해 군집화를 위해 현재까지 널리 사용되는 방법 중 하나이다. 하지만 K-means는 집단의 개수가 사전에 결정되어야 하는 근본적인 문제점이 있다. 이 논문에서는 BIC(Bayesian information criterion) 점수를 이용하여 효율적으로 집단의 개수를 추정할 수 있는 X-means 알고리즘을 확장한 두 가지 알고리즘을 제안한다. 제안한 방법은 기본적으로 X-means 방법을 따르면서 집단이 임의의 분산 행렬을 가질 수 있도록 함으로써 X-means 알고리즘이 원형 집단만을 허용함에 따른 over-fitting을 개선한다. 제안한 방법은 하나의 집단에서 시작하여 계속해서 집단을 나누어가는 하향식 방법으로, BIC score를 최대로 증가시키는 집단을 분할해 나간다. 제안한 알고리즘은 Modified X-means(MX-means)와 Generalized X-means(GX-means)의 두 가지로, 전자는 K-means 알고리즘을, 후자는 EM 알고리즘을 사용하여 현재 주어진 집단들에서 최적의 분할을 찾아낸다. MX-means는 GX-means보다 그 속도에서 앞서지만 집단들이 중첩 된 경우에는 올바른 집단을 찾아낼 수 없는 단점이 있다. GX-means는 실행 속도가 느린 단점이 있지만 집단들이 중첩된 경우에도 안정적으로 집단들을 찾아낼 수 있다. 이러한 점들은 일련의 실험을 통해서 확인할 수 있으며, 제안한 방법들이 기존의 방법들에 비해 나은 성능을 보임을 확인할 수 있다.

Abstract ▼ AI-Helper

K-means is one of the simplest unsupervised learning algorithms that solve the clustering problem. However K-means suffers the basic shortcoming: the number of clusters k has to be known in advance. In this paper, we propose extensions of X-means, which can estimate the number of clusters using Bayesian information criterion(BIC). We introduce two different versions of algorithm: modified X-means(MX-means) and generalized X-means(GX-means), which employ one full covariance matrix for one cluster and so can estimate the number of clusters efficiently without severe over-fitting which X-means suffers due to its spherical cluster assumption. The algorithms start with one cluster and try to split a cluster iteratively to maximize the BIC score. The former uses K-means algorithm to find a set of optimal clusters with current k, which makes it simple and fast. However it generates wrongly estimated centers when the clusters are overlapped. The latter uses EM algorithm to estimate the parameters and generates more stable clusters even when the clusters are overlapped. Experiments with synthetic data show that the purposed methods can provide a robust estimate of the number of clusters and cluster parameters compared to other existing top-down algorithms.

주제어

AI 본문요약
AI-Helper

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

문제 정의

X-means, G-means는 K-means의 wrapper 알 고리 즘이고 PG-means는 EM 알고리즘의 wrapper 알고리즘이며 BK-means는 가변 기법(variatkmal method)을 사용한다. 이 논문에서는 이들 알고리즘 중 K-means를 사용하는 G-mears와 기존의 알고리즘 중 가장 나은 성능을 보이는 BK-means를 그 비교 대상으로 실험 하였다.

가설 설정

X-means 알고리즘의 기본적인 문제점은 모든 집단이 동일한 분산행렬을 가지며, 분산 행렬은 단위행렬의 상수배로 주어진다는 점이다. 즉 모든 집단이 동일한 분포를 가지 며 이분 포는 구형 가우시 안 분포라고 가정 한다. 이러한 가정은 데이터가 구형으로 분포하지 않는 경우 심각한 과대 적 합을 유발하는 문제 점 이 있다.

제안 방법

GX-means 알고리즘은 알려진 하향식 알고리즘 중 가장 많은 연산을 필요로 하며, BK-means에 비해서도 3-4건1| 느리다. 따라서 이 논문의 실험을위해서 다른 알고리즘들은 Matlab으로 구현하였지만, GX-means 알고리즘의 EM 알고리즘 부분은 C로 구현하여 실험 하였다.
하지만G-means가국부적으로 하나의 집단에 속하는 데이터가 하나의 가우시안 분포에서 생성 되 었는지 를 AD 테스트로 검사하는 반면, PG-means 는 전역적으로 모든 데이터가 가우시안 혼합(mb血此) 분포에서 생성되었는지를 Kolmogonw-Smimov 테스트 (KS test)를 통해 검사한다. 또한 중첩된 집단 문제를 해결하기 위해 K-means가 아닌 EM 알고리즘을 이용하여 최적의 분할을 찾아낸다. PG-means는 연산의 효율성을 위해 데이터를 1차원으로 무작위 투영(randomprojectfon) 을 행한 후 이 데이터를 이용하여 KS 테스트를 시행한다.
이 논문에서 제안한 두 알고리즘, MX-means와 GX-means의 성능을 기존의 G-means와 BK-means 알고리즘과 비교하기 위해 일련의 실험 데이터에 대한 실험을 수행하였다.
이 논문에서는 BIC 점 수를 이용하여 군집 의 개수를 효율적 으로 결정 하는 X-means 알고리즘을 개선한 두 가지 알고리즘, MX-meaM와 GX-means 알고리즘을 제안하였다. 제안한 알고리즘들은 하나의 집단에서 시작하여 BIC 점 수를 증가시 키 는 집 단들을 반복적 으로 분할해나가는 하향식 wrapper 알고리즘으로, 주어진 집 단의 수 k에서 최적의 집단들을 찾아내기 위해 MX-means는 K-means 알고리즘을 사용하여 lard clustering을 수행하고 GX-means는 EM 알고리즘을 통해 soft clustering을 수행하는 점에서 다르다.
이 논문에서는 기존의 X-means[2] 알고리즘을 확장한 두 개의 알고리즘, MX-means (Modified X-means)와 GX-means (Generalized X-means)를 제안한다. X-means알고리즘은 하나의 집단에서 시작하여 반복적으로 집단을 분할해 나가는 하향식 알고리 즘으로 집 단의 분할을 위한 기준으로 BIC(Bayesian Information Criterion) 점수(score)를 사용한다.
하지만 EM을 이 용하기 위해서는 중심과 더불어 분산 및 각 집단의 사전 확률을 할당해줄 필요가 있다. 이 논문에서는, 하나의 집 단을 두 개로 분할한 경우 분산 행렬은 분할하기 전 집단의 분산 행렬로 동일하게 지정하였고, 집단의 사전 확률은 분할하기 이전 집단 값의 1/2로 두 집단에 동일하게 설정하였다・
이는 MX-means 알고리즘이 K-means 알고리즘을 통해 각 데이터 포인트를 하나의 집단에만 할당하는 hard clustering에 기인한 것으로 G-means의 경우도 마찬가지 이다. 이를 해결하기 위해서 다음 장에서는 K-means 알고리즘 대신 EM 알고리즘을 사용하여 하나의 데이터 포인트가 모든 집단에 속할 수 있는 soft clustering을 이용한 GX-means 알고리즘을 제안한다.
제안한 알고리즘들은 하나의 집단에서 시작하여 BIC 점 수를 증가시 키 는 집 단들을 반복적 으로 분할해나가는 하향식 wrapper 알고리즘으로, 주어진 집 단의 수 k에서 최적의 집단들을 찾아내기 위해 MX-means는 K-means 알고리즘을 사용하여 lard clustering을 수행하고 GX-means는 EM 알고리즘을 통해 soft clustering을 수행하는 점에서 다르다. 실험 결과에 나타나 있듯이 MX-means 알고리즘eK-means의 wrapper 알고리즘들중 가장 우수한 성능을 보였으며, GX-means는 비교 대상이 되는 모든 알고리즘중에서 가장 우수한 성능을 보였다, 또한 제안한 알고리즘들은여타의 파라미터를 필요로 하지 않는 장점이 있다.
따라서 line 11은 동일한 집단을 서로 다른 초기화 값을 통해 여러 번 나누어 보고 그 중BIC 점수를 최 대로 하는 분할을 선 택 한다. 초기 값의 설 정 은 X-means 의 경우 무작위로 집단의 중심을 두 개의 중심으로 나누었지 만, 여 기 서 는 PCA를 통해 데 이 터 가 분포되는 방향을 참고하여 중심을 분할하였다. 동일한 집단에 대한 분할 시 도 횟수는 데 이 터 의 차원으로 설정 되었다.

대상 데이터

두 알고리즘은 기본적으로 X-means와 마찬가지로 하나의 집 단에서 시 작하여 BIC 점수를 최대로 하는 집단의 분할을 반복적으로 시행해나가는 하향식 알고리즘이 다 집 단의 병 합을 이용하는 상향식 알고리즘들도여러가지 존재하지만, 상향식 알고리즘의 경우 최대 집단의 개수를 지정해 주어야 하며 하향식 알고리즘에 비해 초기 집단의 설정에 민감한 단점이 있다. 따라서 이 논문에서는 집단의 개수를 추정하는 기존의 하향식 알고리즘만을 대상으로 비교 실험하였다. 알려진 하향식 알고리즘으로는 X-means[2],

이론/모형

제안하였다. G-means 알고리즘은 Anderson-Darling 테스트(AD test)를 이용하여 국부적 인 가설, 즉 집 단을 이 루는 데 이 터 들이 하나의 가우시안 분포로부터 생성된 점들인지를 검사한다. 이 가설을 만족시키지 못하는 집단들은 K~means 알고리즘을 이용하여 두 개의 집단으로 분할하며, 이 과정은 집단들이 모두 AD 테스트를 만족할 때까지 반복적으로 시행된다.
Pelleg와 Mooi이2]가 제시한 X-meang 알고리즘은 일정 범위의 * 값에 대해 K-means 알고리즘을수행하고 각 결과를 BIC score[6, 기를 이용하여 평가한다. X-means 알고리즘의 기본적인 문제점은 모든 집단이 동일한 분산행렬을 가지며, 분산 행렬은 단위행렬의 상수배로 주어진다는 점이다.
X-means, G-means는 K-means의 wrapper 알 고리 즘이고 PG-means는 EM 알고리즘의 wrapper 알고리즘이며 BK-means는 가변 기법(variatkmal method)을 사용한다. 이 논문에서는 이들 알고리즘 중 K-means를 사용하는 G-mears와 기존의 알고리즘 중 가장 나은 성능을 보이는 BK-means를 그 비교 대상으로 실험 하였다.
그림 1은 MWmeans의 수행 과정을 나타낸 의사코드(pseudocode)이다. 하나의 집단이 두 개로 분할된 후에 각 집단에 할당되는 데이터들은 K-means 알고리즘을 통해 결정된다. MX-means 알고리즘은 G-means와 마찬가지로 하나의 집단을 두 개로 나눌 것인지를 국부적으로 결정한다.

성능/효과

제안한 알고리즘들은 하나의 집단에서 시작하여 BIC 점 수를 증가시 키 는 집 단들을 반복적 으로 분할해나가는 하향식 wrapper 알고리즘으로, 주어진 집 단의 수 k에서 최적의 집단들을 찾아내기 위해 MX-means는 K-means 알고리즘을 사용하여 lard clustering을 수행하고 GX-means는 EM 알고리즘을 통해 soft clustering을 수행하는 점에서 다르다. 실험 결과에 나타나 있듯이 MX-means 알고리즘eK-means의 wrapper 알고리즘들중 가장 우수한 성능을 보였으며, GX-means는 비교 대상이 되는 모든 알고리즘중에서 가장 우수한 성능을 보였다, 또한 제안한 알고리즘들은여타의 파라미터를 필요로 하지 않는 장점이 있다. 하지만 GX-means는 EM 알고리즘을 반복적으로 수행하는 구조로 인해 실행 속도가 느린 단점이 있으며, 비교 대상 알고리즘들중에서 가장 느리다.
C로 구현한 GX-means 알고리즘은 충분히 큰 데이터 집합이나 고차원의 데이터를 처리하는데 문제가 없지만, 다른 알고리즘과동일하게 Matlab 만으로 구현한 경우에는 속도에 문제가 있다. 실험 결과에서 알 수 있듯이, 집단들이 중첩되지 않게 분포하는 경우에는 MX-means 알고리 즘을사용하면 빠른 속도로 정확한 집단 구성이 가능하며, 집단들이 중첩되어 분포하는 경우에는 GX-means 알고리즘을통해 정확한 집 단 구성 이 가능하다.
means) [4], BK-means (Bayesian K-means)[5] 등이 있다. 제안한 두 알고리즘eX-means와G-means에 비해 나은 성능을 보였으며, 특히 GX-means는 다른 모든 알고리즘에 비해 비슷하거나 나은 성능을 보였다. 또한 MX-means, GX-means 알고리즘은 다른 알고리즘이 몇개의 파라미터 설정을 필요로 하는 것과 달리 추가적인 파라미터를 필요로 하지 않는 장점이 있다.
X-means 알고리즘이 효율적으로 데이터를 묘사하는 가우시안 컴포넌트의 개수를 추정할 수 있지만, X-means는 기본적 으로 모든 집 단들이 동일한 대각 행렬의 분산 행렬을 가진다고 가정함으로써 원형이 아닌 가우신안 컴포넌트의 경우 심각한 과대 적합(over-fitting)이 발생하는 문제 점 이 있다. 제안한 알고리 즘은 X-means와 마찬가지로 가우시 한 형 태 를 가지 는 집단의 개수와 파라미터 값을 자동으로 결정해 주지만, X-means의 분산 행 렬에 대한 제 한을 없 앰으로써 타원형의 가우시안 집 단에서 심각한 과대적 합이 발생하는 문제점을 해결한다. 또한 이들 알고리즘eX-means와 마찬가지로 각기 K-meanse]- EM(Expectation Maximization) 알고리즘의 wrapper 알고리즘이다 MX-means 는 K-means 알고리즘을 사용하여 현재 집단의 개수 k가 주어졌을 때 최적의 분할을 찾아낸다.

후속연구

GX・means는 하나의 집단을 분할하기 위해서 전역적으로 분할을 평가하고 있다. 하지만MX-means의 실험 결과에서 알 수 있듯이 국부적인 결정으로도 일정 수준 이상의 정확도는 얻어 낼 수 있으므로 국부적 인 분할 결정을 통해 상당 부분 연산량을줄일 수 있을 것으로 기대된다. 또한 중심을 분할하는 경우 분할을 시도하는 회수를 제 한하는 방법도 가능하다.

참고문헌 (9)

Christopher M. Bishop, Pattern Recognition and Machine Learning, Springer, 2006
Dan Pelleg and Andrew Moore, "X-means: Extending K-means with Efficient Estimation of the Number of Clusters," Proceedings of the 17th International Conference on Machine Learning, pp. 727-734, 2000
Greg Hamerly and Charles Elkan, "Learning the k in k-means," Proceedings of the 17th Annual Conference on Neural Information Processing Systems(NIPS-2003), pp. 281-288, 2003
Yu Feng and Greg Hamerly, "PG-means: learning the number of clusters in data," Proceedings of the 20th Annual Conference on Neural Information Processing Systems(NIPS-2006), pp. 393-400, 2006
Max Welling and Kenichi Kurihara, "Bayesian k-means as a 'maximization- expectation' algorithm," Proceedings of the 6th SIAM Conference on Data Mining, pp. 472-476, 2006
Robert E. Kass and Larry Wasserman, "A Reference Bayesian Test for Nested Hypotheses and Its Relationship to the Schwarz Criterion," Journal of the American Statistical Association, Vol.90, No.431, pp. 928-934, 1995

상세보기
Gideon Schwarz, "Estimating the Dimension of a Model," The Annals of Statistics, Vol.6, No.2, pp. 461-464, 1978

상세보기
J. Rissanen, "Modeling by shortest data description," Automatica, Vol.14, No.5, pp. 454-471, 1978
Sanjoy Dasgupta, "Experiments with Random Projection," Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence (UAI-2000), pp. 143-151, 2000

저자의 다른 논문 :

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

연합인증