Estimating the city-block two-dimensional scaling model with simulated annealing

摘要

Two-dimensional Scaling is a technique to represent dissimilarities among n objects in a two-dimensional space so that the interpoint distances can best approximate the observed dissimilarities between pairs of objects. The coordinates are found by minimizing the STRESS function. It is well known that the number of local minima of the STRESS function increase with n. In this paper, we present a new approach for finding the global minimum of the STRESS function for the city-block two-dimensional scaling model. The proposed method consists of two stages. While the least square regression is used to obtain the local minimum of the STRESS function in stage 1, simulated annealing is applied to search for the global minimum in stage 2. Real and simulated examples (n=30, 50, 70) are used to assess the performance of the proposed algorithm. Results show that the coordinates can be quite accurately recovered by the proposed method.