Jurnal Tugas Akhir

PENGENALAN INDIVIDU BERDASARKAN GAIT

MENGGUNAKAN PCA DAN K-NEAREST NEIGHBOR

Putri Chairina¹, Achmad Rizal², Tjokorda Agung BW²

^{1, 2, 3}Departemen Teknik Informatika Institut Teknologi Telkom, Bandung

¹putri.chairina@gmail.com, ²arl@sttelkom.co.id, ³cok@stttelkom.ac.id

Abstrak

Identifikasi berdasarkan gait memiliki kelebihan dalam hal sifatnya yang tidak mudah untuk ditiru dan diubah, serta sensor yang dapat bekerja dari jarak jauh.

Tugas akhir ini akan mencoba mengimplementasikan metode reduksi data Principal Component Analysis (PCA) dan metode klasifikasi K-Nearest Neighborhood (KNN) dalam identifikasi individu berdasarkan gait. PCA berfungsi untuk membentuk data baru yang tingkat korelasinya rendah. Dengan PCA, ukuran data yang baru akan lebih kecil dibandingkan data aslinya. Proses selanjutnya adalah klasifikasi menggunakan KNN. KNN merupakan metode klasifikasi instance-based. KNN akan menggunakan metode perhitungan nilai ketidakmiripan. Dalam penelitian ini, metode perhitungan nilai ketidakmiripan yang digunakan adalah Euclidean, Square Euclidean, dan Manhattan.

Dalam penelitian ini, ketiga metode perhitungan tersebut menghasilkan nilai akurasi yang sama. Penggunaan PCA pun terbukti telah menurunkan tingkat penggunaan waktu untuk eksekusi sebesar 26,67%. Selain itu, PCA juga telah meningkatkan hasil akurasi identifikasi dengan rata-rata peningkatan sebesar 41,67%. Akurasi tertinggi dalam penelitian ini adalah 75%.

Kata kunci : identifikasi, gait, PCA, KNN.

1. Pendahuluan

Gait adalah cara atau sikap berjalan kaki.[1] Tiap orang memiliki Gait yang berbeda. Karakteristik inilah yang kemudian digunakan untuk identifikasi individu. Kelebihan Gait adalah proses pengambilan Gait dapat dilakukan dari jarak jauh. Tidak seperti identifikasi sidik jari, iris mata, suara, dan wajah yang memerlukan kedekatan antara objek dengan sensor. Kelebihan identifikasi Gait lainnya adalah ia sulit untuk disembunyikan ataupun direkayasa. [2]

Ada dua pendekatan Gait, yakni pendekatan holistik dan model.[2] Pendekatan holistik memandang ciri dari keseluruhan bentuk tubuh.[3] [4] [5][6] Sedangkan pendekatan model dengan menganalisa bagian-bagian tubuh tertentu (tangan, kaki, kepala).[1] Kedua pendekatan tersebut menekankan pada ekstraksi ciri dari bentuk tubuh, bukan kinematik (kecepatan, koordinat) karena ia lebih signifikan dalam menentukan akurasi identifikasi daripada kinematik.[3] Siluet merupakan salah satu bentuk pendekatan holistik. Siluet didapatkan dengan memisahkan objek dari latar belakangnya (background substraction).

Dalam penelitian ini, akan dilakukan pengidentifikasian Gait berdasarkan analisa siluet. Siluet akan dipilih berdasarkan yang paling berpengaruh dalam menentukan satu siklus Gait.[6] Kemudian siluet 2D ini diubah menjadi sinyal 1D untuk mempercepat proses pengenalan. Perubahan gambar 2D menjadi sinyal 1D menggunakan metode perhitungan jarak antara titik tengah badan dengan titik terluar kontur siluet (diameter).[4] Kemudian dilakukan proses transformasi data dengan menggunakan PCA (Principal Component Analysis) yang berfungsi untuk mengurangi dimensi data.[8] Untuk proses klasifikasi, digunakan KNN dengan menggunakan tiga metode perhitungan nilai kemiripan dengan Euclidean-distance [9], Square Euclidean, dan Manhattan distance. Efektifitas kombinasi dari kedua metode ini dalam mengidentifikasi individu berdasarkan gait kemudian akan dianalisa.

2. Principal Component Analysis (PCA)

2.1 Definisi

Principal Compinent Analysis (PCA) merupakan salah satu metode pre-processing data yang akan melakukan dekomposisi data sehingga menghasilkan koefisien-koefisien yang tidak berkorelasi. Tujuan PCA adalah menangkap variasi total pada citra latih dan merepresentasikan variasi tersebut dalam variabel-variabel yang jumlahnya lebih sedikit. PCA dikenal juga dengan sebutan transformasi Karhunen-Loeve dan transformasi Hotteling.

2.2 Algoritma PCA

Berikut ini adalah algoritma PCA yang digunakan dalam penelitian ini [11, 12] :

1. Mengumpulkan data dalam sebuah matriks (matriks ensamble)

Tiap data disimpan dalam bentuk vektor kolom. Kolom menunjukkan jumlah percobaan dan baris menunjukkan titik ciri dari tiap percobaan.

2. Membuat data normal dengan mengurangi setiap titik ciri dari data dengan mean. Mean tiap titik ciri dihitung dengan mencari rata-rata dari seluruh kolom data untuk setiap titik cirinya.

3. Menghitung matriks kovarian dari data normal ¹⁾

4. Menghitung nilai dan vektor eigen dari matriks kovarian.

5. Membuat principal component (PC). Nilai eigen disusun secara terurut menurun. Kemudian vektor eigen disusun sesuai dengan nilai eigennya. Vektor eigen yang tersusun itulah yang disebut sebagai PC.

6. Membentuk data baru

Data baru dihasilkan dengan mengalikan vektor transpose dari principal component dengan data normal.

3. K-Nearest Neighbor (KNN)

3.1 Definisi

K-Nearest Neighborhood (KNN) adalah metode klasifikasi instance-based yang merupakan pengembangan dari 1-NN. 1-NN Dari sekumpulan objek latih,1-NN akan memilih satu objek latih yang memiliki sifat ketetanggaan (neighborhood) yang paling dekat. Sifat ketetanggaan ini didapatkan dari perhitungan nilai kemiripan ataupun ketidakmiripan. Tetangga terdekat adalah objek latih yang memiliki nilai kemiripan terbesar ataupun ketidak-miripan terkecil. Perbedaannya KNN dengan 1-NN terletak pada jumlah tetangga yang dipilih. 1-NN hanya akan memilih satu tetangga terdekat. Sedangkan KNN akan memilih K-tetangga terdekat. Dari K-tetangga itu, KNN akan menentukan hasil klasifikasi dengan melihat jumlah kemunculan dari kelas dalam K-tetangga yang terpilih. Kelas yang paling banyak muncullah yang akan menjadi kelas hasil klasifikasi.

3.2 Algoritma KNN

Berikut ini adalah algoritma KNN :

1. Menghitung nilai kemiripan/ketidakmiripan (similarity/dissimilarity distance). Metode perhitungan yang diganakan ada tiga, yaitu :

• Euclidean distance,
• Square euclidean distance
• Manhattan distance

2. Mengurutkan hasil dari perhitungan nilai kemiripan/ketidakmiripan secara terurut menurun.

3. Menentukan nilai K dan mengambil K-jumlah tetangga dari hasil langkah 2.

4. Menentukan kelas dari data uji berdasarkan kelas yang paling banyak muncul dari hasil langkah 3.

4. Analisis Hasil Pengujian

4.1 Pengaruh kondisi objek terhadap akurasi identifikasi

Dari tabel 1 dapat dilihat akurasi identifikasi/ (correct correlation rate/CCR). Rata-rata CCR dengan menggunakan siluet puncak adalah 45,14% dan rata-rata akurasi identifikasi dengan menggunakan siluet lembah adalah 35,42%.

4.2 Pengaruh penggunaan PCA terhadap akurasi identifikasi dan waktu eksekusi

Tabel 2. Pengaruh penggunaan PCA terhadap CCR dan waktu eksekusi

Dari tabel 2 dapat dilihat dari segi akurasi bahwa nilai CCR terbesar yang didapat ketika sistem identifikasi tidak menggunakan PCA adalah 58,33% dan nilai CCR terendah adalah 33,33%. Sedangkan ketika sistem menggunakan PCA nilai CCR meningkat menjadi 75%.

Dari segi waktu eksekusi, dapat dilihat bahwa pada sistem identifikasi yang tidak menggunakan PCA waktu eksekusi terbesarnya adalah 150,92 milidetik. Sedangkan ketika sistem menggunakan PCA, waktu eksekusi terbesarnya adalah 114,67 milidetik.

4.3 Pengaruh jumlah PC yang digunakan

Dari tabel 4-3 dapat dilihat bahwa nilai CCR yang paling besar, 75%, terjadi pada saat jumlah PC yang digunakan adalah 3. Sedangkan nilai CCR terendah, 8,33%, terjadi pada saat jumlah PC yang digunakan adalah 2 dan 7.

4.4 Analisis nilai K dan metode perhitungan nilai ketidakmiripan

Tabel 3. Pengaruh metode perhitungan nilai kemiripan terhadap CCR

Tabel 4. Pengaruh metode perhitungan nilai kemiripan terhadap waktu eksekusi

Dari tabel 3 dapat dilihat bahwa ketiga metode perhitungan nilai ketidakmiripan menghasilkan CCR yang sama pada tiap pengujian. Selain itu dapat juga dilihat bahwa nilai K yang terlalu kecil menghasilkan akurasi yang rendah. Hal ini disebabkan dengan kecilnya nilai K, maka klasifikasi akan lebih terpengaruh oleh noise. Nilai K yang terlalu besar pun juga menghasilkan akurasi yang rendah karena dengan semakin besarnya nilai K, semakin besar noise yang diterima.

Dari waktu eksekusinya, Euclidean membutuhkan waktu eksekusi yang relatif lebih lama daripada dua metode lainnya. Dengan rata-rata waktu eksekusi 86,92 milidetik. (Tabel 4)

5. Kesimpulan dan Saran

5.1 Kesimpulan

Beberapa hal yang dapat disimpulkan dari penelitian ini adalah :

1. Dari pengujian pengaruh kondisi siluet terhadap akurasi identifikasi, diketahui bahwa rata-rata akurasi identifikasi dengan menggunakan siluet puncak (objek dalam kondisi puncak) adalah 45,14%. Sedangkan rata-rata akurasi identifikasi dengan menggunakan siluet lembah (objek dalam kondisi lembah) adalah 35,42%. Sehingga dapat diambil kesimpulan bahwa siluet puncak dapat menghasilkan akurasi yang lebih baik daripada siluet lembah.
2. Dari pengujian pengaruh penggunaan PCA terhadap waktu eksekusi diperoleh waktu aksekusi yang lebih cepat pada saat identifikasi menggunakan PCA dibandingkan dengan identifikasi yang tidak menggunakan PCA, dengan rata-rata penurunan waktu eksekusi sebesar 26,67%.
3. Dari pengujian pengaruh penggunaan PCA terhadap akurasi identifikasi, diperoleh nilai CCR yang lebih tinggi pada saat sistem menggunakan PCA dengan rata-rata peningkatan akurasi identifikasi adalah sebesar 41,67%.
4. Dari pengujian pengaruh jumlah principal component terhadap akurasi identifikasi, diperoleh nilai akurasi terbesar, yaitu 75%, pada saat digunakan tiga buah principal component.
5. Dari pengujian pemilihan nilai K, dengan tiga buah principal component, diperoleh nilai CCR maksimal, yaitu 75% pada saat nilai K=3,4,6, dan 7.
6. Dari pengujian pemilihan metode perhitungan nilai ketidakmiripan diperoleh hasil akurasi yang sama antara ketiga metode tersebut. Sedangkan untuk waktu eksekusinya, Euclidean membutuhkan waktu eksekusi yang lebih lama dibandingkan kedua metode lainnya, dengan rata-rata waktu eksekusi sebesar 86,92 milidetik.
7. Kondisi puncak berbeda dengan kondisi seseorang sedang berdiri tegak. Pada saat berdiri tegak, seseorang berpijak dengan kedua kakinya. Pada saat kondisi puncak, seseorang bertumpu pada salah satu kaki saja. Ada aspek temporal yang diperhatikan pada saat kondisi puncak.

5.2 Saran

Saran dari penulis terhadap kelanjutan dari penelitian ini adalah :

1. Menggunakan metode pengambilan ciri yang lainnya.
2. Menggunakan metode klasifikasi selain KNN
3. Menggunakan metode optimalisasi data selain PCA.
4. Menggunakan video sebagai masukan sistem.
5. 
   

[1]	Dawson, Mark R., 2002, Gait Recognition, London, Imperial Collage of Science, Technology and Medicine.
[2]	Boulgouris, N. V., Dimitrios Hatzinakos, Konstantinos N. P., 2005, Gait Recognition: A Challenging Signal Processing Technology for Biometric Identification, IEEE Signal Processing Magazine.
[3]	Liu, Zongyi, Sudeep Sarkar, 2006, Improved Gait Recognition by Gait Dynamics Normalization, USA, IEEE Transaction on Pattern Analysis and Machine Intelligence vol.28 no. 6.
[4]	Tan, Tieniu, Liang Wang, Huazong Ning, Weiming Hu, 2003, Silhouette Analysis-Based Gait Recognition for Human Identification, USA, IEEE Transaction on Pattern Analysis and Machine Intelligence.
[5]	Abdelkader, Chiraz Ben, Ros Cutler, Harsh Nanda, Larry Davis, EigenGait:Motion-based Recognition of People using Image Self-similarity, University of Maryland Collage Park.
[6]	Collins, R. T., R. Gross, J. Shi, 2002, Silhouette-based Human Identification from Body Shape and Gait, Washington DC, IEEE Conf. Automatic Face and Gesture Recognition.
[7]	CASIA Gait Database, http://www.sinobiometrics.com
[8]	Davies, A.M.C. Back to Basic: the principal of Principal Component Analysis [PDF]
[9]	Anonim. 2007. Euclidean-distance . http://en.wikipedia.org/wiki/Euclidean_distance (10:42, 11 November 2007)
[10]	Parades, Roberto dan Enrique Vidal, 2005, Learning Weighted Metrics to Minimize Nearest-Neighbor Classification Error, Spanyol, Institut Teknologi Informatika Spanyol.
[11]	Jonathon Shlens, 2005, A Tutorial on Principal Component Analysis, California, Univeristy of California.
[12]	Roth, Peter M and Martin Winter, 2008, Survey of Appearance-based methods for Object Recognition, Austria, Graz University of Technology

——————
Tulisan lainnya (tips, jurnal, proposal, dll) tentang Tugas Akhir saya, dapat dilihat di : kategori “Tugas Akhir” (klik saja disini).
——————