Sequence Clustering

24 06 2008

Clustering on Sequential Pattern merupakan sub ilmu dari Data Mining dan Soft Computing.

Clustering on Sequential Pattern adalah suatu proses pengelompokan data, dimana data yang dikelompokkan merupakan suatu pola berurut dan feature dalam data yang muncul sebelumnya menentukan probabilitas dari kemunculan feature berikutnya. Clustering on Sequential Pattern bisa dilakukan dengan memanfaatkan berbagai jenis metode clustering yang salah satunya adalah metode mixture modelling.

Memodel data sequence dalam bentuk cluster dengan memanfaatkan teori probabilitas dapat dilakukan dengan dua cara yaitu:
1. Menganggap data sequence yang ada sebagai model Markov Chain
2. Dengan memanfaatkan metode Hidden Markov Model sebagai model dari data sequence yang ada

Untuk kasus yang pertama, sequential pattern dapat dimodel dengan Markov Chain, dimana order dari Markov Chain ini menentukan berapa banyak feature yang akan menentukan nilai dari feature yang akan datang. Umumnya Markov Chain yang digunakan adalah Markov Chain dengan order satu, dimana satu feature sebelumnya saja yang menentukan nilai feature yang akan datang beserta probabilitasnya. Markov Chain dengan order n, berarti bahwa sebanyak n feature sebelumnya yang menentukan nilai feature yang akan datang dan probabilitasnya.

Untuk kasus yang kedua, sequential pattern dapat dimodel menggunakan Hidden Markov Model yang merupakan perkembangan dari Markov Chain model. Hidden Markov Model mempunyai suatu variabel tambahan dibandingkan dengan Markov Chain yaitu berupa hidden variabel yang berfungsi untuk memodel jumlah dan jenis sumber darimana bagian-bagian dari sequence tersebut berasal.

Mixture modelling terhadap data sequence dilakukan dengan memodel Markov Chain model atau Hidden Markov Model yang didapatkan dari data sequence yang bersangkutan. Distance measure yang digunakan adalah log-likelihood dari sequence yang bersangkutan ke model sequence representasi dari cluster yang terbentuk. Dari pemodelan ini, akan didapatkan jumlah cluster yang paling sesuai, jenis data yang masuk di dalam masing-masing cluster dan juga proporsi (relative size) dari masing-masing cluster.

Beberapa variasi dari sequence analisis juga didapatkan dalam bioinformatics dimana proses sequence alignment juga perlu untuk dilaksanakan, untuk memastikan ada tidaknya mutasi dari suatu gen ke gen yang lain. Dalam penganalisaan web sequence juga sering didapatkan bahwa suatu sequence adalah mirip dengan sequence yang lain dimana satu bagian dari salah satu sequence tidak terdapat pada sequence lainnya.

Referensi:
Smyth P (1997). Clustering Sequences with Hidden Markov Models, Moser M. C. et al eds, Advances in Neural Information Processing Systems, vol 9, The MIT Press, page 648.
Rabiner L. R. (1999). A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of The IEEE, Vol. 77, No 2, pp. 257 – 286.


Actions

Information

2 responses

10 01 2009
Yudi Agusta

Mmm, contoh yang paling sederhana, mungkin mengklusterisasi deretan coin tossing dengan beberapa coin yang jenisnya berbeda-beda. Coin dengan karakteristik yang sama biasanya akan mempunyai sequence yang sama. Sehingga akan dikelompokkan ke dalam kelompok yang sama.

Contoh yang lebih advance mungkin untuk menentukan jenis musik para pemusik klasik. Maestro-maetro mana yang ada dalam satu kelompok bisa dianalisa menggunakan sequence clustering ini.

Semoga menjawab.

5 01 2009
bambs

Assalamualaikum..
dear P’ Yudi….

saya dalam squence clustering yang bapak tulis mendapatkan sedikit kesulitan dalam contoh aplikasi sederhana…

saya minta tolong diberi contoh kasus dan analisanya…
sehingga ditemukan solusinya
sebelumnya saya sampaikan terima kasih…
Wassalam…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: