MAKALAH SEMINAR TUGAS AKHIR PERIODE JANUARI 2010
EKSTRAKSI FITUR EEG DENGAN MENGGUNAKAN FAKTORISASI KERNEL MATRIKS NONNEGATIF Rahmah Mustika Ningrum1, Yudhi Purwananto2, Rully Soelaiman3 Teknik Informatika, Fakultas Teknologi Informasi, ITS email :
[email protected],
[email protected],
[email protected] dan Gamma (>30Hz). Untuk deteksi epilepsi, potensial karena rangsangan cahaya bisa digunakan.
ABSTRAKSI Electroencephalogram (EEG) merupakan sinyal sensor paling populer yang digunakan untuk Brain Computer Interface (BCI). Karakteristik EEG menyebabkan tidak semua algoritma dapat digunakan untuk mengekstraksi fiturnya. Dalam tugas akhir ini, akan diimplementasikan algoritma NMF dan KNMF untuk ekstraksi fitur EEG, yang sangat penting dalam klasifikasi EEG. Salah satu metode yang dapat digunakan untuk mengekstraksi fitur EEG dengan baik adalah Nonnegative Matrix Factorization (NMF). NMF mendekomposisikan sebuah
Salah satu konsep yang menjadi fokus saat ini adalah pemanfaatan secara langsung sinyal EEG secara langsung dalam mengontrol suatu perangkat tanpa melalui kanal pada syaraf motorik dan otot, yang diperlukan untuk pasien stroke dan amputasi, sehingga lebih mudah berinteraksi dengan perangkat kursi roda, komputer atau perangkat lainnya. Kondisi mental pasien tersimpan secara implisit dalam sinyal EEG, oleh karena itu perlu dilakukan klasifikasi untuk tiap data EEG yang tersimpan, dan untuk melakukan proses klasifikasi ini diperlukan sebuah metode ekstraksi fitur yang tepat.
matriks nonnegatif X ≥ 0 ke dalam sebuah hasil kali
dari dua buah matriks nonnegative U ≥ 0 dan V ≥ 0 sedemikian hingga ketergantungan antara X dengan
UV T minimal. Salah satu turunan dari metode NMF adalah
Kernel
Nonnegative
Matrix
Metode Nonnegative Matrix Factorization (NMF) mudah mendeterminasikan diskriminatif vektor basis dengan reflek yang bagus untuk menghasilkan karakteristik spektral tanpa cross-validation motor imagery task.
Factorization
(KNMF), asumsikan U = XW dalam dekomposisi, dimana , kernel NMF (KNMF) mudah diturunkan dalam framework optimasi least square. Saat kernel linier digunakan dalam NMF, fitur spectral EEG dapat dengan mudah dihitung menggunakan perkalian matriks.
Saat metode KNMF dengan kernel linier digunakan, fitur spectral dengan mudah dapat dihitung dengan sebuah multiplikasi matriks, padahal jika menggunakan metode NMF standar, multiplikatif harus dilakukan berulang kali dengan menggunakan faktor matriks tetap yang lainnya, atau dengan kata lain, jika menggunakan metode standar NMF, masih diperlukan pseudo-inverse dari sebuah matriks. Lebih jauh lagi, metode KNMF dengan kernel linier mudah membangun seleksi fitur atau seleksi data.
Kata kunci : Klasifikasi EEG, Ekstraksi Fitur, Metode Kernel, Multiplicative Update, Fakstorisasi, dan Matriks Nonnegatif
1
PENDAHULUAN
Pengukuran sinyal otak dengan EEG adalah salah satu teknik yang relatif paling murah dibandingkan dengan penggunaan Magneto-Enchepalography (MEG), Fungsional Magnetic Resonance Imaging (fMRI). Kelebihan lain dari EEG adalah pada resolusi temporal yang tinggi dan cepat merespon segala perubahan aktivitas otak, walaupun dari sisi resolusi spasial relatif paling rendah dibandingkan dengan kedua perangkat yang disebutkan diatas.
Tugas akhir ini menggunakan metode KNMF untuk mengekstraksi fitur representasi data EEG yang sangat penting dalam klasifikasi EEG. Penggunaan metode KNMF untuk mengekstrasi fitur EEG dipilih karena : 1. Dengan menggunakan metode KNMF kernel linier, fitur spectral dengan sangat mudah dapat dihitung menggunakan perkalian matriks, yang tidak disediakan oleh penggunaan metode NMF standar 2. KNMF dengan kernel linier menyediakan tiap kolom dalam W memenuhi sum-to-one-constraint. Seleksi fitur ataupun seleksi data dapat dengan mudah dilakukan dengan metode KNMF dengan kernel linier
Sinyal EEG diukur dengan elektroda pada hemisphere kepala dan pada beberapa titik pengukuran yang dibagi pada daerah utama frontal, temporal, central, parietal dan occipital lobe. Untuk keperluan klinik, sinyal EEG dapat digunakan untuk menganalisa kondisi mental pasien, dimana sinyal EEG terkait suatu kejadian/rangsangan akan dianalisa berdasarkam daya spektral dari sinyal EEG yang terkenal dengan istilah gelombang delta (0.15Hz), Theta (4-7Hz), Alpha (8-13Hz), Beta (14-30Hz)
1
MAKALAH SEMINAR TUGAS AKHIR PERIODE JANUARI 2010
2
C3
EEG
Cz
C4
CP1
CP2
P3
Pz
P4
Electroencephalogram (EEG) banyak digunakan sebagai salah satu informasi untuk keperluan diagnosis terkait masalah dengan syaraf serta kondisi mental pasien, salah satunya adalah karena biaya komputasinya yang tdiak semahal penggunaan Magneto-Enchepalography (MEG), Fungsional Magnetic Resonance Imaging (fMRI). Dataset pertama hasil penyimpanan sinyal otak yang diukur dengan menggunakan EEG adalah dataset dalam format IDIAP. Dataset IDIAP mengandung rekaman data EEG dari 3 subjek (orang) normal selama 4 sesi feedback, yang melibatkan tiga tugas, yaitu imaginasi dari gerakan tangan ke kiri/kanan, dan pengucapan kata-kata yang dimulai dengan huruf acak yang sama. Keempat sesi feedbacknya terjadi pada hari yang sama, tiap setiap sesinya selama 4 menit dengan sela (istirahat) 5-10 menit diantara dua sesi. Subjek mengerjakan satu tugas selama kurang lebih 15 detik dan kemudian melakukan tugas selanjutnya secara random (tugas lain ataupun mengulang tugas yang sama) sesuai degan permintaan operator.
8
20 30
8
20 30
8
20 30
8
20 30
8
20 30
8
20 30
8
20 30
8
20 30
Gambar 1. Data IDIAP subjek 1 mengandung 8 channel (C3,Cz,C4,CP1,CP2,P3,Pz,P4) dalam 12 frekuensi (8,10,12,...,30 Hz)
3 METODE NONNEGATIVE MATRIX FACTORIZATION Metode Nonnegative Matrix Factorization (NMF) adalah sebuah metode analisis multivariate [5] yang terbukti sangat berguna dalam pembelajaran respresentasi data nonnegative, seperti citra-citra, spectrogram-spectogram, dan dokumen-dokumen. Metode NMF
Data EEG yang akan digunakan dalam penelitian ini adalah data EEG dalam format IDIAP yang disediakan oleh BCI Competition V.
mendekomposisikan sebuah matriks nonnegatif X ≥ 0 ke dalam sebuah hasil kali dari dua buah matriks
Data IDIAP disediakan dalam dua bentuk : 1 Raw EEG signals (sinyal EEG kasar) (dengan contoh freluensi : 512 Hz) direkam dari 32 elektroda 2 Precomputed Feature. Berupa data power spectral density (PSD) dalam 8-30 Hz setiap 62.5 ms (16 kali dalam satu detik) detik lebih, dengan resolusi frekuensi 2 Hz untuk 8 parietal-channels (C3, Cz, C4, CP1, CP2, P3, Pz, dan P4) setelah raw EEG potensial pertama kali secra spasial difilter berdasarkan mean sebuah surface Laplacian (8 channel, 12 komponen frekuensi).
nonnegatif sedemikian hingga
U ≥ 0 dan V ≥ 0 .
X ≈ UV T
untuk
Metode NMF membolehkan hanya kombinasi nonsubtractive dari vektor basis nonnegatif untuk mendekati nilai data nonnegatif sebenarnya, mungkin menyediakan representasi berdasarkan atas data sebagian. NMF mencari dekomposisi dari matriks X ∈ R menjadi bentuk
Data IDIAP dalam bentuk Precomputed Feature yang disediakan oleh IDIAP Research Institute yang diberikan melalui dataset V dalam BCI Competition III adalah :
nxm
X ≈ UV T , . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .( 1 ) nxr mxr dimana U ∈ R dan V ∈ R dibatasi harus matriks
Tabel 1 Dataset IDIAP V BCI Competition III
nonnegatif, dalam kasus ini, Subject 1 Subject 2 Subject 3
Training 3488/3472/3568 3472/3456/3472 3424/3424/3440
Testing 3504 3472 3488
• Vektor kolom dalam V adalah vektor basis dengan mencerminkan r yang merepresentasikan karakteristik spektral yang dipelajari dari contoh data EEG • Baris vektor dalam matriks U kemudian, mencerminkan bagaimana mempelajari pola yang dikodekan untuk spektral vektor data (berasosiasi dengan
Visualisasi data training subjek 1 dapat dilihat pada Gambar 1.
vektor baris matriks X ) Alternatif sederhana mengenai asal mula update perkalian untuk Least Square NMF, yang dikembangkan secara oroginal oleh Lee dan Seung [6].
2
MAKALAH SEMINAR TUGAS AKHIR PERIODE JANUARI 2010 Fungsi objektif Least Square yang diberikan sebagai :
Karena memerlukan kemampuan untuk data matriks yang tanpa batas, maka NMF diperluas menjadi beberapa variasi [4], yakni : 1 NMF Konveks 2 Semi NMF 3 Kernel NMF
2 1 X − UV T 2 . . . . . . . . . . . . . . . . . . . . . . . . . .( 2 )
J =
X
menunjukkan norm Frobenius dari sebuah matrik X . Mengambil batasan/constraint nonnegative
Dimana
U ≥0
4 METODE KERNEL NONNEGATIVE MATRIX FACTORIZATION
dan V ≥ 0 ke dalamlaporan, Lagrangian
diberikan sebagai :
LK =
1 X − UV T 2
2
{
} {
− tr ∆U T − tr ΩV T
Metode KNMF dipilih dari beberapa variasi metode NMF yang ada sebagai metode ekstraksi fitur EEG ini karena kasusnya adalah matriks nonnegatif, yang dapat dengan mudah dekembangkan. Asumsikan U = XW untuk W ≥ 0 dalam dekomposisi matriks
}
....(3)
Dimana ∆ ≥ 0 dan Ω ≥ 0 adalah pengali Lagrangian. Kondisi optimal KKT memerlukan :
X ≈ UV T Untuk ekstraksi fitur EEG, metode KNMF diturunkan dari kondisi KKT, dimana α − divergence dapat digunakan mengukur kesalahan dari NMF.
UV V − XV = ∆, . .. . . . . . . . . . . . . . .. . . . . . . . . . ( 4 ) T
VU T U − X TU = Ω, . . . . . . . . . . . . . . . .. . . . . . . . ( 5 ) ∂L ∂L =0 =0 ∂U ∂V Dimana hasil dari dan . KKT
[UV [VU
]
Hyekyoung Lee, Cichocki Andrzej dan Seungjin Choi dalam paper Kernel nonnegative matrix factorization for spectral EEG feature extraction [1] menyimpulkan mengapa digunakan metode KNMF untuk mengekstraksi fitur spektral diskriminatif dari time-frequency representasi data EEG, antara lain : 1 Dengan menggunakan KNMF dengan kernel linier, fitur spektral sangan mudah dihitung dengan perkalian matriks, dimana dengan NMF standar, ini tidak dengan mudah dilakukan, namun harus dilakukan berulang-ulang dengan faktor pengali matriks yang fix (perlu pseudoinverse matriks) 2 KNMF dengan kernel linier adalah kasus khusus convex-NMF, dengan syarat tiap kolom dalam matriks W memenuhi sum-to-one constraint. Semua perilaku KNMF diverifikasi dari percobaan pada dataset IDIAP EEG dalam kompetisi BCI III.
melengkapi kondisi slackness memerlukan : T T
V − XV ⨀ U = 0 . . . . . . . . . . . . . . . . . . . . ( 6 ) U − X T U ⨀U = 0 . . . . . . . . . . . . . . . . . ( 7 )
]
Dimana ⨀ menotasikan Hadarmard product (elemenwise multiplication) [3]. Persamaan (6) dan (7) menjadi dasar fungsi multiplicative update untuk matriks fitur U dan matriks basis V sebagai berikut:
U ←U ⨀
XV ............. ...........(8) UV TV X TU V ←V ⨀ . . . . . . . . . . . . . . . . . . . . . . . . .( 9 ) VU T U
Trik sederhana untuk mengembangkan kernel NMF adalah mengasumsikan bahwa fitur profil (vektor kolom U ) adalah kombinasi koveks dari profil frekuensi (vektor kolom dari X ) dari data spektral dalam dekomposisi NMF. U = XW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .( 11 )
Dimana pembagian dilakukan dalam elemen-wisemanner. Aturan ini tepat sama dengan satu usulan Lee dan Seung [6]. Saat sebuah matrik data set fitur matrik berbeda : 1 Matriks
U test
U test
X test
diberikan, asosiasinya
dapat dihitung dengan 2 cara yang
[ ]
Dimana tiap kolom dalam W menyediakan sum-to-one constraint. Dengan mensubtitusikan dugaan awal KNMF (11) ke dalam fungsi objektif Least Square (2) memberikan :
ditentukan oleh proyeksi LS,
U test = X test V T
−1
. . . . . . . . . . . . . . . . . . . . . . . ( 10 )
2 Ulangi update rule (9) sampai konvergen, dengan yang diperoleh dari fase training yang sudah fix.
JK =
V
1 X − XWV T 2
2
. . . . . . . . . . . . . . . . . . . . ( 12 )
Untuk menangani pertidaksamaan constraint W ≥ 0 dan V ≥ 0 , mempertimbangkan Lagrangian sesuai pada persamaan (3), 3
MAKALAH SEMINAR TUGAS AKHIR PERIODE JANUARI 2010
LK =
1 X − XWV T 2
{
} {
}
parameter Θ, ketika ∇J K = 0 saat konvergen tercapai [2]. Perlu diketahui bahwa penurunan dengan W dan V dihitung sebagai :
− tr ∆W T − tr ΩV T ..( 13)
2
Dimana ࢫ dan Ω adalah pengali Lagrangian. Berdasarkan (7) dan (9). KKT secara membutuhkan :
∂J K ∂J K ∂J K = − = KWV TV − KV . .( 24 ∂W ∂W ∂W
optimal
+
X XWV V − X XV = ∆ . . . . . . . . . . . . .. . . . ( 14 ) VW T X T XW − X T XW = Ω . . . . . . . . . . . .. . . .( 15 ) ∂LK ∂L Sebagai akibat dari = 0 dan K = 0, ∂W ∂V T
T
T
−
)
∂J K ∂J K ∂J K T = − ∂V = VW KW − KW .( 25 ∂V ∂ V +
Definisikan sebuah matriks kernel (matriks Gram) T
−
)
sebagai K = X X , entry (i, j ) merepresentasikan kesamaan antara dua frekuensi profil i dan j . Kemudian, Kondisi KKT melengkapi kondisi slackness memberikan :
Demikian, relasi (24) dengan η = 1 , satu dapat dengan mudah diturunkan update multiplicative (18) dan (19)
[KWV V − KV ]⨀W = 0 . . . . . . . . . .. . . . . . . ( 16 ) [VW KW − KW ]⨀ V = 0 . . . . . . . . .. . . . . . . . .( 17 ) T
5
UJI COBA DAN EVALUASI
T
Relasi ini berdasarkan pada perkalian sebagai berikut :
4.1 Perbandingan Metode NMF dan KNMF pada Contoh Data
V ←V ⨀
Matriks Data yang diberikan adalah :
KW . . . . . . . . . . . . . . . . . . . . .( 18 ) VW T KW KV . . . . . . . . . . . . . . . . . . . . . ( 19 ) W ←W ⨀ KWV T U
0.3692 0.1112 0.7803 X = 0.3897 0.2417 0.4039 0.0965
Seluruhnya, tugas akhir ini hanya menggunakan kernel linier
K = X T X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ( 20 ) Meskipun demikian, metode ini tetap untuk
K = φ T φ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . ( 21 ) dimana adalah sebuah matriks φ = φ ( X ij )
[
]
∇J K = [∇J K ] − [∇J K ]− . . . . . . .. . . . . . . . . . . . .( 22 ) +
[
]+ > 0
[
dan ∇J K
]− > 0 .Seperti sebuah
1.5752 1.1690 0.7447 0.0811
1.2348 1.7317 0.6868 0.7757 1.3532 1.6477 0.1835 0.4868 1.0598 1.6491 0.1890 0.9294
dengan random dengan random
Dengan melakukan ekstraksi fitur menggunakan metode NMF, maka akan menghasilkan : Matriks fitur : 0.3041 0.7813 0.0948 1.0772 0.0722 1.2274 U NMF = 1.1926 0.2046 1.1005 0.4994 1.2695 0.4915 1.2652 0.2627 Matriks Basis V :
kasus, update perkalian untuk parameter Θ mempunyai bentuk :
[∇J K ]− Θ ← Θ ⨀ + [∇J K ]
0.9561 0.0430 0.2963 1.7802
Dimana : • Tiga baris pertama akan dibangkitkan menambahkan distribusi uniform (U[0,1]) numbers [0,0,0,0,1]T. • Empat baris terakhir dibangun menambahkan distribusi uniform (U[0,1]) numbers [0,1,1,0,0]T.
transformasi dalam ruang fitur. Kami juga menyediakan sebuah alternatif penurunan dari rules (18) dan (19). Anggap bahwa gradien dari fungsi tujuan (12) mempunyai sebuah dekomposisi dari bentuk
Dimana ∇J K
0.1320 0.8212 0.4509 1.3685 0.9421 0.0154 0.5407 1.6256
. . . . . . . . . . . . . .. . . . . . ( 23 ) •η
Dimana ( ) •η menunjukkan kekuatan elemen-wise dan η adalah sebuah angka yang diperoleh dari fase training (0 < η ≤ 1) . Ini dapat dengan mudah dilihat bawa update perkalian (24) memelihara nonnegatif dari
4
MAKALAH SEMINAR TUGAS AKHIR PERIODE JANUARI 2010
VNMF
0.1141 0.8918 = 1.2749 0.2803 0.0111
0.3975 0.5576
Selanjutnya akan diperlihatkan bagaimana KNMF mampu menyelesaikan permasalahan data yang nilai perbedaan fiturnya tidak terlalu besar. Matriks Data yang diberikan adalah :
0.0724
0.3425 1.5393
0.3803 0.4021
0.0861 0.7988
Dimana : • Tiga baris pertama akan dibangkitkan dengan menambahkan distribusi uniform U[0,0.5] random numbers [0,0,0,0,0.5]T. • Empat baris terakhir dibangun dengan menambahkan distribusi uniform uniform U[0,0.5] random numbers [0,0,0,0,0.5]T. Dengan melakukan ekstraksi fitur menggunakan metode NMF, maka akan menghasilkan : Matriks Fitur :
Dengan melakukan ekstraksi fitur menggunakan metode KNMF, maka akan menghasilkan : Matriks Fitur :
U KNMF
1.1076 1.2566 1.4718 = 0.1937 0.7409 0.7002 0.3898
Matriks Basis :
VKNMF
0.3017 0.2421 = 0.0000 0.2189 1.2282
0.3371 0.2630 0.9133 0.1067 0.8998
X =
0.5499
1.3278
1.4152 1.5348 1.5296
1.0517
0.1622 0.6541 0.1524 0.9619 0.7599
0.7943 0.6892 0.8258 0.0046 1.3001
0.3112 1.2842 1.0383 0.7749 0.4314
0.1656 0.5838 0.5782 0.8687 0.1818 0.6020 0.7290 0.9427 0.0844 0.2638 0.5285 0.9505 1.4961 0.8173 0.9106
1.1996 0.2081 1.6799 U NMF = 0.5987 1.2498 0.0699 0.9144
0.2372 0.0000
Tiap vektor kolom dari matriks basis VNMF dan VKNMF merepresentasikan vektor basis ideal karena entri terakhir pada vektor kolom pertama jauh lebih besar dengan entri yang lain pada kolom yang sama, dan entri kedua dan ketiga pada kolom kedua jauh lebih besar dari entri lainnya pada kolom yang sama.
Matriks Basis :
0.4215 0.3539 V NMF = 0.6637 0.0000 0.6596
Tiap vektor baris dalam matriks fitur UNMF dan UKNMF merupakan variabel indikator untuk pengelompokkan (cluster) Sebagai contoh, baris pertama dalam UKNMF mempunyai 2 entri 1.1076 dan 0.5499 dimana elemen pertama lebih besar daripada elemen kedua, sehingga vektor baris pertama akan masuk pada cluster 1. Meneliti matriks fitur UKNMF dengan cara ini, dapat melihat bahwa kedua matriks fitur mengidentifikasi bahwa tiga vektor baris pertama sebagai cluster 1 dan empat vektor baris terakhir sebagai cluster 2.
0.0284
0.8158 0.0086
1.0605
0.8657 0.2973 0.8465
0.0907
0.5435 0.9202 0.1932 0.7899
Dari hasil matriks basis dan matriks fitur diatas, terlihat bahwa metode NMF untuk kasus ini tidak dapat mengekstraksi matriks fitur dengan hasil klasifikasi yang tepat, yakni baris 1,3,4, dan 6 matriks U terklasifikasi menjadi kolom pertama lebih besar dari kolom kedua, sedangkan baris 2,5, dan 7 matriks U terklasifikasi menjadi kolom pertama lebih kecil dari kolom kedua, sehingga dua bagian tersebut berbeda mutlak. Hasil ini tidak sesuai dengan matriks data yang dibangun dengan dua cara yang berbeda atas 3 baris pertama dan 4 baris terakhir.
Dari hasil matriks basis dan matriks fitur diatas, terlihat bahwa metode NMF dan KNMF untuk kasus ini berhasil mengekstraksi matriks fitur dengan hasil klasifikasi yang tepat, yakni tiga baris pertama matriks U terkluster terpisah dengan empat baris terakhir. Hasil ini sesuai dengan matriks data yang dibangun dengan dua cara yang berbeda atas 3 baris pertama dan 4 baris terakhir.
Dengan melakukan ekstraksi fitur menggunakan metode KNMF, maka akan menghasilkan : 5
MAKALAH SEMINAR TUGAS AKHIR PERIODE JANUARI 2010 0.85
0.8244 0.6760 1.2189 U KNMF = 0.4500 0.8834 0.1983 0.3275
0.4682
KNMF NMF
0.8
Keakuratan Klasifikasi
Matriks Fitur :
0.5309 0.5578
1.0062
0.6408 0.6234
1.0990
0.75 0.7 0.65 0.6 0.55 0.5 0
2
4
6
8
10
12
14
16
18
20
Jumlah Fitur
0.4255 0.0252 VKNMF = 0.1280 0.0000 1.0540
(a) 0.1863 1.0277
KNMF NMF
0.8
1.1014
Kakuratan Klasifikasi
Matriks Basis :
0.7437 0.0011
Tiap vektor kolom dari matriks basis VKNMF merepresentasikan vektor basis ideal karena entri terakhir pada vektor kolom pertama jauh lebih besar dengan entri yang lain pada kolom yang sama, dan entri kedua dan ketiga pada kolom kedua jauh lebih besar dari entri lainnya pada kolom yang sama.
0.75 0.7 0.65 0.6 0.55 0.5 0
2
4
6
8
10
12
14
16
18
Jumlah Fitur
(b) Gambar 2. Grafik Pengaruh Penambahan Jumlah Fitur dalam ekstraksi fitur menggunakan metode NMF (warna biru) dan KNMF (warna merah) terhadap Keakuratan Klasifikasi pada Subjek 1 pada running pertama (a) dan running kedua (b) dengan inisialisasi matriks random
Tiap vektor baris dalam matriks fitur UKNMF merupakan variabel indikator untuk pengelompokkan (cluster). Sebagai contoh, baris pertama dalam UKNMF mempunyai 2 entri 0.8244 dan 0.4682 dimana elemen pertama lebih besar daripada elemen kedua, sehingga vektor baris pertama akan masuk pada cluster 1. Meneliti matriks fitur UKNMF dengan cara ini, dapat melihat bahwa kedua matriks fitur mengidentifikasi bahwa tiga vektor baris pertama sebagai cluster 1 dan empat vektorbaris terakhir sebagai cluster 2.
Dari Gambar 2, dapat dilihat bahwa nilai keakuratan klasifikasi data EEG melalui ekstraksi fitur menggunakan metode NMF dan KNMF tidak jauh berbeda, namun, dengan menggunakan KNMF, cenderung lebih bagus.
Dari hasil matriks basis dan matriks fitur diatas, terlihat bahwa metode KNMF untuk kasus ini berhasil mengekstraksi matriks fitur dengan hasil klasifikasi yang tepat, yakni tiga baris pertama matriks U terkluster terpisah dengan empat baris terakhir. Hasil ini sesuai dengan matriks data yang dibangun dengan dua cara yang berbeda atas 3 baris pertama dan 4 baris terakhir.
Dalam hal keefektifan waktu, KNMF jauh lebih bagus daripada NMF. Dengan menggunakan KNMF, waktu yang digunakan hanya sekitar 60% dari waktu yang diperlukan untuk ekstraksi fitur menggunakan NMF. Hal ini adapat dilihat pada Tabel 2.
4.2 Uji Coba pada DATA EEG sebenarnya
Tabel 2 Perbandingan Waktu Kerja Sistem (Klasifikasi Data EEG subjek 2) dengan Ekstraksi Fitur Menggunakan NMF dan KNMF NMF KNMF cputime 1409.4 930.19(*) 24 menit 8 detik 14 menit 7 detik (*) Run time
Uji Coba pertama dilakukan dengan mengambil 7000 data PSD data training subjek 1 sebagai data training, dan sisanya (10528-7000=3528) data PSD data training subjek 1 sebagai data testing. Dengan mengambil 1 sampai 20 fitur, akan diperoleh keakuratan klasifikasi yang dapat dilihat pada Gambar 2.
6
20
MAKALAH SEMINAR TUGAS AKHIR PERIODE JANUARI 2010 Grafik Pengaruh Jumlah Fitur terhadap Keakuratan Klasifikasi Subjek 2
0.65 KNMF NMF
2. Tingkat keakuratan klasifikasi data EEG dari proses ekstraksi fitur menggunakan metode Nonnegative Matrix Factorization tidak jauh berbeda dengan tingkat keakuratan klasifikasi data EEG dari proses ekstraksi fitur menggunakan Kernel Nonnegative Matrix Factorization. 3. Penggunaan KNMF untuk ekstraksi fitur EEG jauh lebih efisien dibandingkan dengan penggunaan NMF. Dengan menggunakan KNMF, waktu dapat dihemat ratarata 35-40%. 4. Penggunaan matriks random pada inisialisasi matriks basis V, matriks fitur U dan juga matriks W pada metode Nonnegative Matrix Factorization dan metode Kernel Nonnegative Matrix factorization tidak menjadi masalah karena terbukti proses multiplicative update kedua metode tersebut menghasilkan matriks fitur yang tidak jauh berbeda pada running yang berbeda.
Keakuratan Klasifikasi
0.6
0.55
0.5
0.45
0.4 0
2
4
6
8
10
12
14
16
18
20
Jumlah Fitur
Gambar 3 Grafik Pengaruh Penambahan Jumlah Fitur dalam ekstraksi fitur menggunakan metode NMF (warna biru) dan KNMF (warna merah) terhadap Keakuratan Klasifikasi pada Subjek 2 Uji Coba pertama dilakukan dengan mengambil 7000 data PSD data training subjek 2 sebagai data training, dan sisanya (10400-7000=3400) data PSD data training subjek 1 sebagai data testing. Dengan mengambil 1 sampai 20 fitur, akan diperoleh keakuratan klasifikasi yang dapat dilihat pada Gambar 3.
REFERENSI [1] Lee, Hyekyoung, Choi, Seungjin, dan Cichocki, Andrzej. April, 2009. Kernel Nonnegative Matrix Factorization for Spectral EEG feature Extraction. [2] Lee, Hyekyoung, Kims, Yong-Deok , Cichocki, Andrzej, dan Choi, Seungjin. Agustus, 2007. Nonnegative Tensor Factorization for Continuous EEG Classification. International Journal of Neural Systems 17 (4) (2007) 305–317. [3] Million, Elizabeth. 2007. The Hadamard Product. 12 Agustus 2007. Creative Commons Attribution 3.0 United States License. [4] T. Li, C. Ding. 2006 The relationships among various nonnegative matrix factoriza- tion methods for clustering. Proceedings of the IEEE International Conference on Data Mining, Hong Kong. [5] Universitas Gajah Mada. 2006. Analisis Multivariat sesi-4. Universitas Gajah Mada. Lee, Daniel D. dan Seung, H. Sebastian.. 2001. [6] Algorithms for Non-negative Matrix Factorization. Advances in Neural Information Processing Systems, 13, MIT Press, Cambridge.
Dalam hal keefektifan waktu, KNMF jauh lebih bagus daripada NMF. Dengan menggunakan KNMF, waktu yang digunakan hanya sekitar 30% dari waktu yang diperlukan untuk ekstraksi fitur menggunakan NMF. Hal ini dapat dilihat pada Tabel 3.
Tabel 3 Perbandingan Waktu Kerja Sistem (Klasifikasi Data EEG subjek 2) dengan Ekstraksi Fitur Menggunakan NMF dan KNMF
cputime Run time (*)
6
NMF
KNMF
1680.5 27 menit 17 detik
371.38 (*) 9 menit 28 detik ( ) *
menunjukkan waktu yang lebih efisien
KESIMPULAN
Dari uji coba yang telah dilakukan dan setelah menganalisis hasil pengujian terhadap implementasi metode ekstraksi fitur pada pengklasifikasian data EEG dalam dataset format IDIAP dapat diambil beberapa kesimpulan antara lain: 1. Penambahan jumlah fitur yang diambil dalam proses ekstraksi fitur mempengaruhi keakuratan proses klasifikasi matriks fitur terhadap kelas label yang tepat. Semakin banyak fitur yang diambil, tingkat keakuratan proses klasifikasi matriks fitur cenderung lebih bagus.
7
