Algoritma untuk segmentasi data urutan

8

Saya memiliki urutan besar vektor dengan panjang N. Saya perlu beberapa algoritma pembelajaran tanpa pengawasan untuk membagi vektor ini menjadi segmen M.

Sebagai contoh:

masukkan deskripsi gambar di sini

K-means tidak cocok, karena menempatkan elemen serupa dari lokasi yang berbeda ke dalam satu cluster.

Memperbarui:

Data nyata terlihat seperti ini:

masukkan deskripsi gambar di sini

Di sini, saya melihat 3 kelompok: [0..50], [50..200], [200..250]

Pembaruan 2:

Saya menggunakan k-means yang dimodifikasi dan mendapatkan hasil yang dapat diterima ini:

masukkan deskripsi gambar di sini

Batas-batas kelompok: [0, 38, 195, 246]

machine-learning clustering sequence secara umum
sumber
2
Kualitas pertanyaan harus ditingkatkan untuk mendapatkan jawaban yang tepat misalnya apakah semua urutan selalu berubah pada titik yang sama (seperti bagaimana Anda digambarkan dalam contoh)?
Kasra Manshaei
Data saya yang sebenarnya lebih rumit. Ini adalah daftar vektor 9 dimensi. Saya akan menambahkan gambar ke bagian utama.
umum

Jawaban:

8

Silakan lihat komentar saya di atas dan ini adalah jawaban saya sesuai dengan apa yang saya mengerti dari pertanyaan Anda:

Seperti yang Anda katakan dengan benar, Anda tidak perlu Clustering tetapi Segmentasi . Memang Anda mencari Poin Perubahan dalam seri waktu Anda. Jawabannya sangat tergantung pada kompleksitas data Anda. Jika data sesederhana contoh di atas, Anda dapat menggunakan perbedaan vektor yang melampaui overshoot di titik-titik perubahan dan menetapkan ambang batas mendeteksi titik-titik seperti di bawah ini: masukkan deskripsi gambar di sini Seperti yang Anda lihat misalnya ambang 20 (yaitudx<-20 dan dx>20) akan mendeteksi poin. Tentu saja untuk data nyata Anda perlu menyelidiki lebih banyak untuk menemukan ambangnya.

Pra-pemrosesan

Harap dicatat bahwa ada trade-off antara lokasi akurat dari titik perubahan dan jumlah segmen yang akurat yaitu jika Anda menggunakan data asli Anda akan menemukan titik perubahan yang tepat tetapi seluruh metode adalah untuk sensitif terhadap kebisingan tetapi jika Anda memperlancar sinyal Anda terlebih dahulu Anda mungkin tidak menemukan perubahan yang tepat tetapi efek kebisingan akan jauh lebih sedikit seperti yang ditunjukkan pada gambar di bawah:

masukkan deskripsi gambar di sini masukkan deskripsi gambar di sini

Kesimpulan

Saran saya adalah untuk memperlancar sinyal Anda terlebih dahulu dan pergi untuk mthod pengelompokan sederhana (misalnya menggunakan GMM ) untuk menemukan estimasi akurat dari jumlah segmen dalam sinyal. Dengan informasi ini, Anda dapat mulai menemukan titik perubahan yang dibatasi oleh jumlah segmen yang Anda temukan dari bagian sebelumnya.

Saya harap semuanya membantu :)

Semoga berhasil!

MEMPERBARUI

Untungnya data Anda cukup mudah dan bersih. Saya sangat merekomendasikan algoritma pengurangan dimensionalitas (misalnya PCA sederhana ). Saya kira itu mengungkapkan struktur internal cluster Anda. Setelah Anda menerapkan PCA ke data, Anda dapat menggunakan k-means jauh lebih mudah dan lebih akurat.

Solusi Serius (!)

Menurut data Anda, saya melihat distribusi generatif dari berbagai segmen berbeda yang merupakan peluang besar bagi Anda untuk mensegmentasi deret waktu Anda. Lihat ini (asli , arsip , sumber lain ) yang mungkin merupakan solusi terbaik dan paling canggih untuk masalah Anda. Gagasan utama di balik makalah ini adalah bahwa jika segmen yang berbeda dari rangkaian waktu dihasilkan oleh distribusi dasar yang berbeda, Anda dapat menemukan distribusi itu, menetapkan tham sebagai kebenaran dasar untuk pendekatan pengelompokan Anda dan menemukan cluster.

Sebagai contoh, asumsikan sebuah video panjang di mana 10 menit pertama seseorang bersepeda, dalam 10 menit kedua ia berjalan dan pada ketiga ia duduk. Anda dapat mengelompokkan tiga segmen (aktivitas) yang berbeda ini menggunakan pendekatan ini.

Kasra Manshaei
sumber
Terima kasih atas tanggapan terperinci. Seperti yang Anda lihat di atas, saya tidak dapat menggunakan ambang batas untuk urutan data nyata saya, saya pikir, itu terlalu rumit untuk itu. Saya mencoba untuk memodifikasi algoritma k-means, itu akan mempertimbangkan kondisi urutan (elemen hanya dapat milik salah satu dari dua cluster tetangga). Saya harap, bahwa saya tidak menemukan kembali roda. :)
generall
1
Saya pikir data Anda tidak terlalu berisik (yaitu rumit) dan Anda bisa mencari hal-hal ambang batas. intinya adalah bahwa Anda memiliki kesan data sehingga Anda dapat menggunakan algoritma yang agak diawasi yaitu mencoba untuk belajar ambang batas (dan berharap itu digeneralisasikan dengan baik!). Saya juga memperbarui jawaban saya untuk solusi yang bagus :)
Kasra Manshaei
Terima kasih atas tautan yang menarik, saya pikir, itu dapat digunakan untuk tujuan saya, tetapi untuk sekarang, saya menggunakan k-means dengan modifikasi saya, yang memberi saya hasil yang dapat diterima (gambar. Pertanyaan).
umum
1
hasil yang sangat bagus! langkah cerdas. Saya bangga dengan Anda: D Semoga Sukses!
Kasra Manshaei
1

K-means clustering diketahui memberikan minimum lokal, tergantung pada inisialisasi awal Anda dari pusat-pusat cluster.

Namun, segmentasi k-means dapat, saya pikir, diselesaikan secara global, karena kami tidak mengizinkan apa pun dalam menemukan solusi.

Saya dapat melihat dari komentar Anda bahwa Anda akhirnya berhasil mencapai segmentasi. Apakah Anda dapat memberikan umpan balik? Apakah solusi Anda solusi terbaik? Atau apakah Anda puas dengan solusi yang cukup baik?

Nolatar
sumber
Segmentasi K-means juga dapat memberikan minimum lokal, karena Anda masih perlu memilih medoid awal \ centroid. Solusi saya saat ini cukup baik untuk saya, tetapi saya tidak bisa mengklaim itu adalah yang terbaik. Saya dapat membagikan detail solusi saya jika Anda tertarik.
umum
Itu tergantung bagaimana Anda menerapkannya. Sementara itu, saya telah menemukan dalam beberapa literatur bahwa untuk segmentasi, layak untuk menemukan minimum global, dalam waktu polinomial.
Nolatar
0

Sama seperti saran: Anda dapat mencoba menggunakan algoritma DBSCAN, karena sering bekerja jauh lebih baik daripada K-means untuk pengelompokan

Kalau tidak, jika Anda ingin mencoba sesuatu yang baru untuk pengelompokan dan mempelajari beberapa hal menarik, saya sarankan Anda mencoba beberapa Analisis Data Topologis melalui diagram persisten. Saya meninggalkan Anda di sini intro mudah :)

https://towardsdatascience.com/persistent-homology-with-examples-1974d4b9c3d0

Davide ND
sumber