Clustering Untuk Categorical Data

Dalam sebuah diskusi di suatu milis, ada yang menanyakan tentang metode untuk melakukan clustering terhadap categorical data. Dari beberapa masukan yang ada, ada beberapa metode yang bisa digunakan untuk melakukan clustering jenis ini, termasuk di antaranya metode K-Modes clustering yang algoritmanya mirip dengan k-means (penjelasan tentang k-modes ada di dalam k-means page ini), ada yang mengusulkan tree models (CART) yang dapat didownload free, ada yang mengusulkan sebuah paket program yang disebut Party, Algoritma TWOSTEP, PREFSCAL dari SPSS yang dokumentasinya ada di sini, dan Latent Class Analysis.

Penanya awal dari diskusi ini ingin menggunakan K-Modes untuk melakukan analisa, tetapi dari diskusi yang muncul, ternyata banyak juga algoritma yang bisa digunakan untuk ini. Dan dari beberapa sumber di internet, ternyata K-Modes banyak mempunyai kelemahan. Beberapa kelemahan k-modes antara lain hasil clustering yang berbeda-beda tergantung pada proses initialisasi, dan juga error rate yang tinggi. Mungkin ada satu lagi metode yang secara prinsip sama dengan algoritma yang diusulkan terakhir (Latent Class Analysis) yang bisa digunakan untuk clustering jenis ini. Metode tersebut adalah Mixture Modelling. Metode ini merepresentasikan data categorical menjadi suatu bentuk distribusi Binomial atau Multinomial sebagai pengganti distribusi continuous seperti Gaussian. Penjelasan tentang mixture model dapat dilihat di My Mixture Model Page untuk lebih jelasnya.

Similarity Measure

Dalam melakukan pattern matching ataupun untuk melakukan berbagai jenis pengklasifikasian, similarity measure merupakan bagian penting yang harus diperhatikan. Ada beberapa jenis similarity measure yang bisa digunakan termasuk di antaranya:

Distance-Based Similarity Measure

Distance-Based Similarity Measure mengukur tingkat kesamaan dua buah objek dari segi jarak geometris dari variabel-variabel yang tercakup di dalam kedua objek tersebut. Yang termasuk sebagai distance-based similarity measure antara lain:

• Manhattan Distance (L1 Norm) : mengukur jarak dua buah objek dengan rumus sebagai berikut:

  d_L1 (x1, x2) = SUM (i=0 to n) |x1i - x2i|

• Euclidean Distance (L2 Norm) : menguruk jarak dua buah objek dengan rumus sebagai berikut:

  d_L2 (x1, x2) = SQRT ( SUM (i=0 to n) (x1i - x2i)^2 )

• Minkowski Distance (Lp Norm) : menguruk jarak dua buah objek dengan rumus sebagai berikut:

  d_Lp (x1, x2) = ROOT_p ( SUM (i=0 to n) (x1i - x2i)^p )

• Chebyshev Distance (Chessboard Distance, L_Infinity Norm) : menguruk jarak dua buah objek dengan rumus sebagai berikut:

  d_Chebyshev (x1, x2) = max_i {x1i - x2i}

• Mahalanobis Distance : mengukur jarak dua buah objek seperti L2 Norm dengan memikirkan korelasi antar objek dalam bentuk vector variabel dari objek dan matrik covariance dari kedua objek tersebut dengan rumus sebagai berikut:

  d_Mahalanobis (x1, x2) = SQRT ((x1 - x2)^T COV^(-1) (x1 - x2))

  Apabila matrik covariance adalah matrik identity maka Mahalanobis distance adalah Euclidean distance, dan apabila matrik covariance adalah matrik diagonal maka Mahalanobis distance adalah Normalised Euclidean distance dimana korelasi antara objek dianggap tidak ada. Dalam hal ini Mahalanobis distance dihitung dengan rumus sebagai berikut:

  d_Mahalanobis (x1, x2) = SQRT ( SUM (i=0 to n) (x1i - x2i)^2/SIGMA_i^2)

• Hamming Distance : mengukur jarak antara dua string yang ukurannya sama dengan membandingkan simbol-simbol yang terdapat pada kedua string pada posisi yang sama. Hamming distance dari dua string adalah jumlah simbol dari kedua string yang berbeda. Sebagai contoh Hamming distance antara string ‘toned’ dan ‘roses’ adalah 3.
• Levenshtein Distance : mengukur jarak antara dua string yang ukurannya tidak sama dengan menghitung jumlah pengoperasian yang perlu dilakukan untuk mengubah string yang satu menjadi string yang kedua yang diperbandingkan. Pengoperasian yang dilakukan termasuk operasi insert, delete dan substitusi. Sebagai contoh Levenshtein distance antara string ‘kitten’ dan ’sitting’ adalah 3 dengan pengoperasian substitusi k dengan s, substitusi e dengan i, dan insert g.
• Hausdorff Distance : mengukur jarak berbasis nilai infimum/greatest lower bound dan supremum/greatest upper bound dari kedua objek, dimana semua variabel dari kedua objek tersebut mempunyai nilai compact/closed. Hausdorff distance dihitung dengan rumus sebagai berikut:

  d_Hausdorff (x1, x2) = max {sup (x1i in x1) inf (x2i in x2) d_L2 (x1i, x2i), sup (x2i in x2) inf (x1i in x1) d_L2 (x1i, x2i)}

Probabilistic-Based Similarity Measure

Probabilistic-Based Similarity Measure menghitung tingkat kemiripan dua objek dengan merepresentasikan dua set objek yang diperbandingkan tersebut dalam bentuk probability. Beberapa metode probabilistic-based similarity measure termasuk:

• Kullback Leibler Distance : mengukur tingkat kemiripan variabel objek yang direpresentasikan dalam bentuk probabilita dua distribusi statistik. Sering disebut juga information distance, information gain, atau relative entropy. Jarak antara dua objek yang bernilai diskrit dalam Kullback Leibler distance dihitung dengan rumus sebagai berikut:

  D_KL (P,Q) = SUM (i) P(i) log (P(i)/Q(i))

  Sedang untuk objek yang bernilai continuous dihitung dengan rumus sebagai berikut:

  D_KL (P,Q) = INTEGRAL (i) P(i) log (P(i)/Q(i))

• Posterior Probability : mengukur tingkat kemiripan dengan mempertimbangkan nilai posterior probability terhadap nilai perbedaan variabel dari kedua objek yang diperbandingkan. Untuk menentukan posterior probability dari perbedaan variabel tersebut diperlukan data nilai-nilai perbedaan yang independent sebagai bahan training untuk pembentukan fungsi likelihood dari perbedaan-perbedaan tersebut.

Set-Based Similarity Measure

Jaccard Index adalah indeks yang menunjukkan tingkat kesamaan antara suatu himpunan (set) data dengan himpunan (set) data yang lain. Jaccard Index dihitung menggunakan rumus sebagai berikut:

J(A,B) = (A INTERSECT B)/(A UNION B)

Sebagai kebalikannya, tingkat ketidak samaan antara dua himpunan dihitung dengan:

J_delta(A,B) = ((A UNION B) - (A INTERSECT B))/(A UNION B)

Feature-Based Similarity Measure

Feature-based similarity measure melakukan penghitungan tingkat kemiripan dengan merepresentasikan objek ke dalam bentuk feature-feature yang ingin diperbandingkan. Feature-based similarity measure banyak digunakan dalam melakukan pengklasifikasian atau pattern maching untuk gambar dan text.

Context-Based Similarity Measure

Context-based similarity measure melakukan penghitungan tingkat kemiripan objek-objek yang mempunyai struktur yang tidak biasa seperti objek yang harus direpresentasikan dengan tree structure atau struktur yang lainnya.

Lake Beratan and Kebun Raya

Petunjuk menuju daerah Bedugul ada di bagian bawah tulisan ini.

Beberapa waktu lalu, kami bertamasya ke Danau Beratan dan Kebun Raya yang ada di dekatnya. Berikut ini sedikit cerita dan beberapa gambar yang kami sempat ambil di sana.

Danau Beratan adalah merupakan salah satu dari tiga danau yang terletak di daerah Bedugul, suatu daerah yang membatasi dua kabupaten yaitu Kabupaten Tabanan di selatan dan Kabupaten Buleleng di utara. Bedugul sendiri merupakan daerah pegunungan yang sangat sejuk dan biasanya didatangi oleh para pengunjung yang ingin mendapatkan suasana lain dari biasanya yang lebih sejuk dan pemandangan fresh yang hijau. Bedugul sendiri identik dengan pegunungan, bunga, dan buah-buahan. Mungkin karena sejuknya tersebut, bunga dan buah-buahan begitu mudah untuk ditemukan di sana.

Di samping mengunjungi Danau Beratan ada suatu tempat yang sangat nyaman untuk dikunjungi untuk sekedar duduk-duduk sambil memakan makanan ringan maupun makan siang. Tempat tersebut disebut dengan Kebun Raya Bedugul. Banyak pepohonan yang bisa ditemukan di sana dan banyak lapangan luas yang terbentang yang mengijinkan anak-anak untuk berlari-lari dan bagi orang tua untuk bersantai duduk sambil melihat pemandangan. Salah satu bagian yang menjadi tempat favorit kami kalau berkunjung ke sana adalah suatu lapangan rumput yang cukup luas yang letaknya agak ke dalam di dalam kebun raya tersebut. Lapangan tersebut menghadap ke Danau Beratan di bagian bawahnya. Kami sering duduk di sana untuk bersantai sambil menyantap snack atau makan siang dan mendengarkan lagu-lagi dari radio yang sengaja kami bawa.

Danau Beratan sendiri sangat terkenal dengan suatu pura yang disebut dengan Pura Ulun Danu Danau Beratan. Gambar Pura Ulun Danu ini banyak dan sering sekali terpampang di beberapa brosur yang mempromosikan pariwisata Pulau Bali. Keunikan dari pura ini adalah letaknya yang ada sedikit di tengah danau. Pada saat air danau tinggi, kita bahkan tidak bisa melihat jalan atau daratan yang menghubungkan pura tersebut dengan tepi danau. Dari pura tersebut kita juga dapat menyewa perahu kecil untuk bisa berkeliling di tengah danau. Saat kami berkunjung mendung atau mungkin kabut lumayan pekat, sehingga kami memutuskan hanya duduk-duduk saja menikmati pemandangan danau. Saat itu, Nicolas, salah satu internship asal Perancis yang sedang melakukan magang di Bali di bawah bimbingan saya, juga ikut bertamasya. Di sana, saya sempat mengabadikan Nicolas di depan Pura Ulun Danu tersebut sebagai kenangan.

Direction: Untuk mencapai daerah Bedugul, kalau anda berangkat dari arah Denpasar, anda perlu untuk menuju ke arah Terminal Bis Ubung terlebih dahulu. Dari sana, anda terus menyusuri jalan utama menuju arah utara, dan sampai di pertigaan Bringkit, anda berbelok ke kanan. Dari pertigaan tersebut, anda hanya perlu menyusuri jalan utama, sekitar 20-25 km dan anda akan sampai di Danau Beratan tersebut. Pintu masuk ke Kebun Raya Bedugul ada sebelum Danau Beratan. Letak absolut daerah Bedugul dapat dilihat dengan membuka peta Pulau Bali melalui thumbnail peta di samping. Letak daerah tersebut tersebut ditandai dengan angka nomor [4].

Expectation Maximisation Algorithm

Expectation Maximisation Algorithm (EM Algorithm) adalah algoritma yang sering digunakan untuk menemukan nilai estimasi Maximum Likelihood (ML) dari parameter dalam sebuah model probabilistic, dimana model juga tergantung pada latent variabel yang belum diketahui. Dalam algoritma ini, ada dua hal yang dilakukan secara bergantian yaitu E step yang menghitung nilai ekspektasi dari likelihood termasuk laten variabel seolah-olah seperti mereka ada, dan M step menghitung nilai estimasi ML dari parameter dengan memaksimalkan nilai ekspektasi dari likelihood yang ditemukan pada E step.

Latent variabel adalah variabel yang tidak terobservasi, yang dapat juga disamakan dengan missing data, missing measurements, dan hidden variabel. Dalam kasus mixture model, latent variabel juga mengacu pada jumlah komponen dari suatu mixture model.

Kalau y dianggap incomplete data dan terdiri dari nilai variabel yang sudah terobservasi dan z adalah missing data, maka y dan z akan membentuk complete data. Kalau p(y,z|theta) adalah joint probability density (mass) function, maka p(y,z|theta) bisa dianggap sebagai likelihood dari suatu complete data. Mengikuti teori Bayesian, selanjutnya conditional distribution dari missing data dengan berbasis pada data yang sudah terobservasi dapat diekspresikan sebagai:

p(z|y,theta) = p(y,z|theta)/p(y|theta)
= p(y|z,theta)*p(z|theta)/(INT p(y|z_est,theta)*p(z_est|theta)dz_est

Selanjutnya, EM algorithm secara iterative memperbaiki nilai estimasi dengan mengikuti proses estimasi seperti di bawah ini:

theta_(n+1) = arg max_theta Q(theta)

dimana Q(theta) = SUM(z) p(z|y,theta_n) log p(y,z|theta) atau dengan bentuk yang lebih umum Q(theta) = E_z[log p(y,z|theta)|y] merupakan nilai ekspektasi dari likelihood yang berbasis pada variabel yang sudah diobservasi (yang juga tergantung pada nilai estimasi sebelumnya).

Di sini, log likelihood digunakan sebagai ganti likelihood karena akan mempermudah formula. Perubahan ini tetap akan menghasilkan suatu nilai maksimum pada suatu bagian dari likelihood. Yang perlu diperhatikan di sini adalah nilai z tergantung pada nilai theta_n bukan theta_(n+1).

Berdasarkan pada persamaan di atas, nilai estimasi yang baru, theta_(n+1), akan didapatkan dengan mencari nilai estimasi yang memaksimalkan (M Step) nilai conditional expectation (E Step) dari log likelihood dari complete data yang berbasis pada variabel yang sudah terobservasi dan nilai paremeter terdahulu.

Sebagai catatan, bentuk continuous dari expectation Q(theta) adalah :

Q(theta) = INT(-infty to infty) p(z|y,theta_n) log p(y,z|theta) dz

Referensi:
Dempster A., Laird N., and Rubin D. (1977). Maximum Likelihood From Incomplete Data Via the EM Algorithm. Journal of the Royal Statistical Society, Series B, 39(1): 1-38.

Sensor Pendeteksi Uang

Beberapa bulan ini saya membiasakan diri untuk menyimpan uang di beberapa bagian dari dompet saya, sebagai tempat persembunyian. Karena kadang-kadang uang yang saya simpan di dompet tiba-tiba sudah habis, padahal ada waktunya saya harus mengeluarkan uang untuk membayar barang yang sudah terlanjur saya beli. Kebiasaan saya ini mulai diketahui istri saya. Dan sekarang ini, kalau di bagian penyimpan uang utama di dompet saya tidak ada uangnya, dia pasti mencari di bagian lain, untuk memastikan apakah ada uang yang tersembunyi di tempat lain. Makin hari kelihatannya ‘Sensor Pendeteksi Keberadaan Uang’ ini semakin intens saja. Karena beberapa kali uang cadangan yang saya simpan, sudah tidak ada pada tempatnya lagi. Mungkin suatu titik nanti saya akan menghentikan kebiasaan saya ini, karena fungsi utama menyimpan uang cadangan ini sudah tidak ada lagi .