Web Mining

ISSN:1907.3526

Proueedinl

Seminar Nasional Riset Teknologi lnformasi - SBITI 2006 Yogyak8rra, O1 JUL 2006

Artif icial lntelegence Computotion Database Tech Data Communication Data Mining,/ Web Mining lmage Processing lnformation System

Microprocessor Muirimedia Networking Operatinq System Secunty

SekdahTnqoi Maisemen nlomarka dai

komluef

DAFTAR ISI

KEY oIE SPEAKER

Pen.nfaaran Tcknologi Infonnasi di Ncg@ Berkembug I tcl

h^'ia

Peranglat Lunak dan Data Mlnlng Pnrnsld Lun,k Pc'no, d \or B,.or
A.

Rekayasa

tr,,"^

t^- tt^.

lLqoht

l.lo"t.Itd) MLhnaD,rho

(r' {it

D(.rnds- lmphmfl' tuiApl 1,.' Pe_c"ddio,nKrkrcgdsh-Vensol'h \{rmh o,m,'Pemurr^6,nd Pel.)a'(''-'lnkm3'onJ<enins --tp\ontut turnar- ltt: oh lqan Fahado A'vnt tdt.. Pemir^arlrnrt Fo'-n.il D!ldkrICEVenjaj ilode oem.lir n't.,i o.,i.t 1.",.n,. D;.-o"' , D\' x,dn Ea,ul- Hedra tadtv Letanao" "'

i.r. K'i\.ltrtr,,Annyl'napddaD.ESinvJ ldnngden8sVengg'nalan r;,"4"..^",. M,rtur Model dan Reconn tuded PhseSpace Chaaine Fdi.hah,luhd Nafis Saadi Nol Tatfk,vrdhi PltvoDo t' .\o

?en{,pzn Sattu e Q aliy ,lstands pa& Olganh$i Penge bang Perarytar Lnml ar Lun ak

trfiuk Mc tr itrgkatkan Kus liras Pedngk

1plikasiTeo Kisi

Hr'.',^.aJar

d

alam Implement

s i

Merddc Tabulasi u nh k Mctrvededdakan Fungs i

B

oolc

P.ndekatai softwaE Rcquiremeni P te!tr untok Prasvarar dan Spcsifikrsi S isienr h,fo.mar i Kcmggolaan d i Runrn Sakn F*. K Btdidilio. Kodrdt Mdhatm........ ... ....

Desin Scbush Obrtk donean Menggunakan Metod. Coad Yourdon d5n R*ponsibiliryDrivcn Desili (RDD) En.la,z Wdhyu inslih.. .... ....,. ...-..---- ..-

$aln6

datr

P.Bodelatr Enkripsi Dab Pada Mclodc Caesar Chipq Me.g8Makatr --t ADia L.nt Deb rrh

r.

Bi.senham AlSorithm:

K hi.

,,/rr,,4ralian

dtu] Andlvtis ih

Rdkr

Shapc

rata t uhhan Caal.

*"-',.*"*-*'**--l

Microelt Windows din Alat Eleklronik Mengrgualm Sura (Voic. hn ader) yrdi ,4:tim,lnlra vatini. .... .... . .... ... .... ... ... .. Pengendali

N{engonrol Konrpnter secam

Rdote Melalui IRc de4@ vftuil Baic

....

2ll

....... .........

.............

217

.. .... ..... .....

................

221

PetukaEn Data Elektrcnik denEan LMail d.n9nn Mdode StaE-,4 d-Fm d .................................... I oede Mujiratna,Y suyuro......

i5

tlni A4i.a kdra votini.. ....

Uj i

KonparEi Algoritn" Penmpat Data Tak-Hilotrg

H.na*anSulisryaDto.................. ...

P.nerjemah Bihasa

(Insslill

onesia) Mensigunatd Tekmlosi lr',i?./ess

dadlone

MuhammidEBinAshaiHaryono,YustiDNiIsm1i....,,....,.....,........................................

BI

SistenRouterAmanM gglnakan CD Lile Linux tYoEita. ... .... .,--- -- -- Memanaa*an Voice Modm sebasai Galeway VOIP

Si-qitAn$.o......--..................,.......................

c

241

Jarr.gan syaralnrum, sist€m ce.da, dan Fury

Pengmh .t e,,,r,s Kata dalam Peningkat Unjuk Keoa mh,k Dokum.nB bshdaIndonesia

D,./-e,r Cl6r./,rg

amlHmai.,

253

Khsinkasi Mulirpcchol Re ate Se,ri,g Ganbd dm8m Jeinertr Syaml .1dhur Doriel Lih tna, Darnahto Dvi K aio Buuki, Eedwig,4kdrr Ldtnana ..... Penbcdaan

kyaBl Tektonik

dan

Volkdik Meqgunakd

JST Perceplon

B!,o B.d or

271

Ferglunaan ModelArnFpadi Jaringan Sdaf Tiruan

"- P?l{t

aplikBi Jaringan N.ural utrtuk Konpresi Zorrl'sr Data 'Itomd si vidodo... ............................,,..,.,,...,,,...,,,....

239

Pe4e6huan Berbasis Ontologi unruk Ped8elolaan asor lnlclclilual padr Perusahaan Teknolosi ldfomasi PeDerapan Skrem Mmalcmen

.rlot: s\l n P?tnia

vatJo)a, st. Hanat..

... ....

793

Pefommsi Pelayman Bisni Peds$en tuatdo)a, S\ba"or Pqanoo S', Ha, tar.. ... .... ... .. .. .. .L-lo'i. Vod.l

ACen Cerd6 untuk Monitoring

--\plik6i Sistem Pakar Mereguoka Jda &tsri S/. g, DiasDsis Pcn'€tit pada Pasien Peny*ir Dalm Cho:tine Fatichoh,

Gdae

Wibiroho, rudli

fre,

Pu||mto

dengm Studi Kasus

..-..

...-

alliar Cr etic Alxarrln in DacMt Siriloit lcces Rachnod, M&anhdd Zoli:, Pattak Sihanbinz.. ................,.............,....,,...

ldi

s.l6i Ttd.llirg

attntur

Salestun Ptuble, denee Algoriha Oendika ahali .. .,... .........-

,^

107

.. ,.

...........-----.. -

315

32t

Pengaruh Stemming Kata Dalam Peningkatan Unjuk Kerja Document Clustering Untuk Dokumen Berbahasa Indonesia 1)

Amir Hamzah1) Jurusan Teknik Informatika, Institut Sains & Teknologi AKPRIND Yogyakarta Jl. Kali Sahak No.28, Komplek Balapan Yogyakarta 55222 Tlp(0274)563029 E-mail : [email protected]

Abstrak Document Clustering banyak diteliti karena peranan pentingnya dalam bidang text-mining dan information retrieval. Dalam teknik clustering berbasis feature kata dengan model ruang vektor selalu muncul problem tingginya dimensi ruang vektor akibat banyaknya kata yang digunakan. Hal ini menyebabkan kinerja clustering turun karena jarak antar titik cenderung bernilai sama. Reduksi dimensi dengan penurunan jumlah kata dapat dilakukan dengan cara stemming. Penelitian ini melakukan kajian tentang pengaruh stemming kata dalam peningkatan kinerja clustering. Tiga pendekatan clustering yang dicobakan adalah pendekatan hierarchi, partisi dan hibrid. Untuk pendekatan hierachi digunakan teknik aglomeratif dengan 5 model similaritas yaitu GroupAverage, CompleteLink, SingleLink, IntraCluster dan ClusterCenter. Untuk pendekatan partisi, yaitu KMeans dan Bisecting K-Mean dan untuk model hibrid digunakan Buckshot clustering. Algoritma stemming yang digunakan adalah algoritma Tala yang menggunakan pendekatan Porter stemmer untuk kata Indonesia, yaitu pendekatan stemming berbasis rule (aturan pemberian imbuhan). Koleksi dokumen yang digunakan adalah 30, 50, 100, 200, 300, 400 dan 500 dokumen berita dengan 3,5,10,11 dan 13 kategori yang telah diketahui sebelumnya. Kriteria kinerja clustering diukur dengan validitas clustering menggunakan nilai F-measure, yaitu nilai yang diturunkan dari Recall dan Precision yang mengukur kemampuan algoritma melakukan klasifikasi secara benar. Hasil penelitian menunjukkan bahwa penggunaan stemming mampu meningkatkan secara signifikan nilai F-measure antara 5% sampai 10%. Kata Kunci: document clustering, algoritma clustering, stemming, validitas clustering

1. PENDAHULUAN Sumber informasi on-line yang berkembang pesat telah menyebabkan ledakan informasi yang menyulitkan navigasi dan temu kembali informasi. Saat ini diperkirakan ada sekitar

8.058.044.651 web-pages terindeks [5], dengan jutaan halaman web bertambah setiap hari dan sebagian besar adalah dokumen teks, yang mencapai 80% total informasi. Membanjirnya informasi teks digital telah mendorong kebutuhan riset untuk elaborasi koleksi teks (text-mining) dan riset untuk optimalisasi mesin pencari informasi (information retrieval system), atau sistem IR. Meningkatnya jumlah bahasa dalam web telah menjadi tantangan baru penelitian sistem IR. Saat ini masih sangat sedikit penelitian dibidang IR dan clustering dokumen yang berbasis bahasa Indonesia [14]. Menurut [3], Indonesia dengan jumlah penduduk diatas dua ratus juta sangat memerlukan penelitian pada dua bidang tersebut, mengingat kebanyakan penelitian yang ada selalu berbasis kata atau phrasa bahasa Inggris. Dalam model ruang vektor dimana koleksi dokumen diwakili oleh matrik kata-dokumen dan sebuah dokumen diwakili oleh sebuah vektor dalam ruang dimensi t , dimana t adalah jumlah feature terindeks dalam koleksi dokumen tersebut umum dijumpai bahwa dimensi t akan sangat tinggi [7]. Dalam dimensi tinggi jarak antar titik akan cenderung bernilai sama [11]. Hal ini akan berakibat algoritma clustering yang bertumpu pada fungsi jarak menghasilkan solusi yang bias. Upaya reduksi dimensi ruang vektor dapat ditempuh dalam dua cara, yaitu pada tahap clustering atau tahap pre-processing. Pada tahap clustering reduksi dimensi ditempuh dengan beberapa pendekatan misalnya projected clustering [1], analisis SVD atau PCA [10]. Tahap pre-processing ditempuh antara lain dengan membuang kata-kata yang frekuensinya terlalu rendah atau frekuensinya terlalu tinggi [12]. Kata yang terlalu tinggi frekuensinya dibuang dengan cara stop-word removal, yaitu membuang kata ‘non-discriminating word’ seperti ‘dan’, ‘ini’,’itu’, ‘dengan’ dan lain-lain. Sedang kata frekuensi rendah dibuang dengan membatasi frekuensi kemunculan kata dalam dokumen dengan suatu treshold tertentu.

PENGARUH STEMMING KATA DALAM PENINGKATAN UNJUK KERJA DOCUMENT CLUSTERING UNTUK DOCUMENT BERBAHASA INDONESIA Amir Hamzah

253

Langkah baku reduksi dimensi dalam tahap pre-processing adalah dengan melakukan stemming kata [16], karena dengan mengembalikan varian kata ke dalam kata dasarnya maka jumlah kata yang ada akan berkurang. Mengingat proses stemming yang berbeda antara kata Indonesia dan kata Inggris, maka diperlukan penyelidikan apakah pemberlakuan stemming kata dalam clustering dokumen bahasa Indonesia memberikan efek dalam memperbaiki kinerja clustering.

antara frekuensi kata dengan kata (diurutkan berdasar frekuensi) dan batas atas serta batas bawah frekuensi yang harus dipotong. Kata dengan frekuansi tinggi dibuang karena biasanya membawa sedikit informasi, sedangkan frekuensi rendah dibuang karena jarang muncul dalam query.

2. LANDASAN TEORI DAN EKSPERIMEN 2.1. Model ruang vektor koleksi dokumen Model ruang vektor untuk koleksi dokumen mengandaikan dokumen sebagai sebuah vektor dalam ruang kata (feature). Klustering dokumen dipandang sebagai pengelompokan vektor berdasarkan suatu fungsi similarity antar dua vektor tersebut. Jika koleksi n buah dokumen dapat diindeks oleh t buah term/feature maka suatu dokumen dapat dipandang sebagai vektor berdimensi t dalam ruang term tersebut. Dengan demikian koleksi dokumen dapat dituliskan sebagai matrik kata-dokumen X, yang dapat ditulis : X = {xij } i= 1,2,..t ; j =1,2,.. n

(1)

xij adalah bobot term i dalam dokumen ke j Proses menyusunan matrik kata-dokumen (sering disebut tahap pre-processing) adalah sebagai berikut: tahap awal adalah pengubahan ekspresi kata ke lower-case dan penghilangan stop-word, seperti artikel atau preposisi misalnya ‘ini’,’itu’,’yang’, ‘yaitu’ dan lain-lain. Penghilangan stop-word ini dapat mengurangi frekuensi feature 30 sampai 40 persen [16]. Proses leksikal yang lain terhadap feature kata adalah proses stemming, yang akan mereduksi semua kata ke dalam akar katanya. Algoritma stemming yang sudah luas diterapkan dalam sistem IR adalah algoritma yang dibangun oleh [15], biasa disebut dengan Porter Stemmer. Algoritma ini telah dimodifikasi ke dalam berbagai bahasa. Untuk meningkatkan kemampuan term sebagai pembeda dokumen pembobotan atas term perlu dilakukan. Pembobotan dasar dilakukan dengan menghitung frekuensi kemunculan term dalam dokumen karena dipercaya bahwa frekuensi kemunculan term merupakan petunjuk sejauh mana term tersebut mewakili isi dokumen. Menurut Luhn [12], kekuatan pembeda terkait dengan frekuensi term (term-frequency, tf), di mana term yang memiliki kekuatan diskriminasi adalah term dengan frekuensi sedang. Gambar 1. menyajikan hubungan

254

Gambar 1. Hubungan frekuensi kata dan kata ter-ranking frekuensi (Luhn, 1958)

Pembobotan Term (term – weighting) Penggunaan hanya frekuensi term dalam dokumen sebagai bobot term tersebut dalam representasi dokumen tidaklah memadai. Hal ini karena bias dapat muncul dari faktor lain, misalnya banyaknya dokumen yang memuat term tersebut, atau faktor panjang dokumen dimana term tersebut muncul [16]. Faktor panjang dokumen dalam koleksi berakibat seolah-olah term yang sering muncul pada dokumen panjang lebih penting dari pada term yang kurang sering muncul pada dokumen pendek. Untuk itu normalisasi frekuensi term terhadap panjang dokumen diperlukan. Secara umum bentuk pembobotan akhir term dapat dirangkumkan sebagai berikut [6] : wij=Lij.Gi.Nj

(2)

di mana wij adalah akhir bobot total term i dalam dokumen ke j, Lij adalah bobot lokal term i dalam dokumen ke j yang mengukur seberapa penting peranan term i dalam dokumen j , Gi bobot global term i yang mengukur seberapa penting term i dalam seluruh koleksi dokumen, dan Nj adalah faktor normalisasi untuk dokumen ke j untuk menghilangkan pengaruh bias karena panjang dokumen. Berbagai variasi pembobotan lokal, global dan normalisasi yang dapat diterapkan pada vektor dokumen dirangkumkan dalam [6]. Kombinasi terbaik yang sering digunakan adalah fij untuk bobot

N

lokal Lij (disebut TF), dan log   sebagai bobot  ni  global Gi (disebut IDF) dan pembobotan normal sehingga panjang vektor adalah satu, yaitu :


Nj=

1

(3)

 G L  m

2

i 0

i

ij

Sehingga bentuk akhir disebut sebagai pembobotan TF-IDF ternormalisasi, yaitu :

wij=

N (ln( f ij )  1).log   ni      (ln( f ij )  1).log N    n    i  

(4)

2

di mana wij adalah akhir bobot total term i dalam dokumen ke j, fij adalah frekuensi kata ke-i dalam dokumen ke-j, N cacah dokumen dalam koleksi, ni cacah dokumen mengandung term i.

Fungsi similaritas antar vektor dokumen Kesamaan antara dokumen Di dengan dokumen Dj dapat diukur dengan fungsi similaritas ( mengukur kesamaan) atau fungsi jarak (mengukura ketidaksamaan). Beberapa fungsi similaritas dan fungsi jarak yang dapat dijumpai antara lain adalah Dice, Jaccard, Overlap, asimmetric, Minowski distance, Euclidean distance, Pearson Correlation dan Cosine. Menurut [18] untuk tujuan clustering dokumen jarak fungsi yang palking baik adalah fungsi similariutas Cosine, berikut : t

D D Cosine-sim(Di,Dj)=

i

i 1

t

j

(5)

t

 (D )  (D ) 2

i 1

i

2

j

i 1

Selanjutnya jika vektor dokumen Di dan vektor dokumen Dj masing-masing adalah ternormalisasi menjadi vektor satuan, sehingga ||Di||2=1 dan ||Dj||2=1 maka fungsi similaruitas cosine menjadi perkalian antar vektor, yaitu : t

Cosine-sim(Di,Dj) =

D D i 1

i

j

(6)

2.2. Stemming Kata Stemming memiliki peran mendasar dalam teknik pemrosesan bahasa alami [4]. Ia digunakan untuk mentransformasi varian-varian kata ke bentuk kata dasar yang sama dengan menerapkan aturanaturan morphologi. Untuk bahasa inggris algoritma stemming yang dikembangkan oleh Porter [15] digunakan luas dalam clustering dokumen dan sistem IR. Stemming kata Indonesia menghadapi persoalan variasi imbuhan (affix) yang lebih

kompleks dibandingkan dengan bahasa Inggris [5]. Sebagai contoh untuk menghilangkan imbuhan (affix) yang dapat berupa awalan (prefixes), akhiran (suffixes) dan sisipan (infixes) atau kombinasi (confixes) untuk memperoleh akar kata harus dilakukan dengan pertimbangan yang rumit menyangkut urutannya. Untuk kasus sederhana seperti kata “minuman” memiliki kata dasar “minum” dan akhiran “-an”, persoalan dapat dianalogikan seperti penghilangan akhiran “s” atau akhiran “ed” dalam bahasa inggris. Penghilangan imbuhan untuk beberapa kasus berikut tidak dijumpai analoginya dalam bahasa Inggris: -

“pemerintah”, diturunkan dari kata dasar “perintah” mendapat sisipan “em” “buku-buku”, bentuk jamak dari buku “pemberdayaannyapun” memiliki kata dasar “daya” mendapat awalan “pe-” dan “ber-” dan akhiran “-an”, “-nya” dan “-pun”

Dalam bahasa Indonesia imbuhan dapat dikelompokkan menjadi beberapa kelompok [13], yaitu: 1. Akhiran infleksi (inflection suffixes), yaitu akhiran yang tidak mengubah akar kata, misalnya “duduk” dapat ditambah akhiran “-lah” menjadi “duduklah”. Infleksi lebih jauh dapat dibagi dua: a) Partikel, yaitu: “-lah”, “-kah” atau “-pun” b) Kata ganti milik (possesive pronoun), yaitu: “ku”, “-mu” dan “-nya” Partikel dan possesive dapat muncul bersamaan, dan jika itu terjadi maka possesive akan mendahului partikel, misalnya dalam kata “rumahnyapun” atau “mobilmulah”. 2. Akhiran derivasi (derivation suffixes), yaitu akhiran yang diterapkan langsung pada akar kata membentuk kata baru. Hanya ada satu akhiran derifasi untuk satu kata. Kata “lapor” dapat ditambah dengan akhiran derifasi “-kan” menjadi “laporkan”, dan ditambah dengan akhiran infleksi ”lah” menjadi “laporkanlah” 3. Awalan derivasi (derivation prefixes), awalan yang dapat diterapkan langsung pada akar kata, misalnya “perawat” atau dapat diterapkan pada kata yang sudah berawalan seperti kata “pemberangkatan”. Teknik Stemming Berbagai teknik stemming bahasa Indonesia berupaya membuang imbuhan yang mungkin ada pada akar kata. Jika seluruh kemungkinan imbuhan dituliskan, suatu kata akan memiliki kemungkinan berimbuhan dengan rumus: [DP + [DP + [DP]]] Root [ [DS] +[PP] + [P]] dengan DP = Derivation Prefixes DS = Derivation Suffix PP = Possesive Pronoun P = Particel.

(7)


255

Root = akar kata Teknik stemming diimplementasikan dengan dua cara, yaitu berbasis kamus (dictionary based) dan berbasis aturan (rule based). Beberapa algoritma stemming yang telah dirancang adalah algoritma Nazief [13], algoritma Arifin dan Setiono [2] serta algoritma Tala [19]. Dikarenakan imbuhan yang berupa sisipan (infixes) pada praktisnya lebih jarang muncul daripada awalan atau akhiran maka hampir semua algoritma stemming yang ada mengabaikan keberadaan imbuhan berupa sisipan. Algoritma Nazief dan Adriani Algoritma Nazief dan Adriani memiliki tiga komponen, yaitu : pengelompokan imbuhan, urutan penggunaan aturan (rule) dan kamus (dictionary). Kamus akan dicek setiap penerapan aturan stemming berhasil diidentifikasi, dan apabila stemming berhasil menemukan akar kata algoritma mengambalikan kata dalam kamus dan algoritma berhenti. Langkah-langkah stemming algoritma Nazief dan Adriani: 1) Kata yang akan distemm dicari dalam kamus. Jika ditemukan maka dianggap kata tersebut adalah akar kata sehingga kata tersebut direturn dan algoritma stop di sini. 2) Hilangkan imbuhan infleksi (“-lah”, “-kah”,”ku”,”-mu” dan “-nya”). Jika ini berhasil dan jika akhiran adalah partikel (“-lah” atau “kah”) langkah ini dilanjutkan dengan menghilangkan imbuahan possesive (“-ku”, “mu” dan “-nya”). 3) Hilangkan imbuhan derivasi (“-i” atau “-an”). Jika berhasil, lanjutkan ke langkah 4, jika tidak lakukan hal berikut ini: a) Jika “-an” dibuang, dan huruf terakhir dari kata adalah “-k”, maka “-k” juga dibuang dan pergi ke langkah 4. b) Penghilangan akhiran “-i”, “-an” dan “kan” dibatalkan. 4) Penghilangan awalan dengan berbagai variasi (lihat Asian [5]). 5) Jika semua langkah telah ditempuh dan tidak berhasil, maka kembalikan kata asli yang belum distemm. Algoritma Arifin dan Setiono Algoritma Arifin dan Setiono [2], meskipun menggunakan kamus sebagaimana algoritma Nazief dan Adriani, mengajukan proses stemming yang lebih sederhana. Secara singkat algoritma Arifin dan Setiono menghilangkan seluruh kemungkinan awalan dan kemudian seluruh kemungkinan akhiran. Setiap kali awalan atau

256

akhiran dihilangkan program mengecek ke dalam kamus. Algoritma Arifin dan Setiono mengasumsikan bahwa setiap kata memiliki dua awalan dan tiga akhiran, yaitu : [AW1] + [AW2] + KD + [AK3] + [AK2] +[AK1] (8) dimana AW = awalan , KD = kata dasar dan AK = akhiran Langkah-langkah stemming algoritma Arifin dan Setiono: 1) Lakukan pemeriksaan setiap kata, siapkan variabel p1,p2,s1,s2, 2) Pemotangan dilakukan secara berurut, yaitu: a) Awalan I, hasil disimpan pada p1 b) Awalan II, hasil disimpan pada p2 c) Akhiran I, hasil disimpan dalam s1 d) Akhiran II, hasil disimpan dalam s2 e) Akhiran III, hasil disimpan dalam s3 Setiap tahap pemotongan hasil dicek dalam kamus, jika ada dalam kamus algoritma selesai, jika tidak ada proses dilanjutnya ke pemotongan berikutnya. 3) Jika sampai pada langkah 2.e. belum ditemukan dalam kamus, maka dilakukan proses kombinasi. Kata dasar yang dihasilkan dikombinasikan dengan imbuhan-imbuhan dalam 12 kombinasi, yaitu: a) Kata Dasar b) Kata Dasar + AK III c) Kata Dasar + AK III + AK II d) Kata Dasar + AK III + AK II + AK I e) AW I + AW II + Kata Dasar f) AW I + AW II + Kata Dasar + AK III g) AW I + AW II + Kata Dasar + AK III + AK II h) AW I + AW II + Kata Dasar + AK III + AKII + AK I i) AW II + Kata Dasar j) AW II + Kata Dasar + AK III k) AW II + Kata Dasar + AK III + AK II l) AW II + Kata Dasar + AK III + AK II + AK I Kelebihan algoritma ini dibandingkan dengan algoritma Nazief adalah dalam hal mengatasi overstemming, yaitu jika sebagian kata dasar distemm karena dainggap awalan atau akhiran. Sebagai contoh kata “diselamatkan” memiliki akar kata “selamat”. Setelah langkah pertama awalan I “di” dibuang kata yang dihasilkan adalah “selamatkan”. Karena kata tidak ada dalam kamus proses dilanjutkan dengan menghilangkan awalan II “se” menghasilkan “lamatkan” yang merupakan kekeliruan karena “se” bukan awalan tetapi bagian dari akar kata. Setelah penghilangan awalan selesai proses dilanjutkan dengan penghilangan akhiran


“kan” menghasilkan “lamat”. Karena “lamat” tidak ada dalam kamus jadi langkah 3 ditempuh dengan mencoba memasang kembali berbagai kombinasi imbuhan, dan setelah memasang kembali awalan “se” menghasilkan “selamat” ternyata ada dalam kamus, maka proses stemming berhasil.

4. Berdasarkan aturan tertentu dipilih dua kemungkinan: a). Hilangkan awalan 2 diikuti hilangkan akhiran b). Hilangkan akhiran dilanjutkan hilangkan awalan 2 5. Kembalikan hasil stemming

Algoritma Tala Algoritma stemming dari Tala [19] menggunakan informasi aturan morphologi tanpa menggunakan bantuan kamus dan murni berbasis aturan (purely rule-based stemmer). Algoritma Tala merupakan pengembangan algoritma Porter yang diaplikasikan untuk Bahasa Indonesia. Argumentasi yang dibangun seperti dikemukakan oleh [15] bahwa untuk kepentingan peningkatan kinerja retrieval dari sistem IR penggunaan kamus akan menurunkan kinerja stemmer. Seperti algoritma Nazief dan algoritma Arifin, algoritma Tala juga menggunakan analisis morphologi yang pada prinsipnya membagi imbuhan menjadi dua jenis, yaitu imbuhan infleksi dan imbuhan derivasi. Akhiran dibedakan menjadi akhiran infleksi dan akhiran derivasi, sedangkan awalan semua bersifat derivasi.

1.

2.

Akhiran infleksi terdiri dari dua kelompok : akhiran : “-lah”, “-kah”, “-pun” , disebut juga partikel. Tidak merubah makna hanya memperkuat atau bermakna menyangatkan. Akhiran : “-ku:, “-mu”, “-nya”, bermakna milik (possesive). Akhiran derivasi yaitu : “-i”, “-an” dan “-kan” Tabel 1. Kombinasi awalan akhiran yang dilarang

Awalan bedikemesete-

Akhiran yang tidak diperbolehkan -i -an -i, -kan -an -i, -kan -an

Jika awalan dan akhiran ditambahkan dengan perkecualian (seperti tabel 1) kemungkinan formula adalah seperti yang diajukan oleh Arifin, yaitu : dua buah awalan dan tiga buah akhiran sebagai berikut : [awalanl] + [awalan2] + KataDasar + [akhiran] +[ possesive] + [partikel] (9) Adapun langkah-langkah stemming dengan algoritma Tala adalah : 1. Hilangkan partikel 2. Hilangkan possesive prononoun 3. Hilangkan awalan 1

2.2. Clustering Dokumen Clustering didefinisikan sebagai upaya pengelompokan data ke dalam kluster sehingga datadata didalam kluster yang sama memiliki lebih kesamaan dibandingkan dengan data-data pada kluster yang berbeda [9]. Metode Hierarchi Agglomerative untuk Clustering dokumen Berikut ini algoritma dasar klustering secara aglomerative, dengan menggunakan notasi cˆ = himpunan cluster, n = cacah objek dan c = cacah cluster yang akan dibuat: Andaikan cˆ =n dan himpunan objek C={xi }, i=1,2,…n 2. Jika | cˆ | < c stop 3. Temukan dua kluster terdekat, sebut Ci dan Cj 4. gabungkan Ci dan Cj, hapus Cj dan kurangi | cˆ | dengan satu 5. Pergi ke langkah 2 1.

Tahap paling krusial yaitu langkah 3, ditentukan dengan beberapa ukuran similaritas antar kluster antara lain, misalnya: Single Link, Complete Link, UPGMA [9]. Berikut ini ringkasan masingmasing teknik :  Single Link (SL) : jarak terbaik dua kluster diwakili oleh jarak terdekat (similaritas tertinggi) dari dua titik dari dua kluster.  Complete Link(CL) : jarak terbaik dua kluster diwakili oleh jarak terjauh (similaritas terendah) dari dua titik dari dua kluster.  Unweighted Pair Group Method Average similarity (UPGMA): Similaritas dua kluster diukur dengan rata-rata hitung similaritas antar seluruh pasangan titik antara kedua kluster.  Intra-Cluster Similarity (IST) : Dua kluster digabungkan jika selisih similaritas dua cluster gabungan dengan similaritas masing-masing kluster adalah maksimal.  Centorid- Similarity Technique(CIST) : Jarak antar kluster ditentukan dengan jarak antar pusat kluster.


257

K-Means Clustering Algoritma K-means clustering merupakan algortima iteratif dengan meminimalkan jumlah kuadrat error antara vektor objek dengan pusat kluster terdekatnya [9], yaitu : k

  x  m j 1 x

2 j

(10)

j

di mana mj adalah pusat kluster (mean vector) dalam kluster ke j. Selanjutnya algoritma K-means standard dapat dituliskan sebagai : 1. 2.

3. 4.

Ambil K objek sebagai seed dari K pusat kluster Untuk semua objek: cari kluster dengan jarak terdekat, dan tetapkan objek masuk dalam kluster tersebut. Hitung ulang pusat kluster dengan rata-rata objek dalam kluster tersebut Hitung fungsi kriteria dan lakukan evaluasi. Jika fungsi kriteria berubah cukup kecil algoritma berhenti.

Bisecting K-Means Clustering Metode Bisecting K-means [17] mencoba menggabungkan pendekatan partitional dengan divisive hierarchi, yaitu mula-mula seluruh dokumen dibagi dua dengan cara K-means (bisecting-step). Selanjutnya cara itu dikenakan pada tiap-tiap kluster sampai diperoleh K buah kluster. Berikut ini algoritmanya : 1. 2. 3.

4.

Ambil satu kluster untuk displit Tentukan 2 sub kluster dengan K-means (bisecting step) Ulangi langkah 2 sebanyak ITER kali, dan ambil hasil terbaik yang memiliki overal similarity terbesar. Ulangi langkah 2 dan 3 sampai didapatkan K buah kluster.

Overall similarity pada langkah 3 ditentukan sebagai rata-rata similaritas setiap titik terhadap pusat klsuternya masing-masing.

2.3 Validitas Clustering (Cluster validity) Untuk mengevaluasi hasil dari suatu algoritma clustering diusulkan konsep yang disebut dengan validitas clustering (cluster validity). Validitas yang dapat digunakan antar lain Confusion Matrix yaitu matriks yang disusun berdasarkan berapa banyak objek yang diklasifikasikan dengan benar oleh proses clustering. Dua pengukuran kualitas clustering yang dapat diturunkan dari confusion matrix yang umum digunakan untuk document clsutering adalah F-measure (persamaan (11)) dan entropy (E-measure) (persamaan 12) :

2 PR PR 2 PR E-measure = 1 PR F-measure =

(11) (12)

2.4. Eksperimen Bahan Bahan eksperimen berupa test-collection dokumen teks yang diambil dari koleksi [3] dikemas menjadi 6 koleksi yang masing-masing telah dikluster secara. Statistik koleksi tes tersaji dalam Tabel 2. Tabel 2. Koleksi Dokumen Untuk Pengujian algoritma clustering

Colec Name

 doc

 clus

Clust Size

uniq Word

avg word/ doc

T30 T50 T100 T200 T300 T400 T500

50 50 100 200 300 400 500

3 5 10 10 10 11 13

Sama Sama Sama Sama Beda Beda Beda

1.536

262

2.860 4.385 6.652 8.472 10.153 11.637

382 368 372 373 388 385

Setiap koleksi tertdiri dari sejumlah dokumen dengan format setiap dokumen seperti gambar 2.

Buckshot Clustering Algoritma Buckshot menggunakan pendekatan hierarchie agglomerative untuk mendapatkan k buah vektor sebagai pusat kluster awal. Langkah Buckshot mula-mula mengambil sampel acak sebesar kn buah dokumen, yang dikluster dengan cluster subroutine, yaitu prosedur hierarchie agglomerative untuk mendapatkan k buah kluster. Selanjutnya dengan partisi awal yang didapat dari Buckshot proses refinement dilakukan sebagaimana dalam K-means clustering.

258


3. HASIL DAN PEMBAHASAN news035-html mayjen syafrie samsuddin akan jadi kapuspen tni jakarta media mantan pangdam jaya mayjen syafrie samsuddin akan menjadi kapuspen tni menggantikan marsekal muda graito husodo menurut informasi yang diperoleh antara jakarta kamis syafrie samsuddin menjadi kapuspen tni dan serah terima jabatan akan dilakukan pada akhir februari 2002 namun kebenaran informasi tersebut hingga kini belum dapat dikonfirmasikan ke kapuspen tni m-1 Gambar 2. Format koleksi dokumen untuk Tes

Alat Alat Penelitian berupa seperangkat komputer dan perangkat lunak, yaitu: a) Perangkat keras : Processor Intel Pentium IV 2.8 GHz , RAM 1 GB , dan Hard Disk 80 GB b) Perangkat lunak : MS-WINDOWS, MATLAB for WINDOW, J2SDK Prosedur eksperimen Tahapan eksperimen dimulai dengan preprocessing dokumen dengan ekstrak kata, penyusunan matrik kata-dokumen, proses stemming pada kata dan penyusunan ulang matrik katadokumen dan pembobotan ternormalisasi. Program dirancang dengan coding bahasa Java. Selanjutnya dengan metode-metode clustering yang akan diujikan, yaitu : adalah metode hierarchi aglomerative (strategi similaritas: Single Link, Complete Link, Group Average, centroid similarity, intra cluster similarity), metode partitional (K-means, bisecting k-means, Buckshot). Program dirancang dengan script MATLAB. Dengan melakukan clustering pada dua koleksi, yaitu koleksi dengan kata asal dan koleksi pada kata yang di-stemm hasil clustering dibandingkan. Kriteria pembanding yang digunakan adalah nilai F-measure sebagai kriteria unjuk kerja clustering dan waktu pre-process dan waktu clustering. Pengujian statistik dikakukan dengan uji t dan uji wilcoxon sign-rank test untuk pengamatan berpasangan.

Efek Stemming pada penurunan kata Pada koleksi yang diujikan jumlah kata untuk tiap-tiap frekuensi (yaitu frekuensi kemunculan 1 sampai 5 dan diatas 5) dicacah. Pada 7 koleksi yang diuji terlihat bahwa stemming menurunkan frekuensi kata pada setiap frekuensi untuk setiap koleksi. Tabel 3. Penurunan kata karena Stemming

Frek kata freq=1 freq=2 freq=3 freq=4 freq=5 freq>5 total Turun Frek kata freq=1 freq=2 freq=3 freq=4 freq=5 freq>5 total Turun Frek kata freq=1 freq=2 freq=3 freq=4 freq=5 freq>5 total Turun Frek kata freq=1 freq=2 freq=3 freq=4 freq=5 freq>5 total Turun

term 917 271 124 67 35 122 1536

term 2215 739 386 259 138 648 4385

term 3720 1474 761 450 297 1770 8472

term 4851 1971 1001 648 449 2717 11637

30 dok stemm 1080 253 74 34 16 29 1486 3.26% 100 dok stemm 1912 523 262 167 105 445 3414 22.14% 300 dok stemm 3088 1052 506 305 200 1213 6364 24.88% 500 dok stemm 4080 1413 707 428 270 1805 8703 25.21%

term 1578 488 223 143 101 327 2860

term 3085 1128 583 352 259 1245 6652

term 4361 1728 885 556 386 2237 10153

50 dok stemm 1422 318 184 109 68 190 2291 19.9% 200 dok stemm 2578 782 396 247 154 879 5036 24.29% 400 dok stemm 3644 1238 591 377 244 1520 7614 25.01%


259

Dari Tabel 3 dan rankuman Tabel 4 Terlihat bahwa semakin banyak jumlah dokumen maka semakin tinggi prosentase penurunan kata. Untuk koleksi 400 dan 500 dokumen penurunan kata setelah distemm dapat mencapai 25% (lihat Gambar 3). Penurunan jumlah kata ini akan menurunkan dimensi matrik kata dokumen yang berakibat komputasi clustering akan semakin efisien. Tabel 4. Penurunan prosentase Term karena Stemming

dok % turu n

30

50

100

200

300

400

500

3.26

19.9

22.1 4

24.2 9

24.8 8

25.0 1

25.2 1

Gambar 3. Prosentase Penurunan kata karena stemming

Efek Stemming pada perbaikan kinerja clustering dokumen Untuk membandingkan kinerja clustering dokumen dengan fitur kata yang distemming, maka pada tiap koleksi diambil beberapa tingkatan fitur berdasarkan varian fitur. Diambil 100%, 20%, 15%, 10% dan 5% dari total kata. Pada setiap level dilakukan clustering dengan fitur asal dan fitur distemm. Hasilnya dibandingkan melalui nilai F yang diuji statistik. Contoh untuk koleksi 50 dok hasil perbandingan adalah sebagai berikut : Tabel 4.

Perubahan nilai F hasil clustering akibat stemming (untuk koleksi 50 dokumen)

Metode

Word

hcaUPGMA hcaCST hcaIST hcaSL hcaCL spherekm bisectkm buckshot

0.960 0.698 0.940 0.506 0.960 0.837 0.980 0.960

260

100% Term Stemmed Naik/ Word Turun 0.980 2.12% 0.980 40.39% 0.961 2.26% 0.718 41.90% 0.980 2.12% 0.553 -33.99% 1.000 2.05% 0.939 -2.21% Rata-rata 6.83%

Metode

Word


0.960 0.804 0.960 0.483 0.960 0.815 0.919 0.980

Metode

Word


0.980 0.980 0.960 0.515 0.980 0.633 0.939 0.980

Metode

Word


0.980 0.980 0.961 0.494 0.980 0.641 0.980 1.000

Metode

Word


0.960 0.960 0.919 0.677 0.960 0.787 1.000 0.980

20% Term Stemmed Word 0.980 0.980 0.941 0.862 0.980 0.980 1.000 0.980 Rata-rata 15% Term Stemmed Word 0.980 0.980 0.941 0.862 0.980 0.980 1.000 0.980 Rata-rata 10% Term Stemmed Word 0.980 0.980 0.849 0.669 0.980 0.751 1.000 0.980 Rata-rata 5% Term Stemmed Word 0.960 0.960 0.941 0.846 0.846 0.803 1.000 0.980 Rata-rata

Naik/ Turun 2.12% 21.88% -1.98% 78.46% 2.12% 20.22% 8.86% 0.00% 16.46% Naik/ Turun 0.00% 0.00% -1.99% 67.43% 0.00% 54.79% 6.54% 0.00% 15.85% Naik/ Turun 0.00% 0.00% -11.68% 35.29% 0.00% 17.12% 2.05% -2.01% 5.10% Naik/ Turun 0.00% 0.00% 2.42% 24.97% -11.91% 2.06% 0.00% 0.00% 2.19%

Jika seluruh fitur digabungkan maka rerata kenaikan nilai F akibat stemming untuk koleksi 50 dokumen adalah 6.90% yang diuji scara statistik merupakan kenaikan yang signifikan. Untuk hampir seluruh koleksi dokumen yang lain perbandingan nilai F-measure antara clustering dengan feature di-stemm dengan feature


kata asal menunjukkan perbedaan yang signifikan. Berikut ini rangkuman perbandingan untuk koleksi dokumen yang lain. Tabel 5. Uji statistik kenaikan F koleksi tes KOLEKSI Rata2 F NonStem Rata2 F Stemming % Kenaikan Uji Statistik

50 dok

100 dok

200 dok

300 dok

0.87

0.84

0.76

0.70

0.93

0.87

0.80

0.75

6.90%

3.45% Non Sig

5.26%

7.14%

Sig

Sig

Sig

(tabel 5 : lanjutan)

KOLEKSI Rata2 F NonStem Rata2 F Stemming % Kenaikan Uji Statistik

400 dok

500 dok 0.64

0.66

Terlihat dari Grafik Gambar 4 bahwa feature optimal didapat pada seleksi feature 15%. Hal ini sesuai dengan penelitian Steinbach [17] tentang prosentase feature terbaik berdasar varians feature, yaitu 15%.

0.68

Aspek waktu komputasi

0.68 6.25% 3.02% Non Sig

Sig

Terlihat dari tabel 5 bahwa pada semua koleksi, fitur di-stemm telah menaikkan nilai F hasil clustering sekitar 3% sampai 7%. Uji statistik menunjukkan bahwa 4 koleksi telah menunjukkan kenaikan yang signifikan secara statistik.

Kenaikan F-measure optimal Pada setiap koleksi dokumen dan setiap prosentase feature terpakai sebagai clustering, terlihat bahwa hasil hampir selalu menghasilkan kenaikan pada F (perkecualian pada koleksi T100 untuk feature 20% dan feature 5%). Tabel 6 berikut adalah rangkumannya. Tabel 6. Prosentase Kenaikan F berdasar Prosentase Feature

Kolek si T100 T200 T300 T400 T500 Rata2

Gambar 4. Perubahan F karena stemming

Prosentase Feature Terpakai (%) 100 20 15 10 5 5.60 -3.19 14.29 11.03 -0.65 1.78 7.81 7.72 4.44 9.95 10.44 9.75 15.42 12.61 9.58 2.68 4.68 6.36 3.34 7.92 4.70 6.94 5.21 4.38 5.73 5.04 5.20 9.80 7.16 6.50

Dari tabel 6 terlihat bahwa pada feature 15% prosentase kenaikan nilai F sebesar 9.8% merupakan kenaikan tertinggi, yang terjadi pada hampir semua koleksi yang dites.

Jika stemming menunjukkan kenaikan dalamperbaikan unjuk kerja clustering, tentu dimaklumi bahwa ada trade-off berupa waktu preprocessing yang lebih lama, yaitu untuk proses stemming dan penyusunan matriknya. Tabel 7 berikut ranghkuman waktu pre-processing dan waktu clustering (total untuk 5 algoritma hierrachical). Tabel 7 . Waktu preprocessing dan clustering dua metode

Tahap ekstrak term stemm susunMat ssnMatStem Tot Preprocss Clustering Total Tahap ekstrak term stemm susunMat ssnMatStem Tot Preprocess Clustering Total

T100 NnStm Stemm 0.328 0.28 0.19 0.687 1.844 1.015 2.314 3.984 3.187

T200 NnStm Stemm 0.453 0.453 0.25 1.516 4.09 1.969 4.793 17.812 15.454

4.999 5.501 T300 NnStm Stem 0.56 0.56 0.25 2.344 7.391

19.781 20.247 T400 NnStm Stem 1.125 1.125 0.26 3.547 11.734

2.904 49.344

8.201 43.844

4.672 95.422

52.248

52.045

100.09

13.119 94.328 107.44 7


261

Tabel 8 . Perbandingan Waktu clustering (detik)

Koleksi NonStem Stemm

T100 4.999 5.501

T200 19.781 20.247

T300 52.248 52.045

T300 100.09 107.15

Gambar 5 . Grafik Perbandingan Waktu clustering (detik)

Terlihat dari tabel 8 bahwa waktu pre-processing yang lebih lama untuk stemming dapat dikompensasi dengan waktu clustering yang lebih cepat dalam feature stemming sehingga secara keseluruhan waktu hampir sam (lihat Gambar 5).

4. KESIMPULAN Beberapa kesimpulan yang dapat ditarik dari penelitian ini adalah :  Penerapan operasi stemming kata dapat menurunkan dimensi ruang vektor sampai 25% dari dimensi semula  Penerapan stemming kata memperbaiki kinerja clustering, ditunjukkan dengan naiknya nilai Fmeasure secara signifikan  Waktu yang digunakan untuk clustering dangan feature distemm lebih pendek dari waktu clustering dengan kata semula  Preprocess untuk feature distemm memerlukan waktu lebih lama  Secara total waktu preproses dan waktu clustering tidak berbeda jauh antara fitur dengan kata non stemm dan kata di stemm

262

DAFTAR PUSTAKA [1] Aggarwal,C. C. and P.S. Yu, 2000, Finding Generalized Projected Cluster in High Dimensional Spaces, Proc.ACM SIGMOD Conf., 2000 [2] Arifin, A. Z. dan A. N. Setiono, (2002), Classification of Event News Documents in Indonesian LanguageUsing Single Pass Clustering Algorithm, in `Proceedings of the Seminar on Intelligent Technology and its Applications (SITIA)', Teknik Elektro, Sepuluh Nopember Institute of Technology,Surabaya, Indonesia [3] Asian, J., H. E. Williams, and S. M. M. Tahaghoghi, 2004, Tesbed for Indonesian Text Retrieval, 9th Australian Document Computing Symposiom, Melbourne December, 13 2004 [4] Asian, J., H. E. Williams, and S. M. M. Tahaghoghi, 2005, Stemming Indonesian, 28th Australian Computer Science Conference (ACS2005). [5] Bifet, A. , C. Castillo, P. A. Chirita and I. Weber, 2005, An Analysis of Factors Used in Search Engine Ranking. airweb.cse.lehigh.edu/2005/bifet.pdf [6] Chisholm, E. and T. G. Kolda, 1999, New Term Weighting Formula for the Vector Space Method in Information Retrieval, Research Report, Computer Science and Mathematics Division, Oak Ridge National Library, Oak Ridge, TN 3781-6367, March 1999. [7] Dhillon, S. I., J. Fan, and Y. Guan, 2001, Efficient Clustering of Very Large Document Collection, www.citeseer.ist.psu.edu/dhillon01.html [8] Dhillon, I., J. Kogan, and C. Nicholas, 2002, Feature Selection and Document Clustering, www.csee.umbc.edu/cadip/2002Symposim/kogh an.pdf [9] Jain, A.K. and R. C. Dubes, 1988, Algorithms for Clustering Data, Prentice-Hall [10] Gao, J. and J. Zhang, 2003, Clustered SVD Strategies in Latent Semantic Indexing, Technical Report No. 382–03, Department of Computer Science, University of Kentucky, Lexington, KY,2003 [11] Hinneburg, A. and D.K. Keim, 1999, Optimal Grid-Clustering: Towards Breaking the Curse of Dimensionality in High-Dimensional Clustering”, Proceeding of 25th VLDB Conference, Edinburg, Scotland, 1999 [12] Luhn, H.P. (1958), The Automatic Creation of Literature Abstracts. IBM Journal of Research and Development, 2:159-165 [13] Nazief, B. A. A. dan M. Adriani, 1996, Confixstripping: Approach to Stemming Algorithm for Bahasa Indonesia. Internal publication, Faculty of Computer Science, University of Indonesia, Depok, Jakarta.


[14] Nazief,

B., 2000, Development of Computational Linguistic Research: a Challenge for Indonesia”, Computer Science Center, University of Indonesia

[15] Porter, M. , 1980, An Algorithm for Suffix Stripping, Program 13(3), 130-137. [16] Rijsbergen, C. J.,1979, Information Retrieval,

Information Retrieval Group, University of Glasgow , UK [17] Steinbach, M., G. Karypis, and V. Kumar , 2000, A Comparison of Document Clustering Techniques, KDD Workshop on Text Mining, www.citeseer.ist.psu.edu/steincah00comparison .html [18] Strehl, A., J. Ghosh, and R. Mooney, 2000, Impact of Similarity Measures on Web-Page Clustering, Proceeding of the Workshop of Artificial Intelligent for Web Search, 17 th National Conference on Artificial Intelligence, July 2000. [19] Tala, F. Z., 2004, A Study of Stemming Effect on Information Retrieval in Bahasa Indonesia, Master Thesis, Universiteit van Amsterdam, The Netherlands


263

Web Mining

Recommend Documents