Distance-Based Similarity Measure

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. Hamming Distance juga digunakan untuk mengukur jarak antar dua string binary misalnya jarak antara 10011101 dengan 10001001 adalah 2.
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.