En matemàtiques, informàtica i especialment en teoria de grafs, una matriu de distàncies és una matriu quadrada (matriu bidimensional) que conté les distàncies, preses per parells, entre els elements d'un conjunt. Depenent de l'aplicació en qüestió, la distància que s'utilitza per definir aquesta matriu pot ser o no una mètrica. Si hi ha elements, aquesta matriu tindrà una mida En aplicacions de teoria de grafs, els elements es denominen més sovint punts, nodes o vèrtexs.
Matriu de distàncies no mètrica En general, una matriu de distàncies és una matriu d'adjacència ponderada d'un graf. En una xarxa, un graf dirigit amb pesos assignats als arcs, la distància entre dos nodes de la xarxa es pot definir com el mínim de les sumes dels pesos dels camins més curts que uneixen els dos nodes (on el nombre de passos del camí està limitat). Aquesta funció de distància, tot i que està ben definida, no és una mètrica. No cal que hi hagi restriccions sobre els pesos més enllà de la necessitat de poder combinar-los i comparar-los, de manera que en algunes aplicacions s'utilitzen pesos negatius. Com que els camins són dirigits, la simetria no es pot garantir, i si existeixen cicles de pes negatiu, la matriu de distàncies pot no ser buida (i en absència d'un límit en el recompte de passos, la matriu pot estar indefinida).
Una formulació algebraica de l'anterior es pot obtenir utilitzant l'àlgebra min-plus. La multiplicació matricial en aquest sistema es defineix de la següent manera: Donades dues matrius i , el seu producte de distància es defineix com una matriu tal que
Cal tenir en compte que els elements fora de la diagonal que no estan connectats directament s'hauran de definir a infinit o a un valor gran adequat perquè les operacions mínim-plus funcionin correctament. Un zero en aquestes ubicacions s'interpretarà incorrectament com una aresta sense distància, cost, etc.
Si és una matriu que conté els pesos de les arestes d'un gràfic, aleshores (utilitzant aquest producte de distàncies) dona les distàncies entre vèrtexs utilitzant camins de longitud com a màxim arestes, i també ho és la matriu de distàncies del gràfic quan el límit del recompte de passos s'estableix a k. Si no hi ha bucles de pes negatiu, donarà la matriu de distàncies real, sense límit, perquè eliminar vèrtexs repetits d'un camí no pot reduir-ne el pes. D'altra banda, si i i j es troben en un bucle de pes negatiu, disminuirà sense límit a mesura que k augmenta.
Un graf arbitrari sobre vèrtexs es pot modelar com un graf complet ponderat sobre vèrtexs assignant un pes d'un a cada aresta del graf complet que correspon a una aresta de i infinit a totes les altres arestes. per a aquest graf complet és la matriu d'adjacència de La matriu de distàncies de es pot calcular a partir de com s'ha indicat anteriorment; en canvi, si s'utilitza la multiplicació matricial normal i els vèrtexs no enllaçats es representen amb 0, codificaria en canvi el nombre de camins entre dos vèrtexs de longitud exactament .
Matriu de distàncies mètriques El valor d'un formalisme de matriu de distàncies en moltes aplicacions rau en com la matriu de distàncies pot codificar manifestament els axiomes mètrics i en com es presta a l'ús de tècniques d'àlgebra lineal. És a dir, si amb és una matriu de distàncies per a una distància mètrica, aleshores
les entrades de la diagonal principal són totes zero (és a dir, la matriu és una matriu buida), és a dir, per a tot , totes les entrades fora de la diagonal són positives ( si ), (és a dir, una matriu no negativa), la matriu és una matriu simètrica ( ), i per a qualsevol i j , per a tot (la desigualtat triangular). Això es pot expressar en termes de multiplicació matricial tropical
Quan una matriu de distàncies satisfà els tres primers axiomes (convertint-la en una semimètrica), de vegades s'anomena matriu de predistància. Una matriu de predistància que es pot inserir en un espai euclidià s'anomena matriu de distàncies euclidiana. Per a dades de tipus mixt que contenen descriptors numèrics i categòrics, la distància de Gower és una alternativa comuna.
Un altre exemple comú de matriu de distàncies mètriques sorgeix en la teoria de codificació quan en un codi de blocs els elements són cadenes de longitud fixa sobre un alfabet i la distància entre ells ve donada per la mètrica de distància de Hamming. L'entrada més petita diferent de zero a la matriu de distàncies mesura la capacitat de correcció d'errors i detecció d'errors del codi.
Matriu de distàncies additives Una matriu de distàncies additiva és un tipus especial de matriu utilitzada en bioinformàtica per construir un arbre filogenètic. Sigui el mínim avantpassat comú entre dues espècies i j , esperem que . D'aquí prové la mètrica additiva. Una matriu de distàncies per a un conjunt d'espècies es diu additiva si i només si existeix una filogènia per tal que:
Cada aresta de està associada amb un pes positiu Per a cada , és igual a la suma dels pesos al llarg del camí de i a j en
Per a aquest cas, s'anomena matriu additiva i s'anomena arbre additiu. A continuació podem veure un exemple d'una matriu de distàncies additives i el seu arbre corresponent: alt=Additive distance matrix (left) and its phylogeny tree (right)|sense marc|444x444px
Matriu de distàncies ultramètriques La matriu de distàncies ultramètrica es defineix com una matriu additiva que modela el rellotge molecular constant. S'utilitza per construir un arbre filogenètic. Una matriu es diu ultramètrica si existeix un arbre tal que:
iguala la suma dels pesos externs al llarg del camí des de i a j en Es pot identificar una arrel de l'arbre amb la distància igual a totes les fulles
sense marc|395x395px
Bioinformàtica La matriu de distàncies s'utilitza àmpliament en el camp de la bioinformàtica i és present en diversos mètodes, algoritmes i programes. Les matrius de distàncies s'utilitzen per representar estructures de proteïnes de manera independent de les coordenades, així com les distàncies per parells entre dues seqüències en l'espai de seqüències. S'utilitzen en l'alineació estructural i seqüencial, i per a la determinació d'estructures de proteïnes a partir de la RMN o la cristal·lografia de raigs X.
De vegades és més convenient expressar les dades com una matriu de similitud.
També s'utilitza per definir la correlació de distància.
Mineria de dades i aprenentatge automàtic Mineria de dades Una funció comuna en la mineria de dades és aplicar l'anàlisi de clústers a un conjunt de dades determinat per agrupar dades en funció de com de similars o més similars són en comparació amb altres grups. Les matrius de distància es van convertir en una forta dependència i es van utilitzar en l'anàlisi de clústers, ja que la similitud es pot mesurar amb una mètrica de distància. Així, la matriu de distància es va convertir en la representació de la mesura de similitud entre tots els diferents parells de dades del conjunt.
Agrupació jeràrquica Una matriu de distàncies és necessària per als algoritmes tradicionals de clústering jeràrquic, que sovint són mètodes heurístics emprats en ciències biològiques, com ara la reconstrucció de la filogènia. Quan s'implementa qualsevol dels algoritmes de clústering jeràrquic en mineria de dades, la matriu de distàncies contindrà totes les distàncies per parells entre cada punt i després començarà a crear clústers entre dos punts o clústers diferents basats completament en les distàncies de la matriu de distàncies.
La complexitat temporal és a causa dels càlculs repetitius que es fan després de cada clúster per actualitzar la matriu de distàncies La complexitat espacial és
Aprenentatge automàtic Les mètriques de distància són una part clau de diversos algoritmes d'aprenentatge automàtic, que s'utilitzen tant en l'aprenentatge supervisat com en el no supervisat. Generalment s'utilitzen per calcular la similitud entre punts de dades: aquí és on la matriu de distàncies és un element essencial. L'ús d'una matriu de distàncies efectiva millora el rendiment del model d'aprenentatge automàtic, ja sigui per a tasques de classificació o per a l'agrupació en clústers.
K-Veïns més propers L'algoritme k-NN utilitza una matriu de distàncies, que és un dels algoritmes d'aprenentatge automàtic basats en instàncies més lents però més senzills i utilitzats, que es pot utilitzar tant en tasques de classificació com de regressió. És un dels algoritmes d'aprenentatge automàtic més lents, ja que el resultat predit de cada mostra de prova requereix una matriu de distàncies completament calculada entre la mostra de prova i cada mostra d'entrenament del conjunt d'entrenament. Un cop calculada la matriu de distàncies, l'algoritme selecciona el nombre K de mostres d'entrenament que són les més properes a la mostra de prova per predir el resultat de la mostra de prova en funció del valor majoritari (classificació) o mitjà (regressió) del conjunt seleccionat.
La complexitat del temps de predicció és , per calcular la distància entre cada mostra de prova amb cada mostra d'entrenament per construir la matriu de distàncies on:
k = nombre de veïns més propers seleccionats n = mida del conjunt d'entrenament d = nombre de dimensions que s'utilitzen per a les dades
Aquest model centrat en la classificació prediu l'etiqueta de l'objectiu basant-se en la matriu de distàncies entre l'objectiu i cadascuna de les mostres d'entrenament per determinar el nombre K de mostres que són les més properes a l'objectiu.
Referències
Categoria:Matrius Categoria:Geometria