BAB II TINJAUAN PUSTAKA

BAB II TINJAUAN PUSTAKA

2.1

Penambangan Data (Data Mining)

Penambangan data (Data Mining) adalah serangkaian proses untuk menggali nilai tambah dari sekumpulan data berupa pengetahuan yang selama ini tersembunyi dibalik data atau tidak diketahui secara manual (Han, J dan Kamber, M, 2006). Proses untuk menggali nilai tambah dari sekumpulan data sering juga dikenal sebagai penemuan pengetahuan dari pangkalan data (Knowledge Discovery in Databases = KDD) yaitu tahap-tahap yang dilakukan dalam menggali pengetahuan dari sekumpulan data. Tahap-tahap yang dimaksud digambarkan seperti Gambar 2.1.

Universitas Sumatera Utara

Gambar 2.1. Tahap-Tahap Menggali Pengetahuan Dari Pangkalan Data Sumber : Fayyad 1996

Tahap-tahap data mining seperti yang diilustrasikan pada Gambar 2.1 dapat dijelaskan sebagai berikut: 1. Pembersihan Data (Untuk membuang data yg tidak konsisten dan Noise) 2. Integrasi data ( Penggabungan data dari berbagai sumber) 3. Transformasi data (Data diubah menjadi bentuk yang sesuai untuk teknik data mining) 4. Aplikasi Teknik Data Mining 5. Evaluasi pola yang ditemukan (untuk menemukan informasi dan pengetahuan yang menarik) 6. Presentasi pengetahuan (dengan menggunakan teknik visualisasi)

Berdasarkan beberapa pengertian tersebut dapat ditarik kesimpulan bahwa data mining adalah suatu teknik menggali informasi berharga yang terpendam atau tersembunyi pada suatu koleksi data (database) yang sangat besar sehingga ditemukan suatu pola yang menaik yang sebelumnya tidak diketahui. Data mining sendiri berarti usaha untuk mendapatkan sedikit barang berharga dari sejumlah besar material dasar. Karena itu data mining sebenarnya memiliki akar yang panjang dari bidang ilmu seperti kecerdasan buatan (artificial intelligent) machine learning, statistik dan database. Beberapa metode yang sering disebut dalam literatur data mining antara lain clustering, classification, association rules, neural network genetic algorithm dan lain-lain (Pramudiono, 2006).


Data mining sering digunakan untuk membangun model prediksi/inferensi yang bertujuan untuk memprediksi tren masa depan atau prilaku berdasarkan analisis data terstruktur. Dalam konteks ini, prediksi adalah pembangunan dan penggunaan model untuk menilai kelas dari contoh tanpa label, atau untuk menilai jangkauan nilai atau contoh yang cenderung memiliki nilai atribut. Klasifikasi dan regresi adalah dua bagian utama dari masalah prediksi, dimana klasifikasi digunakan untuk memprediksi nilai diskrit atau nominal sedangkan regresi digunakan untuk memprediksi nilai terus-menerus atau nilai yang ditentukan (Larose, 2005). Masalah-masalah yang sesuai untuk diselesaikan dengan teknik data mining dapat dicirikan dengan (Piatetsky dan Shapiro, 2006) : - Memerlukan keputusan yang bersifat knowledge-based - Mempunyai lingkungan yang berubah - Metode yang ada sekarang bersifat sub-optimal - Tersedia data yang bisa diakses, cukup dan relevan - Memberikan keuntungan yang tinggi jika keputusan yang diambil tepat

2.2. Penambangan Data Pada Pendidikan Tinggi Penambangan

data

(Data

Mining)

adalah

satu

proses

untuk

mengungkapkan informasi atau pengetahuan yang tidak nampak dipermukaan tetapi mungkin potensial digunakan dan tersembunyi didalam data (Han J dan Kember, 2006). Aplikasi data mining pada perguruan tinggi adalah area yang baru yang disebut sebagai Educational Data Mining. Romero C dan Ventura S,(2007) telah melakukan survey pada educational data mining dari tahun 1995 – 2005 ,


mereka menyimpulkan bahwa pendidikan adalah wilayah penelitian yang sangat menjanjikan, dan cukup spesifik yang tidak dipresentasikan pada domain riset yang lain. Merceron. A dan Yacep.K (2005), memberikan sebuah studi kasus yang menggunakan data mining untuk mengidentifikasi prilaku mahasiswa yang gagal untuk memperingatkan mahasiswa sebelum ujian akhir. Data mining pada area pendidikan juga digunakan oleh Naeimeh D, et. al (2005), untuk mengidentifikasi dan kemudian meningkatkan proses pendidikan pada system pendidikan tinggi. Waiyamai K (2003), menggunakan data mining untuk membantu pengembangan kurikulum yang baru dan membantu mahasiswa teknik untuk menseleksi bidang utamanya. Sajadin S, et al (2009), menggunakan data mining untuk memonitor pencapaian dan meningkatkan prestasi akademik mahasiswa. Data mining dibagi menjadi beberapa kelompok berdasarkan tugas yang dapat dilakukan, yaitu (Larose, 2005) : 1. Deskripsi (Description) Terkadang penelitian analisis secara sederhana ingin mencoba mencari cara untuk menggambarkan pola dan kecenderungan yang terdapat dalam data. Sebagai contoh, petugas pengumpulan suara mungkin tidak dapat menemukan keterangan atau fakta bahwa siapa yang tidak cukup profesional akan sedikit didukung dalam pemilihan presiden. Deskripsi dari pola dan kecenderungan sering memberikan kemungkinan penjelasan untuk suatu pola atau kecenderungan. 2. Estimasi (Estimation)


Estimasi hampir sama dengan klasifikasi, kecuali variabel target estimasi lebih ke arah numerik daripada ke arah kategori. Model dibangun menggunakan record lengkap yang menyediakan nilai dari variabel target sebagai nilai prediksi. Selanjutnya, pada peninjauan berikutnya estimasi nilai dari variabel target dibuat berdasarkan nilai variabel prediksi. Sebagai contoh, akan dilakukan estimasi tekanan darah sistolik pada pasien rumah sakit berdasarkan umur pasien, jenis kelamin, indeks berat badan, dan level sodium darah. Hubungan antara tekanan darah sistolik dan nilai variabel prediksi dalam proses pembelajaran akan menghasilan model estimasi. Model estimasi yang dihasilkan dapat digunakan untuk kasus baru lainnya 3. Prediksi (Prediction) Prediksi hampir sama dengan klasifikasi dan estimasi, kecuali bahwa dalam prediksi nilai dari hasil akan ada di masa datang. Contoh prediksi dalam bisnis dan penelitian adalah :  Prediksi harga beras dalam tiga bulan yang akan datang  Prediksi persentase kenaikan kecelakaan lalu lintas tahun depan jika batas bawah kecepatan dinaikkan. Beberapa metode dan teknik yang digunakan dalam klasifikasi dan estimasi dapat pula digunakan (untuk keadaan yang tepat) untuk prediksi 4. Klasifikasi (Classification) Dalam klasifikasi, terdapat target variabel kategori. Sebagai contoh, penggolongan pendapatan dapat dipisahkan dalam tiga kategori, yaitu pendapatan tinggi, pendapatan sedang dan pendapatan rendah.


Contoh lain klasifikasi dalam bisnis dan penelitian adalah :  Menentukan apakah suatu transaksi kartu kredit merupakan transaksi yang curang atau bukan  Memperkirakan apakah suatu pengajuan hipotek oleh nasabah merupakan suatu kredit yang baik atau buruk  Mendiagnosis penyakit seorang pasien untuk mendapatkan kategori penyakit apa. 5. Pengklusteran (Clustering) Pengklusteran

merupakan

pengelompokkan

record,

pengamatan

atau

memperhatikan dan membentuk kelas objek-objek yang memiliki kemiripan. Cluster adalah kumpulan record yang memiliki kemiripan satu dengan yang lainnya dan memiliki ketidakmiripan dengan record-record dalam cluster lain. Pengklusteran berbeda dengan klasifikasi yaitu tidak adanya variabel target dalam pengklusteran. Pengklusteran tidak mencoba untuk melakukan klasifikasi, mengestimasi, atau memprediksi nilai dari variabel target. Akan tetapi, algoritma pengklusteran mencoba untuk melakukan pembagian terhadap keseluruhan data menjadi kelompok-kelompok yang memiliki kemiripan (homogen), yang mana kemiripan record dalam satu kelompok akan bernilai maksimal, sedangkan kemiripan dengan record dalam kelompok lain akan bernilai minimal. Contoh pengklusteran dalam bisnis dan penelitian adalah :  Melakukan pengklusteran terhadap ekspresi dari gen, untuk mendapatkan kemiripan perilaku dari gen dalam jumlah besar.


 Mendapatkan kelompok-kelompok konsumen untuk target pemasaran dari suatu produk bagi perusahaan yang tidak memiliki dana pemasaran yang besar.  Untuk tujuan audit akuntansi, yaitu melakukan pemisahan terhadap perilaku finansial dalam keadaan baik atau mencurigakan. 6. Asosiasi (Assosiation) Tugas asosiasi dalam data mining adalah menemukan atribut yang muncul dalam satu waktu. Dalam dunia bisnis lebih umum disebut analisis keranjang belanja Contoh asosiasi dalam bisnis dan penelitian adalah :  Menemukan barang dalam supermarket yang dibeli secara bersamaan dan barang yang tidak pernah dibeli secara bersamaan.  Meneliti jumlah pelanggan dari perusahaan telekomunikasi seluler yang diharapkan untuk memberikan respons posistif terhadap penawaran upgrade layanan yang diberikan.

2.3

Algoritma Clustering (Clustering Algorithm) Clustering (pengelompokkan data) mempertimbangkan sebuah pendekatan

penting untuk mencari kesamaan dalam data dan menempatkan data yang sama ke dalam kelompok-kelompok. Clustering membagi kumpulan data ke dalam beberapa kelompok dimana kesamaan dalam sebuah kelompok adalah lebih besar daripada diantara kelompok-kelompok (Rui Xu dan Donald 2009). Gagasan mengenai pengelompokkan data atau clustering, memiliki sifat yang sederhana


dan dekat dengan cara berpikir manusia, kapanpun kepada kita dipresentasikan jumlah data yang besar, kita biasanya cenderung merangkumkan jumlah data yang besat ini ke dalam sejumlah kecil kelompok-kelompok atau kategori-kategori untuk memfasilitasi analisanya lebih lanjut. Selain dari itu, sebagian besar data yang dikumpulkan dalam banyak masalah terlihat memiliki beberapa sifat yang melekat yang mengalami pengelompokkan-pengelompokkan natural (Hammuda dan Karay, 2003). Algoritma-algoritma clustering digunakan secara ekstensif tidak hanya untuk mengorganisasikan dan mengkategorikan data, akan tetapi juga sangat bermanfaat untuk kompresi data dan konstruksi model. Melalui pencarian kesamaan dalam data, seseorang dapat mempresentasikan data yang sama dengan lebih sedikit simbol misalnya. Juga, jika kita dapat menemukan kelompokkelompok data, kita dapat membangun sebuah model masalah berdasarkan pengelompokkan-pengelompokkan ini (Dubes dan Jain, 1988). Clustering menunjuk pada pengelompokkan record, observasi-observasi, atau kasus-kasus ke dalam kelas-kelas objek yang sama. Cluster adalah sekumpulan record yang adalah sama dengan satu sama lain dan tidak sama dengan record dalam cluster lain. Clustering berbeda dari klasifikasi dimana tidak ada variabel target untuk clustering. Tugas clustering tidak mencoba untuk mengklasifikasikan, mengestimasi atau mempredikasi nilai variabel target (Larose, 2005). Bahkan, algoritma clustering berusaha mensegmentasikan seluruh kumpulan data ke dalam subkelompok-subkelompok atau cluster-cluster


homogen secara relatif. Dimana kesamaan record dalam cluster dimaksimalkan dan kesamaan dengan record diluar cluster ini diminimalkan. Clustering sering dilaksanakan sebagai langkah pendahuluan dalam proses pengumpulan data, dengan cluster-cluster yang dihasilkan digunakan sebagai input lebih lanjut ke dalam sebuah teknik yang berbeda, seperti neural diatas dapat diperoleh sebagai jarak dari pembaharuan formula Lance-Williams (Lance & Williams, 1967). D(C 1 .. C 1 , C k =

a(i) d

(C i , C k )+ a(k) d (C j , C k )+

bd

(C i , C j )+ cld (C i , C k )- d (C j , C k )

Dimana, a,b,c, adalah koefisien-koefisien yang sesuai dengan hubungan tertentu. Formula ini menyatakan sebuah metrik hubungan antara kesatuan dari dua cluster dan cluster ketiga dalam bentuk komponen-komponen yang mendasari. Clustering hirarki berdasarkan metrik hubungan mengalami kompleksitas waktu. Dibawah asumsi-asumsi yang tepat, seperti kondisi daya reduksi (metodemetode grafik memenuhi kondisi ini), metode-metode metrik hubungan memiliki kompleksitas (N2) (Olson 1995). Dalam

linguistik, pencarian informasi dan taksonomi biner aplikasi

clustering dokumen adalah sangat membantu. Metode-metode aljabar linear, yang didasarkan pada dekomposisi nilai singular (Singular Value Decomposition-SVD) digunakan untuk tujuan ini dalam filtering kolaboratif dan pencarian informasi (Berry & Browne, 1999). Aplikasi SVD terhadap clustering divisive hirarkhi dari kumpulan dokumen menghasilkan algroitma PDDP (Prinsipal Direction Divisive Partitioning) (Boley, 1998). Algoritma ini membagi dua data dalam ruang Euclidean dengan sebuah hyperplane yang mengalir melalui centroid data secara


orthogonal pada eigenvector dengan nilai singular yang besar. Pembagian cara k (konstanta) juga memungkinkan jika k nilai singular yang besar. Pembagian cara k juga memungkinkan jika k nilai singular terbesar dipertimbangkan. Divisive hirarki yang membagi dua rata-rata k terbukti (Steinbach et al. 2000) dapat dipilih untuk clustering dokumen network. karena ukuran yang besar dari banyak database yang direpresentasikan saat ini, maka sering sangat membantu untuk menggunakan analisa clustering terlebih dahulu, untuk mengurangi ruang pencarian untuk algoritma-algoritma downstream. Aktivitas clustering pola khusus meliputi langkah-langkah berikut (Dubes dan Jain, 1988) : (I)

Representasi pola (secara opsional termasuk ekstraksi dan/atau seleksi sifat)

(II)

Defenisi ukuran kedekatan pola yang tepat untuk domain data

(III)

Clustering pengelompokkan

(IV)

Penarikan data (jika dibutuhkan) dan

(V)

Pengkajian output (jika dibutuhkan) Representasi pola merujuk pada jumlah kelas, jumlah pola-pola yang ada,

dan jumlah, tipe dan skala fitur yang tersedia untuk algoritma clustering. Beberapa informasi ini dapat tidak bisa dikontrol oleh praktisioner. Seleksi sifat (fitur) adalah proses pengidentifikasian subset fitur original yang paling efektif untuk digunakan dalam clustering. Ekstraksi fitur adalah penggunaan satu atau lebih transformasi dari sifat-sifat input untuk menghasilkan sifat-sifat baru yang lebih baik.


Pertimbangan dataset X yang terdiri dari point-point data (atau secara sinonim, objek-objek, hal-hal kasus-kasus, pola, tuple, transaksi) x i = (x i1 , …, x id ) Є A dalam ruang atribut A, dimana i = 1, N, dan setiap komponen adalah sebuah atribut A kategori numerik atau nominal. Sasaran akhir dari clustering adalah untuk menemukan point-point pada sebuah sistem terbatas dari subset k, cluster. Biasanya subset tidak berpotongan (asumsi ini terkadang dilanggar), dan kesatuan mereka sama dengan dataset penuh dengan pengecualian yang memungkinkan outlier. C i adalah sekelompok point data dalam dataset X, dimana X = C i .. C k .. C outliers , C jl .. C j2 = 0.

2.3.1. Clustering Hirarkhi (Hierarchical Clustering) Clustering hirarkhi membangun sebuah hirarkhi cluster atau dengan kata lain sebuah pohon cluster, yang juga dikenal sebagai dendrogram. Setiap node cluster mengandung cluster anak; cluster-cluster saudara yang membagi point yang ditutupi oleh induk mereka. Metode-metode clustering hirarkhi dikategorikan ke dalam agglomerative (bawah-atas) dan idivisive (atas-bawah) (Jain & Dubes, 1988; Kaufman & Russeeuw, 1990). Clustering agglomerative dimulai dengan cluster satu point (singleton) dan secara berulang mengabungkan dua atau lebih cluster yang paling tepat. Cluster divisive dimulai dengan satu cluster dari semua point data dan secara berulang membagi cluster yang paling tepat. Proses tersebut berlanjut hingga kriteria penghentian (seringkali, jumlah k yang diperlukan dari cluster) dicapai. Kelebihan cluster hirarkhi meliputi :


(I)

Fleksibilitas yang tertanam mengenai level granularitas

(II)

Kemudahan menangani bentuk-bentuk kesamaan atau jarak

(III)

Pada akhirnya, daya pakai pada tipe-tipe atribut apapun

Kelemahan dari clustering hirarkhi berhubungan dengan : (I)

Ketidakjelasan kriteria terminasi

(II)

Terhadap perbaikan hasil clustering, sebagian besar algoritma hirarkhi tidak mengunjungi kembali cluster-clusternya yang telah dikonstruksi.

Untuk clustering hirarkhi, menggabungkan atau memisahkan subset dari point-point dan bukan point-point individual, jarak antara pint-point individu harus digeneralisasikan terhadap jarak antara subset. Ukuran kedekatan yang diperoleh disebut metrik hubungan. Tipe metrik hubungan yang digunakan secara signifikan mempengaruhi algortima hirarkhi, karena merefleksikan konsep tertentu dari kedekatan dan koneksitas. Metrik hubungan antar cluster utama (Murtagh 1985, Olson 1995) termasuk hubungan tunggal, hubungan rata-rata dan hubungan sempurna. Semua metrik hubungan

2.3.2. Clustering Partisional (Partitional Clustering) Dengan mengetahui objek-objek database N, sebuah algoritma clustering partisional membentuk k bagian dari data, dimana setiap cluster mengoptimalkan kriteria clustering, seperti minimasi jumlah jarak kuadrat dari rata-rata dalam setiap cluster.


Salah satu isu dengan algoritma-algoritma tersebut adalah kompleksitas tinggi, karena menyebutkan semua pengelompokkan yang memungkinkan dan berusaha mencari optimum global. Bahkan untuk jumlah objek yang kecil, jumlah partisi adalah besar. Itulah sebabnya mengapa solusi-solusi umum dimulai dengan sebuah partisi awal, biasanya acak, dan berlanjut dengan penyempurnaannya. Praktek yang lebih baik akan berupa pelaksanaan algoritma partisional untuk kumpulan point-point awal yang berbeda (yang dianggap sebagai representative) dan meneliti apakah semua solusi menyebabkan partisi akhir yang sama atau tidak. Algoritma-algoritma clustering partisional berusaha memperbaiki secara local sebuah kriteria tertentu. Pertama, menghitung nilai-nilai kesamaan atau jarak, mengurutkan hasil, dan mengangkat nilai yang mengoptimalkan kriteria. Oleh karena itu, dapat dianggap sebagai algoritma seperti greedy. Sebuah pendekatan terhadap pembagian data adalah mengambil sudut pandang konseptual yang mengidentifikasikan cluster dengan model tertentu yang parameternya tidak diketahui harus ditemukan. Model-model probabilistik menganggap bahwa data berasal dari campuran beberapa populasi yang didistribusi dan prioritasnya ingin ditemukan. Sebuah kelebihan yang jelas dari metode-metode probabilitas adalah daya interpretasi dari cluster-cluster yang dibuat. Dengan memiliki representasi cluster yang tepat juga memungkinkan penghitungan yang tidak ekspensif dari ukuran-ukuran intra-cluster dari kesesuaian yang memberikan fungsi objektif yang tergantung pada sebuah pembagian (partition). Tergantung pada bagaimana representative dibuat,


algoritma-algoritma partitioning optimasi literative dibagi lagi ke dalam metodemetode K-medoids dan K-means.

2.4

Analisis Cluster

Analisis cluster adalah suatu analisis statitik yang bertujuan memisahkan obyek kedalam beberapa kelompok yang mempunyai sifat berbeda antar kelompok yang satu dengan yang lain. Dalam analisis ini tiap-tiap kelompok bersifat homogen antar anggota dalam kelompok atau variasi obyek dalam kelompok yang terbentuk sekecil mungkin (Prayudho, 2008).

Tujuan Analisis Cluster : 1. Untuk mengelompokkan objek-objek (individu-individu) menjadi kelompokkelompok yang mempunyai sifat yang relatif sama (homogen) 2. Untuk membedakan dengan jelas antara satu kelompok (cluster) dengan kelompok lainnya.

Adapun manfaat Analisis Cluster sebagai berikut : 1. Untuk menerapkan dasar-dasar pengelompokkan dengan lebih konsisten 2. Untuk mengembangkan suatu metode generalisasi secara induktif, yaitu pengambilan kesimpulan secara umum dengan berdasarkan fakta-fakta khusus. 3. Menemukan tipologi yang cocok dengan karakter obyek yang diteliti 4. Mendeskripsikan sifat-sifat / karakteristik dari masing-masing kelompok Analisis cluster dilakukan dengan langkah-langkah berikut :


1. Merumuskan permasalahan 2. Memilih ukuran jarak atau kesamaan 3. Memilih prosedur pengklusteran 4. Menetapkan jumlah cluster 5. Interpretasi dan profil dari cluster 6. Menaksir reliabilitas dan validitas

2.5

Metode Kernel

Machine learning untuk penelitian pengolah sinyal sangat dipengaruhi oleh metode yang popular kernel Mercer (Christianini & Taylor, 2000). Point utama dalam metode kernel adalah apa yang disebut “kernel trick”, yang memungkinkan penghitungan dalam beberapa inner product, kemungkinan dengan dimensi yang tidak terbatas, ruang fitur Anggaplah x i dan x j adalah dua point data ruang input. Jika fungsi kernel k(…) memenuhi kondisi Mercer maka : k (x i , x j ) = Φ(x i ).Φ(x j )

(2.1)

Dimana, (x i, x j ) menunjukkan inner product dan Φ(.) melambangkan pemetaan non-linier dari ruang input kepada fitur kernel. Kernel trick memungkinkan pelaksanaan dari algoritma pembelajaran, yang dinyatakan dalam bentuk inner product ruang fitur kernel. Metode-metode Kernel adalah algoritma yang secara implisit melaksanakan, melalui penggantian inner product dengan Kernel Mercer yang tepat, sebuah pemetaan nonlinear dari data input ke ruang fitur berdimensi tinggi (Vapnik,


1995). Metode-metode kernel yang sangat disupervisi telah dikembangkan untuk menyelesaikan masalah-masalah klasifikasi dan regresi. K-means adalah algoritma unsupervised learning yang membagi kumpulan data ke dalam sejumlah cluster yang dipilih dibawah beberapa ukuran-ukuran optimisasi. Sebagai contoh, kita sering ingin meminimalkan jumlah kuadrat dari jarak Euclidean antara sampel dari centroid. Asumsi di belakang ukuran ini adalah keyakinan bahwa ruang data terdiri dari daerah elliptical yang terisolasi. Meskipun demikian, asumsi tersebut tidak selalu ada pada aplikasi spesifik. Untuk menyelesaikan masalah ini, sebuah gagasan meneliti ukuran-ukuran lain, misalnya kesamaan kosinus yang digunakan dalam pencarian informasi. Gagasan lain adalah memetakan data pada ruang baru yang memenuhi persyaratan untuk ukuran optimasi. Dalam hal ini, fungsi kernel merupakan pilihan yang baik.

2.6

Fungsi Kernel

Ada kalanya tidak cukup bagi machine learning untuk bekerja dalam ruang input karena asumsi di belakang mesin tidak menyesuaikan pola riil dari data. Sebagai contoh, SVM (support vector machine) dan Perceptron memerlukan data yang tidak dapat dipisahkan secara linier, sedangkan K-means dengan jarak Euclidean mengharapkan data terdistribusi ke dalam daerah elliptical. Ketika asumsi tersebut tidak digunakan, maka kita dapat menggunakan beberapa jenis transformasi pada data, dengan memetakan mereka pada ruang baru dimana machine learning dapat digunakan. Fungsi Kernel memberikan kepada kita sebuah alat untuk mendefenisikan transformasi.


Anggaplah kita diberikan sekumpulan sampel x 1 , x 2 , x 3 ,…, x N , dimana x i ɛ RD, dan fungsi pemetaan Φ yang memetakan x 1 dari ruang input RD pada ruang baru Q. Fungsi kernel didefenisikan sebagai dot product dalam ruang baru Q : k (x i , x j ) = Φ(x i ).Φ(x j )

(2.2)

Sebuah fakta penting mengenai fungsi kernel adalah bahwa fungsi ini dibangun tanpa mengetahui bentuk kongkrit dari Φ, yaitu transformasi yang didefinisikan secara implicit. Tiga fungsi kernel yang secara umum tercantum di bawah ini : Polynomial k ( x i , x j ) = (x i . x j + 1 )d

(2.3)

Radial k ( x i , x j ) = exp (-r || x i – x j ||2)

(2.4)

Neural k ( x i , x j ) = tanh (ax i . x j + b)

(2.5)

Kelemahan utama dari fungsi Kernel meliputi, pertama beberapa sifat dari ruang baru hilang, misalnya, dimensionalitas dan tingkatan nilainya, sehingga kekurangan bentuk eksplisit untuk Φ. Kedua, penentuan bentuk kernel yang tepat untuk kumpulan data tertentu harus diwujudkan melalui eksperimen-eksperimen. Bahkan, biaya penghitungan dan penyimpanan meningkat menurut margin luas. Prinsip ini menjamin bahwa fungsi kernel dapat selalu diexpresikan sebagi dot product diantara dua input vector dalam beberapa ruang dimensi yang tinggi.


Feature Space

Input Space

k ( x1 , x

2

) = Φ ( x1 ) • Φ ( x

2

)

Gambar 2.2. Proses Pemetaan Kernel

2.7. KERNEL K-MEANS CLUSTERING Clustering adalah salah satu metode yang terkenal dalam data mining, yang digunakan untuk mendapatkan kelompok-kelompok dari data, dimana setiap objek data akan dikelompokkan kedalam satu kelompok berdasarkan kemiripannya, dan yang lainnya akan dikelompokan pada

kelompok yang lain.( Han,J. and

Kamber,M, 2006) K-Means Clustering merupakan teknik dalam klaster data yang sangat terkenal karena kecepatannya dalam mengklasterkan data. Akan tetapi K-Means Clustering memiliki kelemahan didalam memproses data yang berdimensi banyak. Khususnya untuk masukan yang bersifat non-linierly separable. K-Means clustering juga tidak mampu mengrupkan data yang bertipe kategorikal dan juga data campuran (numeric dan kategorikal). Kenyataan didunia nyata data yang tersedia atau yang diperoleh memiliki dimensi yang banyak dan juga bersifat campuran. Untuk mengatasi permasalahan ini, telah banyak diusulkan oleh para peneliti metode-metode yang dapat mengatasi kelemahan ini, salah satu diantaranya adalah Kernel K-Means Clustering (L.S Dhillon, et. al, 2005).


Kernel K-Means Clustering, pada prinsipnya mirip dengan K-Means tradisional, letak perbedaan yang mendasar ada pada perubahan masukannya. Dalam Kernel K-Means data point akan dipetakan pada dimensi baru yang lebih tinggi menggunakan fungsi non-linier sebelum dilakukan proses clustering (Cristianini N, Taylor,J.S.2000) Kemudian Kernel K-Means akan mempartisi data menggunakan linier separator pada space yang baru. Metode kernel pertama dan barangkali yang paling tepat adalah Support Vector Machine (SVM) (Burges, 1998), yang mengoptimalkan kriteria margin maksimum dalam ruang fitur kernel. Algoritma k-means barangkali telah menjadi teknik clustering popular sejak diperkenalkan dalam era 1960an. Ini memaksimalkan jarak Euclidean kuadrat antara pusat-pusat cluster. Meskipun demikian, telah diketahui bahwa ini hanya optimal untuk (yang dapat dipisahkan secara linear) cluster terdistribusi Gaussian. Metode yang berbeda untuk melaksanakan algoritma ini dalam ruang kernel yakni kernel k-means telah diperoleh. Dalam (Zang dan Alexander, 2006) teknik optimasi stochastic dikembangkan dengan menggunakan kernel trick, sedangkan dalam (Girolami, 2002) pemetaan data actual diperkirakan melalui eigenvector dari apa yang disebut matriks kernel. Secara eksperimental, penelitian-penelitian ini memperlihatkan bahwa keterbatasan k-means bisa telah teratasi, dan hasil yang baik dicapai juga untuk kumpulan-kumpulan data yang memiliki batasan-batasan cluster nonlinear. Motivasi untuk keinginan melaksanakan K-means dalam ruang fitur kernel dinyatakan secara longgar sebagai “masalah kemampuan memisahkan nonlinear


yang dapat dielakkan oleh kelas melalui pemetaan data yang diamati pada ruang data berdimensi yang lebih tinggi dengan cara nonlinear sehingga setiap cluster untuk setiap kelas membentang ke dalam bentuk sederhana”. Meskipun demikian, tidak jelas bagaimana kernel K-means berhubungan dengan sebuah operasi pada kumpulan data ruang input. Juga tidak jelas cara menghubungkan lebar kernel dengan sifat-sifat kumpulan data input. Beberapa pemikiran yang disebutkan pada point-point ini telah dibuat dalam (Girolami, 2002; Cristianini & Taylor, 2000). Biasanya perluasan dari k-means ke kernel k-means direalisasi melalui pernyataan jarak dalam bentuk fungsi kernel (Girolami, 2002; Muller et al 2003). Meskipun demikian, implementasi tersebut mengalami masalah seris seperti biaya clustering tinggi karena kalkulasi yang berulang dari nilai-nilai kernel, atau memori yang tidak cukup untuk menyimpan matriks kernel, yang membuatnya tidak dapat sesuai untuk corpora yang besar. Anggaplah kumpulan data memiliki N sampel x 1 , x 2 ,…x N . Algoritma Kmeans bertujuan untuk membagi sampel N ke dalam cluster K, C 1 , C 2 , …, C K , dan kemudian mengembalikan pusat dari setiap cluster, m 1 , m 2 ,…,m k sebagai representative dari kumpulan data. Selanjutnya kumpulan data N-point dipadatkan ke dalam “code book” point K. Algoritma K-means clustering mode batch yang menggunakan jarak Euclidean bekerja sebagai berikut :

Algoritma 1 Langkah 1

Pilih awal pusat K : m 1 , m 2 , …. m K

Langkah 2

Menentukan setiap sampel x 1 (1 < I < N) pada pusat


terdekat, yang membentuk cluster K. yaitu menghitung nilai fungsi indicator δ (x i , C k ), (1 < k < K). 1, D ( x i , m k ) < D( x i , m j ) for all j ≠ k δ (x i , c k ) =  0, otherwise Langkah 3

Hitunglah pusat baru m k untuk setiap cluster C k 1 ck

Mk =

∑

n i =1

δ ( xi , C k ) xi

Dimana C k adalah jumlah sampel dalam C k

Ck = Langkah 4

∑

n

i =1

δ ( xi , Ck ) xi

menghasilkan m k (1 < k < K)

Isu utama yang memperluas k-means tradisional ke kernel k-means adalah penghitungan jarak dalam ruang baru. Anggaplah u i = Φ (x i ) menunjukkan transformasi x 1 . Jarak Euclidean antara u i dan u j ditulis sebagai : D2 (u i , u j ) = || Φ (x i ) – Φ (x j ) ||2 = Φ2 (x i ) -2 Φ (x i ) Φ (x j ) + Φ2(x j ) = k (x i , x i ) -2 k (x i , x i ) + k (x j , x j )

(2.6)

Anggaplah z k adalah pusat cluster dalam ruang yang ditransformasikan dimana, Zk =

1 ck

∑

N i =1

δ (u i , C k ) u i (2.7)

Dimana δ (u i , C k ) adalah fungsi indikator. Jarak antara u i dan z k dinyatakan sebagai berikut : 2

1 D {u i ,z k } = u i − ck 2

∑

N i =1

δ (u i , C k ) u i


= k (x i , x i ) + f (x i , C k ) + g (C k ) Dimana, f (x i , C k ) =

2 ck

∑

N i =1

δ (u j , C k ) k ( x i , x j )

(2.8)

Perbedaan utama antara kernel k-means dengan versi tradisional k-means ada di langkah 4, dalam algoritma Kernel K-means. Karena cluster dalam ruang yang ditransformasikan tidak dapat dinyatakan secara eksplisit, maka harus memilih pseudo centre. Dengan menggunakan Jarak Euclidean pada tradisional kmeans, diperoleh kernel berdasarkan algoritma k-means sebagai berikut :

Algoritma 2 Langkah 1

Tentukan δ (x i , C k ) (1< I < N, 1 < k < K) dengan nilai awal, yang membentuk cluster initial K C 1 , C 2 ,…, C k

Langkah 2

Untuk setiap cluster C k hitunglah |C k | dan g (C k )

Langkah 3

Untuk setiap sampel latihan x i dan cluster C k , hitunglah f(x i , C k ) dan kemudian tentukan x i pada cluster terdekat δ (x i , C k ) 1, f ( x i , C k ) + g (C k ) < f ( x i , C j ) + g (C j )  =  untuk j ≠ k 0, yang lain 

Langkah 4

Untuk setiap cluster C k , pilih sampel yang terdekat dengan pusat sebagai representative dari C k , m k = arc min D (δ (x i ),z k ). x i , dimana δ (x 19 , C k ) = 1


Dalam persamaan faktor k (x i , x j ) diabaikan karena tidak berkontribusi untuk menentukan cluster terdekat. Perbedaan utama antara kernel k-means dan versi tradisionalnya ada dalam langkah 4.

2.8. DECISION TREE Decision tree merupakan salah satu metode klasifikasi yang menggunakan representasi struktur pohon (tree) dimana setiap node mempresentasikan atribut, cabangnya merepresentasikan nilai dari atribut, dan daun merepresentasikan kelas. Node yang paling atas dari decision tree disebut sebagai root Decision tree merupakan metode klasifikasi yang paling popular digunakan. Selain karena pembangunannya relatif cepat, hasil dari model yang dibangun mudah untuk dipahami. Pada decision tree terdapat 3 jenis node, yaitu : a. Root Node, merupakan node paling atas, pada node ini tidak ada input dan bisa tidak mempunyai output atau mempunyai output atau mempunyai output lebih dari satu. b. Internal Node, merupakan node percabangan, pada node ini hanya terdapat satu input dan mempunyai output minimal dua. c. Leaf node atau terminal node, merupakan node akhir, pada node ini hanya terdapat satu input dan tidak mempunyai output.


2.9. ALGORITMA C 4.5 Algoritma C 4.5 adalah salah satu metode untuk membuat decision tree berdasarkan training data yang telah disediakan. Algoritma C 4.5 merupakan pengembangan dari ID3. Beberapa pengembangan yang dilakukan pada C 4.5 adalah sebagai antara lain bisa mengatasi missing value, bisa mengatasi continue data, dan praining. Pohon keputusan merupakan metode klasifikasi dan prediksi yang sangat kuat dan terkenal. Metode pohon keputusan mengubah fakta yang sangat besar menjadi pohon keputusan yang merepresentasikan aturan. Aturan dapat dengan mudah dipahami dengan bahasa alami. Dan mereka juga dapat diekspresikan dalam bentuk bahasa basis data seperti Structured Query Language untuk mencari record

pada

kategori

tertentu.

pohon

keputusan

juga

berguna

untuk

mengeksplorasi data, menemukan hubungan tersembunyi antara sejumlah calon variable input dengan sebuah variable target. Karena pohon keputusan memadukan antara eksplorasi data dan pemodelan, pohon keputusan sangat bagus sebagai langkah awal dalam proses pemodelan bahkan ketika dijadikan sebagai model akhir dari beberapa teknik lain. Sebuah model pohon keputusan terdiri dari sekumpulan aturan untuk membagi sejumlah populasi yang heterogen menjadi lebih kecil, lebih homogeny dengan memperhatikan pada variable tujuannya. Sebuah pohon keputusan mungkin dibangun dengan seksama secara manual atau dapat tumbuh secara otomatis dengan menerapkan salah satu atau beberapa algoritma pohon keputusan untuk memodelkan himpunan data yang belum terklasifikasi.


Variabel tujuan bisaanya dikelompokkan dengan pasti dan model pohon keputusan lebih mengarah pada perhitungan probability dari tiap-tiap record terhadap kategori-kategori tersebut atau untuk mengklasifikasi record dengan mengelompokkannya dalam satu kelas. Pohon keputusan juga dapat digunakan untuk mengestimasi nilai dari variabel continue meskipun ada beberapa teknik yang lebih sesuai untuk kasus ini. Banyak algoritma yang dapat dipakai dalam pembentukan pohon keputusan, antara lain ID3, CART, dan C4.5 (Larose, 2006). Data dalam pohon keputusan bisaanya dinyatakan dalam bentuk tabel dengan atribut dan record. Atribut menyatakan suatu parameter yang dibuat sebagai criteria dalam pembentukan pohon. Misalkan untuk menentukan main tenis, kriteria yang diperhatikan adalah cuaca, angin dan temperatur. Salah satu atribut merupakan atribut yang menyatakan data solusi per item data yang disebut target atribut. Atribut memiliki nilai-nilai yang dinamakan dengan instance. Misalkan atribut cuaca mempunyai instance berupa cerah, berawan dan hujan (Basuki dan Syarif, 2003). Proses pada pohon keputusan adalah mengubah bentuk data (tabel) menjadi

model

pohon,

mengubah

model

pohon

menjadi

rule,

dan

menyederhanakan rule (Basuki dan Syarif, 2003).

Berikut ini algoritma dasar dari C 4.5 : Input : sampel training, label training, atribut 1. Membuat simpul akar untuk pohon yang dibuat


2. Jika semua sampel positif, berhenti dengan suatu pohon dengan satu simpul akar, beri tanda (+) 3. Jika semua sampel negatif, berhenti dengan suatu pohon dengan satu simpul akar, beri tanda (-) 4. Jika atribut kosong, berhenti dengan suatu bohon dengan suatu simpul akar, dengan label sesuai nilai yang terbanyak yang ada pada label training 5. Untuk yang lain, Mulai a. A ---- atribut yang mengklasifikasikan sampel dengan hasil terbaik (berdasarkan Gain rasio) b. Atribut keputusan untuk simpul akar ---- A c. Untuk setiap nilai, vi, yang mungkin untuk A 1) Tambahkan cabang di bawah akar yang berhubungan dengan A = vi 2) Tentukan sampel Svi sebagai sbset dari sampel yang mempunyai nilai vi untuk atribut A 3) Jika sampel Svi kosong i. Di bawah cabang tambahkan simpul daun dengan label = nilai yang terbanyak yang ada pada label training ii. Yang lain tambah cabang baru di bawah cabang yang sekarang C 4.5 (sampel training, label training, atribut – [A]. d. Berhenti

Mengubah tree yang dihasilkan dalam beberapa rule. Jumlah rule sma dengan jumlah path yang mungkin dapat dibangun dari root sampai leaf node. Tree Praining dilakukan untuk menyederhanakan tree sehingga akurasi dapat bertambah. Pruning ada dua pendekatan, yaitu : a. Pre-praining, yaitu menghentian pembangunan suatu subtree lebih awal (yaitu dengan memutuskan untuk tidak lebih jauh mempartisi data training). Saat seketika berhenti, maka node berubah menjadi leaf (node akhir). Node akhir ini menjadi kelas yang paling sering muncul di antara subset sampel.


b. Post-praining, yaitu menyederhanaan tree dengan cara membuang beberapa cabang subtree setelah tree selesai dibangun. Node yang jarang dipotong akan menjadi leaf (node akhir) dengan kelas yang paling sering muncul.

Secara umum algoritma C 4.5 untuk membangun pohon keputusan adalah sebagai berikut : 1. Pilih atribut sebagai akar 2. Buat cabang untuk masing-masing nilai 3. Bagi kasus dalam cabang 4. Ulangi proses untuk masing-masing cabang sampai semua kasus pada cabang memiliki kelas yang sama

Untuk memilih atribut sebagai akar, didasarkan pada nilai Gain tertinggi dari atribut-atribut yang ada. Untuk menghitung Gain digunakan rumus seperti tertera dalam Rumus I (Craw, 2005). Gain(S,A) = Entropy(S) –

∑

n i =1

Si S

* Entropy ( Si )

Dengan S

: Himpunan Kasus

A

: Atribut

N

: Jumlah Partisi atribut A

|Si|

: Jumlah kasus pada partisi ke i

|S|

: Jumlah kasus dalam S


Sedangkan perhitungan nilai Entropy dapat dilihat pada rumus 2 berikut (Craw, 2005) : Entropy(A) =

∑

n i =1

− pi * log 2 pi

Dengan S

: Himpunan Kasus

A

: Fitur

n

: Jumlah partisi S

pi

: Proporsi dari Si terhadap S

Riset-Riset Terkait Terdapat beberapa riset yang telah dilakukn oleh banyak peneliti berkaitan dengan domain pendidikan, seperti yang akan dijelaskan di bawah ini. Yu et al (2010) dalam risetnya menjelaskan mengenai sebuah pendekatan data mining dapat diaplikasikan untuk meneliti faktor-faktor yang mempengaruhi tingkat daya ingat mahasiswa. Oyelade et al. (2010) dalam risetnya mengimplementasikan algoritma k-means clustering dikombinasikan dengan deterministik model untuk menganalisa hasil prestasi mahasiswa pada perguruan tinggi swasta Nugroho, (2008) menjelaskan dalam risetnya mengenai Implementasi decision tree berbasis analisis teknikal untuk pembelian dan penjualan saham, menyimpulkan system pendukung keputusan decision tree yang dibangun berdasarkan analisis teknikal mampu memberikan gambaran saat saham diperdagangkan hanya beerdasarkan pergerakan trend. Perdagangan berdasarkan


pergerakan trend ini bersifat spekulasi namun cukup mampu memberikan keuntungan. Sunjana (2010b) menjelaskan dalam risetnya tentang klasifikasi data nasabah sebuah asuransi menggunakan algoritma C 4.5, berikut adalah kesimpulan yang dapat diambil dari data nasabah asuransi setelah dilakukan analisis menggumakan metode algoritma C 4.5 : 1. Aplikasi dapat menyimpulkan bahwa rata-rata nasabah memiliki status L dikarenakan pembayaran premi yang melebihi 10% dari penghasilam 2. Dengan persentase atribut premi dasar dan penghasilan, maka dapat diketahui rata-rata status nasabah memiliki nilai P atau L Bhargavi at al (2008) menjelaskan dalam risetnya tetang menguraikan pengetahuan menggunakan aturan dengan pendekatan decision tree. Al-Radaideh et al (2006) menjelaskan dalam risetnya tentang pemanfaatan data mining terhadap data mahasiswa menggunakan decision tree. Adeyemo dan Kuye (2006) menjelaskan dalam risetnya untuk memprediksi kinerja mahasiswa di bidang akademik menggunakan algoritma decision tree. Dedy Hartama (2011) menjelaskan model aturan keterhubungan data mahasiswa menggunakan Algoritma C 4.5 untuk meningkatkan indeks prestasi. 2.10. Persamaan dengan Riset-Riset Lain Kruck dan Lending (2003) dalam penelitiannya menjelaskan sebuah model untuk memprediksi kinerja di tingkat perguruan tinggi dalam mata kuliah pengantar sistem informasi.


Ogor (2007) dalam penelitiannya menggunakan teknik data mining yang digunakan untuk membangun prototype Penilaian Kinerja Monitoring Sistem (PAMS) untuk mengevaluasi kinerja mahasiswa. Sajadin et al (2009) menggunakan teknik data mining dalam pemantauan dan memprediksi peningkatan prestasi mahasiswa berdasarkan minat, prilaku belajar, pemanfaatan waktu dan dukungan orang tua di perguruan tinggi.

2.11. Perbedaan dengan Riset-Riset Lain Dari beberapa riset yang dilakukan peneliti sebelumnya, terdapat beberapa titik perbedaan dengan riset yang akan dilakukan ini : Analisa dalam proses pengambilan keputusan dalam melakukan tindakan preventif terhadap mahasiswa yang cenderung gagal kuliah atau drop-out, diperlukan sebuah model profil mahasiswa yang dapat menggambarkan situasi ril mahasiswa tersebut pada saat mengikuti perkuliahan, selanjutnya bagaimana model ini dapat dijadikan sebagai indikator untuk deteksi dini kondisi mahasiswa yang cenderung drop-out. Pada penelitian ini hasil akhir yang diharapkan dengan analisa model profil mahasiswa dan model prediksi yang diperoleh dari penelitian ini juga dapat dipergunakan oleh institusi-institusi pendidikan tinggi yang memiliki program sarjana, sebagai sistem informasi pendukung dalam proses pengambilan keputusan untuk melakukan tindakan preventif terhadap mahasiswa diploma tiga yang cenderung drop-out.


2.12. Kontribusi Riset Penelitian ini memberikan kontribusi pada pemahaman kita tentang hubungan para dosen untuk lebih mengenal situasi para mahasiswanya, dan dapat dijadikan sebagai pengetahuan dini dalam proses pengambilan keputusan untuk tindakan preventif dalam hal mengantisipasi mahasiswa drop-out, untuk meningkatkan prestasi mahasiswa, untuk meningkatkan kurikulum, meningkatkan proses kegiatan belajar dan mengajar

dan banyak lagi keuntungan lain yang bisa

diperoleh dari hasil penambangan data yang telah ditentukan oleh perguruan tinggi. Beberapa kemungkinan lain mungkin dianggap penting adalah dosen wali dapat menggunakan informasi yang diberikan dalam mengambil beberapa tindakan untuk meningkatkan kinerja mahasiswa dalam meningkatkan predikat kelulusan. Pembuat keputusan bisa menggunakan model profil mahasiswa yang potensial drop out menggunakan Teknik kernel k-mean clustering dan Decision tree untuk meningkatkan kualitas pengambilan keputusan. Penelitian ini memperkenalkan aplikasi metode Kernel K-Means Clustering untuk lembaga pendidikan tinggi


BAB II TINJAUAN PUSTAKA

Recommend Documents