Bagaimana saya bisa secara terprogram mendeteksi segmen dari seri data agar sesuai dengan kurva yang berbeda?

14

Apakah ada algoritma yang didokumentasikan untuk memisahkan bagian-bagian dari dataset yang diberikan ke dalam kurva berbeda yang paling sesuai?

Sebagai contoh, kebanyakan manusia yang melihat bagan data ini akan dengan mudah membaginya menjadi 3 bagian: segmen sinusoidal, segmen linier, dan segmen eksponensial terbalik. Sebenarnya, saya membuat ini dengan gelombang sinus, garis dan rumus eksponensial sederhana.

Bagan data dengan tiga bagian berbeda terlihat

Apakah ada algoritma yang ada untuk menemukan bagian-bagian seperti itu, yang kemudian dapat secara terpisah dipasang ke berbagai kurva / garis untuk membuat semacam rangkaian campuran kumpulan data yang paling cocok?

Perhatikan bahwa meskipun contoh memiliki ujung segmen yang cukup banyak berbaris, ini tidak selalu menjadi kasus; mungkin juga ada sentakan tiba-tiba pada nilai pada cutoff segmen. Mungkin kasus-kasus itu akan lebih mudah dideteksi.

Pembaruan: Ini adalah gambar dari sedikit data dunia nyata: Grafik dunia nyata

Pembaruan 2: berikut adalah kumpulan data dunia nyata yang luar biasa kecil (hanya 509 poin data):

4,53,53,53,53,58,56,52,49,52,56,51,44,39,39,39,37,33,27,21,18,12,19,30,45,66,92,118,135,148,153,160,168,174,181,187,191,190,191,192,194,194,194,193,193,201,200,199,199,199,197,193,190,187,176,162,157,154,144,126,110,87,74,57,46,44,51,60,65,66,90,106,99,87,84,85,83,91,95,99,101,102,102,103,105,110,107,108,135,171,171,141,120,78,42,44,52,54,103,128,82,103,46,27,73,123,125,77,24,30,27,36,42,49,32,55,20,16,21,31,78,140,116,99,58,139,70,22,44,7,48,32,18,16,25,16,17,35,29,11,13,8,8,18,14,0,10,18,2,1,4,0,61,87,91,2,0,2,9,40,21,2,14,5,9,49,116,100,114,115,62,41,119,191,190,164,156,109,37,15,0,5,1,0,0,2,4,2,0,48,129,168,112,98,95,119,125,191,241,209,229,230,231,246,249,240,99,32,0,0,2,13,28,39,15,15,19,31,47,61,92,91,99,108,114,118,121,125,129,129,125,125,131,135,138,142,147,141,149,153,152,153,159,161,158,158,162,167,171,173,174,176,178,184,190,190,185,190,200,199,189,196,197,197,196,199,200,195,187,191,192,190,186,184,184,179,173,171,170,164,156,155,156,151,141,141,139,143,143,140,146,145,130,126,127,127,125,122,122,127,131,134,140,150,160,166,175,192,208,243,251,255,255,255,249,221,190,181,181,181,181,179,173,165,159,153,162,169,165,154,144,142,145,136,134,131,130,128,124,119,115,103,78,54,40,25,8,2,7,12,25,13,22,15,33,34,57,71,48,16,1,2,0,2,21,112,174,191,190,152,153,161,159,153,71,16,28,3,4,0,14,26,30,26,15,12,19,21,18,53,89,125,139,140,142,141,135,136,140,159,170,173,176,184,180,170,167,168,170,167,161,163,170,164,161,160,163,163,160,160,163,169,166,161,156,155,156,158,160,150,149,149,151,154,156,156,156,151,149,150,153,154,151,146,144,149,150,151,152,151,150,148,147,144,141,137,133,130,128,128,128,136,143,159,180,196,205,212,218,222,225,227,227,225,223,222,222,221,220,220,220,220,221,222,223,221,223,225,226,227,228,232,235,234,236,238,240,241,240,239,237,238,240,240,237,236,239,238,235

Ini dia, memetakan, dengan appoximate posisi beberapa dikenal elemen dunia nyata ujung-ujungnya ditandai dengan garis putus-putus, sebuah kemewahan yang kita tidak akan biasanya memiliki:

masukkan deskripsi gambar di sini

Satu kemewahan yang kita miliki, bagaimanapun, adalah ke belakang: data dalam kasus saya bukan deret waktu, tetapi agak berhubungan secara spasial; masuk akal untuk menganalisis seluruh dataset (biasanya 5.000 - 15.000 titik data) sekaligus, bukan secara berkelanjutan.

burung hantu
sumber
1
ps posting pertama ke CV; Saya seorang pengembang perangkat lunak dan saya biasanya lebih sering bergaul dengan SO. Maaf jika saya telah melanggar tabu lokal. Banyak pencarian saya untuk jawaban mengarah ke sini, jadi saya pikir ini akan menjadi tempat terbaik untuk bertanya.
whybird
Mengapa Anda tidak memposting data dan saya akan mencoba menjawab pertanyaan Anda dengan contoh.
IrishStat
x
1
Anda membuat contoh sehingga ide itu masuk akal: sejauh ini, sangat bagus. Dengan histogram nyata, jauh lebih umum bahwa bentuk rumit mencerminkan campuran distribusi yang tumpang tindih: minat tidak kemudian berubah dalam histogram yang diamati yang umumnya tidak ada secara meyakinkan atau bukan cara yang tepat untuk memikirkan campuran. Namun, mungkin saja Anda menggunakan "histogram" dengan cara yang jauh lebih luas daripada standar dalam ilmu statistik yang artinya bagan batang frekuensi atau distribusi probabilitas (hanya).
Nick Cox
@IrishStat - kumpulan data biasa memiliki 5.000 hingga 15.000 entri. Saya sedang mencoba menyiapkan yang dirangkum yang asli untuk di sini, tetapi ternyata itu menjadi contoh yang buruk, dan saya harus memulai dari awal. Di sisi lain, melakukan itu memang menyarankan jawaban parsial kepada saya dalam hal hanya menghaluskan dan rata-rata gumpalan data untuk mencari awalnya untuk pola, untuk dikerjakan nanti jadi terima kasih untuk itu :) Saya punya yang asli hanya 509 lebar yang sepertinya itu bisa baik; Saya akan menambahkan itu ke pertanyaan ketika saya bisa.
whybird

Jawaban:

2

Interpretasi saya terhadap pertanyaan adalah bahwa OP mencari metodologi yang sesuai dengan bentuk contoh yang diberikan, bukan residu HAC. Selain itu, rutinitas otomatis yang tidak memerlukan intervensi manusia atau analis yang signifikan juga diinginkan. Box-Jenkins mungkin tidak sesuai, meskipun mereka ditekankan dalam utas ini, karena mereka memang membutuhkan keterlibatan analis yang substansial.

Modul R ada untuk jenis yang tidak berbasis momen, pencocokan pola. Clustering distribusi permutasi adalah teknik pencocokan pola yang dikembangkan oleh ilmuwan Max Planck Institute yang memenuhi kriteria yang telah Anda uraikan. Aplikasinya adalah untuk data deret waktu, tetapi tidak terbatas pada itu. Berikut kutipan untuk modul R yang telah dikembangkan:

pdc: Paket R untuk Clustering Time Series Berbasis Kompleksitas oleh Andreas Brandmaier

Selain PDC, ada pembelajaran mesin, rutin iSax dikembangkan oleh Eamon Keogh di UC Irvine yang juga layak untuk dibandingkan.

Akhirnya, ada makalah ini Penghancuran Data: Mengungkap Urutan Mengintai dalam Dataoleh Chattopadhyay dan Lipson. Di luar judul yang cerdik, ada tujuan serius di tempat kerja. Berikut abstraknya: "Dari pengenalan suara otomatis hingga menemukan bintang yang tidak biasa, yang mendasari hampir semua tugas penemuan otomatis adalah kemampuan untuk membandingkan dan membedakan aliran data satu sama lain, untuk mengidentifikasi koneksi dan menemukan outlier. Meskipun terdapat prevalensi data, metode otomatis tidak mengikuti kecepatan. Hambatan utama adalah bahwa sebagian besar algoritma perbandingan data saat ini bergantung pada seorang ahli manusia untuk menentukan 'fitur' data yang relevan untuk perbandingan. Di sini, kami mengusulkan prinsip baru untuk memperkirakan kesamaan antara sumber-sumber sewenang-wenang. aliran data, tidak menggunakan pengetahuan domain atau pembelajaran. Kami mendemonstrasikan penerapan prinsip ini untuk analisis data dari sejumlah masalah yang menantang di dunia nyata, termasuk disambiguasi pola elektro-ensefalograf yang berkaitan dengan kejang epilepsi, deteksi aktivitas jantung anomali dari rekaman suara jantung dan klasifikasi benda-benda astronomi dari fotometri mentah. Dalam semua kasus ini dan tanpa akses ke pengetahuan domain apa pun, kami menunjukkan kinerja yang setara dengan akurasi yang dicapai oleh algoritma dan heuristik khusus yang dirancang oleh para pakar domain. Kami menyarankan bahwa prinsip-prinsip penghancuran data dapat membuka pintu untuk memahami pengamatan yang semakin kompleks, terutama ketika para ahli tidak tahu apa yang harus dicari. " Dalam semua kasus ini dan tanpa akses ke pengetahuan domain apa pun, kami menunjukkan kinerja yang setara dengan akurasi yang dicapai oleh algoritma dan heuristik khusus yang dirancang oleh para pakar domain. Kami menyarankan bahwa prinsip-prinsip penghancuran data dapat membuka pintu untuk memahami pengamatan yang semakin kompleks, terutama ketika para ahli tidak tahu apa yang harus dicari. " Dalam semua kasus ini dan tanpa akses ke pengetahuan domain apa pun, kami menunjukkan kinerja yang setara dengan akurasi yang dicapai oleh algoritma dan heuristik khusus yang dirancang oleh para pakar domain. Kami menyarankan bahwa prinsip-prinsip penghancuran data dapat membuka pintu untuk memahami pengamatan yang semakin kompleks, terutama ketika para ahli tidak tahu apa yang harus dicari. "

Pendekatan ini jauh melampaui fit lengkung. Perlu dicoba.

Mike Hunter
sumber
Terima kasih - Anda benar bahwa yang saya inginkan adalah menemukan cluster secara otomatis, tanpa campur tangan analis. Untuk apa yang ingin saya lakukan untuk bekerja, saya perlu memecah set data 5.000-15.000 poin data ke dalam kelompok yang masing-masing sesuai dengan rumus sederhana (termasuk yang berulang) tanpa campur tangan manusia terhadap kelompok sekitar 50000 kumpulan data dalam jangka waktu yang dapat ditoleransi oleh manusia pada perangkat keras komputer domestik.
whybird
Adapun kurva mana yang cocok untuk setiap cluster, setelah saya mendeteksi batas dengan cara apa pun, cukup sederhana saya pikir untuk hanya mencoba model yang berbeda (gelombang sinus, polinomial, eksponensial) dan melihat mana yang memberikan r ^ 2 biasa lebih baik.
whybird
2
OK, saya pikir miskomunikasi muncul dari ini: Sax dan iSax adalah format representasi untuk menyimpan dan memproses deret waktu, mereka bukan pengelompokan atau algoritma deteksi segmen / pola (per pos OP). Pemahaman saya dari jawaban Anda adalah bahwa Keogh telah datang dengan algoritma yang didasarkan pada format representasi SAX dan terjadi untuk mengatasi masalah OP. Tapi saya pikir ini bukan yang Anda maksud?
Zhubarb
2
OK, tidak perlu menjangkau Keogh, saya tahu tentang iSax dan Sax , mereka adalah format representasi untuk penambangan seri waktu yang efisien. Tautan menjelaskannya. iSax adalah versi yang lebih baru. Saya senang dengan kesalahpahaman saya tentang jawaban Anda, maka pertanyaan-pertanyaannya (tidak berusaha untuk menjadi terlalu tinggi) :).
Zhubarb
2
saya tidak berusaha menyembunyikan apa pun, saya menafsirkan 'isax routine' sebagai algoritma yang beroperasi pada isax. Saya sarankan jawaban Anda perlu diulang / dimodifikasi setelah klarifikasi.
Zhubarb
2

Mendeteksi titik-titik perubahan dalam suatu rangkaian waktu membutuhkan pembuatan model ARIMA global yang kuat (tentu saja cacat oleh perubahan model dan perubahan parameter dari waktu ke waktu dalam kasus Anda) dan kemudian mengidentifikasi titik perubahan paling signifikan dalam parameter-parameter model itu. Menggunakan nilai 509 Anda, titik perubahan paling signifikan adalah sekitar periode 353. Saya menggunakan beberapa algoritma kepemilikan yang tersedia di AUTOBOX (yang telah saya bantu kembangkan) yang mungkin bisa dilisensikan untuk aplikasi khusus Anda. Ide dasarnya adalah untuk memisahkan data menjadi dua bagian dan setelah menemukan titik perubahan yang paling penting, analisis kembali masing-masing dari dua rentang waktu secara terpisah (1-352; 353-509) untuk menentukan titik perubahan lebih lanjut dalam masing-masing dari dua set. Ini diulangi hingga Anda memiliki k himpunan bagian. Saya telah melampirkan langkah pertama menggunakan pendekatan ini.masukkan deskripsi gambar di sini

masukkan deskripsi gambar di sini

IrishStat
sumber
Mengapa 353 ditandai ketika 153 dan 173 memiliki nilai-P yang lebih rendah?
Nick Cox
@NickCox Pertanyaan bagus! Komentar yang bagus Untuk tujuan peramalan, seluruh idenya adalah untuk memisahkan subset terbaru (signifikan) dari subset yang lebih lama, itulah sebabnya 353 dimenangkan .... Untuk tujuan di sini orang memang akan memilih 173.
IrishStat
Judul "POINT BREAK SIGNIFIKAN
YANG
Terima kasih! Ini sangat menarik dan sangat dihargai. Saya mungkin menghubungi Anda untuk perincian lebih lanjut.
whybird
Terima kasih atas penjelasannya: idenya memang eksplisit di catatan terakhir. (kebetulan, saya belum melihat KASUS UPPER dalam output program sejak sekitar awal 1990-an. Saya akan merekomendasikan mengubah "tingkat kepercayaan 95%" menjadi "tingkat signifikansi 5%" dengan asumsi itulah yang dimaksud.)
Nick Cox
2

Saya pikir judul utasnya menyesatkan: Anda tidak mencari untuk membandingkan fungsi kerapatan tetapi sebenarnya Anda mencari penahan struktural dalam rangkaian waktu. Namun, Anda tidak menentukan apakah jeda struktural ini seharusnya ditemukan di jendela waktu bergulir atau di belakang dengan melihat riwayat total rangkaian waktu. Dalam hal ini pertanyaan Anda sebenarnya merupakan duplikat dari ini: Metode apa untuk mendeteksi jeda struktural pada rangkaian waktu?

Seperti yang disebutkan oleh Rob Hyndman dalam tautan ini, R menawarkan paket strucchange untuk tujuan ini. Saya bermain-main dengan data Anda tetapi saya harus mengatakan bahwa hasilnya mengecewakan [apakah titik data pertama benar-benar 4 atau seharusnya 54?]:

raw = c(54,53,53,53,53,58,56,52,49,52,56,51,44,39,39,39,37,33,27,21,18,12,19,30,45,66,92,118,135,148,153,160,168,174,181,187,191,190,191,192,194,194,194,193,193,201,200,199,199,199,197,193,190,187,176,162,157,154,144,126,110,87,74,57,46,44,51,60,65,66,90,106,99,87,84,85,83,91,95,99,101,102,102,103,105,110,107,108,135,171,171,141,120,78,42,44,52,54,103,128,82,103,46,27,73,123,125,77,24,30,27,36,42,49,32,55,20,16,21,31,78,140,116,99,58,139,70,22,44,7,48,32,18,16,25,16,17,35,29,11,13,8,8,18,14,0,10,18,2,1,4,0,61,87,91,2,0,2,9,40,21,2,14,5,9,49,116,100,114,115,62,41,119,191,190,164,156,109,37,15,0,5,1,0,0,2,4,2,0,48,129,168,112,98,95,119,125,191,241,209,229,230,231,246,249,240,99,32,0,0,2,13,28,39,15,15,19,31,47,61,92,91,99,108,114,118,121,125,129,129,125,125,131,135,138,142,147,141,149,153,152,153,159,161,158,158,162,167,171,173,174,176,178,184,190,190,185,190,200,199,189,196,197,197,196,199,200,195,187,191,192,190,186,184,184,179,173,171,170,164,156,155,156,151,141,141,139,143,143,140,146,145,130,126,127,127,125,122,122,127,131,134,140,150,160,166,175,192,208,243,251,255,255,255,249,221,190,181,181,181,181,179,173,165,159,153,162,169,165,154,144,142,145,136,134,131,130,128,124,119,115,103,78,54,40,25,8,2,7,12,25,13,22,15,33,34,57,71,48,16,1,2,0,2,21,112,174,191,190,152,153,161,159,153,71,16,28,3,4,0,14,26,30,26,15,12,19,21,18,53,89,125,139,140,142,141,135,136,140,159,170,173,176,184,180,170,167,168,170,167,161,163,170,164,161,160,163,163,160,160,163,169,166,161,156,155,156,158,160,150,149,149,151,154,156,156,156,151,149,150,153,154,151,146,144,149,150,151,152,151,150,148,147,144,141,137,133,130,128,128,128,136,143,159,180,196,205,212,218,222,225,227,227,225,223,222,222,221,220,220,220,220,221,222,223,221,223,225,226,227,228,232,235,234,236,238,240,241,240,239,237,238,240,240,237,236,239,238,235)
raw = log(raw+1)
d = as.ts(raw,frequency = 12)
dd = ts.intersect(d = d, d1 = lag(d, -1),d2 = lag(d, -2),d3 = lag(d, -3),d4 = lag(d, -4),d5 = lag(d, -5),d6 = lag(d, -6),d7 = lag(d, -7),d8 = lag(d, -8),d9 = lag(d, -9),d10 = lag(d, -10),d11 = lag(d, -11),d12 = lag(d, -12))

(breakpoints(d ~d1 + d2+ d3+ d4+ d5+ d6+ d7+ d8+ d9+ d10+ d11+ d12, data = dd))
>Breakpoints at observation number:
>151 
>Corresponding to breakdates:
>163 

(breakpoints(d ~d1 + d2, data = dd))
>Breakpoints at observation number:
>95 178 
>Corresponding to breakdates:
>107 190 

Saya bukan pengguna biasa dari paket ini. Seperti yang Anda lihat, itu tergantung pada model yang Anda muat pada data. Anda dapat bereksperimen dengan

library(forecast)
auto.arima(raw)

yang memberi Anda model ARIMA pas terbaik.

HOSS_JFL
sumber
Terima kasih! Saya telah mengedit kata 'histogram' dari judul; Saya telah salah menggunakannya pada awalnya, dan lupa mengedit judul ketika saya menghapusnya dari tubuh di edit sebelumnya sebagai tanggapan terhadap komentar.
whybird
Data saya sebenarnya adalah serangkaian data yang berhubungan secara spasial, tidak berdasarkan waktu dan biasanya tidak akan ada pada garis lurus atau bahkan di dalam pesawat cukup sering - tetapi Anda benar bahwa pada tingkat dasar dapat dianggap sama. cara; Saya kira itu mungkin menjadi bagian dari mengapa pencarian saya sebelumnya tidak menemukan jawaban yang saya harapkan.
whybird
Poin data pertama dalam contoh itu adalah benar-benar 4, tetapi bisa jadi kita kebetulan mencapai akhir struktur sebelumnya atau mungkin itu noise; Saya akan senang meninggalkannya sebagai pencuri, tetapi sistem apa pun yang saya hasilkan harus mengatasi hal-hal seperti itu juga.
whybird
Oh, dan analisisnya di belakang. Saya akan mengedit pertanyaan untuk menjelaskan.
whybird