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
Tidak ada komentar:
Posting Komentar