Trajetórias de cluster (dados GPS de pontos (x, y)) e mineração de dados

Eu tenho duas perguntas sobre a análise de um conjunto de dados GPS.

1) Extraindo trajetórias Eu tenho um enorme banco de dados de coordenadas GPS gravadas do formulário (latitude, longitude, date-time). De acordo com os valores de data e hora de registros consecutivos, estou tentando extrair todas as trajetórias / caminhos seguidos pela pessoa. Por exemplo; dizer com o tempo M, os (x,y)pares estão mudando continuamente até o tempo N. Depois N, a mudança de (x,y)pares diminui, e nesse ponto concluo que o caminho percorrido de tempos Mem temposNpode ser chamado de trajetória. Essa é uma abordagem decente a seguir ao extrair trajetórias? Existem abordagens / métodos / algoritmos conhecidos que você pode sugerir? Existem estruturas ou formatos de dados que você gostaria de sugerir para manter esses pontos de maneira eficiente? Talvez, para cada trajetória, descobrir a velocidade e a aceleração seja útil?

2) Minerando as trajetórias Depois de ter seguido todas as trajetórias / caminhos seguidos, como posso compará-los / agrupá-los? Gostaria de saber se os pontos inicial ou final são semelhantes. Como os caminhos intermediários se comparam?

Como faço para comparar os 2 caminhos / rotas e concluir se são semelhantes ou não. Além disso; como agrupar caminhos semelhantes?

Eu apreciaria muito se você puder me indicar uma pesquisa ou algo semelhante sobre esse assunto.

O desenvolvimento será em Python, mas todos os tipos de sugestões de bibliotecas são bem-vindos.

Estou abrindo exatamente a mesma pergunta /programming/4910510/comparing-clustering-trajectories-gps-data-of-xy-points-and-mining-the-data no StackOverflow. Pensei em obter mais respostas aqui ...

Dois artigos nos quais você provavelmente estaria interessado, pois eles têm motivações semelhantes às suas:

Limites de previsibilidade na mobilidade humana por: Chaoming Song, Zehui Qu, Nicholas Blumm, Albert-László Barabási. Science , vol. 327, No. 5968. (19 de fevereiro de 2010), pp. 1018-1021.

Compreendendo os padrões individuais de mobilidade humana por: Marta C. Gonzalez, Cesar A. Hidalgo, Albert-Laszlo Barabasi. Nature , vol. 453, n ° 7196. (05 de junho de 2008), pp. 779-782.

Observe que os dois estudos usam os mesmos dados, que são semelhantes aos seus, mas não no nível de precisão no espaço ou no tempo. Acho que não descreveria o que você deseja encontrar como uma trajetória, mas também não tenho certeza do que chamaria. Por que exatamente você deseja agrupar os nós de início / fim de suas "trajetórias"?

PySAL - a Biblioteca de análise espacial do Python pode ser um bom começo - http://code.google.com/p/pysal/

Particularmente a seção de autocorrelação:

A autocorrelação espacial refere-se ao padrão não aleatório de valores de atributos em um conjunto de unidades espaciais. Isso pode assumir duas formas gerais: autocorrelação positiva, que reflete a similaridade de valores no espaço, e autocorrelação negativa ou dissimilaridade de valores, no espaço. Em ambos os casos, a autocorrelação surge quando o padrão espacial observado é diferente do que seria esperado em um processo aleatório operando no espaço.

http://pysal.org/1.2/users/tutorials/autocorrelation.html

Você também pode considerar usar as bibliotecas R http://cran.r-project.org/web/views/Spatial.html para análise de padrões de pontos .

Outros pacotes R:

• classes e métodos para dados espaço-temporais
• Análise espacial dos dados das faixas de animais :

Funções para acessar e manipular dados espaciais para rastreamento de animais. Filtre a velocidade e crie gráficos de tempo gasto a partir de dados de trilhas de animais.

Também pode simplificar a análise se você encaixar os pontos nas redes de transporte linear existentes (rodoviárias / ferroviárias) disponíveis no OSM. Em seguida, você pode simbolizar com base nessas linhas e quantas pessoas as usam em determinados momentos do dia.

Embora eu não possa comentar muito sobre as trajetórias ou caminhos de seu pessoal, acho que você está no caminho certo com a abordagem de cluster e tempo.

Eu montei uma demonstração para a Esri UC no ano passado enquanto trabalhava com algumas pessoas no Snow Leopard Conservancy, disponível em: http://resources.arcgis.com/gallery/file/geoprocessing/details?entryID=1F9F376F-1422-2418 -7FBC-C359E9644702

Ele analisa os "locais de alimentação" (grupos) de Snow Leopards com base em critérios determinados:

• como esses pontos estavam agrupados (distância um do outro)
• um limite mínimo de pontos (minha análise exigiu mais de 4 pontos, pois as leituras eram realizadas a cada 12 horas)
• os pontos devem ser seqüenciais (parte fácil da análise, pois eles devem ser coletados em uma ordem linear)

Embora ele use as ferramentas da Esri para fazer a análise da distância, o script python interno pode ajudá-lo com a ideia de agrupar quando você souber quais pontos estão próximos um do outro. (usa a teoria dos grafos: http://en.wikipedia.org/wiki/Graph_theory )

Como mencionado nas outras respostas, existem documentos disponíveis para determinar os atributos que você precisa para tomar as decisões.

A análise baseou-se livremente nos conceitos de: Knopff, KH, ARA Knopff, MB Warren e MS Boyce. 2009. Avaliando as técnicas de telemetria do Sistema de Posicionamento Global para estimar parâmetros de predação de puma. Journal of Wildlife Management73: 586-597.

Para executar qualquer tipo de agrupamento em seu conjunto de trajetórias, é necessário calcular a semelhança ou a distância dos pares de trajetórias. Existem vários métodos para isso, e novos estão sendo desenvolvidos para casos especiais ou para corrigir uma deficiência dos tradicionais (estou trabalhando pessoalmente em um novo para minha tese de doutorado). Os algoritmos conhecidos são os seguintes:

• Menor distância do par: defina simplesmente a distância de 2 trajetórias pela distância do par de pontos mais próximo um do outro. As trajetórias devem consistir no mesmo número de pontos.
• Soma da distância dos pares: calcule as distâncias para cada par de pontos e some-as. Também funciona apenas se as trajetórias tiverem o mesmo comprimento
• Distância do Dynamic Time Warping (DTW): Este algoritmo foi desenvolvido para lidar com trajetórias de diferentes quantidades de pontos medidos. Ele funciona em pares de pontos e permite que um ponto de uma trajetória seja usado várias vezes nos cálculos de distância dos pares, se o outro estiver se movendo "muito rápido". (Imagem da Wikipedia )
• Subseqüência comum mais longa: como o nome sugere, ele define a similaridade de duas trajetórias pelo comprimento da sub-trajetória mais longa em que os caminhos originais estão se aproximando.
• Editar Distância na Sequência Real (EDR) e Editar Distância com Pena Real (ERP) definem a similaridade pelo número de operações de edição (adicionar, remover ou substituir) necessárias para transformar uma das trajetórias na outra.

Se você estiver nesse campo, recomendo vivamente o livro chamado "Computação com trajetórias espaciais" de vários pesquisadores da Microsoft Ásia.

Isso também pode ser útil para você:

Orellana D, Wachowicz M. Explorando padrões de suspensão de movimento na mobilidade de pedestres. Geogr Anal. 2011; 43 (3): 241-60. PubMed PMID: 22073410.

Também dê uma olhada neste blog:

ideasonmovement.wordpress.com/