PE DAHULUA
Latar Belakang Pemilihan Kepala Daerah dan Wakil Kepala Daerah, atau seringkali disebut Pilkada, adalah pemilihan umum untuk memilih Kepala Daerah dan Wakil Kepala Daerah secara langsung di Indonesia oleh penduduk daerah setempat yang memenuhi syarat. Pilkada dilaksanakan setiap lima tahun sekali. Pilkada Kota Bogor dilaksanakan pada tanggal 25 Oktober 2008. Hasil Pilkada Kota Bogor merupakan akumulasi dari hasil perhitungan suara di setiap Tempat Pemungutan Suara (TPS). Data hasil pemilihan tersebut dikumpulkan oleh Komisi Pemilihan Umum Daerah Kota Bogor. Salah satu bentuk analisis yang dapat diterapkan pada data hasil Pilkada adalah deteksi pencilan (outlier detection). Pada umumnya, TPS yang jaraknya berdekatan memiliki hasil pemenang pemungutan suara yang relatif sama. Data hasil Pilkada Kota Bogor hanya memiliki atribut non-spasial, sehingga hanya akan terdeteksi global outlier. Jika data tersebut digabung dengan data spasial Kota Bogor, spatial outlier dapat terdeteksi. Spatial outlier adalah objek yang tereferensi secara spasial di mana nilai atribut non-spasial secara signifikan berbeda dari objek yang tereferensi secara spasial di sekitarnya. Proses analisis data yang besar dapat menggunakan teknik data mining. Secara khusus, jika data yang dianalisis merupakan data spasial maka teknik tersebut disebut spatial data mining. Salah satu teknik dalam spatial data mining adalah spatial outlier detection. Dalam teknik spatial outlier detection, terdapat beberapa algoritme. Namun beberapa di antaranya memiliki kelemahan yaitu masih mengandung kesalahan dalam mendeteksi spatial outlier yang sebenarnya. Penggunaan algoritme Iterative Ratio dan Iterative Z-value dianggap dapat mengurangi kesalahan deteksi. Penelitian ini akan mengimplementasikan kedua algoritme tersebut untuk mendeteksi spatial outlier pada data hasil Pilkada Kota Bogor. Tujuan Penelitian ini bertujuan untuk mendeteksi data TPS di Kecamatan Bogor Tengah Kota Bogor yang menjadi spatial outlier dengan menggunakan algoritme Iterative Ratio dan Iterative Z-value.
Ruang Lingkup Penelitian ini menggunakan data sekunder hasil Pilkada Kota Bogor tahun 2008 yang berasal dari Komisi Pemilihan Umum Daerah (KPUD) Bogor daerah Kecamatan Bogor Tengah. Manfaat Penelitian ini diharapkan dapat mengungkap data pada TPS mana yang menjadi spatial outlier. Dengan demikian, hasil tersebut dapat dijadikan bahan untuk analisis lanjutan agar dapat memahami proses politik yang terjadi.
TI JAUA PUSTAKA Praproses Data Data yang tersimpan dalam suatu basis data seringkali tidak sempurna, mengandung noise (data error), atau tidak konsisten. Oleh karena itu, perlu dilakukan praproses data agar dapat meningkatkan kualitas data yang pada akhirnya akan meningkatkan akurasi dan efisiensi data tersebut. Kualitas data akan menentukan kualitas keputusan (Han & Kamber 2006). Tahap dari praproses dapat dilihat pada Gambar 1 yang terdiri atas :
Data cleaning
Data integration
Data transformation Data reduction
Gambar 1 Bentuk praproses data (Han & Kamber 2006). 1 Pembersihan data Permasalahan data membersihkannya : •
kotor
dan
cara
Nilai yang kosong Untuk mengatasi nilai yang kosong (missing values) dalam data dapat dilakukan dengan penghapusan tuple, mengisi dengan konstanta global
1
seperti ‘tidak tahu’ atau ‘‘∞’, menggunakan nilai rata rata-rata dari nilai atribut yang kosong, mengisi meng dengan nilai rata-rata rata dari kelas yang sama, atau mengisi isi dengan nilai yang mungkin dengan menggunakan metode regresi, induksi pohon keputusan (decision tree), dan lain sebagainya. •
Nilai mengandung noise Data dengan nilai yang mengandung noise dapat diganti dengan nilai hasil perhitungan dengan metode binning, metode regresi, i, atau dengan cara clustering.
•
Data tidak konsisten Data tidak konsisten diperbaiki dengan menggunakan referensi eksternal.
2 Integrasi data Integrasi data adalah proses penggabungan data dari berbagai sumber penyimpanan data. 3 Transformasi data Transformasi data akan mengubah data ke dalam bentuk yang sesuai untuk proses data mining. Transformasi masi data mencakup smoothing,, agregasi, generalisasi, normalisasi, atau konstruksi atribut. 4 Reduksi data Teknik reduksi data seperti agregasi kubus data,, reduksi dimensi, kompresi data, atau discretization dapat digunakan untuk mereduksi representasi data dengan meminimalkan informasi yang hilang. Data Mining Data mining adalah sebuah proses pencarian secara otomatis informasi yang berguna dalam tempat penyimpanan nyimpanan data berukuran besar (Tan et al. 2005). Istilah lain yang sering digunakan diantaranya knowledge discovery (mining) in databases (KDD), knowledge extraction extraction, data/pattern analysis, data archeology, data dredging, information harvesting, dan business intelligence. Teknik data mining digunakan untuk memeriksa basis data berukuran besar sebagai cara untuk menemukan pola yang baru dan berguna. Data mining adalah bagian integral dari KDD. Keseluruhan proses KDD untuk konversi raw data ke dalam info informasi yang berguna ditunjukkan dalam Gambar 2.
Gambar 2 Proses knowledge discovery in databases. Spatial Data Mining Spatial data mining mengacu pada ekstraksi pengetahuan, hubungan spasial, atau pola menarik lainnya yang tidak secara eksplisit tersimpan pada basis data spasial (Shekhar et al. 2003). Tantangan terbesar pada spatial data mining adalah proses eksplorasi. Mengekstraksi pola yang menarik dan berguna dari kumpulan data spasial lebih sulit dibandingkan dengan mengekstraksi pola yang berhubungan dengan data kategorik. Hal ini disebabkan oleh kompleksitas dari tipe data spasial, hubungan spasial, dan otokorelasi spasial. Spatial Outlier Detection Outlier secara informal didefinisikan sebagai suatu pengamatan pada kumpulan data di mana muncul ketidakkonsistenan suatu data dengan data yang lainnya pada kumpulan data yang sama, atau yang terdeviasi terlalu banyak dari pengamatan yang lain dengan mekanisme yang berbeda (Tan et al.. 2005 2005). Secara informal, spatial outlier merupakan objek yang tereferensi secara spasial di mana atribut nonnon spasialnya relatif sangat berbeda dengan lingkungannya (Shekhar et al. 2003). Global outlier merupakan an objek yang nilainya berbeda secara signifikan dengan seluruh nilai yang ada. Ilustrasi dari global outlier dan spatial outlier terlihat pada Gambar 3. Pendeteksian Pe spatial outlier sangat berguna dalam aplikasi sistem informasi geografis dan basis data spasial.
Gambar 3 Global outlier (G) dan spatial outlier (S) (Lu et al. 2003).
2
Sekumpulan data spasial dapat dimodelkan sebagai kumpulan objek yang tereferensi secara spasial. Objek spasial memiliki dua kategori dimensi yang berbeda sesuai dengan atribut mana yang akan diukur. Kategori tersebut terdiri atas : 1
Atribut spasial dari objek yang tereferensi secara spasial seperti lokasi, bentuk, dan geometrik atau topologi lainnya.
2
Atribut non-spasial dari objek yang tereferensi secara spasial seperti trafficsensor-identifiers, umur, dan pemilik.
K-earest eighbor earest eighbor merupakan teknik klasifikasi yang berdasarkan kedekatan objek. Kedekatan disini didefinisikan dengan ukuran jarak misalnya Euclidean. Jarak Euclidean antar dua titik, misal Titik1=(x1, y1) dan Titik2=(x2, y2) adalah (Han & Kamber 2006) : DistTitik1 ,Titik2 =(x1 -x2 )2 +(y1 -y2 )2 K- earest eighbor (k-NN) akan mengklasifikasikan data terhadap k labeled data terdekat. Algoritme untuk k- earest eighbor adalah : 1
Menentukan nilai k.
2
Menghitung jarak antar setiap titik.
3
Mengelompokkan dengan k titik terdekat untuk setiap titik.
Algoritme Iterative Ratio Tantangan yang perlu diperhatikan dalam pendeteksian spatial outlier adalah meminimalkan kesalahan deteksi. Kesalahan terjadi jika spatial outlier yang sebenarnya akan diabaikan, sedangkan spatial outlier yang bukan sebenarnya akan teridentifikasi atau sebaliknya. Salah satu contoh algoritme yang berpotensi melakukan kesalahan deteksi adalah Moran Scatterplot. Moran Scatterplot merupakan plot antara nilai atribut yang telah dinormalisasi (sumbu x) dengan nilai rataan tetangga atribut yang telah dinormalisasi (sumbu y) (Luc 1995). Moran Scatterplot memiliki empat kuadran. Jika objek berada pada kuadran low outlier dan high outlier, maka objek tersebut merupakan spatial outlier. Low outlier adalah objek yang nilainya rendah diantara objek yang nilainya tinggi. High outlier adalah objek yang nilainya tinggi diantara objek yang nilainya rendah. Jika objek berada pada kuadran cluster, maka objek tersebut bukan spatial outlier karena nilai dari
objek tersebut tidak berbeda dengan objek tetangganya. Hal ini ditunjukkan oleh Gambar 4.
Gambar 4 Struktur Moran Scatterplot. Kesalahan deteksi spatial outlier yang dilakukan Moran Scatterplot diperlihatkan pada Gambar 5 dan 6. Pada Gambar 5(a) dan Gambar 6(a), titik dibagi menjadi tiga kelas yaitu kelas sedikit, sedang, dan banyak. Ketiga kelas ini direpresentasikan dengan warna berbeda. Warna hijau merepresentasikan kelas sedikit, warna kuning merepresentasikan kelas sedang, dan warna merah merepresentasikan kelas banyak. Titik dengan ID_OBJ=81 merupakan spatial outlier. Pada Gambar 5(a) terlihat bahwa kelas titik tersebut berbeda dengan kelas titik di sekitarnya di mana kelas titik di sekitarnya adalah kelas sedikit dan sedang. Dengan menggunakan Morran Scatterplot, titik tersebut tidak terdeteksi sebagai spatial outlier karena titik berada pada kuadran cluster. Spatial Outlier dengan ID_OBJ=81
(a)
Spatial outlier
(b) Moran Scatterplot Gambar 5 Kesalahan deteksi spatial outlier pada Moran Scatterplot.
3
Moran Scatterplot juga melakukan kesalahan dengan mendeteksi suatu titik sebagai spatial outlier, tetapi titik tersebut bukan merupakan spatial outlier. Pada Gambar 6(a), titik dengan ID_OBJ=136 bukan spatial outlier karena tetangga dari titik tersebut kelasnya sama yaitu kelas sedikit (warna hijau). Dengan Moran Scatterplot, titik tersebut dianggap sebagai spatial outlier karena berada pada kuadran high outlier.
1
Untuk setiap titik spasial xi, dihitung k nearest neighbors set k(xi) dan fungsi neighborhood g(xi) 1 g(xi ) k xϵ
f(x)
k (xi )
Dihitung juga fungsi hi = h(xi) = f(xi)/g(xi). Gambar 7 memperlihatkan ilustrasi dari perhitungan set k(xi), g(xi), dan h(xi).
ID_OBJ=136
W Z-Score Attribute of values
(a) Spatial outlier Low outlier
Gambar 7 Ilustrasi perhitungan set g(xi), dan h(xi).
cluster
2
ID_OBJ=136 3 High outlier
cluster
Z-Score Attribute of values
(b) Morran Scatterplot
4
Gambar 6 Kesalahan deteksi spatial outlier pada Moran Scatterplot. Beberapa variabel yang digunakan dalam algoritme Iterative Ratio dan Iterative Z-value adalah: •
xi adalah titik spasial.
•
k(xi) adalah k nearest neighbors terhadap titik x.
•
f(x) adalah fungsi yang merepresentasikan nilai atribut dari xi.
•
•
g(x) adalah fungsi yang memetakan X (data set spasial) ke R (bilangan real). Fungsi ini diimplementasikan dengan fungsi rataan. h(x) adalah fungsi yang digunakan untuk membandingkan g dan f.
Algoritme Iterative Ratio adalah sebagai berikut (Lu et al. 2003):
k(xi),
Misal hq menunjukkan nilai maksimum dari h1, h2,…, hn Dengan batas θ yang telah diketahui, jika hq ≥ θ, maka xq ditentukan sebagai spatial outlier (S-outlier). Nilai f(xq) diperbaharui sebagai g(xq). Untuk setiap titik spasial xi di mana k(xi) mengandung xq, nilai g(xi) dan hi diperbaharui. Langkah 2, 3, dan 4 diulangi sampai nilai hi tidak melebihi batas θ atau sampai total jumlah S-outlier sebesar m.
Algoritme Iterative Z-value Algoritme Iterative Z-value adalah sebagai berikut (Lu et al. 2003): 1
Untuk setiap titik spasial xi, dihitung k nearest neighbors set fungsi k(xi), neighborhood g(xi). 1 g(xi ) k xϵ
k (xi )
f(x)
Dihitung juga fungsi hi=h(xi) = f(xi) – g(xi). 2
Misal µ dan σ menunjukkan rataan sampel dan standar deviasi sampel dari suatu data set {h1, h2,….,hn}. Selanjutnya, dihitung nilai absolut yi untuk i = 1, 2,….,n. hi - µ , σ Misal yq adalah nilai maksimum dari y1,y2,…,yn. Dengan batas θ yang telah yi =
4
diketahui, jika yq ≥ θ, maka xq ditentukan S-outlier. 3
Nilai f(xq) diperbaharui sebagai g(xq). Untuk setiap titik spasial xi di mana k(xi) mengandung xq, nilai g(xi) dan hi diperbaharui.
4
Nilai µ dan σ dihitung kembali pada data set {h1, h2, …, hn}. Untuk i = 1,2,…,n, nilai diperbaharui.
5
Langkah 2, 3, dan 4 diulangi sampai nilai yi tidak melebihi batas θ atau sampai total jumlah S-outlier sebesar m.
Penggabungan Data Proses spatial data mining memerlukan data spasial dan non-spasial. Oleh karena itu, untuk proses selanjutnya data spasial dan non-spasial digabungkan.
Pada algoritme Iterative Ratio dan Iterative Z-value, jika S-outlier terdeteksi, maka koreksi akan dilakukan dengan segera. Koreksi yang dilakukan adalah dengan mengganti nilai atribut S-outlier dengan nilai rataan atribut di sekitarnya. Dengan adanya koreksi ini dapat mencegah titik normal yang berada dekat dengan spatial outlier terdeteksi sebagai spatial outlier.
METODE PE ELITIA Penelitian ini dilakukan dalam beberapa tahap seperti yang digambarkan pada Gambar 8 yaitu pengadaan data, praproses data, penggabungan data, membentuk k-NN list, analisis spatial outlier dengan algoritme Iterative Ratio dan Iterative Z-value, dan visualisasi. Pengadaan Data Data hasil Pilkada Kota Bogor pada tahun 2008 diperoleh dari KPUD Kota Bogor. Karena penelitian ini difokuskan pada kecamatan Bogor Tengah, maka pengadaan data dilanjutkan dengan meminta data pada Panitia Pemungutan Suara (PPS) Bogor Tengah. Data tersebut merupakan data yang memiliki atribut nonspasial. Data yang juga diperlukan adalah data spasial Kota Bogor. Praproses Data Praproses dilakukan untuk data hasil Pilkada dan peta. Beberapa tahapan yang dilakukan dalam tahap praproses, di antaranya: •
Pembersihan data
•
Transformasi data
Praproses data dilakukan untuk meningkatkan kualitas data yang dianalisis. Dengan peningkatan kualitas data maka kualitas hasil keputusan juga akan lebih baik.
Gambar 8 Tahap penelitian. Pendugaan Spatial Outlier Pada langkah ini, akan diduga data pada TPS mana yang menjadi spatial outlier. Pendugaan dilakukan dengan melihat pola sebaran dari kelas persentase. Ada dua metode yang digunakan yaitu Equal Interval dan atural Breaks. Equal interval merupakan proses pembagian nilai menjadi beberapa kelas dengan interval yang sama untuk setiap kelas. atural Breaks merupakan proses pembagian nilai ke dalam beberapa kelas dengan menggunakan algoritme Jenk’s Optimization. Algoritme Jenk’s Optimization adalah sebagai berikut (Slocum 2004) :
5
