Semelhança entre strings de linha

Question

Tenho uma série de trilhas registradas por um GPS, que mais formalmente podem ser descritas como uma série de sequências de linhas.

Agora, algumas das trilhas gravadas podem ser gravações da mesma rota, mas por causa de imprecisões no sistema GPS, o fato de que as gravações foram feitas em ocasiões separadas e que podem ter sido gravadas viajando em velocidades diferentes, elas não serão combinam perfeitamente, mas ainda parecem próximos o suficiente quando visualizados em um mapa por um humano para determinar que é na verdade a mesma rota que foi registrada.

Quero encontrar um algoritmo que calcule a semelhança entre duas sequências de linhas.Eu criei alguns métodos caseiros para fazer isso, mas gostaria de saber se esse é um problema que já possui bons algoritmos para resolvê-lo.

Como você calcularia a similaridade, visto que médias semelhantes representam o mesmo caminho em um mapa?

Editar: Para aqueles que não têm certeza do que estou falando, consulte este link para obter uma definição do que é uma string de linha: http://msdn.microsoft.com/en-us/library/bb895372.aspx - Eu sou não perguntando sobre cadeias de caracteres.

Answer 1

Calcule o Distância Frechet em cada par de faixas.A distância pode ser usada para avaliar a semelhança de suas trilhas.

Alerta matemático: Fréchet foi pioneiro no campo da espaço métrico que é relevante para o seu problema.

Answer 2

Eu adicionaria um buffer ao redor da primeira linha com base no erro provável estimado e, em seguida, determinaria se a segunda linha cabe inteiramente dentro do buffer.

Answer 3

Para determinar a "mesma rota", crie o conjunto mínimo de vetores de caminho normalizados, calcule as diferenças totais de potência e compare o total com uma medida de qualidade.

1. Normalize os waypoints GPS no comprimento total do caminho,
2. percorrer os vetores dos caminhos juntos, criando um novo conjunto de vetores de caminho para cada caminho com base no vetor mais curto em cada ponto de referência;
3. calcular as diferenças de potência total entre os pontos finais de cada vetor na ponderação dos caminhos normalizados para o comprimento do vetor, e
4. comparar com uma medida de qualidade.

Ajuste visualmente o poder das diferenças (comece com, digamos, diferenças quadradas) e a medida de qualidade (digamos, como uma porcentagem do total de diferenças de poder).Este algoritmo produz uma medida de qualidade contínua da correspondência do caminho, bem como um resultado binário (os caminhos são iguais?)

Paul Tomblin disse:Eu adicionaria um buffer em torno da primeira linha com base no provável erro estimado e, em seguida, determinaria se a segunda linha se encaixa inteiramente dentro do buffer.

Você pode modificar o algoritmo à medida que os pontos finais do vetor normalizado são comparados.Você poderia determinar se alguma diferença de ponto final estava acima de um determinado tamanho (implementando a ideia de buffer de Paul) ou talvez, se os pontos finais estivessem fora do "buffer", usar esse fato para ignorar essa diferença de ponto final, permitindo uma comparação ignorando viagens paralelas.

Answer 4

Você poderia caminhar ao longo de cada ponto (Pa) da LineString A e medir a distância de Pa até o segmento de linha mais próximo da LineString B, calculando a média de cada uma dessas distâncias.

Este não é um método rápido ou perfeito, mas deve ser capaz de fornecer um número útil e é bastante rápido de implementar.

As sequências de linhas começam e terminam em pontos semelhantes ou têm extensões muito diferentes?

Answer 5

Se você considerar uma sequência de linha única como uma sequência de pontos [x,y] (ou pontos [x,y,z]), poderá calcular a similaridade entre cada par de sequências de linha usando o método Needleman-Wunsch algoritmo.Conforme descrito no artigo da Wikipedia referenciado, o algoritmo Needleman-Wunsch requer uma "matriz de similaridade" que define a distância entre um par de pontos.No entanto, seria fácil usar uma função em vez de uma matriz.No seu caso, você poderia simplesmente usar o 2D Distância euclidiana função (ou uma função euclidiana 3D se seus pontos tiverem elevação) para fornecer a distância entre cada par de pontos.

Answer 6

Na verdade, estou do lado da pessoa (Aaron F) que disse que você poderia estar interessado no problema da distância de Levenshtein (e citou esse).Sua resposta me parece a melhor até agora.

Mais especificamente, a distância de Levenshtein (também chamada de distância de edição), não mede estritamente a distância caractere por caractere, mas também permite realizar inserções e exclusões.O melhor algoritmo para essa medida de distância pode ser calculado em tempo quadrático (muito lento se suas strings forem longas), mas os biólogos computacionais têm heurísticas muito boas para isso, que podem ser do seu interesse por si só.Confira EXPLOSÃO e RÁPIDO.

No seu problema, parece que você está lidando com diferenças entre sequências de números e se preocupa com os números.Se você fornecer mais informações, poderei direcioná-lo para a variante correta do BLAST/FASTA/etc para seus propósitos.De qualquer forma, você pode considerar adaptar o BLAST e o FASTA às suas necessidades.Eles são bem simples.

1: http://en.wikipedia.org/wiki/Levenshtein_distance, http://www.nist.gov/dads/HTML/Levenshtein.html