Daugiamatės skalės daugiamačiams duomenims vizualizuoti

Eksperimentiniai mokslai surenka daug duomenų, kurie vėliau yra analizuojami įvairiais būdais. Dažnai norimoms žinioms išskirti iš duomenų matematiniai metodai turi būti derinami su tyrėjo patirtimi ir intuicija. Žmonių euristiniai sugebėjimai gerai išvystyti objektų analizei mažo matmenų skaičiaus - vienmatėje, dvimatėje ir trimatėje, erdvėje. Daugiamačių duomenų atvaizdavimas mažo matmenų skaičiaus erdvėje labai pagelbėja euristinei analizei. Daugiamatės skalės (DS) naudojamos daugiamačių duomenų struktūros analizei atvaizduojant juos dvimatėje arba trimatėje erdvėje. DS yra naudojamos daugelyje taikymų.

DS metodas sprendžia, kaip artumo duomenimis apibrėžti objektai gali būti patikimai atvaizduoti taškais mažo matmenų skaičiaus erdvėje. Objektų artumas yra apibrėžiamas jų porų skirtingumu. Ieškoma taškų mažo matmenų skaičiaus erdvėje, tarp kurių atstumai atitiktų duotus skirtingumus. Atvaizdavimo kokybė yra matuojama įtempimo funkcija, kuri lygina objektų skirtingumą ir atstumą tarp juos atvaizduojančių taškų. Objektų atvaizdžiai gali būti randami minimizuojant šią funkciją: turi būti rastos tokios taškų koordinatės, kad įtempimo funkcija būtų minimali. Dažniausiai DS naudojama Euklido norma. Tačiau DS su kitokiomis Minkovskio normomis sprendimo erdvėje gali būti informatyvesnės.

Įtempimo funkciją minimizuoti yra sudėtinga, kadangi yra daug lokalių minimumų taškų, o svarbu rasti globalų minimumą ir jį atitinkantį atvaizdį. Be to įtempimo funkcija yra invariantinė perkėlimui, sukimui ir atspindžiams, o kas blogiausia - ne visur diferencijuojama. Įtempimo funkcija su miesto kvartalų norma gali būti nediferencijuojama netgi minimumo taške. Dėl to tokios funkcijos minimizavimas yra ypač sudėtingas. Standartinių lokalių paieškų panaudojimas globalaus optimizavimo pagreitinimui yra netinkamas. Dviejų lygmenų algoritmas dvimatėms skalėms su miesto kvartalų norma buvo pasiūlytas. Vėliau šis algoritmas buvo apibendrintas daugiamačiam atvejui [1]. Algoritmas naudoja kombinatorinę globalią paiešką ir lokalią paiešką, sukurtą specialiai įtempimo funkcijai su miesto kvartalų norma išnaudojant dalimis kvadratinę tokios funkcijos struktūrą. Viršutinio lygmens uždavinio tikslo funkcija yra apibrėžta natūrinių skaičių kėlinių rinkinio aibėje. Kombinatorinis uždavinys gali būti sprendžiamas įvairiais algoritmais, pavyzdžiui pilnu perrinkimu, šakų ir rėžių algoritmu, evoliucine paieška. Šiame projekte buvo sukurtas šakų ir rėžių algoritmas daugiamatėms skalėms [2].

Kadangi DS yra sudėtingi globalaus optimizavimo uždaviniai, jų sprendimas reikalauja nemažai laiko [3]. Panaudojant lygiagrečiuosius skaičiavimus, sprendimo laikas gali būti sutrumpintas ir didesni uždaviniai išspręsti. Buvo sukurtas lygiagretusis šakų ir rėžių algoritmas daugiamatėms skalėms [4]. Algoritmu garantuotai išspręsti daugiamačių skalių uždavinius atitinkantys globaliojo optimizavimo uždaviniai su nediferencijuojama tikslo funkcija ir iki 27 kintamųjų.

  1. J. Žilinskas (2008) On dimensionality of embedding space in multidimensional scaling. Informatica, ISSN 0868-4952, 19(3), 447-460. [Abstracted/Indexed in ISI Web of Science, Academic Search Complete, Inspec, Zentralblatt MATH]
  2. A. Žilinskas, J. Žilinskas (2009) Branch and bound algorithm for multidimensional scaling with city-block metric. Journal of Global Optimization, ISSN 0925-5001, 43(2-3), 357-372. doi:10.1007/s10898-008-9306-x [Abstracted/Indexed in ISI Web of Science, SpringerLink, Zentralblatt MATH]
  3. J. Žilinskas (2009) Parallel global optimization in multidimensional scaling. In: R. Čiegis, D. Henty, B. Kågström, J. Žilinskas (Eds.), Parallel Scientific Computing and Optimization. Vol. 27 of Springer Optimization and Its Applications, Springer, ISSN 1931-6828, pp. 69-82. doi:10.1007/978-0-387-09707-7_6 [Abstracted/Indexed in ISI Web of Science (Conference Proceedings Citation Index), SpringerLink, Inspec, Zentralblatt MATH. Preview at Google Books]
  4. J. Žilinskas. Parallel branch and bound algorithm for multidimensional scaling with city-block distances. Mathematical Modelling and Analysis, ISSN 1392-6292. Įteiktas

Bylos atsisiuntimui

post date title description download
08.18.2009 Programos Šakų ir rėžių algoritmas daugiamatėms skalėms DaugiamatesSkalesBB.tgz