OPTIMASI METODE DISCRIMINATIVELY REGULARIZED LEAST SQUARE DENGAN ALGORITMA GENETIKA DAN PARTICLE SWARM OPTIMIZATION UNTUK PENGKLASIFIKASIAN Ariadi Retno Tri Hayati Ririd1) Agus Zainal Arifin2) Anny Yuniarti3) 1,2,3
Jurusan Teknik Informatika, Institut Teknologi Sepuluh Nopember Kampus ITS, Sukolilo, Surabaya 60111 e-mail :
[email protected],
[email protected],
[email protected],
2008). Untuk menggabungkan karakteristik dari kedua metode optimasi ini, maka dibangun pengembangan optimasi yang merupakan penggabungan dari kedua metode dikenal dengan istilah GAPSO. Penelitian ini mengoptimasikan parameter K dan η dengan GAPSO berdasarkan error terkecil dari hasil pengklasifikasian secara otomatis.
Abstrak— Metode regularization telah banyak diaplikasikan pada pengenalan pola yang bertujuan untuk menghasilkan klasifikasi data. Penelitian ini menggunakan metode Discriminatively Regularized Least Squares Classification (DRLSC) dimana pengklasifikasian datanya berdasarkan informasi discriminative yang dipengaruhi oleh jumlah data-data yang terdekat berdasarkan metode K Nearest Neighbor dan regularization parameter. Untuk meningkatkan keakurasian dari metode DRLSC, penelitian ini mengoptimasi jumlah data-data yang terdekat sebelum membangun matrix Laplacian dan regularization parameter berdasarkan error terkecil. Metode yang digunakan adalah penggabungan Algoritma Genetika dan Particle Swarm Optimization (GAPSO). Data yang digunakan untuk uji coba adalah database UCI, yaitu IRIS, WINE, dan LENSA. Berdasarkan hasil uji coba untuk mengoptimasi metode DRLSC maka nilai fitness yang dihasilkan metode GAPSO lebih baik jika dibandingkan Algoritma Genetika (GA) dan Particle Swarm Optimization (PSO) dengan selisih nilai fitness 7.3e-008 hingga 0,025.
II. PENGKLASIFIKASIAN DRLSC Langkah-langkah pada sebagaimana Gambar 1.
pengklasifikasian
DRLSC
Kata Kunci : Desain Klasifikasi, Discriminatively Regularized Least Square Classification, Algoritma genetika, Particle Swarm Optimization, Pengenalan Pola.
I. PENDAHULUAN Metode DRLSC mengklasifikasikan data-data secara discriminative berdasarkan intraclass dan interclass sehingga cenderung menghasilkan keakurasian yang lebih baik dibandingkan metode regularization sebelumnya (Xue, 2009). DRLSC sangat dipengaruhi oleh jumlah tetangga terdekat setiap data sebanyak K pada metode KNN dan regularization parameter ( η ). Berdasarkan hal ini maka perlu adanya penentuan secara otomatis pada jumlah tetangga terdekat pada setiap data (K) dan η . Metode Algoritma genetika telah banyak digunakan dalam mengoptimasi dengan menggunakan operator crossover dan mutasi sehingga dalam mencari search point memiliki karakteristik mencari pola baru yang diharapkan agar memiliki nilai fitness yang lebih baik. Pada Particle Swarm Optimization (PSO), dalam mencari search point berdasarkan nilai fitness yang terbaik dengan resultan posisi point saat ini dengan nilai yang akan dicapai. Sehingga karakteristik pada pencarian nilai pada PSO berdasarkan satu nilai point yang memiliki fitness terbaik, sedangkan pada Algoritma Genetika pencarian nilai dilakukan oleh seluruh kromosom dengan menggunakan operator Algoritma Genetika (Sivanandam,
Gambar.1.Diagram Alir pengklasifikasian metode DRLSC Parameter yang dioptimasi adalah parameter K yang terdapat pada proses pengelompokan data dengan metode KNN dan regularization parameter yang terdapat pada proses penghitungan S η .
1
adjacency (Xue, 2009). Konsep dari matrix adjacency dalam pemberian bobot untuk matrix dari graph Gw dan Gb adalah sebagai berikut:
Pengklasifikasian DRLSC dimulai dari pengelompokan data dengan metode KNN hingga menentukan kelas data berdasarkan hasil output. 2.1 K Nearest Neighbor K Nearest Neighbor digunakan untuk menentukan hubungan antara data. Pada setiap data x i maka dicari K data yang memiliki jarak yang terdekat kemudian dibangun edge yang menghubungkan data x i dengan K data. K data yang terdekat disimpan pada variabel ne(i)= { x i1 ,..., x ik } . Berikut adalah algoritma dari KNN (Duda, 2001; Song, 2007; Liu, 2004): 1. Menentukan nilai K. 2. Menghitung jarak data pada setiap data training dengan eucledian. 3. Mendapatkan K data yang memiliki jarak terdekat. Penghitungan jarak pada metode KNN dengan eucledian antara vektor xi dan vektor x j dengan rumus sebagaimana
(3) Matrix adjacency yang telah dibangun menunjukkan hubungan keterkaitan antara data-data. Setelah membangun Gw dan Gb, maka dilanjutkan dengan membangun matrik Laplacian. 2.4 Matrik Laplacian Matrik Laplacian dibangun berdasarkan matrik Gw dan Gb. Persamaan untuk membangun matrik Laplacian sebagaimana berikut:
persamaan 1. 1
D 2 d(xi , x j ) = (xi − x2 ) (xi −x j ) = ∑(xi − x j )2 i=1 T
dimana
(1)
Lw = Dw − Gw
Lb = Db − Gb
xi adalah data ke-i dan x j adalah data ke-j, d ( xi , x j )
adalah jarak kedua data. Semakin mirip kedua data, maka nilai dari jarak kedua data semakin kecil. Sebaliknya semakin besar hasil dari d ( xi , x j ) maka semakin tinggi perbedaan
dimana D w adalah matrix diagonal yang elemen diagonalnya adalah jumlah seluruh j elemen dari Gw. Sedangkan Db merupakan matrix diagonal yang elemen diagonalnya adalah jumlah seluruh j elemen dari Gb. Nilai pada elemen-elemen diagonal merupakan penjumlahan dari data-data yang terdapat pada Gw dan Gb berdasarkan kolomnya pada setiap baris.
karakteristik antara kedua data vektor. 2.2 Membedakan new dan neb Setelah mendapatkan K data terdekat pada setiap data, dilanjutkan dengan dua pembagian kelompok data dari K data terdekat pada setiap data. Pembagian ini berdasarkan data-data yang terkelompokkan berdasarkan kelasnya (new) atau data-data yang terkelompokkan tidak termasuk dalam kelasnya (neb) sebagaimana persamaan berikut: j
new(i)={ x i |jika j
x ij dan xi j
neb(i)={ x i |jika x i dan
xi
2.4 Least Square Konsep dari penghitungan Least Square adalah mendapatkan solusi dari vektor C yang memenuhi persamaan AC=B, ATAC~=ATB (5) Pada penyelesaian matrik invers dibutuhkan matrik square, sehingga dilakukan pendekatan ATA ≈ A . C~ adalah solusi Least Squares dengan melakukan invers (Duda, 2001; Grodzevich, 2005; Jia, 2008; Rifkin, 2007) sebagaimana persamaan berikut: C~=(ATA)-1ATB (6) Jika hasil dari invers ATA adalah matrik singular (mendekati nilai nol), maka digunakan pseudoinverse berdasarkan singular value decomposition(Rifkin, 2007; Bartolli,2000). Konsep dasar dari penghitungan pseudoinverse adalah singular value decomposition (svd). Jika terdapat matrix G berukuran matrix [NxM], dengan menggunakan singular value decomposition akan didapatkan nilai matrix U [u1,u2,…uN] yang merupakan left singular vektor dari matrix G dan nilai matrix V [v1,v2,…vM] yang merupakan nilai right singular vektor dari matrix G.
kelas yang sama, 1≤j≤K} kelas yang berbeda, 1≤j≤K}
(4)
(2)
Jika seluruh K tetangga terdekat terkelompokkan pada new maka jumlah neb data tersebut bernilai 0. Seluruh anggota pada new dan neb merupakan anggota dari ne pada setiap data. Hasil pengelompokan dari new dan neb akan menjadi dasar yang sangat penting untuk membangun keterhubungan data-data sebagai dasar dari matrix Laplacian. 2.3 Membangun matrix Gw dan Gb Dasar dalam membangun matrik Laplacian adalah membangun matrik weight berdasarkan new yaitu Gw dan berdasarkan neb yaitu Gb dengan menggunakan konsep matrix
2
2.7 Penghitungan Hasil Keluaran Setelah mendapatkan nilai b dan γ , maka dilanjutkan dengan penghitungan bobot (w) berdasarkan persamaan 10.
2.5 Penghitungan Sη
Sη adalah parameter yang bertujuan memberikan informasi
N
pada data-data pembelajaran mengenai informasi yang terdapat pada matrix Laplacian sebagaimana persamaan 7.
Sη = X [ηLw − (1 − η )Lb ]X
T
Sesuai dengan persamaan diatas, maka w adalah penjumlahan dari hasil perkalian dari Langrange multipliers, invers dari Sη dan, data ke-i sejumlah N data. Setelah mendapatkan nilai w
(7)
2
dan bias, maka hasil keluaran untuk pengklasifikasian multiclass sebagaimana persamaan 11.
f ( x ) = wT x + b
Hasil dari pengklasifikasian dari metode DRLSC digunakan sebagai dasar dari penghitungan fitness pada metode Optimasi Algoritma Genetika dan Particle Swarm Optimization.
(8) 3.
GAPSO Penelitian ini mengimplementasikan penggabungan dua metode optimasi yaitu Algoritma Genetika dan Particle Swarm Optimization dengan istilah GAPSO. Konsep dasar dari PSO yaitu mengembangkan simulasi sekumpulan burung dalam ruang dimensi XY (dua dimensi) direpresentasikan dengan partikel berdasarkan informasi posisi dan kecepatan (velocity). Setiap partikel mengetahui nilai terbaiknya (Pbest) dan posisinya (x). Selanjutnya, setiap particle mengetahui nilai terbaik didalam seluruh data (Gbest). Pada Gambar 2 menggambarkan konsep desain sistem untuk menggabungkan kedua metode.
bias (b) dan parameter Langrange Multiplier ( γ ) sebagai dasar dalam mendapatkan nilai bobot dari metode DRLSC.
γ
Kelebihan dari metode DRLSC adalah dapat mengklasifikasikan data secara multiclass (pada waktu bersamaan dapat mengklasifikasikan data-data dengan kelas yang berbeda) tanpa mengklasifikasikannya pada beberapa pengklasifikasian binary class. Persamaan multiclass sebagaimana persamaan 9.
[b
T 0 1N = [0 N 1N Ωη + I N
γ ]
(11)
dimana w∈Rnxc, b∈Rc
dimana σ adalah variabel varian. Setelah didapatkan nilai dari hasil perhitungan Sη , dilanjutkan dengan penghitungan nilai
2.6 Penghitungan b dan
(10)
i =1
dimana η adalah regularization parameter dan X adalah kumpulan dari data-data x. Jika data diproyeksikan berdasarkan kernel, maka perlu pembangunan matrik kernel dengan cara data diproyeksikan kedalam fungsi kernel kemudian dilanjutkan dengan penyelesaian persamaan linier (Xue, 2009). Penelitian ini menggunakan gaussian kernel (Xue, 2009). Persamaan 8 adalah persamaan untuk kernel gaussian.
x −x i j K ( xi , x j ) = exp − 2 2σ
+
w = ∑ γ i ( Sη ) xi
Y]
(9)
dimana
Ωη,ij = xTj (Sη ) xi ,1N = [1,...,1] , γ = [γ 1 ,...,γ N ] , I N ∈ R NxN I +
merupakan matrik identitas,
T
T
0 c = [0,...,0] , Y = [ y1 ,..., y N ], T
N adalah jumlah data pembelajaran dan, (.)+ adalah invers dari matrik. Untuk pengklasifikasian multiclass, maka pada label kelas dibangun secara vektor dengan tujuan dapat mengatasi permasalahan multiclass. Jika data xi termasuk pada kelas k
Gambar 2. Diagram pengklasifikasian metode GA dan PSO Berikut adalah algoritma dari metode GAPSO (Kao, 2008):
maka target kelas merupakan yi=[0,...,1,...,0] ∈ R , dimana kelas ke-k bernilai 1 dan yang lain bernilai 0. T
c
1. Inisialisasi random populasi sebanyak N data. 2. Evaluasi dan ranking evaluasi fitness pada setiap N individu, dimana fungsi fitness pada penelitian ini
MeanSquareError ( MSE ) =
1 N
3
2 ∑1N ( y − f ( x )) ,
berdasarkan mean square error, sebagaimana persamaan 12 (Dondeti, 2005; Coletti, 1999).
IV. HASIL UJI COBA DAN ANALISA Setiap uji coba yang dilakukan pada ke-3 dataset akan dibandingkan pada empat metode yaitu tanpa optimasi, dengan metode GA, metode PSO, dan optimasi dengan GAPSO. Tabel 1. Hasil Pembelajaran Data IRIS
(12) dimana y adalah nilai target yang diinginkan, f(x) adalah hasil keluaran dari pengklasifikasian data.
Metode
Fitness
%Uji Coba
Σ iterasi
K
ita
3. Algoritma genetika dengan menggunakan real code operator GA, dari N/2 data terbaik.
Tanpa
1,1e-004
93,33%
24
104
6
3.1Seleksi dari N data pilih N/2 data dengan fitness terbaik.
GA
1,1e-004
93,33%
27
129,65
6
PSO
1,1e-004
93,33%
13
56,54
6
GAPSO
1,1e-004
93,33%
13
85,41
6
Optimasi
3.2 Crossover N/2 data sebagaimana persamaan 13. 3.3 Mutasi dengan pengaruh fungsi gaussian terhadap nilai random. Probabilitas mutasi sebesar 0.2 sebagaimana persamaan 14. ' x i = α * x i + (1 − α ) x i +1 i = 1, 2 ,......, 2 N − 1 ' x i = α * x i + (1 − α ) x1 i = 2N ,
Berdasarkan hasil percobaan pada Tabel 1, hasil pembelajaran pada ketiga metode optimasi dan tanpa optimasi menghasilkan parameter K dan η yang sama, sehingga fitness pada ke-4 parameter memiliki nilai yang sama.
(13) Tabel 2. Hasil Pembelajaran Data WINE (14)
Fitness
%Uji Coba
Σ iterasi
K
η
Tanpa
0,076
93,33%
24
175,32
2
GA
4,2e-004
93,33%
30
254,45
17
PSO
4,7e-006
93,33%
17
140,11
2
GAPSO
8,9e-010
93,33%
50
558,55
2
Optimasi
4. Setelah pembelajaran dengan metode crossover dan mutasi, maka dilanjutkan dengan pembelajaran PSO. Operasi yang digunakan pada pembelajaran PSO untuk penentuan velocity pada pembelajaran GAPSO sebagaimana persamaan 15.
VidNew = cxrandx( p gd − xidold ),
Metode
(15) Hasil yang diperoleh berdasarkan Tabel 2, nilai fitness terkecil diperoleh oleh metode GAPSO.
dimana nilai c adalah 2, rand adalah nilai random antara 0 dan 1, p gd adalah nilai Gbest. Pada pembelajaran GAPSO pada
Tabel 3. Hasil Pembelajaran Data LENSA
penelitian ini tidak menggunakan velocity lama untuk memperbarui nilai velocity, hal ini berpengaruh positif sehingga menuju nilai optimal lebih terarah dan lebih cepat. Hal ini disebabkan karena pada pada metode GAPSO, dapat terjadi kemungkinan data dari PSO menjadi data pembelajaran pada GA yang tidak membutuhkan informasi nilai velocity sebelumnya. Dari hasil pembelajaran GA ini diperoleh generasi baru yang tidak dipengaruhi oleh nilai velocity sebelumnya. Dengan demikian, maka penggunaan velocity sebelumnya dapat memperlambat kearah nilai optimal jika terjadi kemungkinan nilai dari data PSO pada generasi berikutnya digunakan sebagai pembelajaran pada metode GA.
Metode
Fitness
%Uji
Σ iterasi
K
Η
Coba Tanpa
0,005
92,31%
2
0,17
2
Optimasi GA
0,0186
92,31%
11
1,7
2
PSO
2,6e-005
92,31%
17
3,68
5
GAPSO
1,9e-006
92,31%
13
3,03
2
Sebagaimana pada hasil percobaan pada Tabel 3, hasil fitness yang didapatkan pada GAPSO memiliki nilai terbaik dibandingkan ke-2 metode optimasi dan tanpa optimasi. Berdasarkan analisa pada seluruh uji coba maka kecenderungan metode GAPSO menghasilkan nilai fitness yang lebih kecil jika dibandingkan metode GA ataupun PSO. Metode GAPSO sejak iterasi pertama hingga konvergen memiliki kecenderungan menghasilkan nilai fitness yang lebih kecil jika dibandingkan dengan metode GA ataupun PSO sendiri pada setiap iterasinya. Hal ini dipengaruhi oleh hasil pembelajaran dari metode Algoritma Genetika mempengaruhi data pembelajaran pada metode PSO pada setiap iterasinya. Semakin banyak jumlah iterasi untuk mencapai konvergen dengan data pembelajaran yang sama pada metode
Setelah pembelajaran dengan metode GA dilanjutkan dengan metode PSO, maka dilakukan analisa fitness dalam penelitian ini Mean Square Error dari pengklasifikasian DRLSC untuk mengetahui error yang telah dicapai oleh pembelajaran GAPSO. Penentuan iterasi berhenti dalam penelitian ini menggunakan maksimum iterasi. Sebelum memasuki optimasi pada PSO, maka perlu adanya konversi nilai dari kromosom sebagaimana persamaan 16 (Saruhan, 2004): x=rb+(ra-rb)g, (16) dimana rb adalah batas bawah dan ra adalah batas atas dengan g adalah gen dari kromosom.
4
GAPSO memiliki kecenderungan menghasilkan nilai fitness yang terkecil dibandingkan metode optimasi GA ataupun PSO untuk data yang sama.
a.
Grafik GAPSO
b.
Grafik PSO
VI. DAFTAR PUSTAKA Bartolli, Andrien (2000), “Numerical Optimization I Linear Least Squares”, Copenhagen, Denmark. Coletti, M., Lash, T., Mandsager, C., Michalski, R.S. dan Moustafa, R. (1999), “Comparing Performance of the Learnable Evolution Model and Genetic Algorithms Applied to Digital Signal Filters”. Dondeti, S., Kannan, K. dan Manavalan, R. (2005), “Genetic Algorithm Optimized Neural Networks Ensemble for Estimation of Mefenamic Acid and Paracetamol in Tablets”, Acta Chim. Slov., 52, 440–449 Duda, R.O., Hart, P.E. dan Stork, D.G. (2001), “Pattern Classification”, Wiley, New York. Grodzevich, O. dan Wolkowicz, H. (2005), “Regularization Using a Parameterized Trust Region Subproblem”, The Natural Sciences and Engineering Research Council of Canada. Jia, Y., Zhang, C. (2008), “Local Regularized Least-Square Dimensionality Reduction”, IEEE 978-1-4244-21756/08. Kao, Y.T. dan Zahara (2008), E., “A hybrid genetic algorithm and particle swarm optimization for multimodal functions”, Applied Soft Computing 8 849–857. Liu, D., Shi, T., DiDonato, J.A., Carpten, J.D., Zhu, J. dan Duan, Z.H. (2004), “Application of Genetic Algorithm/K-Nearest Neighbor Method to the Classification of Renal Cell Carcinoma”, Proceedings of the IEEE Computational Systems Bioinformatics Conference. Nes, Antle, (2003), “Hybrid System for Face Recognition”, Norwegian University of Science and Technology, Faculty of Information Technology,Mathematics and Electrical Engineering, Department of Computer and Information Science, Division of Intelligent Systems / Image Processing Rifkin, R. M. dan Lippert, R. A. (2007), “Notes on Regularized Least Squares”, Computer Science and Artificial Intelligence Laboratory Technical Report , MIT-CSAILTR-2007-025 Saruhan, H. (2004), “Genetic Algorithms: An Optimization Technique”, TEKNOLOJĐ, Volume 7, Issue 1, 105-114. Sivanandam, S.N. dan Deepa, S.N. (2008), “Introduction to Genetic Algorithms”, Springer-Verlag Berlin Heidelberg. Song, Y., Huang, J, Zhou, D., Zha, H. dan Giles, C. L. (2007), “IKNN: Informative K-Nearest Neighbor Pattern Classification”, Springer-Verlag Berlin Heidelberg. Xue, H., Chen, S. dan Yang, Q. (2009), “Discriminatively Regularized Least-Squares Classification”, Science Direct, Pattern Recognition 42 93 – 104.
b. Grafik GA
d. Grafik Tanpa Optimasi
Gambar 3. Grafik ke-4 Metode dengan data Wine
V.KESIMPULAN Berdasarkan hasil uji coba dan analisa yang telah dilakukan maka dapat diuraikan beberapa kesimpulan, yaitu: • Pada penelitian ini mampu mendapatkan parameter K dan η secara otomatis dengan menerapkan metode optimasi GAPSO. • Metode GAPSO yang diterapkan untuk mengoptimasi metode DRLSC memiliki kecenderungan mampu menghasilkan nilai fitness yang lebih baik jika dibandingkan metode optimasi GA ataupun PSO sendiri dan tanpa optimasi. • Pada metode GAPSO, semakin banyak jumlah iterasi untuk mencapai konvergen akan menghasilkan nilai fitness yang lebih baik jika dibandingkan metode GA ataupun PSO dengan data yang sama. Pada penelitian ini masih terdapat kelemahan ketika proses pembelajaran KNN membutuhkan waktu yang lama karena menggunakan dimensi sebenarnya, untuk mengatasi hal ini perlu adanya penelitian pengurangan dimensi untuk mempercepat proses komputasi ketika pada pembelajaran KNN.
5
