BAB 2 LANDASAN TEORI

BAB 2

LANDASAN TEORI

2.1 Pengertian Stemming

Stemming merupakan suatu proses atau cara dalam menemukan kata dasar dari suatu kata. Stemming sendiri berfungsi untuk menghilangkan variasi-variasi morfologi yang melekat pada sebuah kata dengan cara menghilangkan imbuhan-imbuhan pada kata tersebut, sehingga nantinya di dapat suatu kata yang benar sesuai struktur morfologi bahasa Indonesia yang benar.

Stemming sendiri merupakan bagian dari proses Information Retrieval. Secara umum

ada

dua

proses

utama

dalam

IR,

yaitu

Indexing dan Searching.

Proses Indexing terdiri dari 4 subproses antara lain : Word Token (mengubah dokumen menjadi kumpulan term dengan cara menghapus semua karakter dalam tanda

baca

yang

terdapat

pada

dokumen

dan

mengubah

kumpulan term menjadi lowercase), StopWord Removal (Proses penghapusan katakata

yang

sering

ditampilkan

dalam

dokumen

seperti:and,

or,

not dan

sebagainya),Stemming (Proses mengubah suatu kata bentukan menjadi kata dasar) dan Word Weighting (Proses pembobotan setiap term di dalam dokumen). Ada banyak algoritma yang digunakan untuk melakukan proses stemming, khususnya stemming bahasa indonesia. Algoritma-algoritma tersebut antara lain : Algoritma Nazief

dan

Andriani,

algoritma Arifin

dan

Setiono,

algoritma Idris dan

Mustofa, algoritma Vega, algoritma Ahmad, Yussof dan Sembok, Porter dsb [5].

Universitas Sumatera Utara

2.2 Stemming Porter

Algoritma yang diimplementasikan dalam aplikasi ini menggunakan algoritma Porter. Algoritma Porter ditemukan oleh Martin Porter 1980. Algoritma tersebut digunakan untuk stemming bahasa inggris, kemudian karena proses stemming bahasa inggris berbeda dengan bahasa indonesia maka, dikembangkan algoritma porter khusus untuk bahasa indonesia (Porter Stemmer for Bahasa Indonesia) oleh W.B. Frakes pada tahun 1992. Algoritma ini terkenal digunakan sebagai stemmer untuk bahasa Inggris. Porter Stemmer dalam bahasa Indonesia akan menghasilkan keambiguan karena aturan morfologi bahasa Indonesia. Bila dibandingkan, untuk teks berbahasa Indonesia, Porter stemmer lebih cepat prosesnya daripada algoritma stemming yang lain. Tidak banyak algoritma yang dikhususkan untuk stemming bahasa Indonesia dengan berbagai keterbatasan didalamnya. Algoritma Porter salah satunya, algoritma ini membutuhkan waktu yang lebih singkat dibandingkan dengan stemming menggunakan algoritma lainnya [7]. Langkah-langkah algoritma Stemming Porter adalah sebagai berikut: 1. Periksa pada kata yang akan di Stemm jika terdapat partikel (“-kah”, “-lah”, “pun”), maka hapus partikel yang melekat. 2. Hapus kata ganti kepemilikan seperti “-ku”, “-mu”, “-nya”, jika ada. 3. Hapus first order prefiks (awalan pertama) seperti “-meng”, “-meny”, “-men”, “-mem”, “-me”, “-peng”, “-peny”, “-pen”, “-pem”, “-di”, “-ter”, “-ke”. 4. Hapus second order prefiks (awalan kedua) seperti “-ber”, “-per”. 5. Hapus sufiks (akhiran) seperti “-kan”, “-i”, “-an”.


Kah

NULL

2

Additional Condition NULL

Lah pun

NULL NULL

2 2

NULL NULL

Suffix

Measure Condition

Replacement

examples Bukukah buku Adalah ada Bukupunbuku

Tabel 2.1 Kelompok rule pertama : inflectional particles

Tabel 2.2 Kelompok rule kedua :inflectional possesive pronouns Suffix Ku Mu nya

Measure Condition

Replacement NULL NULL NULL

2 2 2

Additional Condition NULL NULL NULL

examples Bukuku buku bukumu buku Bukunyabuku


Tabel 2.3 Kelompok rule ketiga: first order of derivational prefixes Prefiks Meng Meny Men Mem Mem Me Peng Peny Pen Pem Pem Di Ter Ke

Replacement NULL s NULL p NULL NULL NULL s NULL p NULL NULL NULL NULL

Measure condition 2 2 2 2 2 2 2 2 2 2 2 2 2 2

Additional Condition NULL v… NULL v… NULL NULL NULL v… NULL v… NULL NULL NULL NULL

Examples mengukur--->ukur menyapu--->sapu menduga--->duga memilah--->pilah membaca--->baca merusak--->rusak pengukur--->ukur penyapu--->sapu penduga--->duga pemilah--->pilah pembaca--->baca diukur--->ukur tersapu--->sapu kekasih--->kasih

Tabel 2.4 Kelompok rule keempat: second order of derivational prefixes prefiks

replacement

Ber Bel Be Per Pel pe

NULL NULL NULL NULL NULL NULL

Measure condition 2 2 2 2 2 2

Additional condition NULL ajar K*er NULL ajar NULL

examples Berlarilari Belajarajar Bekerjakerja Perjelasjelas Pelajarajar Pekerjakerja


Tabel 2.5 Kelompok rule kelima: derivational suffixes suffix

replacement

Measure condition

kan

NULL

2

Additional condition Prefix

an

NULL

2

prefix

i

NULL

2

V, prefix

examples Tarikantarik (Meng)ambilkanambil Makananmakan (per)janjianjanji Tandaitanda (men)dapatidapat Pantaipanta

Stemming adalah proses untuk menggabungkan atau memecahkan setiap varianvarian suatu kata menjadi kata dasar [7]. Stem (akar kata) adalah bagian dari kata yang tersisa setelah dihilangkan imbuhannya (awalan dan akhiran). Contoh : connect adalah stem dari connected, connecting, connection, dan connections. Metode stemming memerlukan input berupa term yang terdapat dalam dokumen. Sedangkan outputnya berupa stem. Ada tiga jenis metode stemming, antara lain : 1.

Successor Variety (SV) : lebih mengutamakan penyusunan huruf dalam kata dibandingkan dengan pertimbangan atas fonem. Contoh untuk kata-kata : corpus, able, axle, accident, ape, about menghasilkan SV untuk kata apple : 1.

Karena huruf pertama dari kata “apple” adalah “a”, maka kumpulan kata yang ada substring “a” diikuti “b”, “x”, “c”, “p” disebut SV dari “a” sehingga “a” memiliki 4 SV.

2.

Karena dua huruf pertama dari kata “apple” adalah “ap”, maka kumpulan kata yang ada substring “ap” hanya diikuti “e” disebut SV dari “ap” sehingga “ap” memiliki 1 SV.


2.

N-Gram Conflation : ide dasarnya adalah pengelompokan kata-kata secara bersama berdasarkan karakter-karakter (substring) yang teridentifikasi sepanjang N karakter.

3.

Affix Removal : membuang suffix dan prefix dari term menjadi suatu stem. Yang paling sering digunakan adalah algoritma Porter Stemmer karena modelnya sederhana dan effisien. 1.

Jika suatu kata diakhiri dengan “ies” tetapi bukan “eies” atau “aies”, maka “ies” direplace dengan “y”

2.

Jika suatu kata diakhiri dengan “es” tetapi bukan “aes” atau “ees” atau “oes”, maka “es” direplace dengan “e”

3.

Jika suatu kata diakhiri dengan “s” tetapi bukan “us” atau “ss”, maka “s” direplace dengan “NULL”

Algoritma Stemming

Successor Variety

Affix Removal

N-Grams Conflation

Porter Stemmer

Gambar 2.1 Diagram Stemming


Stemming adalah proses pemetaan dari penguraian berbagai bentuk kata baik itu prefik sufik, maupun gabungan antara prefik dan sufik,menjadi bentuk kata dasarnya atau stem.Algoritma Stemming yang digunakan adalah Potter Stemmer untuk bahasa Indonesia. Algoritma stemming

dapat mengatasi akhiran yang

berupa partikel,

kata

akhiran

yang

menunjukkan

ganti kepemilikan, prefiks

(imbuhan), sufiks (akhiran), dan gabungan antara prefiks dan sufiks. Sebelum melakukan

proses

penghilangan

imbuhan

pada Potter

Stemmer, dilakukan

perhitungan measure. Stemming itu proses pemotongan (pemangkasan) kata untuk mendapatkan bentuk dasar (kata dasar) dari kata tersebut. Misal terdapat kata mempermainkan, maka dari kata tersebut bisa dipilah-pilah menjadi mem + per + main + kan. Secara ilmu bahasa, hal ini mudah dilakukan oleh manusia, karena manusia sudah punya database memori linguistik yang komplit untuk melakukan parsing komponen-komponen penyusun (ejaan : imbuhan dan kata dasar) dari suatu kata. Seperti misalnya, dari kata mengantuk, kita bisa langsung memilah-milah menjadi me(ng) + kantuk (bukan meng + antuk atau me + ngantuk). Namun bagaimana jika kita ingin melakukan automasi proses stemming ini dengan sebuah program? Mampukah program mengenali perubahan morfologi kata ini dengan tepat? Hal ini bukanlah tidak mungkin. Proses stemming sendiri sudah cukup terkenal, bahkan seringkali kita gunakan tanpa kita sadari. Misal Google? Proses pencariannya sekarang sudah memakai Stemming (pencarian kata fishing juga menghasilkan katakata fish, fishy, fisherman dll).Pemeriksaan semua kemungkinan bentuk kata. Setiap kata diasumsikan memiliki 2 awalan (prefiks) dan 3 akhiran (sufiks). Sehingga bentuknya menjadi :


Prefiks 1 + Prefiks 2 + Kata dasar + Sufiks 3 + Sufiks 2 + Sufiks 1 Pemotongan dilakukan berurutan : Awalan 1, Awalan 2, Akhiran 1, Akhiran 2, Akhiran 3 (kalau ada), dan Kata Dasar.Setiap tahap pemotongan diikuti dengan pemeriksaan di kamus (berisi daftar kata dasar) apakah hasil pemotongan itu sudah berada dalam bentuk dasar. Jika pemeriksaan berhasil maka proses dinyatakan selesai dan tidak perlu melanjutkan proses pemotongan imbuhan selanjutnya.



Gambar 2.2 Flowchart Stemmer Porter

Pada proses stemmer porter, pertama-tama masukkan kata yang akan di stem, lalu memeriksa apakah terdapat partikel, jika ada maka hapus partikel, jika tidak maka lanjutkan memeriksa apakah terdapat kata kepemilikan, jika ada maka hapus, jika tidak maka lanjutkan. Periksa apakah terdapat prefix, jika ada maka hapus, jika tidak maka lanjutkan memeriksa apakah terdapat sufiks.Jika terdapat sufiks maka hapus. Jika pemeriksaan berhasil maka proses dinyatakan selesai dan tidak perlu melanjutkan proses pemotongan imbuhan selanjutnya. Dokumen dalam bahasa indonesia mempunyai keunikan tersendiri, karena kata - kata dalam bahasa indonesia dapat berubah bentuk saat mendapatkan imbuhan. Akibat dari hal proses Stemmer dari dokumen berbahasa Indonesia, yaitu proses mengembalikan kata ke bentuk dasar, memerlukan teknik tersendiri yang berbeda dengan teknik Stemmer pada bahasa bahasa lain. Fungsi Stemmer yang didesain berdasarkan algoritma Porter Stemmer for Bahasa Indonesia adalah inti dari tahap pre-processing yang dibuat. Guna dari fungsi ini adalah sebagai berikut: 1. Dengan mengembalikan kata menjadi kata dasarnya, akan sangat mengurangi macam kata yang perlu diperiksa dan dibandingkan dengan tabel Stopword maupun tabel Keyword. Hal ini akan mempercepat proses perbandingan kata serta mengurangi isi tabel Stopword dan tabel Keyword.

2. Pengembalian kata ke bentuk dasarnya dapat dilihat sebagai pengelompokan beberapa macam kata yang memiliki arti sama atau sejenis dan digeneralisasi menjadi satu kata saja. Hal ini berguna untuk proses Text Mining selanjutnya, karena akan


dapat meningkatkan kemungkinan terbentuknya sebuah Rule Assosiasi, atau dapat meningkatkan kualitas Rule Assosiasi yang dihasilkan.

2.3 Winnowing

Algoritma Winnowing merupakan algoritma yang digunakan untuk deteksi penjiplakan. Input dari algoritma ini adalah dokumen teks yang diproses sehingga menghasilkan output berupa kumpulan nilai-nilai hash, nilai hash merupakan nilai numerik yang terbentuk dari kumpulan nilai hash

perhitungan

ASCII

tiap

karakter.

Kumpulan-

tersebut selanjutnya disebut fingerprint [11]. Fingerprint

inilah yang digunakan dalam deteksi penjiplakan. Langkah awal dalam penerapan algoritma Winnowing adalah membuang karakter-karakter dari isi dokumen yang tidak relevan misal tanda baca spasi dan simbol lain. Langkah kedua isi dokumen yang telah dilakukan pembersihan selanjutnya dilakkukan pembentukan rangkaian gram, dimana n =5. Langkah ketiga dari rangkaian gram yang telah terbentuk dibentuk nilai hash dengan nilai ASCII tiap karakter.

Pembentukan nilai hash

menggunakan persamaan rolling hash. Langkah keempat nilai-nilai hash yang telah terbentuk dibentuk window-window. Dari window-window yang telah terbentuk dilakukan pemilihan nilai hash terkecil pada tiap window untuk dijadikan


fingerprint tiap dokumen. Nilai-nilai fingerprint inilah yang digunakan untuk menemukan tingkat presentase kesamaan sebuah dokumen dengan dokumen lain. Input dari algoritma ini sendiri adalah string dari dokumen tersebut, dan output nya berupa nilai-nilai hash yang dinamakan fingerprints dari dokumen tersebut. Syarat dari algoritma deteksi penjiplakan seperti whitespace insensitivity, yaitu pencocokan teks file seharusnya tidak terpengaruh oleh spasi, jenis huruf kapital, tanda baca dan sebagainya, noise surpression yaitu menghindari pencocokan teks file dengan panjang kata yang terlalu kecil atau kurang relevan dan bukan merupakan kata yang umum digunakan, dan position independence yaitu pencocokan teks file seharusnya tidak bergantung pada posisi kata-kata sehingga kata dengan urutan posisi berbeda masih dapat dikenali jika terjadi kesamaan. Winnowing telah memenuhi syarat-syarat tersebut dengan cara membuang seluruh karakter-karakter yang tidak relevan misal: tanda baca, spasi dan juga karakter lain, sehingga nantinya hanya karakter-karakter yang berupa huruf atau angka yang akan diproses lebih lanjut.

Gambar 2.3 Persamaan Winnowing


Algoritma winnowing lebih cepat waktu komputasinya daripada algoritma rabin-karp karena fingerprint dari algoritma rabin-karp lebih banyak sedangkan winnowing dipilih nilai minimum dari window nya. keunggulan algoritma winnowing bisa memberikan informasi posisi fingerprint. Penggunaan nilai window yang semakin besar dapat mempengaruhi dalam waktu proses, karena semakin besar nilai dari suatu window mempengaruhi proses pembentukan nilai-nilai hashing yang semakin kecil. Selain itu, nilai k-gram dan basis juga mempengaruhi dalam memberikan persentasi kemiripan yang diperoleh sistem itu sendiri [3].

2.3.1 Hashing

Hashing adalah mengubah serangkaian karakter menjadi suatu kode atau nilai yang menjadi penanda dari rangkaian karakter tersebut. Dengan adanya

pengubahan

inilah, maka tercipta penanda sebagai indeks untuk digunakan dalam mencari informasi kembali atau information retrieval. Fungsi untuk menghasilkan nilai ini disebut fungsi hash, sedangkan nilai yang dihasilkan disebut nilai hash [11]. Nilai hash pada umumnya digambarkan sebagai fingerprint yaitu suatu string pendek yang terdiri atas huruf dan angka yang terlihat acak. Fungsi Hash adalah suatu cara menciptakan “fingerprint” dari berbagai data masukan. Fungsi Hash akan mengganti atau mentranspose-kan data tersebut untuk menciptakan fingerprint, yang biasa disebut hash value. Hash value biasanya digambarkan sebagai suatu string pendek yang terdiri atas huruf dan angka yang terlihat random (data biner yang ditulis dalam notasi hexadecimal). Algoritma fungsi hash yang baik adalah yang menghasilkan sedikit hash collision. Hash collision merupakan kejadian dua atau lebih hash memiliki nilai hash yang sama.


2.3.2 K-gram

K-gram adalah rangkaian substring yang bersebelahan dengan panjang. Metode ini menghasilkan rangkaian substring sejumlah k-grams, dimana k adalah parameter yang dipilih oleh user. K-gram mengambil substring karakter huruf sejumlah k dari sebuah kata yang secara kontinuitas dibaca dari teks sumber hingga akhir dari dokumen [9]. Dibawah ini salah satu contoh k-gram dengan k=5: Text: pohon anggur, dan melon Kemudian dilakukan penghilangan spasi : pohonanggurdanmelon Sehingga

dihasilkan

rangkaian

5-grams

yang

diturunkan

dari text : Pohon|| ohona || honan ||onang|| nanggu ||anggu ||nggur ggurd

||gurda||

urdan||

rdanm||

danme||

anmel||

nmelo

||melon


2.4 Jaccard’s Similarity Coefficient

Jaccard’s Similarity Coefficient (Jaccard 1912) merupakan indeks umum untuk variabel biner. Hal ini didefinisikan sebagai hasil bagi antara persimpangan dan serikat variabel dibandingkan berpasangan antara dua benda. Untuk menghitung kemiripan dari dua dokumen , diperlukan Jaccard’s Similarity Coefficient, dengan rumus :

│ Aᴖ B│ D(A,B) = ________________

X

100%

│ AᴗB│- │ Aᴖ B│

Keterangan:

D(A,B) merupakan nilai similarity , │ Aᴖ B│ jumlah dari fingerprints dokumen 1 dan 2 yang sama, │ AᴗB│ ialah jumlah fingerprints dokumen 1 dan 2 dikurangi jumlah dari fingerprint dokumen 1 dan 2 yang sama.


BAB 2 LANDASAN TEORI

Recommend Documents