RINGKASAN MULTI DOKUMEN BERBASIS ISI DENGAN

PENGKLASTER SEKUENSIAL DAN ALGORITMA GENETIKA

*Dewi Yanti Liliana, **Tiara Arinta Dewi

Program Studi llmu Komputer, Program Teknologi Informasi dan llmu Komputer, Universitas

Brawijaya, J1. Veteran Malang, Jawa Timur, 65141

E-mail: *dewi.liliana@ub.ac.id

Abstrak

Peringkasan dokumen diperlukan untuk mengekstrak intisari atau bagian penting dari keseluruhan dokumen untuk mempermudah menangkap informasi yang disampaikan pada suatu dokumen tunggal. Permasalahan yang dihadapi adalah bagaimana jika pengguna menginginkan ringkasan informasi dari berbagai dokumen (ringkasan multi dokumen). Berbagai macam dokumen tidal( dapat diringkas menjadi satu, hanya dokumen-dokumen yang memiliki kesamaan isi yang dapat menghasilkan satu ringkasan. Untuk itu sebelum diringkas, dokumen-dokumen tersebut dikelompokkan terlebih dahulu menggunakan algoritma pengklaster sekuensial. Selanjutnya peringkasan dokumen dilakukan dengan ekstraksi kalimat dan perangkingan berbasis algoritma genetika. Ekstraksi kalimat berfungsi untuk mengidentifikasi kalimat¬kalimat penting berdasarkan fitur-fitur yang ditentukan, dan dari nilai fitur tersebut kalimat akan dirangking secara optimal dengan algoritma genetika. Hasil dari ringkasan tiap dokumen dalam satu klaster digabung menjadi satu ringkasan. Penelitian ini diujikan pada beberapa klaster dokumen dengan ukuran ringkasan 25%, 50%, dan 75%. Berdasarkan pengujian yang dilakukan dihasilkan rata-rata precision 0.710491, rata-rata recall 0.70388, dan rata-rata F-measure yang merepresentasikan akurasi sistem 0.7069. Dengan akurasi yang dihasilkan maka metode yang diusulkan dapat membantu memperoleh ringkasan infomasi secara efektif.

Kata kunci: algoritma genetika, ekstraksi fitur, pengklaster sekuensial, peringkasan multi dokumen

Abstract

Document summarization is required to extract the essential part of the whole document to facilitate the capture of information presented in a single document. The problem faced is what if the user wants to summarize from the various documents (multi-document summarization). Various kinds of documents cannot be condensed into one, only documents that have similar content can generate a summary. For that reason before summarized, these documents are grouped first using sequential clustering algorithms. Furthermore document summarization is done by sentence extraction and ranked-based genetic algorithms. Sentence extraction serves to identib, important sentences based on determined features, and the value of those features will rank sentences optimally with genetic algorithms. The result of a summary of each document in the cluster is combined into a single summary. This study tested on several clustering documents with a summary measure of 25%, 50%, and 75%. Based on tests performed its yield 0.710491 average precision, average recall 0.70388, and the average F-measure system accuracy representing 0.7069. With the resulting accuracy of the proposed method can help to obtain an information summary effectively.

Key words: genetic algorithms, feature extraction, sequential clustering, multi documents summarization

PENDAHULUAN

Perkembangan informasi online menjadi media yang semakin penting untuk menemukan dan merepresentasikan informasi tekstual. Mengingat dokumen teks sekarang ini begitu banyak, maka diperlukan suatu cara yang mudah untuk mendapatkan informasi yang dibutuhkan. Salah satu cara yang dapat ditempuh adalah dengan meringkas dokumen [1].

Tersedianya sumber informasi yang tidak terbatas mengakibatkan perolehan sumber informasi dan pertukaran data berupa teks melibatkan banyak sumber informasi sehingga memicu penelitian mengenai metode peringkasan dokumen yang semula ditujukan untuk membuat sebuah ringkasan dari dokumen tunggal menjadi metode peringkasan multi dokumen [2].

Dokumen-dokumen yang akan diringkas menjadi satu hams memiliki keterkaitan topik atau isi [3, 4]. Untuk itu, sebelum diringkas dokumen-dokumen tersebut dikelompokkan terlebih dahulu sesuai kesamaan konten, dalam penelitian ini menggunakan Pengklaster sekuensial. Kemudian, dokumen diekstrak menggunakan enam fitur [3]. Hasil dari ekstraksi kalimat akan dirangking untuk

menentukan       kalimat-kalimat  penting.

Perangkingan kalimat dilakukan dengan pendekatan algoritma genetika. Algoritma genetika dapat bekerja secara optimal untuk mengolah keenam nilai tersebut agar menjadi satu nilai tunggal dimana semua nilai fitur dapat terpenuhi bersamaan. Dengan nilai tunggal yang dihasilkan, kalimat dapat diurutkan dari yang paling besar nilainya. Nilai mengindikasikan tingkat kepentingan kalimat. Dengan adanya ringkasan, diharapkan pengguna dapat dengan mudah memahami makna sebuah teks tanpa hams membaca keseluruhan teks.

DESAIN SISTEM

Sistem akan menerima input beberapa dokumen berbahasa Inggris dari user kemudian dokumen-dokumen tersebut akan diproses melalui beberapa tahapan untuk menghasilkan ringkasan yang merupakan intisari dari dokumen-dokumen masukan.

Pertama, sistem akan melakukan preprocessing terhadap dokumen-dokumen masukan. Sebelum diringkas dokumen¬dokumen masukan tersebut akan

dikelompokkan  terlebih dahulu.

Pengelompokkan dokumen dilakukan berdasarkan kesamaan konten yang dimiliki karena hanya dokumen yang memiliki banyak kesamaan konten yang dapat diringkas menjadi satu [2]. Pengelompokkan dilakukan menggunakan metode pengklaster sekuensial.

Selanjutnya, peringkasan untuk masing-masing dokumen dilakukan dalam dua bagian yaitu ekstraksi kalimat dan perangkingan kalimat berbasis algoritma genetika. Hasil dari ringkasan tiap dokumen akan digabung. Proses penggabungan dilakukan terhadap ringkasan suatu dokumen dengan ringkasan dokumen lain dalam satu klaster, sehingga dihasilkan teks ringkasan gabungan untuk multi dokumen. Dokumen-dokumen yang berada dalam satu klaster akan menghasilkan sebuah ringkasan, jadi jumlah ringkasan sama dengan jumlah klaster. Hasil ringkasan multi dokumen akan dievaluasi menggunakan tiga parameter yaitu precision, recall, dan F-measure [6].

A. Pengklaster sekuensial

Perhitungan pengklaster sekuensial menggunakan nilai TF.1DF yang telah dinormalisasi dan cosine similarity. TF.1DF adalah perkalian antara term frequency dengan inverse document frequency. Variabel TF merupakan jumlah suatu term/kata dalam suatu dokumen, sedangkan 1DF merupakan invers document frequency dari sebuah term/kata. Dengan menggunakan bobot TF-1DF, sebuah dokumen dapat dimodelkan

sebagai sebuah vektor. Dokumen               dapat dimodelkan atas komponen Ti sehingga jika seluruh dokumen dikumpulkan maka akan terbentuk matriks term-dokumen dengan bobot term/TF-IDF sebagai nilainya.

Tahapan proses pengklaster sebagai betikut :

1.            Masukan dari proses ini adalah

kumpulan dokumen hasil praproses.

2.            Inisialisasi nilai threshold kemiripan = 0.085 (pengesetan awal berasal dari ujicoba) dan Smax = 0.

3.            Untuk setiap dokumen dilakukan perhitungan kemitipan dengan dokumen yang telah terklaster.

4.            Sebelum dilakukan perhitungan kemitipan, dilakukan pengecekan pada klaster ke-1. Jika klaster ke-1 kosong maka dokumen ke-i langsung dimasukkan pada klaster 1 .

5.            Nilai Smax dihitung dari maksimum nilai kemiripan dokumen ke-i dengan dokumen lain yang sudah terklaster.

6.            Jika nilai Smax lebih besar daripada nilai threshold maka dokumen ke-i dimasukkan pada klaster yang bersesuaian.

7.            Jika nilai Smax lebih besar daripada nilai threshold maka dokumen ke-i dimasukkan pada klaster yang bersesuain.

8.            Jika nilai Smax kurang dan threshold maka dokumen dimasukkan pada klaster ban'.

9.            Dilakukan sampai semua dokumen terklaster

B. Ekstraksi Kalimat

Sebelum melakukan ekstraksi kalimat, dokumen dipecah menjadi tiap kalimat. Setiap kalimat dan dokumen tersebut akan diekstraksi sehingga memiliki nilai yang mewakili kalimat tersebut. Ada enam fitur untuk setiap kalimat. Setiap fitur diberi nilai antara '0 'dan '1'. Enam fitur tersebut sebagai berikut:

1.            Fitur Panjang Kalimat (F1)

Fitur ini berfungsi untuk menyaring kalimat pendek seperti nama pengarang dan datelines seperti pada artikel berita. Kalimat pendek tidak dipakai untuk ringkasan dokumen. Perhitungan fitur ini ditunjukkan dengan persamaan 1:

jumlah kata pada suatu kalimat

(1)

Fl = jumlah kata pada kalimat terpanjang

2.            Fitur Pembobotan Kata/Term Weight (F2) Nilai suatu kalimat dapat dihitung sebagai jumlah nilai bobot kata dalam kalimat tersebut. Di sini akan dilakukan penghitungan menggunakan persamaan TF.IFS dan kata ke¬k sampai ke-n untuk kalimat(S) dan x sampai y. TS.ISF adalah perkalian antara term frequency dengan inverse sentence frequency. Ide dasar dan penilaian TF.ISF adalah mengevaluasi setiap kata dalam distribusinya pada seluruh kalimat di dokumen. Jadi nilai TF.ISF ditentukan untuk mengevaluasi pentingnya sebuah kata dalam dokumen bedasarkan frekuensinya dalam sebuah kalimat dan distribusinya di seluruh kalimat dalam dokumen.

Perhitungan fitur ini ditunjukkan dengan persamaan berikut:

o (s)

F2 =        k             (2)

Max (Elk'=1 ok (sr))

3. Fitur Kemiripan Kalimat (F3)

Fitur ini merupakan kesamaan antar kalimat. Untuk tiap kalimat S, kemitipan antara S dan tiap kalimat lain dihitung menggunakan cosine similarity Bobot kata TS.ISF; dan TS.ISFj dari kata t sampai n pada kalimat Si dan Si direpresentasikan oleh vektor. Kemiripan tiap kalimat ditunjukkan oleh persamaan berikut :

4.            Fitur Proper noun (F4)

Kalimat yang mengandung proper noun termasuk kalimat penting yang biasanya masuk dalam ringkasan. Proper noun adalah kata yang menunjukkan nama sesuatu, seperti nama orang, nama tempat, nama bulan, dan sebagainya. Berikut ini persamaan untuk menghitung nilai proper noun :

F4jumlah proper noun pada kalimat S 14) = panjang kalimat/jumlah kata S

5.            Fitur Thematic word (F5)

Thematic word yang dimaksud adalah kata yang frekuensinya tinggi pada suatu dokumen. Fitur ini penting karena berhubungan dengan topik. Pada penelitian ini diasumsikan Thematic word atau kata tematik adalah kata yang frekuensinya lebih dari satu, untuk

mengantisipasi   dokumen             pendek.

Persamaannya ditunjukkan oleh persamaan berikut :

F5 =

jumlah thematic word pada kalimat S

Max jumlah thematic word pada suatu kalimat

(5)

6. Fitur Numerical data (F6)

Kalimat yang mengandung data numerik dianggap kalimat penting dan biasanya masuk dalam ringkasan. Nilai dari fitur ini dihitung dengan persamaan berikut :

jumlah data numerik pada kalimat S

F6 =        (6)

panjang kalimat S

C. Perangkingan Berbasis Algoritma

Genetika

Berikut ini penjelasan langkah-langkah perangkingan berbasis Algoritma Genetika (AG):

1.            Pembangkitan Populasi Awal dan Representasi Kromosom

Pada      penelitian            ini           kromosom

merepresentasikan fitur-fitur yang ada. Satu individu terdiri dari enam kromosom sesuai dengan jumlah fitur. Tiap kromosom terdiri dari sejumlah gen sesuai dengan persamaan berikut [5] :

Li= [ 2log[(b — a)102 + 1]1            (7)

dengan b = batas atas interval dan a = batas bawah interval.

Maka jumlah gen untuk tiap kromosom sebagai berikut:

Li= [ 2log[(1 — 0)102 + 1]1

(8)

= [ 21og[101]= 7

Dengan demikian ukuran gen untuk tiap individu dengan enam kromosom (enam fitur) =7 x 6 = 42.

2.            Crossover Satu Titik

Proses crossover tergantung pada suatu parameter yaitu probabilitas crossover (Pc). Misalkan probabilitas crossover adalah 0.8, artinya diharapkan 80% individu yang akan mengalami crossover.

3.            Mutasi Biner

Sama dengan pengkodeannya, mutasi yang digunakan adalah mutasi biner. Mutasi biner yaitu mengubah nilai 1 menjadi 0 dan sebaliknya, 0 jadi 1. Proses mutasi tergantung pada probabilitas mutasi (Pm). Misalkan probabilitas mutasi 0.01, artinya diharapkan 1% dari total gen mengalami mutasi.

4.            Perhitungan Nilai Fitness dan Seleksi

Seleksi yang digunakan pada penelitian ini adalah seleksi Rank-Based fitness. Seleksi dilakukan dengan mengurutkan individu sesuai nilai fitnessnya kemudian mengambil individu-individu teratas. Seluruh individu, yaitu individu awal, anakan hasil crossover, dan anakan hasil mutasi dihitung nilai fitnessnya kemudian diurutkan mulai dari yang

terbesar sesuai nilai fitness dan diambil yang tertinggi sebanyak ukuran populasi / jumlah individu awal. Fungsi fitness didapatkan dari persamaan objektif Fan. Persamaan objektif Fan merupakan persamaan minimum sehingga fungsi fitness dihitung dari invers persamaan objektif Fan. Persamaan fungsi fitness ditunjukkan pada persamaan berikut:

Fitness =              (9)

m ,

               ETi( 1     2 max    bj —by) n

Nilai w? dihitung dari nilai wi yang telah didapat pada tahap sebelumnya. Nilai max br merupakan nilai maksimum fitur ke-j pada semua kalimat.

Untuk menghitung nilai W digunakan persamaan berikut :

x

=             .              (10)

x total

Dimana j = 1,2,...,n (n adalah jumlah kromosom tiap individu). Untuk menghitung nilai x yang merupakan variabel temporer dengan persamaan berikut:

xi = a+ Rb —a)1(214 — 1)] x vi

(11)

dengan a = batas bawah interval data, pada kasus ini adalah 0; b = batas atas interval data, pada kasus ini adalah 1; Lj = panjang gen ke-j Kemudian dihitung x total untuk tiap individu (pada kasus ini sepanjang 6 kromosom).

5.            Merangking kalimat

Setelah diketahui individu mana yang memiliki nilai fitness tertinggi, individu tersebut dij adikan sebagai solusi terbaik. Untuk mendapatkan urutan rangking, nilai bobot dari individu yang tepilih sebagai solusi terbaik, digunakan untuk menghitung nilai altematif ke-i sebagai nilai kalimat ke-i dengan persamaan berikut [5]:

gt= E7=1Wi it

(12)

D. Penggabungan Ringkasan tiap Master

Penggabungan merupakan proses untuk menggabungkan hasil ringkasan masing-masing dokumen yang ada dalam satu klaster. Hasil ringkasan digabungkan menggunakan perhitungan cosine similarity dengan TF (Term Frequency). TF adalah frekuensi kata pada suatu kalimat. Perhitungan cosine

similarity dengan TF seperti ditunjukkan pada persamaan berikut:

~ ~

,∑k=1 7&k × ,∑ 7)

~~~

dengan 7&k jumlah kata k pada kalimat I; 7)k jumlah kata k pada kalimat j.

METODE EVALUASI

Proses evaluasi hasil text summarization dilakukan menggunakan tiga parameter yaitu precision, recall, dan F-measure [6]. Sebuah sistem informasi dikatakan baik jika tingkat precision, recall, dan F-measurenya tinggi. Cara mengevaluasinya yaitu membandingkan ringkasan otomatis hasil sistem dengan ringkasan manual.

1.            Precision

Precision merupakan perbandingan jumlah informasi relevan yang didapatkan sistem dengan jumlah seluruh informasi yang terambil oleh sistem baik yang relevan maupun tidak. Persamaan precision ditunjukkan pada persamaan berikut :

P =          ;4335;7 (14)

(;4335;7R<34n8)

2.            Recall

Recall merupakan perbandingan jumlah informasi relevan yang didapatkan sistem dengan jumlah seluruh informasi relevan yang ada dalam koleksi informasi (baik yang terambil atau tidak terambil oleh sistem). Persamaan recall ditunjukkan pada persamaan berikut:

Keterangan:

correct : jumlah kalimat yang diekstrak oleh sistem dan manusia.

wrong : jumlah kalimat yang diekstrak oleh sistem tetapi tidak diekstrak oleh manusia. missed : jumlah kalimat yang diekstrak oleh manusia tetapi tidak diekstrak oleh sistem.

3.            F-Measure

F-Measure merupakan hubungan antara recall dan precision yang merepresentasikan akurasi sistem. Persamaan F-Measure seperti pada persamaan berikut:

F = ~∗T∗U (TRU) (16)

HASIL UJI COBA

Pengujian dilakukan untuk mengetahui seberapa dekat hasil ringkasan sistem dengan hasil ringkasan manual. Perhitungan terhadap tiga parameter yang berbeda yaitu precision, recall, dan F-measure dilakukan untuk ukuran ringkasan dokumen yang berbeda, yaitu 25%, 50%, dan 75%. Setelah dilakukan pengujian akan diketahui kemampuan sistem dalam menghasilkan informasi yang relevan yang diinginkan user.

Dari 9 dokumen yang dimasukkan terbagi menjadi 4 klaster. Hasil percobaan untuk semua ukuran ringkasan dengan parameter algoritma genetika jumlah individu = 20, maksimum generasi = 50, probabilitas crossover = 0.8, dan probabilitas mutasi 0.01 ditunjukkan pada gambar 1, 2, dan 3.

Gambar 1. Grafik Nilai Precision

Pada Gambar 1 nilai precision terendah dihasilkan oleh klaster 1 dengan ukuran ringkasan 25%. Nilai precision tertinggi dihasilkan klaster 2 dengan ukuran ringkasan 75%.

Gambar 2. Grafik Nilai Recall

Pada gambar 2 nilai recall terendah dihasilkan oleh klaster 1 dengan ukuran ringkasan 25% sedangkan nilai recall tertinggi dihasilkan oleh klaster 2 dengan ukuran ringkasan 75%.

Gambar 3. Grafik Nilai F-measure

Pada gambar 3 nilai F-measure terendah dihasilkan oleh klaster 1 dengan ukuran ringkasan 25%, sedangkan nilai tertinggi dihasilkan oleh klaster 2 dengan ukuran ringkasan 75%. Untuk ukuran ringkasan 25% didapatkan rata-rata nilai F-measure 0.5878, ukuran ringkasan 50% didapatkan rata-rata nilai F-measure 0.6891, dan untuk ukuran ringkasan 75% rata-rata nilai F-measure sebesar 0.8438.

Di sini terlihat nilai F-measure semakin naik untuk ukuran ringkasan yang semakin besar

pula.      Rata-rata             nilai        F-measure

merepresentasikan akurasi sistem ini, yaitu 0.7069.

KESIMPULAN

Penelitian ini telah menghasilkan sistem peringkasan multi dokumen berbahasa Inggris berbasis isi menggunakan pengklaster sekuensial dan perangkingan berbasis algoritma genetika. Berdasarkan evaluasi

sistem   yang      dilakukan             dengan

membandingkan hasil ringkasan sistem dan

ringkasan manual diperoleh nilai F-measure tertinggi untuk ukuran ringkasan 75% yaitu sebesar 0.8438, sedangkan nilai F-measure untuk ukuran ringkasan 25% dan 50% yaitu sebesar 0.5878 dan 0.6891. Jadi semakin besar ukuran ringkasan semakin tinggi nilai F-measure atau akurasinya. Rata-rata nilai F-measure untuk semua ukuran ringkasan yang merepresentasikan akurasi sistem yaitu sebesar 0.7069.

PUSTAKA

[1]          Fattah, M. A. dan Ren, Fuji. Automatic Text Summarization. World Academy of Science, Engineering and Technology. Singapore. 2008

[2]          Hariharan, S. Extraction Based Multi Document Summarization using Single Document Summary Cluster. B.S. Abdur Rahman University. Vandalur. 2010

[3]          Kogilavani, A., dan Balasubramani, P. Clustering Feature Specific Sentence Extraction Based Summarization of Multiple Documents. Kongu Engineering College. Erode. 2010

[4]          Kuo, J. dan Chen, H. Cross-document Event Clustering Using Knowledge Mining From Co-reference Chains. National Taiwan University. Taipei. 2006.

[5]          Kusumadewi, Sri. Pencarian Bobot Atribut Pada Multiple Attribute Decision Making (MADM) dengan Pendekatan Obyektif Menggunakan Algoritma Genetika. Gematika Jurnal Manajemen Informatika. Jakarta. 2005

[6]          Nedunchelian, R., Muthucumarasamy, R., dan Saranathan, E. Comparison Of Multi Document Summarization Techniques. IJCSNS (International Journal of Computer Science and Network Security). 2011

PENGELOMPOKAN DATA KATEGORI DENGAN MISSING VALUE MENGGUNAKAN ALGORITMA K-NEAREST NEIGHBOUR IMPUTATION DAN K-MODES

Lailil Muflikhah*, Aditya Hari Bawono**

*Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya

** Program Studi Ilmu Komputer, Universitas Brawijaya

*lailil@ub.ac.id, **gunslingerism@gmail.com

Abstrak

Salah satu solusi untuk mempermudah pencarian adalah dengan melakukan pengelompokan dan salah satu metoda yang cukup terkenal adalah k-Means clustering, dimana bentuk data yang dikelompokkan berjenis numerik. Namun pada dunia nyata, data dapat berjenis kategori dan juga tak selalu lengkap berisikan nilai-nilai. Oleh karena itu, dalam paper ini dikenalkan dua metode untuk mengatasi hal tersebut, yakni k-Nearest Neighbour Imputation (k-NN Imputation) sebagai cara untuk mengatasi data yang mengandung missing value dan k-Modes sebagai cara untuk melakukan pengelompokan data berkategori.

Uji coba dilakukan dengan memberikan tiga dataset: mushroom, balance scale dan car evaluation dengan berbagai jumlah prosentase data ber-missing value, yakni 5%, 10% dan 15%. Dari hasil uji coba didapatkan adanya penurunan performa F-measure dari ketiga dataset tersebut tetapi tidak mengandung missing value.

Kata kunci : k-Means, k-Modes, k-NN Imputation, missing value

Abstract

One solution to facilitate the search is by grouping and k-Means clustering is a well-known clustering method, in which the form of segmented in numeric data type. However, in the real world, the data can be diversified category and also they do not always contain the completed values. Therefore, this paper introduced two methods to overcome this problem, the k-Nearest Neighbour Imputation (k-NN Imputation) is used to solve data containing missing value and k-Modes as a way to perform clustering of categorical data.

An experiment test is done by giving three datasets: mushroom, balance scale and car evaluation with high-percentage amount of data missing value, such as 5%, 10% and 15%. The test result is obtained a decrease in F-measure performance of the three datasets but does not contain the missing value.

Keywords: k-Means, k-Modes, k-NN Imputation, missing value

PENDAHULUAN

Dalam penelitian sebelumnya, beberapa algoritma yang digunakan untuk melakukan pengelompokan, diantaranya adalah k-means [1] beserta variasi-variasinya. K-means adalah algoritma yang efisien untuk melakukan pengelompokan. Namun, penggunaannya cenderung terbatas pada data numerik dikarenakan algoritma k-means menghitung rata-rata cluster. [2] mengajukan suatu metode campuran numerik dan simbolik untuk mengembangkan algoritma k-

means untuk melakukan pengelompokan pada atribut kategori. Namun terjadi lamanya perhitungan apabila atribut kategori memiliki banyak kategori. Pada penelitian selanjutnya, [3] mengajukan sebuah algoritma k-modes yang merupakan pengembangan dari algoritma k-means dengan maksud mengatasi masalah pengklasteran pada data kategori. Pada penelitian tersebut oleh Huang digunakan beberapa dataset lengkap, tanpa adanya missing value seperti dataset soybean dan nursery. Namun, dalam kejadian nyata, data tidak selalu lengkap, seringkali terdapat missing

value[4]. Sedangkan, pengelompokan tidak dapat dilakukan apabila terdapat missing value, dikarenakan dapat menimbulkan perkiraan dan mempengaruhi kualitas algoritma[5]. Pada umumnya, penanganan missing value adalah menemukan pendekatan yang dapat mengisi dengan nilai yang mungkin. Beberapa metode yang digunakan untuk menangani missing value adalah mean imputation, case deletion, dan k-NN imputation. Pada penelitian yang dilakukan Acuna [6], menunjukkan, k-NN imputation memiliki tingkat kesalahan yang paling rendah dari metode-metode tersebut, sehingga digunakan dalam penelitian ini.

TINJAUAN PUSTAKA

Data

Menurut Lee dan Santana [7] data dan informasi memiliki pengertian yang berbeda. Data dikatakan sebagai bahan mentah dari informasi. Data merupakan kumpulan kejadian nyata yang dapat dijamin kebenarannya. Data dapat dikelompokkan ke dalam dua jenis, yaitu data kategori dan data numerik. Data kategori adalah data yang mengambil suatu himpunan nilai tertentu. Namun, data numerik adalah data yang berbentuk angka. Data numerik kebanyakan didefinisikan sebagai kuantitatif, dan dapat pula berupa “kontinyu”, juga berupa “diskrit”.

Missing Value

Missing value merupakan hal yang biasa terdapat pada dataset. Missing value pada dataset didefinisikan sebagai kekosongan nilai dari variabel tertentu pada dataset. Sebagian besar algoritma data mining tidak dapat bekerja secara langsung dengan dataset yang tidak lengkap. Oleh karena itu diperlukan suatu metode penanganan untuk missing value pada dataset tersebut.[8]

Pada umumnya metode untuk menangani missing value dapat dibagi dalam tiga kategori, yaitu Case/Pairwise Deletion, Parameter Estimation dan Teknik Imputasi. Pada metode teknik Imputasi, missing value digantikan dengan nilai perkiraan yang didasarkan pada informasi yang terdapat pada dataset. Beberapa metode yang termasuk teknik imputasi diantaranya adalah Mode Imputation dan K-Nearest Neighbor Imputation.[9]

K-Nearest Neighbor Imputation (KNNI)

K-Nearest Neighbor (KNN) adalah pendekatan untuk mencari kasus dengan menghitung kedekatan antara kasus baru dengan kasus lama, yaitu berdasarkan pada pencocokan bobot dari sejumlah fitur yang ada.[10]

Menurut Olivas [11], k-Nearest Neighbor Imputation termasuk dalam Machine Learning Solutions dalam teknik imputasi. Metode ini menangani missing value pada suatu data dengan melakukan imputasi dengan mempertimbangkan nilai yang diberikan oleh record yang paling mirip.

Pengelompokan (Clustering)

Menurut Anderberg [12], membagi himpunan obyek ke dalam klaster yang homogen adalah operasi yang mendasar dalam data mining. Pengklasteran adalah suatu pendekatan yang banyak digunakan untuk mengimplementasi operasi tersebut. Metode pengklasteran membagi himpunan obyek ke dalam suatu klaster dimana obyek-obyek dikelompokkan yang sama adalah mirip maupun sama satu dengan lainnya dibanding obyek-obyek di kelompok lainnya berdasarkan konsep maupun sifat yang dibawa obyek tersebut, sebagaimana terlihat pada Gambar 1.

Gambar 1. Ilustrasi pengelompokan

Menurut Zaiane [13], pada Gambar 1 dapat dengan mudah diidentifikasikan empat kelompok di mana data dibagi, kriteria jarak adalah similarity atau kesamaan jika dua atau lebih benda milik klaster yang sama jika mereka dekat menurut jarak tertentu (dalam kasus ini jarak geometris). Hal ini disebut pengelompokan berdasarkan jarak.

Algoritma K-Modes

Menurut Huang [13], algoritma k-means memiliki kelemahan dimana penggunaan yang terbatas untuk data numerik. Huang melakukan modifikasi pada algoritma k-means. Adapun algoritma k-Modes secara keseluruhan sebagaimana berikut:

1. Pilih k awal, satu per kelompok

2.            Alokasikan obyek ke kelompok. Gunakan Euclidean Distance seperti pada persamaan 2.2. Update modus per kelompok.

3.            Setelah setiap obyek dialokasikan ke dalam kelompok, lakukan tes ulang terhadap dissimilarity obyek terhadap modus saat ini. Jika sebuah obyek ditemukan lebih dekat dengan suatu klaster yang lain daripada klaster sekarang, lakukan alokasi ulang obyek dan update modus setiap kelompok.

4.            Ulangi langkah 3 hingga tidak ada obyek berganti kelompok setelah pengetesan penuh terhadap seluruh record dalam dataset.

Accuracy

Metode evaluasi yang digunakan dalam penelitian ini adalah performance metric error rate digunakan untuk mengevaluasi nilai atribut yang bertipe kualitatif dan F-measure yang ditentukan berdasarkan nilai precission dan recall. Menurut Tan.,dkk. [14], Error rate dapat dihitung dengan persamaan 1.

Error rate= Jumlah Prediksi Salah

(1)

Jumlah Total Prediksi

Sedangkan accuracy adalah kebalikan dari error rate. Accuracy dapat dihitung dengan persamaan 2.

Accuracy= 1 − error rate (2)

F-Measure

F-measure merupakan gabungan antara recall dan precision yang didefinisikan dengan persamaan 3 [15]:

F − Measure = METODOLOGI

Adapun perancangan perangkat lunak yang digunakan meliputi tiga proses utama sebagaimana terlihat pada Gambar 2, yakni

1.            Proses request data

2.            Proses penanganan missing value dengan metoda k-NN Imputation (KNNI)

3.            Proses pengelompokkan dengan k-Modes

Pada proses request data merupakan pemilihan dataset yang digunakan untuk dalam uji coba. Sedangkan untuk penanganan missing value ditunjukkan dalam Gambar 3. Pada tahap awal dilakukan pemilihan terhadap data uji yang memiliki missing value dan yang lengkap. Proses selanjutnya dilakukan penghitungan nilai jarak eucledian beserta pengurutan terhadap nilai jarak

tersebut. Kemudian ditentukan nilai data dengan frekuensi terbanyak.

Gambar 2. Gambaran umum sistem

Gambar 3. Flow chart proses penanganan missing value dengan k-NN Imputation

tetangga yang memungkinkan adalah banyaknya Tabel 4 Hasil dataset balance scale 1, accuracy

data yang lengkap pada dataset.

Analisa pengaruh rasio missing value

Contoh dataset balance scale dengan tiga buah missing value yang berbeda tempat akan ditunjukkan oleh Tabel 1, Tabel 2, dan Tabel 3. Tabel 1 Contoh bagian dataset balance scale 1

No          Att1       Att2       Att3       Att4

1             1             1             1             1

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

72           3             1             3             5

73                          1             3             5

74           5                            3             1

75           1             1                            1

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

625        5             5             5             5

Tabel 2 Contoh bagian dataset balance scale 2

No          Att1       Att2       Att3       Att4

1             1             1             1             1

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

72           3             1             3             5

73                          1             3             5

74                          1             3             1

75                          1             4             1

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

625        5             5             5             5

Tabel 3 Contoh bagian dataset balance scale 3

No          Att1       Att2       Att3       Att4

1             1             1             1             1

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

72           3             1             3             5

73           4             1             3             5

74                                                        5

75           1             1             4             1

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

625        5             5             5             5

Pada k = 15 diujikan pada metoda KNNI dan dapatkan nilai hasil beserta akurasinya seperti pada Tabel 4, Tabel 5, dan Tabel 6.

Tabel 7 Contoh potongan dataset mushroom 1

N o         At t1      ...           At t9      Att

10           Att

11           Att

12           Att

13           ...           Att

22

1             x             ...           k             e             e             s             s             ...           u

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

14           x             ...           t              e             s             f              w            ...           u

15           x             ...           e                            s             s             w            ...           g

16           s             ...           t              e                            s             w            ...           u

= 0.66667

Posisi     Nilai KNNI           Nilai nyata

(73, 0)    5             4

(74, 1)    1             1

(75, 2)    4             4

Tabel 5 Hasil dataset balance scale 2, accuracy = 0.3333

Posisi     Nilai KNNI           Nilai nyata

(73, 0)    5             4

(74, 0)    5             5

(75, 0)    4             1

Tabel 6 Hasil dataset balance scale 3 accuracy = 0

Posisi     Nilai KNNI           Nilai nyata

(74, 0)    4             5

(74, 1)    4             1

(74, 2)    2             3

Dari Tabel 4, Tabel 5, dan Tabel 6 dapat diambil kesimpulan bahwa accuracy dipengaruhi oleh peletakan missing value. Pada Tabel 1, dataset diletakkan pada baris dan kolom yang berbeda, hal ini membuat rentang nilai perhitungan jarak terhadap tetangga sebanyak k menjadi lebih luas yang berakibat pada hasil yang baik. Berbeda dengan dataset pada Tabel 3 dimana dalam satu baris terdapat tiga missing value dan hanya satu kolom untuk perhitungan jarak. Pada Tabel 1 rentang nilai jarak berkisar antara -/0 hingga -/3 sedangkan pada Tabel 3.3 hanya berkisar antara antara -/0 hingga -/1 yang dapat mengakibatkan kemungkinan masuknya nilai tetangga sebanyak k yang tidak diinginkan.

Jika dilakukan analisa terhadap dataset mushroom yang memiliki panjang kolom 22, maka hasil percobaan akan ditunjukkan oleh Tabel 7, Tabel 8 dan Tabel 9.

17           f              ...           e             e             s                            w            ...           g

18           x             ...           e             e             s             s             w            ...           g

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

30 0       x             ...           p             e             e             s             s             ...           g

Tabel 8 Contoh potongan dataset mushroom 2

N o         At t1      ...           At t9      Att

10           Att

11           Att

12           Att

13           ...           Att

22

1             x             ...           k             e             e             s             s             ...           u

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

14           x             ...           t              e             s             f              w            ...           u

15           x             ...           e                            s             s             w            ...           g

16           s             ...           t                             s             s             w            ...           u

17           f              ...           e                            s             s             w            ...           g

18           x             ...           e             e             s             s             w            ...           g

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

30 0       x             ...           p             e             e             s             s             ...           g

Tabel 9 Contoh potongan dataset mushroom 3

No          Att 1      ...           Att 9      Att1 0    Att1 1    Att1 2    Att1 3

1             x             ...           k             e             e             s             S

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

14           x             ...           t                                                           W

15           x             ...           e             e             s             s             W

16           s             ...           t              e             s             s             W

17           f              ...           e             e             s             s             W

18           x             ...           e             e             s             s             W

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

30 0       x             ...           p             e             e             s             S

Dengan k=15,didapatkan hasil dan nilai akurasinya seperti pada Tabel 10, Tabel 11, dan Tabel 12.

Tabel 10 Hasil dataset mushroom 1,accuracy = 1

Posisi     Nilai KNNI           Nilai nyata

(15,        10)         e             e

(16,        11)         s             s

(17,        12)         s             s

Tabel 11 Hasil dataset mushroom 2,accuracy = 1

Posisi     Nilai KNNI           Nilai nyata

(15,        10)         e             e

(16,        10)         e             e

(17,        10)         e             e

Tabel 12 Hasil dataset mushroom 3,accuracy = 0.6667

Posisi     Nilai KNNI           Nilai nyata

(14, 10) e             E

(14, 11) s             S

(14, 12) s             F

Pada dataset mushroom yang terdapat jumlah kolom yang lebih banyak daripada dataset balance scale dan car evaluation, accuracy yang dihasilkan lebih baik. Dengan jumlah kolom sebanyak 22, dataset mushroom mampu menampung variasi jarak dengan rentang 0 hingga √22 dengan variasi jarak yang sedemikian hingga, maka kemiripan dan ketidakmiripan suatu record dengan record yang lain akan tampak lebih jelas dan lebih signifikan. Jika dilihat dari rasio jumlah kolom yang terdapat missing value, walaupun jumlah hilangnya sama (yaitu tiga), namun pada dataset balance scale kehilangan tiga data dalam satu record adalah kehilangan 75% data untuk perhitungan dari record tersebut, sedangkan pada dataset mushroom hanya kehilangan 13.6%. Perbedaan yang amat signifikan inilah yang alasan perbedaan tingkat accuracy pada dataset dengan jumlah kolom yang berbeda.

Analisa jumlah tetangga (k)

Untuk dataset yang memiliki banyak outlier, k terbaik adalah pada k yang cenderung besar

nilainya, demikian sebaliknya untuk dataset yang memiliki lebih sedikit outlier. Hal ini dibuktikan dengan rata-rata accuracy pada dataset balance scale dan car evaluation yang memiliki lebih banya outlier daripada dataset mushroom.

Pada dataset balance scale, rata-rata accuracy terbaik untuk setiap banyak prosentase missing

value adalah 0.11099 pada k = 77. Hal ini

disebabkan pada k = 77 bernilai tinggi pada dataset balance scale 5% missing value demikian

pula dengan prosentasi missing value yang lain

pada dataset balance scale. Sebaliknya, pada k = 10 dataset balance scale memiliki rata-rata

accuracy terendah 0.0799. Hal ini dikarenakan pada k = 10, sistem mengambil 10 tetangga yang kebanyakan memiliki nilai yang tidak sesuai dengan nilai yang sebenarnya.

Pada dataset car evaluation, rata-rata accuracy terbaik pada setiap prosentase missing value adalah 0.2160 pada k = 90 dan rata-rata accuracy terkecil pada k = 10 dengan nilai 0.1744. Pada dataset mushroom, rata-rata accuracy terbaik untuk setiap banyak prosentase missing value adalah 0.9294 pada k = 29 dan rata-rata accuracy terkecil sebesar 0.6478 pada k = 100.

Analisa banyak kelas dalam dataset terhadap nilai precision, recall, dan f-measure

Pada dataset balance scale dengan kelas sebanyak tiga, kisaran f-measure antara 0.427¬ 0.4642. Untuk dataset car evaluation dengan kelas sebanyak empat, kisaran f-measure antara 0,1227-0.2275. Sedangkan pada dataset mushroom dengan dua kelas, kisaran f-measure antara 0.799-0.958. Dari hasil pengujian disimpulkan banyaknya kelas pada data asli mempengaruhi performa pengelompokkan, makin sedikit kelas, maka semakin baik performa pengklasteran..

Analisa jumlah cluster k terhadap f-measure

Pada k-modes, terdapat centroid awal yang acak, Kualitas pengklasteran k-modes amat dipengaruhi oleh centroid awal. Jika centroid awal cocok dengan kelas pada dataset yang bersangkutan, maka nilai f-measure akan bernilai lebih baik daripada yang tidak cocok. Dari data pengujian dapat ditarik kesimpulan bahwa missing value berpengaruh pada baiknya penilaian pengelompokkan. Hal tersebut disebabkan oleh semakin buruk kualitas dataset dengan semakin banyak outlier, maka hasil pengelompokan cenderung tidak relevan. Dari hasil pengujian didapatkan penurunan kualitas pengelompokkan K-Modes pada dataset yang mengandung rmissing value sebesar 3% pada dataset balance scale, 26.24% pada dataset car evaluation, dan 6.4% pada dataset mushroom. Jika dihitung rata-rata penurunan kualitas pengelompokan K-Modes maka dihasilkan 11.8% penurunan untuk pengelompokkan pada dataset yang mengandung missing value.

KESIMPULAN

Kualitas pengklasteran K-Modes dipengaruhi oleh banyaknya missing value yang salah digantikan oleh metode KNNI. Makin banyak missing value pada dataset, semakin buruk pula performa pengklasteran.

Nilai accuracy metode KNNI dipengaruhi oleh rasio, jumlah missing value, dan dataset yang bersangkutan. Rasio missing value sebesar 75% yang berada pada attribute yang sama akan memperburuk perhitungan. Sedangkan nilai rata-rata accuracy tertinggi pada dataset balance pada k = 77 dengan nilai 0.11099 dan accuracy terburuk pada k = 10 dengan nilai 0.0799. Pada dataset car evaluation, rata-rata accuracy terbaik untuk setiap banyak prosentase missing value adalah 0.2160 pada k = 90 dan rata-rata accuracy terkecil pada k = 10 dengan nilai 0.1744. Pada

dataset mushroom, rata-rata accuracy terbaik untuk setiap banyak prosentase missing value adalah 0.9294 pada k = 29 dan rata-rata accuracy terkecil sebesar 0.6478 pada k = 100.

Pada pengklasteran dengan metode k-Modes, terdapat kelemahan yang mendasar pada langkah penentuan centroid awal yang dilakukan secara acak. Pemilihan centroid awal secara acak akan mengakibatkan hasil yang acak pula. Meskipun dengan dataset yang bermissing value dan dengan tingkat accuracy yang beraneka ragam, 11.8% adalah rata-rata hasil perbedaan kualitas f-measure proses dataset bermissing value dengan yang tidak bermissing value oleh kombinasi metode K-Modes dan KNNI.

DAFTAR PUSTAKA

[1]          MacQueen, J. B. (1967). Some Methods for Classification and Analysis of Multivariate Observations, In Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, pp. 281-297.1967

[2]          Ralambondrainy, H. A Conceptual Version of

the k-Means       Algorithm,           Pattern

Recognition Letters, Volume:16, pp.1147¬ 1157. 1995.

[3]          Z. Huang. Extensions to the k-means algorithm for clustering large data sets with categorical values. Data Mining and Knowledge Discovery. Volume: 2, pp.283¬ 304. 1998

[4]          Zhang, S., Qin, Z., X. Ling, C., Sheng, S., “Missing is useful”: Missing values in cost-sensitive decision trees. IEEE Transactions on Knowledge and Data Engineering, Volume: 17, pp. 1689-1693. 2005

[5]          Qin, Y., Zhang, S., Zhu, X., Zhang, J., Zhang C., Semi-parametric Optimization for

Missing Data Imputation.              Applied

Intelligence, Volume 27(1): 79-88. 2007

[6]          Acuna, Edgar dan Rodriguez,Caroline. The Treatment of Missing Values and its Effect in the Classifier Accuracy. University of Puerto Rico, Mayaguez. 2003.

[7]          Lee, Finn dan Santana, Juan. Data Mining : Meramalkan Bisnis Perusahaan. PT. Elex Media Komputindo, Jakarta. 2010.

[8]          Gheyas, Iffat A. dan Smith, Leslie S. A Novel Nonparametric Multiple Imputation Algorithm for Estimating Missing Data. Proceedings of the World Congress on Engineering, Volume II WCE, London, U.K. 2009

[9]          Little, R. J. and Rubin, D.B. Statistical Analysis with Missing Data Second Edition. John Wiley and Sons, New York. 2002

[10]        Luthfi, E.T dan Kusrini. Algoritma Data Mining. Andi Offset, Yogyakarta.2009

[11]        Olivas, Emilio Soria. Handbook of Research on Machine Learning Application and Trends : Algorithms, Methods, and Techniques. IGI Global, United States of America. 2010

[12]        Anderberg, M. R.. Cluster Analysis for Applications. New York : Academic Press Inc1.973

[13]        Zaiane, Osmar R. Principles of Knowledge Discovery in Databases. University of Alberta. 1999

[14]        Tan, Pang-Ning, Michael Steinbach dan Vipin Kumar. Introducing to data mining. New York. 2004.

[15]        Yang, Yiming dan Liu, Xin. A Re-examinationof Text Categorization Methods. In Proceedings of ACM SIGIR Conference on Research and development in Information Retrieval (SIGIR), pp 42-49. 1999.

http://www.cs.cmu.edu/~yiming/publication s.html tanggal akses: 21 Februari 2011

[16]        UCI Machine Learning Repository, http:

//www  .ics.        uci.         Edu

/mlearn/MLRepository.html,        Diakses

tanggal 22 Maret 2011

CI - 31