Abstrak —Klasifikasi  merupakan  sebuah  metode  yang  cukup sering  digunakan  dalam  bidang  statistika  dan  komputasi  cerdas terutama  dengan  kaitannya  untuk  memprediksi  sesuatu berdasarkan  data  yang  diterima.  Klasifikasi  dapat  dilakukan untuk  berbagai  macam  tipe  data  mulai  dari  numerik,  ordinal ataupun  kategorik.  Pada  data  kategorik  perhitungan  jarak perbedaan  atau  kesamaan  tidak  dapat  dihitung  menggunakan operasi  matematik  seperti  yang  dapat  dilakukan  terhadap  data numerik.  Salah  satu  metode  yang  dapat  digunakan  untuk menghitung  jarak  pada  data  kategorik  adalah Simple  Matching Coefficient (SMC) . Namun metode ini terkesan tidak adil karena menganggap bahwa setiap atribut memiliki kotribusi yang sama terhadap  tiap  label  kelas.  Karena  itu  metode  SMC  akan dioptimasi  dengan  menggunakan Weighted  Simple  Matching Coefficient(WSMC) . Dalam penelitian kali ini, diimplementasikan sebuah  metode  klasifikasi  terhadap  data  kategorik  yang menggunakan  metode  klasifikasi Nearest-Neighbor dengan pembobotan  atribut  menggunakan  WSMC.  Uji  coba  yang dilakukan  terhadap  6  dataset  dengan  atribut  bersifat  kategorik, menunjukkan kemampuan metode dalam melakukan klasifikasi. Dengan rata-rata akurasi tertinggi didominasi oleh metode lokal. Rata-rata akurasi tertinggi untuk dataset Nursery , Cars , Gerakan tangan, Soybeans , Vote dan Dhermatology berturut-turut sebesar 77.31%, 80.35%, 97.00%, 91.64%, 92.41%, dan 95.90%.
Kata  Kunci — Nearest-Neighbor ,  data  kategorik,  pembobotan atribut.

## I. PENDAHULUAN
ADA  era  saat  ini,  aplikasi  komputer  atau  perangkat bergerak  yang  diperuntukkan  untuk  para  pakar  maupun yang diperuntukkan untuk orang awam terus dikembangkan ke arah yang lebih cerdas untuk memudahkan pekerjaan manusia. Aplikasi  yang  dibuat  haruslah  memiliki  kemampuan  untuk memberikan  rekomendasi  hasil  analisa  input.  Contoh  input yang paling sering dianalisa adalah data, baik itu data numerik maupun  data  kategorik.  Di  sinilah  peran  klasifikasi  sangat dibutuhkan  oleh  para  pembuat  aplikasi  untuk  terus mengembangkan  aplikasinya  agar  semakin  cerdas  dan diminati banyak orang.
Metode  klasifikasi  yang  paling  umum,  simpel  dan  mudah untuk diterapkan salah satunya adalah k-Nearest-Neighbor (k- NN).  Algoritma  k-NN  dinilai  cepat  karena  merupakan Instance-based  learning atau lazy-learning [1] yang  tidak memerlukan  fase  latihan  pada  awal  proses  [2].  Namun  dalam penerapannya,  untuk  melakukan  klasifikasi  terhadap  data kategorik,  diperlukan  cara  khusus  dalam  menghitung  jarak
antar data yang ada. Salah satu cara khusus dalam menghitung jarak  antar  data  yang  paling  sering  diterapkan  adalah menggunakan Simple Matching Coefficient (SMC)[3].
Dalam  penelitian  kali  ini,  diimplementasikan  sebuah metode klasifikasi terhadap data kategorik yang menggunakan metode  klasifikasi Nearest-Neighbor dengan  pembobotan atribut  menggunakan Weighted  Simple  Matching  Coefficient (WSMC).
Diskusi  pada  jurnal  ini  dibagi  dalam  struktur  sebagai berikut: Bab II membahas materi dan metode yang digunakan dalam  sistem.  Bab  III  membahas  hasil  dan  diskusi  uji  coba yang  dilakukan  terhadap  enam  dataset  dengan  atribut  data kategorik.  Terakhir  pada  Bab  IV  membahas  kesimpulan  dan saran dari hasil yang didapatkan dalam penelitian ini.

## II. MATERI DAN METODE
Pada sistem yang dibangun, terdapat dua tahap penting yang dilakukan. Dua tahap tersebut adalah tahap training dan tahap testing. Tahap training adalah  tahap  dimana  proses perhitungan  bobot  atribut  dilakukan,  dan  tahap testing adalah tahap  dimana  proses  klasifikasi  k-NN  dilakukan  dengan pembobotan  atribut  yang  sudah  didapatkan  pada  tahap training .  Sistem  menggunakan  metode Weighted  Simple Matching Coefficient untuk melakukan perhitungan jarak antar data dan k-Nearest Neighbor untuk proses klasifikasi.
A. Weighted Simple Matching Coefficient (WSMC)
Weighted  Simple  Matching  Coefficient  (WSMC) adalah perhitungan  statistik  yang  hampir  sama  dengan Simple Matching  Coefficient yang  melakukan  perbandingan  untuk tiap  atribut  dengan  atribut  yang  lain,  namun  dalam implementasinya,  setiap  atribut  tidak  akan  dihitung  secara rata,  namun  dengan  memberikan  bobot  terhadap  tiap  atribut sehingga  secara  tidak  langsung  mengurangi  pengaruh  data yang  akan  mengacaukan  klasifikasi.  Metode  perhitungan  ini dapat  digunakan  secara  efektif  untuk  melakukan  klasifikasi terhadap  data  yang  bersifat  kategorik[3].  Pengukuran  jarak baru  akan  dinotasikan  dengan WSMC global dan WSMC local tergantung  dari  metode  pembobotan(global  atau  lokal)  yang digunakan.  Pada  metode  global,  atribut  dikaitkan  dengan vektor bobot ϖ = ( ω 1 , ... , ω d , ... , ω D ) dan jarak WSMC antara objek data x i dan x j diberikan pada persamaan ( 1) .

## Implementasi Nearest Neighbor pada Data Kategorik dengan Pembobotan Atribut Menggunakan Weighted Simple Matching Coefficient
Romario Wijaya, Nanik Suciati, dan Wijayanti Nurul Khotimah Departemen Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS)
e-mail : nanik@if.its.ac.id
P

## (1)
Dimana I (.) adalah  fungsi indikator dengan I ( true ) = 1 dan I ( false ) = 0, dan ω d adalah bobot unik  yang diberikan kepada atribut d yang akan dihitung berdasarkan dari Global Entropy ( GE )  dan Global  Gini  diversity  index ( GG ).  Dari  perspektif peringkat  fitur,  nilai Entropy dan Gini  diversity  index di  sini mengukur derajat kontribusi dari atribut dalam mendiskriminasikan  kelas training .  Secara  formal, Entropy dan Gini diversity index dapat dihitung dengan persamaan (3) dan (5) .
Pada  metode  lokal,  tujuannya  adalah  memberikan  bobot yang  didapat  berdasarkan  kelas  untuk  tiap  atribut,  yang mengindikasikan  kontribusi  yang  berbeda  oleh  tiap  atribut terhadap  kelas  yang  berbeda.  Pada  kasus  ini,  kelas  ke- m dikaitkan  dengan  vektor  bobot w m = ( w m1 ,  ...  , w md ,  ...  , w mD ) dengan 0 ≤ w md ≤ 1 untuk d = 1,2,...D. jarak SMC antara objek data x i dan x j berubah menurut persamaan (2).
(2)
Bobot  lokal  dapat  dihitung  juga  menggunakan  informasi Entropy dan Gini  diversity  index ,  seperti  pada  bobot  global, namun  dengan  menggunakan Local  Entropy ( LE )  dan Local Gini  diversity  index ( LG ).  Adapun LE dan LG didefinisikan dalam persamaan (9) dan (11) .
(3)
Dengan s d menotasikan  sebuah  kategori  ke- d ,  M  adalah jumlah kelas yang ada pada dataset dan
didefinisikan dengan persamaan (4).
(4)
Pada  persamaan  (4)  dilakukan  perhitungan  terhadap  tiap data yang pada kelas m yang memiliki atribut ke d bernilai s d dan dibagi dengan jumlah semua data yang memiliki atribut ke d bernilai s d . Persamaan  (3)  disebut Global  Entropy karena dihitung  menggunakan
yang  menyebabkan  nilainya unik  terhadap  tiap  kelas  yang  ada m. Hal  ini  menyebabkan persamaan  (5)  juga  disebut  sebagai Global  Gini  diversity index mengingat perhitungan juga menggunakan
.
(5) Dengan p(m|s d ) dihitung dengan persamaan (4). Perhitungan persamaan (3) dan (5) berpengaruh besar terhadap perhitungan Global  Weight ( ).  Apabila dihitung menggunakan GE akan  menghasilkan
yang  dapat dihitung  menggunakan  persamaan  (6),  sedangkan  apabila dihitung  menggunakan GG akan  menghasilkan
yang dapat dihitung menggunakan persamaan (8).
Pada  persamaan  (6)  dan  (8),  muncul  sebuah  variabel  baru yang  merupakan  derajat  pengaruh  atribut terhadap  semua  data  yang  digunakan.  Adapun
dapat
dihitung menggunakan persamaan (7).
(6) (7)
Dengan tr adalah training  dataset dan N menunjukkan jumlah data.
(8)
Sama  halnya  dengan  perhitungan  pada  GE  dan  GG, perhitungan  LE  dan  LG  pada  persamaan (9) dan (11) tidak jauh  berbeda.  Yang  memberikan  perbedaan  pada  metode Global  dan  Lokal  adalah  pada  perhitungan  derajat  kontribusi tiap  atribut  terhadap  tiap  kelas.  Pada  metode  Global, digunakan
yang  perhitungannya  melibatkan  semua data  yang  ada  pada  data training .  Berbeda  dengan  metode Global,  pada  metode  Lokal  dihitung  menggunakan yang tidak melibatkan semua data yang ada pada data training namun hanya  menghitung spesifik terhadap satu  kelas  khusus saja.
(9) Dengan didefinisikan dengan persamaan (10). (10) Dengan merupakan  kelas  ke-m  dan
adalah  jumlah sampel pada kelas ke-m.
(11)
Dengan p(s d |m) dihitung  menggunakan  persamaan  (10). Berbeda dengan pembobotan global, bobot lokal yang masing- masing  dihitung  dengan  persamaan (12) dan (13) tidak menggabungkan  nilai  dari  tiap-tiap LE dan LG yang  sudah dihitung  seperti  yang  dilakukan  pada  metode  global.  Pada pembobotan  lokal,  bobot  akan  dihitung  secara  berulang  kali terhadap  tiap LE dan LG, sehingga  akan  didapatkan  matriks bobot  yang  ukurannya  lebih  besar,  namun  menunjukkan hubungan  antara  sebuah  atribut  dengan  masing-masing kategori  label  kelas  secara  spesifik  dan  unik.  Contoh  bobot atribut yang didapatkan dapat dilihat pada Tabel 1 .
(12)
(13)
Tabel 1 . Contoh Tabel Bobot yang Didapatkan Attribu Attribu Attribu Attribu Attribu Attribu
te #1 te #2 te #3 te #4 te #5 te #6 WeightG E 0.5831 0.5685 0.5481 0.6075 0.5560 0.6225 WeightG G 0.5584 0.5526 0.5441 0.5946 0.5487 0.6019 WeightL EC1 0.3808 0.3704 0.3687 0.5323 0.3753 0.5381 WeightL EC2 0.6371 0.6271 0.3688 0.5336 0.3713 0.5396 WeightL EC3 0.3825 0.3729 0.3685 0.3801 0.3692 0.3824 WeightL EC4 0.6301 0.4651 0.3841 0.5338 0.5441 1 WeightL GC1 0.3793 0.3702 0.3686 0.4727 0.3757 0.4811 WeightL GC2 0.5611 0.5455 0.3687 0.4746 0.3715 0.4833 WeightL GC3 0.3799 0.3727 0.3684 0.3820 0.3694 0.3842 WeightL GC4 0.5502 0.4247 0.3821 0.4749 0.4899 1
B. k-Nearest Neighbor dengan WSMC k-Nearest  Neighbor dengan WSMC adalah  sebuah  metode pengembangan  dari  k-NN  dengan  SMC,  dimana  di  dalam k- Nearest  Neighbor dengan SMC ,  atribut  yang  ada  dihitung begitu  saja  dengan  bobot  yang  sama  rata.  Dalam pengembangan  metode  ini,  perhitungan  terhadap  jarak  antar atribut  tetap  menggunakan  SMC,  namun  dengan  tambahan pembobotan  untuk  tiap  atributnya,  sehingga  tiap  atribut memiliki  bobot  peran  yang  berbeda  dalam  menentukan  hasil klasifikasi  (lihat  persamaan  (1)  dan  (2).  Algoritma learning dapat  dilihat  pada Gambar  1. Algoritma  1 dan Gambar  2. Algoritma 2 . Pada Gambar  1. Algoritma  1 bobot  dari  tiap  atribut  akan dihitung  menggunakan  metode  global,  sehingga  bobot  yang dipakai adalah (jika  dipilih  fitur Entropy )  atau (jika  dipilih  fitur Gini  Diversity  index ).  Bobot  ω d yang  telah digantikan oleh atau selanjutnya akan digunakan untuk  melakukan  klasifikasi  dengan  cara  mengalikan  bobot atribut dengan jarak  yang sudah dihitung  menggunakan SMC untuk tiap atributnya.
Sedangkan  untuk Gambar  2. Algoritma  2 ,  bobot  dari  tiap atribut  akan  dihitung  menggunakan  metode  lokal,  sehingga bobot  yang  dipakai  adalah
(jika  dipilih  fitur Entropy ) atau (jika  dipilih  fitur Gini  Diversity  index ).  Berbeda dengan  metode  global,  pada  metode  lokal  bobot  yang terbentuk tidak hanya satu untuk tiap atribut, namun sejumlah label  kelas  yang  ada.  Hal  ini  dimaksudkan  agar  nantinya ketika data diklasifikasikan, bobot atribut yang dipakai adalah bobot atribut yang sesuai dengan karakter label kelas tertentu. Setelah  bobot  lokal  terbentuk,  dilakukan  proses  klasifikasi dengan  cara  mengalikan  jarak  yang  dihitung  menggunakan SMC  dengan  bobot  lokal  untuk  masing-masing  label  kelas. Adapun  secara  rinci, pseudocode k-Nearest  Neighbor  dengan WSMC dapat dilihat pada Gambar 3. Algoritma 3 .
Input: , dan GE atau GG yang ditentukan untuk metode pembobotan yang berbeda.
Output: ϖ = < ω 1 , ... , ω d , ... , ω D > begin for d=1 to D do
if GE yang dipilih then ω d ←
menggunakan (6) else ω d ←
menggunakan (8)
end end
Gambar 1. Algoritma 1 Global Weights Learning Algorithm GWLA
Input: , dan LE or LG yang ditentukan untuk metode pembobotan yang berbeda.
Output: w m = < w m1 , ... , w md , ... , w mD > begin for d=1 to D do if LE yang dipilih then
ϖ md ← menggunakan (12)
else ϖ md ← menggunakan (13) end
for d=1 to D do , sedemikian hingga || w m || 1 = 1. end end Gambar 2. Algoritma 2 Local Weights Learning Algorithm LWLA
Input : tr, konstanta nearest neighbors k , dan sampel tes z = (x,y)
Output : y, label kelas dari x Begin 1. Hitung WSMC (x, x i , w), jarak antara z dengan setiap sampel (x i ,y i ) ∈ tr; 2. Pilih NN z ⊆ tr, k set dari k sampel training terdekat terhadap z, dari segi jarak;
3. Output y = argmax m

## End
Gambar 3. Algoritma 3 k-NN dengan WSMC

## III. HASIL DAN DISKUSI UJI COBA
Data uji coba yang digunakan sebagai masukan adalah data tabel  dalam  format  .csv.  Adapun  isi  dari  tabel  adalah  atribut yang bersifat kategorik, diikuti dengan label kelas pada kolom terakhir.  Jumlah  data,  jumlah  atribut,  jumlah  kategori  atribut dan  jumlah  kategori  label  kelas  pada  dataset  uji  coba bervariatif  untuk  melakukan  uji  coba  karakteristik  masing- masing metode pembobotan.
Untuk  data  yang  digunakan  serta  parameter  jumlah  atribut dan  jumlah  kategori  label  kelas  dapat  dilihat  pada  Tabel  2. Adapun  untuk  dataset  selain  data  gerakan  tangan  didapatkan dari http://ftp.ics.uci.edu/pub/machine-learning-databases/ . Pengujian  ditujukan  untuk  mendapatkan  tingkat  akurasi  rata- rata  untuk  tiap  dataset.  Adapun  pengujian  dilakukan  dengan metode k-Fold  Cross  Validation .  Dengan  menggunakan metode  k-Fold  Cross  Validation  hasil  yang  didapatkan  dari pengujian  dapat  lebih  merata  dan  adil  untuk  tiap  datasetnya.
Uji coba juga dilakukan terhadap metode  k-NN dengan SMC tanpa  pembobotan  atribut  yang  diimplementasikan  pada MATLAB dan WEKA.
Hasil  uji  coba  ditampilkan  dalam  bentuk  tabel  dengan masing-masing  akurasi  untuk  tiap  dataset  dan  tiap  metode. Akurasi  paling  tinggi  ditunjukkan  dengan  tanda  bintang(*) pada dan dapat dilihat pada Tabel 3.
Tabel 2.
Data yang Digunakan untuk Uji Coba Data Set #Atrib ut (D) Contoh nilai atribut #Kelas (M) #Jumlah Data (N) Nursery 8 Recommended, priority, not_recom 5 12958 Cars 6 Vgood, good, 5more 4 1728 Gerakan Tangan 36 6, 7, 8 (kategorik) 10 150 Soybeans 35 3, 0, 2 (kategorik) 19 683 Vote 16 Y, N 2 435 Dhermatol ogy 34 0, 1, 2 (kategorik) 6 366 Tabel 3. Hasil Uji Coba Akurasi (%) Dataset GE- NN GG- NN LE- NN LG- NN k-NN SMC (Matlab) k-NN (WEKA) Nursery 72.45 72.76 76.92 77.31* 40.04 76.38 Cars 77.46 77.46 80.35* 79.77 64.74 74.77 Gerakan Tangan 90.50 90.50 93.50 97.00* 92.00 95.50 Soybeans 89.31 89.01 91.65* 90.62 88.72 91.22 Vote 91.95 92.18 92.41* 91.03 91.26 91.95 Dhermatology 92.34 91.80 95.90* 95.90* 90.43 95.35
Untuk setiap data, dari hasil uji coba yang sudah dilakukan, rata-rata  metode lokal  yang  memiliki tingkat akurasi rata-rata yang  tinggi.  Jika  dibandingkan  dengan  metode  lokal,  metode global  memiliki  tingkat  akurasi  yang  sedikit  lebih  rendah. Namun.  Dari  hasil  uji  coba  tersebut,  dapat  dilihat  bahwa metode  pembobotan  atribut  rata-rata  memiliki  tingkat  akurasi lebih  baik  dibandingkan  dengan  k-NN  tanpa  pembobotan atribut.
Metode  lokal  dapat  memiliki  tingkat  akurasi  yang  lebih tinggi  dibandingkan  dengan  metode  global,  dikarenakan  sifat dari  data  uji  coba  itu  sendiri.  Dalam  klasifikasi,  data  yang diberikan adalah data sebenarnya dari sebuah eksperimen atau uji  coba.  Yang  mana  setiap  label  kelas  sudah  memiliki  ciri tersendiri,  hal  ini  menyebabkan  persebaran  data  seakan-akan telah  memiliki  kelompok-kelompok  tersendiri.  Hal  ini menyebabkan  metode  lokal  lebih  unggul  mengingat  metode lokal  memberi  bobot  spesifik  untuk  tiap  label  kelas  yang berbeda. Hal ini dibuktikan dari beberapa data uji coba.
Seperti  pada  data Nursery dan Cars ,  metode  global cenderung  memiliki  tingkat  akurasi  yang  berselisih  jauh
dengan  metode  lokal.  Ini  karena  data Nursery dan Cars memiliki  jumlah  data  yang  cukup  banyak  namun  dengan jumlah  label  kelas  yang  sedikit.  Berbeda  dengan  performa untuk  data Soybeans ,  yang  memiliki  jumlah  kelas  cukup banyak namun jumlah data yang sangat sedikit, metode global dapat  memperkecil  selisih  ketertinggalannya  hingga  hanya sekitar  2%.  Hal  ini  dapat  memberikan  sedikit  gambaran tentang  bagaimana  karakteristik  tiap  metode  baik  itu  lokal maupun global.

## IV. KESIMPULAN DAN SARAN
Metode klasifikasi k-NN dapat lebih dimaksimalkan dengan menggunakan  pembobotan  atribut  baik  itu  global  maupun lokal.  Pemberian  bobot  kepada  k-NN  dapat  melalui  beberapa metode  perhitungan  yaitu Global  Entropy , Global  Gini Diversity , Local  Entropy ,  dan Local  Gini  Diversity . Berdasarkan  uji  coba  yang  telah  dilakukan,  apabila  diamati lebih lanjut, pemilihan metode perhitungan bobot menggunakan metode global atau lokal harus mempertimbangkan  bentuk  persebaran  data.  Metode  global kemungkinan lebih cocok untuk data berjumlah sedikit namun memiliki  label  kelas  yang  cukup  banyak  sehingga  tidak  ada data  yang  seakan-akan  telah  memiliki  kelompok  tersendiri seperti  data Soybeans atau  data  lain  yang  memiliki  jumlah label kelas lebih banyak, sedangkan metode lokal lebih cocok digunakan  pada  data  yang  berjumlah  banyak  dengan  label kelas  sedikit  sehingga  data  cenderung  berkelompok  dengan karakteristik  tiap  label  kelas  seperti  pada  data Nursery , Cars , dan Gerakan Tangan yang telah diuji cobakan sebelumnya.
Performa  metode  k-NN  dengan  pembobotan  atribut  dapat dikatakan  lebih  baik  di  dalam  hal  akurasi  dibandingkan dengan  metode  k-NN  tanpa  pembobotan  atribut.  Berdasarkan uji  coba  yang  telah  dilakukan  terhadap  beberapa  dataset sebelumnya,  terbukti  metode  k-NN  dengan  pembobotan atribut  memiliki  akurasi  yang  lebih  tinggi  dibandingkan dengan  metode  k-NN  normal  yang  dilakukan  tanpa pembobotan atribut.
Untuk penelitian selanjutnya, terdapat beberapa hal yang dapat diperbaiki.  Pertama,  perbaikan  dataset  sebelum  dilakukan training maupun testing untuk  menghilangkan missing  value atau reduksi dimensi dan menghilangkan noise ( Preprocessing ).  Kedua,  pemaksimalan  metode  klasifikasi dengan menggunakan metode perhitungan jarak yang lainnya. Ketiga,  penggunaan  metode  klasifikasi  yang  lain,  mengingat kompleksitas dari metode klasifikasi k-NN adalah cukup besar yaitu O(n 2 ).

## DAFTAR PUSTAKA
[1] “ k -nearest neighbors algorithm,” Wikipedia . Nov-2016.
[2] Wikipedia, “Instance-based learning,” Wikipedia , 2016. .
[3] L. Chen and G. Guo, “Nearest neighbor classification of categorical data by attributes weighting,” Expert Syst. Appl. , vol. 42, no. 6, pp. 3142–3149, Apr. 2015.