imputasi missing data dengan k-nearest neighbor...

IMPUTASI MISSING DATA DENGAN K-NEAREST NEIGHBOR DAN ALGORITMA GENETIKADAN ALGORITMA GENETIKA

Oleh:Ucik Mawarsari

NRP. 1310201714

Pascasarjana Jurusan StatistikaFakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA)

Institut Teknologi Sepuluh Nopember

Outline2

1. Pendahuluan

2. Tinjauan Pustaka. jaua usta a

3. Metodologi

4. Hasil dan Pembahasan

5. Kesimpulan dan Saran

6. Daftar Pustaka

01/05/2012Seminar Hasil Tesis

Pendahuluan (1)3

Survei skalabesar Nonrespon

Unit

It ImputasiModel-donor

Item Imputasidata

Real-donor


Pendahuluan (2)4

MetodeKNNI

Survei IBS Nonrespon

Unit

Item

Variabelbahan

b k dImputasi

d t

Metodehibrida

KNNI-GAte baku dan

penolongdata

Metodehibridahibrida

ANN-GA


Pendahuluan (3)5

Rumusan

• Bagaimana melakukan imputasi missing data dengan metode KNNI.• Bagaimana melakukan imputasi missing data dengan metode hibrida

KNNI-GA untuk seleksi dan pembobotan variabel.• Bagaimana kinerja metode KNNI dan metode hibrida KNNI-GA

dibandingkan metode imputasi lainMasalah dibandingkan metode imputasi lain.

• Melakukan imputasi missing data dengan metode KNNI.• Melakukan imputasi missing data dengan metode hibrida KNNI-GA

untuk seleksi dan pembobotan variabel.• Melakukan perbandingan kinerja metode KNNI dan metode hibrida

Tujuan• Melakukan perbandingan kinerja metode KNNI dan metode hibrida

KNNI-GA dengan metode imputasi lain.


Pandahuluan (4)6

M b ik t d lt tif d t di k l h BPS d l

Manfaat

• Memberikan metode alternatif yang dapat digunakan oleh BPS dalammelakukan imputasi missing data, khususnya pada data SurveiPerusahaan Industri Besar dan Sedang.

• Mengembangkan wawasan keilmuan mengenai metode imputasi danpenerapannya.penerapannya.

Batasan

• Permasalahan penelitian dibatasi pada cakupan Survei Perusahaan Industri Besar dan Sedang Provinsi DKI Jakarta tahun 2008 padakategori perusahaan industri sedang KBLI 18.

• Metode imputasi lain yang dibandingkan adalah metode hibrida ANN-Al it G tik (ANN GA)Batasan Algoritma Genetika (ANN-GA).

• Pola missing data pada kasus ini adalah pola missing data univariatdengan asumsi mekanisme Missing Completely at Random (MCAR).


Tinjauan Pustaka (1)7

Missing Data

• Pola missing data (Saekhoo, 2008)• File matching missing data• Univariat missing data• Monotone missing data• General pattern missing data

• Mekanisme missing data (Little dan Rubin, 1987):• Missing Completely at Random (MCAR)• Missing at Random (MAR)


g ( )• Missing Not at Random (MNAR)


K-Nearest Neighbor Imputation (KNNI)

• Ukuran jarak yang digunakan adalah jarak euclidian:

• Pemilihan observasi terdekat dilakukan dengan hanya mempertimbangkan observasiyang tidak memuat nilai missing pada variabel yang bersesuaian pada observasi target.Nil i K di k d l h K• Nilai K yang digunakan adalah 2<=K<=15

• Prosedur estimasi yang digunakan adalah weighted mean estimation:



Algoritma Genetika (GA)

• Algoritma genetika merupakan algoritma untuk memecahkan suatu pencarian nilaid l l h i i d i ik d khl k hiddalam masalah optimasi dengan meniru proses genetik pada makhluk hidup

• Individu merepresentasikan sebuah solusi pada permasalahan yang dihadapi. • Individu dikodekan dalam bentuk kromosom yang terdiri dari komponen genetik

terkecil, yaitu gen. R t i k d t b bil bi i t t bil iil • Representasi kromosom dapat berupa bilangan biner, integer, ataupun bilangan riil.

• Pada individu-individu tersebut kemudian dilakukan proses evaluasi nilai fitness, seleksi, perkawinan silang (crossover), mutasi, elitism dan replacement sehinggamembentuk populasi baru yang memiliki kriteria yang lebih baik.

• Setelah beberapa generasi terbentuk algoritma akan konvergen pada individu terbaik• Setelah beberapa generasi terbentuk, algoritma akan konvergen pada individu terbaikyang diharapkan merepresentasikan solusi optimal dari permasalahan yang dihadapi.


Tinjauan Pustaka (4)

Siklus algoritma genetika

10

Populasi awal Evaluasi fitness Seleksi

Crossover danmutasi

Elitism danreplacement



Survei Industri Besar dan Sedang (IBS)

• Survei Industri Besar dan Sedang (IBS) Tahunan dilakukan untuk memperoleh informasidari perusahaan-perusahaan yang bergerak di bidang industri.

• Beberapa konsep terkait dengan survei IBS (BPS, 2008) adalah:• Industri pengolahan adalah suatu kegiatan ekonomi yang melakukan kegiatan

mengubah suatu barang dasar menjadi barang jadi atau setengah jadi, dan sifatnyalebih dekat kepada pemakai akhir.lebih dekat kepada pemakai akhir.

• Jasa industri adalah kegiatan industri yang melayani keperluan pihak lain.• Nilai tambah adalah besarnya output dikurangi besarnya input (biaya antara).


Metodologi (1)12

Data

• Data yang digunakan adalah data hasil Survei IBS 2008 kategori perusahaan industrisedang Provinsi DKI Jakarta pada KBLI 18sedang Provinsi DKI Jakarta pada KBLI 18.

• Variabel yang digunakan: nilai pendapatan (X1), nilai upah/gaji pekerja (X2), nilai bahanbakar (X3), nilai tenaga listrik (X4), nilai pengeluaran lain (X5), dan nilai bahan bakudan penolong (X6)dan penolong (X6).

• Imputasi missing data dilakukan pada variabel nilai bahan baku dan penolong (X6).


Metodologi (2)13

StartGambar 1. Diagram Alir Penelitian

Membangkitkan 3 data simulasi terdiri dari 6

variabelData Survei IBS

Menghilangkan nilai X6 sebanyak 10%

Imputasidengan KNNI

Imputasi denganKNNI-GA

Imputasi denganANN-GAdengan KNNI KNNI GA

Optimasi K danseleksi variabel

Optimasi K danpembobotan

variabel

ANN GA

Membandingkan nilai RMSE danwaktu running dari masing-masing

metode

End


End

Metodologi (3)14

M t d Hib id KNNI GAMetode Hibrida KNNI-GA

• Metode 1: KNNI-GA untuk seleksi variabel. • Contoh kromosom individu yang terbentuk adalah : [1 1 0 1 1]• Contoh kromosom individu yang terbentuk adalah : [1 1 0 1 1]• String tersebut akan dikodekan dalam KNNI menjadi, variabel yang berkontribusi

dalam proses imputasi dengan KNNI adalah variabel pertama, kedua, keempat, dankelima. Variabel ketiga tidak diikutsertakan karena berkode 0.

• Metode 2: KNNI-GA untuk pembobotan variabel.• Contoh kromosom individu yang terbentuk adalah : [10001 00110 01100 10101 01011]• String tersebut akan dikodekan dalam KNNI menjadi, bobot untuk variabel pertama

adalah 10001, nilai desimalnya adalah 17, sehingga bobot variabel pertama adalah, y 7, gg p17/31=0,5484. Langkah yang sama dilakukan untuk variabel kedua s.d kelima.

• Untuk menentukan nilai K optimum pada metode hibrida KNNI-GA, nilai K direpresentasikan dalam 4 gen biner. Sebagai contoh adalah: [1 0 0 0]. String biner

b k dik d k k d l d KNNI j di il i K di k


tersebut akan dikodekan ke dalam metode KNNI menjadi, nilai K yang digunakanadalah K=8.

Metodologi (4)15

M t d Hib id KNNI GAMetode Hibrida KNNI-GA

• Langkah dalam algoritma genetika selanjutnya adalah:• Membangkitkan secara random sebanyak 50 individu dalam populasi• Membangkitkan secara random sebanyak 50 individu dalam populasi.• Menghitung nilai fitness untuk setiap individu dalam populasi.• Membentuk individu baru dengan melakukan seleksi roullete wheel, single point

crossover dengan probabilitas (Pc) sebesar 0.8, dan mutasi dengan probabilitas (Pm) sebesar 0.2. Kemudian melakukan elitism dan replacement sehingga diperolehp gg ppopulasi baru.

• Memilih individu terbaik dari populasi yang merupakan solusi terbaik setelah kriteriayang ditentukan terpenuhi, yaitu ketika mencapai generasi maksimum 50 generasiatau selisih nilai fitness terbaik dalam 5 generasi terakhir tidak lebih dari 1 x 10-8.


Hasil dan Pembahasan (1)16

Data Simulasi 1

• Simulasi pertama dilakukan dengan membangkitkan data berdistribusi normal lti i t b k b i t di i d i 6 i b l di tid k t d tmultivariat sebanyak 100 observasi yang terdiri dari 6 variabel, dimana tidak terdapat

korelasi antar variabel.• Tabel 1. Hasil Imputasi Missing Data pada Data Simulasi 1 dari 5 Kali Percobaan.

Hasil TerbaikR

Rata-rata

MetodeRata-rata

RMSE

Waktu Running

(detik)

Seleksi/Bobot Variabel

Nilai RMSE

KNNI [1 0 0 1 1] 10 64,9338 64,9338 0,9475KNNI GA Seleksi Variabel [1 0 0 1 1] 10 64 9338 64 9338 1 2107KNNI-GA Seleksi Variabel [1 0 0 1 1] 10 64,9338 64,9338 1,2107

KNNI-GA Bobot Variabel [0,3548 0,0323 0,0323 0,9032

0,3226]

9 62,9251 63,6884 2,9938


ANN-GA 67,5134 68,3198 1.063,4014


Gambar 2 Grafik Nilai Imputasi dan Nilai Aktual pada Data Simulasi 1

700

Gambar 2. Grafik Nilai Imputasi dan Nilai Aktual pada Data Simulasi 1

600

650

Nilai Aktual

500

550KNNI

KNNI-GA Seleksi

KNNI-GA Bobot

ANN-GA

400

450



Data Simulasi 2

• Simulasi kedua dilakukan dengan membangkitkan data berdistribusi normal multivariatb k b i t di i d i 6 i b l di X d X b k l isebanyak 100 observasi yang terdiri dari 6 variabel, dimana X1 dan X3 berkorelasi

dengan X6.• Tabel 2. Hasil Imputasi Missing Data pada Data Simulasi 2 dari 5 Kali Percobaan.

Hasil TerbaikR

Rata-rata

MetodeRata-rata

RMSE

Waktu Running

(detik)


Nilai RMSE



0,4194]

3 29,1031 31,5285 2,9265


ANN-GA 25,3905 30,7505 1.215,1973



700


550

600

650

Nilai Aktual

450

500

550KNNI

KNNI-GA Seleksi

KNNI-GA Bobot

ANN-GA

350

400



Data Simulasi 3

• Simulasi ketiga dilakukan dengan membangkitkan data berdistribusi normal multivariatb k b i t di i d i 6 i b l di X X X X d Xsebanyak 100 observasi yang terdiri dari 6 variabel, dimana X1, X2, X3, X4, dan X5

berkorelasi dengan X6. Terdapat multikolinearitas antara X2, X3, X4, dan X5.• Tabel 3. Hasil Imputasi Missing Data pada Data Simulasi 3 dari 5 Kali Percobaan.

Hasil TerbaikR

Rata-rata

MetodeRata-rata

RMSE

Waktu Running

(detik)


Nilai RMSE



0,5161]

7 8,0263 8,9048 2,7230


ANN-GA 10,7611 11,8223 1.890,6804



650


550

600

Nilai Aktual

450

500KNNI

KNNI-GA Seleksi

KNNI-GA Bobot

ANN-GA

350

400



Data Survei IBS

• Variabel yang digunakan adalah nilai pendapatan (X1), nilai upah/gaji pekerja (X2), nilaib h b k d l (X ) il i t li t ik di k (X ) il ibahan bakar dan pelumas (X3), nilai tenaga listrik yang digunakan (X4), nilaipengeluaran lain (X5), dan nilai bahan baku dan penolong (X6).

• Matriks korelasi:



S i SData Survei IBS

• Tabel 4. Hasil Imputasi Missing Data pada Data Survei IBS dari 5 Kali Percobaan.

Metode

Hasil TerbaikRata-rata

RMSE

Rata-rata Waktu

Running(detik)


Nilai RMSE(detik)

KNNI [1 1 1 0 1] 7 415,4998 415,4998 5,3252KNNI-GA Seleksi Variabel [1 1 1 0 1] 7 415,4998 415,4998 5,3557

KNNI-GA Bobot Variabel [0,0968 0,2581 0 7097 0 6129

2 303,3308 314,7428 10,19210,7097 0,6129

0,7742]

ANN-GA 330,3085 357,2930 1.272,3939



Gambar 5 Grafik Nilai Imputasi dan Nilai Aktual pada Data Survei IBS

7000

Gambar 5. Grafik Nilai Imputasi dan Nilai Aktual pada Data Survei IBS

4000

5000

6000

Nilai Aktual

2000

3000

4KNNI

KNNI-GA Seleksi

KNNI-GA Bobot

ANN-GA

0

1000


-1000

Kesimpulan dan Saran (1)25

K i lKesimpulan

• Imputasi missing data dengan metode KNNI memiliki rata-rata waktu running program yang cepat. yang cepat.

• Imputasi missing data dengan metode hibrida KNNI-GA untuk pembobotan variabelmenghasilkan nilai RMSE yang lebih kecil daripada metode hibrida KNNI-GA untukseleksi variabel, akan tetapi dilihat dari rata-rata waktu running program, metodehibrida KNNI-GA untuk seleksi variabel lebih efisien karena memiliki waktu running

l bih tprogram yang lebih cepat.• Metode KNNI dan hibrida KNNI-GA untuk seleksi variabel menghasilkan nilai RMSE

yang sama. • Metode hibrida KNNI-GA untuk pembobotan variabel dapat digunakan sebagai alternatif

metode hibrida ANN-GA karena secara umum dapat menghasilkan nilai imputasimetode hibrida ANN-GA, karena secara umum dapat menghasilkan nilai imputasidengan nilai RMSE yang kecil dan waktu running program yang jauh lebih cepat.

• Imputasi missing data dengan KNNI dengan menggunakan nilai bobot variabel yang diperoleh dari metode hibrida KNNI-GA dapat menghasilkan nilai RMSE yang lebih kecildaripada imputasi KNNI dengan menggunakan bobot koefisien korelasi variabel.


Kesimpulan dan Saran (1)26

SSaran

• Pada metode KNNI menggunakan fungsi jarak selain euclidian, misalnya jarakmahalanobismahalanobis.

• Penerapan pada persentase missing data yang lain dan penggunaan variabel yang lebihbanyak untuk melihat kinerja dari masing-masing metode.

• Pada Algoritma Genetika perlu dikembangkan metode seleksi dan crossover yang lain sehingga diharapkan dapat mencapai konvergen dengan lebih baik.gg p p p g g


Daftar Pustaka27

Analoui, M. dan Amiri, M.F., 2006, "Feature Reduction of Nearest Neigbor Classifier using Genetic Algorithm", World Academy of Science, Engineering and Technology 17, 36-39.

Batista G. dan Monard M.C., 2003, A Study of K-Nearest Neighbour as an Imputation Method, Working Paper, University Sao Paulo, Brazil.

Chaimongkol, W. dan Suwattee, P., 2004, Weighted Nearest Neighbor and Regression Imputation, Working Paper, National Institute of Development Administration.

Engelbrecht, A.P., (2002), Computational Intelligence: An Introduction, John Wiley & Sons, Inc, England.

G M d Ch R ( ) G ti Al ith d O ti i ti E i i J h Wil & S I J Gen, M. dan Cheng, R., (1999), Genetic Algorithm and Optimization Engineering, John Wiley & Sons, Inc, Japan.

Jerez, J.M., dan Molina, I., (2010), "Missing Data Imputation Using Statistical And Machine Learning Methods In A Real Breast Cancer Problem", Artificial Intelligence in Medicine 50, 105-115.

Li, Y., Xie, M., dan Goh, T., (2009), "A Study of Project Selection and Feature Weighting for Analogy Based Software Cost Estimation", The Journal of System and Software 82, 241-252.

Little R J dan Rubin D B (1987) Statistical Analysis with Missing Data John Wiley & Sons Inc New York Little, R.J., dan Rubin, D.B., (1987), Statistical Analysis with Missing Data, John Wiley & Sons, Inc, New York.

Meesad, P. dan Hengpraprohm, K., (2008), "Combination of KNN-Based Feature Selection and KNN Based Missing Value Imputation of Microarray Data", International Conference on Innovative Computing Information and Control.

Saekhoo, J. (2008). Simple Linear Regression Analysis for Incomplete Longitudinal Data, Disertasi Ph.D, National Institute of Development Administration.

Siedlecki,W. dan Sklansky, J., (1989), "A Note on Genetic Algorithms for Large-Scale Feature Selection", Pattern Recognition , y, J , ( 989), g g , gLetters 10, 335-347.

Wasito, I. dan Mirkin, B., (2005), "Nearest Neighbor Approach in the Least Square Data Imputation Algorithms", Information Sciences 169, 1-25.

Zarnoch, S.J., Cordell, H.K., Bets, C., dan Bergstrom, J.C., (2010), Multiple Imputation: An Application to Income Nonresponsein the National Survey on Recreation and the Environment, Research Paper, United States Department of Agriculture.


Terima Kasih28


imputasi missing data dengan k-nearest neighbor...

Documents