Journal of KIISE:Computing Practices and Letters (한국정보과학회논문지:컴퓨팅의 실제 및 레터)

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

Non-Metric Multidimensional Scaling using Simulated Annealing

담금질을 사용한 비계량 다차원 척도법

  • 이창용 (공주대학교 산업시스템공학과) ;
  • 이동주 (공주대학교 산업시스템공학과)
  • Received : 2010.01.18
  • Accepted : 2010.03.29
  • Published : 2010.06.15
Download PDF
⟨ Previous Next ⟩

Abstract

The non-metric multidimensional scaling (nMDS) is a method for analyzing the relation among objects by mapping them onto the Euclidean space. The nMDS is useful when it is difficult to use the concept of distance between pairs of objects due to non-metric dissimilarities between objects. The nMDS can be regarded as an optimization problem in which there are many local optima. Since the conventional nMDS algorithm utilizes the steepest descent method, it has a drawback in that the method can hardly find a better solution once it falls into a local optimum. To remedy this problem, in this paper, we applied the simulated annealing to the nMDS and proposed a new optimization algorithm which could search for a global optimum more effectively. We examined the algorithm using benchmarking problems and found that improvement rate of the proposed algorithm against the conventional algorithm ranged from 0.7% to 3.2%. In addition, the statistical hypothesis test also showed that the proposed algorithm outperformed the conventional one.

비계량 다차원 척도법은 개체들 간의 비유사성이 비계량으로 주어져 개체들 간의 거리 개념을 설정하기 어려운 경우에 개체들을 유클리드 공간 상으로 사상하여 개체 간의 관련성을 연구하는 방법으로 지역 최적치가 많은 최적화 문제로 간주할 수 있다. 비계량 다차원 척도법을 위한 기존의 알고리즘은 최대 경사법을 사용함으로 일단 지역 최적치에 도달하면 더 이상 향상된 해를 찾기 어렵다는 단점이 있다. 이러한 단점을 해결하기 위하여 본 논문에서는 담금질 방법을 비계량 다차원 척도법에 접목하여 지역 최적치에 빠지지 않고 전역 최적치를 효율적으로 찾을 수 있는 새로운 비계량 다차원 척도법 알고리즘을 제안하였다. 제안한 알고리즘을 벤치마킹 문제에 적용하고 실험을 통하여 기존 알고리즘과 비교 분석한 결과, 제안한 알고리즘은 기존 알고리즘 대비 0.7%에서 3.2%의 향상률을 보였다. 또한 통계적 가설 검정을 통하여 제안한 알고리즘의 우수성을 입증하였다.

Keywords

References

  1. J. Lattin et al, Analyzing Multivariate Data, Thomson, Nelson, 2003.
  2. J. Kruskal "Multidimensional Scaling by Optimizing Goodness of Fit to a Nonmetric Hypothesis," Psychometrika, vol.29, pp.1-27, 1964. https://doi.org/10.1007/BF02289565
  3. J. Kruskal "Nonmetric Multidimensional Scaling," Psychometrika, vol.29, pp.115-129, 1964. https://doi.org/10.1007/BF02289694
  4. Y. H. Taguchi, and Y. Oono, "Relational patterns of gene expression via non-metric multidimensional scaling analysis," Bioinformatics, vol.21, pp. 730-740, 2005. https://doi.org/10.1093/bioinformatics/bti067
  5. M. Garey and D. Johnson, Computers and Intractability: A Guide to the theory of NP-completeness, New York, W. H. Freeman, 1979.
  6. I. Shmulevich and W. Zhang, "Binary analysis and optimization-based normalization of gene expression data," Bioinformatics, vol.18, pp.555-565, 2002. https://doi.org/10.1093/bioinformatics/18.4.555
  7. R. Shepard "The analysis of Proximities: Multidimensional Scaling with an unknown Distance Function," Psychometrika, vol.27, pp.125-140, 1962. https://doi.org/10.1007/BF02289630
  8. P. L. Leung and K. Lau, "Estimating the cityblock two-dimensional scaling model with simulated annealing," European Journal of Operational Research, vol.158, pp.518-524, 2004. https://doi.org/10.1016/S0377-2217(03)00357-6
  9. A. Zilinskas and J. Zilinskas, "On Multidimensional Scaling with Euclidean and City Block Metrics," Okio Technologinis Ir Ekonominis Vystymas, pp.69-75, 2006.
  10. S. W. Malone, P. Tarazaga, and M. W. Trosset, "Better initial configurations for metric multidimensional scaling," Computational Statistics & Data Analysis, vol.41, pp.143-156, 2002. https://doi.org/10.1016/S0167-9473(02)00145-7
  11. 박기용, 안성식, 정기용, "다차원척도법을 이용한 외식 기업 경쟁요인 비교분석에 관한 연구", 외식경영학회, vol.9, pp.93-114, 2006.
  12. 김철수, 정병두, 이원수, "공동주택 외부공간의 주거만족도 분석", 국토연구, vol.53, pp.277-294, 2007.
  13. D. B. Fogel, Evolutionary Computation: Toward a New Philosophy of Machine Intelligence, New York, IEEE Press, 1995.
  14. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by simulated annealing," Science, vol.220, pp.671-680, 1983. https://doi.org/10.1126/science.220.4598.671
  15. N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller, "Equation of state calculations for fast computing landscape," J. Chem. Phys., vol.2, pp.1087-1093, 1953.
  16. M. Newman, "The structure and function of complex networks," SIAM Rev., vol.45, pp.167-256, 2003. https://doi.org/10.1137/S003614450342480
  17. L. Chao, Statistics: Methods and Analyses, McGraw-Hill, N.Y., 1966.