INTEGRASI PEMBOBOTAN TF-IDF PADA METODE K-MEANS UNTUK CLUSTERING DOKUMEN TEKS

Prosiding Seminar Nasional Manajemen Teknologi XV Program Studi MMT-ITS, Surabaya 4 Pebruari 2012

INTEGRASI PEMBOBOTAN TF-IDF PADA METODE K-MEANS UNTUK CLUSTERING DOKUMEN TEKS Deddy Wijaya Suliantoro 1, *), Irya Wisnubhadra 2) dan Ernawati 3) 1) Magister Teknik Informatika, Universitas Atma Jaya Yogyakarta Gedung Bonaventura Kampus III, Jl. Babarsari 43, Yogyakarta 55281 Telp : 0274-487711 ext 3208, 3212 e-mail: [email protected] 2) Magister Teknik Informatika, Universitas Atma Jaya Yogyakarta 3) Magister Teknik Informatika, Universitas Atma Jaya Yogyakarta ABSTRAK Pada era teknologi informasi seperti saat ini, dokumen teks, berita, dan jurnal-jurnal sudah cenderung tersimpan dalam format digital karena mudah dan cepat dalam penyimpanan. Terlalu banyaknya dokumen teks yang tersimpan dalam komputer membuat pencarian informasi menjadi sulit. Kesulitan dalam pencarian informasi yang sesuai dengan kebutuhan seringkali menjadi penghambat proses pembelajaran. Pengelompokan data (clustering) menjadi salah satu solusi untuk mengorganisasi dokumen-dokumen teks digital yang berjumlah besar. Metode k-Means clustering, dipadukan dengan pembobotan TF-IDF yang diimplementasikan ke dalam sebuah aplikasi pengelompokan dokumen dapat melakukan proses clustering dokumen teks secara otomatis sehingga menghemat waktu untuk mengelompokkan dokumen secara manual. Hasil proses clustering dari aplikasi pengelompokan dokumen ini menunjukkan tingkat presisi yang tinggi dalam mengelompokkan dokumen-dokumen berdasarkan isi dokumen tersebut sehingga diyakini mampu membantu proses pencarian informasi dari data yang terlalu banyak. Kata kunci: clustering, k-Means, TF-IDF, dokumen teks

PENDAHULUAN Dengan banyaknya dokumen teks seperti jurnal, buku, dan berita yang sudah tersimpan secara digital, muncul permasalahan dimana informasi yang tadinya tersedia dengan baik menjadi kabur/hilang karena terlalu banyak dokumen/berkas yang tersimpan dalam media penyimpanan digital. Imbasnya, proses mencari informasi tertentu yang dibutuhkan dari berkas-berkas tersebut menjadi makin sulit dan lama. Masalah lain akan terjadi ketika setiap dokumen tersebut ingin dikategorikan ke dalam kelas-kelas tertentu, karena harus dilihat, dibaca, dan dipahami isi tiap dokumen dalam korpus, barulah bisa ditentukan kelas-kelas bagi dokumen dan membagi dokumen dalam kelas tersebut. Sebuah kajian ilmu yang bernama Information Retrieval (IR) memunculkan beberapa metodologi yang memudahkan pencarian informasi dari sejumlah besar dokumen digital, salah satunya adalah dengan proses clustering/classification, yaitu pengelompokan data/berkas berbasis teks berdasarkan kemiripannya. Beberapa metode clustering telah dikembangkan untuk mengelompokkan data terstruktur sejenis relational database seperti k-Means, decision tree, Naïve Bayes, dan sebagainya. Salah satu metode clustering, k-Means, terkenal simpel dan cepat dalam perhitungannya (Arthur, 2006), serta menjadi dasar pengembangan metode clustering yang ISBN : 978-602-97491-4-4 C-1-1


lain (Kanungo, 2002; Bhatia, 2004; Pham, 2004, Mahdavi, 2008; Tarpey 2007). Metode kMeans yang dipadukan dengan pembobotan TF-IDF menjadi solusi untuk pengelompokan data tak terstruktur seperti dokumen teks secara otomatis. Penelitian ini bermaksud menggabungkan dan mengevaluasi kinerja perpaduan metode k-Means dan TF-IDF dalam proses clustering dokumen teks ke dalam suatu aplikasi clustering dokumen teks digital. Aplikasi ini diharapkan mampu melakukan klasifikasi secara otomatis bagi dokumen-dokumen dalam korpus. Bagian kedua akan menjelaskan tentang metode k-Means clustering. Selanjutnya, konsep TFIDF dan normalisasinya dijelaskan pada bagian ketiga. Bagian keempat adalah merupakan konstribusi utama dari paper ini, yaitu memperkenalkan integrasi pembobotan TF-IDF ke metode k-Means clustering beserta hasil pengujian dan penelitian yang telah dilakukan. METODE TF-IDF (terms frequency – inverse document frequency) Metode TF-IDF (Robertson, 2004) merupakan suatu cara untuk memberikan bobot hubungan suatu kata (token) terhadap suatu dokumen. Metode ini menggabungkan dua konsep dalam perhitungan bobot yaitu, frekuensi kemunculan sebuah kata di dalam sebuah dokumen dan inverse dari frekuensi dokumen yang mengandung kata tersebut. Frekuensi dokumen yang mengandung kata tersebut menunjukkan seberapa umum kata tersebut. Bobot hubungan antara sebuah kata dan sebuah dokumen akan tinggi apabila frekuensi kata tersebUt tinggi didalam dokumen dan frekuensi keseluruhan dokumen yang mengandung kata tersebut yang rendah pada kumpulan dokumen (database). Rumus umum untuk pembobotan TF-IDF:

wtd  tf td  idf wtd  tf td  log(

N ) df t

(1)

(2)

Keterangan: wtd = bobot kata/token tt terhadap dokumen dd tftd = jumlah kemunculan kata/token tt dalam dokumen dd N = jumlah semua dokumen dalam database dft = jumlah dokumen yang mengandung kata/token tt Berdasarkan rumus (2), berapapun besarnya nilai tftd, apabila N = dft dimana sebuah kata/token muncul di semua dokumen, maka akan didapatkan hasil 0 (nol) untuk perhitungan idf, sehingga perhitungan bobotnya diubah menjadi sebagai berikut:

wtd  tf td  (log(

N )  1) df t

(3)

Rumus (3) dapat dinormalisasi dengan rumus (4) dengan tujuan menstandarisasi nilai bobot (wtd) ke dalam interval 0 s.d. 1, seperti yang ditulis oleh Intan (2006):

ISBN : 978-602-97491-4-4 C-1-2


w td 

tf td  (log( N t

 (tf td ) k 1

2

df t

)  1)

  (log( N )  1)  df t  

2

(4)

Tabel 1. Contoh data Term Frequency Doc Token tf D1 t1 1 D1 t2 2 D1 t3 4 D2 t1 1 D2 t2 2 D2 t3 3 D3 t1 2 D3 t2 3 D3 t3 4 Sebagai contoh menghitung normalisasi TF-IDF token t1 pada dokumen D1 di tabel 1 dapat dilakukan dengan menggunakan rumus (4) sebagai berikut: N = 3, tf11 = 1, dan df1 = 3, sehingga: idf 1  (log 3 )  1)  1 3 11 w11  2 2 2 2 ((1  1 )  ( 2 2  1 )  ( 4 2  1 )) w 11 

1 1  4  16

w 11  0 . 21822 Tabel 2. Hasil normalisasi TF-IDF Doc Token tf w D1 t1 1 0.21822 D1 t2 2 0.43643 D1 t3 4 0.87287 D2 t1 1 0.26726 D2 t2 2 0.53452 D2 t3 3 0.80178 D3 t1 2 0.37139 D3 t2 3 0.55708 D3 t3 4 0.74278 Dapat dilihat pada hasil perhitungan normalisasi TF-IDF di Tabel 2, semakin sedikit sebuah kata/token ditemukan dalam dokumen di database dan semakin banyak token tersebut ditemukan dalam sebuah dokumen, maka bobot hubungan antara token terhadap dokumen akan semakin besar.

ISBN : 978-602-97491-4-4 C-1-3


K-MEANS CLUSTERING K-Means clustering (Llyoid, 1982) merupakan metode clustering/pengelompokan data yang terkenal simpel dan cepat (Arthur, 2006). k-Means clustering adalah metode clustering yang mengelompokkan semua data yang dimiliki ke dalam k cluster, dimana nilai k sudah ditentukan sebelumnya. k-Means mengelompokkan data berdasarkan jarak vektor/parameter dari tiap data ke vektor/parameter dari pusat cluster (centroid) yang sudah ditentukan sebanyak k, dan mengelompokkan data-data ke pusat cluster yang terdekat.

Gambar 1. Ilustrasi proses k-Means clustering

Algoritma dari metode k-Means itu seperti yang digambarkan pada Gambar 1 adalah sebagai berikut: a. Pilih secara acak vektor data yang akan digunakan sebagai centroid awal sebanyak k. b. Cari centroid yang paling dekat dari setiap data dengan cara menghitung jarak setiap data dengan setiap centroid cluster. c. Hitung ulang untuk menentukan centroid baru dari setiap cluster dengan menghitung rata-rata nilai vektor semua data dalam cluster tersebut. d. Lakukan langkah b dan c hingga centroid tidak mengalami perubahan lagi (Tidak ada data yang berpindah cluster lagi) atau perubahan centroid lebih kecil dari nilai error/threshold yang ditetapkan. Dalam menentukan jarak antara sebuah data dengan centroid sebuah cluster, digunakan rumus euclidean distance seperti pada rumus (5).

d ij  (| xi1  x j1 | 2  | xi 2  x j 2 | 2 ...)

(5)

Keterangan: dij = jarak dari data i terhadap data j xi(n) = nilai vektor ke-n pada data i xj(n) = nilai vektor ke-n pada data i INTEGRASI TF-IDF DALAM K-MEANS CLUSTERING Mengintegrasikan pembobotan TF-IDF ke dalam k-Means clustering dilakukan dengan cara menggunakan nilai wtd (bobot token) yang didapat dalam perhitungan TF-IDF sebagai vektor/parameter dalam proses clustering menggunakan k-Means clustering, sehingga banyaknya vektor data akan didapat dari jumlah token unik di dalam kamus token (lexicon) seluruh dokumen dalam database. Berikut ini diberikan contoh penerapan k-Means clustering yang diintegrasikan dengan pembobotan TF-IDF seperti yang sudah dijelaskan sebelumnya untuk mempermudah pemahaman. Sebagai sampel, terdapat 4 buah dokumen sebagai berikut yang akan dikelompokkan ke dalam 2 cluster: ISBN : 978-602-97491-4-4 C-1-4


D1 D2 D3 D4

: “Shipment of gold damage in a fire” : “Delivery of silver arrived in a silver truck” : “Shipment of gold arrived in a truck” : “Silver truck arrived in the silver city”

Nilai k adalah 2 dan centroid awal diletakkan secara acak, dalam contoh ini, centroid 1 diletakkan pada dokumen D1 dan centroid 2 pada dokumen D2. Berdasarkan data sampel di atas, pertama-tama dilakukan proses pembangunan indeks untuk membentuk lexicon (kamus token) dan pembobotan dengan TF-IDF hingga didapat nilai wtd (bobot) sesuai dengan rumus TF-IDF standar yang belum dinormalisasi seperti pada rumus (2). Berikut ini diberikan lexicon yang terbentuk dan contoh perhitungan untuk token “shipment”. Token “shipment” dimiliki oleh Dokumen D1 sebanyak 1, dan dokumen D3 sebanyak 1. Jadi df untuk token “shipment” adalah 2. Hasil perhitungan tf dan idf ditunjukkan pada Tabel 3. Tabel 3. Tabel perhitungan tf dan idf

shipment of gold damage in a fire delivery silver arrived truck the city

tf t,D1 1 1 1 1 1 1 1 0 0 0 0 0 0

tf t,D2 0 1 0 0 1 1 0 1 2 1 1 0 0

tf t,D3 1 1 1 0 1 1 0 0 0 1 1 0 0

tft,D4 0 0 0 0 1 0 0 0 2 1 1 1 1

idf 0.301 0.125 0.301 0.602 0 0.125 0.602 0.602 0.301 0.125 0.125 0.602 0.602

dft 2 3 2 1 4 3 1 1 2 3 3 1 1

Setelah diketahui nilai tf, df, dan idf untuk masing-masing dokumen dan masingmasing token, kemudian dihitung nilai w untuk tiap token dalam tiap dokumen. Contoh perhitungan:

wsilver , D 2  tf silver , D 2  idf silver

wsilver ,D 2  2  0.301 wsilver , D 2  0.602 Hasil perhitungan keseluruhannya terlihat pada Tabel 4.

ISBN : 978-602-97491-4-4 C-1-5


Tabel 4. Tabel w (bobot token) w t,D1 w t,D2 w t,D3 0.301 0 0.301 shipment 0.125 0.125 0.125 of 0.301 0 0.301 gold 0.602 0 0 damage 0 0 0 in 0.125 0.125 0.125 a 0.602 0 0 fire 0 0.602 0 delivery 0 0.602 0 silver 0 0.125 0.125 arrived 0 0.125 0.125 truck 0 0 0 the 0 0 0 city

wt,D4 0 0 0 0 0 0 0 0 0.602 0.125 0.125 0.602 0.602

Dengan data pembobotan tersebut, maka dapat dihitung jarak antara masing-masing dokumen dengan masing-masing centroid menggunakan rumus euclidean distance. Hasil perhitungannya ditunjukkan pada Tabel 3. Tabel 3. perhitungan jarak dokumen dengan centroid Dokumen Centroid Jarak D1 Centroid 1 0 D1 Centroid 2 1.2892 D2 Centroid 1 1.2892 D2 Centroid 2 0 D3 Centroid 1 0.86958 D3 Centroid 2 0.9519 D4 Centroid 1 1.4338 D4 Centroid 2 1.0576

Dilihat dari hasil perhitungan tersebut, dokumen D1 dan D3 masuk ke cluster 1, sedangkan dokumen D2 dan D4 masuk ke cluster 2. Kemudian centroid 1 dan 2 dihitung kembali dengan cara menghitung rata-rata nilai w untuk tiap token dari tiap dokumen dalam cluster masing-masing. Setelah nilai centroid baru dihasilkan, maka dilakukan perulangan untuk menentukan cluster baru dari tiap dokumen. Proses akan berulang terus sampai tidak ada lagi dokumen yang berpindah cluster. HASIL DAN PEMBAHASAN Setelah membangun sebuah perangkat lunak yang mengimplementasikan k-Means clustering yang dipadukan dengan pembobotan TF-IDF, dilakukan sejumlah percobaan dengan beberapa jenis dokumen yang berbeda. Jenis dokumen yang digunakan dalam pengujian ini adalah dokumen teks berita yang didownload dari situs berita kompas yang dikopikan ke dalam file plain text (.txt). ISBN : 978-602-97491-4-4 C-1-6


Nilai w yang dihasilkan dari rumus (2) ternyata menunjukkan hasil clustering yang tidak baik. Terjadi anomali hasil clustering dimana hampir seluruh dokumen masuk ke dalam satu cluster tertentu saja. Namun setelah perhitungan w menggunakan rumus normalisasi TFIDF, maka hasil clustering menunjukkan peningkatan presisi. Percobaan juga dilakukan pada perubahan nilai centroid awal. Dari percobaan tersebut didapatkan bahwa untuk centroid awal yang berbeda, akan dihasilkan cluster yang berbeda pula. Pengujian akurasi dilakukan dengan parameter precision dan recall (Buckland, 1994). Nilai precision didapat dari melihat berapa persen dokumen dalam suatu cluster yang masuk ke cluster yang benar, sedangkan nilai recall didapat dari berapa persen dokumen yang seharusnya masuk ke dalam satu cluster benar-benar berada di cluster tersebut. Tabel 4. Hasil Pengujian Clustering

Cluster

Jumlah Dokumen

Cluster 1 (ekonomi)

13 dokumen

Cluster 2 (politik-hukum)

18 dokumen

Cluster 3 (olahraga)

14 dokumen

Isi Cluster

P

11 berita ekonomi, 85% 2 berita politik-hukum 13 berita politik-hukum, 4 berita ekonomi, dan 1 berita 72% olahraga 14 berita olahraga

100%

R 73% 87% 93%

Contoh perhitungan nilai precision dan recall dari hasil pengujian yang ditunjukkan oleh Tabel 4 adalah: Pada cluster 1, dari 13 dokumen yang masuk, 11 dokumen adalah berita ekonomi dan sisanya adalah 2 berita politik hukum, sehingga didapat nilai precision adalah 11/13 = 0.85 = 85%, sedangkan nilai recall-nya didapat dari 11 berita ekonomi yang masuk ke cluster 1 dibagi dengan 15 berita ekonomi yang seharusnya masuk semua ke cluster 1. 11/15 = 0.73 = 73%. Tingkat precision dan recall yang didapat dari percobaan-percobaan lain yang sudah dilakukan cukup tinggi (di atas 50%). Hasil percobaan juga menunjukkan bahwa semakin besar jumlah dokumen dalam database, semakin tinggi pula rata-rata precision dan recall dari hasil clustering yang dilakukan. Rata-rata nilai precision dan recall dari tiap pengujian ditunjukkan pada Tabel 5. Tabel 5. Rata-rata nilai precision dan recall

Jumlah dokumen dalam korpus (N) 6 dokumen sampel 20 berita olahraga 20 berita umum 45 berita umum

Rata-rata Precision (%) 68,2 75,25 75,3 85,6

Rata-rata Recall (%) 66,4 80,5 73,3 84,3

Proses clustering yang dilakukan oleh sistem juga tidak memakan waktu lama. Pada saat uji coba dengan 45 dokumen dalam korpus, sistem hanya membutuhkan waktu 3 menit untuk melakukan clustering meskipun membutuhkan waktu sampai 3 jam dalam melakukan proses penghitungan w (bobot) token dari seluruh dokumen dalam database.

ISBN : 978-602-97491-4-4 C-1-7


KESIMPULAN DAN SARAN Dengan tingkat precision dan recall tinggi yang dihasilkan dan waktu kerja yang relatif singkat oleh sistem yang mengimplementasikan metode k-Means clustering yang dipadukan dengan pembobotan TF-IDF, maka metode ini cocok digunakan untuk clustering dokumen teks. Pengembangan penelitian ini dapat dilakukan pada jenis dokumen berbeda serta penggunaan metode pembobotan yang lain. DAFTAR PUSTAKA Arthur, D. dan Vassilvitskii, S. (2006) How Slow is the k-Means Method, Stanford University, Stanford, CA. Kanungo, T., Mount, D. M., Nethanyahu N. S., Piatko, C. D., Silverman R., Wu A. Y. (2002) An Efficient k-Means clustering Algorithm: Analysis and Implementation, IEEE Transactions on Pattern Analysis and Machine Intelligence. Bhatia, S. K. (2004) Adaptive K-Means clustering, Department of Mathematics & Computer Science, University of Missouri – St. Louis. Pham, D. T., Dimov S. S., dan Nguyen C. D. (2004) An Incremental k-Means Algorithm, Proceedings of the Institution of Mechanical Engineers; Jul 2004; 218, 7; ProQuest Science Journals. Mahdavi, M. dan Abolhassani H. (2008) Harmony k-Means Algorithm for Document clustering, Springer Science+Business Media, LLC 2008. Tarpey, T. (2007) A Parametric k-Means Algorithm, © Springer Verlag 2007, Computational Statistic 22: 71-89. Ramos, J. (2010) Using TF-IDF to Determine Word Relevance in Document Queries, Department of Computer Science, Rutgers University, Piscataway. Robertson, S. (2004). Understanding Inverse Document Frequency: On Theoritical Arguments for IDF, Journal of Documentation; 2004; 60, 5; ABI/INFORM Global. Intan, R. dan Defeng, A. (2006). Subject Based Search Engine Menggunakan TF-IDF dan Jaccard’s Coefficient, Universitas Kristen Petra, Surabaya. Lloyd., S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory 28 (2): 129–137. doi:10.1109/TIT.1982.1056489 Buckland, M. dan Gey F. (1994) The Relation between Recall and Precision, Journal of the American Society for Information Science (1986-1998); Jan 1994; 45, 1; ABI/INFORM Global pg. 12.

ISBN : 978-602-97491-4-4 C-1-8

INTEGRASI PEMBOBOTAN TF-IDF PADA METODE K-MEANS UNTUK CLUSTERING DOKUMEN TEKS

Recommend Documents