nips nips2002 nips2002-117 nips2002-117-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Balázs Kégl
Abstract: We propose a new algorithm to estimate the intrinsic dimension of data sets. The method is based on geometric properties of the data and requires neither parametric assumptions on the data generating model nor input parameters to set. The method is compared to a similar, widelyused algorithm from the same family of geometric techniques. Experiments show that our method is more robust in terms of the data generating distribution and more reliable in the presence of noise. 1
[1] T. Kohonen, The Self-Organizing Map, Springer-Verlag, 2nd edition, 1997.
[2] T. F. Cox and M. A. Cox, Multidimensional Scaling, Chapman & Hill, 1994.
[3] S. Roweis and Saul L. K., “Nonlinear dimensionality reduction by locally linear embedding,” Science, vol. 290, pp. 2323–2326, 2000.
[4] J. B. Tenenbaum, V. de Silva, and Langford J. C., “A global geometric framework for nonlinear dimensionality reduction,” Science, vol. 290, pp. 2319–2323, 2000.
[5] E. Ch´ avez, G. Navarro, R. Baeza-Yates, and J. Marroqu´ “Searching in metric spaces,” ACM ın, Computing Surveys, p. to appear, 2001.
[6] J. Bruske and G. Sommer, “Intrinsic dimensionality estimation with optimally topology preserving maps,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 20, no. 5, pp. 572–575, 1998.
[7] S. Roweis, “EM algorithms for PCA and SPCA,” in Advances in Neural Information Processing Systems. 1998, vol. 10, pp. 626–632, The MIT Press.
[8] C. M. Bishop, M. Svens´ and C. K. I. Williams, “GTM: The generative topographic mapping,” en, Neural Computation, vol. 10, no. 1, pp. 215–235, 1998.
[9] P. Grassberger and I. Procaccia, “Measuring the strangeness of strange attractors,” Physica, vol. D9, pp. 189–208, 1983.
[10] F. Camastra and A. Vinciarelli, “Estimating intrinsic dimension of data with a fractal-based approach,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, to appear.
[11] A. Belussi and C. Faloutsos, “Spatial join selectivity estimation using fractal concepts,” ACM Transactions on Information Systems, vol. 16, no. 2, pp. 161–201, 1998.
[12] J. Hastad, “Clicque is hard to approximate within n 1−ε ,” in Proceedings of the 37th Annual Symposium on Foundations of Computer Science FOCS’96, 1996, pp. 627–636.
[13] T. Erlebach, K. Jansen, and E. Seidel, “Polynomial-time approximation schemes for geometric graphs,” in Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms SODA’01, 2001, pp. 671–679.