Pemilu Presiden Indonesia 2014: Pendekatan Pembelajaran Mesin

Pemilihan Umum Presiden Indonesia tahun 2014 sudah berakhir. Kalau boleh saya bilang ini pemilu presiden paling ramai yang pernah saya ikuti (walaupun saya belum ikut banyak pemilu sebenarnya, baru 2 kali sejak dapat KTP 7 tahun lalu). Orang berantem setiap hari di media sosial karena beda pilihan presiden (Facebook belum terlalu beken lima tahun lalu kayaknya). Yang bikin kurang sedap adalah banyak munculnya berita/tudingan/tuduhan yang kebenarannya tidak dapat dipertanggungjawabkan. Setelah saya pikir-pikir, mungkin hal-hal seperti ini ada baiknya juga sebagai bahan pembelajaran untuk kita semua warga Indonesia agar semakin cerdas dan dewasa, salah satunya dalam masalah politik. Nanti ke depannya, pada pemilu yang berikutnya misalnya, kita bisa memilih dan menyikap dengan lebih bijak.

Kebetulan saya kemarin bertugas menjadi salah satu petugas pelaksana pemilu luar negeri (PPLN) untuk negara Stockholm dan Latvia. Pemilu di luar negeri tentunya mempunyai nuansa yang agak berbeda dibandingkan di dalam negeri. Di luar negeri, penggunaan hak pilih dapat dilakukan melalui pos atau datang langsung ke TPS.

Jumlah pemilih di seluruh Swedia mencapai sekitar 700an. Untuk TPS, di Stockholm ada 1 TPS yang didirikan di Wisma Duta KBRI Stockholm. Alhamdulillah pemilu berjalan lancar sampai akhir. Hasil penghitungan akhir dapat dilihat di http://indonesiskaambassaden.se/hasil-pemilu/.

Persiapan dan pelaksanaannya sendiri tidak terlalu susah. Yang paling sulit mungkin adalah masalah pendataan pemilih yang datanya sudah tidak valid (sudah pindah atau ganti kewarganegaraan) atau tidak terdaftar sebagai pemilih karena tidak melapor ketika datang ke KBRI Swedia. Mungkin solusinya bisa menggunakan personnummer?

tps
TPS di Stockholm. Sepi ya, enggak kayak di Hong Kong.
20140909_120934
Perlengkapan pemilu untuk yang memilih lewat pos.

Ketatnya pemilu kali ini memunculkan wacana “kawal pemilu” untuk menjaga agar tidak terjadi kecurangan. Bak gayung bersambut, KPU ternyata juga menyediakan hasil scan formulir C1 yang berisi hasil penghitungan suara di situsnya https://pemilu2014.kpu.go.id/c1.php. Bermunculanlah karyakarya orang-orang kreatif dan inisiatif Indonesia di seantero dunia yang menyediakan sarana bagi masyarakat untuk merekapitulasi suara dari form C1. Fenomena ini dijabarkan dengan apik oleh dosen saya Pak Ruli di sini: http://theconversation.com/open-election-data-mass-interaction-indonesian-public-as-watchdog-29450.

Fenomena ini sangat positif, apalagi mungkin bagi para pakar e-government yang mendukung open data. Akan tetapi, karena bidang ilmu saya adalah Machine Learning, saya melihat upaya crowdsourcing ini dalam cahaya yang berbeda. Saya melihat ini adalah kesempatan untuk mendapatkan data dengan labelnya yang nantinya bisa dipakai untuk supervised learning.

Data adalah hal yang berlimpah ruah di era internet seperti sekarang. Akan tetapi, kebanyakan data-data yang tersedia tersebut bersifat unsupervised atau tidak ada label yang menunjukkan bahwa data tersebut termasuk ke kategori apa. Pada zaman dahulu kala, biasanya data harus diklasifikasikan manual oleh expert (Kalau contohnya pengkategorian objek pada gambar, maka manusia, asal punya akal sehat, menjadi expert-nya. Kalau misalkan data medis, maka harus dokter yang melakukan proses labelling).

Di era sekarang, biasanya dataset dibuat disusun dengan menggunakan jasa crowdsourcing berbayar seperti misalnya Amazon Mechanical Turk (walau tetap harus disupervisi). Contoh datasetnya misalkan Image-Net dan Microsoft COCO. Tapi tetap yang bisa membuat dataset adalah institusi riset yang mempunyai funding atau korporasi besar yang memiliki kapital yang besar juga (Coba bayangkan berapa biaya yang dikeluarkan Microsoft untuk mengumpulkan data hingga ratusan ribu gambar ketika mendesain algoritma deteksi skeleton untuk Kinect).

Oleh karena itu, ini adalah kesempatan emas untuk mendapatkan data tulisan tangan digit angka orang Indonesia dengan jumlah yang banyak. Dalam satu form C1 terdapat 12 angka. Jika dikalikan dengan jumlah TPS yang mencapai lebih dari 400 ribu maka total kita bisa mendapatkan data training sebanyak hampir 5 juta data. Sebagai pembanding, data handwritten digit yang sering dipakai untuk benchmarking performa algoritma machine learning baru, MNIST (walaupun ini sebenarnya hanya subset dari dataset yang lebih besar lagi ukurannya), memiliki jumlah 60.000 data untuk training dan 10.000 data untuk testing.

Berangkat dari motivasi di atas, maka saya memutuskan untuk mencoba mengekstraksi gambar tulisan angka dari gambar dan mengumpulkannya menjadi sebuah dataset kemudian melakukan eksplorasi dan eksperimen klasifikasi dengan machine learning sehingga nantinya mungkin bisa dibuat program yang otomatis akan menghitung rekap suara hanya dengan meng-upload gambar C1. Ini saya kerjakan pada liburan musim panas kemarin disambung sela-sela kuliah semester ganjil sekarang.

Akuisisi Data

Ada beberapa situs yang menyediakan jasa crowdsourcing yang bisa dipilih. Saya memilih kawalpemilu.org karena sepertinya ini yang paling lengkap (kawalpemilu.org menyelesaikan scan C1 dari 478.685 TPS yang tersebar di seluruh Indonesia dengan mengandalkan tenaga 700an relawan dalam waktu kira-kira lima hari) dan sepertinya datanya dapat dengan mudah diekstrak (halamannya cuma pakai tag table jadi saya kira cukup parsing halaman HTML saja). Saya putuskan saya harus men-download dulu semua file gambar dan rekap karena saya tidak tahu sampai kapan data tersebut akan dibuka.

Ekspektasi kedua saya ternyata salah karena situs kawalpemilu adalah satu halaman aplikasi javascript. Tetapi setelah menengok isi source code-nya, ternyata hasil rekap bisa dirikues dari webservice (yang di-host di Google Apps Engine) dalam format json. Dari source code saya juga menjadi tahu kalau scan C1 juga dapat dirikues ke server dengan cukup menyediakan nama file dengan format nomor daerah sebanyak 7 digit, nomor tps di daerah tersebut sebanyak 3 digit, dan angka yang menunjukkan halaman C1 yang diminta, dari 01 sampai 04 (yang diperlukan halaman keempat).

Kurang lebih potongan kode untuk men-download semua file adalah sebagai berikut (file scrap.py)

import requests as req

def prefix_pad(s, n):
    """ Prepend string s with 0 until it has length of n
    :param s: The string to be prepended
    :param n: The final length of prepended string
    :return: The prepended string
    """
    while len(s) < n:
        s = '0' + s
    return s

def image_filename(i, j):
    """ Prepare the KPU formatted image filename
    :param i: the area code
    :param j: the station code
    :return: The formatted filename
    """
    return prefix_pad(i, 7) + prefix_pad(j, 3) + '04'

# Loop for every area in Indonesia
start_area = 1
end_area = 80000
tps = 0
for i in xrange(start_area, end_area):
    print 'Now donwloading data from area: ', i
    r = req.get('http://kawal-pemilu.appspot.com/api/tps/' + str(i))

    if r.text == 'Error':
        continue

    json = r.json()
    for j in xrange(len(json)):
        # Check to see whether there is no error in json and also there is vote count data inside
        if json[j][6] and json[j][7] == '0':
            # Download C1 scanned image
            print 'TPS ke: ', tps
            imfname = image_filename(str(i), str(j + 1))
            imreq = req.get('http://scanc1.kpu.go.id/viewp.php?f=' + imfname + '.jpg')

            # Save to file
            f = open('scrap/' + str(i) + '_' + str(j) + '.txt', 'w')
            f.write('prabowo, jokowi, suara sah, tidak sah' + '\n')
            prabowo_count = str(json[j][2])
            jokowi_count = str(json[j][3])
            valid_count = str(json[j][4])
            invalid_count = str(json[j][5])
            f.write(prabowo_count + ',' + jokowi_count + ',' + valid_count + ',' + invalid_count)
            f.close()
            f = open('scrap/' + str(i) + '_' + str(j) + '.jpg', 'wb')
            f.write(imreq.content)
            f.close()
            tps += 1

Setelah kode tersebut dieksekusi, butuh waktu hingga 3 minggu untuk men-download semua file gambar dan rekap json. Programnya sendiri harus di-restart beberapa kali. Hasil akhirnya adalah File gambar dengan jumlah cukup banyak sekitar 417 ribu dengan ukuran total 60 gigabytes yang sementara tersimpan dengan aman di harddisk eksternal saya. Setelah melakukan bersih-bersih dengan menghapus data yang korup, sekarang kita bisa melakukan hal-hal menarik terhadap data yang kita punya.

c1
Contoh beberapa file scan form C1 yang diunduh. Hampir semua gambar memiliki ukuran, resolusi, dan kondisi yang beraneka ragam seperti terbalik atau tertukan dengan halaman lain. Hal-hal seperti ini yang mempersulit proses ekstraksi nantinya.

Ektraksi Data

Menentukan Region of Interest.

Untuk mempercepat proses komputasi dalam mengekstrak angka yang ada di dalam gambar, kita potong gambar hingga hanya menjadi region of interest-nya saja. Hal yang mempersulit adalah resolusi gambar yang berbeda-beda. Jika harus ditangani satu per satu maka kode-nya bisa meledak. Setelah melakukan investigasi singkat, kira-kira ada 3 jenis ukuran resolusi, kecil, sedang, dan tinggi. Saya buatlah aturan yang mudah-mudahan mengakomodir semua gambar.

    dim = c1.shape
    y0 = 350
    y1 = y0 + 450
    if dim[0] < 1100:
        y0 = dim[0] * 300 / 1700
        y1 = y0 + dim[0] * 400 / 1700
    elif 1700 < dim[0] < 2400:
        y0 = 350
        y1 = y0 + 450
    else:
        y0 = dim[0] * 350 / 1700
        y1 = y0 + dim[0] * 450 / 1700
    x0 = dim[1] * 19 / 24

Ekstraksi Digit

Setelah kita mendapatkan area yang mengandung rekap suara, proses ekstraksi dapat dilakukan dengan mudah dan cepat. Ada 2 pendekatan yang saya gunakan. Pertama, ekstraksi menggunakan Hough transform yang mengambil inspirasi dari sini sudokugrab.blogspot.se/2009/07/how-does-it-all-work.html. Pendekatan kedua menggunakan Harris corner detection.

Extraction based Hough transform

Pertama, gambar perlu di-threshold menggunakan Otsu threshold untuk mendapatkan edge dari gambar. Tidak perlu teknik sulit-sulit macam Canny edge detection, karena gambar relatif bebas dari noise dan tidak terlalu kompleks.

Kemudian kita panggil fungsi untuk melakukan Hough transform. Dari Hough space ini kita bisa mendapat semua garis yag ada di gambar. Dari semua garis yang didapat, kita seleksi 4 garis yang paling dekat dengan sisi terluar gambar (2 vertikal, 2 horizontal). Dari pasangan garis tadi kita hitung titik perpotongan antara garis vertikal dan horizontal untuk mendapat pojok terluar dari kotak rekap.

Setelah mendapat 4 pojok dari kotak, kita lakukan transformasi Affine. Transformasi ini bisa dalam bentuk skala, rotasi, dan translasi di mana garis paralel sebelum transformasi akan tetap paralel setelah transformasi. Kita transformasi agar orientasinya lurus dan ukurannya seragam semua 400 x 150. Setelah ditransformasi cukup dipotong kotak-kotak sebanyak 12.

ekstrak digit
Tahapan proses, dimulai dari region of interest, thresholding, hough transform, dan terakhir transformasi.

 

Extraction based Harris corner

Berbeda dengan pendekatan menggunakan Hough transform, dengan corner detection kita sudah otomatis mendapatkan titik-titik yang potensial menjadi ujung dari kotak rekap suara tanpa harus melewati pencarian garis terlebih dahulu. Selanjutnya cukup mencari titik yang terdekat dengan keempat ujung gambar. Transformasi yang sama juga dilakukan setelah itu.

Akan tetapi setelah melihat hasil empiris, maka saya lebih memilih teknik Hough transform karena file gambar hasil akhir lebih rapi dibanding dengan corner detection. Hal ini ditengarai karena corner dapat terdeteksi pada posisi-posisi yang salah dan ini mengakibatkan angka setelah ditransformasi menjadi terdistorsi.

Batch process

Setelah sukses melakukan ekstraksi pada satu gambar C1, berikutnya proses ekstraksi  akan dijalankan ke semua gambar scan C1. Niatnya  awalnya ke semua gambar, tapi saya jalankan untuk 100.000 data pertama dahulu.

Hasil akhirnya ratusan ribu gambar angka berhasil terekstrak. Tetapi ternyata banyak gambar-gambar yang rusak karena salah ekstraksi (region of interest-nya salah sehingga kotak yang berisi angka tidak berhasil ditemukan atau terpotong). Oleh karena itu masih diperlukan seleksi secara manual (walaupun sebenarnya cepat untuk dilakukan, cukup Ctrl+X Ctrl+V, tapi membosankan untuk dilakukan). Hasil sementara ada 11 kelas (0 sampai 9 tambah kelas khusus X untuk digit ratusan atau puluhan yang nilai tidak sampai situ) dengan masing-masing kelas mempunyai 2000 data. Masih ada banyak lagi data yang bisa diambil, mungkin solusinya perlu di-crowdsourcing juga.

Semua proses di atas ada dalam modul extract.py di repositori.

digit.pn
Contoh subset dataset dengan 100 data per kelas. Datanya lumayan variatif kan…

Training & Testing

Setelah kita mendapatkan data per kelas yang cukup banyak kita bisa memulai proses training. Untuk proses ini saya menggunakan framework machine learning favorit saya, Weka. Weka men-support banyak algoritma serta memiliki kemampuan untuk menyimpan dan memuat model hasil pelatihan sebelumnya. Untuk eksperimen awal ini, kita coba menggunakan data yang masih raw dan classifier nearest neighbor (di weka namanya adalah IB1). Kita coba pada dataset yang kecil terlebih dahulu, dengan ukuran 500 instance per kelas.

weka load data
500 data per kelas, masing-masing data memiliki 5000 fitur.

Dengan skema 10-fold cross validation, akurasi yang didapatkan adalah sekitar 60%. Hmm, tidak terlalu buruk. Tentunya hasil akurasi di atas bisa ditingkatkan lebih lanjut, dengan menggunakan teknik-teknik ekstraksi fitur yang lebih canggih atau menggunakan classifier yang lebih powerful dan dilakukan fine tuning hingga hanya memiliki error yang sangat kecil.

weka run
Hasil klasifikasi dalam bentuk akurasi dan confusion matrix.

Terakhir, kita buat tampilan grafik yang digunakan untuk memuat dan melakukan ekstraksi dan klasifikasi digit dengan model yang telah didapatkan. GUI dibuat dengan Tkinter.

gui
Tampilan GUI awal; setelah me-load scan lembar C1 dan model; serta setelah diproses.

Kalau dilihat-lihat hasilnya ada salah prediksi untuk angka 2 dan karakter X. Yah, lumayanlah…

Penutup

Demikian kira-kira bagaimana ilmu machine learning bisa ikut-ikutan pada hajatan pemilu 2014. Kalau kawalpemilu butuh 5 hari untuk merekap semua suara, maka dengan bantuan komputer seharusnya itu bisa selesai lebih cepat lagi. Jika ada yang mempunyai ide berbeda untuk tahap pengekstrakan agar lebih efektif, bisa langsung dengan me-fork repositori dan langsung implementasi atau langsung kirim email untuk berdiskusi.

Untuk file dataset dapat di-download di http://db.orangedox.com/ontgRUzd9EjjlxZVoD/11c_2000i.zip. Kalau perlu gunakan module prepare_input.py untuk membaca file gambar dan menjadikannya ke file CSV yang siap diproses di Weka.

Rencananya akan saya update begitu saya bisa memisahkan lebih banyak data lagi per kelasnya. Sementara kode untuk semua bisa dilihat di repository github: https://github.com/mitbal/pemilu

Post-post berikutnya kita akan membahas metode ekstraksi fitur dan klasifikasi yang lebih powerful. Mudah-mudahan bisa coba sampai metode representasi fitur yang state-of-the-art macam fitur CNN.

Semoga berguna. Salam.

4 thoughts on “Pemilu Presiden Indonesia 2014: Pendekatan Pembelajaran Mesin

  1. Memang berat ya pak kalau machine learning dibuat untuk masalah kritis semacam ini.
    Kayanya jumlah data latih masing berpengaruh besar untuk tingkat akurasinya. Mungkin butuh 1000 perkategori kali yah :D . Kalau udah diatas 95 persen mungkin baru bisa dimainkan ketahap produksi, soalnya orang bisa pada ribut kalau mesinnya salah :D.
    Thanks!

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s