City-Block Scaling: Smoothing Strategies for Avoiding Local Minima

Abstract

Multidimensional scaling (MDS) with city-block distances suffers from many local minima if the Stress function is minimized In fact, the problem can be viewed as a combinatorial problem, where finding the correct order of the coordinates on a dimension is crucial for attaining the minimum. Several strategies have been proposed for arriving at a global minimum of the Stress function. We pay particular attention to Pliner’s (1996) smoothing strategy for unidimensional scaling, which smoothes the concave part of the Stress function. We discuss three extensions of this strategy to the multidimensional case with city-block distances. The first extension is shown to lead to problems because it yields a unidimensional solution. A second extension, proposed by Pliner (1986), and a third extension, distance smoothing introduced here, do not have this problem. Numerical experiments with the smoothing strategy have been limited to the unidimensional case. Therefore, we present a comparison study using real data, which shows that the smoothing strategy performs better than three other strategies considered.

Supported by The Netherlands Organization for Scientific Research (NWO) by grant nr. 030-56-403 for the ‘PIONEER’ project ‘Subject Oriented Multivariate Analysis’.