Выбор способа декомпозиции пространства признаков для нелинейного снижения размерности
Мясников Е.В.

Самарский государственный аэрокосмический университет имени академика С.П. Королёва
(национальный исследовательский университет) (СГАУ),

Институт систем обработки изображений РАН

Аннотация:
В работе рассматриваются два подхода к иерархической декомпозиции пространства признаков для повышения эффективности нелинейного метода снижения размерности. Первый подход, предложенный автором настоящей работы, основывается на декомпозиции исходного пространства признаков с использованием иерархической кластеризации. Второй оригинальный подход основывается на иерархической декомпозиции целевого пространства с использованием KD-деревьев. Анализируемые подходы оцениваются с точки зрения эффективности работы нелинейного метода снижения размерности.

Ключевые слова :
снижение размерности, декомпозиция пространства признаков, иерархическая кластеризация, KD-деревья.

Литература:

  1. Hiroike, A. Visualization of information spaces to retrieve and browse image data / A. Hiroike, Y. Musha, A. Sugimoto, Y. Mori // Proceedings of the Third International Conference on Visual Information and Information Systems (VISUAL'99). Lecture Notes in Computer Science. – Springer, 1999. – Vol. 1614. – P. 155-162.
  2. Мясников, Е.В. Навигация по коллекциям цифровых изображений на основе методов автоматической классификации / Е.В. Мясников // Интернет-Математика 2007: cб. работ. – Екатеринбург: Изд-во Урал. ун-та, 2007. – C. 144-152. (Myasnikov, E.V. Digital image collection navigation based on automatic classification methods / E.V. Myasnikov // Internet-Mathematics 2007: Collected papers. – Ekaterinburg, Russia, 2007. – P. 144-152. – (In Russian).)
  3. Rodden, K. Evaluating Similarity-Based Visualisations As Interfaces For Image Browsing / K. Rodden. – Technical Report. – University of Cambridge, Computer Laboratory, 2002. – 248 p.
  4. Rose, T. ANVIL: a system for the retrieval of captioned images using NLP techniques / T. Rose, D. Elworthy, A. Kotcheff, A. Clare, P. Tsonis // The Challenge of Image Retrieval. Electronic Workshops in Computing, 2000.
  5. Rubner, Y. Adaptive color-image embeddings for database navigation / Y. Rubner, C. Tomasi, L.J. Guibas // Proceedings of the IEEE Asian Conference on Computer Vision, 1998. – P. 104-111.
  6. Kruskal, J.B. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis / J.B. Kruskal // Psychometrika. – 1964. – Vol. 29. – P. 1-27.
  7. Sammon, J.W., Jr. A nonlinear mapping for data structure analysis / J.W. Sammon, Jr. // IEEE Transactions on Computers. – 1969. – Vol. C-18, Issue 5. – P. 401-409.
  8. Calvert, T.W. Randomly Generated Nonlinear Transformations for Pattern Recognition / T.W. Calvert, T.Y. Young // IEEE Transactions on Systems Science and Cybernetics. – 1969. – Vol. 5. – P. 266-273.
  9. De Leeuw, J. Applications of convex analysis to multidimensional scaling / J. De Leeuw, J.R. Barra, F. Brodeau, G. Romie [et al.] // Recent developments in statistics. – 1977. – P. 133-145.
  10. Lee, J.A. Nonlinear Dimensionality Reduction / J.A. Lee, M. Verleysen. – Springer, 2007.
  11. Eades, P. A Heuristic for Graph Drawing / P. Eades // Congressus Numerantium. – 1984. – Vol. 42. – P. 149-160.
  12. Fruchterman, T. Graph Drawing by Force-directed Placement / T. Fruchterman, E. Reingold // Software – Practice and Experience. – 1991. – Vol. 21, Issue 11. – P. 1129-1164.
  13. Kamada, T. An Algorithm for Drawing General Undirected Graphs / T. Kamada, S. Kawai // Information Processing Letters. – 1989. – Vol. 31. – P. 7-15.
  14. Lee, R.C.T. A Triangulation Method for the Sequential Mapping of Points from N-Space to Two-Space / R.C.T. Lee, J.R. Slagle, H. Blum // IEEE Transactions on Computers. – 1977. – Vol. 26, Issue 3. – P. 288-292.
  15. Pekalska, E. A new method of generalizing Sammon mapping with application to algorithm speed-up / E. P"ekalska, D. de Ridder, R.P.W. Duin, M.A. Kraaijveld // Proc. ASCI'99, 5th Annual Conf. of the Advanced School for Computing and Imaging. – Heijen, The Netherlands: 1999, June 15-17. – P. 221-228.
  16. Chalmers, M. A Linear Iteration Time Layout Algorithm for Visualizing High–Dimensional Data / M. Chalmers // Proc. IEEE Visualization `96. – San Francisco, 1996. – P. 127-132.
  17. Morrison, A. Fast Multidimensional Scaling Through Sampling, Springs and Interpolation / A. Morrison, G. Ross, M. Chalmers // Information Visualization. – 2003. – Vol. 2. – P. 68-77.
  18. Myasnikov, E.V. A Nonlinear Method for Dimensionality Reduction of Data Using Reference Nodes / E.V. Myasnikov // Pattern Recognition and Image Analysis. – 2012. – Vol. 22, Issue 2. – P. 337-345.
  19. Quigley, A. FADE: Graph Drawing, Clustering, and Visual Abstraction / A. Quigley, P. Eades // Proceedings of the 8-th International Symposium on Graph Drawing. – 2001. – P. 197-210.
  20. Мясников, Е.В. Анализ методов снижения размерности в задаче представления коллекций цифровых изображений / Е.В. Мясников // Компьютерная оптика. – 2008. – Т. 32, № 3. – С. 296-301. (Myasnikov, E.V. The study of dimensionality reduction methods in the task of browsing of digital image collections / E.V. Myasnikov // Computer Optics. – 2008. – Vol. 32(3). – P. 296-301. – (In Russian).)
  21. Stricker, M. Similarity of color images / M. Stricker, M. Orengo // In Proc. SPIE Conf. on Vis. Commun. and Image Proc. ? 1995.
  22. Swain, M. Color indexing / M. Swain, D. Ballard // International Journal of Computer Vision. – 1991. – Vol. 7(1).
  23. Haralick, R.M. Texture features for image classification / R.M. Haralick, K. Shanmugam, I. Dinstein // IEEE Transactions on Systems, Man and Cybernetics. – 1973. – SMC-3(6).

© 2009, IPSI RAS
Institution of Russian Academy of Sciences, Image Processing Systems Institute of RAS, Russia, 443001, Samara, Molodogvardeyskaya Street 151; E-mail: ko@smr.ru; Phones: +7 (846) 332-56-22, Fax: +7 (846) 332-56-20