En matemáticas y estadística, la proyección aleatoria es una técnica utilizada para reducir la dimensionalidad de un conjunto de puntos que se encuentran en el espacio euclidiano . Los métodos de proyección aleatoria son conocidos por su potencia, simplicidad y bajas tasas de error en comparación con otros métodos [ cita requerida ] . Según los resultados experimentales, la proyección aleatoria conserva bien las distancias, pero los resultados empíricos son escasos. [1] Se han aplicado a muchas tareas de lenguaje natural bajo el nombre de indexación aleatoria .
Reducción de dimensionalidad
La reducción de la dimensionalidad, como su nombre indica, consiste en reducir la cantidad de variables aleatorias utilizando varios métodos matemáticos de la estadística y el aprendizaje automático. La reducción de dimensionalidad se usa a menudo para reducir el problema de administrar y manipular grandes conjuntos de datos. Las técnicas de reducción de dimensionalidad generalmente utilizan transformaciones lineales para determinar la dimensionalidad intrínseca de la variedad, así como para extraer sus direcciones principales. Para este propósito hay varias técnicas relacionadas, incluyendo: análisis de componentes principales , análisis discriminante lineal , análisis de correlación canónica , transformada de coseno discreta , la proyección al azar, etc.
La proyección aleatoria es una forma simple y computacionalmente eficiente de reducir la dimensionalidad de los datos intercambiando una cantidad controlada de error por tiempos de procesamiento más rápidos y tamaños de modelo más pequeños. Las dimensiones y la distribución de las matrices de proyección aleatorias se controlan para preservar aproximadamente las distancias por pares entre dos muestras cualesquiera del conjunto de datos.
Método
La idea central detrás de la proyección aleatoria se da en el lema de Johnson-Lindenstrauss , [2] que establece que si los puntos en un espacio vectorial tienen una dimensión suficientemente alta, entonces pueden proyectarse en un espacio adecuado de dimensiones inferiores de una manera que aproximadamente conserva las distancias entre los puntos.
En la proyección aleatoria, los datos originales de d-dimensión se proyectan a un subespacio k-dimensional (k << d), usando un - matriz dimensional R cuyas columnas tienen unidades de longitud. [ cita requerida ] Usando notación matricial: si es el conjunto original de observaciones N d-dimensionales, entonces es la proyección de los datos en un subespacio de menor dimensión k. La proyección aleatoria es computacionalmente simple: forme la matriz aleatoria "R" y proyecte el matriz de datos X sobre K dimensiones de orden . Si la matriz de datos X es escasa con aproximadamente c entradas distintas de cero por columna, entonces la complejidad de esta operación es de orden. [3]
Proyección aleatoria gaussiana
La matriz aleatoria R se puede generar usando una distribución gaussiana. La primera fila es un vector unitario aleatorio elegido uniformemente de. La segunda fila es un vector unitario aleatorio desde el espacio ortogonal a la primera fila, la tercera fila es un vector unitario aleatorio desde el espacio ortogonal a las dos primeras filas, y así sucesivamente. De esta forma de elegir R, R es una matriz ortogonal (la inversa de su transpuesta), y se satisfacen las siguientes propiedades:
- Simetría esférica: para cualquier matriz ortogonal , RA y R tienen la misma distribución.
- Ortogonalidad: las filas de R son ortogonales entre sí.
- Normalidad: Las filas de R son vectores de longitud unitaria.
Proyecciones aleatorias más eficientes desde el punto de vista computacional
Achlioptas [4] ha demostrado que la distribución gaussiana se puede reemplazar por una distribución mucho más simple como
Esto es eficiente para aplicaciones de bases de datos porque los cálculos se pueden realizar usando aritmética de enteros.
Más tarde se mostró cómo usar aritmética de enteros mientras se hacía la distribución aún más escasa, con muy pocos valores distintos de cero por columna, en el trabajo de la Transformada Sparse JL. [5] Esto es ventajoso ya que una matriz de incrustación escasa significa poder proyectar los datos a una dimensión inferior aún más rápido.
Grandes bases cuasiortogonales
El lema de Johnson-Lindenstrauss establece que grandes conjuntos de vectores en un espacio de alta dimensión pueden mapearse linealmente en un espacio de dimensión n mucho más baja (pero aún alta) con una preservación aproximada de las distancias. Una de las explicaciones de este efecto es la dimensión cuasiortogonal exponencialmente alta del espacio euclidiano n- dimensional . [6] Hay conjuntos exponencialmente grandes (en dimensión n ) de vectores casi ortogonales (con un valor pequeño de productos internos ) en el espacio euclidiano n- dimensional. Esta observación es útil para indexar datos de alta dimensión. [7]
La cuasiortogonalidad de grandes conjuntos aleatorios es importante para los métodos de aproximación aleatoria en el aprendizaje automático . En dimensiones altas, un número exponencialmente grande de vectores elegidos al azar e independientemente de la equidistribución en una esfera (y de muchas otras distribuciones) son casi ortogonales con una probabilidad cercana a uno. [8] Esto implica que para representar un elemento de un espacio de tan alta dimensión mediante combinaciones lineales de vectores elegidos al azar e independientemente, a menudo puede ser necesario generar muestras de longitud exponencialmente grande si usamos coeficientes acotados en combinaciones lineales. Por otro lado, si se permiten coeficientes con valores arbitrariamente grandes, el número de elementos generados aleatoriamente que son suficientes para la aproximación es incluso menor que la dimensión del espacio de datos.
Implementaciones
- RandPro : un paquete R para proyección aleatoria [9] [10]
- sklearn.random_projection : módulo de Python para proyección aleatoria
- Implementación de Weka [1]
Ver también
Referencias
- ^ Ella, Bingham; Heikki, Mannila (2001). "Proyección aleatoria en reducción de dimensionalidad: Aplicaciones a datos de imagen y texto". KDD-2001: Actas de la Séptima Conferencia Internacional ACM SIGKDD sobre Descubrimiento de Conocimiento y Minería de Datos . Nueva York: Association for Computing Machinery. págs. 245–250. CiteSeerX 10.1.1.24.5135 . doi : 10.1145 / 502512.502546 .
- ^ Johnson, William B .; Lindenstrauss, Joram (1984). "Extensiones de mapeos de Lipschitz en un espacio de Hilbert". Conferencia sobre análisis moderno y probabilidad (New Haven, Conn., 1982) . Matemáticas contemporáneas. 26 . Providence, RI: Sociedad Matemática Estadounidense. págs. 189–206 . doi : 10.1090 / conm / 026/737400 . ISBN 9780821850305. Señor 0737400 ..
- ^ Bingham, Ella; Mannila, Heikki (6 de mayo de 2014). "Proyección aleatoria en reducción de dimensionalidad: Aplicaciones a datos de imagen y texto" (PDF) .
- ^ Achlioptas, Dimitris (2001). "Proyecciones aleatorias compatibles con bases de datos". Actas del vigésimo simposio ACM SIGMOD-SIGACT-SIGART sobre los principios de los sistemas de bases de datos - PODS '01 . págs. 274-281. CiteSeerX 10.1.1.28.6652 . doi : 10.1145 / 375551.375608 . ISBN 978-1581133615. S2CID 2640788 .
- ^ Kane, Daniel M .; Nelson, Jelani (2014). "Transformaciones de Sparser Johnson-Lindenstrauss". Revista de la ACM . 61 (1): 1–23. arXiv : 1012.1577 . doi : 10.1145 / 2559902 . Señor 3167920 . S2CID 7821848 .
- ^ Kainen, Paul C .; Kůrková, Věra (1993), "Dimensión cuasiortogonal de los espacios euclidianos", Letras de matemáticas aplicadas , 6 (3): 7–10, doi : 10.1016 / 0893-9659 (93) 90023-G , MR 1347278
- ^ Hecht-Nielsen, R. (1994). "Vectores de contexto: representaciones de significado aproximado de propósito general autoorganizadas a partir de datos brutos". En Zurada, Jacek M .; Marks, Robert Jackson; Robinson, Charles J. (eds.). Inteligencia computacional: imitando la vida . IEEE. págs. 43–56. ISBN 978-0-7803-1104-6.
- ^ Gorban, Alexander N .; Tyukin, Ivan Y .; Prokhorov, Danil V .; Sofeikov, Konstantin I. (2016). "Aproximación con Bases Aleatorias: Pro et Contra". Ciencias de la información . 364–365: 129–145. arXiv : 1506.04631 . doi : 10.1016 / j.ins.2015.09.021 . S2CID 2239376 .
- ^ Ravindran, Siddharth (2020). "Una técnica de proyección reutilizable independiente de datos (DIRP) para la reducción de dimensiones en la clasificación de Big Data utilizando k-vecino más cercano (k-NN)". Cartas de Ciencias de la Academia Nacional . 43 : 13-21. doi : 10.1007 / s40009-018-0771-6 . S2CID 91946077 .
- ^ Siddharth, R .; Aghila, G. (julio de 2020). "RandPro- Una implementación práctica de extracción de características basada en proyección aleatoria para análisis de datos multivariados de alta dimensión en R" . SoftwareX . 12 : 100629. Bibcode : 2020SoftX..1200629S . doi : 10.1016 / j.softx.2020.100629 .
Otras lecturas
- Fodor, Imola K (2002). Una encuesta sobre técnicas de reducción de dimensiones (Informe). CiteSeerX 10.1.1.8.5098 .
- Menon, Aditya Krishna (2007). Proyecciones aleatorias y aplicaciones a la reducción de dimensionalidad (Tesis). CiteSeerX 10.1.1.164.640 .
- Ramdas, Aditya. Una introducción aleatoria a las proyecciones aleatorias (informe). CiteSeerX 10.1.1.377.2593 .