Мы используем файлы cookie.
Продолжая использовать сайт, вы даете свое согласие на работу с этими файлами.

Matriz de distancias

Подписчиков: 0, рейтинг: 0

En matemáticas, ciencias de la computación y teoría de grafos, una matriz de distancias es una matriz cuadrada cuyos elementos representan las distancias entre los puntos, tomados por pares, de un conjunto. Dependiendo de su aplicación, la distancia usada para definir esta matriz puede o no ser una métrica. Se trata, por lo tanto, de una matriz simétrica de tamaño (dado un conjunto de puntos en el espacio euclídeo) conteniendo números reales no negativos como elementos. El número N de pares de puntos, (N-1)/2, es el número de elementos independientes en la matriz de distancias.

Las matrices de distancias están relacionadas con las matrices de adyacencia, diferenciándose en que las últimas sólo informan sobre qué vértices están conectados, pero no especifican costes o distancias entre los vértices; además, cada elemento de una matriz de distancias es más pequeño cuanto más cercanos se encuentren los puntos, mientras que vértices cercanos (conectados) producen elementos mayores en una matriz de adyacencia.

Matriz de distancias no métricas

En general, una matriz de distancias es una matriz de adyacencia ponderada de alguna gráfica. En una red, una gráfica dirigida con pesos asignados en sus aristas, la distancia entre dos nodos de la red se puede definir como el mínimo de las sumas de los pesos en los caminos más cortos que unen los dos nodos. Esta función de distancia, aunque bien definida, no es una métrica. No es necesario que haya restricciones en los pesos, aparte de la necesidad de poder combinarlos y compararlos, por lo que los pesos negativos se utilizan en algunas aplicaciones. Dado que los caminos están dirigidos, la simetría no se puede garantizar, y si los ciclos existen, la matriz de distancia puede no ser hueca.

Una formulación algebraica de lo anterior se puede obtener mediante el álgebra min-plus. La multiplicación de la matriz en este sistema se define de la siguiente manera: Dadas dos matrices de tamaño , y , su producto de distancia se define como una matriz de tamaño tal que

Tenga en cuenta que los elementos fuera de la diagonal que no están conectados directamente tendrán que ajustarse al infinito o un valor grande adecuado para que las operaciones min-plus funcionen correctamente. Un cero en estas ubicaciones será interpretado incorrectamente como una arista sin distancia, costo, etc.

Si es una matriz de tamaño que contiene los pesos de las aristas de una gráfica, entonces (usando este producto de distancia) da las distancias entre vértices usando caminos de longitud ce a lo más aristas, y es la matriz de distancias de la gráfica.

Una gráfica arbitraria sobre vértices puede ser modelada como una gráfica completa ponderada sobre vértices, asignando un peso de uno a cada arista de la gráfica completa que corresponde a una arista de y cero a todos las aristas restantes. Para esta gráfica completa, es la matriz de adyacencia de . La matriz de distancias de se puede calcular a partir de como se indica anteriormente, sin embargo, calculada por la multiplicación matricial habitual solo codifica el número de caminos entre dos vértices de longitud exactamente .

Matriz de distancias métricas

En muchas aplicaciones, el valor de una matriz de distancias está en como puede codificar los axiomas métricos y en como se presta al uso de técnicas de álgebra lineal. Es decir, si con es una matriz de distancias con una distancia métrica, entonces

  1. Las entradas en la diagonal son todas cero, i.e. para todo .
  2. Todas las entradas fuera de la diagonal son positivas ( si ), es decir, es una matriz no-negativa.
  3. La matriz es una matriz simétrica () y
  4. Para cualquier y , para todo (desigualdad del triángulo).


Una matriz de distancias métricas que puede ser encajada en espacio Euclidiano se llama una matriz de distancias Euclidiana.

Otro ejemplo común de una matriz de distancias métricas surge en la teoría de códigos cuando en un bloque de códigos los elementos son cadenas de longitud fija sobre un alfabeto y la distancia entre ellos está dada por la distancia Hamming. La entrada más pequeña distinta de cero, mide la capacidad de corrección y detección de errores del código.

Matriz de distancia aditiva

Una matriz de distancia aditiva es un tipo especial de matriz utilizada en bioinformática para construir un árbol filogenético. Si es el ancestro común más antiguo entre dos especies y , esperamos que . Aquí es de donde viene la métrica aditiva. Una matriz de distancia para un conjunto de especies se dice que es aditiva si y sólo si existe una filogenia para tal que:

  • Cada arista en se asocia con un peso positivo ,
  • Para todo , es igual a la suma de los pesos a lo largo del camino de a en .

En este caso, se denomina una matriz aditiva y se denomina un árbol aditivo. A continuación podemos ver un ejemplo de una matriz de distancia aditiva y su árbol correspondiente:

Matriz de distancia aditiva (izquierda) y su árbol filogenético (derecha).

Matriz de distancias ultramétricas

La matriz de distancia ultramétrica se define como una matriz aditiva que modela el reloj molecular constante. Es usada para construir un árbol filogenético. Una matriz se dice que es ultramétrica si existe un árbol tal que:

  • es igual a la suma de los pesos de las aristas de una trayectoria en de a .
  • Una raíz del árbol se puede identificar con la misma distancia a todas las hojas.

El siguiente es un ejemplo de una matriz de distancia ultramétrica con su correspondiente árbol.

Ejemplo de un árbol ultramétrico de filogenética

Bioinformática

La matriz de distancia es ampliamente utilizada en el campo de la bioinformática, y está presente en varios métodos, algoritmos y programas. Las matrices de distancia se utilizan para representar estructuras de proteínas de manera independiente de las coordenadas, así como las distancias de emparejamiento entre dos secuencias en el espacio de secuencia. Se utilizan en la alineación estructural y secuencial, y para la determinación de estructuras de proteínas a partir de la cristalografía de rayos X o resonancia magnética nuclear.

A veces es más conveniente expresar los datos como una matriz de similitud.

También se utiliza para definir la correlación de la distancia.

Alineación de Secuencias

Una alineación de dos secuencias se forma mediante la inserción de espacios en ubicaciones arbitrarias a lo largo de las secuencias de modo que terminan con la misma longitud y no hay dos espacios en la misma posición de las dos secuencias aumentadas. [3] Uno de los principales métodos para la alineación de secuencias es la programación dinámica. El método se utiliza para llenar la matriz de distancia y luego obtener la alineación. En el uso típico, para la alineación de secuencias se utiliza una matriz para asignar puntuaciones a las coincidencias de aminoácidos o desajustes, y una penalización por hueco por emparejar un aminoácido en una secuencia con un hueco en la otra.

Alineamiento Global

El algoritmo de Needleman-Wunsch utilizado para calcular la alineación global utiliza programación dinámica para obtener la matriz de distancia.

Alineamiento Local

El algoritmo de Smith-Waterman también está basado en programación dinámica que consiste también en obtener la matriz de distancias y luego obtener la alineación local.

Alineación de Secuencias Múltiples

La alineación múltiple de secuencias es una extensión de la alineación por pares para alinear varias secuencias a la vez. Los diferentes métodos de ASM se basan en la misma idea de la matriz de distancia que las alineaciones globales y locales.

  • Método de Estrella Central. Este método define una secuencia central que minimiza la distancia entre la secuencia y cualquier otra secuencia . Luego genera una alineación múltiple para el conjunto de secuencias de modo que para cada la distancia de alineación es la alineación de emparejamiento óptima. Este método tiene la característica de que la alineación calculada para , cuya distancia de suma de pares es como máximo el doble de la alineación múltiple óptima.
  • Método de alineación progresiva. Es un método heurístico para crear ASM, donde primero alinea las dos secuencias más relacionadas, y progresivamente alinea las siguientes dos secuencias más relacionadas hasta que todas las secuencias se alinean.

Hay otros métodos que tienen su propio programa debido a su popularidad:

MAFFT

La Alineación Múltiple usando la Transformada Rápida de Fourier (MAFFT) es un programa con un algoritmo basado en la alineación progresiva, y ofrece varias estrategias de alineación múltiple. Primero, MAFFT construye una matriz de distancia basada en el número de 6 tuplas compartidas. Segundo, construye el árbol de guía basado en la matriz anterior. En tercer lugar, agrupa las secuencias con la ayuda de la transformada rápida de Fourier y comienza la alineación. Basado en la nueva alineación, reconstruye el árbol de guía y se alinea de nuevo.

Análisis Filogenético

Para realizar el análisis filogenético, el primer paso es reconstruir el árbol filogenético: dada una colección de especies, el problema es reconstruir o inferir las relaciones ancestrales entre las especies, es decir, el árbol filogenético entre las especies. Los métodos de matriz de distancia realizan esta actividad.

Métodos de matriz de distancia

Los métodos de matrices de distancia del análisis filogenético se basan explícitamente en una medida de "distancia genética" entre las secuencias que se clasifican, y por lo tanto requieren múltiples secuencias como entrada. Los métodos de distancia intentan construir una matriz todo-a-todo a partir del conjunto de consultas de secuencia que describe la distancia entre cada par de secuencias. A partir de esto se construye un árbol filogenético que coloca secuencias estrechamente relacionadas bajo el mismo nodo interior y cuyas longitudes de rama reproducen estrechamente las distancias observadas entre secuencias. Los métodos de matrices de distancia pueden producir árboles enraizados o no enraizados, dependiendo del algoritmo utilizado para calcularlos. Dada la especie , la entrada es una matriz de distancia de tamaño donde es la distancia de mutación entre las especies y . El objetivo es producir un árbol de grado 3 que sea consistente con la matriz de distancia.

Se utilizan con frecuencia como base para tipos progresivos e iterativos de alineamiento múltiple de secuencias. La principal desventaja de los métodos de matrices de distancia es su incapacidad para usar eficientemente la información sobre regiones locales de alta variación que aparecen a través de múltiples subárboles. A pesar de los problemas potenciales, los métodos de distancia son extremadamente rápidos, y a menudo producen una estimación razonable de la filogenia. También tienen ciertos beneficios sobre los métodos que usan caracteres directamente. Cabe destacar que los métodos de distancia permiten el uso de datos que no pueden convertirse fácilmente en datos de caracteres, como los ensayos de hibridación de ADN-ADN.

Los siguientes son métodos basados en la distancia para la reconstrucción filogenética:

Reconstrucción de Árboles Aditivos

La reconstrucción del árbol aditivo se basa en matrices de distancia aditivas y ultramétricas. Estas matrices tienen una característica especial:

Considere una matriz aditiva . Para cualquier tres especies ,,, el árbol correspondiente es único. Cada matriz de distancia ultramétrica es una matriz aditiva. Podemos observar esta propiedad para el árbol de abajo, que consiste en la especie ,,.

Unique tree additive matrix.png


La técnica de reconstrucción del árbol aditivo comienza con este árbol. Y luego agrega una especie más cada vez, basado en la matriz de distancia combinada con la propiedad mencionada anteriormente. Si consideramos por ejemplo una matriz aditiva y 5 especies a, b, c, d y e, primero formamos un árbol aditivo para dos especies a y b. Luego elegimos una tercera, digamos c y lo adjuntamos a un punto x en la arista entre a y b. Los pesos de la arista se calculan con la propiedad anterior. A continuación añadimos la cuarta especie d a cualquiera de las aristas. Si aplicamos la propiedad, identificamos que d debe estar unido a una sola arista específica. Por último, añadimos e siguiendo el mismo procedimiento que antes.

MPGMA

El principio básico de MGPMA (Método de Grupo de Pares no Ponderado con Media Aritmética) es que especies similares deben estar más cerca en el árbol filogenético. Por lo tanto, construye el árbol agrupando secuencias similares iterativamente. El método funciona construyendo el árbol filogenético de abajo hacia arriba a partir de sus hojas. Inicialmente, tenemos hojas (o árboles de un único punto), cada uno representando una especie en . Esas hojas se conocen como clusters. Luego, realizamos iteraciones. En cada iteración, identificamos dos clusters y con la distancia promedio más pequeña y los combinamos para formar un cúmulo más grande . Si suponemos que es ultramétrica, para cualquier cluster creado por el algoritmo UPGMA, es un árbol ultramétrico válido.

Unión de vecinos

Unión de vecinos es un método de agrupación ascendente. Toma una matriz de distancia que especifica la distancia entre cada par de secuencias. El algoritmo comienza con un árbol completamente sin resolver, cuya topología corresponde a la de una red en estrella, e itera sobre los siguientes pasos hasta que el árbol se resuelve por completo y se conocen todas las longitudes de las ramas:

  1. Según la matriz de distancia actual, calcule la matriz (definida a continuación),
  2. Encuentre el par de taxones distintos y para los cuales tiene su valor más bajo. Estos taxones se unen a un nodo recién creado, que está conectado al nodo central. En la figura de la derecha, y se unen al nuevo nodo ,
  3. Calcule la distancia desde cada uno de los taxones del par hasta este nuevo nodo,
  4. Calcule la distancia desde cada uno de los taxones fuera de este par hasta el nuevo nodo,
  5. Inicie el algoritmo nuevamente, reemplazando el par de vecinos unidos con el nuevo nodo y usando las distancias calculadas en el paso anterior.​

Fitch-Margoliash

El método de Fitch-Margoliash utiliza un método de mínimos cuadrados ponderados para el agrupamiento basado en la distancia genética. A las secuencias estrechamente relacionadas se les da más peso en el proceso de construcción de árboles para corregir la mayor inexactitud en la medición de distancias entre secuencias distantemente relacionadas. El criterio de mínimos cuadrados aplicado a estas distancias es más preciso pero menos eficiente que los métodos de unión vecinal. Una mejora adicional que corrige las correlaciones entre distancias que surgen de muchas secuencias estrechamente relacionadas en el conjunto de datos también se puede aplicar a un costo computacional mayor.​

Minería de datos y aprendizaje automático

Minería de datos

Una función común de la minería de datos es aplicar el agrupamiento jerárquico en un conjunto dado de datos para agrupar datos en función de que tan similares son en comparación con otros grupos. Las matrices de distancia se volvieron muy dependientes en estos análisis, ya que la similitud puede ser medida con una métrica. Por lo tanto, la matriz de distancia se convirtió en la representación de la medida de similitud entre todos los diferentes pares de datos en el conjunto.

Agrupamientos jerárquicos

Una matriz de distancia es necesaria para los algoritmos de agrupamiento jerárquico tradicionales, que a menudo son métodos heurísticos empleados en ciencias biológicas, como la reconstrucción filogenética. Al implementar cualquiera de los algoritmos de agrupamiento jerárquico en la minería de datos, la matriz de distancia contendrá todas las distancias por pares entre cada punto y luego comenzará a crear grupos entre dos puntos diferentes o grupos basados completamente en distancias desde la matriz de distancia.

Si es el número de puntos, en el agrupamiento jerárquico:

  • La complejidad del tiempo es debido a los cálculos repetitivos realizados después de cada grupo para actualizar la matriz de distancia.
  • La complejidad del espacio es .

Aprendizaje automático

Las métricas de distancia son una parte clave de varios algoritmos de aprendizaje automático, que se utilizan tanto en el aprendizaje supervisado como en el no supervisado. Generalmente se utilizan para calcular la similitud entre puntos de datos: aquí es donde la matriz de distancia es un elemento esencial. El uso de una matriz de distancia efectiva mejora el rendimiento del modelo de aprendizaje automático, ya sea para tareas de clasificación o para agrupamiento​.

K-vecino más cercano

Se utiliza una matriz de distancia en el algoritmo k-NN, el cual es uno de los algoritmos de aprendizaje automático basados en instancias más lentos pero más simples y más utilizados que se puede usar tanto en tareas de clasificación como de regresión. Es uno de los algoritmos de aprendizaje automáticos más lentos, ya que el resultado predicho de cada muestra requiere de una matriz de distancia calculada totalmente entre la muestra de prueba y cada muestra de entrenamiento. Una vez que se calcula la matriz de distancia, el algoritmo selecciona el número K de muestras de entrenamiento que son las más cercanas a la muestra de prueba para predecir el resultado de la muestra de prueba en función del valor del conjunto mayoritario (clasificación) o promedio (regresión).

  • La complejidad del tiempo de predicción al calcular las distancias entre cada muestra de prueba con cada muestra de entrenamiento para construir la matriz de distancias, donde:
    1. es igual al número de vecinos más cercanos seleccionados.
    2. es igual al tamaño del conjunto de entrenamiento.
    3. es el número de dimensiones a ser usadas por los datos.

Este modelo centrado en la clasificación predice la etiqueta del objetivo en función de la matriz de distancia entre el objetivo y cada una de las muestras de entrenamiento para determinar el número K de muestras que son las más cercanas al objetivo.

Matriz de distancia usada para seleccionar K muestras de entrenamiento para KNN.
Modelo de aprendizaje automático que predice el valor objetivo con K-NN.

Visión computacional

Se puede usar una matriz de distancia en redes neuronales para la regresión de 2D a 3D en modelos de aprendizaje automático de predicción de imágenes.

Recuperación de Información

Matrices de distancia utilizando la distancia de mezcla gaussiana

La distancia de mezcla gaussiana es usada para realizar una búsqueda precisa del vecino más cercano para la recuperación de información. Bajo un modelo de mezcla finita gaussiana establecido para la distribución de los datos en la base de datos, la distancia de mezcla gaussiana se formula basada en minimizar la divergencia de Kullback-Leibler entre la distribución de los datos de recuperación y los datos en la base de datos. La comparación del rendimiento de la distancia de mezcla gaussiana con las distancias euclidiana y de mahalanobis basada en una medición de rendimiento de precisión. Los resultados experimentales demuestran que la función de distancia de mezcla gaussiana es superior en los demás para diferentes tipos de datos de prueba.

Los posibles algoritmos básicos que vale la pena señalar sobre el tema de la recuperación de información son el algoritmo de búsqueda de cardúmenes de peces, un recuperador de información que participa en el acto de usar matrices de distancia para recopilar el comportamiento colectivo de los cardúmenes de peces. Mediante el uso de un operador de alimentación para actualizar sus pesos

Ecuación A:

Ecuación B:

donde define el tamaño del desplazamiento de volumen máximo realizado con la matriz de distancia. Específicamente usando una matriz de distancia euclidiana.

Evaluación de la similitud o disimilitud de las matrices de Similitud Coseno y Distancia

La fórmula de conversión entre similitud de coseno y distancia euclidiana está dada por:

Mientras que la medida de similitud del coseno es quizás la medida de proximidad más frecuentemente aplicada en la recuperación de información al medir los ángulos entre documentos en el espacio de búsqueda sobre la base del coseno. La distancia euclidiana es invariable a la corrección media. La distribución muestral de una media se genera mediante un muestreo repetido de la misma población y el registro de las medias muestrales obtenidas. Esto forma una distribución de diferentes medias, y esta distribución tiene su propia media y varianza. Para los datos que pueden ser tanto negativos como positivos, la distribución nula para la similitud del coseno es la distribución del producto escalar de dos vectores unitarios aleatorios independientes. Esta distribución tiene una media de cero y una varianza de . Mientras que la distancia euclidiana será invariable a esta corrección.

Agrupamiento de Documentos

La aplicación de la agrupación jerárquica con métricas basadas en la distancia para organizar y agrupar documentos similares exigirá la necesidad y utilización de una matriz de distancia. La matriz de distancia representará el grado de asociación que un documento tiene con otro documento que se utilizará para crear grupos de documentos estrechamente asociados que se utilizarán en los métodos de recuperación de documentos pertinentes para la consulta de un usuario.

ISOMAP

Isomap incorpora matrices de distancia para utilizar distancias geodésicas distancia geodésica para poder calcular encajes de dimensiones inferiores. Esto ayuda a abordar una colección de documentos que residen dentro de un número masivo de dimensiones y ser capaz de realizar la agrupación de documentos.

Visualizador de Recuperación de Vecindarios (VRVe)

Algoritmo que se utiliza tanto para la visualización supervisada como no supervisada que utiliza matrices de distancia para encontrar datos similares en función de las similitudes que se muestran en una pantalla.

La matriz de distancia necesaria para el VRVe no supervisado se puede calcular a través de distancias de par de entrada fijas.

La matriz de distancia necesaria para VRVe supervisado requiere formular una métrica de distancia supervisada para poder calcular la distancia de la entrada de manera supervisada.

Química

La matriz de distancia es un objeto matemático ampliamente utilizado en las versiones de la química tanto gráfico-teórica (topológica) como geométrica (topográfica)​. La matriz de distancia se usa en química tanto en forma explícita como implícita.

Mecanismos de interconversión entre dos isómeros permutacionales

Las matrices de distancias han sido usadas como el enfoque principal al representar y revelar la secuencia en ruta más corta necesaria para determinar la reorganización entre los dos isómeros permutacionales.

Polinomios de distancia y espectros de distancia

Se requiere el uso explícito de matrices de distancia para construir los polinomios de distancia y los espectros de distancia de las estructuras moleculares.

Modelo de estructura-propiedad

El uso implícito de matrices de distancia se aplicó mediante el uso del índice de Wiener/número de Wiener métrico basado en la distancia, que se formuló para representar las distancias en todas las estructuras químicas. El número de Wiener es igual a la mitad de la suma de los elementos de la matriz de distancia.

Matriz de distancias del grafo teórico

La matriz de distancia en química que se utiliza para la realización en 2D de gráficos moleculares, se utilizan para ilustrar las principales características fundamentales de una molécula en una gran variedad de aplicaciones.

  1. Crear un árbol etiquetado que represente su fórmula esqueletal de una molécula en función de su matriz de distancias. La matriz de distancias es imperativa en esta aplicación ya que moléculas similares pueden tener varios árboles etiquetados diferentes asociados a su fórmula esqueletal. La estructura del árbol etiquetado asociado a la fórmula esqueletal del hexano () que se crea en función de la matriz de distancia en el ejemplo, tiene diferentes variantes de su fórmula esqueletal que afectan tanto a la matriz de distancia como al árbol etiquetado.
    Representación del árbol etiquetado de la fórmula esqueletal de basada en su matriz de distancias.
  2. Crear un grafo etiquetado con peso en sus aristas, utilizado en la teoría de grafos químicos, que representa moléculas con heteroátomos.

Matriz de distancia geométrica

Mientras que la matriz de distancia 2D de distancia teórica gráfica captura las características constitucionales de la molécula, su carácter tridimensional (3D) está codificado en la matriz de distancia geométrica. La matriz de distancia geométrica es un tipo diferente de matriz de distancia que se basa en la matriz de distancia teórica gráfica de una molécula para representar y graficar la estructura de la molécula en 3D​. La matriz de distancia geométrica de una estructura molecular es una matriz simétrica real de tamaño definida en la misma forma que una matriz bidimensional. Sin embargo, los elementos de la matriz contendrán una colección de distancias cartesianas más cortas entre y en . También conocida como matriz topográfica, la matriz de distancias geométricas se puede construir a partir de la geometría conocida de la molécula. Como ejemplo, la matriz de distancias geométricas de la fórmula esqueletal del se muestra en la figura siguiente:

Matriz de distancia geométrica del


Otras aplicaciones

Análisis de series de tiempo

Las matrices de distancia de deformación dinámica del tiempo se utilizan con los algoritmos de agrupación y clasificación de una colección/grupo de objetos de series temporales.

Ejemplos

Supóngase, por ejemplo, el siguiente conjunto de datos a analizar, donde la distancia euclidiana entre píxeles es la métrica de la distancia:

Datos en bruto.

La matriz de distancias podría ser:

a b c d e f
a 0 184 222 177 216 231
b 184 0 45 123 128 200
c 222 45 0 129 121 203
d 177 123 129 0 46 83
e 216 128 121 46 0 83
f 231 200 203 83 83 0

Estos datos pueden ser vistos de forma gráfica como un mapa de calor. En la siguiente imagen, el negro denota una distancia de 0, representando el blanco la distancia máxima:

Vista gráfica.

Véase también


Новое сообщение