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.

My K-Means Clustering Page

I have started a page for k-means clustering algorithm and its variances. Hope it is of any use.

My Mixture Modelling Page

Yudi Agusta’s mixture modelling page has been just started. Hope this of any use.

Akurasi Hasil Pemodelan K-Means

Ada yang menanyakan tentang bagaimana mengetahui apakah model clustering yang didapatkan dengan k-means sudah cukup akurat atau tidak?

Memang sedikit susah kalau kita ingin menilai tingkat akurasi pemodelan clustering yang kita dapatkan kalau kita menggunakan metode k-means. Ada suatu pendekatan yang sering dipasangkan dengan k-means dalam pemodelannya yaitu Partition Entroy (PE). Tetapi saya selalu mendapat hasil yang mengecewakan pada saat menggunakan metode ini.

Sebagai alternatif, mungkin anda bisa menggunakan suatu trik yang menurut saya lebih aplikatif dan rasional berikut ini:

• Pertama, pilah data yang dimiliki menjadi dua set data yang mungkin ukuran tertentu, mungkin sekitar 80%:20%. Yang 80% dipakai sebagai training data, data yang digunakan untuk memodel. Sedangkan yang 20% digunakan sebagai validation data. Gunakan metode random dalam memilah data tersebut.
• Selanjutnya lakukan pemodelan menggunakan k-means terhadap training data. Catat persentase data yang menjadi bagian masing-masing cluster dan cluster center dari masing-masing cluster.
• Kemudian, model validation data dengan k-means. Bandingkan persentase data yang menjadi bagian dari masing-masing cluster yang terbentuk dengan persentase yang didapat dengan memodel training data. Bandingkan pula cluster center dari kelompok yang dihasilkan dalam pemodelan validation data dan pemodelan training data. Metode membandingkan bisa saja dengan melihat jarak cluster center dan perbedaan persentase antara kedua model yang didapat. Tentu saja cluster mana yang cocok dengan cluster mana harus dicari suatu trik sehingga jarak terdekat ‘dan’ perbedaan persentase terkecillah yang menjadi hasil perbandingan.
• Model yang mempunyai perbedaan antara training data dan validation data terkecil yang dipilih sebagai model yang paling tepat. Contohnya, apabila model k-means dengan dua kelompok lebih bagus daripada dengan tiga kelompok, maka model dengan dua kelompok itulah yang paling akurat.

Untuk menambah akurasi, proses tahap 1 sampai 3 mungkin bisa dilakukan berulang beberapa kali (misalnya 10 kali), dan perbedaan antara hasil pemodelan training data dan test data pada tahap 4 dicari dengan nilai rata-rata perbedaan setiap pemodelan yang dilakukan.

Mudah-mudahan membantu.