UPDis: A user-assisted projection technique for distance information

Abstract

Multidimensional projection techniques have become essential analytical tools. Typically, they map data from a high-dimensional space into a low-dimensional visual space, preserving distance or neighborhood structures on the produced layout. Despite the advances, with faster and highly precise techniques, existing methods still carry deficiencies that impair their use as exploratory tools. An example is the mismatching that can occur between what the user considers similar/dissimilar and what is conveyed by the visual representation. Recently, a class of projection techniques aims at addressing this limitation, allowing users to control the projection process by changing the distance relationships using small data samples. Among such methods, Local Affine Multidimensional Projection has proved to be the state-of-the-art regarding the effectiveness of user intervention. Although Local Affine Multidimensional Projection has attained a relative success, it is limited to certain application domains. Since it relies on feature vector representations with data instances described by vectors embedded into a Euclidean space, scenarios that offer only distance information or a distance function cannot be handled. In this article, we present a novel multidimensional projection technique, called User-assisted Projection Technique for Distance Information, which takes advantage of the solid mathematical framework provided by Local Affine Multidimensional Projection, adapting it to scenarios where only distance information or a distance function is available. The results show that User-assisted Projection Technique for Distance Information is as fast, accurate, robust, and flexible as the existing state-of-the-art techniques, enabling the application of the refined user control provided by Local Affine Multidimensional Projection on domains not previously covered. Its versatility is illustrated in an application that involves the organization of book collections that employs an external source of information for the recommendation of new readings.

Keywords

Multidimensional projection distance-based projection visual recommendation application

Get full access to this article

View all access options for this article.

References

Tejada

Minghim

Nonato

. On improved projection techniques to support visual exploration of multidimensional data sets. Inform Visual 2003; 2(4): 218–231.

Paulovich

Silva

Nonato

. Two-phase mapping for projecting massive data sets. IEEE T Vis Comput Gr 2010; 16(6): 1281–1290.

Paulovich

Silva

Nonato

. User-centered multidimensional projection techniques. Comput Sci Eng 2012; 14(4): 74–81.

Joia

Coimbra

Cuminato

. Local affine multidimensional projection. IEEE T Vis Comput Gr 2011; 17: 2563–2571.

De Silva

Tenenbaum

. Sparse multidimensional scaling using landmark points. Technical report, Stanford University, Stanford, CA, 2004.

Jolliffe

. Principal component analysis. New York: John Wiley & Sons, 2005, pp. 1580–1584.

Torgerson

. Multidimensional scaling: I. Theory and method. Psychometrika 1952; 17(4): 401–419.

Van der Maaten

Postma

van den Herik

. Dimensionality reduction: a comparative review. Technical report 2009-005, Tilburg University, Tilburg, 26October2009.

Sammon

. A nonlinear mapping for data structure analysis. IEEE T Comput 1969; 18(5): 401–409.

10.

Hinton

Roweis

. Stochastic neighbor embedding. In: Becker

Thrun

Obermayer

(eds) Neural information processing systems. London: MIT Press, 2003, pp. 857–864.

11.

Van der Maaten

Hinton

. Visualizing data using t-SNE. J Mach Learn Res 2008; 9: 2579–2605.

12.

Venna

Peltonen

Nybo

. Information retrieval perspective to nonlinear dimensionality reduction for data visualization. J Mach Learn Res 2010; 11: 451–490.

13.

Faloutsos

Lin

. FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets. In: Proceedings of the ACM SIGMOD international conference on management of data, San Jose, CA, 22–25 May 1995, pp. 163–174. New York: ACM.

14.

Platt

. FastMap, MetricMap, and landmark MDS are all nystrom algorithms. In: Proceedings of the tenth international workshop on artificial intelligence and statistics, Bridgetown, Barbados, 6–8 January 2005, pp. 261–268, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.59.8082&rep=rep1&type=pdf

15.

Chalmers

. A linear iteration time layout algorithm for visualising high-dimensional data. In: Proceedings of the 7th conference on visualization, San Francisco, CA, 28–29 October 1996, pp. 127–ff. New York: IEEE.

16.

Paulovich

Nonato

Minghim

. Least square projection: a fast high-precision multidimensional projection technique and its application to document mapping. IEEE T Vis Comput Gr 2008; 14(3): 564–575.

17.

Morrison

Ross

Chalmers

. A hybrid layout algorithm for sub-quadratic multidimensional scaling. In: Proceedings of the IEEE symposium on information visualization (InfoVis’02), Boston, MA, 28–29 October 2002, pp. 152–158. New York: IEEE.

18.

Pekalska

de Ridder

Duin

RPW

. A new method of generalizing Sammon mapping with application to algorithm speed-up. In: Proceedings of the annual conferences advanced school for computer and imaging, Heijen, The Netherlands, 15–17 June 1999, pp. 221–228. Delft: ASCI.

19.

Cox

MAA

. Multidimensional scaling. 2nd ed. Boca Raton, FL: Chapman & Hall/CRC, 2000.

20.

Jackson

. Stopping rules in principal components analysis: a comparison of heuristical and statistical approaches. Ecology 1993; 74(8): 2204–2214.

21.

Paulovich

Eler

Poco

. Piecewise Laplacian-based projection for interactive data exploration and organization. Comput Graph Forum 2011; 30(3): 1091–1100.

22.

Bache

Lichman

. UCI machine learning repository, 2013, http://archive.ics.uci.edu/ml

23.

Poco

Eler

Paulovich

. Employing 2d projections for fast visual exploration of large fiber tracking data. In: Computer Graphics Forum. (Vol. 31, No. 3pt2, pp. 1075–1084). Blackwell Publishing Ltd, 1 June 2012.

24.

Shneiderman

Seo

. Hierarchical clustering explorer for interactive exploration of multidimensional data, 2008, http://goo.gl/cnPR47

25.

Kruskal

. Nonmetric multidimensional scaling: a numerical method. Psychometrika 1964; 29(2): 115–129.

26.

Tan

Steinbach

Kumar

. Introduction to data mining. 1st ed.Boston, MA: Addison-Wesley, 2005.

27.

Fadel

Fatore

Duarte

. Loch: a neighborhood-based multidimensional projection technique for high-dimensional sparse spaces. Neurocomputing 2014; 150: 546–556.

28.

Paulovich

Minghim

. HiPP: a novel hierarchical point placement strategy and its application to the exploration of document collections. IEEE T Vis Comput Gr 2008; 14(6): 1229–1236.