Journal of KIISE:Computer Systems and Theory (한국정보과학회논문지:시스템및이론)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지

A New Fast EM Algorithm

새로운 고속 EM 알고리즘

  • 김성수 (충북대학교 전기전자 및 컴퓨터공학부) ;
  • 강지혜 (충북대학교 전기전자 및 컴퓨터공학부)
  • Published : 2004.10.01
Download PDF
⟨ Previous Next ⟩

Abstract

In this paper. a new Fast Expectation-Maximization algorithm(FEM) is proposed. Firstly the K-means algorithm is modified to reduce the number of iterations for finding the initial values that are used as the initial values in EM process. Conventionally the Initial values in K-means clustering are chosen randomly. which sometimes forces the process of clustering converge to some undesired center points. Uniform partitioning method is added to the conventional K-means to extract the proper initial points for each clusters. Secondly the effect of posterior probability is emphasized such that the application of Maximum Likelihood Posterior(MLP) yields fast convergence. The proposed FEM strengthens the characteristics of conventional EM by reinforcing the speed of convergence. The superiority of FEM is demonstrated in experimental results by presenting the improvement results of EM and accelerating the speed of convergence in parameter estimation procedures.

본 논문은 여러 분야에서 활용될 수 있는 향상된 고속 Expectation-Maximization(FEM) 알고리즘을 제안한다. 첫째, EM의 초기값 설정의 방법으로 많이 사용되고 있는 클러스터링 기법인 K-means의 문제점을 해결하여 개선된 EM의 초기값 선정에 적용하였다. 이것은 기존 K-means 알고리즘에서 임의로 지정하던 랜덤한 초기값 선정을, 데이타 분포 특성을 이용한 균등 분할법을 사용하여 EM의 초기값 문제를 해결하였다. 둘째, EM 과정의 핵심을 이루는 후행 확률(Posterior)의 의미를 부각하여 최대 가능성 후행 확률(Maximum Likelihood Posterior: MLP)과정을 적용하였다. 최종적으로, 본 논문에서 제안한 고속 EM알고리즘(FEM)은 근본적으로 해결하기 못했던 기존의 EM 초기치 선정과 수렴에 대한 문제점을 개선함으로써, EM 알고리즘의 특성을 극대화하는 방향으로 상대적으로 마른 수렴과 향상된 결과를 가져온다. 제안된 알고리즘의 객관적 타당성을 위해 기존의 방법과 제안된 방법에 의한 시뮬레이션의 결과를 여러 데이타들을 가지고 비교 분석하여 제안한 알고리즘의 우수성을 입증하였다.

Keywords

References

  1. C. N. Schizas and C. S. Pattichis, 'Neural networks, genetic algorithms and the K-means algorithm: in search of data classification,' COGANN-92. International Workshop, pp. 201-222, Jun 1992 https://doi.org/10.1109/COGANN.1992.273938
  2. C.M. Bishop, Neural Networks for Pattern Recognition, Oxford University Press, 1995
  3. Wong Ching-Chang and Chen Chia-Chong, 'K-means-based fuzzy classifier design,' IEEE Fuzzy Systems International Conference, vol. 1, pp. 48-52, May 2000 https://doi.org/10.1109/FUZZY.2000.838632
  4. K. K. Paliwal and V. Ramasubramainan, 'Modified K-means algorithm for vector quantizer design,' IEEE Image Processing Trans, vol. 9 pp. 1964-1967, Nov 2000 https://doi.org/10.1109/83.877216
  5. Ian T. Nabney, NETLAB Algorithms for Pattern Recognition, Springer, 2001
  6. R.O. Duda and P.E. Hart, Pattern Classification, Willey, 2001
  7. Su Mu-Chun and Chou Chien-Hsing, 'A modified version of the K-means algorithm with a distance based on cluster symmetry,' IEEE Pattern Analysis and Machine Intelligence Trans, vol. 23, pp. 674-680, Jun 2001 https://doi.org/10.1109/34.927466
  8. A. P. Dempster, N.M. Laird, and D.B. Rubin, 'Maximum likelihood from incomplete data via the EM algorithm,' J. Royal Statisticla Soc., Set. B, vol. 39, no. 1, pp.1-38, 1977
  9. E. Redner & H. Walker, 'Mixture Densities, Maximum Likelihood and the EM Algorithms', SIAM Review, Vol.26, No.2, pp.195-239, Apr., 1984 https://doi.org/10.1137/1026034
  10. S. Zabin and H. Poor, 'Efficient estimation of class- A noise parameters via the EM algorithm,' IEEE Trans. Info T., vol. 37, no. 1, pp. 60-72, 1991 https://doi.org/10.1109/18.61127
  11. H. Chen, R. Perry, and K. Buckley, 'Direct and EM-based map sequence estimation with unknown time-varying channels,' Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, vol. 4, pp. 2129-2132, 2001 https://doi.org/10.1109/ICASSP.2001.940414
  12. R. A. Boyles, 'On the convergence of the EM algorithm,' J. Roy. Sta. B., vol. 45, no. 1, pp. 47-50, 1983
  13. C. Wu, 'On the convergence properties of the EM algorithm,' Ann. Statist., vol. 11. 1, pp. 95-103, 1983 https://doi.org/10.1214/aos/1176346060
  14. R. J. Kozick, B. M. Sadler, 'Maximum-likelihood array processing in non-Gaussian noise with Gaussian mixtures,' IEEE Trans. on Signal Processing, vol. 48, No. 12, pp. 3520-3535, 2000 https://doi.org/10.1109/78.887045