Metode Penentuan Kemiripan Dan Jarak Berupa Warna, Kata Dan Makna (Studi

Kasus : Search Engine Google Dalam Menentukan Kata Kunci Yang Mirip)

ENDIK KUSWANTORO 2214206706

Telematika CIO INSTITUT TEKNOLOGI SEPULUH NOPEMBER

ABTRAKSI

Seiring dengan perkembangan zaman dan teknologi yang semakin mutakhir, keperluan manusia tidak pernah terlepas dari penggunaan komputer untuk membantu efisiensi dalam pengolahan data yang

meliputi suara, citra, teks dan sebagainya. Suatu hal dalam pengolahan citra adalah penemuan kembali informasi atau data-data yang diinginkan oleh pengguna atau dengan istilah temu balik informasi atau

Information retrieval (IR). Tujuannya tidak lain ialah menemukan kembali dokumen yang memuat informasi yang sesuai dengan query dari pengguna. Dalam makalah ini akan dijelaskan bagaimana teknik

– teknik dalam menentukan kemiripan berupa citra dan menentukan jarak antar citra sehingga dapat diketahui jarak terdekatnya. Selain itu bagaimana menentukan kata dan makna yang berkaitan dan berdekatan maknanya, sehingga user merasa terbantu dengan menentukan kata kunci yang sesuai

dengan yang diinginkan.

I. PENDAHULUAN

Kemutakhiran teknologi yang sudah berkembang menuntut manusia untuk terus melakukan pengembangan – pengembangan dalam teknologi informasi, terutama , keperluan manusia tidak pernah terlepas dari penggunaan komputer untuk membantu efisiensi

dalam pengolahan data yang meliputi suara, citra, teks dan sebagainya. Salah satu teknologi yang cukup mempengaruhi perkembangan teknologi lainya ialah teknologi search engine, dimana seseorang dapat memperoleh banyak informasi pengetahuan yang luas melalui aplikasi search engine tersebut, dengan semakin banyak orang mengakses search engine maka teknologi yang digunakannya pun semakin berkembang tidak hanya inputan berupa teks tetapi pencarian berdasar image atau gambar dimana user cukup memasukan gambar yang akan dicari untuk di upload secara otomatis search engine akan menampilkan gambar yang mirip dengan gambar yang dijadikan kata kunci tersebut. Dalam makalah ini akan membahas metode menentukan ejaan yang tepat jika user memasukan ejaan yang salah, metode cara menentukan kemiripan citra bagaimana menentukan jarak antar citra, dan metode cara menentukan hubungan makna kata yang paling dekat.

II. PENENTUAN EJAAN KATA PADA SEARCH ENGINE

Mesin pencari sangat dibutuhkan saat ini. Hampir semua orang terbantu untuk mencari informasi melalui mesin pencari. Hanya dengan memasukkan keyword, maka akan muncul ratusan hasil yang terkait dengan keyword tersebut. Namun terkadang beberapa orang tidak sengaja memasukkan keyword dengan ejaan yang salah, mungkin keyword tersebut kurang sejumlah huruf atau salah mengetikkan beberapa huruf dalam keyword tersebut. Hal ini berdampak pada hasil pencarian yang muncul. Mungkin hasil pencarian yang keluar tidak sesuai dengan apa yang kita maksud atau kadang-kadang pencarian dengan keyword tersebut tidak memberikan hasil sama sekali. Namun jika hal itu terjadi, biasanya mesin pencari akan memberi tahu kita bahwa ejaan keyword yang kita masukkan ada yang salah. Contohnya pada Google Search seperti berikut ini:

Dalam contoh tersebut penulis mengetikkan keyword dengan ejaan yang salah, tapi aplikasi Google Search memberikan rekomendasi mengenai keyword yang mirip dengan keyword yang penulis masukkan. Dan memang benar keyword yang diberikan Google tersebut sebenarnya keyword yang penulis cari. Untuk pengecekan apakah ejaan suatu keyword itu benar atau salah bisa dilakukan dengan mencari dalam kamus. Jika suatu keyword tidak terdapat dalam kamus, bisa berarti keyword tersebut mungkin salah ejaan. Untuk memberikan rekomendasi keyword yang sesuai dengan yang kita masukkan dapat dilakukan dengan mencari keyword dalam kamus yang mempunyai kemiripan dengan masukan keyword dengan ejaan yang salah sebelumnya. Untuk mencari kemiripan tersebut bisa dilakukan dengan melakukan pencarian substring dari keyword yang ingin dicari terhadap kata-kata dalam kamus. Semakin banyak substring yang ditemukan pada suatu kata, kemungkinan besar kata tersebut merupakan kata yang dicari. Pencocokan substring tersebut bisa dilakukan dengan menggunakan algoritma KMP. Algoritma Knuth-Morris-Pratt dikembangkan oleh D. E. Knuth, bersama-sama dengan J. H. Morris dan V. R. Pratt. Dalam algoritma pencarian string dengan menggunakan brute force, ketika ditemukan ketidakcocokan pattern dengan teks, maka pattern tersebut digeser satu karakter ke kanan. Sedangkan jika menggunakan algoritma KMP (Knuth-Morris-Pratt), informasi yang digunakan untuk melakukan jumlah pergeseran setiap terjadi ketidakcocokan akan dikelola dalam algoritma ini. Kemudian algoritma ini menggunakan informasi tersebut untuk

membuat pergeseran yang lebih jauh, tidak seperti algoritma brute force yang hanya digeser satu karakter. Dengan algoritma KMP, waktu pencarian dapat dikurangi secara signifikan. Dalam algoritma KMP, terdapat beberapa definisi yang digunakan :

Misalkan A adalah alfabet dan x = x1x2…xk , k € N, adalah string yang panjangnya k yang dibentuk dari karakter-karakter di dalam alfabet A.

Awalan (prefix) dari x adalah upa-string (substring) u dengan u = x1x2…xk – 1 , k {1,2, …, k – 1} dengan kata lain, x diawali dengan u.

Akhiran (suffix) dari x adalah upastring (substring) u dengan u = xk – b xk – b + 1 …xk , k € {1, 2, …, k – 1} dengan kata lain, x diakhiri dengan v.

Pinggiran (border) dari x adalah upa-string (substring) r sedemikian sehingga r = x1 x2…xk – 1 dan u = xk – b xk – b + 1 …xk, k ∈{1, 2, …, k = 1}, dengan kata lain, pinggiran dari x adalah upa-string yang keduanaya awalan dan juga akhiran sebenarnya dari x.

Algoritma KMP melakukan proses awal terhadap pattern P dengan menghitung fungsi pinggiran yang mengindikasikan pergeseran s terbesar yang mungkin dengan menggunakan perbandingan yang dibentuk sebelum pencarian string. Dengan menggunakan fungsi pinggiran ini, dapat dicegah pergeseran yang tidak berguna seperti yang terjadi pada algoritma brute force. Fungsi pinggiran tersebut hanya bergantung pada karakter-karakter di dalam pattern, bukan karakter- karakter yang ada di dalam teks. Fungsi pinggiran b(j) didefinisikan sebagai ukuran awalan terpanjang dari P yang merupakan akhiran dari P[1..j]. Sebagai contoh, misalnya pattern P = abcabd. Nilai fungsi pinggiran untuk setiap karakter dalam pattern P sebagai berikut:

Algoritma untuk menghitung pinggiran sebagai berikut:

Selanjutnya dilakukan percobaan pencocokan pattern P dengan sebuah teks T = abcabcabd. Awal pencocokan digambarkan sebagai berikut:

Kemudian ditemukan ketidakcocokan pada posisi ke 6. Jumlah pergeseran setelah itu ditentukan oleh pinggiran dari awalan P yang bersesuain. Awalan yang diperoleh yaitu abcab, dengan panjang l = 5 dan pinggiran terpanjang untuk string P[1..5] adalah ab dengan nilai fungsi pinggirannya 2 sehingga jarak pergeseran selanjutnya adalah l – b = 5 – 2 = 3. Setelah digeser sebanyak 3 karakter akhirnya pattern P ditemukan dalam teks T.

III. PENENTUAN KEMIRIPAN CITRA

Seiring dengan perkembangan zaman dan teknologi yang semakin mutakhir, keperluan

manusia tidak pernah terlepas dari penggunaan komputer untuk membantu efisiensi dalam

pengolahan data yang meliputi suara, citra, teks dan sebagainya. Suatu hal dalam

pengolahan citra adalah penemuan kembali informasi atau data-data yang diinginkan oleh

pengguna atau dengan istilah temu balik informasi atau Information retrieval (IR).

Tujuannya tidak lain ialah menemukan kembali dokumen yang memuat informasi yang

sesuai dengan query dari pengguna.

Pada dokumen citra ini tersusun dari pixel demi pixel dan ukurannya dinyatakan dalam

jumlah pixel misalkan citra berukuran 100 x 100 pixel artinya citra ini berukuran persegi

dengan panjang setiap sisinya 100 pixel. Karena persepsi manusia terhadap suatu citra lebih

dipengaruhi oleh komposisi warna, maka kita juga sering membedakan citra berdasarkan

warna yang dikandungnya. Persepsi itulah yang menimbulkan gagasan dibuatnya Image

retrieval yang memakai histogram warna dari pixel-pixel citra sebagai representasi dari

komposisi warna suatu citra untuk menghitung dan mencari nilai-nilai kemiripan dari satu

citra grayscale yang dibandingkan dengan citra-citra grayscale uji diluar citra yang

direpresentasikan sebagai database. Tingkat kemiripan antar citra dapat ditentukan

berdasarkan nilai jarak antar histogramnya, semakin kecil jaraknya, maka semakin tinggi

tingkat kemiripannya. Jarak antar histogram pada citra berwarna dihitung untuk setiap

komponen warnanya.

Pada percobaan itu diambil 1 gambar grayscale berukuran bebas dan dinormalisasi menjadi

100 x 100 pixel sebagai database yang akan dicari nilai kemiripannya dengan sekelompok

citra-citra grayscale lainnya yang sama-sama berada pada sebuah folder.

Karena dalam percobaan kali ini penulis mengharuskan 3 macam gambar sebagai

citra database maka pengambilan gambar hingga eksekusi pengukuran similarity dilakukan

3 kali dengan citra-citra yang berbeda namun masih dalam satu folder yang berisi banyak

citra tadi agar mudah dibandingkan. Sehingga ketika pengambilan gambar telah berhasil lalu

proses hitung kemiripan berlangsung, maka akan tampak statistik yang memuat daftar

masing-masing nama file citra beserta nilai kemiripannya dari yang termirip (bernilai Nol)

sampai paling jauh kemiripannya. Maka dari itu bisa didapatkan: citra yang termirip dengan

database image 1 adalah citra X ,citra yang termirip dengan database image 2 adalah citra Y,

begitu pula yang termirip dengan database image 3 adalah citra Z. Proses dan mekanisme

terjadinya pengkuran kemiripan citra percobaan ini ialah Mula-mula citra yang akan dipakai

sebagai pembanding (citra database) di load. Proses ini akan memberikan mekanisme input

image sekaligus normalisasi kedalam 100 x 100 pixel sebagai hasil dari proses oleh

algoritme aplikasi CBIR ini. Lalu terjadi ekstraksi untuk pengenalan histogramnya dan

dideskripsikan sebagai vector ciri dan direkam dalam basis data ciri. Pada proses ini

histogram dari citra database direkam untuk siap dibandingkan pada sekumpulan histogram

yang direpresentasikan kedalam vector ciri dari citra-citra query dalam satu folder. Jadi

ketika suatu folder yang memuat citra query dari user telah di browse masuk kedalam

system maka algoritma melanjutkan kalkulasi kemiripan dengan nilai-nilai histogram

masing-masing citra query yang sudah direpresentasikan dalam vector cirri tadi sehingga

didapatkan jarak kemiripannya. Dalam proses pembandingan kemiripan digunakan indeks

agar pengaksesan vektor ciri dalam basis data lebih efisien. Selanjutnya dilakukan proses

temu-balik dan pengurutan citra berdasarkan nilai yang dihasilkan pada proses

pembandingan tingkat kemiripan. Dengan histogram ini pula dapat dicari citra yang

memiliki kemiripan komposisi warna, tentunya pegukurannya dengan menghitung jarak

histogram. Jika G = {g1, g2, . . . , gN } dan H = {h1, h2, . . . , hN } adalah histogram

warna dari dua buah citra, dimana gi dan hi adalah jumlah piksel pada level ke i dari kedua

histogram dan N adalah jumlah level untuk tiap histogram, maka jarak (d) antara dua

histogram dapat dinyatakan dalam jarak Manhattan seperti pada Persamaan (1) sebagai

berikut

Pada masing-masing citra, jumlah pixelnya sangat beragam, maka histogram perlu

dinormalisasi agar nilai selisih jarak histogram invariant terhadap ukuran citra. Normalisasi

dilakukan dengan cara membagi jumlah piksel untuk masing-masing level dengan jumlah

total piksel dalam citra (N) sehingga didapatkan nilai minimum 0 dan maksimum 1 untuk

tiap level warna. Normalisasi tiap level histogram (hi) dinyatakan dalam Persamaan berikut

(Nilai rerata dari h) = hi/N

Dalam percobaan kali ini dapat disimpulkan bahwa sistem temu-balik (retrieval) yang telah

dibuat dapat menemukan kemiripan antar citra berdasarkan nilai jarak antar histogramnya.

Ini terbukti dengan hasil percobaan pada program yang telah dibuat menunjukkan bahwa

citra yang memiliki kemiripan distribusi warna masuk dalam ranking atas, dan citra yang

sama persis, masuk di ranking satu dan memiliki selisih jarak sama dengan nol.

IV. PENENTUAN KEMIRIPAN MAKNA KATA

Kemiripan kata yang dimaksud adalah kemiripan antara dua kata secara kontekstual,

misalnya kata “merah” lebih mirip dengan “putih” dibandingkan dengan “merak” secara

konteks. Kemampuan menghitung kemiripan kata adalah bagian penting dalam banyak

aplikasi pemrosesan bahasa alami. Dalam information retrieval atau question answering,

pengolahan kata-kata dalam suatu dokumen memerlukan informasi kata-kata yang memiliki

kesamaan makna. Pada summarization, generation, dan machine translation, informasi

kemiripan antara dua kata diperlukan untuk mengganti satu kata dengan kata yang lain

dalam konteks tertentu.

Algoritma untuk menentukan kemiripan kata terdiri atas dua metode, yaitu thesaurus

methods dan distributional methods. Thesaurus methods melakukan pengukuran terhadap

jarak antara dua kata secara makna pada on-line thesaurus seperti WordNet atau MeSH,

sedangkan distributional methods melakukan estimasi kemiripan kata dengan menemukan

kata-kata yang memiliki kemiripan disribusi dalam sebuah korpus (Jurafsky dan James,

2009). karena belum ada on-line thesaurus yang memadai untuk bahasa Indonesia, kita akan

membahas bagaimana menghitung kemiripan kata menggunakan distributional methods .

Intuisi dari distributional methods adalah bahwa makna dari sebuah kata berhubungan

terhadap distribusi kata-kata disekelilingnya. Sebagai contoh, misalnya dalam korpus

terdapat tiga kalimat seperti berikut ini :

Saya tinggal di Bandung,

Kota Bandung sangat indah,

Bandung berada di pulau Jawa.

Konteks dari kata “Bandung” akan sama dengan kata “Pontianak” karena sangat besar

kemungkinannya, jika kata “Bandung” diganti dengan kata “Pontianak” maka kalimat-

kalimat nya juga akan terdapat di korpus. Selanjutnya dapat ditentukan fitur-fitur untuk kata

“Bandung”, misalnya “muncul setelah terdapat kata tinggal”, “muncul langsung setelah kata

kota”, “muncul sebelum terdapat kata pulau” dan lain-lain. Secara umum fitur dapat

didefinisikan sebagai “kata w yang muncul di sekitar kata vi”. Selanjutnya makna dari

sebuah kata w dapat direpresentasikan sebagai fitur vektor w = (f1, f2, f3, … ,fn) (Jurafsky

dan James, 2009):

Lin (1998), menggambarkan bahwa setiap fitur f terdiri dari pasangan sebuah kata dan relasi

(r,w'), misalnya fitur (berada_di, pulau), “berada_di” adalah relasi dan pulau adalah kata

nya. Nilai setiap kata dapat ditentukan dengan menghitung jumlah kemunculan kata tersebut

di dalam korpus terhadap fitur yang ada. Probabilitas sebuah fitur diberikan kepada target

kata w adalah P(f|w) yang dapat didefinisikan sebagai P(f|w) = count(f,w) / count(w).

Probabilitas sederhana dapat didefinisikan sebagai sebuah ukuran hubungan (measure of

association) : assocprob(w,f) = P(f|w)

Keterkaitan Hubungan w,r,w' dapat dianggap sebagai bagian hubungan dari 3 kejadian yaitu

: A: Kata w yang dipilih secara acak

B: Relasi r yang dipilih secara acak

C: Kata w' yang dipilih secara acak

Jika diasumsikan hubungan A dan C dengan relasi B adalah conditionally independent,

probabilitas dari hubungan terjadinya A, B, dan C diestimasikan sebagai (Lin, 1998) :

PMLE (B) PMLE (A|B) PMLE (C|B)

dimana PMLE adalah probablilitas maximum likelihood estimation dari probabilitas distribusi

dengan (Lin, 1998) :

Lin (1998), mendefinisikan mutual information antara kata w dan w' dengan r sebagai

bagian dari relasi (r,w') sebagai :

Jeff dkk. (2011) mengadopsi definisi yang dipaparkan oleh Lin (1998) dengan mengganti r

dengan n-gram, sebagai contoh Cnt(w1,r,w2) diganti dengan total dari jumlah [2,3,4,5]-gram

yang dimulai dengan w1 dan diakhiri dengan w2.

Dengan T(w1) yang didefinisikan sebagai set pasangan (r,w2) dan syarat I(w1 ,r,w2) harus

positif, dapat didefinisikan kemiripan kata S(w1,w2) sebagai :

V. DAFTAR PUSTAKA Jeff, M.A., Matsoukas S., dan Schwartz , S.R. (2011). Improving Low-Resource

Statistical Machine Translation with a Novel Semantic Word Clustering Algorithm,

Proceedings of the MT Summit XIII, Xiamen, China, 352-359.

Jurafsky, D., dan Martin, H. (2009) : Speech and Language Processing, Parson

International Edition, New Jersey.

Lin, D. (1998) : Automatic Retrieval and Clustering of Similar Words, Proceedings

of the 17th international conference on computational linguistics. Vol. 2, Canada.

Munir, Rinaldi, Diktat Kuliah IF2211 Strategi Algoritma. Program Studi Teknik Informatika ITB, 2013.

http://fivedots.coe.psu.ac.th/Software.coe/LAB/PatMatch/PatternMatching.ppt. 19 Desember 2013