Algoritma Mengesan Titik Perubahan harmonikawan, June 20, 2013August 2, 2024 Lama sangat tangguh nak cerita tentang phd aku yang makin lama, makin pening. Takpa, sebab nak betul betul philosophy tu, jadi nak tak nak, kita kena berusaha dan menggali, ianya seperti menggali harta karun, dan samalah juga kita mengembara untuk memahami erti kehidupan. Memang ada orang boleh buat phd, cepat je siap, dan ada orang memang lambat. Ianya bergantung juga kepada bidang yang kita selidiki. Kawan-kawan semua tanya, berapa lama dah buat, kalau saya ambil kira, kiranya dah 4 tahun lebih, dari sebelum daftar, mendaftar, kena tendang bright spark, dan sebagainya. Oklah, kali ini saya nak cerita sikit tentang algoritma pengesan perubahan. Apa yang special sangat benda ni ? Ok jom kita baca !! Pengenalan Saya rasa kalau anda baca tajuk kali ini, nampaknya macam mudah faham kan ? Contohnya, sebuah kereta yang sedang bergerak lurus, dan lepas itu tiba-tiba dia menukar laluan, bagaimana anda mengesan perubahan itu ? Cara paling mudah ialah melihat sendiri pergerakkan kereta itu melalui video, ataupun membuat perbandingan gambar. Gambar bawak kereta lurus kan tak sama dengan gambar kereta tengah buat selekoh, jadi jika dibandingkan 2 gambar itu, tentu anda dapat mengesan bila kereta itu akan menukar haluan. Jadi anda spot masa perubahan itu bila. Senangkan ? Idea tentang perubahan ni memang senang ,jika anda lakukannya secara manual, dengan melihat sendiri perubahan gambar atau graf isyarat. Kenapa Perlu Automatik ? Hmm bayangkan anda perlukan orang menjaga sesuatu sistem, perhatikan betul-betul sistem itu. Contoh orang yang kerja tengok gelombang gempa bumi. Bayangkan, kerja dia tengok benda tu betul -betul, lepastu kalau tiba-tiba mengantuk macam mana ? Ataupun dia tengok , pastu cakap ada gempa bumi, tapi sebenarnya tidak ? Algorithma pengesan ini amatlah penting kepada kerja-kerja pemerhatian sebegini. Walaupun kita perlukan juga orang menjaganya, algoritma ini sangat penting, kerana ianya sebagai bantuan yang sangat berguna kepada pemerhati tersebut. Ianya membantu pemerhati itu membuat keputusan secara analitik, berdasarkan nombor dan statistik, dan bukannya main tembak sahaja. Apakah kriteria yang bagus untuk Pengesan Titik Perubahan ini ? Sepanjang yang saya belajar, banyak juga kriteria yang perlu diambil kira, tapi bukannya semua benda dapat kita kira dengan tepat dan berkesan, kadang-kadang ada juga yang terlambat, dan benda-benda ini bahaya jika kita lambat mengesan sesuatu perubahan itu. Contohnya macam gempa bumi, kalau kita lambat, lambatlah orang bertindak untuk menyelamatkan diri, terutama bila berlakunya tsunami di Acheh dan Fukushima. Beberapa perkara perlu diambil kira untuk algoritma ini antaranya ialah Boleh meramal – Satu kriteria terpenting untuk algoritma itu meramal bila akan berlakunya perubahan sesuatu sistem fizikal. Contohlah , macam sistem gempa bumi tadi, kalau kita dapat meramal dengan tepat, sistem amaran dapat dikeluarkan dan rakyat jelata dapat bertindak sebelum sesuatu yang buruk berlaku. Mengambil kira pengalaman lama – Bayangkan jika kita perhatikan sesuatu perkara, orang baru mungkin tak faham, tapi orang yang lebih arif, tentu tahu apa yang berlaku. Algoritma begini amat penting, kerana mengambil kira data-data lama, dan pengalaman lalu amat sesuai buat membantu orang baru untuk membuat keputusan berdasarkan pengesan titik perubahan. Ianya membuatkan pengesan itu lebih cekap dan berkesan. Bolehkan kita memprogramkan “pengalaman” ini ? Ya, memang ada konsep begini, nanti kita buka topik lain. Boleh mengagak isyarat sebenar – Sesuatu pengukuran, tentunya ada noise dan kotoran yang perlu dibersihkan. Sistem pengesan apapun, perlu mengambil kira dan menapis isyarat ini supaya ianya lebih mudah di proses dan menggambarkan isyarat sebenar sebuah sistem. Kerja filter sebegini, kita boleh serahkan kepada Pakcik Kalman hehehe. Real -Time -Kalau boleh, semuanya nak kena berlaku secara real-time, cepat dan tepat. Contohnya kalau kita buat permainan interaktif seperti Wii yang perlu detect pergerakan tangan kita, tentunya algorithm tu kena real-time, kalau tak susah nak kesan. Dulu juga saya pernah cerita bagaimana Iron Man boleh kawal armornya dengan hanya menggunakan otak ? Kalau algorithm itu lambat membuat pengiraan, habis lambat armor Iron Man tu nak berlawan. Online dan offline Secara dasarnya, algoritma kita buat secara offline dulu. Kita mengumpul data-data yang lepas, dan mula menerbitkan formula matematik berkenaan. Dengan offline, kita dapat menguji dulu ketepatan algoritma kita, sebelum kita betul-betul memprogramkan algoritma itu untuk tujuan online, yang perlukan pengiraan yang pantas dan peranti yang betul-betul canggih dan berkesan. Dalam penyelidikan pula, ramai yang menggunakan offline sebagai hasil keluaran, kerana di dalam kajian mereka itu, banyak perkara yang mereka ambil kira untuk menghasilkan suatu formula atau algoritma yang bagus untuk mengesan sesuatu titik perubahan. Parameteric vs Nonparametric Biasanya, sesuatu isyarat boleh di modelkan dengan membuat beberapa anggapan seperti gaussian noise dan sebagainya. Parametric bolehlah dikatakan satu kaedah yang amat popular kerana keberkesanannya, dan ianya menarik jika kita lebih tahu apa matematik model yang betul-betul menggambarkan isyarat yang hendak kita kaji itu. Berbeza pula dengan nonparametric yang tidak membuat apa-apa anggapan tentang isyarat tersebut. Kaedah nonparametric terus menerus memproses isyarat yang ada, dan ianya sangat berguna. Satu kaedah matematik yang dipanggil Wavelet Transform, boleh memberikan kita gambaran yang lebih jelas tentang sesuatu isyarat itu, dari segi masa dan frekuensi. Jika berlakunya sedikit perubahan frekuensi pada sesuatu isyarat, kaedah wavelet dapat mengesan perubahan tersebut dengan mudah. Tapi aku sendiri sampai sekarang tak dapat nak faham betul-betul matematik Wavelet ini. Bayesian dan Statistik Jika kita inginkan modelkan knowledge lama yang kita tahu, kiranya kaedah bayesian dapat digunakan untuk menerbitkan suatu kebarangkalian, bilakah perubahan itu berlaku. Biasanya kaedah bayesian ini agak bebas digunakan, tapi untuk memahamkannya, ianya perlukan pemahaman matematik yang betul betul mendalam. Kalau dapat faham kaedah bayesian ini, kita boleh terbitkan rumus matematik sendiri, dengan membuat beberapa anggapan terhadap isyarat yang hendak dikaji. Statistik juga sering digunakan jika kita ingin mengkaji perubahan yang berlaku. Secara mudahnya, sesuatu isyarat yang berubah akan memberikan nilai statistik, ataupun model statistik yang berbeza dengan isyarat sebelum berubah. Salah satu formula khas untuk mengira perubahan statistik ini ialah Kullback-Leibler Divergence. (KLD). Jika kita ada dua data berbeza, kita boleh tengok berapa banyak bezanya dengan gunakan KLD ni. Kalman Filter Sebelum ini saya pernah bercerita tentang Kalman Filter dan pengesan titik perubahan di entry statistik. Secara normalnya, Kalman filter hanya mampu digunakan untuk mengeluarkan isyarat yang bersih dari isyarat yang diganggu dengan noise. Selain itu juga, Kalman Filter juga sangat sesuai digunakan untuk algoritma online, kerana pengiraannya cepat, dan hanya memerlukan satu data sebelum untuk meramalkan apa yang berlaku. Kebanyakan penyelidik menggabungkan Kalman Filter dengan beberapa formula statistik seperti Cumulative Sum Control Chart (CUSUM) untuk mengira berapa banyak perubahan yang berlaku. Selain itu terdapat juga formula lain seperti Exponentially Weighted Moving Average (EWMA) dan sebagainya. Multiple Model Kalman Filter Cara paling menarik untuk mengesan sesuatu perubahan ialah dengan menggunakan kaedah Multiple Model. Secara normalnya, sesuatu model boleh di dimodelkan dengan Model A, yang mungkin hanya suatu model biasa. Jika kita tahu perubahan yang berlaku, kita boleh modelkan isyarat yang berubah itu dengan Model B. Dengan membuat beberapa terbitan matematik dengan kaedah bayesian, kita boleh mencari, kebarangkalian bagi sesuatu model itu benar jika diberikan data sebelumnya. Melihat kepada gambarajah dibawah, kita mengetahui, kebarangkalian isyarat normal akan mengikut Model A lebih tinggi dari Model B. Tetapi jika perubahan berlaku, kebarangkalian Model B akan lebih dominan, dan di situ kita boleh anggarkan titik perubahan yang kita inginkan. Penutup Banyak lagi cara lain yang boleh digunakan. Ianya bergantung kepada sesuatu aplikasi dan kajian yang betul-betul kita minta. Saya memang berusaha mendalami ilmu Kalman Filter ini, dan banyak juga evolusi yang berlaku terhadap filter ini. Jadi evolusi ini akan saya ceritakan di post yang akan datang. Oklah, selamat memotivasikan diri. Gambar kat atas tu pun hasil dari kerja phd saya yang baru sikit ini, hehehe. Related Related Posts:Pengesan Perubahan Struktur IsyaratStatistik : Teori dan AplikasiCara Pengiraan KebarangkalianCara Kira Bonus Shaklee3 Sebab Nak Buat VLOGMari BerusahaKalman Filter : Bahagian 2Apa Itu PHD ?Tukar Duit Raya Jadi EmasCadangan Vitamin Menyusu Shaklee Mampu Milik SAINS