Similarity Measure

13 05 2008

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.


Actions

Information

37 responses

12 01 2016
Zahra Ashfiya Risnawati

salam pak yudi, saya mau tanya buku apa yah yang membahas tentang mahalanobis distance?
terima kasih sebelumnya.

20 03 2016
Yudi Agusta

Buku data mining biasanya membahas tentang definisi jarak tersebut. Kalau ada pembahasan tentang Mixture Modelling, biasanya mahalanobis distance selalu dibahas. Tks

5 11 2016
ilham akbar

pak jika semantik dan sintaktik similarity itu masuk ke bagian mana ya? apa kelebihan dan kekurangan amsing2? buat tugas akhir saya pak, makasih

9 10 2015
Ogie Nurdiana

untuk perhitungan cosine similarity apakah harus menghitung pembobotan yaitu TF-IDF ??

4 10 2015
Mukarromah :)

selamat malam pak,
pak apa kelebihan dan kekurangan masing2x pengukuran jarak tersebut ? mana yang lebih baik digunakan ?

20 03 2016
Yudi Agusta

Tidak ada lebih tidak ada kurang, yang perlu dipastikan bahwa dalam memilih definisi jarak, harus dilihat dulu tujuan pemodelan dan kesesuaian data dengan metode jarak yang akan digunakan. Demikian dan tks

24 08 2015
Muhammad shofi al baaqi

selamat malam pak, saya mahasiswa universitas airlangga jurusan sistem informasi.. saya mau mengerjakan skripsi dengan judul klasifikasi ayam petelur produktif berdasarkan ciri2 fisik ayam dengan metode knn.. kriterianya sudah saya lampirkan.. kriteria tersebut berupa data ordinal pak.. kalau memakai pendekatan euclidean distance dirasa tidak cocok untuk data yang saya punya.. kalau menurut bapak kira2 saya pakek perhitungan jarak apa ya pak ? saya sudah cari referensi dengan menormalisasi dengan normalize rank transformation.. tp saya kira itu juga kurang cocok.. mohon bantuannya pak.. terima kasih sebelumnya dan maaf merepotkan🙂
Kalau pakai hamming distance contohnya gimana pak.. Kan itu buat data binary seperti yang di contohkan..

20 03 2016
Yudi Agusta

Bagus sekali, memang data ordinal tidak cocok dengan euclidean distance. Hamming distance mungkin yang paling cocok dari semua definisi jarak yang ada. Tks

24 02 2015
Andrian Aprilianto

Assalamualaikum pak, mohon bantuan penjelasannya.
kalau untuk mengukur kesamaan atau kemiripan objek yang satu dengan objek yang lain paling cocok dengan rumus apa ya pak? seperti similarity yang di gunakan google play store dan amazon. apakah rumus Euclidean Distance cocok di gunakan? atau ada rumus lain yang lebih sesuai.

Terima Kasih.

2 10 2014
Hastuty

Pak bagaimana menggunakan rumus k-nearest neighbor pada tipe data ordinal ? apa dengan mixed euclidean distance

1 03 2015
Yudi Agusta

Metode jarak yang digunakan harus yang bisa untuk data ordinal. Misalnya coba Hamming distance. Tks

4 08 2014
Yudi Agusta

Pertanyaan dari Sdr. Reza Farmahni Galih:

Bapak yudi yth,

saya ingin menanyakan…
1. bagaimana cara meningkatkan probabilitas pada AMOS?
2. rumus malahanabois distance terdatapat T COV? bagaimana cara menghitung di excelnya pa?

Terima Kasih saya ucapkan

4 08 2014
Yudi Agusta

1. Probabilitas pada AMOS bisa ditingkatkan dengan menyusun variabel dalam model AMOS yang fit pada data paling bagus, tetapi dengan tetap mengakomodasi bahwa model harus tetap sederhana.
2. Mohon maaf, saya tidak familiar dengan penerapan statistik kompleks dalam excel.

Demikian

11 01 2014
Viiyaa Sylvia Wulandari

selamat malam, saya Sylvia saya sedang mengerjakan skripsi ttg clustering single linkage dengan Manhattan distance, Saya mauu tanya pak, apa kelebihan Manhattan distance dgn yg lain nya dlm clustering? terima kasih

26 02 2014
Yudi Agusta

Manhattan distance mempunyai konsep berbeda dengan fungsi jarak yang lain. Sebagai perbandingan, Euclidean distance mengukur jarak dengan rumus Pythagoras jarak = sqrt (x^2 + y^2). Sedangkan Manhattan distance diukur dengan rumus jarak = | x | + | y |. Jadi memang berbeda. Perbandingan antara keduanya tidak berupa kelebihan ataupun kekurangan, tetapi dari cara kita menterjemahkan hasil yang nanti didapatkan dalam proses yang dilakukan termasuk proses clustering.

Regards,

28 08 2012
alfin s

salam kenal pa yudi,
sebelumnya saya ucapkan terima kasih untuk tulisan yang bapak muat, sangat membantu untuk tugas saya
mau tanya pak, apakah tulisan diatas merujuk pada suatu sumber?
karena saya ingin mencantumkannnya pada daftar pustaka,

terima kasih pa🙂

26 02 2014
Yudi Agusta

Wah saya mengambil dari beberapa sumber. Lupa saya memunculkan sumber-sumbernya.

11 03 2012
sefia

maaf pak bole minta emailnya untuk tanya2 mengenai clustering..

trima kasih seblumnya..

(sefia_chandra@yahoo.com)

26 02 2014
Yudi Agusta
19 06 2011
gildhot

matab pak ulsan y bagus bgt…. sya sdang mengerjakan skripsi menggunakan metode levenshtein distance, sya mw tnya kelemahan dan kelebihan metode ini apa ya…

6 10 2011
Yudi Agusta

Levenshtein distance bukanlah suatu metode, tetapi suatu definisi dari suatu distance space yang berguna untuk string. Jadi kalau ditanya kelebihan dan kekurangan, tidak bisa dijelaskan. Yang ada adalah perbedaan dari distance space yang lain, yang pada intinya sudah dijelaskan di atas.

Semoga membantu

13 04 2011
K-MeaNs « electriboy

[…] ada di masing-masing cluster.Step 4. Alokasikan masing-masing data ke cluster terdekat menggunakan Hemming DistanceStep 5. Kembali ke Step 3, apabila masih ada data yang berpindah cluster atau apabila perubahan […]

11 02 2011
wahyu

pak,.saya perlu materi ini, supaya mempermudah saya mencarinya, saya mohon izin copas ke website saya ya pak..terima kasih

6 10 2011
Yudi Agusta

Silahkan, asal jangan lupa di-referensi di bagian bawahnya ya, sebagai bagian dari kode etik mengkopi tulisan orang lain…..

4 01 2011
boynurah

salam pak yudi, dan selamat tahun baru pak.
blog bapak sangat mantab sekali isinya. to the point pak😀
gini, saya sedang mengerjakan skripsi yang membahas clustering menggunakan agglomerative clustering, dengan membandingkan metode cosine similarity dan covariance similarity. untuk cosine similarity, saya bisa. tapi saya ada masalah di covariance pak. karena hasil perhitungan manual saya untuk covariance similarity antar 2 dokumen menghasilkan nilai minus, apakah itu benar atau salah pak? mohon pencerahan dari bapak. terima kasih sebelumnya atas jawaban dari bapak.
NB: untuk rumus covariance yang sya pakai adalah ini pak http://i644.photobucket.com/albums/uu170/immorality_boy/rumuscov.png

6 10 2011
Yudi Agusta

Dari rumus saja sudah ketahuan tidak akan mungkin negative, karena ada proses penghitungan kwadrat di dalamnya. Kemungkinan ada salah perhitungan dalam prosesnya.

Demikian

11 08 2010
si Paijah

terima kasih infonya sangat berguna

19 01 2010
Wulan

ada contoh penjelasan tentang humming distance calculation pada IR (saat stemming) tdk pak??
mohon pencerahannya trimakasih +))

20 01 2010
Yudi Agusta

Secara prinsip Hamming distance bisa diaplikasikan pada apa saja seperti yang telah dijelaskan di atas. Ada beberapa mungkin yang sering menjadi perhatian seperti panjang string yang dibandingkan tidak sama. Dalam hal tersebut, mungkin HD diimplementasikan dalam bentuk MHD (Modified Hamming Distance) yang bisa mengakomodasi perbedaan panjang string. Hal ini banyak terjadi pada word atau document matching ataupun stemming dalam kegiatan IR yang ditanyakan.

Semoga bisa sedikit menjawab.

20 01 2010
wulan

terimakasih pak yudhi,
cross-cek menurut penjelasan klo saya implementasikan
misal
term awal : building
term stlh di sremming : build
terdapat kamus kata-kata dasar

utk perhitunganny apakah benar nilai HD-ny 3 hanya melihat perbedaan panjang string antara term awal dengan hasil setelah di stemming?
tanpa membandingkan pd kamus walaupun dibagun kamus kata dasar..?

pertanyaan lain
menyimpang dari pembahasan measurement di IR performance selain HD, ada juga ERRT error counting yang menghitung “overstemming” dan “understemming”, saya kurang paham saat mengimplementasikannya dlm program…. setelah term stem sudah dihasilkan bagaimana program menentukan bahwa terjadi overstemming atau understemming mohon bantuannya…

terimakasih ^_^

17 11 2009
Rizky

salam pak yudi
pak, sya mw tanya kelebihan dan kelemahan pendekatan/ mengukur tingkat kesamaan(similiarity) dengan Posterior Probability dibandingkan Distance Similarity ? terima kasih pak..

17 11 2009
Yudi Agusta

Posterior Probability yang dihitung perbedaan probabilitas di antara variabel dari dua data yang dibandingkan. Sedangkan jarak, menghitung perbedaan absolut antara variabel dari dua data yang dibandingkan.

Mana yang lebih bagus? Saya tidak bisa merekomendasikan, karena biasanya posterior probability membandingkan dengan mengetahui karakteristik populasinya terlebih dahulu, sedangkan distance space menghitung jarak langsung antar data tanpa harus mengetahui karakteristik dari populasi dimana data itu berada.

Mudah ini menjawab dan bisa membantu

18 11 2009
Rizky

terima kasih pak,
ehm…pak maksud bpk u/ posterior probability dg mengetahui karakteristik populasinya terlebih dahulu, karakteristik yang seperti apa ?
terima kasih pak sebelumnya

30 11 2009
Yudi Agusta

Yang namanya probabilitas berarti harus ada dulu populasi yang mendasarinya. Yang berarti ada karakteristik dari populasi tersebut. Sedangkan jarak, tidak perlu untuk mengetahui populasinya, jadi tidak ada karakteristik yang perlu untuk dijadikan dasar untuk menghitung jarak.

Demikian dan semoga menjawab.

17 08 2009
Lauren

saya mau tanya nih, maksud d_Chebyshev (x1, x2) = max_i {x1i – x2i} apa ya?
makasih sblmnya..

17 11 2009
Yudi Agusta

Mencari nilai maksimal di antara perbedaan nilai antara variabel-variabel data yang satu dengan variabel-variabel data yang lain.

16 05 2009
Manellen

Terima kasih atas tulisan anda.
Sangat berguna.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: