×
Sun, Jigang; Crowe, Malcolm; Fyfe, Colin

Extending metric multidimensional scaling with Bregman divergences. (English) Zbl 1209.68486

Pattern Recognition 44, No. 5, 1137-1154 (2011).
Summary: Sum of weighted square distance errors has been a popular way of defining stress function for metric multidimensional scaling (MMDS) like the Sammon mapping. In this paper we generalise this popular MMDS with Bregman divergences; as an example we show that the Sammon mapping can be thought of as a truncated Bregman MMDS (BMMDS). We also show that the full BMMDS improves upon the Sammon mapping on some standard data sets and investigate the reasons underlying this improvement. We then extend with BMMDS a well known family of MMDS that deploy a strategy of focusing on small distances, and we empirically investigate limitations of the strategy. Then an opposite strategy is introduced to create another family of BMMDS that gives increasing mapping quality. A data preprocessing method and a distance matrix preprocessing are introduced.

Cited in 2 Documents

MSC:

68T10 Pattern recognition, speech recognition

Keywords:

multidimensional scaling; Sammon mapping; Bregman divergence; distance matrix preprocessing; strategy focusing on small distances; stress function definition

Software:

XGvis
Cite Review PDF
Full Text: DOI

References:

[1] Banerjee, A.; Merugu, S.; Dhillon, I. S.; Ghosh, J., Clustering with Bregman divergences, Journal of Machine Learning Research, 6, 1705-1749 (2005) · Zbl 1190.62117
[2] I. Borg, P.J.F. Groenen, Modern Multidimensional Scaling, second ed., Springer, New York, 2005.; I. Borg, P.J.F. Groenen, Modern Multidimensional Scaling, second ed., Springer, New York, 2005. · Zbl 1085.62079
[3] Buja, A.; Swayne, D. F., Visualization methodology for multidimensional scaling, Journal of Classification, 2002, 19 (2001) · Zbl 1137.91603
[4] L. Chen, A. Buja, Local multidimensional scaling for nonlinear dimension reduction, graph drawing and proximity analysis, Ph.D. Thesis, University of Pennsylvania, 2006.; L. Chen, A. Buja, Local multidimensional scaling for nonlinear dimension reduction, graph drawing and proximity analysis, Ph.D. Thesis, University of Pennsylvania, 2006. · Zbl 1388.62182
[5] Child, D., The Essentials of Factor Analysis (1973), Rinehart and Winston: Rinehart and Winston London, Holt
[6] Demartines, P.; Hérault, J., Curvilinear component analysis: a self-organizing neural network for nonlinear mapping of data sets, IEEE Transactions on Neural Networks, 8, 1 (1997)
[7] C. Fyfe, Data visualization using Bregman divergences, Computing and Information Systems Technical Reports, November 2008.; C. Fyfe, Data visualization using Bregman divergences, Computing and Information Systems Technical Reports, November 2008.
[8] Hotelling, H., Analysis of a complex of statistical variables into principal components, Journal of Educational Psychology, 24, 417-441 (1933) · JFM 59.1182.04
[9] J. Hérault, C. Jausions-Picaud, A. Guérin-Dugué, Curvilinear component analysis for high-dimensional data representation: I. Theoretical aspects and practical use in the presence of noise, in: IWANN, vol. 2, 1999, pp. 625-634.; J. Hérault, C. Jausions-Picaud, A. Guérin-Dugué, Curvilinear component analysis for high-dimensional data representation: I. Theoretical aspects and practical use in the presence of noise, in: IWANN, vol. 2, 1999, pp. 625-634.
[10] Mao, J.; Jain, A. K., Artificial neural networks for feature extraction and multivariate data projection, IEEE Transactions on Neural Networks, 6, 2, 296-317 (1995)
[11] Sammon, J., A nonlinear mapping for data structure analysis, IEEE Transactions on Computing, 18 (1969)
[12] Kohonen, T.; Schroeder, M. R.; Huang, T. S., Self-Organizing Maps (2001), Springer-Verlag New York, Inc.: Springer-Verlag New York, Inc. Secaucus, NJ, USA · Zbl 0957.68097
[13] Lee, J. A.; Verleysen, M., Nonlinear Dimensionality Reduction (2007), Springer: Springer Berlin · Zbl 1128.68024
[14] Lee, R. C.T.; Slagle, J. R.; Blum, H., A triangulation method for sequential mapping of points from n-space to two-space, IEEE Transactions on Computers, 6, 288-292 (1977)
[15] E. Pekalska, D. de Ridder, R.P.W. Duin, M.A. Kraaijveld, A new method of generalizing Sammon mapping with application to algorithm speed-up, in: 5th Annual Conference of the Advanced School for Computing and Imaging, ASCI, 1999, pp. 221-228.; E. Pekalska, D. de Ridder, R.P.W. Duin, M.A. Kraaijveld, A new method of generalizing Sammon mapping with application to algorithm speed-up, in: 5th Annual Conference of the Advanced School for Computing and Imaging, ASCI, 1999, pp. 221-228.
[16] Roweis, S. T.; Saul, L. K., Nonlinear dimensionality reduction by locally linear embedding, Science, 290, 2323-2326 (2000)
[17] J. Sun, M. Crowe, C. Fyfe, Curvilinear component analysis and Bregman divergences, in: European Symposium on Artificial Neural Networks, d-side Publications, 2010, pp. 81-86.; J. Sun, M. Crowe, C. Fyfe, Curvilinear component analysis and Bregman divergences, in: European Symposium on Artificial Neural Networks, d-side Publications, 2010, pp. 81-86.
[18] J. Sun, M. Crowe, C. Fyfe, Extending metric multidimensional scaling with bregman divergences, in: N. García-Pedrajas, F. Herrera, C. Fyfe, J.M. Benítez, M. Ali, (Eds.), Trends in Applied Intelligent Systems, Lecture Notes in Computer Science, vol. 6097, Springer, 2010, pp. 615-626.; J. Sun, M. Crowe, C. Fyfe, Extending metric multidimensional scaling with bregman divergences, in: N. García-Pedrajas, F. Herrera, C. Fyfe, J.M. Benítez, M. Ali, (Eds.), Trends in Applied Intelligent Systems, Lecture Notes in Computer Science, vol. 6097, Springer, 2010, pp. 615-626. · Zbl 1209.68486
[19] Tenenbaum, J. B.; Silva, V.; Langford, J. C., A global geometric framework for nonlinear dimensionality reduction, Science, 290, 5500, 2319-2323 (2000)
[20] L. Yang, Sammon’s nonlinear mapping using geodesic distances, in: Proceedings of the 17th International Conference on Pattern Recognition, ICPR’04, vol. 2, IEEE Computer Society, Washington, DC, USA, 2004, pp. 303-306.; L. Yang, Sammon’s nonlinear mapping using geodesic distances, in: Proceedings of the 17th International Conference on Pattern Recognition, ICPR’04, vol. 2, IEEE Computer Society, Washington, DC, USA, 2004, pp. 303-306.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.