Pengklasifikasi Berdasarkan Optimisasi Fungsi Harga (Cost Function) Rachmawati, 06902,TE Jurusan Teknik Elektro dan Teknologi Informasi, FT UGM, Yogyakarta
2.1 PENDAHULUAN Bab ini berkaitan dengan teknik - teknik dan algoritma yang “membebaskan” dari dasar pemikiran teori keputusan Bayes. Fokusnya adalah pada desain langsung sebuah fungsi diskriminan/ decision surface yang memisahkan kelas-kelas menjadi beberapa pilihan berdasarkan kriteria yang di adopsi (digunakan). Teknikteknik yang dibangun disekitar pengklasifikasi Bayesian yang optimal bergantung pada estimasi fungsi pdf menggambarkan distribusi data dalam setiap kelas. Namun, secara umum ini ternyata menjadi tugas yang sulit, terutama dalam ruang dimensi tinggi. Sebagai alternatif, dapat difokuskan pada merancang permukaan keputusan yang memisahkan kelas-kelas secara langsung dari kumpulan data pelatihan, tanpa harus menyimpulkan itu dari pdfs. Hal ini merupakan permasalahan yang lebih mudah, dan meskipun solusinya mungkin tidak sesuai dengan pengklasifikasi (Bayesian) yang optimal, dalam praktek,dimana ukuran dari set data pelatihan dibatasi, ternyata sering menghasilkan kinerja yang lebih baik dibandingkan pengklasifikasi Bayesian jika kemudian digunakan perhitungan yang melibatkan pdfs. Pembaca yang tertarik dapat menemukan lebih banyak komentar terkait pada [Theo 09,Bagian 10.5.2]. Kita mulai dengan kasus sederhana perancangan pengklasifikasi linier, dideskripsikan dengan persamaan:
Dapat juga ditulis sebagai:
Daripada bekerja dengan hyperplane dalam ruang
, kita bekerja dengan hyperplane dalam ruang
yang melalui origin (titik asal). Hal ini hanya untuk penyederhanaan notasi. Sesudah w’ dihitung, sebuah x diklasifikasi ke kelas ω1(ω2 ) jika:
Untuk pengklasifikasi 2-kelas. Dengan kata lain, pengklasifikasi ini menghasilkan decision surface hyperplane, titik –titik yang terletak pada satu sisi itu diklasifikasi untuk ω1 dan titik-titik yang terletak pada
sisi lain diklasifikasikan sebagai ω2. Agar lebih sederhana, notasi w,x,;vektor-vektor tersebut diasumsikan untuk dapat ditambahkan dengan w0 dan 1,dan berada di ruang
.
Gambar 2.1 (a) Pengklasifikasi 2 kelas yang dapat dipisahkan secara linier (b)-(c) permasalahan pengklasifikasi 2-kelas yang tidak dapat dipisahkan secara linier. 2.2
ALGORITMA PERCEPTRON
Algoritma perceptron sesuai untuk masalah 2-kelas dan untuk kelas-kelas yang terpisah secara linier (linearly separable). Gambar 2.1(a) menunjukkan sebuah contoh kelas-kelas yang dapat dipisahkan secara linier. Algoritma perceptron menghitung nilai-nilai bobot-bobot w dari pengklasifikasi linier, yang memisahkan dua kelas. Algoritma adalah iteratif. Dimulai dengan perkiraan awal dalam perluasa (l+1)-ruang dimensi dan konvergen terhadap sebuah penyelesaian dengan jumlah langkah iterasi yang terbatas. Solusi w mengklasifikasi secara benar semua titik-titik pelatihan (dengan asumsi,tentu saja, bahwa mereka berasal dari kelas yang dapat dipisahkan secara linier). Mulai dari kondisi awal yang berbeda, hasil hyperplane yang berbeda. Pembaruan pada langkah iterasi ke-t memiliki bentuk sederhana :
Dimana w ditambah (augmented) dengan vector w0, Y adalah himpunan sampel-sampel yang salah diklasifikasikan oleh estimasi w(t),δx adalah -1 jika x Є ω1 dan +1 jika x Є ω2, dan ρt adalah parameter yang ditentukan oleh user yang mengendalikan kecepatan konvergensi dan harus mematuhi persyaratan tertentu untuk menjamin konvergensi ( sebagai contoh, ρt dapat dipilih konstan, ρt = ρ). Algoritma konvergen pada saat Y menjadi kosong. Setelah pengklasifikasi (classifier) dihitung, sebuah titik,x, diklasifikasikan ke salah satu dari dua kelas tergantung pada hasil operasi berikut:
Fungsi f(.) dalam bentuk yang paling sederhana adalah step atau sign function (f(z) = 1 if z > 0; f(z) = -1 jika z < 0). Namun, mungkin memiliki bentuk lain; sebagai contoh, output dapat berupa 1 atau 0 untuk z > 0 dan z < 0. Secara umum, ini dikenal sebagai fungsi aktivasi. Model dasar jaringan, dikenal sebagai perceptron atau neuron, yang mengimplementasi operasi pengklasifikasian yang tersirat pada persamaan (2.1), ditunjukkan pada Gambar 2.2. Untuk menjalankan algoritma perceptron, ketik: [w,iter,mis_clas] = perce(X,y,w_ini,rho) dimana X adalah (l+1) x N matriks yang terdiri dari (augmented-by-1) vektor pelatihan sebagai kolom. y adalah vector N-dimensi, dimana komponen ke-i nya adalah label kelas dari vektor fitur masingmasing ( -1 atau +1), w_ini adalah perkiraan awal w, rho adalah (konstan) kecepatan pembelajaran, w adalah vektor yang dihitung dengan algoritma, iter adalah jumlah iterasi yang dikerjakan, mis-clas adalah jumlah vektor misclassified ( tidak bernilai nol jika iterasi mencapai 20000, yang mengindikasikan bahwa algoritma tidak konvergen dan permasalahan tidak dapat dipisahkan secara linier, selain itu 0).
Gambar 2.2 Struktur Perceptron
Contoh 2.2.1 Buatlah empat data set 2-dimensi Xi, i = 1,…,4, masing-masing berisi data vektor dari dua kelas. Dalam semua Xi kelas pertama (dinotasikan -1) berisi 100 vektor terdistribusi merata dalam square [0,2] x [0,2]. Kelas kedua (dinotasikan +1) berisi 100 vektor lainnya yang terdistribusi dalam square [3,5] x [3,5],[2,4] x [2,4],[0,2] x [2,4], dan [1,3] x [1,3] untuk X1,X2,X3, dan X4. Setiap data vektor di tambahkan dengan koordinat ketiga yang sama dengan 1. Lakukan langkah-langkah berikut: 1. Plot keempat set data dan perhatikan bahwa kita bergerak dari X1 ke X3 kelas-kelas saling berdekatan tetapi tetap terpisah secara linier. Dalam X4 dua kelas overlap. 2. Jalankan algoritma perceptron untuk setiap Xi, i = 1,…,4, dengan parameter kecepatan belajar 0.01 dan 0.05 dan perkiraan awal untuk parameter vector [1,1,-0.5]T. 3. Jalankan algoritma perceptron untuk X3 dengan kecepatan belajar 0.05 menggunakan perkiraan awal untuk w [1,1,-0.5]T dan [1,1,0.5]T. 4. Komentar pada hasil. Solusi. Untuk mempertahankan reproduktifitas hasil, pembangkit nilai random MATLAB untuk distribusi uniform diinisialisasi menggunakan seed nilai 0. Ini diperoleh dengan mengetik rand(‘seed’,0) Untuk menghasilkan set data X1 serta vector yang berisi label kelas dari titik-titik di dalamnya, ketik
Data set yang tersisa dapat dihasilkan dengan mengulangi kode sebelumnya dimana baris ketiga digantikan dengan :
Kemudian, lakukan hal berikut: Langkah 1. Untuk plot X1, dimana titik-titik dari kelas yang berbeda dinotasikan dengan warna yang berbeda, ketik
Langkah 2. Untuk menjalankan algoritma perceptron untuk X1 dengan parameter pembelajaran 0.01, ketik
Dengan mengubah kode sebelumnya, algoritma perceptron dapat dilakukan pada data yang tersisa menggunakan nilai parameter pembelajaran yang berbeda. Table 2.1 berisi hasil-hasil yang diperoleh dari eksperimen sebelumnya. Langkah 3. Lakukan seperti di langkah 2, hitung w menggunakan algoritma perceptron untuk perkiraan awal [1,1,-0.5]T dan [1,1,0.5]T. hasilnya adalah [-0.0002, 0.5364, -1.0725]T dan [-0.0103, 0.3839, 0.7525]T Berdasarkan hasil-hasil sebelumnya, dapat ditarik 3 kesimpulan umum : Pertama,untuk parameter pembelajaran yang tetap, jumlah iterasi (secara umum) meningkat sebagaimana kelas-kelas saling bergerak mendekat ( yakni, permasalahan menjadi lebih sulit). Kedua, algoritma gagal untuk konvergen untuk data set X4, dimana kelas tidak terpisah secara linier ( berjalan untuk jumlah maksimum yang diijinkan dari iterasi yang telah ditentukan). Ketiga, perkiraan awal yang berbeda untuk w dapat menyebabkan estimasi akhir yang berbeda (meskipun semua optimal dalam arti bahwa mereka memisahkan data pelatihan dua kelas).
2.2.1 Bentuk Online Algoritma Perceptron Bentuk algoritma perceptron yang telah dijelaskan dikenal sebagai bentuk batch ; pada setiap langkah iterasi,semua data point dipertimbangkan dan sebuah pembaruan dilakukan setelah semua data selesai diproses sebuah pembaruan dapat dilakukan setelah mempertimbangkan setiap point. Setiap kumpulan dari N iterasi berturut-turut,dimana setiap data point telah dipertimbangkan, dikenal sebagai sebuah epoch. Pembaruan algoritmik dilakukan menurut skema berikut:
dimana ρ adalah parameter yang mengendalikan konvergensi, dan x(t) menunjukkan point yang dipertimbangkan dalam iterasi ke- t. Label kelas y(t) sama dengan -1 dan +1 untuk dua kelas ω1 dan ω2.
Pseudocode untuk skema ini diberikan sebagai berikut: 1. Pilih w(0); biasanya w(0) = 0 2. Pilih ρ 3. Pilih max_iter ( Jumlah iterasi maksimum) 4. t = 0 5. Ulangi
6. Sampai count_miscl = 0 or ( t>= max_iter) Contoh 2.2.2 Jalankan versi online dari algoritma perceptron untuk data set pada contoh 2.2.1, dengan parameter belajar 0.01 dan 0.05 dan sebuah perkiraan awal untuk parameter vektor [1,1,-0.5]T. Berikan komentar pada hasil. Solusi. Ulangi code yang diberikan pada contoh 2.2.1, sekarang fungsi perce diganti dengan fungsi perce_online. (Jumlah iterasi maksimum di atur 107. Jumlah yang besar ini diperlukan pada saat kelas-kelas sangat dekat satu dengan lainnya). Hasil yang diperoleh setelah melakukan percobaan diberikan dalam Tabel 2.2. Sekali lagi, semakin dekat kelas, semakin banyak iterasi yang dibutuhkan untuk konvergen. Selain itu, konvergensi tidak terjadi untuk kumpulan data yang berisi kelas-kelas yang tidak terpisah secara linier (not linearly separable).
2.3 THE SUM OF ERROR SQUARE CLASSIFIER ( JUMLAH KUADRAT KESALAHAN PENGKLASIFIKASI ) Tujuan pada bagian ini tetap sama : untuk memperkirakan parameter-parameter vector,w, dalam perluasan ruang dari classifier linier (hyperplane), wT x = 0 dimana x adalah fitur vektor (augmented by-1). Namun, dalam bagian ini,asumsi keterpisahan linier tidak dibutuhkan. Metode ini juga dikenal sebagai Least Square (LS), mengestimasi pengklasifikasi linier terbaik, dimana istilah “terbaik” sesuai dengan w yang meminimalkan nilai:
dimana yi adalah label kelas yang diketahui dari xi, i = 1,2,3,…,N ; dan N adalah jumlah point pelatihan.
Hal ini dapat ditunjukkan bahwa estimasi LS diberikan oleh:
Matriks ( XTX)-1XT juga dikenal sebagai pseudoinverse dari X dan dinotasikan sebagai X# [Theo 09, Bagian 3.4.3]. Keuntungan yang signifikan dari metode LS adalah bahwa ia mempunyai solusi tunggal (sesuai dengan single minimum J(w). Selain itu, ini diperoleh dengan menyelesaikan sebuah persamaan system linier (persamaan(2.3)). Dalam praktek, inverse dari matriks ( l+1 ) x ( l + 1), XTX, dapat menyebabkan beberapa kesulitan numerik, khususnya dalam ruang dimensi tinggi. Dalam kasus tersebut, dapat ditambahkan konstanta positif kecil di sepanjang diagonal utama dan menyelesaikan sistem:
dimana I adalah matriks identitas ( l+1 ) x ( l + 1), dan C adalah konstanta positif kecil yang ditetapkan user. Hal ini dapat ditunjukkan [Theo 09, Bagian 4.19.2] bahwa persamaan (2.4) adalah minimize dari versi regular dari nilai pada persamaan (2.2), atau
Untuk mendapatkan solusi LS gunakan fungsi:
dimana X,y didefinisikan sebagai fungsi perce C adalah parameter yang termasuk dalam persamaan (2.4) w adalah estimator LS dihasilkan oleh fungsi. Perhatikan bahwa versi original (nonregularized) dari classifier LS diperoleh untuk C = 0. Contoh 2.3.1 1. Menghasilkan sekumpulan X1 dari N1 = 200 vektor data, 100 stem vektor pertama dari kelas ω1, yang dimodelkan dengan distribusi Gaussian dengan mean m1 = [0,0,0,0,0]T. Stem selanjutnya dari ω2, yang dimodelkan dengan distribusi Gaussian dengan mean m2 = [1,1,1,1,1]T. Kedua distribusi berbagi matriks kovarians berikut:
Bangkitkan data set tambahan X2 dari N2 = 200 data vector, berikut prescription yang untuk X1. Aplikasikan classifier Bayes pada X2 dan hitung kesalahan pengklasifikasi.
digunakan
2. Tambahkan setiap fitur vector dalam X1 dan X2 dengan menambahkan 1 sebagai koordinat akhir. Definisikan label kelas sebagai -1 dan +1 untuk dua kelas. Gunakan X1 sebagai training set, aplikasikan fungsi SSErr MATLAB (dengan C = 0) untuk memperoleh LS estimasi ŵ. Gunakan estimasi ini untuk klasifikasi vector-vektor X2 sesuai dengan ketidaksamaan
Hitung probabilitas error. Bandingkan hasil dengan hasil yang diperoleh pada langkah 1. 3. Ulangi langkah sebelumnya, pertama dengan X2 diganti dengan sekumpulan X3 berisi N3 = 10,000 vektor data dan kemudian dengan satu set X4 berisi N4 = 100,000 vektor data. X3 dan X4 dihasilkan menggunakan prescription yang diadopsi dari X1. Komentari hasil. Solusi. Lakukan langkah berikut: Langkah 1. Untuk memastikan reproduktifitas hasil, set seed = 0 untuk fungsi randn MATLAB untuk pembangkitan X1; untuk X2,X3,X4 set seed = 100. Atur parameter-parameter Gaussian model dua kelas dengan mengetik:
Untuk menghasilkan X1 dan label kelas yang dibutuhkan (1 untuk ω1, 2 untuk ω2), ketik
X2 dihasilkan dengan cara yang serupa, Untuk menghitung kesalahan pengklasifikasin Bayesian pada X2, ketik:
Kesalahan (Error) adalah 14%. Langkah 2. Untuk menambah vector data X1 dengan sebuah koordinat tambahan yang sama dengan +1, dan untuk merubah label kelas dari 1,2 (digunakan sebelumnya) menjadi -1, +1, ketik:
Set X2 diperlakukan serupa. Untuk menghitung kesalahan pengklasifikasi dari pengklasifikasi LS berdasarkan X2, ketik :
Error adalah 15%. Step 3. Dengan mengganti X2 dengan X3 dan X4, dan mengaplikasikan code yang diberikan pada step 1 dan 2, hasil ditunjukkan pada Tabel 2.3.
Dari tabel dapat dilihat bahwa kesalahan klasifikasi dari LS classifier sangat dekat dengan Bayesian classifier. Hal ini dibuktikan dengan fakta bahwa pengklasifikasi keputusan yang optimal untuk permasalahan tersebut adalah linier [Theo 09, Bagian 2.4.2]. Perhatikan bahwa karena kesalahan klasifikasi dari dua pengklasifikasi dihitung dengan lebih akurat ( yakni, sebagai jumlah vector dalam test set meningkat),mereka lebih dekat satu dengan lainnya. Hal ini menunjukkan pentingnya mempunyai jumlah data set yang banyak tidak hanya untuk pelatihan tetapi juga untuk pengujian. Contoh 2.3.2 Bangkitkan satu set N1= 1000 vektor data dimana 500 stem pertama dari kelas ω1 dimodelkan dengan distribusi Gaussian dengan mean m1 = [0,0,0,0,0,]T dan stem sisanya dari kelas ω2 dimodelkan dengan distribusi Gaussian dengan mean m2 = [2,2,0,2,2]T. Distribusi keduanya mengikuti matriks kovarians
Setiap vector data ditambahkan dengan enam koordinat , yang sama dengan +1 untuk semua vector. Biarkan X1 menjadi matriks (l+1) x N yang kolumnya adalah vector dari data set (untuk reproduktifitas hasil, set seed = 0 untuk fungsi randn MATLAB). Selain itu, bangkitkan satu set X2 yang terdiri dari 10,000 point, gunakan prescription diikuti untuk X1 ( untuk reproduktifitas hasil, atur seed = 100 untuk fungsi randn MATLAB).
1. Hitung jumlah kondisi dari matriks X1XT ( semakin besar jumlah kondisi, matriks semakin mendekati singularitas). Jalankan versi original (nonregularized) dari pengklasifikasi LS (Persamaan.(2.3)) untuk estimasi w. 2. Ulangi langkah 1 untuk versi regularized (pers.(2.4)) dari pengklasifikasi LS untuk C = 0.1. 3. Komentari hasil yang diperoleh pada langkah 1 dan 2. 4. Estimasi kesalahan klasifikasi bersama dengan hasil w dari langkah 1 dan 2 berdasarkan data set X2. Solusi. Untuk membangkitkan matrik X1, ketik :
Dengan cara yang sama, hasilkan X2. Lakukan langkah berikut: Langkah 1. Untuk menghitung jumlah kondisi X1 X1T dan vector solusi w untuk versi original dari pengklasifikasi LS, ketik :
Langkah 2. Ulangi langkah 1 untuk pengklasifikasi LS versi regularized, ketik:
Langkah 3. Amati bahwa jumlah kondisi X1 X1T (1.4767 x 1017) adalah urutan dari magnitude lebih besar dari X1 X1T + CI (9.3791 x 104), dimana I adalah matriks identitas ( l + 1 ) x ( l + 1 ). Dalam versi original ( C= 0 ), dan untuk Precision MATLAB yang sekarang, X1 X1T adalah singular dan tidak dibutuhkan estimasi w, karena system linier (Pers(2.3)) tidak dapat diselesaikan. Sebaliknya, versi regularized, X1 X1T + CI invertible dan diperoleh estimasi w, yakni [ -0.2158, -0.1888, 0, -0.2178, 0.1851, 0.8012]T. Langkah 4. Hitung kesalahan klasifikasi pada X2 untuk w yang diberikan dengan mengetik
Untuk pengklasifikasi LS versi regularized, kesalahan klasifikasi sama dengan 2.67%. 2.3.1 Pengklasifikasi LS Multiclass Asumsikan kita diberikan sekumpulan N point data pelatihan, xi Є , I = 1,2,….,N, dan asumsi bahwa ini dimulai dari kelas c >2. Tujuan adalah untuk merancang sebuah pengklasifikasi yang terdiri dari fungsi diskriminan linier c ( satu untuk setiap kelas):
Design berdasarkan pada kriteria LS. Aturan klasifikasi adalah sebagai berikut : untuk x yang diberikan, klasifikasikan ke kelas ω1 jika
Mengikuti rationale dijelaskan dalam (Theo,09, Bagian 3.4.1], kita merancang fungsi linier c sebagai berikut: Untuk setiap xi, tentukan label kelas vector c-dimensional.
Element ke j, yij adalah 1 jika xi Є ωj, dan 0 untuk yang lain. Estimasi ωj dan ωj0 untuk memperkecil nilai :
Dalam hal ini, setiap harus menyelesaikan c masalah LS, satu untuk setiap kelas. Harus ditegaskan bahwa label kelas berhubungan dengan setiap point pelatihan adalah berbeda untuk setiap satu dari masalah c bergantung pada apakah point merupakan bagian kelas yang berurutan atau tidak. Lebih spesifik, dalam masalah LS ke j, label kelas adalah 1 untuk setiap point dari kelas ke-j dan 0 untuk point dari seluruh kelas-kelas yang lain. Perhatikan bahwa setiap hyperplane, wj, dilatihkan, sehingga idealnya semua point dari kelas ωj terletak pada salah-satu sisinya dan semua titik yang lain terletak pada sisi (bagian) yang lain. Untuk menyelesaikan setiap satu dari masalah c LS, kita mengikuti prosedur yang sama untuk persamaan (2.2). Seperti sebelumnya, threshold wj0 ditempatkan pada masing-masing wj dengan memperluas dimensi dari ruang fitur dengan satu.
Contoh 2.3.3 1. Pertimbangkan sebuah masalah klasifikasi 3-kelas yang terdiri dari tiga kelas ω1, ω2, ω3. Kelas dimodelkan dengan distribusi Gaussian dengan means m1 = [1,1,1]T, m2 = [5,3,2]T, dan m3 = [3,3,4]T. Semua distribusi menggunakan matriks kovarians yang sama:
Hasilkan dan plot dua set data, X1 (training set) dan X2 (test set), yang masing-masing terdiri dari 1000 dan 10,000 vektor data. Apply fungsi SSErr MATLAB pada X1 untuk memperkirakan parameter vector w1,w2,w3 dari tiga fungsi diskriminant linier dalam perluasan ruang 4-dimensi. Gunakan set X2 untuk menghitung probabilitas error. 2. Dari teori [Theo 09, Bagian 3.5.2],diketahui kriteria LS, jika digunakan 0.1 sebagi nilai respon yang diinginkan ( label kelas ), menyediakan estimasi LS dari probabilitas berikutnya; jika wj adalah estimasi LS dari vektor parameter dari fungsi diskriminan linier ke-j, maka:
dan estimasi LSnya, gj (xi). j = 1,….,c, i = Untuk menguji, hitung probabilitas sebenarnya 1,….,N2,pada vector X2 (N2 adalah jumlah vector dalam X2). Kemudian hitung kuadrat error rata-rata dari estimasi menggunakan gj (xi). 3. Hitung error klasifikasi dari (optimal) pengklasifikasi Bayesian pada X2 dan bandingkan dengan hasil pengklasifikasi LS pada langkah 1. Petunjuk Ingat bahwa
dimana
dengan P(ωi) merupakan probabilitas awal kelas ωi .
Solusi. Lakukan Langkah berikut Langkah 1. Untuk memastikan reproduktifitas hasil, inisialisasi fungsi randn MATLAB menggunakan nilai seed 0 untuk X1 dan 100 untuk X2. Untuk menghasilkan X1, ketik :
Untuk plot data set X1, gunakan warna berbeda untuk point pada kelas yang berbeda, ketik :
Gunakan tombol Rotate 3D untuk melihat data set dari sudut berbeda. Berikutnya, tentukan c x N1 dimensional matrik z1, setiap kolom yang berkoresponden terhadap satu training point. Secara spesifik, elemen ke-i kolomnya sama dengan nol kecuali satu, yang sama dengan unity. Posisi akhir menunjukkan kelas dimana koresponden vector xi dari Xi berada.
Dengan cara yang sama, hasilkan X2 dan z2. Untuk estimasi parameter vektor dari 3 fungsi diskriminan, ketik :
Dalam matriks ( l + 1) x c w_all, kolom ke-i berkoresponden ke parameter vektor ke-i fungsi diskriminant. Untuk menghitung error klasifikasi menggunakan set X2, ketik :
Kesalahan klasifikasi dalam kasus ini adalah 5.11 % ( diestimasi berdasarkan X2). Langkah 2. Untuk menghitung perkiraan probabilitas berikutnya sebagai hasil dari framework pengklasifikasi LS, ketik :
Untuk menghitung probabilitas berikutnya yang sebenarnya, ketik pernyataan berikut:
Untuk menghitung kuadrat error rata-rata dalam perkiraann ketik
dengan menggunakan
Error adalah 0.0397. Perhatikan bahwa ini adalah sangat kecil, menunjukkan estimasi yang bagus.
,
Langkah 3. Untuk menghitung error pengklasifikasi Bayesian, dengan posteriori probabilities sebenarnya diketahui, ketik :
Sebagai alternatif, gunakan fungsi MATLAB bayes_classifier. Kesalahan klasifikasi untuk kasus ini adalah 4.82% ( diestimasi berdasarkan X2). Latihan 2.3.1 1. Pertimbangkan setup contoh 2.3.3 dimana sekarang means dari 3 kelas ω1, ω2, ω3 adalah m1 = [0,0,0]T, m2 = [1,2,2]T, dan m3 = [3,3,4]T. Apply fungsi SSErr MATLAB pada data set X1 untuk estimasi parameter vektor w1,w2,w3 dari tiga fungsi diskriminant linier, dalam perluasan ruang 4dimensi. Gunakan set X2 untuk menghitung probabilitas error. 2. Hitung error klasifikasi dari (optimal) pengklasifikasi Bayesian pada X2 dan bandingkan dengan dengan hasil pengklasifikasi LS pada langkah 1. 2.4
SUPPORT VECTOR MACHINES: KASUS LINIER
Perlakuan Anaitis dan derivasi dari rumus terkait untuk pengklasifikasi SVM terdapat di [Theo 09, Bagian 3.7]. di sini, Selain fungsi MATLAB, kami menyediakan beberapa petunjuk berkaitan dengan pemahaman dasar pemikiran SVM. Inti design pengklasifikasi SVM adalah gagasan tentang margin. Pertimbangkan pengklasifikasi linier
Margin adalah daerah anatara dua hyperplane parallel
Hal ini dengan mudah ditunjukkan [Theo 09, Bagian 3.2] bahwa jarak Euclidean dari setiap point yang terletak pada dua hyperplane pada persamaan (2.7) dari pengklasifikasi hyperplane diberikan oleh 1 persamaan (2.6) adalah sama dengan , dimana . menunjukkan Euclidean norm. w Sebuah pertanyaan kadang-kadang diangkat oleh seorang pendatang baru dalam bidang ini adalah mengapa margin didefinisikan oleh kedua “magic” angka +1 dan -1. Jawabannya adalah bahwa ini bukan masalah. Mari kita pertimbangkan sebuah hyperplane dalam ruang- sebagai contoh, persamaan (2.6), seperti ditunjukkan Gambar 2.3 dengan garis penuh dan dua parallel ke hyperplane nya (garis putu-putus) Parameter d dapat berupa nilai berapapun, yang berarti bahwa kedua bidang dapat saling berdekatan atau berjauhan. Tetapkan nilai d dan bagi kedua bagian persamaan sebelumnya dengan d, kita dapatkan ± 1 pada sisi kanan. Bagaimanapun, arah dan posisi dalam ruang dari dua hyperplane tidak berubah. Aplikasi yang sama untuk hyperplane dideskripsikan dengan persamaan (2.6). Normalisasi dengan sebuah nilai d konstan tidak berdampak terhadap titik-titik yang terletak pada (dan menetapkan) sebuah hyperplane.
Sejauh ini, kita telah mempertimbangkan bahwa error adalah “committed” dengan sebuah titik jika itu adalah pada sisi yang salahdari permukaan keputusan yang dibentuk pengklasifikasi masing-masing. Sekarang kita akan menjadi lebih bersyarat. Tidak hanya titik-titik yang berada pada sisi yang salah dari pengklasifikasi yang berkontribusi terhadap fungsi kesalahan perhitungan (error-counting function), melainkan juga setiap titik yang terletak di dalam margin, bahkan jika terletak pada sisi yang benar dari pengklasifikasi. Hanya titik-titik yang terletak di luar margin dan pada sisi yang benar dari pengklasifikasi yang tidak berkonstribusi terhadap error-counting cost. Gambar 2.4 menunjukkan dua kelas yang overlapping dan dua pengklasifikasi linier yang masing-masing digambarkan dengan garis putus-putus dan garis yang solid. Untuk kedua kasus, margin telah dipilih untuk mencakup lima point.Amati bahwa untuk kasus pengklasifikasi “garis putu-putus”, agar dapat mencakup lima poin margin harus dibuat sempit. Bayangkan jika lingkaran yang terbuka dan terisi pada Gambar 2.4 adalah rumah-rumah di dua desa terdekat dan bahwa jalan harus dibangun di antara dua desa. Satu harus memutuskan dimana harus dibangun jalan sehingga dapat selebar mungkin dan dikenakan sedikit biaya ( dalam arti jumlah terkecil menghancurkan rumah). Tidak ada insinyur yang bijaksana akan memilih “garis putus-putus”. Ide ini mirip dengan perancangan sebuah classifier. Harus “ditempatkan” antara daerah berpopulasi tinggi ( kepadatan probabilitas tinggi) dari dua kelas dan di daerah data yang jarang dalam data, meninggalkan kemungkinan margin terbesar. Hal ini ditentukan oleh persyaratan untuk kinerja generalisasi yang baik yang ditunjukkan setiap pengklasifikasi. Beberapa pengklasifikasi “mengetahui” training set dengan baik, karena pernah dicobakan padanya. Maka, kita dapat membentuk sebuah pengklasifikasi dengan hasil error rate yang sangat kecil pada training set tetapi menjadi buruk pada saat dihadapkan dengan “ unknown” data.
Diskusi ini mengarah ke formulasi matematis berikut. Diberikan sekumpulan training point, xi, dengan label kelas masing-masing, yi Є {-1,1}, i = 1,2,…,N, untuk klasifikasi 2-kelas, hitung sebuah hyperlane (Pers. (2.6)) sehingga untuk
2 . Margin error, ξi, tidak negatif ; bernilai nol untuk titik-titik di luar w margin dan pada sisi yang benar dari pengklasifikasi dan positif untuk titik-titik di dalam atau di luar margin dan pada sisi yang salah dari pengklasifikasi. C adalah konstan yang ditentukan user. Solusi diberikan sebagai rata-rata bobot dari training point:
Lebar margin adalah sama dengan
Koefisien λi adalah Lagrange multipliers dari optimisasi dan bernilai nol untuk semua titik di luar margin dan pada sisi yang benar dari pengklasifikasi. Titik-titik tersebut tidak berkonstribusi ke formasi arah pengklasifikasi. Point-point yang tersisa, dengan λi tidak sama dengan nol, yang berkonstribusi untuk membangun w, disebut support vectors. Untuk membangkitkan pengklasifikasi SVM linier, fungsi MATLAB SM02 dapat digunakan. Khususnya SM02 yang dipanggil dengan mengetik:
Dimana inputnya adalah Sebuah matriks X’ berisi titik-titik data set ( setiap baris adalah sebuah titik), Label kelas dari data point (y’), Tipe fungsi Kernel yang akan digunakan ( dalam kasus ini ‘linear’), Dua parameter kernel kpar1 dan kpar2 ( dalam kasus linier keduanya di set menjadi 0), Parameter C, Parameter tol, Jumlah maksimum langkah iterasi dari algoritma,
Threshold eps ( angka yang sangat kecil, biasanya 10-10) digunakan dalam perbandingan dua angka (jika perbedaan keduanya lebih kecil dari threshold, maka dipertimbangkan sama keduanya). Metode optimisasi yang digunakan ( 0 → Platt, 1 → Modifikasi Keerthi 1, 2 → Modifikasi Keerthi2),1 Alpha adalah vektor yang berisi Larange Multiplier berhubungan dengan training points, w0 nilai Threshold, w adalah vektor berisi parameter hyperlane,dihasilkan algoritma. Parameter tol adalah sebuah scalar yang mengendalikan akurasi dari solusi yang diperoleh [Theo 09, Bagian 3.7.2]. Semakin besar nilai tol, semakin jauh solusi algoritma berhenti. Biasanya nilai untuk tol adalah 0.001. Contoh 2.4.1 Dalam ruang 2-dimensi, diberikan dua equiprobable classes, yang mengikuti distribusi Gaussian dengan mean m1 = [ 0, 0]T dan m2 = [ 1.2, 1.2]T dan matriks kovarian S1 = S2 = 0.2I, dimana I adalah matriks identitas 2 x 2. 1. Bangkitkan dan plot data set X1 berisi 200 point dari setiap kelas ( total 400 poin), yang akan digunakan untuk pelatihan ( gunakan nilai 50 sebagai seed untuk randn MATLAB). Bangkitkan data set yang lain X2 berisi 200 point dari setiap kelas, yang akan digunakan untuk pengujian ( gunakan 100 untuk seed untuk fungsi randn MATLAB). 2. Berdasarkan X1, jalankan algoritma Platt untuk menghasilkan 6 pengklasifikasi SVM yang memisahkan dua kelas, gunakan C = 0.1, 0.2, 0.5, 1, 2, 20. Set tol = 0.001. a) Hitung error klasifikasi dari training dan test set b) Hitung support vectors. c) Hitung margin
2 w
d) Plot pengklasifikasi sebagai garis margin Solusi. Lakukan langkah berikut:
Langkah 1. Untuk menghasilkan data set X1, ketik
Untuk plot data set, ketik
Perhatikan bahwa kelas overlap. Untuk menghasilkan X2 ulangi code, ganti baris pertama dengan
Langkah 2. Untuk menghasilkan pengklasifikasi SVM yang dibutuhkan untuk C = 0.1, gunakan fungsi SM02, ketik
Pengklasifikasi yang lain dihasilkan dengan cara yang sama. a) Untuk menghitung error klasifikasi pada training set, ketik
Error klasifikasi pada test set, X2, dihitung dengan cara yang sama. b)
Untuk plot hyperplane pengklasifikasi sebaik garis margin, gunakan fungsi svcplot_book dengan mengetik:
c) Untuk menghitung support vectors, ketik
d) Untuk menghitung margin, ketik
Hasil percobaan ini ditunjukkan dalam Tabel 2.4. Dapat dilihat bahwa margin dari solusi meningkat sesuai dengan C menurun. Hal ini natural karena peningkatan C membuat “margin term” pada persamaan (2.8) lebih signifikan. Untuk permasalahan, kinerja terbaik ( minimum test error) diperoleh untuk C = 0.2. 2.4.1. Generalisasi Multiclass Dalam bagian ini, focus pada satu metode multi kelas, dikenal sebagai one-against-all ( untuk lebih detil pada masalah multikelas lihat [Theo 09, Bagian 3.7.3]). Teknik ini tidak disesuaikan dengan SVM. Hal ini umum dan dapat digunakan dengan beberapa pengklasifikasi untuk masalah 2-kelas. Lebih lanjut, hal ini tidak hanya alat belajar-mengajar, tetapi secara actual digunakan secara luas. Berdasarkan metode one-against-all, pengklasifikasi charus dirancang. Setiap dari mereka didesign untuk memisahkan satu kelas dari lainnya (ingat kembali ini adalah permasalahan yang diselesaikan pada Bagian 2.3.1 berdsarkan kriteria LS). Untuk paradigm SVM, kita harus mendesign c pengklasifikasi linier :
Sebagai contoh, untuk mendesign pengklasifikasi w1, kita pertimbangkan training data dari semua kelas selain ωi untuk membentu kelas kedua. Secara nyata, jika sebuah error dimasukkan diharapkan semua point dari kelas ω1 untuk dihasilkan dalam:
dan data dari kelas-kelas yang tersisa untuk dihasilkan dalam hasil negative. X diklasifikasi dalam ωi jika:
Contoh 2.4.2 1. Hasilkan dan plot dua set dara X1 (training) dan X2 (test) menggunakan prescription pda contoh 2.3.2, kecuali sekarang setiap set berisi 120 data point. 2. Berdasarkan X1, estimasi parameter vektor w1, w2, w3 dari tiga fungsi diskriminan linier menggunakan modifikasi pertama dari algoritma Platt [Keer 01] (pengklasifikasi SVM). Estimasi error klasifikasi berdasarkan X2. Solusi. Lakukan langkah berikut: Langkah 1. Untuk membangkitkan X1 dan X2, kerjakan seperi pada contoh 2.3.3, untuk Plot X1, ketik :
Langkah 2. Dalam kasus ini, matrik z1 dan z2 dibentuk dengan cara yang sama seperti pada contoh 2.3.3, tetapi sekarang elemen-elemen 0 diganti dengan -1. Secara spesifik, ketik :
Dimana c adalah jumlah kelas dan N1 adalah jumlah training vektor. Dengan cara yang sama tentuka z2. Untuk menghitung pengklasifikasi SVM, ketik :
Untuk estimasi error rate klasifikasi berdasarkan X2, ketik
Error klasifikasi dalam kasus ini 0.05%. Sebagai perbandingan, Error klasifikasi Bayesian adalah 3.3 %. ( Jelaskan mengapa nilai yang terakhir berbeda dengan yang didapat dalam contoh 2.3.2)
REFERENSI [1] Theodoridis Sergio, and Konstantinos Koutroumbas, An Introduction To Pattern Recognition : A MATLB Approach, Academic Press, USA, 2010.
