Cluster Analysis via Stochastic Approximation Monte Carlo

다국어 초록 (Multilingual Abstract)

The k-means clustering is one of the simplest unsupervised algorithm used generally in solving clustering problems. However, it may rely on the initial cluster seed and thus it is suffer from the local trap problem due to that its system has multiple local energy minima in a rugged energy landscape. Hence, the global optimal clustering may not be identified. This paper focuses on this problem, and thus we propose to use the Stochastic approximation Monte Carlo(SAMC) algorithm implementing the k-means clustering method to overcome the local trap problem in clustering analysis. SAMC is a general importance sampling and optimization algorithm to search the sample space broadly and escape from the local trap problem regardless of the initial point. The algorithm is tested on simulated and the real dataset, and compared with the k-means clustering algorithm. The numerical results are in favor of SAMC based on the minimization criterion.

참고문헌 (Reference)

1 강현철, "웹유시지 패턴 분류를 위한 군집분석 알고리즘" 한국자료분석학회 5 (5): 337-344, 2003

2 박희창, "사회지표조사 자료의 K-평균 군집분석" 한국자료분석학회 7 (7): 465-476, 2005

3 김승구, "마이크로어레이 유전자 군집분석에서 평활성분평균을 이용한 이상표본 식별" 한국자료분석학회 8 (8): 573-583, 2006

4 Atchad´e, Y. F, "The Wang-Landau algorithm in general state spaces: applications and convergence analysis" Department of Statistics, University of Michigan 2007

5 Liang, F, "Stochastic approximation in Monte Carlo computation" 102 : 305-320, 2007

6 Marinari, E, "Simulated tempering: A new Monte Carlo scheme" 451-458, 1992

7 Mitsutake, A, "Replica-exchange multicanonical and multicanonical replica exchange Monte Carlo simulations of peptides. I. Formula and benchmark test" 118 : 6676-6688, 2003

8 Wong, W. H, "Proceedings of the National Academy of Sciences USA" 14220-14224, 1997

9 Berg, B. A, "Multicanonical algorithms for 1st order phase-transitions" 249-253, 1991

10 Hesselbo, B, "Monte Carlo simulation and global optimization without parameters" 2151-2155, 1995

11 Hastings, W. K, "Monte Carlo sampling methods using Markov chains and their applications" 57 : 97-109, 1970

12 반성수, "Metastasis Related Gene Exploration Using TwoStep Clustering for Medulloblastoma Microarray Data" 한국자료분석학회 10 (10): 1227-1238, 2008

13 Geyer, C. J, "Markov chain Monte Carlo maximum likelihood, in Computing Science and Statistics" Interface Foundation 156-163, 1991

14 Liang, F, "Generalized Wang-Landau algorithm for Monte Carlo Computation" 100 : 1311-1327, 2005

15 Hukushima, K, "Exchange Monte Carlo method and application to spin glass simulations" 65 : 1604-1608, 1996

16 Liang, F, "Evolutionary Monte Carlo sampling: applications to Cp model sampling and change-point problem" 10 : 317-342, 2000

17 Kou, S. C, "Equi-energy sampler with applications to statistical inference and statistical mechanics (with discussion)" 34 : 1581-1619, 2006

18 Metropolis, N, "Equation of state calculations by fast computing machines" 21 : 1087-1091, 1953

19 Wang, F, "Efficient, multiple-range random walk algorithm to calculate the density of states" 2050-2053, 2001

20 Hartigan, J. A, "Clustering Algorithm" John Wiley & Sons 1975

21 Geyer, C. J, "Annealing Markov chain Monte Carlo with applications to ancestral inference" 90 : 909-920, 1995

22 Jin, S, "A study on the partitioning method for cluster analysis" Korea University 1999