Lintasan pengelompokan (data GPS dari (x, y) poin) dan menambang data

Saya punya 2 pertanyaan tentang menganalisis dataset GPS.

1) Mengekstraksi lintasan. Saya memiliki database besar koordinat GPS yang terekam dalam formulir (latitude, longitude, date-time). Menurut nilai waktu-tanggal dari catatan berurutan, saya mencoba untuk mengekstrak semua lintasan / jalur yang diikuti oleh orang tersebut. Contohnya; katakan dari waktu M, (x,y)pasangan terus berubah hingga waktu N. Setelah itu N, perubahan (x,y)pasangan menurun, pada titik mana saya menyimpulkan bahwa jalur diambil dari waktu Mke waktuNbisa disebut lintasan. Apakah itu pendekatan yang layak untuk diikuti saat mengekstraksi lintasan? Apakah ada pendekatan / metode / algoritma terkenal yang dapat Anda sarankan? Apakah ada struktur atau format data yang ingin Anda sarankan agar saya mempertahankan titik-titik itu secara efisien? Mungkin, untuk setiap lintasan, mencari tahu kecepatan dan akselerasi akan berguna?

2) Menambang lintasan Setelah saya mengikuti semua lintasan / jalur yang diambil, bagaimana saya bisa membandingkan / mengelompokkannya? Saya ingin tahu apakah titik awal atau akhir sama, lalu bagaimana jalur perantara membandingkan?

Bagaimana cara membandingkan 2 jalur / rute dan menyimpulkan apakah keduanya mirip atau tidak. Selanjutnya; bagaimana cara mengelompokkan jalur serupa bersama?

Saya akan sangat menghargainya jika Anda bisa mengarahkan saya ke penelitian atau hal serupa tentang hal ini.

Pengembangannya akan menggunakan Python, tetapi semua jenis saran perpustakaan dipersilakan.

Saya membuka pertanyaan yang sama persis /programming/4910510/comparing-clustering-trajectories-gps-data-of-xy-points-and-mining-the-data di StackOverflow. Kupikir aku akan mendapat lebih banyak jawaban di sini ...

Dua artikel yang mungkin menarik bagi Anda, karena memiliki motivasi yang serupa dengan Anda:

Batas Prediktabilitas dalam Mobilitas Manusia oleh: Chaoming Song, Zehui Qu, Nicholas Blumm, Albert-László Barabási. Sains , Vol. 327, No. 5968. (19 Februari 2010), hlm. 1018-1021.

Memahami pola mobilitas manusia individu oleh: Marta C. Gonzalez, Cesar A. Hidalgo, Albert-Laszlo Barabasi. Alam , Vol. 453, No. 7196. (05 Juni 2008), hlm. 779-782.

Perhatikan bahwa dua studi menggunakan data yang sama, yang mirip dengan Anda tetapi tidak pada tingkat ketepatan dalam ruang atau waktu. Saya tidak berpikir apa yang akan saya gambarkan sebagai apa yang ingin Anda temukan sebagai lintasan, tetapi saya juga tidak yakin apa yang akan saya sebut itu. Mengapa tepatnya Anda ingin mengelompokkan node awal / akhir dari "lintasan" Anda.

PySAL - Perpustakaan Analisis Spasial Python mungkin merupakan awal yang baik - http://code.google.com/p/pysal/

Khususnya bagian autokorelasi:

Autokorelasi spasial berkaitan dengan pola nilai atribut non-acak atas satu set unit spasial. Ini dapat mengambil dua bentuk umum: autokorelasi positif yang mencerminkan kesamaan nilai dalam ruang, dan autokorelasi negatif atau perbedaan nilai dalam ruang. Dalam kedua kasus autokorelasi muncul ketika pola spasial yang diamati berbeda dari apa yang diharapkan dalam proses acak yang beroperasi di ruang angkasa.

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

Anda juga dapat mempertimbangkan menggunakan R perpustakaan http://cran.r-project.org/web/views/Spatial.html untuk Analisis Pola Titik .

Paket R lainnya:

• kelas dan metode untuk data spatio-temporal
• Analisis spasial data lintasan hewan :

Fungsi untuk mengakses dan memanipulasi data spasial untuk pelacakan hewan. Saring untuk kecepatan dan buat plot waktu yang dihabiskan dari data lintasan hewan.

Ini juga dapat menyederhanakan analisis jika Anda mengambil titik ke jaringan transportasi linear yang ada (jalan / kereta api) yang tersedia dari OSM. Kemudian Anda dapat melambangkan berdasarkan garis-garis ini dan berapa banyak orang yang menggunakannya pada waktu-waktu tertentu dalam sehari.

Meskipun saya tidak dapat berkomentar banyak tentang lintasan atau jalur orang-orang Anda, saya pikir Anda berada di jalur yang benar dengan pendekatan kluster dan waktu.

Saya mengumpulkan demo untuk Esri UC tahun lalu ketika bekerja dengan beberapa orang di Snow Leopard Conservancy, tersedia di: http://resources.arcgis.com/gallery/file/geoprocessing/details?entryID=1F9F376F-1422-2418 -7FBC-C359E9644702

Itu terlihat di "situs makan" (kelompok) Macan Tutul Salju berdasarkan kriteria yang diberikan:

• bagaimana mengelompokkan titik-titik itu (jarak satu sama lain)
• ambang minimum poin (analisis saya membutuhkan 4+ poin karena bacaan diambil setiap 12 jam)
• poin harus berurutan (bagian mudah dari analisis karena harus dikumpulkan dalam urutan linier)

Meskipun menggunakan alat Esri untuk melakukan analisis jarak, skrip python di dalamnya dapat membantu Anda dengan gagasan pengelompokan setelah Anda tahu titik-titik apa yang saling berdekatan. (Menggunakan teori grafik: http://en.wikipedia.org/wiki/Graph_theory )

Seperti disebutkan dalam jawaban lain, ada makalah di luar sana untuk menentukan atribut yang Anda perlukan untuk membuat keputusan.

Analisis didasarkan secara longgar pada konsep-konsep dari: Knopff, KH, ARA Knopff, MB Warren, dan MS Boyce. 2009. Mengevaluasi teknik telemetri Global Positioning System untuk memperkirakan parameter predasi cougar. Jurnal Manajemen Satwa Liar73: 586-597.

Untuk menjalankan segala jenis pengelompokan pada set lintasan Anda, Anda harus memiliki cara menghitung kesamaan atau jarak pasangan lintasan. Ada beberapa metode yang ada untuk ini, dan yang baru sedang dikembangkan untuk kasus-kasus khusus atau untuk memperbaiki kekurangan yang tradisional (saya pribadi sedang mengerjakan yang baru untuk tesis PhD saya). Algoritma yang terkenal adalah sebagai berikut:

• Jarak pasangan terdekat: cukup tentukan jarak 2 lintasan dengan jarak pasangan titik yang paling dekat satu sama lain. Lintasan harus terdiri dari jumlah titik yang sama.
• Jumlah jarak pasangan: Hitung jarak untuk setiap pasangan titik dan tambahkan. Juga hanya berfungsi jika lintasannya sama panjang
• Jarak Dynamic Time Warping (DTW): Algoritma ini dikembangkan untuk menangani lintasan dengan jumlah titik pengukuran yang berbeda. Ini bekerja pada pasangan titik, dan memungkinkan satu titik lintasan untuk digunakan beberapa kali dalam perhitungan jarak pasangan, jika yang lain bergerak "terlalu cepat". (Gambar dari Wikipedia )
• Subceedence Umum Terpanjang: seperti namanya, itu mendefinisikan kesamaan dua lintasan dengan panjang sub-lintasan terpanjang di mana jalur asli bepergian dekat satu sama lain.
• Edit Distance on Real Sequence (EDR) dan Edit Distance dengan Real Penalty (ERP) mendefinisikan kesamaan dengan jumlah operasi edit (tambah, hapus atau ganti) yang diperlukan untuk mengubah salah satu lintasan menjadi yang lain.

Jika Anda tertarik pada bidang ini, saya sangat merekomendasikan buku berjudul "Komputasi dengan Lintasan Spasial" dari sejumlah peneliti Microsoft Asia.

Ini juga dapat membantu Anda:

Orellana D, Wachowicz M. Menjelajahi pola-pola suspensi gerakan dalam mobilitas pejalan kaki. Anal Geogr. 2011; 43 (3): 241-60. PubMed PMID: 22073410.

Lihat juga blog ini:

ideasonmovement.wordpress.com/