Stockholm

Stockholm is a dark and cold place.

Kurang lebih itulah yang dikatakan oleh bapak2 pengurus museum Nobel yang memberikan kata sambutan pada acara acara Welcome Reception dari KTH kepada mahasiswa internasional, 15 purnama yang lalu, di Stockholm City Hall. Saya yang baru datang beberapa hari yang lalu seakan terhenyak. Karena sejak saya datang hingga hari itu, Stockholm saya rasakan dalam cahaya yang berbeda. Hangat serta sejuk, walau matahari bersinar begitu teriknya.

Hal itu akhirnya saya rasakan ketika kegelapan menyelimuti Stockholm dari musim gugur hingga 6 bulan ke depan. Dark karena awan tampaknya selalu menggentayangi langit. Cold karena suhu dari bulan Oktober sudah bergelayut di satu digit derajat. Terkadang kabut pekat juga turut menyelimuti sekujur kota. Tidak heran kalau ada mitos yang menyatakan kalau tingkat bunuh diri di Swedia tinggi, walaupun merupakan salah satu negara yang paling bahagia di dunia. Izinkan saya tumpahkan perasaan saya ke dalam puisi.

Matahari tak pernah benar-benar terbit

Dia hanya mengintip dari sela-sela awan yang sempit

Dapatkah kurasakan paparan sinarnya lagi

Perasaan hangat yang kini telah pergi

Mohon maaf kalau puisinya kurang bagus. Maklum dulu S1 saya gelarnya S.Kom alias Sastra Komputer. Untungnya Stockholm dapat kembali dinikmati pada waktu musim panas. Tapi keluhannya sekarang adalah waktu puasa yang lama. Haha, dasar saya yang memang kurang bersyukur.

the_mist

Asap kebakaran hutan Riau baru sampai utara, atau adegan dari film The Mist…

 

Walaupun Stockholm itu sangat indah, tetapi menurut saya ini bukan kota turis yang mempunyai banyak atraksi dibandingkan kota tujuan turis populer lainnya. Meme di bawah mungkin bisa sedikit mengilustrasikan keadaan Stockholm.

Stockhom tourist

Walaupun begitu, jika Anda terlanjur datang berikut tempat yang bisa dikunjungi. Saya kompilasi agar kalau ada yang tanya bisa saya arahkan langsung ke tulisan ini kalau misalkan dia tidak percaya dengan rekomendasi dari trip advisor atau wikitravel.

1. Central, Sergels Torg dan sekitarnya.

Kalau misalkan Anda datang dengan menggunakan pesawat dan turun di bandara Arlanda, atau bis flyggbussarna dari bandara Skavsta, maka Anda akan sampai di Central Stockholm yang merupakan gabungan dari terminal bis (Terminalen), stasiun kereta (Central Station), dan stasiun kereta bawah tanah (T-Centralen). Di Sergels Torg ini yang bisa dilihat antara lain tugu Sergels (bukan nama sebenarnya) dan gedung Kulturhuset yang berisi perpus, teater, cafe, dan miniatur Stockholm.

20140315_171447

20141026_163100

Suka dipakai sebagai tempat demo. Untung berjalan tertib dan tidak rusuh.

 

Pusat pertokoan dan perbelanjaan (H & M, Intersport, Clas Ohlsson) juga dapat dinikmati di sini.

2. Drottninggatan

Dari Sergels Torg, lanjutkan perjalanan menuju kota tua melalui jalan Drottninggatan (Jalan Ratu jika diterjemahkan). Oleh-oleh standar seperti helm Viking bertanduk (walau aslinya cuma mitos) dapat dibeli di sini.

DSC00722

3. Gamla Stan

Gamla Stan memiliki arti Kota Tua. Istana Raja (Royal Palace), gedung Parlemen Swedia (Riksdag), dan museum Nobel dapat dilihat di sini selain Anda menikmati jalan gang sempit di tengah bebatuan bangunan tua.

20140315_170121

 

20140315_170455

4. Stadhuset

Stadhuset, atau Stockholm Public Hall, adalah salah satu landmark andalan kota Stockholm. Tempat ini mungkin paling terkenal sebagai tempat pesta jamuan makan malam untuk pesta Nobel setiap tahunnya.

DSC01145

DSC01135

in the Golden Hall of Mountain King

 

6. Katarina Hissen

Kunjungi Katarina Hissen untuk mendapatkan pemandangan tertinggi di tengah kota Stockholm. Katarina Hissen, yang dialihbahasakan menjadi Lift Katarina, dapat dicapai di Slussen.

DSC00877r

 

DSC01643

Jangan lupa ketika di Stockholm untuk makan di restoran dengan cita rasa lokal, Max. Konon burger-nya paling enak se-Skandinavia. Selain murah dan enak, ada Wi-Fi gratis yang mungkin jarang bisa ditemui di tempat lain di Stockholm.

Selamat jalan-jalan. Salam.

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.

ICPR

International Conference on Pattern Recognition (ICPR) 2014 diadakan di Stockholm pada tanggal 24-28 Agustus silam. ICPR merupakan salah satu konferensi di bidang Pattern Recognition dan Machine Learning yang terbesar, selain Neural Information Processing Systems (NIPS) dan International Conference on Machine Learning (ICML) atau saudaranya di bidang Computer Vision seperti Computer Vision and Pattern Recognition (CVPR), International Conference on Computer Vision (ICCV), dan European Conference on Computer Vision (ECCV). Tempat penyelenggaraannya adalah di Waterfront Congress center yang terletak di jantung kota Stockholm

Pada tahun ini penyelenggaranya adalah Uppsala University, Lund University, dan Linkoping University. Kebetulan salah satu chair pada konferensi tersebut adalah professor dari KTH. Maka dibukalah penawaran relawan untuk membantu penyelenggaran konferensi ini kepada semua mahasiswa yang mengambil kelas Image Analysis and Computer Vision tahun 2013 lalu. Karena tertarik maka saya ikut mendaftar menjadi salah satu dari relawan.

Tugas dari relawan antara lain adalah: menjaga registration desk, menjadi guide selama acara konferensi berlangsung, menjaga ruang penitipan jaket (plus tas dan barang lain-lain) atau cloak room, membantu pada sesi presentasi dengan mendistribusikan mic untuk presenter dan pada saat sesi tanya jawab, dan membantu memasang serta melepas poster. Relawan tidak mendapatkan upah, namun memiliki keuntungan bisa mengikuti seluruh kegiatan konferensi, termasuk acara banquet yang konon biaya totalnya bisa mencapai lebih dari 10000 SEK.

conference gears

Conference gears, yang antara lain isinya buku program, name tag, tas, dan flash disk berisi proceeding. Kaus keren eksklusif hanya didapat oleh relawan.

Seperti konferensi pada umumnya, terdapat plenary speech dari invited speaker yang merupakan expert pada bidangnya. Terdapat juga oral session untuk sekitar 200an paper yang diterima dan 600an paper untuk poster session. Sayang sekali saya tidak menemukan orang Indonesia yang presentasi di sini.

20140828_143611

Professor Stan Z. Li dari National Laboratory of Pattern Recognition memberikan plenary speech pada hari terakhir mengenai perkembangan terkini dari face recognition.

poster session

Sesi poster

oral session

Sesi presentasi oral. Yang di kiri belum banyak orang karena belum mulai.

Ada satu poster menarik tentang iris spoofing yang menyebutkan Indonesia di bagian latar belakangnya. Saya ingat ketika mengambil data untuk eKTP salah satu yang diambil adalah iris, tapi belum tahu kalau ternyata teknologi iris recognition sudah dipakai.

indonesia poster

Pada hari ketiga malam harinya diadakan banquet atau gala dinner. Acara diisi dengan penyerahan penghargaan untuk Best Paper dari semua track, serta pengangkatan presiden baru untuk International Association of Pattern Recognition (IAPR).

banquette

Menu santap malam. Pembuka: Marinated Char, Utama: Crispy Duck Breast, Penutup: Chocolate and Truffle Cake. Makanannya enak walaupun daging bebeknya terlalu kenyal (kata saya).

Acara ditutup dengan hiburan dari grup musik asal Swedia, Timoteij.

20140827_225558

ICPR yang berikutnya akan diadakan tahun 2016 di Cancun, Mexico. Semoga dapat kesempatan lagi untuk mengikuti.

cancunn

Stand ICPR 2016 dan foto cakep Cancun dari atas tempat lokasi penyelenggaraan yang saya ambil dari 500px.com

Foto (yang ada sayanya aja)

2014-08-28 213531

Foto relawan bersama. Karena tidak semua relawan bisa bertugas setiap hari, maka yang difoto ini adalah yang kebetulan ada hari Rabu saja.

IMG_1009-m

Briefing satu hari sebelum penyelenggaraan.

2014-08-25 185450

Mengumpulkan tiket masuk untuk welcome reception di Stockholm city hall.

Galeri foto lainnya bisa dilihat di http://www.cb.uu.se/~kristina/ICPR/demo.php

Personnummer

Personnummer atau Personal Identification Number adalah nomor tunggal pengenal identitas diri yang dipakai di Swedia atau istilah kerennya Single Identity Number. Nomor ini dipakai untuk data kependudukan dan digunakan untuk berbagai keperluan seperti sekolah, bank, dan asuransi. Saya pernah diberi tahu kalau bedanya personnummer dengan nomor KTP di Indonesia adalah kalau personnummer kita pasti ingat nomornya sedangkan nomor KTP kita tidak pernah ingat. Ini bisa jadi indikasi bahwa personnummer itu tingkat ke-penting-an-nya sangat tinggi sehingga kita memang butuh mengingatnya karena penggunaannya yang masif, terstruktur, dan sistematis pada kehidupan sehari-hari. Atau memang karena nomornya lebih pendek dari nomor KTP.

Penjelasan lebih dalam dan teknis mengenai personnummer bisa dilihat pada presentasi di bawah.

Untuk kegunaan personnummer yang digunakan dalam riset bisa dilihat di slide presentasi di bawah.

Untuk mendaftar personnummer bagi kaum pendatang, kita harus datang ke kantor pajak atau skatteverket dengan membawa passport, residence permit, dan bukti tinggal di Swedia lebih dari 1 tahun (notification of selection untuk student). Nah, syarat terakhir ini yang membuat agak ‘tricky’ untuk mendapat personnummer. Salah satu kisah nyata perjuangan untuk mendapatkan personnummer bisa dibaca di sini: http://fajriahnur.wordpress.com/2014/05/18/cerita-daftar-personnummer/

skatteverket

Lokasi kantor skatteverket yang ada di sekitar Stockholm

Keuntungan memiliki personnummer cukup beragam, seperti (konon) biaya kesehatan yang jauh lebih murah. Yang ini saya belum bisa buktikan karena Alhamdulillah saya belum pernah ke dokter. Sekarang saya akan cerita tentang kegunaan personnummer yang pernah saya gunakan selain untuk buka akun bank.

1. Kartu SL

Transportasi dalam kota Stockholm yang terdiri dari bis, metro (tunnelbana), commuter rails (pendeltag), dan kapal, semuanya menggunakan kartu SL. Kartu SL ini bisa dibeli di minimarket seperti pressbyran atau SL center yang terdapat di beberapa stasiun tunnelbana dengan harga 20 SEK. Setelah dibeli, kartu SL bisa diisi dengan uang (reskasssa/travel fund) untuk melakukan pembayaran pada setiap kali perjalanan. Untuk perjalanan pada satu zona yang sama dikenakan biaya sebesar 2 kupon atau 25 SEK (1 kupon 12.5 SEK). Jika melewati zona yang berbeda maka biayanya 3 kupon dan jika dari zona A ke C atau sebaliknya dikenakan 4 kupon. Masuk ke daerah lain seperti Uppsala, dikenakan tiket tambahan lagi.

sl card

Kartu SL keren

Alternatif lain selain menggunakan travel fund adalah membeli periodbiljett atau season ticket (atau tiket abodemen kalau bahasa KRL jabodetabek jaman dulu). Tiket dimulai dari 115 SEK untuk 24 jam, 230 SEK untuk 72 jam, 300 SEK untuk 1 minggu, 790 SEK untuk 1 bulan, dan 2300 SEK untuk 3 bulan, Pelajar mendapat diskon untuk tiket 1 bulan menjadi hanya 560 SEK dan tiket 3 bulan menjadi 1540 SEK. Season ticket dan travel fund bisa diisi ditempat kartu tersebut dibeli atau di mesin tiket yang tersedia di semua stasiun tunnelbana.

ticket machine

Mesin untuk membeli tiket yang di-load ke dalam kartu SL. Pembayaran bisa menggunakan kartu dengan logo Visa atau Maestro.

zone map

Peta moda transportasi yang dibagi menjadi Zona A, B, dan C. Kalau menggunakan tiket bulanan sih tidak perlu pusing memikirkan apakah daerah tujuannya termasuk zona yang mana.

Nah, kalau misalkan kita sudah beli tiket SL kemudian diisi tiket untuk perjalanan selama 3 bulan. Kemudian kartu tersebut hilang setelah baru dipakai hanya 1 hari, wah kalau saya pasti nangis darah. Agar amannya, kartu SL bisa didaftarkan di website SL, tentunya dengan menggunakan personnummer.

Buka website sl.se kemudian pilih menu Mitt SL.

sl.se

Daftar akun baru dengan mengklik skapa konto kemudian mengisi data diri dengan benar (jangan lupa personnummer-nya).

create account

Setelah itu seharusnya ada email dari SL yang berisi kode aktivasi. Masukkan.

activate account

Setelah itu Anda bisa log-in dengan username dan password yang sudah diisi tadi.

login

Registrasi kartu Anda dengan memasukkan 10 digit kode angka yang ada di belakang kartu SL. Kasih nama juga yang bagus.

sl card back

register card

Kartu yang sudah didaftarkan akan terlihat di atas beserta isi tiket yang ada di dalamnya. Kita bisa mendaftarkan lebih dari satu kartu ke dalam sistem.

list card

Jika kartu Anda hilang, jangan panik. Klik kartu yang hilang tersebut di menu atas dan pilih Forlustanmal kort untuk memblok kartu yang hilang plus mengirimkan kartu baru ke alamat rumah kita. Loh, tahu dari mana dia alamat rumah kita? Tentunya dari nomor personnummer yang kita gunakan. Berdasarkan pengalaman saya pribadi, kartu baru sampai ke kediaman rumah dalam waktu 3 hari. Enak kan…

block card

2. Kartu Perpustakaan

Setelah kita memiliki personnummer, kita dapat membuat kartu perpustakaan secara gratis, tanpa biaya apapun, agar bisa meminjam pada lebih dari 40 perpustakaan yang tersebar di seluruh penjuru Stockholm. Jumlah buku yang bisa dipinjam dalam satu waktu adalah 50 buku. Lama waktu peminjaman adalah sekitar 4 minggu yang bisa diperpanjang sebanyak 2 kali (kecuali bukunya sudah direservasi orang lain), bisa menggunakan mesin yang sama untuk meminjam buku atau diperpanjang secara online. Buku yang sudah dipinjam dapat dikembalikan di perpus manapun yang Anda mau. Agar tidak repot mencari bukunya (kecuali Anda petualang yang senang menemukan buku-buku menarik tak terduga) di rak-rak yang jumlah banyak, Anda bisa melakukan reservasi buku secara online dengan biaya hanya 10 SEK.

Koleksi buku apa saja yang ada di perpus dapat dilihat di website https://biblioteket.stockholm.se/

biblioteket.se

Untuk mendapatkan kartu perpus, pertama kita harus registrasi secara online di https://biblioteket.stockholm.se/en/user/register

register library

Kemudian datangi perpus terdekat dan minta kartu Anda pada bagian informasi. Jika sudah maka Anda akan mendapat kartu perpus keren seperti ini. Gampang kan…

library card

Kartu perpus keren.

Ini contoh buku yang saat tulisan ini dibuat sedang dipinjam.

books

Dari kiri atas ke kanan bawah. I, Robot oleh Isaac Asimov; Flatland oleh Edwin Abbott; Time Machine oleh H.G. Wells; Black Jack oleh Osamu Tezuka; dan Time Out of Joint oleh Philip K. Dick

Semoga berguna. Salam.

Visualisasi dengan Processing

Pada post ini saya akan memperkenalkan processing. Processing adalah bahasa pemrograman yang digunakan untuk membuat visualisasi dalam bentuk gambar statis dan/atau animasi. Secara bahasa pemrograman, Processing memiliki sintaks yang mirip dengan Java.

logo

Instalasi

Masuk ke halaman Download di situs processing dan pilih file sesuai dengan sistem operasi yang Anda gunakan.

download

Ekstrak file zip ke direktori manapun yang dikehendaki.

Getting Started

Buka folder hasil ekstraksi dan jalankan processing.exe

processing

Gambar di atas adalah tampilan awal dari processing ketika baru dijalankan. Pada text editor, ketikkan kode berikut untuk menginisialisasi visualisasi baru lalu klik tombol Rum (yang gambar segitiga) atau lewat menu Sketch > Run atau dengan shortcut Ctrl+R.

void setup() {
  size(500, 400);
}

void draw() {
  background(0,0,255);
}

Seharusnya keluar window baru dengan warna latar belakang biru. Kode di atas merupakan kode paling dasar pada Processing. fungsi setup() dijalankan sekali pada waktu program mulai berjalan di awal sedangkan fungsi draw() dipanggil berulang kali dalam satu detik. Berapa kali fungsi draw() dipanggil bisa dikontrol dengan fungsi frameRate() di mana nilai standarnya adalah 60 fps.

Contoh: Bacteria random walk

Untuk contoh yang sedikit lebih rumit dibanding hanya background kosong, kita akan membuat animasi bakteri yang berjalan secara acak.
Pertama, kita buat kelas baru untuk menyimpan data posisi bakteri. Jangan lupa fungsi constructor untuk menginisialisasi posisi awal bakteri.

class Bactery {
  int x;
  int y;
  float angle;
  
  Bactery() {
    x = int(random(width));
    y = int(random(height));
    angle = 2*PI*random(1);
  }
  
  Bactery(int x, int y) {
    this.x = x;
    this.y = y;
    angle = 0;
  }
}

Kemudian kita tambahkan fungsi display() untuk menggambar bakteri, dimana kita sederhanakan bentuk bakteri menjadi sebuah segi empat.

void display() {
    stroke(0);
    fill(0);
    
    if(random(1) < 0.2)
      angle = 2*PI*random(1);
      
    int x1 = bactWidth;
    int y1 = 0;
    
    int x2 = bactWidth;
    int y2 = bactHeight;
    
    int x3 = 0;
    int y3 = bactHeight;
    
    // Apply the rotation
    int nx1 = int( x1*cos(angle) - y1*sin(angle) +x);
    int ny1 = int( x1*sin(angle) + y1*cos(angle) +y);
    
    int nx2 = int( x2*cos(angle) - y2*sin(angle) +x);
    int ny2 = int( x2*sin(angle) + y2*cos(angle) +y);
    
    int nx3 = int( x3*cos(angle) - y3*sin(angle) +x);
    int ny3 = int( x3*sin(angle) + y3*cos(angle) +y);
    
    quad(x, y, nx1, ny1, nx2, ny2, nx3, ny3);
  }

Tambahkan pula fungsi step() untuk meng-update posisi bakteri pada setiap frame.

void step() {
    int moveX = int(random(11)) - 5;
    int moveY = int(random(11)) - 5;
    
    x += moveX;
    y += moveY;
  }

Instansiasi objek bakteri di awal, kemudian kita panggil kedua fungsi diatas pada setiap frame.

void setup() {
  size(500, 400);
  
  bacteria = new Bactery[numBact];
  for(int i=0; i<numBact; i++) {
    bacteria[i] = new Bactery();
  }
}

void draw() {
  background(255,255,255);
  
  for(int i=0; i<numBact; i++) {
    bacteria[i].step();
    bacteria[i].display();
  }
}

Jangan lupa untuk menambahkan variabel-variabel global yang dipakai.

Bactery[] bacteria;
int numBact = 200;
int bactWidth = 2;
int bactHeight = 10;

Contoh tampilan ketika dijalankan: bakteri yang jumlahnya banyak menggeliat sepanjang waktu.

bakteri

Processing on the Web

dengan menggunakan processing.js, program processing Anda akan secara ajaib dan otomatis bisa ditampilkan pada halaman web dengan memanfaatkan teknologi HTML5. Cukup dengan membuat sebuah halaman html kosong, import processingjs, dan tambahkan canvas ke dalamnya.

<script src="https://raw.github.com/processing-js/processing-js/v1.4.8/processing.min.js"></script>
<canvas data-processing-sources="bacterium.pde"></canvas>

Karena wordpress.com tidak bisa pakai iframe, maka animasinya bisa dilihat pada link berikut: http://mitbal.com/bacterium.html

Seperti biasa kode lengkap bisa dilihat di repository github: https://github.com/mitbal/pro-bacterium

Demikian, semoga berguna. Sampai ketemu pada contoh-contoh visualisasi lainnya.
Salam.

Baseline Wander Removal dengan Wavelet

Pada post kali ini, kita akan melakukan proses menghilangkan baseline wander (baseline wander removal) pada sinyal EKG dengan menggunakan transformasi wavelet seperti yang ditulis oleh Sargolzaei et al pada paper dengan judul “A new robust wavelet based algorithm for baseline wandering cancellation in ECG signals“.

Latar belakang
Elektrokardiogram (EKG) adalah pembacaan sinyal elektrik jantung dengan cara menempelkan elektroda ke posisi tertentu pada tubuh dan kemudian membaca nilai perbedaan potensial listrik alias tegangan yang dihasilkan. Dari pembacaan ini kita bisa mencari tahu mengenai kondisi jantung. Akan tetapi, sinyal yang baru dibaca ini tidak lepas dari noise sehingga bisa mengganggu proses diagnosis. Sumber noise ini berasal dari berbagai macam, seperti elektroda dari elektroda itu sendiri atau jika tubuh bergerak ketika dilakukan pengukuran. Salah satu kondisi noise yang sering menyerang adalah situasi yang disebut baseline wander. Baseline wander terjadi apabila sinyal EKG tidak lurus pada sumbu x, malah naik turun. Contoh bisa dilihat di gambar 1.

bwr

Contoh sinyal yang terkena baseline wander dan hasilnya setelah dihilangkan. Gambar diambil tanpa izin dari paper yang dirujuk di atas.

Baseline wander removal (BWR) adalah salah satu tahap preprocessing pada sinyal EKG untuk menghilangkan baseline drift ini. Ada beberapa teknik yang bisa dipakai, seperti melakukan filtering. Pada post ini, kita akan mengimplementasikan salah satu teknik yang memanfaatkan transformasi wavelet. Penjelasan dasar mengenai wavelet salah satunya bisa dilihat di http://users.rowan.edu/~polikar/WAVELETS/WTtutorial.html. Kelebihan dari teknik ini adalah kita tidak perlu menentukan parameter seperti ketika menggunakan high pass filter (frequency cut-off) sehingga metode kita bekerja secara non-supervised.

Sinyal EKG yang sudah bersih dari noise semacam ini kemudian bisa digunakan untuk berbagai macam kegunaan. Untuk pembahasan mengenai kegunaan sinyal EKG untuk mengenali tipe detak arrhythmia atau diagnosis tahapan tidur, bisa merujuk ke paper ini dan ini.

Algoritma
Berikut adalah tahapan dalam algoritma ini. Pertama, kita lakukan dekomposisi kepada sinyal asli dengan transformasi wavelet. Dalam hal ini kita memilih Daubechies orde 4 sebagai fungsi basisnya. Sinyal didekomposisi menjadi bagian frekuensi rendah/aproksimasi dan frekuensi tinggi/detail. Kemudian kita hitung nilai energi pada sinyal frekuensi tinggi. Kita cari kondisi dimana nilai energi pada level dekomposisi tersebut lebih rendah dari pada nilai pada level dekomposisi sebelumnya dan sesudahnya (alias lokal minima). Setelah kita temukan level tersebut, kita rekonstruksi sinyal aproksimasi dari level ini dengan membuang nilai pada sinyal frekuensi tinggi (atau dijadikan 0 semua). Sinyal hasil rekonstruksi ini kita sebut dengan baseline. Untuk menghilangkan baseline wander pada sinyal asli, maka kita kurangkan sinyal asli dengan sinyal baseline.

level

Gambar atas: plot nilai energi pada sinyal detail pada berbagai level dekomposisi. Tanda panah menunjukkan level ketika nilainya adalah lokal minima. Gambar bawah: Sinyal asli, baseline, dan sinyal asli yang sudah dikurang baseline. Lagi-lagi diambil dari paper rujukan di atas.

 

Implementasi
Pertama, kita implementasi metode konvolusi antara dua sinyal.

def conv(x, h):
    """ Perform the convolution operation between two input signals. The output signal length
    is the sum of the lenght of both input signal minus 1."""
    length = len(x) + len(h) - 1
    y = [0]*length

    for i in xrange(len(y)):
        for j in xrange(len(h)):
            if i-j >= 0 and i-j < len(x):
                y[i] += h[j] * x[i-j]

    return y

Lalu kita implementasi metode dekomposisi wavelet dan jangan lupa deklarasi koefisien basis fungsi yang dipakai. Dalam kasus ini adalah Daubechies dengan 4 koefisien. Dekomposisi dilakukan dengan cara mengkonvolusi sinyal asli dengan koefisien low pass and high pass. Sinyal keluaran dari proses ini kemudian di-downsampling menjadi setengahnya dengan cara hanya mengambil nilai pada posisi ganjil atau genap saja. Hal ini dilakukan berulang terhadap sinyal keluaran low pass (atau disebut aproksimasi) sebanyak parameter level.

c0 = (1+sqrt(3))/(4*sqrt(2))
c1 = (3+sqrt(3))/(4*sqrt(2))
c2 = (3-sqrt(3))/(4*sqrt(2))
c3 = (1-sqrt(3))/(4*sqrt(2))

def db4_dec(x, level):
""" Perform the wavelet decomposition to signal x with Daubechies order 4 basis function as many as specified level"""

    # Decomposition coefficient for low pass and high pass
    lpk = [c0, c1, c2, c3]
    hpk = [c3, -c2, c1, -c0]

    result = [[]]*(level+1)
    x_temp = x[:]
    for i in xrange(level):
        lp = conv(x_temp, lpk)
        hp = conv(x_temp, hpk)

        # Downsample both output by half
        lp_ds=[0]*(len(lp)/2)
        hp_ds=[0]*(len(hp)/2)
        for j in xrange(len(lp_ds)):
            lp_ds[j] = lp[2*j+1]
            hp_ds[j] = hp[2*j+1]

        result[level-i] = hp_ds
        x_temp = lp_ds[:]

    result[0] = lp_ds
    return result

Fungsi rekontruksi digunakan untuk mencari baseline dari sinyal asal. Rekonstruksi bekerja dengan melakukan konvolusi dengan koefisien rekonstruksi pada kedua sinyal low pass dan high pass, melakukan upsampling dengan menyelipkan 0 di setiap nilai pada sinyal dan kemudian masing-masing posisi pada sinyal saling dijumlahkan.

def db4_rec(signals, level):
    """ Perform reconstruction from a set of decomposed low pass and high pass signals as deep as specified level"""

    # Reconstruction coefficient
    lpk = [c3, c2, c1, c0]
    hpk = [-c0, c1, -c2, c3]

    cp_sig = signals[:]
    for i in xrange(level):
        lp = cp_sig[0]
        hp = cp_sig[1]

        # Verify new length
        length = 0
        if len(lp) > len(hp):
            length = 2*len(hp)
        else:
            length = 2*len(lp)

        # Upsampling by 2
        lpu = [0]*(length+1)
        hpu = [0]*(length+1)
        index = 0
        for j in xrange(length+1):
            if j%2 != 0:
                lpu[j] = lp[index]
                hpu[j] = hp[index]
                index += 1

        # Convolve with reconstruction coefficient
        lpc = conv(lpu, lpk)
        hpc = conv(hpu, hpk)

        # Truncate the convolved output by the length of filter kernel minus 1 at both end of the signal
        lpt = lpc[3:-3]
        hpt = hpc[3:-3]

        # Add both signals
        org = [0]*len(lpt)
        for j in xrange(len(org)):
            org[j] = lpt[j] + hpt[j]

        if len(cp_sig) > 2:
            cp_sig = [org]+cp_sig[2:]
        else:
            cp_sig = [org]

    return cp_sig[0]

Method calcEnergy menghitung nilai energi dari sebuah sinyal berdasarkan definisinya yaitu jumlahan kuadrat sinyal di tiap titik

def calcEnergy(x):
    """ Calculate the energy of a signal which is the sum of square of each points in the signal."""
    total = 0
    for i in x:
        total += i*i
    return total

Kemudian method bwr berikut adalah implementasi dari algoritma yang dijabarkan di atas.

def bwr(raw):
    """ Perform the baseline wander removal process against signal raw. The output of this method is signal with correct baseline
    and its baseline """
    en0 = 0
    en1 = 0
    en2 = 0
    n = 0

    curlp = raw[:]
    num_dec = 0
    last_lp = []
    while True:
        print 'Iterasi ke' + str(num_dec+1)
        print len(curlp)

        # Decompose 1 level
        [lp, hp] = db4_dec(curlp,1)

        # Shift and calculate the energy of detail/high pass coefficient
        en0 = en1
        en1 = en2
        en2 = calcEnergy(hp)
        print en2

        # Check if we are in the local minimum of energy function of high-pass signal
        if en0 > en1 and en1 < en2:
            last_lp = curlp
            break

        curlp = lp[:]
        num_dec = num_dec+1

    # Reconstruct the baseline from this level low pass signal up to the original length
    base = last_lp[:]
    for i in xrange(num_dec):
        base = db4_rec([base,[0]*len(base)], 1)

    # Correct the original signal by subtract it with its baseline
    ecg_out = [0]*len(raw)
    for i in xrange(len(raw)):
        ecg_out[i] =  raw[i] - base[i]

    return (base, ecg_out)

Contoh
Untuk contoh kita ambil data dari situs Physionet khususnya MIT-BIH Arrhythmia database. Data diambil dari salah satu record pasien dengan kode nomor 101. Sinyal EKG diambil sepanjang 1 menit. Sinyal EKG yang diambil berasal dari lead II dan V5.

Contoh kode untuk memanggil modul dan fungsi yang sudah dibuat di atas adalah sebagai berikut

import bwr
import matplotlib.pyplot as plt

# Read input csv file from physionet
f = open('samples1.csv', 'r')
lines = f.readlines()
f.close()

# Discard the first two lines because of header. Takes either column 1 or 2 from each lines (different signal lead)
signal = [0]*(len(lines)-2)
for i in xrange(len(signal)):
	signal[i] = float(lines[i+2].split(',')[1])

# Call the BWR method
(baseline, ecg_out) = bwr.bwr(signal)

plt.subplot(2,1,1)
plt.plot(signal, 'b-')
plt.plot(baseline, 'r-')

plt.subplot(2,1,2)
plt.plot(ecg_out, 'b-')
plt.show()

Berikut contoh pertama. Garis merah pada plot merupakan baseline dari sinyal EKG.

samples1

Berikut adalah contoh kedua.

samples2

Contoh berikut diambil dari lead V5.

samples3

Kode lengkap dan sampel sinyal dapat dilihat di: https://github.com/mitbal/py-bwr

Semoga berguna. Salam.

UPGMA

Pada post kali ini kita akan mengimplementasi algoritma UPGMA atau Unweighted Pair Group Method with Arithmetic Mean untuk melakukan clustering.

Algoritma
UPGMA bekerja dengan prinsip yang sederhana. Pada setiap iterasi, pilih pasangan point dengan point, atau point dengan cluster, atau cluster dengan cluster, yang memiliki jarak yang terpendek. Gabung kedua pasangan ini kedalam satu cluster. Hal ini dilakukan terus menerus hingga jumlah cluster berkurang menjadi jumlah yang diinginkan. Untuk menghitung jarak antar datapoint, kita bisa menggunakan berbagai kriteria jarak. Pada implementasi ini, kita menggunakan euclidean distance untuk menghitung jarak. Sedangkan untuk menghitung jarak antar cluster, kita hitung dengan cara merata-ratakan jarak antar semua pasang point dari cluster pertama ke cluster kedua, atau dengan kata lain:

\frac{1}{|A|.|B|} \sum_{x \in A} \sum_{y \in B} d(x,y)

Teknik UPGMA ini bisa digolongkan kepada teknik hierarchical clustering karena kita bisa melihat hirarki sebuah cluster yang dibentuk dari cluster-cluster lain yang lebih kecil.

Implementasi
Kita implementasikan UPGMA dalam bahasa Python. Pertama, kita butuh struktur data untuk menyimpan point yang terdapat pada sebuah cluster.

class Node:
    def __init__(self, p):
        self.points = p
        self.right = None
        self.left = None

Fungsi UPGMA menerima dua parameter. Parameter pertama adalah set yang berisi datapoints sebanyak n dengan masing-masing point memiliki dimensi d. Parameter kedua adalah jumlah cluster yang kita inginkan.

def upgma(points, k):
    """ Cluster based on distance matrix dist using Unweighted Pair Group Method with Arithmetic Mean algorithm up to k cluster"""

    # Initialize each cluster with one point
    nodes = []
    n = len(points)
    for i in xrange(n):
        node = Node([points[i]])
        nodes = nodes + [node]

    # Iterate until the number of clusters is k
    nc = n
    while nc > k:
        # Calculate the pairwise distance of each cluster, while searching for pair with least distance
        c1 = 0; c2 = 0; i1 = 0; i2 = 0;
        sdis = 9999999999
        for i in xrange(nc):
            for j in xrange(i+1, nc):
                dis = euclidistance(nodes[i], nodes[j])
                if dis < sdis:
                    sdis = dis
                    c1 = nodes[i]; c2 = nodes[j];
                    i1 = i; i2 = j;
        # Merge these two nodes into one new node
        node = Node(c1.points + c2.points)
        node.left = c1; node.right = c2;
        
        #Remove the previous nodes, and add the new node
        new_nodes = []
        for i in xrange(nc):
            if i != i1 and i != i2:
                new_nodes = new_nodes + [nodes[i]]
        new_nodes = new_nodes + [node]
        nodes = new_nodes[:]
        nc = nc - 1

    return nodes

Kemudian terakhir, kita definisikan fungsi jarak yang kita pakai. Selain jarak euclidean, kita bisa yang digunakan kriteria jarak lainnya seperti Manhattan distance atau Chebyshev distance.

import math

def euclidistance(c1, c2):
    """ Calculate the distance between two cluster """
    dist = .0
    n1 = len(c1.points)
    n2 = len(c2.points)
    for i in xrange(n1):
        for j in xrange(n2):
            p1 = c1.points[i]
            p2 = c2.points[j]
            dim = len(p1)
            d = 0
            for k in xrange(dim):
                d = d + (p1[k]-p2[k])**2
            d = math.sqrt(d)
            dist = dist + d
    dist = dist / (n1*n2)
    return dist

Contoh
Untuk contoh pertama kita pakai dataset sintesis yang dihasilkan oleh dua buah distribusi normal multidimensi.

import upgma
import random
import matplotlib.pyplot as plt
import math

# Example 1
datapoints = [(random.normalvariate(2.5, 1.0), random.normalvariate(1.5,1.0)) for i in xrange(100)] + \
				[(random.normalvariate(-1, 0.5), random.normalvariate(3,0.5)) for i in xrange(100)]

# Plot datapoints before clustering
plt.plot([x for (x,y) in datapoints], [y for (x,y) in datapoints], 'k^')
plt.show()

# Cluster the data
nodes = upgma.upgma(datapoints, 2)
plt.plot([x[0] for x in nodes[0].points], [x[1] for x in nodes[0].points], 'b*')
plt.plot([x[0] for x in nodes[1].points], [x[1] for x in nodes[1].points], 'ro')
plt.show()

dan berikut keluaran hasil clustering jika kita pilih 2 sebagai jumlah cluster.
nocluster1cluster1

Contoh kedua kita ambil dataset old faithful geyser (http://www.stat.cmu.edu/~larry/all-of-statistics/=data/faithful.dat).

f = open('faithful.dat.txt', 'r')
lines = f.readlines()
f.close()

datapoints = []
for line in lines:
	tokens = line.split()
	datapoints += [(float(tokens[1]), float(tokens[2]))]

Karena fitur kedua berbeda skalanya dengan fitur pertama (puluhan berbanding dengan satuan), kita lakukan normalisasi z-score pada tiap masing-masing fitur dengan cara mengurangi dengan mean distribusi dan kemudian dibagi dengan standar deviasi.

avg1 = sum([x for (x,y) in datapoints])
avg2 = sum([y for (x,y) in datapoints])
centered_datapoints = map(lambda (x,y): (x-avg1, y-avg2), datapoints)
std1 = math.sqrt(sum(map(lambda x: x*x, [x for (x,y) in centered_datapoints])))
std2 = math.sqrt(sum(map(lambda x: x*x, [y for (x,y) in centered_datapoints])))
normalized_datapoints = map(lambda (x,y): (x/std1, y/std2), centered_datapoints)

Hasil clustering-nya adalah sebagai berikut.

# Before clustering
plt.plot([x for (x,y) in normalized_datapoints], [y for (x,y) in normalized_datapoints], 'k^')
plt.show()

# Cluster the data
nodes = upgma.upgma(normalized_datapoints, 2)
plt.plot([x[0] for x in nodes[0].points], [x[1] for x in nodes[0].points], 'b*')
plt.plot([x[0] for x in nodes[1].points], [x[1] for x in nodes[1].points], 'ro')
plt.show()

nocluster2cluster2

Kode lengkap dapat dilihat di: https://github.com/mitbal/py-upgma

Semoga berguna. Salam.