ISSN:'1410-5829
Jurnal Teknologi ACAN,trFTIA [SEd[ Terdkcditaq tNo. 56 DIKTI/KEP/2005)
Vol. l2 No.l Agustus 2007
""I
-l
JURNAL TEKNOLOGI Pemimpir
0..
U
mu
rvPemlnpli
Redaks i
f
wahyu PuNanto, MS|E Pret AdiS@sanb, M.Sc. Ph.D
P6l L wah[di 0B
Sudisedyawai sLJ Reh.lyo wadoyo, M sc ,Ph D
k
PdslJlno Eto Pambudi, [4.T.
r
Risma Ade
ph0
ia Simajunlak M.'I
06. iudi Seryean, Ms
suwairo Rahado, s.s Ellyawai Selyo
,M
$
., M Kom
AdiilaM,
ST., M
$ H,A( DAN
IGWA! AAN R€OAKS
Lehbaga Penelitian nsutur sa ns STeknolog AKPRTND
Reda]Giig'dakiasl€hyaigldakmem4Jh'
Jl.(aishakNo 23 Kompleks Ba apai Yogyaratu 55222 Te p. {0r4) 563029,544504, Fe (0274) 5633.47 Emai academ a Glaloathnd ad d hno rr\vw aklind a.
imea/pesyamlai
ISSN:14't0-5829
dasrah.
d
t
ki s,
reigadaki peebarra ssian
mmpe$a ibah*ad
be omulas deruan
DAFIAR ISI
rai Daya Tqa Fasa d Dislribus densan unt Pembaigkir yang Asuns Bud' Murano, t Made Ai NQtlha Anarisls A
V
Idak Terpusar
srud komparas Aqoriha Ieks aerbahasa lndonesia A it H.hzah , Adhl s1santa, F Saesianta Jaz Eko lstyanto
C/rsrerirg ookumen
Gerakan Ta^ah Di KaEnssambunq. Penyebab dan Anrisipas pences.hainya
Ap kas Sislem
cer.las
Th€ rnvestgaton
o€
i lheweslTrmor
Kebtakaf Manalemen Resko Sstem
Deposil or Radioisorope Eremenr with n The Mmins Subst.nce
TengqaE Imur Banhabneus Pasanska, Prayata Ktfiani Btotoptspto watuyo rs and Nusa
s
Pengatuh Vskosilas terhadap DislrbuslTekanan Radiatpada AtiEn danlara Dua
E6uariPerayanan kuar,Ese€en.y Banr _^ o surabaya Eko Nrtmdnta Lanl)p Tn:Daana t@ry std)ona Pe^ssrnaan Multistags Fttet Adapr,ye wreror untuk Meninskarkan Kua tas
crE
Ftn utanininsrun wahyu Ad Pnjano
- D'grdrH.s' oopp.as oe1sa" V.rodd d,o,d Marhemalioar fi,lodering for Emuson Lquid Membrane
Peigaruh Ralio Asam ot,.atlorbirorpada produk solbibn Monooteal
meta u
i;:f;.8:,*'*"PembasahanKataisTe.hadapKonversiso]daamReaklor Mahrutl. F.
Hunda
c
nawan
Arelis s Pdbaike sistem Penlanahan pada Kaki rMenara saturan TEnsms Tegansan Tinggt1s0 Kv Eantu-semanu Joqlakana
JURNAL TEKNOLOGI ACADEMIA ISTA Vol. 12. No.1. Agustus 2007
ISSN: 1410-5829
STUDI KOMPARASI ALGORITMA HIERARCHICAL DAN PARTITIONAL UNTUK CLUSTERING DOKUMEN TEKS BERBAHASA INDONESIA 1)
2)
2)
Amir Hamzah , Adhi Susanto , F.Soesianto , dan Jazy Eko Istyanto
3)
ABSTRACT Text document clustering is a technique that has been intensively studied because of its important role in text-mining and information retrieval. In the vector space model it is typically known two main clustering approaches,i.e. hierachical algorithm and partitional algorithm. The hierarchical algorithm produces deterministic result known as a dendogram, but its weakness is high complexity in time and memory. On the other hand, partitiaonal algorithm has linear time and memory complexity although its clustering result is not independent with its initial cluster. The aim of this researh was doing experimental study to compare the performance of several techniques of hierarchical algorithms and partitional algorithms in text document writen in Bahasa Indonesia. The five similarity techniques i.e. UPGMA, CSI, IST,SL and CL are chosen for hierarchical, whereas K-Means, Bisecting K-Mean and buckshot are chosen for partitonal. The document collections from 200 to 800 Indonesian text news that has been categorized manually was used to test these algorithms by using F-measure as clustering performance. This value was derived from Recall and Precision and can be used to measure the performance of the algorithms to correctly classify the collections. Results showed that Bisecting K-Mean as a variant of partitional algorithm has a performance as good as the two best hierarchical techniques,i.e. UPGMA and CL with much lower time complexity. Keywords: document clustering, hierarchical, partitional, clustering validation INTISARI Clustering dokumen merupakan teknik yang intensif dipelajari karena peran pentingnya dalam text mining dan sistem temu kembali informasi. Dalam model ruang vektor dikenal dua pendekatan clustering, yaitu algoritma hierarchical dan algoritma partitional. Algoritma hierarchical menghasilkan clustering yang deterministik berupa sebuah dendodram dan tidak tergantung urutan dokumen tetapi memiliki kelemahan berupa kompleksitas memori dan waktu yang relatif besar. Algoritma partitional meskipun memiliki kompleksitas memori dan waktu yang lebih sederhana tetapi hasil clusteringnya bersifat probabilistik dan dipengaruhi oleh urutan dokumen. Penelitian ini bertujuan melakukan studi unjuk kerja dua pendekatan algoritma tersebut untuk clustering dokumen teks berbahasa Indonesia. Algoritma hierarchical yang dikaji menggunakan lima teknik yaitu UPGMA, CST, IST, SL dan CL, sedangkan untuk algoritma partitional diambil metode KMeans , Bisecting K-Means dan Buckshot. Koleksi dokumen yang digunakan adalah dokumen teks berita bahasa Indonesia 200 sampai 800 dokumen. Parameter yang gunakan untuk membandingkan kinerja algoritma adalah F-measure , nilai yang diturunkan dari recall dan precision. Hasil penelitian menunjukkan bahwa Bisecting K-Mean memiliki kinerja yang sebanding dengan dua teknik terbaik hierarchical, UPGMA dan CL dengan kompleksitas waktu yang jauh lebih kecil. Kata kunci : clustering dokumen, hierarchical, partitional, validitas clustering
PENDAHULUAN
clustering untuk meningkatkan efektifitas pencarian (Tombros, 2002) atau mengemas hasil pencarian sehingga dapat disajikan lebih efektif (Zamir,1999; Osinki, 2004). Dalam dunia web saat ini diperkirakan ada lebih dari 16 milyar dokumen terindeks (www.google.com, 2007), dengan jutaan halaman web bertambah setiap hari dan sebagian besar adalah dokumen teks, yang mencapai 80% total informasi (Bifet, 2005).
Pemanfaatan teknologi digital dan jaringan komputer telah menyebabkan ledakan informasi berkembang eksponensial. Hal ini menyebabkan kesulitan dalam menemukan kembali informasi yang cenderung tidak efektif, baik dalam pencarian maupun penyajian informasinya. Beberapa penelitian mengatasi masalah ini dengan memanfaatkan teknik _____________________________________________________________ 1)
Jurusan Teknik Informatika, FTI, IST AKPRIND, Yogyakarta,
[email protected] Jurusan Teknik Elektro, Fak. Teknik, UGM, Yogyakarta 3) Jurusan Fisika, Fak. MIPA, UGM, Yogyakarta 2)
11
JURNAL TEKNOLOGI ACADEMIA ISTA Vol. 12. No.1. Agustus 2007
ISSN: 1410-5829
Membanjirnya informasi teks digital digital ini 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 (Nazief, 2000). Menurut Asian(2004), Indonesia dengan jumlah penduduk diatas dua ratus juta sangat memerlukan penelitian pada dua bidang tersebut, mengingat kebanyakan penelitian yang ada selalu berbasis bahasa Inggris. Penerapan clustering dokumen untuk meningkatkan kinerja sistem IR telah lama diterapkan (Rijbergen, 1979. Model clustering dokumen yang sering diterapkan untuk meningkatkan efektivitas pencarian query dalam koleksi dokumen adalah model hierarchical, baik aglomerative maupun divisive (Tombros,2002). Model ini memiliki karakteristik tidak tergantung pada urutan dokumen dan menghasilkan clustering yang pasti. Kelemahan model ini adalah kompleksitas waktu dan memory yang tinggi (Jain,1988). Model lain yang belum banyak diterapkan dalam sistem IR adalah partitional. Menurut Kural(1999), koleksi dokumen tidak selalu instrinsik berstruktur hierarchi sehingga pendekatan ini tidak selalu sesuai. Pendekatan partitional memiliki keuntungan kompleksitas waktu komputasi dan penggunaan memory yang linear, meskipun memiliki kelemahan pada hasil clustering yang kurang pasti karena tergantung pada urutan dokumen dan inisialisasi awal clustering. Untuk dokumen berbahasa inggris perbandingan clustering antara beberapa metode hierarchical dan partitional telah dilakukan oleh Steinbach et.al. (2000) dimana hasilnya adalah meode Bisecting K-Maen memiliki kinerja yang sebanding dengan metode hierarchical UPGMA. Namun hasil penelitian ini sangat mungkin tidak sama jika diterapkan pada dokumen bahasa Indonesia mengingat ada proses stemming pada tahap per-processing yang menggunakan algoritma berbeda anyara bahasa inggris dengan bahasa Indonesia. Penelitian ini bertujuan melakukan kajian ekperimental untuk membandingkan kinerja algoritma hierarchical dan algoritma partitional dalam melakukan clustering dokumen teks untuk dokumen berbahasa Indonesia. Hasil yang diharapkan adalah berupa rekomendasi untuk pemilihan algoritma yang paling efisien ditinjau dari waktu komputasi dan penggunaan
memori dengan tidak mengorbankan kinerja clustering. 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 katadokumen 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 (Rijsbergen,1979). 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 Porter (1987), biasa disebut dengan Porter Stemmer. Algoritma ini telah dimodifikasi ke dalam berbagai bahasa. Modifikasi untuk bahasa Indonesia dilakukan oleh Tala(2004). Review detail tentang stemmer bahasa Indonesia telah dilakukan oleh Asian(2005), sedangkan efek stemming pada clustering dokumen bahasa Indonesia dilakuan oleh Hamzah (2006). 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 (1958), kekuatan pembeda terkait dengan frekuensi term (term-frequency, tf), di mana term yang memiliki kekuatan diskriminasi adalah term dengan frekuensi sedang. Untuk itu pemotongan frekuensi bawah biasanya ditempuh dengan memberikan treshold tertentu untuk minimal jumlah dokumen yang memuat term tersebut. Pemotongan term dengan 12
JURNAL TEKNOLOGI ACADEMIA ISTA Vol. 12. No.1. Agustus 2007
ISSN: 1410-5829
frekuensi tinggi dilakukan dengan membuang stop-word. 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 (Rijsbergen, 1979). 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 (Chisholm et.al.,1999) : wij=Lij.Gi.Nj
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 Strehl et.al.(2000) untuk tujuan clustering dokumen jarak fungsi yang paling baik adalah fungsi similariutas Cosine, berikut : t
Cosine-sim(Di,Dj)=
i
t
Cosine-sim(Di,Dj) =
m=
j
(6)
1 nk
nk
D i 1
i
(7)
dengan nk adalah cacah dokumen dalam kluster ke-k. Seleksi feature kata
ij
Setelah pemotongan frekuensi atas kata dengan dengan stop-word filtering dan frekeunsi bawah kata dengan memberi treshold (batas) minimal kata, jumlah kata yang terindeks untuk matrik kata-dokumen biasanya masih relatif besar. Untuk itu seleksi dapat ditempuh dengan memilih kata yang memiliki variansi frekeunsi keumnculan besar (Dhillon et.al., 2002; Hamzah, 2006). Untuk teks bahasa Indonesia seleksi dengan cara ini dapat menurunkan feature kata sampai 15% dari jumlah kata semula dengan kinerja clustering tidak menurun (Hamzah, 2006). Rumusan variansi tiap kata dapat dituliskan sebagai persamaan () berikut :
(4) 2
N 1).log i 1 ni 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 dan t adalah cacah total term.
(log( f
i
Suatu formula yang penting dalam clustering dokumen adalah representasi pusat kluster. Menurut (Rijsbergen, 1979) representasi pusat kluster dapat diwakili oleh dokumen atau beberapa dokumen yang berada di tengah. Namun formula yang paling sering adalah ratarata vektor dokumen (m) seperti rumusan (7) berikut :
(3)
N (log( f ij 1).log ni t
D D i 1
Sehingga bentuk akhir disebut sebagai pembobotan TF-IDF ternormalisasi, yaitu :
wij=
i 1
2
j
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 similaritas cosine menjadi perkalian antar vektor, yaitu :
2
i 0
i
i 1
dan pembobotan normal sehingga panjang vektor adalah satu, yaitu :
G L
(5)
t
2
(2)
1
j
(D ) (D )
N log sebagai bobot global Gi (disebut IDF) ni
m
i
i 1
t
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 Chisholm et.al. (1999). Kombinasi terbaik yang sering digunakan adalah fij untuk bobot lokal Lij (disebut TF), dan
Nj =
D D
ij
13
JURNAL TEKNOLOGI ACADEMIA ISTA Vol. 12. No.1. Agustus 2007
ni
qi(t)= f j j 1
2
1 ni f j ni j 1
ISSN: 1410-5829
Complete Link(CL) : jarak terbaik dua kluster diwakili oleh jarak terjauh (similaritas terendah) dari dua titik dari dua kluster.
2
(8)
Secara teknis masukan bagi algoritma hierarchical clustering adalah matriks similaritas antar dokumen yang berukuran NxN. Iterasi yang setiap tahapnya melakukan penggabungan kluster dilakukan dengan melakukan update pada matrik similaritas. Hal inilah yang menyebabkan algoritma ini memiliki 2 kompleksitas waktu dan ruang O(N ).
dengan qi adalah variansi jika frekuensi minimal kata muncul dalam analisis adalah i (i=0,1,2,...). Clustering Dokumen Clustering didefinisikan sebagai upaya pengelompokan data ke dalam kluster sehingga data-data didalam kluster yang sama memiliki lebih kesamaan dibandingkan dengan data-data pada kluster yang berbeda (Jain,1988). Dari penerapan clustering yang luas pada bidang sains dan teknik salah satu penerapannya adalah untuk clustering dokumen.
K-Means Clustering Algoritma K-means clustering merupakan algortima iteratif dengan meminimalkan jumlah kuadrat error antara vektor objek dengan pusat kluster terdekatnya (Jain, 1988), yaitu :
Metode Hierarchi Agglomerative untuk Clustering dokumen
x K
SSE=
nj
j 1 i 1
Berikut ini algoritma dasar klustering secara aglomerative, dengan menggunakan notasi cˆ = himpunan cluster, N = cacah objek dan c = cacah cluster yang akan dibuat: [1]. Andaikan cˆ =N ; himpunan objek C={xi }, i=1,2,…n [2]. Jika | cˆ | < c stop [3]. Temukan dua kluster terdekat : Ci dan Cj [4]. gabungkan Ci dan Cj, hapus Cj dan kurangi | cˆ | dengan satu [5]. 5. Pergi ke langkah 2
i
mj
2
(9)
di mana mj adalah pusat kluster (mean vector) dalam kluster ke j. Selanjutnya algoritma Kmeans standard dapat dituliskan sebagai : [1]. Ambil K objek sebagai seed dari K pusat kluster [2]. Untuk semua objek: cari kluster dengan jarak terdekat, dan tetapkan objek masuk dalam kluster tersebut. [3]. Hitung ulang pusat kluster dengan rata-rata objek dalam kluster tersebut [4]. Hitung fungsi kriteria dan lakukan evaluasi. Jika fungsi kriteria berubah cukup kecil algoritma berhenti.
Tahap paling krusial yaitu langkah 3, ditentukan dengan beberapa ukuran similaritas antar kluster antara lain, misalnya : UPGMA, CST, IST, Single Link dan Complete Link (Jain,1988). Berikut ini ringkasan masingmasing teknik tersebut:
Fungsi kriteria yang dimaksud dalam langkah [4] dapat diambil SSE persamaan (9).
Bisecting K-Means Clustering
Unweighted Pair Group Method Average similarity (UPGMA): Similaritas dua kluster diukur dengan rata-rata hitung similaritas antar seluruh pasangan titik antara kedua kluster.
Metode Bisecting K-means Steinbach et.al. (2000) mencoba menggabungkan pendekatan partitional dengan divisive hierarchical, yaitu mula-mula seluruh dokumen dibagi dua dengan cara K-means (bisectingstep). Selanjutnya cara itu dikenakan pada suatu kluster yang dipilih dengan cara tertentu sampai diperoleh K buah kluster. Berikut ini algoritmanya :
Centorid- Similarity Technique(CIST) : Jarak antar kluster ditentukan dengan jarak antar pusat kluster. Intra-Cluster Similarity (IST) : Dua kluster digabungkan jika selisih similaritas dua cluster gabungan dengan similaritas masingmasing kluster adalah maksimal.
[1]. Ambil satu kluster untuk displit dengan Kmeans (bisecting step) [2]. Ulangi langkah [1] sebanyak ITER kali, dan ambil hasil terbaik yang memiliki overal similarity terbesar.
Single Link (SL) : jarak terbaik dua kluster diwakili oleh jarak terdekat (similaritas tertinggi) dari dua titik dari dua kluster. 14
JURNAL TEKNOLOGI ACADEMIA ISTA Vol. 12. No.1. Agustus 2007 [3]. Ulangi langkah [1] dan didapatkan K buah kluster.
[2]
ISSN: 1410-5829
sampai
Tabel 1. Koleksi Dokumen Untuk Pengujian algoritma clustering
Overall similarity pada langkah [2] ditentukan sebagai rata-rata similaritas setiap titik terhadap pusat klusternya masing-masing. Sedangkan pemilihan kluster pada langkah satu pada setiap iterasinya dapat digunakan cara memilih kluster dengan ukuran cacah objek terbesar atau memilih kluster yang memiliki variance terbesar. Buckshot Clustering Algoritma Buckshot menggunakan pendekatan hierarchie agglomerative untuk mendapatkan k buah vektor sebagai pusat kluster awal (Cutting et.al.,1992). Langkah Buckshot mula-mula mengambil sampel acak
clus
Clust Size
uniqW ord
K100 K200 K300 K400 K500 K600 K700 K800
100 200 300 400 500 500 500 800
10 10 10 11 13 13 13 14
Sama Sama Beda Beda Beda Beda Beda Beda
4.385 6.652 8.472 10.153 11.637 13.433 14.802 15.752
avg word/ doc 368 372 373 388 385 388 385 410
news035-html eriksson akan ijinkan tim piala dunia inggris mencicipi bir london media tim piala dunia inggris akan diijinkan untuk sekali-sekali mencicipi bir maupun anggur dalam final di korea selatan dan jepang tahun ini satu gelas minuman tak akan membuat seseorang menjadi pemain yang lebih baik atau buruk pelatih sven goran eriksson di london
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 (Halkidi et.al.,2001) Dua pengukuran kualitas clustering yang dapat diturunkan dari confusion matrix yang umum digunakan untuk document clustering adalah F-measure (persamaan (10) dan entropy (E-measure) (persamaan 11) :
2 PR PR 2 PR E-measure = 1 PR
doc
Setiap koleksi terdiri dari sejumlah dokumen dengan format tiap dokumen seperti gambar 1.
kn buah dokumen, yang dikluster sebesar 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.
F-measure =
Colec Name
Gambar 1. Format koleksi dokumen untuk Tes Alat penelitian berupa seperangkat komputer dengan perangkat keras Processor Intel Pentium IV 2.8 GHz , RAM 1 GB , dan Hard Disk 80 GB dan perangkat lunak MSWINDOWS, MATLAB for WINDOW, J2SDK dan SPSS for WINDOWS Tahapan eksperimen dimulai dengan preprocessing dokumen dengan ekstrak kata dengan menggunakan treshold minimal disesuaikan dengan koleksi, yaitu 3 untuk K100, K200, K300 dan K400, dan berturut-turut 4,5,6 dan 7 untuk koleksi K500, K600, K700 dan K800. Perlakukan stemming terhadap feature kata dilakukan untuk meningkatkan kinerja clusterin g dan menurunkan jumlah feature kata terindeks. Proses stemming dilakukan dengan algoritma Tala (2004). Penyusunan matrik katadokumen dengan pembobotan ternormalisasi seperti rumus pada persamaan (5). Program dirancang dengan coding bahasa Java. Selanjutnya metode-metode clustering yang akan diujikan, yaitu : UPGMA, CST, IS, SL dan CL dan metode partitional (K-means,
(10) (11)
Eksperimen yang dilakukan Bahan eksperimen berupa test-collection dokumen teks yang diambil dari koleksi (Asian, 2004) dikemas menjadi 6 koleksi yang masingmasing telah dikluster secara manual. Statistik koleksi tes tersaji dalam Tabel 2.
15
JURNAL TEKNOLOGI ACADEMIA ISTA Vol. 12. No.1. Agustus 2007
ISSN: 1410-5829
bisecting k-means, Buckshot) dibuat kodingnya menggunakan script MATLAB. Hasil evaluasi kinerja clustering yang diwakili oleh ukuran F-measure untuk setiap algoritmanya kemudian dianalisis. Perbandingan kinerja juga dilakukan dengan melihat kompleksitas waktu clustering. Pengujian statistik dikakukan dengan one way anova test untuk pengamatan berpasangan dengan paket statistik SPSS.
dokumen selanjutnya berdasarkan kata yang telah dibatasi frekuensinya, yaitu sebanyak kata seperti pada kolom terakhir Tabel 2 Kinerja algoritma hierarchical Untuk melihat kinerja algoritma hierarchical dalam clustering disajikan hasil rangkuman nilai F-measure dari clustering dengan lagoritma tersebut untuk seluruh koleksi yang ada ( Tabel 3 ). Terlihat dari rata-rata nilai F-measure bahwa dua metode yang terbaik adalah metode UPGMA dan CL. Untuk koleksi K100 dan K200 yang terbaik adalah CL, sedangkan untuk koleksi K300 sampai K800 adalah metode UPGMA. Grafik rata-rata kinerja clustering disajikan dalam Gambar 2. Secara keseluruhan kinerja algoritma akan menurun dengan semakin banyaknya dokumen yang dikluster. Metode hierarchi akan sangat peka terhadap pertambahan dokumen karena kompleksitas waktu komputasinya kuadratis terhadap jumlah dokumen. Dari lima metode komputasi similaritas metode Single Link menunjukkan kinerja yang paling buruk meskipun waktu komputasi ralatif sama dengan algoritma yang lain.
PEMBAHASAN Penyunan matrik kata-dokumen Penyusunan matrik-kata dokumen dengan melakukan ekstrak kata dengan batas minimal disesuaikan dengan besar koleksi dan stop-word filtering dengan menggunakan stoplist dari Tala(2004) yang berupa 764 daftar kata. Hasil statistik kata tersaji dalam Tabel 2. Sesuai dengan teori frekuensi kata dari Luhn(1958) bahwa distribusi kata dalam koleksi akan didominasi kata dengan frekuensi rendah, Tabel 2 memperlihatkan bahwa hampir pada seluruh koleksi 75% lebih kata dalam koleksi adalah memiliki frekuensi kemunculan maksimal 5 kali. Penyusunan matrik kata-
Tabel 2. Statistik ekstraksi feature kata berdasar minimum frekuensi kemunculan
Koleksi
kata
kata f=1
kata f=2
kata f=3
kata f=4
kata f=5
kata f>5
kata f <=5
% kata f<=5
min f kata
kata f>min
K100
4.385
2.215
739
386
259
138
648
3.737
85%
3
1.048
K200
6.652
3.073
1.126
583
352
258
1.242
5.392
81%
3
2.852
K300
8.472
3.720
1.474
761
450
297
1.770
6.702
79%
3
2.517
K400
10.153
4.361
1.728
885
556
386
2.237
7.916
78%
3
3.179
K500
11.637
4.851
1.971
1.001
648
449
2.717
8.920
77%
4
3.166
K600
13.433
5.626
2.143
1.130
781
518
3.235
10.198
76%
5
3.235
K700
14.802
6.185
2.302
1.216
869
581
3.649
11.153
75%
6
3.232
K800
15.752
6.497
2.464
1.292
886
638
3.975
11.777
75%
7
3.172
16
JURNAL TEKNOLOGI ACADEMIA ISTA Vol. 12. No.1. Agustus 2007
ISSN: 1410-5829
Tabel 3. Nilai F-measure algoritma hierarchical untuk seluruh koleksi dan rata-ratanya Metode
K100
K200
K300
K400
K500
K600
K700
K800
rerata
UPGMA
0,9600
0,9236
0,9278
0,8543
0,8083
0,6167
0,6695
0,6261
0,7983
CST
0,6843
0,5004
0,2558
0,3040
0,1747
0,2194
0,2171
0,1870
0,3178
IST
0,9252
0,7193
0,7494
0,5846
0,8029
0,8130
0,6456
0,4256
0,6857
SL
0,5596
0,2792
0,1870
0,1847
0,1649
0,2181
0,2115
0,1870
0,2490
CL
0,9694
0,9453
0,8553
0,7842
0,5215
0,6021
0,6523
0,5320
0,7577
Catatan : cetak tebal = nilai terbesar
Tabel 4. Nilai Rata-rata F-measure algoritma partitional untuk seluruh koleksi dan rata-ratanya K10 Metode
0
K-Mean BSC-KM
rerat K200
K300
K400
K500
K600
K700
K800
0,7095
0,7342
0,6890
0,6197
0,4196
0,5558
0,4523
0,5269
0,5884
0,8761
0,8967
0,8711
0,8739
0,7869
0,6498
0,6012
0,6200
0,7720
Buckshot 0,8612 0,7427 0,7061 Catatan : cetak tebal = nilai terbesar
0,6546
0,5447
0,5625
0,4952
0,4135
0,6178
1200,0 800,0
UPGM A CST
600,0
IST
1000,0
Waktu (detik)
0,80 0,60 0,40 0,20
400,0
SL
200,0 CL 800
700
CL
600
SL
500
IST
Metode
400
CST
100
UPGMA
300
0,0
0,00
200
F-measure
1,00
a
Jum lah Dokum en
Gambar 2. F-measure rata-rata hierarchical
Gambar 3. Waktu komputasi metode hierarchical
Kinerja algoritma Partitional
Perbandingan waktu komputasi dari ke lima metode hierarchi dapat disajikan dalam tabel berikut. Terlihat dari gamabr /tabel bahwa mulai koleksi K500 terjadi lonjakan waktu komputasi hampir pada semua metode kecuali metode CST. Metode CST mengalami lonjakan waktu yang relatif kecil dibandingkan 4 metode yang lain. Hal ini berkaitan dengan metode perhitungan jarak antar cluster pada CST, dimana kesamaan dua kluster dihitung sebagai kesamaan antar pusat klusternya. Pada metode ini tidak diperlukan perhitungan similaritas antar pasangan data dari dua kluster sebagaimana 4 metode yang lain.
Karena algoritma partitional tidak menghasilkan hasil clustering yang bersifat pasti maka nilai F-measure sebagai ukuran kinerja diperoleh dari nilai rata-rata 5 kali eksekusi ( 5 run ) program. Hasil rangkuman kinerja clustering metode partitional disajikan seperti Tabel 4. Secara konsisten terlihat bahwa algoritma partitional yang memiliki kinerja terbaik adalah Bisecting K-Mean. Sedangkan urutan kedua adalah Buckshot dan yang paling buruk adalak K-Mean murni (Gambar 4). Disini terlihat bahwa algoritma K-Mean tanpa 17
JURNAL TEKNOLOGI ACADEMIA ISTA Vol. 12. No.1. Agustus 2007
ISSN: 1410-5829
dimensionality, yaitu nilai jarak 2 objek dalam dimensi tinggi cenderung bernilai sama (Hinneburg,1999).
modifikasi menghasilkan clusteirng yang sangat buruk meskipun waktu komputasinya paling cepat. Sesuai dengan karakteristik algortima partitonal yang bersifat linear terhadap jumlah dokumen algoritma ini tidak bermasalah besar dengan berjumlahnya dokumen yang dikluster. Gambar 5 menunjukkan grafik yang landai untuk koleksi dari 100 sampai 800 jika dibandingkan dengan grafik waktu komputasi pada hierarchical pada gambar 3 .
F-measure
1,00 0,80 0,60 0,40 0,20
M
H BS
BK
KM
L C
SL
T IS
ST C
U
PG M A
0,00
1,0000
Metode
F-measure
0,8000 0,6000
Gambar 6. Perbandingan Kinerja clustering
0,4000
Penggunaan feature kata yang lebih rendah pada jumlah yang tepat dapat memperbaiki kinerja. Sebagai contoh untuk koleksi K400 yang terdiri dari 400 dokumen telah dipilih feature dengan menggunakan metode analisis variance frekeunsi kemunculan kata seperti rumus (8) kemudian dipilih 20%,15%,10% dan 5% kata dengan variansi terbesar. Hasil clustering dapat disajikan seperti dalam Tabel 5 berikut .
0,2000 K-Mean1
Bisct-KM
Bucksht
Metode
8,00 7,00 6,00 5,00 4,00 3,00 2,00 1,00 -
Tabel 5. Efek seleksi feature pada F-measure K-Mean
Persentase penggunaan feature kata Metode 100% 20% 15% 10% 0,854 UPGMA 0,804 0,822 0,810 0,597 CST 0,304 0,375 0,401 0,865 IST 0,585 0,642 0,716 0,238 SL 0,185 0,238 0,204 0,905 CL 0,784 0,891 0,878 0,746 K-MEA 0,620 0,695 0,660 0,880 BSC-K 0,874 0,870 0,856 0,803 BSHOT 0,655 0,758 0,751 0,692 rerata 0,608 0,659 0,691 Catatan: printbold = terbesar tiap metode/rerata
BisectKM
700
600
500
400
300
200
Bucksh ot
100
Waktu clustering (detik)
Gambar 4. Kinerja rata-rata metode partitional
Cacah dokumen
Gambar 5. Waktu clustering partitional
Perbandingan kinerja algoritma hierarchical dan partitional.
5% 0,800 0,583 0,768 0,235 0,845 0,622 0,838 0,654 0,668
Pengujian statistik dengan one-way anova dengan persentase feature sebagai treatment dan metode sebagai ulangan menunjukkan bahwa rerata perbedaan setiap persentase feature kata tidak berbeda signifikan (lihat analisis SPSS Tabel 6). Hal ini menunjukkan bahwa dengan melakukan seleksi feature kinerja clustering tidak menjadi turun, bahkan cenderung naik meskipun kenaikan tidak signifikan. Dari Tabel 5 tyerlihat rerata Fmeasure tertinggi adalah pada penggunaan 15%, yaitu sedikit diatas penggunaan kata 10%. Pada koleksi-koleksi yang lain, jika seleksi feature dilakukan hasilnya kurang lebih sama dengan hasil pada koleksi K400, misalnya pada
Untuk penggunaan 100% term Jika kinerja clustering hiararchical dan patitional dibandingkan kinerjanya melalui F-measure, terlihat bahwa kinerja partitional Bisect K-Mean masih lebih baik dari kinerja algoritma hierarchical metode CST danm Single Link (SL) dan sedikit dibawah metode UPGMA dan CL yang merupakan metode terbaik dari hierarchical (Gambar 6). Penggunaan 100% term memiliki kinerja yang cenderung kurang baik karena tingginya dimensi umumnya mempengaruhi kualitas perhitungan karena efek curse of
18
JURNAL TEKNOLOGI ACADEMIA ISTA Vol. 12. No.1. Agustus 2007
ISSN: 1410-5829
koleksi K300 (Tabel 7) dan koleksi K500(Tabel pada prosentase 5%-10%. 8), kinerja clustering terbaik justru kebanyakan Tabel 6. Anova untuk efek seleksi feature terhadap F-measure pada koleksi 400 dok Sum of Squares ,042 1,848 1,890
Between Groups Within Groups Total
Mean Square ,011 ,053
df 4 35 39
F ,201
Sig. ,936
F-measure
1,000 0,800 0,600 0,400 0,200
O T H BS
BS
C
-K
A
L
KM E
C
SL
IS T
ST C
U
PG
M A
-
100% 20% 15% 10% 5%
Metode
Gambar 7. Efek seleksi feature kata pada kinerja clustering untuk seluruh metode
Catatan: printbold = terbesar tiap metode/rerata
Tabel 7. Efek seleksi Feature pada F-measure Untuk koleksi 300 dokumen
Dari gambar 7 juga terlihat bahwa feature yang tidak 100% justru memperlihatkan kinerja clustering yang lebih baik dari feature 100%, misalnya pada metode CST, CL dan Buckshot. Pada gambar tersebut juga terlihat kinerja Bisecting K-Mean sebanding dengan kinerja UPGMA dan CL.
Persentase penggunaan feature kata Metode 100% 20% 15% 10% 5% 0,841 UPGMA 0,028 0,780 0,783 0,777 CST 0,056 0,527 0,597 0,682 0,674 0,890 IST 0,049 0,758 0,877 0,848 0,187 SL 0,087 0,254 0,186 0,185 CL 0,055 0,834 0,842 0,903 0,778 K-MEA 0,089 0,774 0,634 0,538 0,773 BSC-K 0,071 0,956 0,877 0,977 0,908 0,889 BSHOT 0,006 0,700 0,753 0,761 0,726 rerata 0,055 0,722 0,687 0,708 Catatan: printbold = terbesar tiap metode/rerata
KESIMPULAN Beberapa kesimpulan yang dapat ditarik dari penelitian ini adalah : Kinerja algoritma clustering hierarchical yang terbaik adalah metode UPGMA dan Complet Link.
Tabel 8. Efek seleksi Feature pada F-measure Untuk koleksi 500 dokumen Metode UPGMA CST IST SL CL K-MEA BSC-K BSHOT rerata
Kinerja algoritma partitional yang terbaik adalah metode Bisecting K-Means
Persentase penggunaan feature kata 100% 20% 15% 10% 5% 0,808 0,804 0,803 0,801 0,820 0,175 0,662 0,662 0,789 0,733 0,803 0,933 0,920 0,953 0,950 0,165 0,211 0,282 0,421 0,169 0,522 0,831 0,890 0,826 0,833 0,420 0,458 0,782 0,520 0,575 0,787 0,773 0,802 0,851 0,822 0,545 0,464 0,548 0,676 0,602 0,528 0,642 0,711 0,730 0,688
Metode bisecting K-Means jika dibandingkan dengan kinerja dua metode terbaik dari algoritma hierchical menunjukkan hasil yang tidak kalah, terutama jika menggunakan seleksi feature kata terlebih dahulu, akan tetapi memiliki kelebihan berupa kompleksitas waktu dan memori yang jauh lebih kecil.
19
JURNAL TEKNOLOGI ACADEMIA ISTA Vol. 12. No.1. Agustus 2007
ISSN: 1410-5829
Waktu clustering algoritma hierarchicel seluruh metode jauh lebih besar dengan algoritma partitional. Perbedaan waktu ini semakin mencolok jika jumlah koleksi dokumen semakin besar.
Curse of Dimensionality in HighDimensional Clustering”, Proceeding of th 25 VLDB Conference, Edinburg, Scotland. Jain, A.K. and R. C. Dubes, 1988, Algorithms for Clustering Data, Prentice-Hall Luhn, H.P. ,1958, The Automatic Creation of Literature Abstracts. IBM Journal of Research and Development, 2:159-165 Nazief, B., 2000, Development of Computational Linguistic Research: a Challenge for Indonesia”, Computer Science Center, University of Indonesia
Algoritma partitioanal Bisecting K-Mean memiliki kelebihan jika dokumen dalam koleksi cenderung membesar. Seleksi kata akan memperbaiki kinerja clustering dan rata-rata pada 10 sampai 15% memberikan hasil yang lebih baik dari pada menggunakan 100% kata.
Porter, M. , 1980, An Algorithm for Suffix Stripping, Program 13(3), 130-137.
Rijsbergen, C. J.,1979, Information Retrieval, Information Retrieval Group, University of Glasgow , UK Steinbach, M., G. Karypis, and V. Kumar , 2000, A Comparison of Document Clustering Techniques, KDD Workshop on Text Mining, www.citeseer.ist.psu.edu/steincah00comp arison.html Strehl, A., J. Ghosh, and R. Mooney, 2000, Impact of Similarity Measures on WebPage Clustering, Proceeding of the Workshop of Artificial Intelligent for Web th Search, 17 National Conference on Artificial Intelligence, July 2000. Tala, F. Z., 2004, A Study of Stemming Effect on Information Retrieval in Bahasa Indonesia, Master Thesis, Universiteit van Amsterdam, The Netherlands Zamir, O.E., 1999, Clustering Web Document : A Phrase-Based Method for Grouping Search Engine Result, PhD. Dissertation, University of Washington.
DAFTAR PUSTAKA Asian, J., H. E. Williams, and S. M. M. Tahaghoghi, 2004, Tesbed for Indonesian Text Retrieval, 9th Australian Document Computing Symposiom, Melbourne December, 13. Asian, J., H. E. Williams, and S. M. M. Tahaghoghi, 2005, Stemming Indonesian, 28th Australian Computer Science Conference (ACS2005). 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 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 37816367, March 1999. Cutting, D. R., D. R. Karger, J. O. Pederson, and J. W. Tukey,1992, Scatter/Gather:A Cluster-based Approach to Browsing Large Document Collection, Procedding th 15 Annual Int 7ACM SIGIR Conference on R&D in IR, June 1992. Dhillon, I., J. Kogan, and C. Nicholas, 2002, Feature Selection and Document Clustering, www.csee.umbc.edu/cadip/2002Symposi m/koghan.pdf Halkidi, M., Y. Batistakis, and M. Vazirgiannis, 2001, On Clustering Validation Techniques, Journal of Intelligent Information System17:2/3, 107-145 Hamzah, A,2006, Pengaruh Stemming Kata Dalam Peningkatan Unjuk Kerja Document Clustering Untuk Dokumen Berbahasa Indonesia , Proseding Seminar Nasional Riset Teknologi Informasi, AKAKOM, yogyakarta. Hinneburg, A. and D.K. Keim, 1999, Optimal Grid-Clustering: Towards Breaking the 20
