PENDAHULUAN Latar Belakang Klasifikasi merupakan salah satu bidang kajian pada machine learning. Klasifikasi adalah proses menemukan sekumpulan model atau fungsi yang menggambarkan dan membedakan konsep atau kelas-kelas data, dengan tujuan agar model tersebut dapat digunakan untuk memprediksi kelas dari suatu objek atau data yang label kelasnya tidak diketahui (Han & Kamber 2001). Voting Feature Intervals 5 merupakan algoritma klasifikasi yang bersifat supervised dan non-incremental. Algoritma Voting Feature Intervals dikembangkan sampai pada versi ke-5 (VFI5). Representasi dari algoritma tersebut berdasarkan teknik feature interval. Feature interval adalah suatu teknik dimana kelas-kelas diproyeksikan dalam nilai interval pada masingmasing feature (atribut) dari kelas tersebut secara terpisah. Algoritma VFI5 telah diterapkan oleh Güvenir, Demiroz dan Ilter (1997) pada penelitian diagnosis penyakit Erythemato-Squamous. Algoritma VFI5 membuat interval untuk setiap feature yang berupa range interval atau point interval. Untuk setiap interval, nilai vote untuk setiap kelas pada interval tersebut akan disimpan. Dengan demikian sebuah interval dapat merepresentasikan beberapa kelas dengan menyimpan nilai vote setiap kelas sehingga algoritma VFI5 tersebut dapat disebut sebagai Multi Class Feature Projection Based Algorithms (Demiroz 1997). Algoritma VFI5 membangun range interval dan point interval didasarkan pada nilai minimum dan maksimum suatu feature pada setiap kelas. Algoritma VFI5 dapat diterapkan pada berbagai jenis data, antara lain data kategori, data nominal ataupun data kontinu. Pada jenis data kontinu, nilai vote yang terkandung dalam range interval hanya diwakili oleh satu nilai. Selain itu panjang interval antara range interval satu dengan yang lainnya tidak selalu sama. Kedua hal ini dapat menyebabkan perbedaan representasi kelas pada
range interval tersebut. Contohnya pada suatu himpunan data tertentu, nilai vote dalam suatu range interval yang panjang, yang tidak hanya cukup diwakili oleh satu nilai dapat merepresentasikan lebih dari satu kelas. Permasalahan ini dapat menyebabkan turunnya tingkat akurasi klasifikasi algoritma VFI5. Untuk mengatasi permasalahan tersebut perlu dilakukan kembali penempatan point interval maupun range interval yang lebih merepresentasikan batas setiap kelas. Tujuan Tujuan dari penelitian ini adalah untuk mencari alternatif cara pengambilan nilai end point pada Algoritma Voting Feature Intervals 5. Penelitian ini dilakukan dengan cara menempatkan kembali point interval dan range interval. Ruang Lingkup Ruang lingkup penelitian yang dilakukan adalah sebagai berikut: 1
2 3
Penerapan Algoritma VFI5 dilakukan pada 3 data yaitu data Iris yang memiliki 3 kelas, data Wine yang memiliki 3 kelas dan data Ikan Koi (Tera 2008) yang memiliki 2 kelas. Data Ikan Koi berasal dari Departemen Perikanan IPB. Data Iris, Wine dan Glass didapatkan pada situs UCI Repository of Machine Learning Databases di ics.uci.edu. Semua data yang digunakan memiliki jenis data kontinu. Setiap feature (ciri) data memiliki bobot sama.
TINJAUAN PUSTAKA Klasifikasi Klasifikasi merupakan proses menemukan sekumpulan model (atau fungsi) yang menggambarkan dan membedakan konsep atau kelas-kelas data, yang bertujuan agar model tersebut dapat digunakan untuk memprediksi
kelas dari suatu objek atau data yang label kelasnya tidak diketahui (Han & Kamber 2001). Penelitian terdiri atas dua tahap, yaitu pelatihan dan klasifikasi. Pada tahap pelatihan, dibentuk sebuah model domain permasalahan dari setiap instance (data pelatihan) yang ada. Penentuan model tersebut berdasarkan analisis terhadap sekumpulan data pelatihan, yaitu data yang label kelasnya sudah diketahui. Pada tahap klasifikasi, dilakukan prediksi kelas dari instance (kasus) baru dengan menggunakan model yang telah dibuat pada tahap pelatihan (Güvenir et al. 1998). K-Fold Cross Validation Beberapa teknik memperkirakan generalisasi error telah dikembangkan, yaitu hold out, leave one out, cross validation, dan bootstrapping (Fu 1994). Validasi silang dan bootstrapping merupakan metode dalam memperkirakan generalisasi error berdasarkan “resampling” (Sarle 2004). Metode k-fold cross validation membagi sebuah himpunan contoh secara acak menjadi k himpunan bagian (subset) yang saling bebas, dengan ulangan sebanyak k-kali untuk pelatihan dan pengujian. Pada setiap ulangan, disisakan satu subset untuk pengujian dan subset lainnya untuk pelatihan (Fu 1994). Pada metode ini, data awal dibagi menjadi k subset atau “fold” yang saling bebas secara acak, yaitu S1,S2,S3,…,Sk, dengan ukuran setiap subset kira-kira sama. Pelatihan dan pengujian dilakukan sebanyak k kali. Pada iterasi ke-i subset Si diperlakukan sebagai data pengujian, dan subset lainnya diperlakukan sebagai data pelatihan. Jadi, pada iterasi pertama S2,…,Sk menjadi data pelatihan dan data S1 menjadi data pengujian. Pada iterasi kedua S1,S3,…,Sk menjadi data pelatihan dan data S2 menjadi data pengujian, dan seterusnya. Tingkat akurasi dihitung dengan cara membagi jumlah hasil klasifikasi yang benar dari k iterasi dengan jumlah semua instance pada data awal (Han & Kamber 2001).
Algoritma Voting Feature Intervals 5 (VFI5) Voting Feature Intervals adalah salah satu algoritma yang digunakan dalam pengklasifikasian data. Algoritma tersebut dikembangkan oleh Demiroz dan Güvenir pada tahun 1997. Algoritma Voting Feature Intervals merepresentasikan deskripsi sebuah konsep oleh sekumpulan interval nilai-nilai feature atau atribut. Demiroz dan Güvenir (1997) mengemukakan bahwa algoritma tersebut adalah algoritma yang supervised artinya memiliki target, dalam hal ini adalah kelas-kelas data dari kasus yang ada, dan bersifat non-incremental artinya semua instance pelatihan diproses secara bersamaan. Pengklasifikasian instance baru berdasarkan voting pada klasifikasi yang dibuat oleh nilai tiap-tiap feature secara terpisah. Algoritma Voting Feature Intervals yang dikembangkan sudah sampai pada versi yang ke-5 atau sering disebut VFI5. Algoritma VFI5 memiliki dua tahap yaitu pelatihan dan klasifikasi. Pada tahap pelatihan akan dibentuk interval untuk setiap feature yang berupa range interval atau point interval. Untuk setiap interval, nilai vote untuk setiap kelas pada interval tersebut akan disimpan. Dengan demikian sebuah interval dapat merepresentasikan beberapa kelas dengan menyimpan nilai vote setiap kelas sehingga algoritma VFI5 tersebut dapat disebut sebagai Multi Class Feature Projection Based Algorithms. Keunggulan algoritma VFI5 adalah algoritma tersebut cukup kokoh (robust) terhadap feature yang tidak relevan namun mampu memberikan hasil yang baik pada real-world datasets yang ada. VFI5 mampu menghilangkan pengaruh yang kurang menguntungkan dari feature yang tidak relevan dengan mekanisme votingnya (Güvenir 1998). Algoritma klasifikasi VFI5 mampu melakukan klasifikasi lebih cepat dibandingkan dengan algoritma nearest neighbor dan decision tree. VFI5 mampu menangani nilai feature yang
train(TrainingSet): begin for each feature f for each class c EndPoints[f] = EndPoints[f] find_end_points(TrainingSet,f,c); sort(EndPoint[f]); if f is linear for each end point p in EndPoints[f] form a point interval from end point p form a range interval between p and the next end point ≠ p else /*f is nominal*/ each distinct point in EndPoint[f] forms a point interval for each interval i on feature dimension f for each class c interval_class_count[f,i,c] = 0 count_instances(f,TrainingSet); for each interval i on feature dimension f for each class c interval_class_vote[f,i,c] =
_
_
,,
_
normalize interval_class_vote[f,i,c] * such that interval_class_vote[f,i,c] = I * end Gambar 1 Algoritma pelatihan VFI5 (Demiroz 1997) tidak diketahui (hilang) dengan cara mengabaikan nilai feature tersebut yang ada pada data pelatihan dan data pengujian, sedangkan pada algoritma nearest neighbor dan decision tree, nilai tersebut harus diganti. Demiroz dan Güvenir (1997) mengembangkan algoritma VFI5 menjadi dua tahap yaitu pelatihan dan klasifikasi. 1.
Pelatihan Langkah pertama pada tahap pelatihan adalah menemukan end point setiap feature f dari setiap kelas c. End point untuk feature linier, yaitu feature yang nilainya memiliki urutan atau bias dibandingkan tingkatannya, merupakan nilai minimum dan nilai maksimum feature tersebut. End point untuk feature nominal, yaitu feature yang nilainya tidak memiliki urutan dan tidak bias dibandingkan tingkatannya, merupakan semua
nilai yang berbeda yang ada pada feature kelas yang sedang diamati. Sebelum dibentuk interval, seluruh end point yang diperoleh untuk setiap feature linier diurutkan. Jika suatu feature merupakan feature linier maka akan dibentuk dua interval, yaitu point interval dan range interval. Jika feature tersebut merupakan feature nominal maka akan dibentuk point interval. Batas bawah pada range interval (ujung paling kiri) adalah -∞ sedang batas atas range interval (ujung paling kanan) adalah ∞. Jumlah maksimum end point pada feature linier adalah 2k sedangkan jumlah maksimum intervalnya adalah 4k + 1, dengan k adalah jumlah kelas yang diamati. Setelah itu, jumlah instance pelatihan setiap kelas c dengan feature f untuk setiap interval i dihitung dan direpresentasikan sebagai interval_class_count[f,i,c]. Untuk setiap instance
classify(e): /* e: example to be classified */ begin for each class c vote[c] = 0 for each feature f for each class c feature_vote[f,c] = 0 /* vote of feature f for class c */ if ef value is known i = find_interval(f,ef) feature_vote[f,c] = interval_class_vote[f,i,c] for each class c vote[c] = vote[c] + ( feature_vote[f,c] * weight[f] ) feature class c with highest vote[c] end Gambar 2 Algoritma klasifikasi VFI5 (Demiroz 1997) pelatihan dicari interval i,yaitu nilai feature f dari instamce pelatihan e(ef) tersebut berada pada interval i. Jika interval i merupakan point interval dan ef sama dengan batas bawah interval tersebut (sama dengan batas atas untuk point interval), jumlah instance tersebut (ef) pada interval i ditambah 1. Jika interval i merupakan range interval dan ef jatuh pada interval tersebut maka jumlah kelas instance ef pada interval i ditambah 1. Hasil proses ini merupakan vote kelas c pada interval i. Untuk menghilangkan efek perbedaan distribusi setiap kelas, vote kelas c untuk feature f pada interval i dinormalisasi dengan cara membagi vote tersebut dengan jumlah instance kelas c yang direpresentasikan dengan class_count[c]. Hasil normalisasi ini dinotasikan sebagai interval_class_vote[f,i,c]. Kemudian nilainilai interval_class_vote[f,i,c] dinormalisasi sehingga jumlah vote beberapa kelas pada setiap feature sama dengan 1. Normalisasi ini bertujuan agar setiap feature memiliki kekuatan voting yang sama pada proses klasifikasi yang tidak dipengaruhi oleh ukurannya. 2. Klasifikasi Proses klasifikasi diawali dengan inisialisasi vote setiap kelas dengan nilai nol. Untuk setiap feature f, dicari letak ef pada interval i tersebut berada, dengan ef merupakan nilai feature f dari
instance tes e. Jika ef tidak diketahui (hilang), feature tersebut tidak diikutsertakan dalam voting (memberikan vote nol untuk setiap kelas). Oleh karena itu, feature yang memiliki nilai tidak diketahui diabaikan. Jika ef diketahui maka interval tersebut dapat ditemukan. Interval tersebut dapat menyimpan instance pelatihan dari beberapa kelas. Kelas-kelas dalam sebuah interval direpresentasikan oleh vote kelas-kelas tersebut pada interval itu. Untuk setiap kelas c, feature f memberikan vote yang sama dengan interval_class_vote[f,i,c]. Notasi tersebut merepresentasikan vote feature f yang diberikan untuk kelas c. Setiap feature f mengumpulkan vote-votenya dalam sebuah vektor (feature_vote[f,C1],…, feature_vote[f,Cj],…,feature_vote[f,Ck]), dengan feature_vote[f,Cj] merupakan vote feature f untuk kelas Cj dan k adalah jumlah kelas. Kemudian d vektor vote, dengan d merupakan jumlah feature, dijumlahkan untuk memperoleh total vektor vote (vote[C1],…,vote[Ck]). Kelas dengan jumlah vote terbesar diprediksi sebagai kelas dari instance tes e. Pseudocode algoritma pelatihan dan klasifikasi VFI5 dapat dilihat pada gambar 1 dan 2.
Desil Persentil (percentile) ke-p (untuk nilai p antara 0 hingga 100) dari sebuah sampel adalah membagi sampel sehingga p% dari nilai sampel berada di bawah persentil ke-p dan (100-p)% di atas persentil ke-p (Navidi 2006). Desil (Desil) merupakan variasi lain dari kuartil (quartile) ataupun persentil yang juga merupakan metode pengubahan range. Sebagai contoh, nilai desil pertama (D1) yang juga merupakan persentil ke-10 (P10) terdapat pada penelusuran sampel ke-[(n + 1)/10], nilai desil kedua (D2) atau persentil ke-20 (P20) terdapat pada penelusuran ke-[2(n + 1)/10] dan begitu seterusnya (Fleming & Nellis 1994).
•
d adalah jumlah instance kelas 2 yang berhasil diprediksi dengan benar sebagai kelas 2.
METODE PENELITIAN Penelitian ini melalui beberapa tahapan proses untuk menganalisa peningkatan kinerja algoritma VFI5. Tahapan proses tersebut disajikan pada Gambar 3.
Confusion Matrix Confusion matrix mengandung informasi tentang kelas data yang aktual direpresentasikan pada baris matriks dan kelas data hasil prediksi suatu algoritma direpresentasikan pada kolom matriks klasifikasi. Kemampuan dari algoritma klasifikasi biasanya dievaluasi dari data yang ada pada matriks. Pada Tabel 1 disajikan confusion matrix untuk data dengan dua kelas (Kohavi & Provost 1998 diacu dalam Hamilton 2002). Tabel 1 Confusion matrix data dengan dua kelas. Prediksi Data Kelas 1 Kelas 2 Kelas 1 a b Aktual Kelas 2 c d
Gambar 3 Tahapan penelitian
Keterangan :
Tahapan yang utama adalah tahapan pelatihan untuk melihat model dan domain permasalahan data dan klasifikasi untuk menduga kelas dari data pengujian.
•
Data
•
•
a adalah jumlah instance kelas 1 yang berhasil diprediksi dengan benar sebagai kelas 1, b adalah jumlah instance kelas 1 yang tidak berhasil diprediksi dengan benar karena diprediksi sebagai kelas 2, c adalah jumlah instance kelas 2 yang tidak berhasil diprediksi dengan benar karena diprediksi sebagai kelas 1,
Data yang digunakan sebanyak 3 data yaitu data Iris, data Wine dan data Ikan Koi (Tera 2008) yang berasal dari Departemen Perikanan IPB. Data Iris dan Wine didapatkan dari UCI Repository of Machine Learning Databases, anonymous ftp dari www.ics.uci.edu dalam direktori pub/machine-learning-databases.
