La dimensión intrínseca de un conjunto de datos se puede considerar como el número de variables necesarias en una representación mínima de los datos. De manera similar, en el procesamiento de señales de señales multidimensionales, la dimensión intrínseca de la señal describe cuántas variables se necesitan para generar una buena aproximación de la señal.
Sin embargo, al estimar la dimensión intrínseca, a menudo se usa una definición ligeramente más amplia basada en la dimensión múltiple, donde una representación en la dimensión intrínseca solo necesita existir localmente. Estos métodos de estimación de la dimensión intrínseca pueden manejar conjuntos de datos con diferentes dimensiones intrínsecas en diferentes partes del conjunto de datos. Esto a menudo se denomina dimensionalidad intrínseca local .
La dimensión intrínseca se puede usar como un límite inferior de la dimensión en la que es posible comprimir un conjunto de datos mediante la reducción de dimensión, pero también se puede usar como una medida de la complejidad del conjunto de datos o la señal. Para un conjunto de datos o señal de N variables, su dimensión intrínseca M satisface 0 ≤ M ≤ N , aunque los estimadores pueden producir valores más altos.
Ejemplo
Dejar ser una función (o señal ) de dos variables que tiene la formapara alguna función g de una variable que no es constante . Esto significa que f varía, de acuerdo con g , con la primera variable oa lo largo de la primera coordenada . Por otro lado, f es constante con respecto a la segunda variable oa lo largo de la segunda coordenada. Solo es necesario conocer el valor de una, es decir, la primera variable para determinar el valor de f . Por lo tanto, es una función de dos variables pero su dimensión intrínseca es una.
Un ejemplo un poco más complicado es. f sigue siendo intrínseca unidimensional, lo que se puede ver haciendo una transformación variable y lo que da . Dado que la variación en f puede describirse mediante la variable única y 1, su dimensión intrínseca es uno.
Para el caso de que f sea constante, su dimensión intrínseca es cero, ya que no se necesita ninguna variable para describir la variación. Para el caso general, cuando la dimensión intrínseca de la función de dos variables f no es cero ni uno, es dos.
En la literatura, las funciones que son de dimensión intrínseca cero, uno o dos a veces se denominan i0D , i1D o i2D , respectivamente.
Definición formal de señales
Para una función de N- variable f , el conjunto de variables se puede representar como un vector N -dimensional x :.
Si para alguna función variable M g y matriz A M × N , ¿ es el caso que
- para todo x ;
- M es el número más pequeño para el que se puede encontrar la relación anterior entre f y g ,
entonces la dimensión intrínseca de f es M .
La dimensión intrínseca es una caracterización de f , no es una caracterización inequívoca de g ni de A . Es decir, si la relación anterior se satisface para algunos f , g y A , también debe satisfacerse para los mismos f y g ′ y A ′ dados por y donde B es una matriz M × M no singular , ya que.
La transformada de Fourier de señales de baja dimensión intrínseca
Una función variable N que tiene una dimensión intrínseca M
Un simple ejemplo
Sea f una función de dos variables que es i1D. Esto significa que existe un vector normalizadoy una función g de una variable tal que para todos . Si F es la transformada de Fourier de f (ambas son funciones de dos variables) debe darse el caso de que.
Aquí G es la transformada de Fourier de g (ambas son funciones de una variable), δ es la función de impulso de Dirac y m es un vector normalizado enperpendicular an . Esto significa que F desaparece en todas partes excepto en una línea que pasa por el origen del dominio de la frecuencia y es paralela am . A lo largo de esta línea F varía en función de G .
El caso general
Sea f una función variable N que tiene dimensión intrínseca M , es decir, existe una función variable M g y una matriz A de M × N tal que.
Su transformada de Fourier F se puede describir de la siguiente manera:
- F desaparece en todas partes excepto en un subespacio de dimensión M
- El subespacio M está atravesado por las filas de la matriz A
- En el subespacio, F varía según G la transformada de Fourier de g
Generalizaciones
El tipo de dimensión intrínseca descrita anteriormente supone que se aplica una transformación lineal a las coordenadas de la función N -variable f para producir las M variables que son necesarias para representar cada valor de f . Esto significa que f es constante a lo largo de líneas, planos o hiperplanos, en función de N y M .
En un caso general, f tiene dimensión intrínseca M si existen M funciones a 1 , a 2 , ..., a M y una función variable M g tal que
- para todo x
- M es el número más pequeño de funciones que permite la transformación anterior
Un ejemplo simple es transformar una función de 2 variables f en coordenadas polares:
- , f es i1D y es constante a lo largo de cualquier círculo centrado en el origen
- , f es i1D y es constante a lo largo de todos los rayos desde el origen
Para el caso general, generalmente no es posible una descripción simple de los conjuntos de puntos para los cuales f es constante o de su transformada de Fourier.
Dimensionalidad intrínseca local
La dimensionalidad intrínseca local (LID) se refiere a la observación de que a menudo los datos se distribuyen en una variedad de dimensiones inferiores cuando solo se considera un subconjunto cercano de los datos. Por ejemplo, la funciónse puede considerar unidimensional cuando y está cerca de 0, pero bidimensional cuando y es mucho mayor que 1.
La dimensionalidad intrínseca local se utiliza a menudo con respecto a los datos. Luego, por lo general, se estima en función de los k vecinos más cercanos de un punto de datos, [1] a menudo en función de un concepto relacionado con la dimensión de duplicación en matemáticas. Dado que el volumen de una d -esfera crece exponencialmente en d , la velocidad a la que se encuentran nuevos vecinos a medida que aumenta el radio de búsqueda se puede utilizar para estimar la dimensionalidad intrínseca local (por ejemplo, estimación GED [2] ). Sin embargo, se han propuesto enfoques alternativos de estimación, por ejemplo, estimación basada en ángulos. [3]
Historia
Durante la década de 1950 se desarrollaron en las ciencias sociales los llamados métodos de "escala" para explorar y resumir conjuntos de datos multidimensionales. [4] Después de que Shepard introdujo el escalado multidimensional no métrico en 1962 [5], una de las principales áreas de investigación dentro del escalado multidimensional (MDS) fue la estimación de la dimensión intrínseca. [6] El tema también se estudió en la teoría de la información , iniciada por Bennet en 1965, quien acuñó el término "dimensión intrínseca" y escribió un programa de computadora para estimarlo. [7] [8] [9]
Durante la década de 1970 se construyeron métodos de estimación de dimensionalidad intrínseca que no dependían de reducciones de dimensionalidad como MDS: basados en valores propios locales, [10] basados en distribuciones de distancia, [11] y basados en otras propiedades geométricas dependientes de la dimensión [12]
La estimación de la dimensión intrínseca de conjuntos y medidas de probabilidad también se ha estudiado ampliamente desde alrededor de 1980 en el campo de los sistemas dinámicos, donde las dimensiones de atractores (extraños) han sido el tema de interés. [13] [14] [15] [16] Para los atractores extraños no existe una suposición múltiple, y la dimensión medida es una versión de la dimensión fractal, que también puede ser no entera. Sin embargo, las definiciones de dimensión fractal producen la dimensión múltiple para las variedades.
En la década de 2000 se aprovechó la "maldición de la dimensionalidad" para estimar la dimensión intrínseca. [17] [18]
Aplicaciones
El caso de una señal de dos variables que es i1D aparece con frecuencia en la visión por computadora y el procesamiento de imágenes y captura la idea de regiones de imágenes locales que contienen líneas o bordes. El análisis de tales regiones tiene una larga historia, pero no fue hasta que se inició un tratamiento más formal y teórico de tales operaciones que se estableció el concepto de dimensión intrínseca, aunque el nombre ha variado.
Por ejemplo, el concepto al que aquí se hace referencia como vecindario de imagen de dimensión intrínseca 1 o vecindario i1D se denomina unidimensional por Knutsson (1982), [19] lineal simétrico por Bigün y Granlund (1987) [20] y vecindario simple en Granlund y Knutsson (1995). [21]
Ver también
Referencias
- ^ Amsaleg, Laurent; Chelly, Oussama; Furon, Teddy; Girard, Stéphane; Houle, Michael E .; Kawarabayashi, Ken-ichi; Nett, Michael (10 de agosto de 2015). "Estimación de dimensionalidad intrínseca local" . Actas de la 21ª Conferencia Internacional ACM SIGKDD sobre Descubrimiento de Conocimiento y Minería de Datos . KDD '15. Sydney, NSW, Australia: Asociación de Maquinaria de Computación: 29–38. doi : 10.1145 / 2783258.2783405 . ISBN 978-1-4503-3664-2.
- ^ Houle, YO; Kashima, H .; Nett, M. (2012). "Dimensión de expansión generalizada" . 2012 IEEE 12th International Conference on Data Mining Workshops : 587–594. doi : 10.1109 / ICDMW.2012.94 .
- ^ Thordsen, Erik; Schubert, Erich (2020). Satoh, Shin'ichi; Vadicamo, Lucia; Zimek, Arthur; Carrara, Fabio; Bartolini, Ilaria; Aumüller, Martin; Jónsson, Björn Þór; Pagh, Rasmus (eds.). "ABID: dimensionalidad intrínseca basada en ángulos" . Búsqueda de similitudes y aplicaciones . Apuntes de conferencias en informática. Cham: Springer International Publishing: 218–232. arXiv : 2006.12880 . doi : 10.1007 / 978-3-030-60936-8_17 . ISBN 978-3-030-60936-8.
- ^ Torgerson, Warren S. (1978) [1958]. Teoría y métodos de escalado . Wiley. ISBN 0471879452. OCLC 256008416 .
- ^ Shepard, Roger N. (1962). "El análisis de proximidades: Escalado multidimensional con función de distancia desconocida. I.". Psychometrika . 27 (2): 125–140. doi : 10.1007 / BF02289630 .
- ^ Shepard, Roger N. (1974). "Representación de estructura en datos de similitud: problemas y perspectivas". Psychometrika . 39 (4): 373–421. doi : 10.1007 / BF02291665 .
- ^ Bennet, Robert S. (junio de 1965). "Representación y análisis de señales — Parte XXI: La dimensionalidad intrínseca de las colecciones de señales" . Rep.163 . Baltimore, MD: Universidad Johns Hopkins.
- ^ Robert S. Bennett (1965). Representación y análisis de señales Parte XXI. La dimensionalidad intrínseca de las colecciones de señales (PDF) (PhD). Ann Arbor, Michigan: Universidad Johns Hopkins.
- ^ Bennett, Robert S. (septiembre de 1969). "La dimensionalidad intrínseca de las colecciones de señales". Transacciones IEEE sobre teoría de la información . 15 (5): 517–525. doi : 10.1109 / TIT.1969.1054365 .
- ^ Fukunaga, K .; Olsen, DR (1971). "Un algoritmo para encontrar la dimensionalidad intrínseca de los datos". Transacciones IEEE en computadoras . 20 (2): 176–183. doi : 10.1109 / TC.1971.223208 .
- ^ Pettis, KW; Bailey, Thomas A .; Jain, Anil K .; Dubes, Richard C. (1979). "Un estimador de dimensionalidad intrínseca de la información del vecino cercano". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 1 (1): 25–37. doi : 10.1109 / TPAMI.1979.4766873 . PMID 21868828 .
- ^ Tronco, GV (1976). "Estimación estadística de la dimensionalidad intrínseca de una colección de señales ruidosas". Transacciones IEEE en computadoras . 100 (2): 165-171. doi : 10.1109 / TC.1976.5009231 .
- ^ Grassberger, P .; Procaccia, I. (1983). "Midiendo la extrañeza de atractores extraños". Physica D: Fenómenos no lineales . 9 (1–2): 189–208. Código Bibliográfico : 1983PhyD .... 9..189G . doi : 10.1016 / 0167-2789 (83) 90298-1 .
- ^ Takens, F. (1984). "Sobre la determinación numérica de la dimensión de un atractor". En Tong, Howell (ed.). Sistemas dinámicos y bifurcaciones, actas de un taller celebrado en Groningen, Países Bajos, del 16 al 20 de abril de 1984 . Apuntes de clase en matemáticas. 1125 . Springer-Verlag. págs. 99-106. doi : 10.1007 / BFb0075637 . ISBN 3540394117.
- ^ Cutler, CD (1993). "Una revisión de la teoría y estimación de la dimensión fractal" . Estimación de dimensiones y modelos . Series de tiempo no lineales y caos. 1 . World Scientific. págs. 1-107. ISBN 9810213530.
- ^ Harte, D. (2001). Multifractales: teoría y aplicaciones . Chapman y Hall / CRC. ISBN 9781584881544.
- ^ Chávez, E. (2001). "Buscando en espacios métricos". Encuestas de computación ACM . 33 (3): 273–321. doi : 10.1145 / 502807.502808 . hdl : 10533/172863 .
- ^ Pestov, V. (2008). "Un enfoque axiomático de la dimensión intrínseca de un conjunto de datos". Redes neuronales . 21 (2–3): 204–213. arXiv : 0712.2063 . doi : 10.1016 / j.neunet.2007.12.030 . PMID 18234471 .
- ^ Knutsson, Hans (1982). Filtrado y reconstrucción en procesamiento de imágenes (PDF) . Estudios de Linköping en Ciencia y Tecnología. 88 . Universidad de Linköping. ISBN 91-7372-595-1. oai: DiVA.org: liu-54890.
- ^ Bigün, Josef; Granlund, Gösta H. (1987). "Detección de orientación óptima de simetría lineal" (PDF) . Actas de la Conferencia Internacional sobre Visión por Computador . págs. 433–438.
- ^ Granlund, Gösta H .; Knutsson, Hans (1995). Procesamiento de señales en visión artificial . Académico Kluwer. ISBN 978-1-4757-2377-9.
- Michael Felsberg; Sinan Kalkan; Norbert Krueger (2009). "Caracterización de dimensionalidad continua de estructuras de imagen" . Computación de imagen y visión . 27 (6): 628–636. doi : 10.1016 / j.imavis.2008.06.018 . hdl : 11511/36631 .