Dynamic Time Warping dan normalisasi

9

Saya menggunakan Dynamic Time Warping untuk mencocokkan kurva "kueri" dan "templat" dan sejauh ini berhasil, tetapi saya punya beberapa pertanyaan mendasar:

  1. Saya menilai "kecocokan" dengan menilai apakah hasil DTW kurang dari beberapa nilai ambang batas yang saya buat secara heuristik. Apakah ini pendekatan umum untuk menentukan "kecocokan" menggunakan DTW? Jika tidak, tolong jelaskan ...

    Dengan asumsi jawaban untuk (1) adalah "ya", maka saya bingung, karena hasil DTW cukup sensitif terhadap a) perbedaan amplitudo kurva dan b) panjang vektor kueri dan panjang " vektor "template.

    Saya menggunakan fungsi langkah simetris, jadi untuk (b) Saya menormalkan hasil DTW saya dengan membaginya dengan M + N (lebar + tinggi matriks DTW). Ini tampaknya agak efektif, tetapi tampaknya akan menghukum kecocokan DTW yang lebih jauh dari diagonal (yaitu, yang memiliki jalur yang lebih panjang melalui matriks DTW). Yang tampaknya agak arbitrer untuk pendekatan "normalisasi". Membagi dengan jumlah langkah melalui matriks tampaknya masuk akal secara intuitif, tetapi itu tampaknya bukan cara untuk melakukannya menurut literatur.

  2. Jadi apakah ada cara yang lebih baik untuk menyesuaikan hasil DTW untuk ukuran kueri dan vektor templat?

  3. Akhirnya, bagaimana cara menormalkan hasil DTW untuk perbedaan amplitudo antara kueri dan vektor templat?

Karena, mengingat kurangnya teknik normalisasi yang dapat diandalkan (atau kurangnya pemahaman saya), tampaknya ada banyak upaya manual yang terlibat dalam bekerja dengan data sampel untuk mengidentifikasi tingkat ambang batas terbaik untuk mendefinisikan "kecocokan". Apakah saya melewatkan sesuatu?

tuan blinky
sumber

Jawaban:

8

Tidak ada "pendekatan umum" untuk ini setidak-tidaknya setahu saya. Selain itu Anda mencoba meminimalkan metrik jarak. Misalnya dalam kakek kertas DTW, Sakoe & Chiba (1978) gunakansebagai pengukuran perbedaan antara dua vektor fitur.||Sebuahsaya-bsaya||

Ketika Anda mengidentifikasi dengan benar, Anda harus memiliki jumlah poin yang sama (biasanya) agar dapat bekerja di luar kotak. Saya akan mengusulkan menggunakan lowess () lebih halus / interpolator di atas kurva Anda untuk membuat mereka dengan ukuran yang sama pertama. Ini hal yang cukup standar untuk "statistik kurva". Anda dapat melihat contoh aplikasi di Chiou et al. (2003) ; penulis tidak peduli tentang DTW dalam pekerjaan ini, tetapi ini adalah contoh yang baik bagaimana menangani pembacaan dengan ukuran yang tidak sama.

Selain itu seperti yang Anda katakan "amplitudo" adalah masalah. Ini sedikit lebih terbuka dan jujur. Anda dapat mencoba pendekatan Area-Under-the-Curve seperti yang diusulkan oleh Zhang dan Mueller (2011) untuk menangani hal ini tetapi benar-benar untuk tujuan waktu melengkungkan bahkan normalisasi sup-norm (mis. Ganti dengan dapat melakukan seperti dalam makalah ini oleh Tang dan Mueller (2009) . Saya akan mengikuti yang kedua, tetapi bagaimanapun Anda juga memperhatikan normalisasi sampel adalah kebutuhan.f ( x )f(x)f(x)skamuhaly|f(x)|

Bergantung pada sifat data Anda, Anda dapat menemukan lebih banyak literatur khusus aplikasi. Saya pribadi menemukan pendekatan meminimalkan dengan memperhatikan fungsi melengkung berpasangan target yang paling intuitif dari semua. Jadi fungsi target untuk meminimalkan adalah: , di mana semuanya terlepas dari ketidaktahuan itu sebenarnya cukup mudah: Anda mencoba mencari untuk menemukan fungsi warping yang meminimalkan jumlah yang diharapkan dari ketidakcocokan kurva permintaan melengkung ke kurva referensi (istilahgCλ(Ysaya,Yk,g)=E{T(Ysaya(g(t))-Yk(t))2+λ(g(t)-t)2dt|Ysaya,Yk}gYsaya(g(t))Yk(t)Ysaya(g(t))-Yk(t)) tunduk pada normalisasi terhadap distorsi waktu yang Anda terapkan oleh lengkungan itu (istilah ). Inilah yang diterapkan oleh paket MATLAB PACE . Saya tahu bahwa ada paket R fda oleh JO Ramsay et al. yang mungkin bisa membantu juga, tetapi saya belum secara pribadi menggunakannya (agak mengganggu referensi standar untuk metode paket itu dalam banyak kasus buku Ramsay dan Silverman yang sangat baik, Analisis Data Fungsional (2006) edisi kedua , dan Anda harus menjelajahi Buku 400 halaman untuk mendapatkan apa yang Anda cari; setidaknya itu bagus untuk dibaca)g(t)-t

Masalah yang Anda gambarkan dalam literatur Statistik dikenal secara luas sebagai " pendaftaran kurva " (misalnya lihat Gasser dan Kneip (1995) untuk penanganan awal masalah ini) dan berada di bawah payung umum teknik Analisis Data Fungsional .

(Dalam beberapa kasus saya dapat menemukan kertas asli yang tersedia secara online, tautannya mengarah langsung ke sana; jika tidak, tautannya akan diarahkan ke perpustakaan digital umum. Hampir semua makalah yang disebutkan dapat ditemukan untuk menyusun versi secara gratis. Saya menghapus komentar asli saya seperti semula. digantikan oleh pos ini.)

usεr11852
sumber
Ini adalah jawaban yang sangat bagus dan sangat membantu. Referensi sangat membantu.
Mikko
Apakah Anda tahu referensi yang cocok untuk menyatakan bahwa "amplitudo adalah masalah" di dtw? Ini mungkin sangat jelas sehingga saya berjuang untuk menemukan referensi, yang dengan jelas membahasnya.
Mikko
Aku senang kamu menyukainya. Seperti yang saya katakan perawatan amplitudo "sedikit lebih terbuka berakhir" dan saya tidak berpikir Anda akan menemukan referensi tunggal menyebutkannya kecuali itu terkait dengan aplikasi atau metodologi yang dimaksud (seperti misalnya dalam karya Zhang & Mueller ' 09). Normalisasi diperlukan ketika Anda memiliki data yang diukur dalam unit yang berbeda. Apa yang biasanya penting adalah normalisasi komponen fungsional / kanonik / what_have_you sehingga mereka membentuk dasar dalam . L.2
usεr11852
Dari sumber yang telah disebutkan mungkin taruhan terbaik Anda mungkin akan menjadi buku FDA oleh Ramsay & Silverman, Chapt. 7 pada "pendaftaran dan tampilan data fungsional". Sumber yang sangat bagus adalah buku: "Inferensi untuk Data Fungsional dengan Aplikasi" oleh Horváth dan Kokoszka; Bagian III "Data fungsional dependen" menyentuh masalah normalisasi sebagian besar karena yang peduli tentang deteksi titik perubahan.
usεr11852