IDEAS home Printed from https://ideas.repec.org/a/spr/mathme/v68y2008i3p429-443.html
   My bibliography  Save this article

A hybrid method for multidimensional scaling using city-block distances

Author

Listed:
  • Antanas Žilinskas
  • Julius Žilinskas

Abstract

The problem of multidimensional scaling with city-block distances in the embedding space is reduced to a two level optimization problem consisting of a combinatorial problem at the upper level and a quadratic programming problem at the lower level. A hybrid method is proposed combining randomized search for the upper level problem with a standard quadratic programming algorithm for the lower level problem. Several algorithms for the combinatorial problem have been tested and an evolutionary global search algorithm has been proved most suitable. An experimental code of the proposed hybrid multidimensional scaling algorithm is developed and tested using several test problems of two- and three-dimensional scaling. Copyright Springer-Verlag 2008

Suggested Citation

  • Antanas Žilinskas & Julius Žilinskas, 2008. "A hybrid method for multidimensional scaling using city-block distances," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 68(3), pages 429-443, December.
    • Handle: RePEc:spr:mathme:v:68:y:2008:i:3:p:429-443
    DOI: 10.1007/s00186-008-0238-5
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s00186-008-0238-5
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s00186-008-0238-5?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Lawrence Hubert & Phipps Arabie & Matthew Hesson-Mcinnis, 1992. "Multidimensional scaling in the city-block metric: A combinatorial approach," Journal of Classification, Springer;The Classification Society, vol. 9(2), pages 211-236, December.
    2. Phipps Arabie, 1991. "Was euclid an unnecessarily sophisticated psychologist?," Psychometrika, Springer;The Psychometric Society, vol. 56(4), pages 567-587, December.
    3. Alex Murillo & J. Fernando Vera & Willem J. Heiser, 2005. "A Permutation-Translation Simulated Annealing Algorithm for L 1 and L 2 Unidimensional Scaling," Journal of Classification, Springer;The Classification Society, vol. 22(1), pages 119-138, June.
    4. Jan Leeuw, 1984. "Differentiability of Kruskal's stress at a local minimum," Psychometrika, Springer;The Psychometric Society, vol. 49(1), pages 111-113, March.
    5. Michael J. Brusco, 2001. "A Simulated Annealing Heuristic for Unidimensional and Multidimensional (City-Block) Scaling of Symmetric Proximity Matrices," Journal of Classification, Springer;The Classification Society, vol. 18(1), pages 3-33, January.
    6. Leung, Pui Lam & Lau, Kin-nam, 2004. "Estimating the city-block two-dimensional scaling model with simulated annealing," European Journal of Operational Research, Elsevier, vol. 158(2), pages 518-524, October.
    7. Patrick Groenen & Rudolf Mathar & Willem Heiser, 1995. "The majorization approach to multidimensional scaling for Minkowski distances," Journal of Classification, Springer;The Classification Society, vol. 12(1), pages 3-19, March.
    8. P. J. F. Groenen & W. J. Heiser & J. J. Meulman, 1999. "Global Optimization in Least-Squares Multidimensional Scaling by Distance Smoothing," Journal of Classification, Springer;The Classification Society, vol. 16(2), pages 225-254, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Julius Žilinskas, 2012. "Parallel branch and bound for multidimensional scaling with city-block distances," Journal of Global Optimization, Springer, vol. 54(2), pages 261-274, October.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Julius Žilinskas, 2012. "Parallel branch and bound for multidimensional scaling with city-block distances," Journal of Global Optimization, Springer, vol. 54(2), pages 261-274, October.
    2. Groenen, P.J.F. & Borg, I., 2013. "The Past, Present, and Future of Multidimensional Scaling," Econometric Institute Research Papers EI 2013-07, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    3. Patrick Groenen & Willem Heiser, 1996. "The tunneling method for global optimization in multidimensional scaling," Psychometrika, Springer;The Psychometric Society, vol. 61(3), pages 529-550, September.
    4. Carrizosa, Emilio & Guerrero, Vanesa & Romero Morales, Dolores, 2018. "On Mathematical Optimization for the visualization of frequencies and adjacencies as rectangular maps," European Journal of Operational Research, Elsevier, vol. 265(1), pages 290-302.
    5. Michael Brusco & Hans-Friedrich Köhn & Stephanie Stahl, 2008. "Heuristic Implementation of Dynamic Programming for Matrix Permutation Problems in Combinatorial Data Analysis," Psychometrika, Springer;The Psychometric Society, vol. 73(3), pages 503-522, September.
    6. Andrew Webb, 1997. "Radial basis functions for exploratory data analysis: An iterative majorisation approach for Minkowski distances based on multidimensional scaling," Journal of Classification, Springer;The Classification Society, vol. 14(2), pages 249-267, September.
    7. Eva Ceulemans & Iven Mechelen & Iwin Leenen, 2007. "The Local Minima Problem in Hierarchical Classes Analysis: An Evaluation of a Simulated Annealing Algorithm and Various Multistart Procedures," Psychometrika, Springer;The Psychometric Society, vol. 72(3), pages 377-391, September.
    8. K. Van Deun & P. J. F. Groenen, 2005. "Majorization Algorithms for Inspecting Circles, Ellipses, Squares, Rectangles, and Rhombi," Operations Research, INFORMS, vol. 53(6), pages 957-967, December.
    9. J. Vera & Rodrigo Macías & Willem Heiser, 2009. "A Latent Class Multidimensional Scaling Model for Two-Way One-Mode Continuous Rating Dissimilarity Data," Psychometrika, Springer;The Psychometric Society, vol. 74(2), pages 297-315, June.
    10. Groenen, P.J.F. & Winsberg, S. & Rodriguez, O. & Diday, E., 2006. "I-Scal: Multidimensional scaling of interval dissimilarities," Computational Statistics & Data Analysis, Elsevier, vol. 51(1), pages 360-378, November.
    11. Kohn, Hans-Friedrich, 2006. "Combinatorial individual differences scaling within the city-block metric," Computational Statistics & Data Analysis, Elsevier, vol. 51(2), pages 931-946, November.
    12. Michael Brusco & Stephanie Stahl, 2001. "An interactive multiobjective programming approach to combinatorial data analysis," Psychometrika, Springer;The Psychometric Society, vol. 66(1), pages 5-24, March.
    13. Oliver Hinz & Jochen Eckert, 2010. "The Impact of Search and Recommendation Systems on Sales in Electronic Commerce," Business & Information Systems Engineering: The International Journal of WIRTSCHAFTSINFORMATIK, Springer;Gesellschaft für Informatik e.V. (GI), vol. 2(2), pages 67-77, April.
    14. Roland G. Fryer & Matthew O. Jackson, 2002. "Categorical Cognition: A Psychological Model of Categories and Identification in Decision Making," Microeconomics 0211002, University Library of Munich, Germany.
    15. Patrick Groenen & Rudolf Mathar & Willem Heiser, 1995. "The majorization approach to multidimensional scaling for Minkowski distances," Journal of Classification, Springer;The Classification Society, vol. 12(1), pages 3-19, March.
    16. Michael Brusco & Stephanie Stahl, 2005. "Optimal Least-Squares Unidimensional Scaling: Improved Branch-and-Bound Procedures and Comparison to Dynamic Programming," Psychometrika, Springer;The Psychometric Society, vol. 70(2), pages 253-270, June.
    17. Choulakian, Vartan, 2005. "Transposition invariant principal component analysis in L1 for long tailed data," Statistics & Probability Letters, Elsevier, vol. 71(1), pages 23-31, January.
    18. Eva Ceulemans & Iven Mechelen, 2008. "CLASSI: A classification model for the study of sequential processes and individual differences therein," Psychometrika, Springer;The Psychometric Society, vol. 73(1), pages 107-124, March.
    19. Eguia, Jon X., 2011. "Foundations of spatial preferences," Journal of Mathematical Economics, Elsevier, vol. 47(2), pages 200-205, March.
    20. Dirk Depril & Iven Mechelen & Tom Wilderjans, 2012. "Lowdimensional Additive Overlapping Clustering," Journal of Classification, Springer;The Classification Society, vol. 29(3), pages 297-320, October.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:mathme:v:68:y:2008:i:3:p:429-443. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.