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, dos idiomas, dos programas, dos imágenes, dos sistemas, dos genomas, por nombrar un pocos. Dicha medición no debe depender de la aplicación ni ser arbitraria. Una definición razonable de la similitud entre dos objetos es lo difícil que es transformarlos entre sí.
Se puede utilizar en la recuperación de información y la minería de datos para el análisis de conglomerados .
Distancia de información
Suponemos que los objetos de los que se habla son cadenas finitas de 0 y 1 . Por tanto, nos referimos a la similitud de cuerdas . Cada archivo de computadora tiene esta forma, es decir, si un objeto es un archivo en una computadora, tiene esta forma. Se puede definir la distancia de información entre cadenas. y como la duración del programa más corto que computa de 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 dese utiliza la noción de complejidad de Kolmogorov . Entonces, se ha mostrado [1]
hasta términos aditivos logarítmicos que pueden ignorarse. Se muestra que esta distancia de información es una métrica (satisface las desigualdades métricas hasta un término aditivo logarítmico), es universal (minimiza cada distancia computable calculada, por ejemplo, desde 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, entonces nos interesan más las relativas. Por ejemplo, si dos cadenas de 1.000.000 de longitud difieren en 1000 bits, entonces 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 forma se obtiene la distancia de información normalizada (NID),
dónde es información algorítmica de dado como entrada. El NID se llama "la métrica de similitud". desde la funciónSe 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
Si bien la métrica NID no es computable, tiene una gran cantidad de aplicaciones. Simplemente aproximándose por compresores del mundo real, con es la longitud binaria del archivo comprimido con el compresor Z (por ejemplo, " gzip ", " bzip2 ", " PPMZ ") para facilitar la aplicación de NID. [2] Vitanyi y Cilibrasi reescribieron el NID para obtener la distancia de compresión normalizada (NCD)
El NCD es en realidad una familia de distancias parametrizadas con el compresor Z. Cuanto mejor es Z, más se acerca el NCD al NID y mejores son los resultados. [3]
Aplicaciones
La distancia de compresión normalizada se ha utilizado para reconstruir de forma totalmente automática el lenguaje y los árboles filogenéticos. [2] [3] También se puede utilizar para nuevas aplicaciones de agrupamiento general y clasificación de datos naturales en dominios arbitrarios, [3] para agrupamiento de datos heterogéneos, [3] y para detección de anomalías entre dominios. [5] El NID y NCD se han aplicado a numerosos temas, incluida la clasificación de música, [3] para analizar el tráfico de red y los gusanos y virus informáticos en clúster, [6] atribución de autoría, [7] dinámica de expresión génica, [8] predicción útil versus células madre inútiles, [9] redes críticas, [10] registro de imágenes, [11] sistemas de preguntas y respuestas. [12]
Actuación
Los investigadores de la comunidad de minería de datos utilizan NCD y variantes como herramientas de minería de datos "sin parámetros y sin funciones". [5] Un grupo ha probado experimentalmente una métrica estrechamente relacionada en una gran variedad de puntos de referencia de secuencia. 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 resistente al ruido. [13] Sin embargo, aunque NCD parece "sin parámetros", las preguntas prácticas incluyen qué compresor usar para calcular el 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 confiar en semidistancias relativas (NRC). [15] Estas son medidas que no necesitan respetar la simetría y las propiedades de distancia de desigualdad de triángulos. Aunque el NCD y el NRC parecen muy similares, abordan cuestiones diferentes. El NCD mide qué tan similares son ambas cadenas, principalmente utilizando el contenido de información, mientras que la NRC indica la fracción de una cadena de destino que no se puede construir utilizando información de otra cadena. Para una comparación, con aplicación a la evolución de genomas de primates, ver. [dieciséis]
Distancia de Google normalizada
Los objetos se pueden dar literalmente, como el genoma literal de cuatro letras de un ratón , o el texto literal de Guerra y paz de Tolstoi. Para simplificar, asumimos que todo el significado del objeto está representado por el objeto literal en sí. Los objetos también se pueden dar por su nombre, como "el genoma de cuatro letras de un ratón" o "el texto de" Guerra y paz "de Tolstoi". También hay objetos que no se pueden dar literalmente, sino solo por su nombre, y que adquieren su significado a partir de sus contextos de conocimiento común de fondo en la humanidad, como "hogar" o "rojo". Estamos interesados en la similitud semántica . Usando longitudes de palabras de código obtenidas de los recuentos de visitas a páginas devueltas por Google desde la web, obtenemos una distancia semántica usando la fórmula NCD y viendo a Google como un compresor útil para minería de datos, comprensión de texto, clasificación y traducción. El NCD asociado, llamado distancia de Google normalizada (NGD) se puede reescribir como
dónde indica el número de páginas que contienen el término de búsqueda , y denota el número de páginas que contienen tanto y ,) según lo devuelva Google o cualquier motor de búsqueda capaz de devolver un recuento total de páginas. El númerose puede establecer en el número de páginas indexadas, aunque es más adecuado contar cada página de acuerdo con el número de términos de búsqueda o frases que contiene. Como regla general, se puede multiplicar el número de páginas por, digamos, mil ... [17]
Ver también
- Estimación eficiente de representaciones de palabras en el espacio vectorial
- Word2vec
Referencias
- ^ a b C.H. Bennett, P. Gacs, M. Li, PMB Vitányi y W. Zurek, Distancia de información, IEEE Trans. Informar. Teoría, IT-44: 4 (1998) 1407–1423
- ^ a b c Li, Ming; Chen, Xin; Li, Xin; Ma, Bin; Vitanyi, PMB (27 de septiembre de 2011). "M. Li, X. Chen, X. Li, B. Ma, PMB Vitanyi, La métrica de similitud, IEEE Trans. Inform. Th., 50:12 (2004), 3250–3264". Transacciones IEEE sobre teoría de la información . 50 (12): 3250–3264. doi : 10.1109 / TIT.2004.838101 . S2CID 221927 .
- ^ a b c d e f g Cilibrasi, R .; Vitanyi, PMB (27 de septiembre de 2011). "R. Cilibrasi, PMB Vitanyi, Clustering 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 .
- ^ Terwijn, Sebastiaan A .; Torenvliet, Leen; Vitányi, Paul MB (2011). "No aproximación de la distancia de información normalizada" . Revista de Ciencias de la Computación y Sistemas . 77 (4): 738–742. doi : 10.1016 / j.jcss.2010.06.018 . S2CID 10831035 .
- ^ a b 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 conocimientos en datos: Actas de la décima conferencia internacional ACM SIGKDD sobre descubrimiento de conocimientos y minería de datos, vol. 22, no. 25, págs. 206–215. 2004 . Dl.acm.org. pag. 206. doi : 10.1145 / 1014052.1014077 . ISBN 978-1581138887. S2CID 1616057 .
- ^ "S. Wehner, análisis de gusanos y tráfico de red mediante compresión, Journal of Computer Security, 15: 3 (2007), 303–320" . Iospress.metapress.com . Consultado el 3 de noviembre de 2012 . Cite journal requiere
|journal=
( ayuda ) - ^ Stamatatos, Efstathios (2009). "Un estudio de los métodos modernos de atribución de autoría". Revista de la Sociedad Estadounidense de Ciencia y Tecnología de la Información . 60 (3): 538–556. CiteSeerX 10.1.1.207.3310 . doi : 10.1002 / asi.21001 .
- ^ Nykter, M. (2008). "La dinámica de la expresión genética en el macrófago exhibe criticidad" . Actas de la Academia Nacional de Ciencias . 105 (6): 1897-1900. Código Bibliográfico : 2008PNAS..105.1897N . doi : 10.1073 / pnas.0711525105 . PMC 2538855 . PMID 18250330 .
- ^ Cohen, Andrew R (2010). "Predicción computacional de destinos de células progenitoras neurales". Métodos de la naturaleza . 7 (3): 213–218. doi : 10.1038 / nmeth.1424 . hdl : 1866/4484 . PMID 20139969 . S2CID 18652440 .
- ^ Nykter, Matti; Price, Nathan D .; Larjo, Antti; Aho, 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 una 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 .
- ^ Bardera, Anton; 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 de IEEE sobre teoría de la información, 2006. 436–440 . Ieeexplore.ieee.org. págs. 436–440. doi : 10.1109 / ISIT.2006.261706 . hdl : 10256/3052 . ISBN 978-1-4244-0505-3. S2CID 12549455 .
- ^ 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, Proc. 13ª conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos, 2007, 874–883 . Dl.acm.org. pag. 874. doi : 10.1145 / 1281192.1281285 . ISBN 9781595936097. S2CID 3040254 .
- ^ Cebrian, M .; Alfonseca, M .; Ortega, A. (27 de septiembre de 2011). "La distancia de compresión normalizada es resistente al ruido". Transacciones IEEE sobre teoría de la información . 53 (5): 1895-1900. CiteSeerX 10.1.1.158.2463 . doi : 10.1109 / TIT.2007.894669 . S2CID 15691266 .
- ^ "M. Cebrián, M. Alfonseca y A. Ortega, Errores comunes usando 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 .
- ^ Ziv, J .; Merhav, N. (1993). "Una medida de entropía relativa entre secuencias individuales con aplicación a la clasificación universal". Transacciones IEEE sobre teoría de la información . 39 (4): 1270-1279. doi : 10.1109 / 18.243444 .
- ^ 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 genomas de primates" . Entropía . 20 (6): 393. Bibcode : 2018Entrp..20..393P . doi : 10.3390 / e20060393 .
El material se copió de esta fuente, que está disponible bajo una licencia internacional Creative Commons Attribution 4.0 .
- ^ Cilibrasi, RL; Vitanyi, PMB (27 de septiembre de 2011). "RL Cilibrasi, PMB Vitanyi, la distancia de similitud de Google, IEEE Trans. Conocimiento e ingeniería de datos, 19: 3 (2007), 370-383". Transacciones IEEE sobre conocimiento e ingeniería de datos . 19 (3): 370–383. arXiv : cs / 0412098 . doi : 10.1109 / TKDE.2007.48 . S2CID 59777 .
enlaces externos
- M. Li y P. Vitanyi , Introducción a la complejidad de Kolmogorov y sus aplicaciones, Springer-Verlag, Nueva York, 4a edición de 2019,