ALGORITMA GENETIKA UNTUK PENDETEKSIAN PENCILAN PADA ANALISIS REGRESI LINIER
AMRI LUTHFI NAJIH
DEPARTEMEN STATISTIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2014
PERNYATAAN MENGENAI SKRIPSI DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa skripsi berjudul Algoritma Genetika untuk Pendeteksian Pencilan pada Analisis Regresi Linier adalah benar karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir skripsi ini. Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut Pertanian Bogor.
Bogor, Agustus 2014
Amri Luthfi Najih NIM G14100041
ABSTRAK AMRI LUTHFI NAJIH. Algoritma Genetika untuk Pendeteksian Pencilan pada Analisis Regresi Linier. Dibimbing oleh BAGUS SARTONO dan ITASIA DINA SULVIANTI. Masalah yang sering dihadapi ketika melakukan analisis regresi linier adalah keberadaan data pencilan. Pencilan merupakan suatu keganjilan. Seringkali data pencilan memiliki nilai yang berbeda, lain dari biasanya dan tidak mencerminkan karakteristik data secara umum. Pencilan dapat mempengaruhi dugaan model. Dugaan model yang dihasilkan tidak dapat menggambarkan hubungan antara variabel secara umum. Sehingga, analisis atau interpretasi yang dihasilkan menjadi salah. Oleh karena itu perlu dilakukan pendeteksian pencilan sebelum melakukan analisis regresi. Kriteria Informasi dapat digunakan untuk mendeteksi pencilan. Kriteria Informasi dihitung dengan menyisihkan amatan yang diduga sebagai pencilan. Nilai Kriteria Informasi minimum menunjukkan bahwa amatan yang disisihkan merupakan pencilan. Namun akan banyak kombinasi amatan yang diduga sebagai pencilan yang mungkin ditemukan dalam satu gugus data. Hal tersebut akan menyita waktu ketika dilakukan secara manual. Algoritma genetika dapat digunakan untuk menghitung nilai Kriteria Informasi, sehingga dapat digunakan untuk menentukan nilai minimumnya. Algoritma genetika dapat melakukan pendeteksian seluruh amatan yang berpotensi sebagai pencilan secara serempak. Namun ada beberapa kekurangan dalam program ini, yaitu masalah kecepatan program. Semakin banyak amatan semakin banyak juga waktu yang diperlukan. Banyaknya peubah dalam data tidak mempengaruhi kemampuan program untuk mencapai nilai kriteria informasi minimum. Kata kunci: Algoritma Genetika , Kriteria Informasi, Pencilan, Regresi linier.
ABSTRACT AMRI LUTFI NAJIH. Detecting Outliers in Regression Analysis Using Genetic Algorithm. Supervised by BAGUS SARTONO and ITASIA DINA SULVIANTI. A common problem in linear regression analysis is the existence of outliers. Outlier is an oddity. Frequently the outliers have different values, different from the usual and do not reflect the characteristics of the data in general. Outliers can be affect to models estimation. models estimation can not describe the relationship between variables in general. So that, analysis or interpretation of the result will be incorrect. Therefore it is necessary for the detection of outliers before the analysis. Information criterion can be used to detect outliers. Information criteria calculated by eliminate the observations suspected as outliers. Minimum Information Criterion value indicates an observations eliminated as outlier. But it would be a lot of combinations of observations suspected as outliers that might be found in a set of data. Genetic algorithms can be used to calculate the value of information criteria, so it can be used to determine the minimum value. Genetic algorithm can used to detection of all possible outliers simultaneously. However there are some disadvantages in this
program, that is the problem of program speed. The more observations the more time is required. The number of variables in the data does not affect the program's ability to achieve the minimum information criterion.
Keywords: Genetic Algorithms, Information Criteria, Outlier, linear regression.
ALGORITMA GENETIKA UNTUK PENDETEKSIAN PENCILAN PADA ANALISIS REGRESI LINIER
AMRI LUTHFI NAJIH
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Statistika pada Departemen Statistika
DEPARTEMEN STATISTIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2014
Judul Skripsi : Algoritma Genetika untuk Pendeteksian Pencilan pada Analisis Regresi Linier Nama : Amri Luthfi Najih NIM : G14100041
Disetujui oleh
Dr Bagus Sartono, MSi Pembimbing I
Dra Itasia Dina Sulvianti, MSi Pembimbing II
Diketahui oleh
Dr Anang Kurnia, MSi Ketua Departemen
Tanggal Lulus:
PRAKATA Puji dan syukur penulis panjatkan kepada Allah subhanahu wa ta’ala atas segala karunia-Nya sehingga karya ilmiah ini berhasil diselesaikan. Karya ilmiah ini berjudul Algoritma Genetika untuk Pendeteksian Pencilan pada Analisis Regresi Linier. Terselesainya penyusunan karya ilmiah ini tidak lepas dari dukungan, motivasi, saran, dan kerjasama dari berbagai pihak. Oleh karena itu, penulis mengucapkan terima kasih kepada: 1. Bapak Suhamto dan Ibuk Anis Husainiah selaku orangtua penulis, yang selalu mendoakan penulis untuk menggapai cita – citanya, serta selalu mendukung dan mengarahkan segala sesuatu yang telah dilakukan oleh penulis. 2. Bapak Dr Bagus Sartono, MSi dan Dra Itasia Dina Sulvianti, MSi selaku pembimbing skripsi yang selalu bersemangat untuk mebimbing dan selalu memberi arahan yang positif kepada penulis dalam menyelesaikan karya ilmiah ini. 3. Teman – teman Statistika 2010 IPB yang selama tiga tahun telah menjadi sahabat penulis di Bogor, dan sealu memberi motivasi pada penulis. 4. Staf dan pegawai tata usaha Departemen Statistika yang telah membantu penulis untung mengurusi segala administrasi perkuliahan. Penulis mengucapkan terimakasih juga pada pihak – pihak yang belum disebutkan diatas, atas bantuannya terhadap penulis untuk menyelesaikan karya ilmiah ini. Semoga karya ilmiah ini bermanfaat.
Bogor, 14 Agustus 2014
Amri Luthfi Najih
DAFTAR ISI DAFTAR TABEL
vi
DAFTAR GAMBAR
vi
DAFTAR LAMPIRAN
vi
PENDAHULUAN
1
Latar Belakang
1
Tujuan
2
TINJAUAN PUSTAKA
2
Algoritma Genetika
2
Kriteria Informasi
3
Regresi linier
4
METODE PENELITIAN
6
Data
6
Prosedur Penelitian
7
HASIL DAN PEMBAHASAN
7
Pendeteksian Pencilan Secara Konvensional
7
Algoritma Genetika untuk Mendeteksi Pencilan
8
SIMPULAN
12
DAFTAR PUSTAKA
13
LAMPIRAN
14
RIWAYAT HIDUP
20
DAFTAR TABEL 1 Hasil deteksi pencilan secara konvensional 2 Hasil deteksi pencilan dengan algoritma genetika
8 11
DAFTAR GAMBAR 1 2 3 4
Ilustrasi populasi Ilustrasi perhitungan penduga ragam Ilustrasi kawin silang Waktu yang dibutuhkan algoritma genetika untuk mendeteksi pencilan. 5 Diagram kotak garis banyaknya generasi untuk mencapai nilai minimum
8 9 10 11 12
DAFTAR LAMPIRAN 1 Sisaan masing – masing data dari setiap tahap pendeteksian 2 Sintaks dalam software R 3 Kemampuan program konvergen ke suatu nilai
14 16 19
PENDAHULUAN Latar Belakang Analisis regresi merupakan alat statistika yang banyak digunakan di berbagai bidang ilmu, tidak hanya matematika dan statistika saja namun juga di bidang–bidang lain seperti biologi, kimia pertanian, teknik, ekonomi, dan lain-lain. Analisis regresi dapat digunakan untuk mengolah data dalam rangka mengetahui hubungan antar dua atau lebih peubah sehingga didapatkan model atau hubungan fungsional antar peubah. Peneliti dapat menggunakan model tersebut untuk berusaha memahami, menerangkan, mengendalikan dan kemudian mendapatkan informasi dari model yang dibangun. Masalah yang sering dihadapi ketika melakukan analisis regresi linier adalah keberadaan data pencilan. Pencilan merupakan suatu keganjilan. Seringkali data pencilan memiliki nilai yang berbeda dengan lainnya. Pencilan dapat mempengaruhi dugaan model, sehingga analisis atau interpretasi yang dihasilkan menjadi salah. Oleh karena itu perlu dilakukan pendeteksian pencilan sebelum melakukan analisis regresi. Pendeteksian pencilan bisa terjadi berulang-ulang dalam satu gugus data. Ketika pencilan pertama dihapus dari gugus data kemudian dilakukan pendeteksian kembali, sering muncul pencilan baru dari gugus data tersebut. Pendeteksian pencilan seperti itu selanjutnya dalam tulisan ini disebut dengan pendeteksian pencilan secara konvensional. Pendeteksian pencilan secara konvensional kurang efisien untuk dilakukan. Perlu satu cara untuk melakukan deteksi pencilan secara serempak, agar lebih efisien dilakukan. Pendeteksian pencilan pada regresi linier telah dilakukan oleh Cook (1977) dengan menggunakan jarak Cook’s. Ukuran jarak Cook’s dirumuskan sebagai kombinasi dari sisaan terbakukan, ragam sisaan, dan ragam nilai dugaan. Seppo (1992) mengusulkan metode pendeteksian pencilan dengan cara membuat suatu besaran yang disebut Kriteria Informasi (KI). Pencilan ditentukan dengan menghitung nilai Kriteria Informasi minimum. Barnet dan Lewis (1994) mendeteksi pencilan dengan cara melihat pengaruh amatan yang tidak konsisten dengan amatan lain pada data dengan banyak peubah. Pena dan Prieto (2001) memperkenalkan metode pendeteksian pencilan yang didasarkan pada proyeksi amatan dari titik- titik data contohnya. Filmoser (2005) melakukan pendeteksian pencilan menggunakan jarak Mahalanobis. Adnan et al. (2003) menguraikan suatu metode untuk mendeteksi pencilan dalam regresi linier yang disebut metode Least Trimmed of Squares (LTS) dan metode Single Lingkage Clustering (SLC). Xu et al. (2005) mengembangkan pendeteksian pencilan dalam model regresi linier dengan metode Likelihood Displacement (LD) dan metode Likelihood Ratio (LR). Diaz et al. (2007) mengusulkan pendeteksian pencilan pada model regresi linier dengan modifikasi jarak Cook’s. Penelitian ini dilakukan untuk mengembangkan metode yang diperkenalkan oleh Seppo, agar menghasilkan metode pendeteksian pencilan yang lebih efisien. Semua kemungkinan amatan yang diduga sebagai pencilan dapat dideteksi dengan cara mencari nilai Kriteria Informasi terkecil (minimum).
2 Pengembangan algoritma genetika dalam pemanfaatannya sebagai alat untuk menghitung solusi optimum dapat diterapkan dalam berbagai kasus pengoptimuman. Pencarian/pendeteksian pencilan dalam suatu analisis regresi dapat dipandang sebagai masalah pengoptimuman, yaitu menyisihkan amatan yang diduga sebagai pencilan sedemikian rupa sehingga nilai KI menjadi minimum. Sehingga, algoritma genetika dapat dimanfaatkan untuk kegiatan pendeteksian pencilan. Tujuan Tujuan dari tulisan ini adalah memperkenalkan alternatif metode pendeteksian pencilan dalam analisis regresi linier.
TINJAUAN PUSTAKA Algoritma Genetika Algoritma genetika adalah salah satu metode yang dapat digunakan untuk menyelesaikan masalah optimasi. Contoh masalah optimasi dalam kehidupan sehari-hari adalah menyusun barang-barang yang ingin dibawa ketika berlibur. Masalahnya adalah kita dapat membawa barang secara maksimal sesuai dengan kebutuhan namun dibatasi dengan kapasitas koper atau tas yang terbatas. Akan banyak sekali kobinasi barang bawaan kita, namun kita akan memilih barang bawaan yang sesuai dengan kebutuhan. Begitu juga dengan algoritma genetika, algoritma genetika bekerja dengan cara memilih solusi paling optimum dari beberapa solusi yang ada. Cara kerja algoritma tersebut mengadopsi dari teori evolusi Darwin, sehingga istilah – istilah yang digunakan berkaitan dengan bidang genetika. Individu yang mampu bertahan sampai akhir proses seleksi adalah individu yang akan hidup, dengan prinsip tersebut algoritma genetika akan menghasilkan solusi optimum yang direpresentasikan oleh individu yang bertahan sampai akhir proses seleksi. Komponen - komponen dasar algoritma genetika adalah gen, individu, populasi, nilai fitness, seleksi, kawin silang, mutasi, kriteria konvergensi. Gen merupakan komponen dasar pembentuk algoritma genetika. Gen dapat menjelaskan solusi dari masalah optimasi. Bentuk dari gen bisa berupa bilangan biner atau bilangan real (Haupt and Haupt 2004). Rangkaian beberapa gen membentuk satu individu. Kumpulan dari individu-individu membentuk populasi. Nilai fitness merupakan nilai dari fungsi objektif, nilai tersebut menggambarkan kebaikan dari satu individu. Tujuan algoritma genetika adalah mencari nilai fitness optimum (bisa maksimum atau minimum). Tulisan ini menggunakan gen dalam bentuk bilangan biner 0 dan 1. Individu merepresentasikan satu gugus data. Banyaknya gen dalam satu individu sama dengan banyaknya amatan dalam satu gugus data. Populasi awal terdiri dari 10 buah individu. Untuk memahami gen, individu dan populasi dapat dilihat pada Gambar 1. Tujuan dari algoritma genetika ini adalah mencari nilai fitness minimum. Semakin kecil nilai fitness, semakin bagus kualitas individu. Individu-
3 individu pada populasi dibentuk secara acak dan berevolusi melalui iterasi berurutan yang disebut generasi. Seleksi dilakukan untuk mengurangi banyaknya individu dalam populasi. Seleksi dilakukan dengan memilih individu dengan nilai fitness minimum. Individu yang terpilih akan dilakukan kawin silang (crossover) untuk mendapatkan individu baru dan menurunkan sifat - sifat baik dari induknya. Dibutuhkan dua individu untuk melakukan kawin silang. Ada beberapa cara yang dapat digunakan untuk memilih dua individu tersebut, antara lain memasangkan individu yang memiliki urutan ganjil dengan individu urutan genap, random pairing, weighted random pairing (berdasarkan ranking atau nilai fitness) atau memasangkan semua individu dengan individu lain kecuali dengan individu itu sendiri. Selanjutnya, ada dua cara yang dapat digunakan untuk melakukan kawin silang, yaitu single point crossover untuk gen berupa bilangan biner dan blending method untuk gen berupa bilangan real. Adanya pengaruh eksternal, memungkinkan terjadinya mutasi atau perubahan gen setelah kawin silang. Mutasi dalam kehidupan nyata sangat jarang terjadi dan tidak sampai mengubah seluruh populasi. Peluang terjadinya mutasi sangat rendah, biasanya ditetapkan nilainya oleh peneliti. Setelah proses mutasi, terbentuklah generasi baru yang didalamnya merupakan individu dengan karakteristik lebih baik. Algoritma genetika merupakan proses iterasi atau berulang-ulang. Untuk menghentikan iterasi bisa dengan cara menentukan banyaknya iterasi atau dengan syarat tertentu. Langkah – langkah algoritma genetika secara umum adalah sebagai berikut (Sivanandam dan Deepa 2008): 1. Mendefinisikan individu, fungsi objektif, peluang mutasi dan kriteria konvergensi yang sesuai dengan permasalahan. 2. Membangkitkan secara acak sebuah populasi sebagai generasi awal yang berisi beberapa individu. 3. Menghitung nilai fitness untuk masing-masing individu. 4. Memilih individu dari populasi yang memiliki nilai fitness terbaik. 5. Melakukan kawin silang. 6. Melakukan mutasi dengan peluang yang telah ditentukan. 7. Menempatkan keturunan baru ke populasi baru. 8. Menghitung nilai fitness dari masing – masing individu pada generasi baru. 9. Mengulangi langkah 3 hingga 8 sampai memperoleh generasi yang memenuhi kriteria konvergensi yang telah ditetapkan.
Kriteria Informasi Prinsip dasar dari kriteria informasi adalah menghitung seberapa besar informasi yang hilang dari satu gugus data yang terbentuk dari proses yang tidak diketahui. Nilai kriteria informasi yang semakin kecil menunjukkan bahwa informasi yang hilang dari satu gugus data juga kecil. Dasar pemikiran Seppo (1992) membentuk kriteria informasi yang dapat mendeteksi pencilan berasal dari
4 statistik tataan dari sisaan. Dari statistik tataan sisaan tersebut dibentuk fungsi kriteria informasi dengan menggunakan metode kemungkinan maksimum. berikut fungsi kriteria informasi ( ) tersebut: (
̂
)
dengan k adalah banyaknya amatan yang diduga sebagai pencilan, n merupakan banyaknya amatan dan ̂ merupakan penduga kemungkinan maksimum ragam dari data yang telah dibuang amatan yang dianggap sebagai pencilan. Kriteria Informasi ini merupakan fungsi objektif yang digunakan dalam algoritma genetika, yang akan dicari nilai fitness minimumnya.
Regresi Linier Analisis regresi linier merupakan alat untuk mengevaluasi hubungan antara satu peubah dengan satu peubah lainnya atau antara satu peubah dengan beberapa peubah lainnya (Draper dan Smith 1992). Model yang digunakan untuk analisis regresi linier adalah sebagai berikut:
dengan Y merupakan peubah tidak bebas, p adalah banyaknya peubah bebas, xp merupakan peubah bebas ke–p, βp merupakan koefisien regresi dari peubah bebas ke–p dan ε adalah galat. Model tersebut merupakan model stokastik, karena nilai Y tidak pasti. Nilai galat yang besar menunjukkan bahwa penyimpangan nilai Y terhadap nilai harapan Y juga besar. Semakin besar nilai galat semakin kecil peluang kejadian dari Y. Amatan dikatakan pencilan ketika peluangnya kurang dari 0.025, sehingga dapat diartikan bahwa nilai pada peubah normal baku lebih dari 1.96. Beberapa literatur melakukan penghampiran nilai 1.96 dengan nilai 2. Model regresi dapat dinotasikan dalam bentuk matriks sebagai berikut:
merupakan vektor peubah tidak bebas berukuran n×1, dengan n adalah banyaknya amatan. X adalah matriks peubah bebas berukuran n×(p+1). adalah vektor parameter regresi berukuran (p+1)×1 dan adalah vektor galat berukuran n×1. Penduga parameter regresi dapat dilakukan dengan metode kuadrat terkecil dengan meminimumkan jumlah kuadrat sisaan sebagai berikut: ∑
(
) (
)
5
(
)
Kriteria informasi membutuhkan penduga kemungkinan maksimum dari ragam sisaan, maka berikut akan dijabarkan untuk mendapatkan penduga tersebut. Rumus umum model regresi adalah sebagai berikut: ( ) (
;
( ); adalah ragam galat )
(
)
Model regresi tersebut memiliki fungsi kepekatan peluang sebagai berikut: ( )
[
√
(
(
)
) ]
Berdasarkan fungsi kepekatan peluang tersebut didapatkan fungsi kemungkinan sebagai berikut: ∏ [ [ ( )
√ √
[
√ ]
[ ]
)
∑( [
((
(
(
∑
) )
(
) ] )) ]
] ∑
Untuk mendapatkan penduga kemungkinan maksimum dari ragam sisaan, maka ( ) harus diturunkan terhadap . ( ) (
) (
)
∑
6 ∑ ∑ ∑ sehingga penduga untuk ragam sisaan adalah sebagai berikut: ̂
∑
METODE PENELITIAN Data Data yang digunakan dalam tulisan ini merupakan data dari berbagai penelitian yang dirangkum oleh Rousseeuw dan Leroy (1987). Penulis menggunakan data – data tersebut karena data tersebut merupakan data real dan sering digunakan untuk mencobakan metode pendeteksian pencilan yang lainnya, kecuali data IV yang merupakan data simulasi. Berikut merupakan gambaran umum tentang data yang digunakan dalam penelitian ini. 1. Data I Gugus data ini merupakan hasil penelitian yang diselenggarakan untuk mengetahui hubungan antara tinggi (x1) dan berat badan pasien penyakit jantung (x2) dengan panjang kateter yang diperlukan (y). kateter merupakan sebuah pipa atau selang yang digunakan pada dunia medis, biasanya dipasangkan pada organ dalam. Sebuah kateter dilewatkan ke dalam vena besar atau arteri pada daerah femoral dan menuju ke jantung. Kateter dapat masuk ke daerah - daerah tertentu untuk memberikan informasi mengenai fungsi jantung. Hal seperti ini biasanya diterapkan pada anak - anak dengan cacat jantung bawaan. Panjang yang tepat dari kateter harus diperkirakan oleh dokter. Data diambil dari 12 pasien penyakit jantung. 2. Data II Gugus data ini merupakan hasil penelitian yang diselenggarakan untuk mengetahui hubungan antara fosfor anorganik (x1) dan fosfor organik (x1) dalam tanah dengan kandungan fosfor pada jagung yang ditanam pada tanah tersebut (y). Data diambil dari 18 petak sawah jagung yang berbeda.
7 3. Data III Gugus data ini merupakan hasil penelitian yang diselenggarakan untuk mengetahui hubungan antara konsentrasi garam yang tertinggal dalam sungai selama dua minggu (x1), periode mingguan dihitung sejak awal musim semi (x2) dan volume sungai (x3) dengan kadar garam dalam sungai (y). Data terdiri dari 28 amatan. 4. Data IV Gugus data ini merupakan data buatan berdasarkan fungsi . Semua amatan mengikuti fungsi tersebut, kecuali amatan ke-13 dan lima amatan terakhir. 5. Data V Gugus data ini merupakan hasil penelitian yang diselenggarakan untuk mengetahui hubungan antara rata – rata pendapatan pegawai di sekolah dasar (x1), persentase ayah berkerah putih (x2), status ekonomi keluarga siswa (x3), rata – rata nilai akreditasi guru (x4) dan pendidikan ibu siswa (x5) dengan nilai akreditasi sekolah dasar (y). Data terdiri dari 20 amatan. Prosedur Penelitian Berikut adalah langkah – langkah penulis dalam pengembangan algoritma genetika. 1. Menentukan fungsi objektif yang tepat untuk digunakan dalam algoritma genetika. 2. Menyusun algoritma yang tepat untuk mendeteksi pencilan. 3. Mengubah algoritma tersebut dalam bentuk bahasa pemrogaman R dengan menggunakan program R 3.0.3. Hasilnya dapat dilihat pada Lampiran 2. 4. Melakukan pendeteksian pencilan pada data I, II, III, IV dan V menggunakan cara konvensional. 5. Mengimplementasikan program algoritma genetika untuk mendeteksi pencilan pada data I, II, III, IV dan V. 6. Membandingkan hasil deteksi secara konvensional dengan hasil pendeteksian menggunakan algoritma genetika.
HASIL DAN PEMBAHASAN Pendeteksian Pencilan Secara Konvensional Tabel 1 merupakan hasil pendeteksian pencilan secara konvensional. Kolom pertama adalah kode gugus data yang dianalisis, sedangkan kolom kedua, ketiga, keempat dan kelima merupakan amatan yang terdeteksi sebagai pencilan pada iterasi pertama, kedua, ketiga, keempat dan kelima. Sebagai ilustrasi, kita lihat baris yang pertama. Data yang dianalisis adalah Data I, pendeteksian pertama didapatkan amatan ke-8 sebagai pencilan. Setelah amatan tersebut dihapus, iterasi kedua menghasilkan amatan ke-11 sebagai pencilan. Tidak ada lagi amatan yang dianggap pencilan pada iterasi berikutnya, sehingga proses deteksi ini menghasilkan dua amatan yaitu amatan ke-8 dan ke-11 yang meupakan pencilan. Data I, II, III hanya memerlukan dua kali iterasi untuk mendeteksi pencilan yang
8 ada. Pendeteksian pencilan secara konvensional bisa jadi tidak efisien untuk dilakukan, seperti yang terlihat pada Data IV, dimana pendeteksiannya memerlukan hingga empat kali iterasi. Data V hanya memerlukan satu kali iterasi untuk mendeteksi seluruh pencilan. Pendeteksian pencilan secara konvensional bisa terjadi berkali-kali karena setiap melakukan pendeteksian model regresi yang didapat berbeda. Model berbeda menghasilkan nilai sisaan yang berbeda, sehingga memungkinkan muncul pencilan lagi. Nilai Sisaan terbakukan masing – masing data dari setiap tahap pendeteksian dapat dilihat pada Lampiran 1. Tabel 1 Hasil deteksi pencilan secara konvensional Date Data I Data II Data III Data IV Data V
Pendeteksian Pencilan ke2 3 4 11 17 5 13 24 16,21,22 -
1 8 10 15, 16, 17 23,25 3, 18
5 -
Algoritma Genetika untuk Mendeteksi Pencilan Algoritma diawali dengan membentukan populasi yang beranggotakan 10 individu. Ilustrasi mengenai bentuk populasi dapat dilihat pada Gambar 1. Setiap individu dibentuk dari n buah gen. Individu memberikan informasi banyaknya amatan yang diduga sebagai pencilan. Gen dalam individu berbentuk bilangan biner (0 1), dengan 0 menunjukkan bahwa amatan tersebut diduga bukan pencilan dan 1 menunjukkan bahwa amatan tersebut diduga sebagai pencilan. Banyaknya gen bernilai satu pada individu menggambarakan banyaknya amatan yang diduga sebagai pencilan pada gugus data. Karena peluang kejadian terjadinya pencilan kecil, maka ditentukan banyaknya gen bernilai 1 dalam setiap individu adalah 20% dari banyaknya amatan. Banyaknya gen bernilai 1 akan dibulatkan ke bilangan bulat terdekat, ketika 20% dari banyaknya amatan tidak bilangan bulat. Misalkan banyaknya amatan adalah 23 amatan, maka banyaknya gen bernilai 1 adalah lima buah gen. Gen bernilai 1 dalam setiap individu diletakkan secara acak. Penentuan letak dan banyaknya gen bernilai 1 hanya saat inisialisasi awal saja, saat proses iterasi bisa berubah-ubah letak dan banyaknya gen bernilai 1.
n
Gambar 1 Ilustrasi populasi
9
Nilai fitness masing-masing individu dihitung menggunakan fungsi objektif berikut: ( ) ̂ dengan k adalah banyaknya amatan yang diduga sebagai pencilan, merupakan banyaknya amatan dan ̂ merupakan penduga kemungkinan maksimum ragam sisaan dari data dengan membuang amatan yang dianggap sebagai pencilan. Gambar 2 merupakan ilustrasi perhitungan ragam sisaan dalam program. Individu dengan bentuk (0 1 0 1 0 0) menggambarkan bahwa amatan ke-2 dan ke-4 diduga sebagai pencilan, sehingga perhitungan ragam sisaan dilakukan tanpa amatan ke-2 dan ke-4. Nilai ragam sisaan digunakan untuk menghitung Kriteria Informasi, dengan n=6 dan k=2.
y 7.70
x1 x2 ε 2 1 -3.093
10.23
3
2
8.24
2
4 -0.619
-
17.62
7
1
18.20
5
3 -1.856
19.23
3
2 5.568
𝑛
𝜎̂
𝑛
𝑘
[(
𝑖
. 9)
[
∑ 𝑒𝑖 (
.6 )
(
.86)
5.57 ]
. 9] . 9
Gambar 2 Ilustrasi perhitungan penduga ragam sisaan Masing-masing individu memiliki nilai KI. Seleksi dilakukan dengan cara mengurutkan individu dengan KI terkecil hingga terbesar, lalu diambil 5 individu dengan KI paling kecil. Langkah selanjutnya adalah kawin silang. Kawin silang dilakukan kepada setiap kombinasi 5 individu (hasil proses seleksi). Metode kawin silang yang digunakan adalah Single Point Crossover. Metode Single Point Crossover dilakukan dengan cara mengacak bilangan bulat positif 1 sampai dengan n-1, dengan n adalah banyaknya amatan pada data atau banyaknya gen dalam satu individu. Hasil dari pengacakan bilangan bulat positif tersebut digunakan sebagai titik kawin silang, ilustrasi kawin silang dapat dilihat pada Gambar 3. Ilustrasi pada Gambar 3 adalah mengawinkan dua individu, dengan enam gen pada masing-masing individu. Titik kawin silang ditentukan dengan mengacak bilangan bulat positif 1 sampai dengan 5. Misal hasil pengacakan adalah 4, maka 4 gen awal pada individu satu digabungkan dengan 2 gen akhir pada individu lainnya dan sebaliknya. Satu kali kawin silang menghasilkan dua individu baru, sehingga hasil dari proses kawin silang sebanyak 2 × . Individu hasil proses kawin silang digabungkan kembali dengan indukannya agar sifat induk yang unggul tidak hilang.
Titik kawin silang
10
1 2 3 4 5
Gambar 3 Ilustrasi kawin silang dengan metode single point crossover Proses selanjutnya setelah kawin silang adalah mutasi. Mutasi dilakukan untuk menghindari terjadinya local optimum. Maksud dari local optimum adalah nilai KI yang didapat belum optimal secara global. Peluang terjadinya mutasi sebesar 0.01. Merubah nilai biner pada gen yang terpilih, jika nilainya 0 akan diganti menjadi 1 dan jika nilainya 1 akan diganti menjadi 0. Individu baru yang terbentuk digunakan kembali dalam proses seleksi, kawin silang dan mutasi. Proses iterasi tersebut berhenti sampai nilai KI individu kesatu dan kesepuluh pada satu populasi memiliki nilai yang sama. Tabel 2 merupakan hasil pendeteksian pencilan menggunakan algoritma genetika. Pendeteksian pencilan menggunakan algoritma genetika memberikan hasil yang sama dengan cara konvensional, kecuali pada Data IV. Perbedaan antara pendeteksian pencilan menggunakan agoritma genetika dan cara konvensional adalah banyaknya pendeteksian yang dilakukan. algoritma genetika hanya satu kali pendeteksian, sedangkan cara konvensional lebih dari satu kali. Sebagai ilustrasi, kita lihat hasil pendeteksian pada Data I dengan algoritma genetika dan cara konvensional. algoritma genetika mampu mendeteksi pencilan amatan 8 dan 11 dengan satu kali iterasi, sedangkan cara konvensional memerlukan dua kali iterasi untuk mendapatkan pencilan amatan 8 dan 11. Begitu juga pada Data II, Data III dan Data IV. Pada Data V pendeteksian pencilan yang dilakukan algoritma genetika dan cara konvensional sama-sama memerlukan satu kali iterasi. Hasil pendeteksian pencilan menggunakan algoritma genetika pada Data IV berbeda dengan hasil pendeteksian dengan cara konvensional. Metode konvensional mendeteksi amatan 16 sebagai pencilan, sedangkan algoritma genetika tidak mendeteksi amatan 16 sebagai pencilan. Data IV merupakan data bangkitan dan sudah ditetapkan pencilannya. Data IV dibangkitkan mengikuti persamaan . Amatan 13, 21, 22, 23, 24 dan 25 dibuat sebagai pencilan dengan cara menambahka nilai y dengan suatu nilai. Amatan 16 tidak dibuat sebagai pencilan, nilainya sesuai dengan persamaan tersebut, yaitu x1=2; x2=3; x3=1; x4=0 dan y=11. Data IV tanpa amatan 13, 16, 21, 22, 23, 24, 25 menghasilkan R2=100% dan KI = -583.21, sedangkan Data IV tanpa amatan 13, 21, 22, 23, 24, 25 menghasilkan R2=100% dan KI = -617.19. Meskipun memiliki nilai R2 yang sama, namun tanpa menghapus amatan ke-16 dapat menghasilkan nilai KI yang lebih kecil, sehingga pada algoritma genetika amatan ke-16 tidak dideteksi sebagai pencilan. Dari kasus pada Data IV terlihat bahwa algoritma genetika lebih sensitif terhadap pencilan.
11
Tabel 2 Hasil deteksi pencilan dengan algoritma genetika Pendeteksian Pencilan keData 1 Data I 8,11 Data II 10,17 Data III 5,15, 16, 17 Data IV 13,21,22,23,24,25 Data V 3, 18 Banyaknya amatan dan peubah dapat mempengaruhi waktu proses pendeteksian menggunakan algoritma genetika. Semakin banyak amatan dan semakin banyak peubah waktu yang diperlukan semakin banyak juga, hal tersebut dapat dilihat pada Gambar 4.
Gambar 4 Waktu yang dibutuhkan algoritma genetika untuk mendeteksi pencilan. Data II memiliki jumlah amatan sebanyak 18 dan data V memiliki amatan sebanyak 20, tapi pada Gambar 4 terlihat perbedaan waktu yang mencolok antara data II dan data V. Data V memiliki jumlah peubah lebih banyak yaitu sebanyak 5 peubah dibandingkan dengan data II yang hanya memiliki 2 peubah. Ternyata banyaknya peubah juga mempengaruhi waktu. Kemampuan program untuk mencapai nilai kriteria informasi paling minimum cukup baik pada data yang dipakai, bisa dilihat pada lampiran 3. Penulis melakukan 10 kali penggunaan program untuk melihat rata – rata pada generasi keberapa program tersebut dapat mencapai nilai kriteria informasi minimum. Hasilnya dapat dilihat pada Gambar 5. Banyaknya generasi yang dimaksud adalah banyaknya iterasi yang dilakukan oleh program. Program bisa menghasilkan generasi/iterasi yang berbeda setiap penggunaan. Sebagai ilustrasi, kita lihat diagram kotak garis Data I. Program dicobakan sebanyak 10 kali pada Data I. Dalam 10 kali percobaan tersebut generasi/iterasi yang terbentuk ada yang berbeda, rata – rata pada generasi/iterasi ke-5 program dapat mencapai nilai KI minimum pada Data I. Rata – rata generasi/iterasi pada Data III paling tinggi
12 dibanding yang lain. Hal tersebut disebabkan banyaknya amatan pada data III lebih banyak dibandingkan dengan data yang lain. Data V memiliki banyaknya parameter yang lebih banyak dibandingkan dengan data II, namun rata – rata generasi/iterasi pada kedua data tersebut hampir sama. Sehingga dapat dikatakan bahwa banyaknya amatan mempengaruhi kemampuan program dalam mencapai nilai kriteria informasi minimum, sedangkan banyaknya peubah dalam data tidak mempengaruhi kemampuan program untuk mencapai nilai kriteria informasi minimum.
Gambar 5 Diagram kotak garis banyaknya generasi untuk mencapai nilai minimum
SIMPULAN Berdasarkan hasil penelitian, dapat disimpulkan bahwa algoritma genetika dapat digunakan untuk menghitung nilai Kriteria Informasi, sehingga dapat digunakan untuk menentukan nilai minimumnya. Algoritma genetika dapat melakukan pendeteksian seluruh amatan yang berpotensi sebagai pencilan secara serempak. Namun ada beberapa kekurangan dalam program ini, yaitu masalah kecepatan program. Semakin banyak amatan semakin banyak juga waktu yang diperlukan. Banyaknya peubah dalam data tidak mempengaruhi kemampuan program untuk mencapai nilai kriteria informasi minimum.
13
DAFTAR PUSTAKA Adnan R, Mohamad MN, and Setan H. 2003. Multiple Outliers Detection Procedures in Linear Regression. Matematika1: 29-45. Barnett V, Lewis T. 1994. Outliers in Statistical Data. New Jersey(US): Jhon Wiley and Sons, Inc. Cook RD, Sanford W. 1947. Residuals and Influence in Regression. London(UK): Champ and Hall. Cook RD. 1977 Detection of Influential Observation in Linear Regression, Technometrics. 42(1): 65-68. Diaz-Garcia JA, Gonzalez-Farias G, and Alvarado-Castro V. 2007. Exact Distributions for Sensitivity Analysis in Linear Regression. Applied Mathematical Sciences. 22(1):1083-1100. Draper NR, Smith H. 1992. Analisis Regresi Terapan. Jakarta(ID): PT. Gramedia Pustaka Utama. Filzmoser P. 2005. Identification of Multivariate Outliers: A Performance Study. Austrian Journal of Statistics. 34(2):127-138. Haupt RL, Haupt SE. 2004. Practical Genetic Algorithms Second Edition. New Jersey(US): Jhon Wiley and Sons, Inc Pena D, Prieto FJ. 2001. Multivariate outlier detection and robust covariance matrix estimation.. Technometrics, 43(3):286–310. Rousseeuw PJ dan Leroy AM. 1987. Robust Regression and Outlier Detection. New York(US): Jhon Wiley and Sons, Inc. Seppo P. 1992. Detection of Outliers in Regression Analysis by Information Criteria. Proceedings of the University of Vaasa , number 146. Schwarz G. 1978. Estimating The Dimention of a model. The annals Stat. 6(1): 461-464. Sivanandam SN, Deepa SN. 2008. Introduction to Genetic Algorithms. New York(US): Springer Xu J, Abraham B, dan Steiner SH. 2005. Outlier Detection Methods in Multivariate Regression Models. [diacu 2013 Desember 25], Tersedia dari: http://www.bisrg.uwaterloo.ca/archive/RR-06-07.pdf.
14 Lampiran 1 Sisaan terbakukan masing – masing data dari setiap tahap pendeteksian
obs 1 2 3 4 5 6 7 8 9 10 11 12
obs 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Data I Deteksi Deteksi 1 2 -0.011 -0.065 -0.613 -0.369 -0.298 -1.207 0.451 0.631 0.873 0.972 -1.577 -1.449 0.058 0.168 -2.294 -0.134 -0.885 0.934 -0.736 1.881 2.131 -0.221 0.011
Deteksi 1 -1.155 -0.509 -0.919 0.280 -0.266 0.196 0.489 -1.016 1.932 -0.152 -1.182 -0.137 1.281 -0.601
Deteksi 2 -1.812 -0.187 -1.396 0.177 2.159 0.386 0.821 -1.757 1.832 -0.485 -1.429 -0.563 1.747 -0.658
Deteksi 3 0.201 -0.845 -1.282 1.294 1.620 -1.482 0.533 -0.813 0.120 -0.089
Data III Deteksi 3 obs -1.797 15 0.373 16 -0.892 17 0.583 18 19 0.863 20 1.192 21 -1.901 22 1.611 23 -0.450 24 -1.071 25 -0.662 26 1.845 27 -0.557 28
obs 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Deteksi 1 -2.009 3.037 -2.047 0.544 0.897 0.169 0.718 0.216 -0.098 -0.645 0.223 0.350 0.504 0.814
Data II Deteksi Deteksi 1 2 0.135 0.276 0.084 -0.369 0.408 0.238 0.033 -0.221 -0.678 -1.423 0.795 1.737 0.204 0.615 0.810 1.453 0.692 1.285 -1.723 -2.260 -0.151 -0.039 -0.289 0.430 -1.289 -1.219 -0.294 0.311 -0.388 0.449 -0.454 -0.952 3.177 -0.841 -0.035
Deteksi 2
Deteksi 3
0.494 -0.092 -0.718 0.620 0.137 0.232 -0.323 -0.017 -0.135 0.214 1.269
0.574 -0.712 -1.178 0.409 -0.031 0.833 0.431 -0.045 -0.473 -0.115 1.321
Deteksi 3 -0.245 -0.340 0.516 -0.392 -1.599 1.200 0.492 1.775 1.627 -0.145 0.328 -1.761 0.216 0.131 -1.307 -0.308
15
obs 1 2 3 4 5 6 7 8 9 10 11 12 13
Data IV Deteksi Deteksi Deteksi Deteksi Deteksi Deteksi Deteksi Deteksi 1 2 3 4 obs 1 2 3 4 0.651 0.057 0.079 -0.625 14 -1.334 -1.545 -0.915 -0.622 0.054 -0.193 -0.205 -0.433 15 -0.630 0.624 -0.383 0.326 0.029 0.079 -0.082 0.092 16 -1.254 -0.113 -1.385 -2.187 -0.035 -0.376 -0.008 0.466 17 -0.038 0.393 0.040 0.567 -0.534 -0.697 -0.585 -0.896 18 -1.892 -1.728 -1.334 -1.031 0.053 0.154 -0.176 -0.405 19 -0.033 -0.020 0.013 0.462 -0.601 -0.540 -0.389 0.104 20 -1.195 -0.807 -0.678 0.125 0.015 -0.554 -0.227 -0.572 21 -0.115 0.751 1.598 2.658 -0.542 -0.425 -0.454 -0.383 22 0.495 1.030 1.932 2.564 -0.589 -0.819 -0.519 -0.429 23 2.668 0.621 0.330 0.199 -0.067 24 0.270 1.644 3.177 -0.009 -0.279 -0.104 -0.053 25 2.621 1.898 3.323
obs 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Data V Deteksi 1 Deteksi 2 0.234 0.326 -0.235 -0.203 -2.045 -0.251 -1.044 0.415 1.065 -0.058 0.424 0.397 -0.456 -0.222 -0.391 0.356 -0.841 0.164 0.535 -1.265 -0.585 1.089 1.648 -0.637 -1.472 -0.177 0.604 -1.061 0.458 0.681 1.382 -0.824 -1.854 2.936 0.640 1.370 0.144 -0.697
16 Lampiran 2 Sintaks dalam software R fitness <- function(d) { d <- d[-1,] x <- as.matrix(cbind(1,d[,2:ncol(data)])) y <- as.matrix(d[,1]) b <- solve(t(x)%*%x)%*%t(x)%*%y sse <- (t(y)%*%y)-(t(b)%*%t(x)%*%y) satu <- matrix(1,nrow(d),1) sst <- (t(y)%*%y)-((t(y)%*%satu%*%t(satu)%*%y)/nrow(d)) r2 <- 1-(sse/sst) n <- nrow(d) BIC <- n*log(sse/(n))-2*log(factorial(n-k))+1*log(n) list("BIC"=BIC) } data <- read.table("D:/document/bahan- bahan/outlier/data/data4.txt", header=TRUE) #Populasi pop <- matrix(0,nrow(data),10) for(i in 1:ncol(pop)) { a <- as.matrix(sample(nrow(data),0.2*nrow(data))) for(j in 1:nrow(a)) { pop[a[j,],i] <-1} } #Fitness popF <- rbind(pop,0) for(i in 1:ncol(pop)) { d <- 0 k <- 0 for(j in 1:(nrow(pop))) { ifelse(pop[j,i]==0,d <- rbind(d,data[j,]),k <- k+1) } fit <- fitness(d=d)$BIC ifelse(abs(fit)==Inf,popF[j+1,i] <- NaN, popF[j+1,i] <- fit) }
17
maxiter<-1000 for(iter in 1:maxiter) { #Seleksi ur <- popF[,order(popF[nrow(popF),],decreasing=F)] x.select <- ur[-nrow(ur),1:5] #Cross_Over x.cross <- x.select for(i in 1:(ncol(x.select)-1)) { for(j in 1:ncol(x.select)) { if(j>i){ a <- sample(nrow(x.select)-1,1) x.cross
18 }
#hitung_fitness_lagi popF <- rbind(pop,0) for(i in 1:ncol(pop)) { d <- 0 k <- 0 for(j in 1:(nrow(pop))) { ifelse(pop[j,i]==0,d <- rbind(d,data[j,]),k <- k+1) } fit <- fitness(d=d)$BIC popF[j+1,i] <- fit } cek1 <- popF[,order(popF[nrow(popF),],decreasing=F)] cek <- cek1[nrow(cek1),1]-cek1[nrow(cek1),10] if (cek==0){break} } { if(sum(x.select[,1])==0) { h <- "Tidak Terdapat Pencilan" } else { h <- c(1:nrow(x.select)) for (i in nrow(x.select):1) { if(x.select[i,1]==0) { h <- h[-i] } } } } c <- ur[nrow(ur),1] list("Pencilan Terdapat Pada Observasi Ke:"=h, "Nilai Kriteria Informasi:"=c, "iterasi"=iter,"pop"=cek1)
19 Lampiran 3 Kemampuan program konvergen ke suatu nilai
Data I
Data II
Data III
Data IV
Data V
20
RIWAYAT HIDUP Nama lengkap penulis Amri Luthfi Najih, dilahirkan di Grobogan pada tanggal 8 Mei 1992 dari Bapak Suhamto dan Ibu Anis Husainiah. Penulis adalah putra pertama dari dua bersaudara. Tahun 2010 penulis lulus dari SMA N 1 Purwodadi dan pada tahun yang sama diterima di Institut Pertanian Bogor. Penulis diterima di IPB melalui jalur USMI (Undangan Seleksi Masuk IPB), diterima tanpa tes. Penulis diterima di departemen Statistika, Fakultas Matematika dan Ilmu Pengetahuan Alam. Penulis aktif diberbagai organisasi dan kepanitiaan selama menempuh pendidikan di IPB. Pada tahun 2011-2012 menjabat sebagai ketua PERMADI Bogor (Persatuan Mahasiswa Purwodadi Bogor). Tahun 20122013 sebagai anggota departemen Survey and research di GSB (Gamma Sigma Beta). Tahun 2012 menjadi anggota divisi dekorasi dan dokumentasi di kepanitiaan Statistika Ria. Tahun 2013 menjadi ketua divisi dekorasi dan dokumentasi di kepantiaan Kompetisi Statistika Junior. Ditahun yang sama penulis melaksanakan Praktik Lapang di BULOG (Badan Urusan Logistik) Divisi Regional Jawa Tengah, ditempatkan pada bagian Analisis Harga Pasar.
