Clustering Warping Waktu dinamis

Apa yang akan menjadi pendekatan untuk menggunakan Dynamic Time Warping (DTW) untuk melakukan clustering time series?

Saya telah membaca tentang DTW sebagai cara untuk menemukan kesamaan antara dua seri waktu, sementara mereka dapat digeser waktu. Bisakah saya menggunakan metode ini sebagai ukuran kesamaan untuk algoritma pengelompokan seperti k-means?

Jangan tidak menggunakan k-cara untuk deret waktu.

DTW tidak diminimalkan dengan rata-rata; k-means mungkin tidak konvergen dan bahkan jika konvergen tidak akan menghasilkan hasil yang sangat baik. Mean adalah estimator kuadrat-terkecil pada koordinat. Ini meminimalkan varians, bukan jarak sewenang-wenang, dan k-means dirancang untuk meminimalkan varians, bukan jarak sewenang - wenang .

Asumsikan Anda memiliki dua seri waktu. Dua gelombang sinus, dengan frekuensi yang sama, dan periode pengambilan sampel yang agak panjang; tetapi mereka diimbangi oleh . Karena DTW melakukan pembengkokan waktu, DTW dapat meluruskannya sehingga cocok dengan sempurna, kecuali untuk awal dan akhir. DTW akan menetapkan jarak yang agak kecil untuk dua seri ini. Namun, jika Anda menghitung rata - rata dari dua seri, itu akan menjadi 0 datar - mereka membatalkan. Mean tidak melakukan warping waktu dinamis, dan kehilangan semua nilai yang didapat DTW. Pada data seperti itu, k-means mungkin gagal untuk bertemu , dan hasilnya tidak akan berarti. K-means benar-benar hanya boleh digunakan dengan varians (= kuadrat Euclidean), atau beberapa kasus yang setara (seperti cosinus, pada data normal L2, di mana kesamaan cosinus adalah$\pi$sama dengan jarak Euclidean kuadrat)$2 -$

Sebagai gantinya, hitung matriks jarak menggunakan DTW, lalu jalankan hierarchical clustering seperti single-link. Berbeda dengan k-means, seri ini mungkin memiliki panjang yang berbeda.

Ya, Anda dapat menggunakan pendekatan DTW untuk klasifikasi dan pengelompokan seri waktu . Saya telah mengumpulkan sumber daya berikut , yang berfokus pada topik ini (Saya baru-baru ini menjawab pertanyaan serupa, tetapi tidak di situs ini, jadi saya menyalin konten di sini untuk kenyamanan semua orang):

• Klasifikasi / Pengelompokan Seri Waktu UCR : halaman utama , halaman perangkat lunak , dan kertas yang sesuai
• Klasifikasi Time Series dan Clustering dengan Python : sebuah posting blog
• Capital Bikeshare: Time Series Clustering : posting blog lain
• Klasifikasi dan Kluster Seri Waktu : notebook ipython
• Dynamic Time Warping menggunakan rpy dan Python : posting blog lain
• Menambang Seri-Waktu dengan Triliun Poin: Dynamic Time Warping at Scale : posting blog lain
• Analisis Rangkaian Waktu dan Penambangan dalam R (untuk menambahkan R ke dalam campuran): satu lagi posting blog
• Dan, akhirnya, dua alat mengimplementasikan / mendukung DTW , untuk melengkapi: paket R dan modul Python

Metode DTW Barycenter Averaging (DBA) baru-baru ini telah diusulkan oleh Petitjean et al. untuk seri waktu rata-rata. Dalam makalah lain mereka membuktikan secara empiris dan teoritis bagaimana itu dapat digunakan untuk mengelompokkan deret waktu dengan k-means. Implementasi disediakan di GitHub oleh penulis ( tautan ke kode ).

1 F. Petitjean, G. Forestier, GI Webb, AE Nicholson, Y. Chen dan E. Keogh, "Dynamic Time Warping Rata-Rata dari Time Series Memungkinkan Klasifikasi Lebih Cepat dan Lebih Akurat," Konferensi Internasional IEEE 2014 tentang Data Mining, Shenzhen, 2014 .

2 F. Petitjean, P. Gançarski, Merangkum serangkaian deret waktu dengan rata-rata: Dari urutan Steiner hingga keselarasan berganda yang kompak, Ilmu Komputer Teoritis, Volume 414, Edisi 1, 2012

Dynamic Time Warp membandingkan poin data yang direalisasikan, yang mungkin atau mungkin tidak berfungsi. Pendekatan yang lebih ketat adalah membandingkan distribusi deret waktu dengan metrik yang disebut jarak teleskop .

Yang keren tentang metrik ini adalah bahwa perhitungan empiris dilakukan dengan memasang serangkaian pengklasifikasi biner seperti SVM.

Untuk penjelasan singkat, lihat ini .

Untuk rangkaian waktu pengelompokan, telah terbukti mengungguli DTW; lihat Tabel 1 di kertas aslinya [1].

[1] Ryabko, D., & Mary, J. (2013). Metrik berbasis klasifikasi biner antara distribusi deret waktu dan penggunaannya dalam masalah statistik dan pembelajaran. Jurnal Penelitian Pembelajaran Mesin, 14 (1), 2837-2856.

Iya nih. Pendekatan naif dan berpotensi lambat mungkin,

1. Buat semua kombinasi kluster Anda. k adalah untuk jumlah cluster dan n adalah untuk jumlah seri. Jumlah barang yang dikembalikan harus n! / k! / (n-k)!. Ini akan menjadi sesuatu seperti pusat-pusat potensial.
2. Untuk setiap seri, hitung jarak melalui DTW untuk setiap pusat di setiap kelompok kluster dan tetapkan ke minimum.
3. Untuk setiap kelompok cluster, hitung jarak total dalam kelompok individu.
4. Pilih minimum.

Saya menggunakan ini untuk proyek kecil. Ini adalah repositori saya tentang Time Series Clustering dan jawaban saya yang lain tentang ini.