On multidimensional scaling with Euclidean and city block metrics

Abstract

Experimental sciences collect large amounts of data. Different techniques are available for information elicitation from data. Frequently statistical analysis should be combined with the experience and intuition of researchers. Human heuristic abilities are developed and oriented to patterns in space of dimensionality up to 3. Multidimensional scaling (MDS) addresses the problem how objects represented by proximity data can be represented by points in low dimensional space. MDS methods are implemented as the optimization of a stress function measuring fit of the proximity data by the distances between the respective points. Since the optimization problem is multimodal, a global optimization method should be used. In the present paper a combination of an evolutionary metaheuristic algorithm with a local search algorithm is used. The experimental results show the influence of metrics defining distances in the considered spaces on the results of multidimensional scaling. Data sets with known and unknown structure and different dimensionality (up to 512 variables) have been visualized.

Daugiamačių skalių su Euklido ir Manheteno metrikomis sudarymo metodai

Santrauka. Eksperimentiniai mokslai kaupia didelius duomenų kiekius. Sukurta daug metodų informacijai iš duomenų išgauti. Daûnai statistiniai metodai yra derinami su euristine analize pagrįsta tyrinėtojų intuicija. Tačiau euristiniai žmonių sugebėjimai gerai tinka analizuoti duomenis, kurių matavimų skaičius neviršija 3. Daugiamačių skalių metodas skirtas vaizduoti objektams mažo matavimų skaičiaus erdvėje, kai objektai apibrėžti panašumais/nepanašumais, o atstumai vaizdų erdvėje vaizduoja nepanašumus. Daugiamačių skalių metodai sudaromi kaip vaizdavimo tikslumo kriterijaus, paprastai vadinamo stresu, minimizavimo procedūros. Kadangi optimizavimo uždaviniai daugiaekstremalūs, jiems spręsti reikia globalios optimizacijos metodų. Šiame darbe pasiūlytas algoritmas, jungiantis metaeuristinę globalią paiešką ir lokalios minimizacijos metodą. Eksperimentais ištirta metrikos vaizdų erdvėje įtaka vaizdavimo tikslumui ir algoritmo efektyvumui. Eksperimentuose naudotos duomenų aibės su žinoma ir nežinoma struktūra; optimizacijos uždavinio kintamųjų yra iki 512.

Reikšminiai žodžiai: daugiadimensės skalės, globalioji optimizacija, metaeuristiniai metodai, Manheteno metrika, daugiamačių duomenų vizualizacija.

First Published Online: 21 Oct 2010

Keyword : Multidimensional scaling, global optimization, metaheuristics, city block metrics, visualization of multidimensional data