20100203
Oleh Deneng Eka Putra
5106100054
Pembimbing Ahmad Saikhu, S.Si, MT NIP. 132318030
Mengimplementasikan Algoritma variable predictive models based class discrimination (VPMCD) sebagai metode klasifikasi kesamaan pola
1
20100203
Data observasi yang relatif besar
Overlapping Data
2
20100203
Menggunakan metode Variable Predictive Model
Metode klasifikasi yang memanfaatkan hubungan antara variabelvariabel (inter-relation variables) dalam suatu objek untuk digunakan membentuk persamaan regresi yang mempunyai kemampuan untuk memprediksi / mengklasifikasikan sampel.
3
20100203
Classifier
Training Data
Unseen Data
A
B
C
Kelas
a1
b1
c1
cl1
a2
b1
c2
cl1
a3
b2
c3
cl2
a4
b1
c1
cl2
(a5, b2, c3)
kelas?
cl2
4
20100203
Model
yang digunakan untuk membentuk persamaan VPM adalah :
Liniear (L) Linear Interaction (LI) Quadratic Interaction (QI) Quadratic (Q)
Jumlah
suku pada tiap model ditentukan oleh jumlah variabel prediktor yang digunakan (order) r
Tipe Model
Linear
Bentuk Persamaan
r
X i b0 b j X
j
j 1
Linear Interaction
r
r
j 1
j 1
X i b0 b j X j
r
b
k j 1
jk
X j Xk
Quadratic Interaction
X i b0 b j X j b jj X 2 j
Purequadratic
X i b0 b j X j b jj X 2 j
r
r
r
j 1
j 1
j 1
r
r
j 1
j 1
r
b
k j 1
jk
X j Xk
5
20100203
Step 3 Step 2 Step 1
• pilih tipe model (L, LI, QI, Q) yang digunakan dan order r
• pilih himpunan variabel prediktor yang membuat persamaan regresi VPM paling optimum untuk prediksi
• hitung beta (koefisien tiap variabel prediktor)
6
20100203
Satu persamaan yang dibentuk adalah untuk satu variabel pada kelas tertentu Misal suatu objek memiliki g kelas dan p variabel/fitur maka persamaan yang terbentuk sebanyak g x p persamaan
Untuk setiap variabel memiliki d kandidat pilihan himpunan prediktor
d =
p-1
Cr
Misal order (r) = 1 dan jumlah variabel/fitur (p) pada sebuah objek berjumlah 4 maka kemungkinannya adalah sebanyak 3
Variabel yang diprediksi
Variabel prediktor
X1
X2
X1
X3
X1
X4
Dari d kandidat, akan dipilih himpunan variabel prediktor yang memberikan model terbaik dengan melihat nilai SSE. Hitung selisih kuadrat SSE antara nilai variabel respon yang sebenarnya dengan variabel respon yang diprediksi oleh persamaan regresi. Kemudian pilih himpunan variabel prediktor yang memberikan nilai SSE minimum
7
20100203
Setelah dipilih himpunan variabel prediktor yang menyebabkan persamaan regresi menjadi optimum, kemudian dilanjutkan dengan menghitung koefisien dari variabel prediktor tersebut
b : matrik koefisien variabel prediktor X : matrik variabel prediktor X’ : matrik transpose variabel prediktor y : matrik variabel respon
Set Data N [n x p ]
Gk = [ n2 x p ]
G k = [ n1 x p ]
Gk = [ nk x p ]
X11 = b * X2
X12 = b * X2
X13 = b * X3
X1p = b * Xj + ...
SSE11
SSE12
SSE13
SSE1p
Pilih SSE yang minimum
Pilih persamaan yang memberikan SSE minimum
8
20100203
Setelah terbentuk persamaan VPM yang terbentuk di tiap-tiap kelas, sekarang persamaan tersebut akan digunakan untuk mengklasifikasikan sampel.
Step 1 : ambil matrik sampel S [1 x p] yang akan ditestingkan. Step 2 : masukkan tiap-tiap elemen nilai matrik S pada persamaan VPM yang bersesuaian pada setiap kelas, kemudian simpan nilainya pada matriks (k=1,2,...,g). Step 3: Hitung nilai
,
setelah itu cari
nilai SSE kelas mana yang minimum, dan pilih kelas tersebut untuk menjadi kelas dari sampel yang ditestingkan.
Vektor S [1 x p ]
Xi = b * Xj + ....
Xi+1 = b * Xj + ...
Xi+2 = b * Xj + ...
Xp = b * Xj + ...
Xi = b * Xj + ....
Vektor Spred
Xi+1 = b * Xj + ...
Xi+2 = b * Xj + ...
Xp = b * Xj + ...
Vektor Spred
Hitung SSE vektor Spred dengan S
Cari yang SSE yang paling minimum untuk menentukan kelas yang sesuai
9
20100203
Berikut penerapan algoritma VPMCD pada data set IRIS
Data set bunga IRIS memiliki jumlah data n sebanyak 150 data Bunga IRIS memiliki kelas g sebanyak 3 yaitu Setosa ST, Verginica VC, dan Versicolor VS Tiap-tiap kelas memiliki data observasi sebanyak 50 data Bunga IRIS memiliki variabel/fitur p sebanyak 4 yaitu sepal length (X1), sepal width (X2), petal length (X3), dan petal width (X4)
Sepal Length
Sepal Width
Petal Length
Petal Width
Species
5.1
3.5
1.4
0.2
Setosa
4.9
3.0
1.4
0.2
Setosa
4.7
3.2
1.3
0.2
Setosa
...
...
...
...
...
7.0
3.2
4.7
1.4
Versicolor
6.4
3.2
4.5
1.5
Versicolor
6.9
3.1
4.9
1.5
Versicolor
...
...
...
...
...
6.3
3.3
6.0
2.5
Verginica
5.8
2.7
5.1
1.9
Verginica
7.1
3.0
5.9
2.1
Verginica
....
....
...
...
...
10
20100203
Misal tipe model yang dipilih adalah L dan r = 1 Split data set IRIS menjadi matriks Gk (k =1,2,3,….g) kelas VC (G2)
kelas ST (G1)
kelasVS (G3)
X1
X2
X3
X4
X1
X2
X3
X4
X1
X2
X3
X4
N11
N12
N13
N14
N11
N12
N13
N14
N11
N12
N13
N14
N21
N22
N23
N24
N21
N22
N23
N24
N21
N22
N23
N24
Nj1
Nj2
Nj3
Nj4
Nj1
Nj2
Nj3
Nj4
Nj1
Nj2
Nj3
Nj4
Pilih matriks Gk, untuk setiap variable Xi(i=1,2,3…p) pada Gk bangun persamaan VPM dengan menggukanan kombinasi yang berbeda dari variable set (Xj ;j=1,2,3….r,j≠i) pada Gk Pada kelas G1 Setelah dilakukan penghitungan terhadap SSE didapat X1 baik diprediksi oleh X2, X2 baik diprediksi oleh X1, X3 baik diprediksi oleh X1, dan X4 baik diprediksi oleh X3 kelas G2 didapat
kelas G3 didapat
11
20100203
Terbentuk persamaan untuk data set IRIS Masukkan nilai tiap elemen matriks S yang bersesuaian pada persamaan VPM tiap kelas untuk mendapatkan matrik Spred Hitung SSE pada tiap-tiap kelas
Setosa
Versicolor
Virginica
SSE Minimum adalah Artinya matriks sampel S diprediksi termasuk anggota kelas Setosa
12
20100203
Data set
Membaca data set
Pembentukan VPM lokal optimum
Penghitungan akurasi
Pebentukan VPM global optimum
Persamaan VPM
Daftar seluruh kemungkinan kombinasi tipe model-order yang mungkin dibentuk. Jumlah kemungkinan dapat dirumuskan dengan 4 x (p-1) kemungkinan Melakukan penghitungan akurasi untuk tiap kombinasi tipe model-order
Memilih pasangan tipe model-order yang memberikan nilai akurasi prediksi paling tinggi
13
20100203
Hasil uji coba data set Diabetic dengan proporsi data training 1/2 dari data seluruhnya tipe model
order
Akurasi(%)
L
1
59.2
L
2
68.5
L
3
65.3
L
4
60.3
L
5
60.4
L
6
60.7
L
7
LI
1
59.2
LI
2
70.9*
61.6
LI
3
63.7
LI
4
65
LI
5
64.7
LI
6
65
LI
7
61.2
QI
1
59.5
QI
2
60.7
QI
3
66.5
QI
4
63.9
QI
5
63
QI
6
59.8
QI
7
61
Q
1
59.52
Q
2
60.8
Q
3
64.5
Q
4
62.2
Q
5
61.4
Q
6
59.8
Q
7
59.2
14
20100203
Hasil uji coba data set Diabetic dengan proporsi data training 2/3 dari data seluruhnya tipe model
order
Akurasi(%)
L
1
64.5
L
2
L
3
65
L
4
58.3
L
5
58.5
L
6
57.4
L
7
60.4
LI
1
64.5
LI
2
73.8*
LI
3
67.1
LI
4
65.2
LI
5
63.6
LI
6
61.8
LI
7
63.1
QI
1
65.3
QI
2
67
QI
3
64.2
QI
4
60.7
QI
5
59.6
QI
6
59.1
QI
7
58.2
Q
1
65.3
Q
2
68.7
Q
3
58.8
Q
4
60.4
Q
5
57.6
Q
6
57.9
Q
7
58.5
70
Berikut adalah hasil rangkuman uji coba dari 6 data set Data set
proporsi
Diabetic
½ training testing 2/3 training testing ½ training testing 2/3 training testing ½ training testing 2/3 training testing ½ training testing 2/3 training testing ½ training testing 2/3 training testing ½ training testing 2/3 training testing
Diabetic Heart Heart Iris Iris Wine Wine Digit Digit Letter Letter
Tipe model
Order (r)
Akurasi(%)
½ linear interaction
2
70.9%
1/3 linear interaction
2
73.8%
½ quadratic interaction
10
79.3%
1/3 quadratic interaction
10
79.7%
½ Pure quadratic
2
93.3%
1/3 Pure quadratic
1
96 %
½ Pure quadratic
6
90.6%
1/3 Pure quadratic
5
91.3%
15
100%
6
99.4%
½ quadratic interaction
9
94.2%
1/3 quadratic interaction
10
94.7%
½ quadratic interaction 1/3 linear interaction
15
20100203
Berikut adalah kesimpulan dari uji coba pada Tugas Akhir ini 1. Tiap data set memiliki bentuk (tipe model dan order) VPM optimum yang berbeda-beda dipengaruhi oleh jumlah data set yang ditrainingkan 2. Naiknya jumlah order prediktor tidak selalu menyebabkan naiknya prosentase akurasi prediksi 3. Semakin komplek tipe model tidak selalu menyebabkan prosentase akurasi prediksi meningkat. 4. Variable Predictive Models Based Class Discrimination (VPMCD) terbukti mampu untuk menjadi classifier, dan mampu untuk mengkasifikasikan sampel baru suatu data set.
Berikut adalah saran yang dapat diberikan pada pengerjaan Tugas Akhir ini 1. Perlu dikembangkan algoritma untuk mengatasi data set yang memiliki data observasi sangat banyak, sehingga waktu eksekusi untuk training tidak terlalu lama 2.Perlu dikembangkan algoritma untuk menentukan model yang paling kecil kompleksitasnya bila ada dua atau beberapa model yang memiliki hasil akurasi yang tepat sama. 3. Perlu dikembangkan lagi algoritma untuk mengatasi agar jika kekurangan data training yang cukup banyak hasil akurasi tetap tinggi
16
