On interactive visualization of high-dimensional data using the hyperbolic plane

ABSTRACT

We propose a novel projection based visualization method for high-dimensional datasets by combining concepts from MDS and the geometry of the hyperbolic spaces. Our approach Hyperbolic Multi-Dimensional Scaling (H-MDS) extends earlier work [7] using hyperbolic spaces for visualization of tree structures data ( "hyperbolic tree browser" ).By borrowing concepts from multi-dimensional scaling we map proximity data directly into the 2-dimensional hyperbolic space (H2). This removes the restriction to "quasihierarchical", graph-based data -- limiting previous work. Since a suitable distance function can convert all kinds of data to proximity (or distance-based) data this type of data can be considered the most general.We used the circular Poincaré model of the H2 which allows effective human-computer interaction: by moving the "focus" via mouse the user can navigate in the data without loosing the "context". In H2 the "fish-eye" behavior originates not simply by a non-linear view transformation but rather by extraordinary, non-Euclidean properties of the H2. Especially, the exponential growth of length and area of the underlying space makes the H2 a prime target for mapping hierarchical and (now also) high-dimensional data.We present several high-dimensional mapping examples including synthetic and real world data and a successful application for unstructured text. By analyzing and integrating multiple film critiques from news:rec.art.movies.reviews and the internet movie database, each movie becomes placed within the H2. Here the idea is, that related films share more words in their reviews than unrelated. Their semantic proximity leads to a closer arrangement. The result is a kind of high-level content structured display allowing the user to explore the "space of movies".

REFERENCES

• 1: Trevor F. Cox and Micheal A. Cox. Multidimensional Scaling. Monographs on Statistics and Appied Probability. Chapman and Hall, 1994.
• 2: H.S.M. Coxeter. Non-Euclidean Geometry. University of Toronto Press, 1957.
• 3: J. deLeeuw and I. Stoop. An upper bound for SSTRESS. Psychometrika, 51:149--153, 1986.
• 4: J.A. Hartigan. Representation of similarity matrices by trees. J. Am. Statist, Ass., 62:1140--1158, 1967.
• 5: Hansjörg Klock , Joachim M. Buhmann, Multidimensional Scaling by Deterministic Annealing, Proceedings of the First International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, p.245-260, May 21-23, 1997
• 6: John Lamping , Ramana Rao , Peter Pirolli, A focus+context technique based on hyperbolic geometry for visualizing large hierarchies, Proceedings of the SIGCHI conference on Human factors in computing systems, p.401-408, May 07-11, 1995, Denver, Colorado, United States [doi>10.1145/223904.223956]
• 7: John Lamping , Ramana Rao, Laying out and visualizing large trees using a hyperbolic space, Proceedings of the 7th annual ACM symposium on User interface software and technology, p.13-14, November 02-04, 1994, Marina del Rey, California, United States [doi>10.1145/192426.192430]
• 8: Frank Morgan. Riemannian Geometry: A Beginner's Guide. Jones and Bartlett Publishers, 1993.
• 9: T. Munzner, H3: laying out large directed graphs in 3D hyperbolic space, Proceedings of the 1997 IEEE Symposium on Information Visualization (InfoVis '97), p.2, October 18-25, 1997
• 10: Tamara Munzner, Drawing Large Graphs with H3Viewer and Site Manager, Proceedings of the 6th International Symposium on Graph Drawing, p.384-393, August 01, 1998
• 11: Jörg Ontrup , Helge Ritter, Text Categorization and Semantic Browsing with Self-Organizing Maps on Non-euclidean Spaces, Proceedings of the 5th European Conference on Principles of Data Mining and Knowledge Discovery, p.338-349, September 03-05, 2001
• 12: Peter Pirolli , Stuart K. Card , Mija M. Van Der Wege, Visual information foraging in a focus + context visualization, Proceedings of the SIGCHI conference on Human factors in computing systems, p.506-513, March 2001, Seattle, Washington, United States [doi>10.1145/365024.365337]
• 13: William H. Press , Brian P. Flannery , Saul A. Teukolsky , William T. Vetterling, Numerical recipes in C: the art of scientific computing, Cambridge University Press, New York, NY, 1988
• 14: Kirsten Risden , Mary P. Czerwinski , Tamara Munzner , Daniel B. Cook, An initial examination of ease of use for 2D and 3D information visualizations of Web content, International Journal of Human-Computer Studies, v.53 n.5, p.695-714, Nov. 2000 [doi>10.1006/ijhc.2000.0413]
• 15: H. Ritter. Self-organizing maps on non-euclidean spaces. In S. Oja, E. & Kaski, editor, Kohonen Maps, pages 97--110. Elsevier, Amsterdam, 1999.
• 16: Gerard Salton , Christopher Buckley, Term-weighting approaches in automatic text retrieval, Information Processing and Management: an International Journal, v.24 n.5, p.513-523, 1988 [doi>10.1016/0306-4573(88)90021-0]
• 17: J. W. Sammon, Jr. A non-linear mapping for data structure analysis. IEEE Transactions on Computers, 18:401--409, 1969.
• 18: J.A. Thorpe. Elementary Topics in Differential Geometry. Springer Verlag, 1979.
• 19: William P. Thurston and Jeffrey R. Weeks. The mathematics of three-dimensional manifolds. Scientific American, July:94--107, 1984.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Interaction techniques

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Interaction styles (e.g., commands, menus, forms, direct manipulation)

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Visual

General Terms:
Algorithms, Measurement, Performance

Keywords:
H-MDS, focus+context, hyperbolic multi-dimensional scaling, infoViz, semantic browsing, text mining, visualizing high-dimensional data