Hispanopedia Wiki
Articulo de referencia

Distancia de compresión normalizada

La distancia de compresión normalizada ( NCD ) es una forma de medir la similitud entre dos objetos, ya sean dos documentos, dos cartas, dos correos electrónicos, dos partituras...

Hispanopedia WikiContenido en espanolLectura gratuita

La distancia de compresión normalizada ( NCD ) es una forma de medir la similitud entre dos objetos, ya sean dos documentos, dos cartas, dos correos electrónicos, dos partituras musicales, dos idiomas, dos programas, dos imágenes, dos sistemas o dos genomas, entre otros. Esta medición no debería depender de la aplicación ni ser arbitraria. Una definición razonable de la similitud entre dos objetos es la dificultad de transformarlos uno en el otro.

Puede utilizarse en la recuperación de información y la minería de datos para el análisis de clústeres .

Distancia de información

Suponemos que los objetos de los que hablamos son cadenas finitas de 0 y 1. Por lo tanto, nos referimos a la similitud de cadenas . Todo archivo informático tiene esta forma; es decir, si un objeto es un archivo en un ordenador, tiene esta forma. Se puede definir la distancia de información entre cadenas.incógnita{\displaystyle x}yy{\displaystyle y}como la duración del programa más cortopag{\displaystyle p}que calculaincógnita{\displaystyle x}dey{\displaystyle y}y viceversa. Este programa más corto está en un lenguaje de programación fijo. Por razones técnicas se utiliza la noción teórica de máquinas de Turing . Además, para expresar la longitud depag{\displaystyle p}se utiliza la noción de complejidad de Kolmogorov . Luego, se ha demostrado [ 1 ]

|pag|=máximo{K(incógnita∣y),K(y∣incógnita)}{\displaystyle |p|=\max\{K(x\mid y),K(y\mid x)\}}

hasta términos aditivos logarítmicos que pueden ignorarse. Se demuestra que esta distancia de información es una métrica (satisface las desigualdades métricas hasta un término aditivo logarítmico), es universal (minoriza toda distancia computable calculada, por ejemplo, a partir de características hasta un término aditivo constante). [ 1 ]

Distancia de información normalizada (métrica de similitud)

La distancia de información es absoluta, pero si queremos expresar similitud, nos interesan más las relativas. Por ejemplo, si dos cadenas de longitud 1.000.000 difieren en 1000 bits, consideramos que esas cadenas son relativamente más similares que dos cadenas de 1000 bits que difieren en 1000 bits. Por lo tanto, necesitamos normalizar para obtener una métrica de similitud. De esta manera se obtiene la distancia de información normalizada (NID).

norteID(incógnita,y)=máximo{K(incógnita∣y),K(y∣incógnita)}máximo{K(incógnita),K(y)},{\displaystyle NID(x,y)={\frac {\max\{K{(x\mid y)},K{(y\mid x)}\}}{\max\{K(x),K(y)\}}},}

dóndeK(incógnita∣y){\displaystyle K(x\mid y)}es información algorítmica deincógnita{\displaystyle x}dadoy{\displaystyle y}como entrada. El NID se denomina métrica de similitud. Dado que la funciónnorteID(incógnita,y){\displaystyle NID(x,y)}Se ha demostrado que satisface los requisitos básicos para una medida de distancia métrica. [ 2 ] [ 3 ] Sin embargo, no es computable ni siquiera semicomputable. [ 4 ]

Distancia de compresión normalizada

Aunque la métrica NID no es computable, tiene una gran cantidad de aplicaciones. Simplemente aproximandoK{\displaystyle K}Mediante compresores del mundo real, Vitanyi y Cilibrasi reescribieron el NID para obtener la Distancia de Compresión Normalizada (NCD).Z(incógnita){\displaystyle Z(x)}es la longitud binaria del archivoincógnita{\displaystyle x}comprimido con compresorZ{\displaystyle Z}(por ejemplo, " gzip ", " bzip2 ", " PPMZ ") yZ(incógnitay){\displaystyle Z(xy)}denota la compresión de la concatenación deincógnita{\displaystyle x}yy{\displaystyle y}:

nortedoDZ(incógnita,y)=Z(incógnitay)−min{Z(incógnita),Z(y)}máximo{Z(incógnita),Z(y)}{\displaystyle NCD_{Z}(x,y)={\frac {Z(xy)-\min\{Z(x),Z(y)\}}{\max\{Z(x),Z(y)\}}}}[ 2 ]

La NCD es en realidad una familia de distancias parametrizadas con el compresor Z. Cuanto mejor sea Z, más se aproximará la NCD a la NID y mejores serán los resultados. [ 3 ]

Aplicaciones

La distancia de compresión normalizada se ha utilizado para reconstruir automáticamente árboles filogenéticos y de lenguaje. [ 2 ] [ 3 ] También se puede utilizar para nuevas aplicaciones de agrupamiento y clasificación general de datos naturales en dominios arbitrarios, [ 3 ] para agrupamiento de datos heterogéneos, [ 3 ] y para detección de anomalías en diferentes dominios. [ 5 ] El NID y el NCD se han aplicado a numerosos temas, incluyendo la clasificación musical, [ 3 ] para analizar el tráfico de red y agrupar gusanos y virus informáticos, [ 6 ] atribución de autoría, [ 7 ] dinámica de expresión genética, [ 8 ] predicción de células madre útiles frente a inútiles, [ 9 ] redes críticas, [ 10 ] registro de imágenes , [ 11 ] sistemas de preguntas y respuestas. [ 12 ]

Actuación

Investigadores de la comunidad de minería de datos utilizan NCD y variantes como herramientas de minería de datos "sin parámetros ni características". [ 5 ] Un grupo ha probado experimentalmente una métrica estrechamente relacionada en una gran variedad de conjuntos de datos de referencia de secuencias. Al comparar su método de compresión con 51 métodos principales encontrados en 7 conferencias importantes de minería de datos durante la última década, establecieron la superioridad del método de compresión para agrupar datos heterogéneos y para la detección de anomalías, y la competitividad en la agrupación de datos de dominio.

NCD tiene la ventaja de ser robusto frente al ruido. [ 13 ] Sin embargo, aunque NCD parece "sin parámetros", las cuestiones prácticas incluyen qué compresor usar para calcular NCD y otros posibles problemas. [ 14 ]

Comparación con la compresión relativa normalizada (NRC)

Para medir la información de una cadena en relación con otra, es necesario recurrir a las semidistancias relativas (NRC). [ 15 ] Estas medidas no requieren respetar la simetría ni las propiedades de distancia de desigualdad triangular . Aunque la NCD y la NRC parecen muy similares, abordan cuestiones diferentes. La NCD mide la similitud entre ambas cadenas, principalmente a través de su contenido informativo, mientras que la NRC indica la fracción de una cadena objetivo que no puede construirse utilizando información de otra cadena. Para una comparación, con aplicación a la evolución de los genomas de primates, véase [ 16 ] .

Distancia de Google normalizada

Los objetos pueden darse literalmente, como el genoma literal de cuatro letras de un ratón o el texto literal de Guerra y Paz de Tolstói. Para simplificar, asumimos que todo el significado del objeto está representado por el objeto literal en sí. Los objetos también pueden darse por nombre, como "el genoma de cuatro letras de un ratón" o "el texto de Guerra y Paz de Tolstói". También hay objetos que no pueden darse literalmente, sino solo por nombre, y que adquieren su significado a partir de sus contextos en el conocimiento común de la humanidad, como "casa" o "rojo". Nos interesa la similitud semántica . Utilizando las longitudes de las palabras clave obtenidas a partir de los recuentos de visitas a páginas que Google devuelve desde la web, obtenemos una distancia semántica utilizando la fórmula NCD y considerando a Google como un compresor útil para la minería de datos, la comprensión de texto, la clasificación y la traducción. La NCD asociada, llamada distancia normalizada de Google (NGD), puede reescribirse como

norteGRAMOD(incógnita,y)=máximo{registro⁡F(incógnita),registro⁡F(y)}−registro⁡F(incógnita,y)registro⁡norte−min{registro⁡F(incógnita),registro⁡F(y)},{\displaystyle NGD(x,y)={\frac {\max\{\log f(x),\log f(y)\}-\log f(x,y)}{\log N-\min\{\log f(x),\log f(y)\}}},}

dóndeF(incógnita){\displaystyle f(x)}indica el número de páginas que contienen el término de búsqueda.incógnita{\displaystyle x}, yF(incógnita,y){\displaystyle f(x,y)}indica el número de páginas que contienen ambosincógnita{\displaystyle x}yy{\displaystyle y},) como lo devuelve Google o cualquier motor de búsqueda capaz de devolver un recuento agregado de páginas. El númeronorte{\displaystyle N}Se puede establecer en el número de páginas indexadas, aunque es más apropiado contar cada página según el número de términos o frases de búsqueda que contiene. Como regla general, se puede multiplicar el número de páginas por, digamos, mil... [ 17 ]

Véase también

Referencias

  1. 1 2 C.H. Bennett, P. Gacs, M. Li, PMB Vitányi y W. Zurek, Distancia de información, IEEE Trans. Inform. Theory, IT-44:4(1998) 1407–1423
  2. 1 2 3 Li, Ming; Chen, Xin; Li, Xin; Ma, Bin; Vitanyi, PMB (2011-09-27). "M. Li, X. Chen, X. Li, B. Ma, PMB Vitanyi, La métrica de similitud, IEEE Trans. Inform. Th., 50:12(2004), 3250–3264". IEEE Transactions on Information Theory . 50 (12): 3250– 3264. doi : 10.1109/TIT.2004.838101 . S2CID 221927 . 
  3. 1 2 3 4 5 6 Cilibrasi, R.; Vitanyi, PMB (27 de septiembre de 2011). "R. Cilibrasi, PMB Vitanyi, Agrupación por compresión". Transacciones IEEE sobre teoría de la información . 51 (4): 1523–1545 . arXiv : cs/0312044 . doi : 10.1109/TIT.2005.844059 . S2CID 911 . 
  4. ^ Terwijn, Sebastiaan A.; Torenvliet, Leen; Vitányi, Paul MB (2011). «No aproximabilidad de la distancia de información normalizada» . Revista de Ciencias de la Computación y de Sistemas . 77 (4): 738– 742. doi : 10.1016/j.jcss.2010.06.018 . hdl : 2066/92129 . S2CID 10831035 . 
  5. 1 2 Keogh, Eamonn; Lonardi, Stefano; Ratanamahatana, Chotirat Ann (22 de agosto de 2004). "Hacia la minería de datos sin parámetros". E. Keogh, S. Lonardi y CA Ratanamahatana. "Hacia la minería de datos sin parámetros". En Conferencia sobre Descubrimiento de Conocimiento en Datos: Actas de la décima conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos, vol. 22, n.º 25, págs. 206-215. 2004. Dl.acm.org. pág. 206. doi : 10.1145/1014052.1014077 . ISBN  978-1-58113-888-7. S2CID 1616057 . 
  6. ↑ "S. Wehner, Analyzing worms and network traffic using compression, Journal of Computer Security, 15:3(2007), 303–320" . Iospress.metapress.com . Consultado el 3 de noviembre de 2012 .{{cite journal}}: Para citar una revista se requiere |journal=( ayuda )
  7. ↑ Stamatatos, Efstathios (2009). "Un estudio de los métodos modernos de atribución de autoría". Journal of the American Society for Information Science and Technology . 60 (3): 538– 556. CiteSeerX 10.1.1.207.3310 . doi : 10.1002/asi.21001 . 
  8. ↑ Nykter, M. (2008). "La dinámica de la expresión génica en el macrófago exhibe criticidad" . Actas de la Academia Nacional de Ciencias . 105 (6): 1897–1900 . Bibcode : 2008PNAS..105.1897N . doi : 10.1073/pnas.0711525105 . PMC 2538855. PMID 18250330 .  
  9. ↑ Cohen, Andrew R (2010). "Predicción computacional de los destinos de las células progenitoras neuronales". Nature Methods . 7 (3): 213– 218. doi : 10.1038/nmeth.1424 . hdl : 1866/4484 . PMID 20139969 . S2CID 18652440 .  
  10. ↑ Nykter, Matti; Precio, Nathan D.; Larjo, Antti; Ah, Tommi; Kauffman, Stuart A.; Yli-Harja, Olli; Shmulevich, Ilya (2008). "M. Nykter, ND Price, A. Larjo, T. Aho, SA Kauffman, O. Yli-Harja1 e I. Shmulevich, Las redes críticas exhiben la máxima diversidad de información en las relaciones estructura-dinámica, Phys. Rev. Lett. 100, 058702 (2008)". Cartas de revisión física . 100 (5) 058702. arXiv : 0801.3699 . doi : 10.1103/PhysRevLett.100.058702 . PMID 18352443 . S2CID 5760862 .  
  11. ^ Bardera, Antón; Feixas, Miquel; Boada, Imma; Sbert, Mateu (julio de 2006). "Registro de imágenes basado en compresión". M. Feixas, I. Boada, M. Sbert, Registro de imágenes basado en compresión. Proc. Simposio internacional IEEE sobre teoría de la información, 2006. 436–440 . IEEE . págs. 436– 440. doi : 10.1109/ISIT.2006.261706 . hdl : 10256/3052 . ISBN  978-1-4244-0505-3. S2CID 12549455 . 
  12. ↑ Zhang, Xian; Hao, Yu; Zhu, Xiaoyan; Li, Ming; Cheriton, David R. (2007). "Distancia de información de una pregunta a una respuesta". X Zhang, Y Hao, X Zhu, M Li, Distancia de información de una pregunta a una respuesta, Actas de la 13.ª Conferencia Internacional ACM SIGKDD sobre Descubrimiento de Conocimiento y Minería de Datos, 2007, 874–883 . Dl.acm.org. pág. 874. doi : 10.1145/1281192.1281285 . ISBN  978-1-59593-609-7. S2CID 3040254 . 
  13. ↑ Cebrian, M.; Alfonseca, M.; Ortega, A. (27-09-2011). "La distancia de compresión normalizada es resistente al ruido". IEEE Transactions on Information Theory . 53 (5): 1895– 1900. CiteSeerX 10.1.1.158.2463 . doi : 10.1109/TIT.2007.894669 . S2CID 15691266 .  
  14. ↑ "M. Cebrián, M. Alfonseca y A. Ortega, Errores comunes al usar la distancia de compresión normalizada: qué tener en cuenta en un compresor, Commun. Inf. Syst. 5:4(2005), 367–384" . Projecteuclid.org . Consultado el 3 de noviembre de 2012 .
  15. ↑ Ziv, J.; Merhav, N. (1993). "Una medida de entropía relativa entre secuencias individuales con aplicación a la clasificación universal". IEEE Transactions on Information Theory . 39 (4): 1270– 1279. doi : 10.1109/18.243444 .
  16. ↑ Pratas, Diogo; Silva, Raquel M.; Pinho, Armando J. (2018). "Comparación de medidas basadas en compresión con aplicación a la evolución de los genomas de primates" . Entropy . 20 ( 6): 393. Bibcode : 2018Entrp..20..393P . doi : 10.3390/e20060393 . PMC 7512912. PMID 33265483 .  El material se copió de esta fuente, que está disponible bajo una licencia Creative Commons Attribution 4.0 International .
  17. ↑ Cilibrasi, RL; Vitanyi, PMB (27-09-2011). "RL Cilibrasi, PMB Vitanyi, The Google Similarity Distance, IEEE Trans. Knowledge and Data Engineering, 19:3(2007), 370-383". IEEE Transactions on Knowledge and Data Engineering . 19 (3): 370– 383. arXiv : cs/0412098 . Bibcode : 2007ITKDE..19..370C . doi : 10.1109/TKDE.2007.48 . S2CID 59777 . 
  • Estimación eficiente de representaciones de palabras en el espacio vectorial
  • M. Li y P. Vitanyi , Introducción a la complejidad de Kolmogorov y sus aplicaciones, Springer-Verlag, Nueva York, 4.ª edición, 2019.
Lecturas relacionadas
6 articulos
Igualdad (matemáticas)Igualdad (matemáticas)En matemáticas , la igualdad es una relación entre dos cantidades o, más generalmente, dos expresiones matemáticas , afirmando que las cantidades t...Recuperación de informaciónLa recuperación de información ( IR ) en informática y ciencias de la información es la tarea de identificar y recuperar recursos de sistemas de in...Minería de datosMinería de datosLa minería de datos es el proceso de extracción y descubrimiento de patrones en grandes conjuntos de datos que involucra métodos en la intersección...Análisis de conglomeradosAnálisis de conglomeradosEl análisis de conglomerados o clustering es la tarea de agrupar un conjunto de objetos de tal manera que los objetos del mismo grupo (llamado clus...Flujo de bitsFlujo de bitsUn flujo de bits (o bit stream ), también conocido como secuencia binaria , es una secuencia de bits . Un flujo de bytes es una secuencia de bytes ...Métrica de cadenaEn matemáticas y ciencias de la computación , una métrica de cadena (también conocida como métrica de similitud de cadena o función de distancia de...