Agregasi Nilai Statistik
Data yang telah kita miliki adalah:
Dari PDF, segala nilai seperti rata-rata, median, p95, dan lainnya yang nantinya dibutuhkan dapat dihitung dengan mudah. Strategi yang akan saya gunakan adalah memperkirakan PDF-nya dengan Kernel Density Estimation (KDE).- Daftar ketibaan suatu bus, lengkap dengan:
- lokasi haltenya
- halte tujuan akhirnya
- waktu ketibaannya
- Daftar waktu tempuh suatu bus, lengkap dengan:
- halte awal
- halte akhir
- durasi
Untuk prototipe pertama, informasi statistik berikut perlu didapatkan dengan bermodalkan data mentah di atas:
- Distribusi probabilitas dalam bentuk PDF (Probability Density Function) untuk waktu tunggu di suatu halte, ke halte tujuan, pada suatu waktu.
- PDF untuk waktu tempuh bus antara setiap halte yang bertetanggaan.
Konsepnya cukup sederhana. Bayangkan bahwa waktu tunggu (dalam menit) untuk 15 hari sebelumnya dari halte Glodok ke Blok M pada 06:00 adalah: [3, 2, 4, 2, 5, 3, 7, 4, 2, 1, 4, 6, 1, 2, 2].
Apabila di-plot ke dalam histogram, bentuknya adalah:
Saya membayangkan bahwa konsep dari KDE adalah "melelehkan" setiap balok dari batangan-batangan di histogram menjadi bentuk yang lebih halus. Bentuk lelehan ini haruslah memiliki luas yang sama dengan balok tersebut, yaitu 1 unit. Semua balok akan dilelehkan menjadi bentuk yang seragam. Ketika suatu batangan terdiri dari banyak balok, tentu saja lelehannya akan saling bertumpuk.
Untuk penjelasan secara formal, silakan kunjungi Wikipedia: https://en.wikipedia.org/wiki/Kernel_density_estimation.
Pada Terasi, bentuk lelehan yang akan saya gunakan adalah bentuk segitiga.
Bayangkan apa yang terjadi apabila kita melelehkan seluruh balok penyusun histogram sebelumnya. Ingat bahwa lelehan ini masih "cair", sehingga lelehan yang bertumpuk akan turun. Berikut tampak akhirnya:
Kini didapatkanlah PDF kasarnya.
Perhitungan nilai lainnya menjadi sesederhana. Sebagai contoh, mencari median (=p50) sama dengan mencari nilai c sedemikian sehingga luas kurva dari x=0 sampai x=c sama dengan 0,50.
Selesai memikirkan konsepnya, saya lanjut dengan menuliskan kode menghitung informasi statistik. Bahasa yang digunakan adalah Javascript dari Node.js. Berhubung data yang dimiliki adalah JSON, saya pikir pengolahannya akan mudah.
Rutinitas untuk KDE saya buat dalam bentuk node modules di sini: https://www.npmjs.com/package/pdfast.
Sebenarnya perhitungannya cukup sederhana. Algoritmanya adalah:
- For all busstop x // untuk halte awal
- For all busstop d // untuk destinasi
- arrivals = get_past_arrivals(start=x, end=d, relative_past_day=15)
- Urutkan semua data di "arrivals" berdasarkan waktu (jam, menit, detik)
- Lakukan sliding window berdasarkan (jam, menit, detik) sambil mencari PDF-nya
- Sajikan PDF-nya dalam bentuk polyline, lalu hitung nilai statistik yang diperlukan dan cetak. Ini adalah hasil untuk halte awal x, halte tujuan d, dan waktu sesuai window di sliding window saat ini. Perhatikan gambar di bawah untuk lebih tepatnya.
Mengapa menggunakan sliding window? Dugaan saya adalah waktu tunggu pukul 06:00 dengan 06:01, 06:02, dan seterusnya hingga 06:15 sepertinya tidak jauh berbeda. Memang akan ada penaikan atau penurunan, bergantung memasuki jam sibuk atau tidak. Jadi idenya adalah mari kita melakukan "bucketing" (pengemberan?), sehingga setiap M menit menjadi 1 ember. Nilai M yang saya gunakan adalah 20 menit. Jadi dari 06:00..06:20, waktu tunggunya dianggap sama semua. Jadi cukup cari waktu tunggu pada 06:00, 06:20, 06:40, 07:00, dan seterusnya. Bucketing ini membantu mengkompresi banyaknya data yang dihasilkan menjadi 1/M saja.
Hal yang sama juga saya lakukan untuk waktu tempuh.Karena sifat aktivitas ini adalah menggabungkan data beberapa hari sebelumnya menjadi beberapa nilai, saya akan menyebutnya dengan proses "agregasi".
Pada akhirnya, didapatkanlah data yang saya inginkan. Apabila Anda tertarik, contohnya bisa dilihat di sini:
- Waktu tunggu: https://drive.google.com/open?id=1U-hHhI1MZas9NlRmfyYcXf4hcZBBllN4
- Waktu tempuh: https://drive.google.com/open?id=1rXTEQy8SNqx7JnCGXueQ0TblCWXKbVDc
Intepretasi salah satu data waktu tunggu untuk perjalanan dari Kota ke Blok M, pukul 06:00 dari berkas tersebut adalah:
- Rata-rata: 3 menit
- Median: 3 menit
- Persentil 90: 7 menit (pada 90% kasus, Anda hanya perlu menunggu paling lama 7 menit)
Angka yang sangat baik! Seandainya seluruh koridor memiliki layanan sebaik koridor 1...
Oh ya, saya masih punya data untuk uji coba yang saya lakukan:
 |
| PDF untuk Sawah Besar - Kota, pukul 12:00. Jelas terlihat bentuk distribusi eksponensialnya (tinggi di awal, lalu menurun secara drastis dan penurunannya menjadi semakin pelan). |
 |
| Waktu rata-rata menunggu bus di Sawah Besar untuk ke Kota, dari 00:00 sampai 23:59. Terlihat bahwa bus aktif beroperasi mulai pukul 5 sampai pukul 23. |
Proses agregasi data ini cukup dilakukan untuk satu hari, yang akan mengagregasi data 15 hari sebelumnya. Untuk ke depannya, bisa dibuat script untuk menjalankan agregasi setiap 00:00, untuk merotasi hari-hari yang dilibatkan dalam agregasinya (yang paling lama dikeluarkan, data seharian yang baru dimasukkan).
Kini angka-angka itu siap digunakan sebagai modal untuk perhitungan turunannya, misalnya meramalkan total waktu perjalanan dari suatu halte ke halte lainnya pada jam tertentu.
Pemodelan untuk Database
Dari pemanenan data mentah, diekstraksi, lalu "dimasak" menjadi data statistik yang matang. Kini saatnya data disimpan untuk nantinya disajikan ke aplikasi.
Arsitektur yang klasik untuk back end API adalah:
Arsitektur yang klasik untuk back end API adalah:
- Sebuah database yang menyimpan data
- Sebuah web server yang menerima request, lalu membalasnya dengan jawaban yang diminta.
Dalam kasus Terasi, jawabannya didapatkan dari database.
Apakah saya perlu database khusus? Seperti PostgreSQL, MySQL, atau sejenisnya?
Untuk menjawabnya, perlu dilihat dulu pola data Terasi. Polanya adalah:
Untuk menjawabnya, perlu dilihat dulu pola data Terasi. Polanya adalah:
- Setiap harinya, akan ada sebuah aktivitas "daur ulang" data yang berupa:
- Menghapus seluruh informasi waktu tunggu dan waktu tempuh
- Memasukkan seluruh informasi waktu tunggu dan waktu tempuh yang baru saja diagregasi
- Selain yang ada pada aktivitas "daur ulang", tidak akan ada operasi pengubahan data
- Operasi pembacaan data dipastikan hanya akan membaca 1 titik data (tidak pernah range query).
- Ukuran data cenderung tetap, kecuali ditambahkan koridor atau halte baru yang selama ini jarang terjadi.
Ternyata polanya sangat sederhana. Saya mempertimbangkan untuk menggunakan salah satu dari dua cara berikut:
- In memory database. Maksudnya adalah data cukup disimpan dalam berkas .txt saja. Lalu saat web server dinyalakan, web server akan membacanya dan menyimpannya dalam RAM dalam bentuk array. Dengan cara ini, seluruh operasi menjadi O(1) dan saya tidak perlu pusing dengan I/O. Syarat untuk bisa menggunakannya adalah RAM server cukup untuk menampung seluruh data.
- Database "sederhana" seperti MongoDB. Berhubung saya pernah menggunakannya. Rasanya cukup mudah dan fleksibel. Waktu itu sedang nge-tren, jadi boleh saja deh dicoba-coba. Operasinya menjadi tidak O(1) lagi, tetapi O(log N) dengan pengindeksan data yang benar. Kompleksitas logaritmik itu berasal dari B-Tree dalam MongoDB.
Setelah hitung-hitung memori, in memory database dapat digunakan.
Struktur Back End API
Inilah bagian penyajian data yang telah disimpan.
Untuk keperluan prototipe, saya hanya perlu menyediakan 2 end point:
Untuk keperluan prototipe, saya hanya perlu menyediakan 2 end point:
- GET /waiting-time/:startBusStop/:endBusStop/:time
- GET /travel-time/:startBusStop/:endBusStop/:time
... dan selesai.
Itu pun sekedar melihat data yang disimpan dalam array saja. Jadi seharusnya selesailah pembuatan back end ini.
Tapi ternyata tidak semudah itu. Hitung-hitungan memori saya ternyata tidak tepat. Karena back end diimplementasikan dengan Node.js, ternyata konsumsi memorinya tidak mudah diprediksi. Misalnya kita membuat array bilangan integer 32 bit sebesar N. Ukuran memori yang digunakan tidak semata-mata (sekitar) 4*N byte. Memang tidak mungkin sama dengan segitu, karena ada block size, paging, atau sejenisnya pada penyimpanan hard disk. Tetapi kurang lebih mestinya mirip. Pada kasus Node.js, ternyata memorinya meledak-ledak, sampai komputer saya thrashing.
Mungkin saya bisa hardcore untuk membuat web server dengan C++? Atau bahasa pemrograman yang bertipe data statis lainnya? Yang tidak perlu garbage collection? Karena tidak berhasil menemukan framework atau bahasa yang tepat, akhirnya saya memutuskan untuk menggunakan opsi database kedua, yaitu MongoDB.
Sekitar dua hari menulis script untuk memasukkan data ke database dan membuat back end API, akhirnya selesailah.
Itu pun sekedar melihat data yang disimpan dalam array saja. Jadi seharusnya selesailah pembuatan back end ini.
Tapi ternyata tidak semudah itu. Hitung-hitungan memori saya ternyata tidak tepat. Karena back end diimplementasikan dengan Node.js, ternyata konsumsi memorinya tidak mudah diprediksi. Misalnya kita membuat array bilangan integer 32 bit sebesar N. Ukuran memori yang digunakan tidak semata-mata (sekitar) 4*N byte. Memang tidak mungkin sama dengan segitu, karena ada block size, paging, atau sejenisnya pada penyimpanan hard disk. Tetapi kurang lebih mestinya mirip. Pada kasus Node.js, ternyata memorinya meledak-ledak, sampai komputer saya thrashing.
Mungkin saya bisa hardcore untuk membuat web server dengan C++? Atau bahasa pemrograman yang bertipe data statis lainnya? Yang tidak perlu garbage collection? Karena tidak berhasil menemukan framework atau bahasa yang tepat, akhirnya saya memutuskan untuk menggunakan opsi database kedua, yaitu MongoDB.
Sekitar dua hari menulis script untuk memasukkan data ke database dan membuat back end API, akhirnya selesailah.
Langkah Selanjutnya
Sejauh ini, berikut diagram aliran data yang dimulai dari API Transjakarta sampai digunakan di back end.
Beberapa keterangan untuk menyimpulkan:
Urusan data sudah selesai. Selanjutnya adalah pembuatan front end.
Beberapa keterangan untuk menyimpulkan:
- Pemanen bekerja setiap menit, menghasilkan snapshot lokasi setiap bus setiap menitnya
- Graph Transjakarta dihasilkan oleh manusia yang secara manual menuliskan hubungan halte + rute berikut polyline-nya.
- Pengekstrak dan pengagregat data akan bekerja setiap malam, memproses data yang telah didapatkan hari itu dan menghasilkan data waktu tunggu dan waktu tempuh. Hasil agregasi ini dimuat ke dalam database.
- Back end API membaca data dari database, dan menjadi dependensi dari front end (entah web, atau apps hp) & pengguna.
Urusan data sudah selesai. Selanjutnya adalah pembuatan front end.
Saya menghabiskan 1 hari untuk belajar D3.js (https://d3js.org/) untuk membuat halaman HTML + ajax yang mengambil data dari back end, lalu menampilkan grafik. Sekedar untuk keperluan melihat-lihat data dan mewaspadai anomali. Tentu saja, kalau waktu tunggu dari suatu halte ke halte lainnya mencapai berjam-jam, berarti ada kekacauan dalam algoritma yang digunakan.
Hasilnya terlihat menjanjikan, sehingga tahap selanjutnya adalah pembuatan aplikasi Androidnya. Saya menghabiskan waktu 2 minggu untuk belajar Android apps development di Udacity (https://www.udacity.com/) secara gratis.
Kemudian langsung lanjut membuat UI sederhana yang asal fungsionalitasnya bisa dicoba. Saya berhasil membuat search bar nama halte, pemilihan waktu, dan baru menampilkan data waktu tunggunya saja.
Tulisan mendatang akan menjelaskan kelanjutan dari proyek ini.
Tidak ada komentar :
Posting Komentar