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”.
Universitas Sumatera Utara
Kah
NULL
2
Additional Condition NULL
Lah pun
NULL NULL
2 2
NULL NULL
Suffix
Measure Condition
Replacement
examples Bukukah buku Adalah ada Bukupunbuku
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 Bukunyabuku
Universitas Sumatera Utara
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 Berlarilari Belajarajar Bekerjakerja Perjelasjelas Pelajarajar Pekerjakerja
Universitas Sumatera Utara
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 Tarikantarik (Meng)ambilkanambil Makananmakan (per)janjianjanji Tandaitanda (men)dapatidapat Pantaipanta
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.
Universitas Sumatera Utara
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
Universitas Sumatera Utara
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 :
Universitas Sumatera Utara
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.
Universitas Sumatera Utara
Universitas Sumatera Utara
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
Universitas Sumatera Utara
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
Universitas Sumatera Utara
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
Universitas Sumatera Utara
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.
Universitas Sumatera Utara
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
Universitas Sumatera Utara
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.
Universitas Sumatera Utara