Komparasi Hidden Markov Model dan KD-Tree pada Proses Map Matching Berbasis Data GPS

ALFATH NUURLATHIF SULISTIANTO, Ir. Azkario Rizky Pratama, S.T., M.Eng., Ph.D. ; Widyawan, S.T., M.Sc., Ph.D.

2024 | Skripsi | TEKNOLOGI INFORMASI

Penggunaan data sebagai sumber informasi dalam pengambilan keputusan dapat digunakan pada berbagai bidang, seperti kebijakan pemerintahan. Tentunya, kebijakan pemerintahan memiliki dampak yang sangat besar karena seluruh masyarakat dapat merasakannya. Oleh karena itu, dibutuhkan tahapan perencanaan yang matang dan implementasi yang terstruktur. Data dapat menjadi salah satu parameter sebagai dasar pembuatan perencanaan dengan tepat. Kebijakan yang dibuat dapat mencakup berbagai lingkup, diantaranya mobilitas masyarakat. Contoh kebijakan pada lingkup tersebut adalah fasilitas kesehatan darurat yang dibangun pada wilayah Jawa dan Bali saat masa pandemi Covid-19. Terdapat berbagai jenis data yang dapat digunakan dalam perancangan kebijakan tersebut, salah satunya adalah Mobile Positioning Data (MPD). Data tersebut memiliki keunggulan karena dapat dikumpulkan dalam waktu singkat. Namun, data MPD memerlukan proses yang cukup rumit karena memiliki noise yang dapat memengaruhi informasi yang dihasilkan. Salah satu metode yang dapat digunakan dalam mengatasi noise tersebut adalah map matching. Penulis tertarik untuk membandingkan tingkat akurasi map matcing menggunakan algoritma Hidden Markov Model (HMM) dan KD-Tree. Dalam penelitian ini, kedua algoritma tersebut memproses beberapa kategori data GPS yang berbeda. Selain itu, dilakukan manipulasi pada data GPS yang digunakan, yaitu pengurangan secara acak. Parameter yang digunakan untuk membandingkan algoritma tersebut adalah simlarity score yang didapatkan dari nilai distances pada metode Dynamic Time Warping (DTW). Hasil pengujian menunjukkan algoritma HMM memiliki tingkat akurasi sekitar 80% untuk seluruh kategori data yang diujikan dan algoritma KD-Tree memiliki tingkat akurasi sekitar 55% untuk seluruh kategori data yang diujikan. Dapat disimpulkan, algoritma HMM lebih unggul dalam melakukan proses map matching untuk seluruh kategori data dibandingkan algoritma KD-Tree. Selain itu, ditemukan bahwa pengurangan data GPS secara acak dapat memengaruhi tingkat akurasi yang dihasilkan.

The use of data as a source of information in decision-making can be applied across various fields, such as government policy. Naturally, government policies have

a significant impact because the entire society can feel their effects. Therefore, careful planning and structured implementation are required. Data can serve as one of the parameters for accurate planning. Policies can cover a wide range of scopes, including public mobility. An example of such a policy is the emergency health facilities built in the Java and Bali regions during the COVID-19 pandemic. Various types of data can be used in designing these policies, one of which is mobile positioning data (MPD). This data is advantageous because it can be collected quickly. However, MPD requires a complex process due to noise that can affect the information produced. One method to address this noise is map matching. The author is interested in comparing the accuracy levels of map matching using the Hidden Markov Model (HMM) algorithm and the KD-Tree algorithm. In this study, both algorithms process different categories of GPS data. Additionally, there is manipulation of the GPS data used, specifically random reduction. The parameter used to compare these algorithms is the similarity score obtained from the distance values in the Dynamic Time Warping (DTW) method. The test results show that the HMM algorithm has an accuracy level of about 80% for all tested data categories, while the KD-Tree algorithm has an accuracy level of about 55% for all tested data categories. It can be concluded that the HMM algorithm is superior in performing map matching for all data categories compared to the KD-Tree algorithm. Furthermore, it was found that a random reduction of GPS data can affect the resulting accuracy levels. 

Kata Kunci : Data GPS, Map Matching, Hidden Markov Model, KD-Tree, Dynamic Time Warping