LAPORAN TUGAS METODE PENELITIAN DENGAN ALGORITMA C4.5 TENTANG MAHASISWA DROP OUT BAB 2

BAB II

LANDASAN TEORI

1.1        JURNAL PENDUKUNG

a.       Peneraapan Algoritma C4.5 pada progam Klasifikasi Mahasiswa Dropout

Berdasarkan  sudut  pandang  operasional,  data  mining  adalah  proses  terpadu  dari analisis data yang terdiri dari serangkaian kegiatan yang berjalan berdasarkan definisi tujuan yang akan dianalisis, dengan analisis datanya sampai interpretasi dan evaluasi hasil, Guidici dan Figini [7]. Data mining didefinisikan sebagai proses menemukan pola dalam data.   Proses ini harus otomatis atau biasanya secara semi-otomatis.Pola yang dihasilkan harus berarti bahwa pola tersebut memberikan beberapa keuntungan.Pola tersebut diidentifikasi, divalidasi, dan digunakan untuk membuat sebuah prediksi,Witten, Frank, dan Hall[8]. Klasifikasi   merupakan   salah   satu   teknik   data   mining.Klasifikasi   (taksonomi) merupakan proses penempatan objek atau konsep tertentu ke dalam satu set kategori berdasarkan objek yang digunakan.   Salah satu teknik klasifikasi yang paling popular digunakan adalah decision tree, Han dan Kamber[6].  Decision tree merupakan salah satu metode klasifikasi yang menggunakan representasi struktur pohon (tree) di mana setiap node merepresentasikan atribut, cabangnya merepresentasikan nilai dari atribut, dan daun merepresentasikan kelas.Node yang paling atas dari decision tree disebut sebagai root. 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 lebih dari satu.

b.      Internal Node , merupakan node percabangan, pada node ini hanya terdapat satu

c.       input dan mempunyai output minimal dua.

d.      Leaf  node  atau  terminal  node  ,  merupakan  node  akhir,  pada  node  ini  hanya terdapat satu input dan tidak mempunyai output.

Banyak algoritma yang dapat dipakai dalam pembentukan pohon keputusan, antara lain ID3, CART, dan C4.5, Larose[9].  Data dalam pohon keputusan biasanya dinyatakan dalam bentuk tabel  dengan atribut dan record. Atribut menyatakan suatu parameter yang dibuat sebagai kriteria dalam pembentukan pohon. Misalkan untuk menentukan main tenis, kriteria yang diperhatikan adalah cuaca, angin, dan temperatur. Seperti ditunjukkan dalam Gambar 1, decision tree tergantung pada aturan if-then, tetapi tidak membutuhkan parameter dan metrik.  Strukturnya yang sederhana dan dapat ditafsirkan memungkinkan decision tree untuk memecahkan masalah atribut multi-type.Decision tree juga dapat mengelola nilai-nilai yang hilang atau data noise, Dua dan Xian [10]. Algoritma C4.5 dan pohon keputusan merupakan dua model yang tak terpisahkan, karena untuk membangun sebuah pohon keputusan, dibutuhan algoritma C4.5.Di akhir tahun 1970 hingga di awal tahun 1980-an, J. Ross Quinlan seorang peneliti di bidang mesin pembelajaran mengembangkan sebuah model pohon keputusan yang dinamakan ID3 (Iterative Dichotomiser), walaupun sebenarnya proyek ini telah dibuat sebelumnya oleh E.B. Hunt, J. Marin, dan P.T. Stone. Kemudian Quinlan membuat algoritma dari pengembangan ID3 yang dinamakan C4.5 yang berbasis supervised learning Han dan Kamber[6]. Serangkaian perbaikan yang dilakukan pada ID3 mencapai puncaknya dengan menghasilkan sebuah sistem praktis dan berpengaruh untuk decision tree yaitu C4.5. Perbaikan ini meliputi metode untuk menangani numeric attributes, missing values, noisy data, dan aturan yang menghasilkan rules dari trees, Witten, Frank, dan Hall [8]. Ada  beberapa  tahapan  dalam  membuat  sebuah  pohon  keputusan  dalam algoritma

C4.5, Larose [9] yaitu :

a.       Mempersiapkan data training. Data training biasanya diambil dari data histori yang pernah terjadi sebelumnya atau disebut data masa lalu dan sudah dikelompokkan dalam kelas-kelas tertentu.

b.      Menghitung akar dari pohon. Akar akan diambil dari atribut yang akan terpilih, dengan  cara  menghitung  nilai  gain  dari  masing-masing  atribut,  nilai  gain  yang paling tinggi yang akan menjadi akar pertama. Sebelum menghitung nilai gain dari atribut,  hitung  dahulu  nilai  entropy

b.      Analisis komparasi algoritma klasifikasi data mining untuk prediksi mahasiswa non aktif

Perguruan tinggi merupakan penyelenggara pendidikan akademik bagi mahasiswa [1]. Lima lembaga perguruan tinggi diantaranya adalah universitas, institut, sekolah tinggi, akademi dan politeknik. Data yang diperoleh dari Pusat Statistik Pendidikan Badan Penelitian dan Pengembangan Departemen Pendidikan Nasional Republik Indonesia [2] menyebutkan bahwa jumlah lembaga penyelenggara perguruan tinggi mengalami peningkatan setiap tahunnya. Sampai dengan tahun 2010 tercatat 3011 perguruan tinggi diselenggarakan di Indonesia. Perguruan tinggi diharapkan menyelenggarakan pendidikan yang berkualitas bagi mahasiswa sehingga menghasilkan sumber daya manusia yang berilmu, cakap dan kreatif [3]. Semakin bertambah jumlah perguruan tinggi maka semakin meningkat pula jumlah sumber daya manusia berkualitas yang  dihasilkan  perguruan  tinggi.  Salah  satu  faktor  yang  menentukan  kualitas  perguruan  tinggi  adalah  persentasi kemampuan  mahasiswa untuk menyelesaikan  studi tepat  waktu.  Berdasarkan  matriks  penilaian  instrument  akreditasi program studi Badan Akreditasi Nasional Perguruan Tinggi [4] bahwa persentase mahasiswa yang lulus tepat waktu merupakan salah satu elemen penilaian akreditasi universitas. Data dari Pusat Statistik Pendidikan Badan Penelitian dan Pengembangan Departemen Pendidikan Nasional Republik Indonesia [2] pada tahun akademik 2001/2002 sampai dengan 2009/2010 menunjukkan bahwa perguruan tinggi menerima rata-rata sebanyak 868.050 mahasiswa baru dan meluluskan rata-rata 451.168 mahasiswa setiap tahunnya. Jumlah lulusan perguruan tinggi ternyata hanya mencapai 51,97% dari jumlah mahasiswa baru setiap tahun. Artinya, terdapat 48,03% mahasiswa yang tidak diketahui statusnya.   Ketidakjelasan status tersebut bisa jadi karena mahasiswa menempuh studi tidak tepat waktu, memiliki status non-aktif (mangkir) atau bahkan drop out. Saat ini, masalah kegagalan studi siswa dan faktor-faktor penyebabnya menjadi topik yang menarik untuk diteliti [5]. Perguruan tinggi perlu mendeteksi perilaku mahasiswa yang memiliki status “tidak diinginkan” tersebut  sehingga dapat diketahui faktor-faktor penyebab kegagalannya. Beberapa penyebab kegagalan mahasiswa diantaranya rendahnya kemampuan akademik, faktor pembiayaan, domisili saat menempuh studi dan faktor lainnya. Universitas Dian Nuswantoro merupakan salah satu perguruan tinggi swasta terbesar di Jawa Tengah yang memiliki 13.416 mahasiswa. Gambar 2 menunjukkan  bahwa  terdapat  30,84%  atau  sekitar  4.138  mahasiswa  dengan  status  non  aktif.  Tingginya  persentasi mahasiswa yang memiliki status non aktif menyebabkan tingginya persentasi mahasiswa lulus tidak tepat waktu. Hal tersebut menjadi sangat penting bagi manajemen universitas mengingat persentasi mahasiswa lulus tepat waktu adalah salah satu elemen penilaian akreditasi yang ditetapkan oleh Badan Akreditasi Nasional. Manajemen memerlukan tindakan untuk mengetahui faktor-faktor penyebab mahasiswa memiliki status non aktif. Database perguruan tinggi menyimpan data akademik, administrasi dan biodata mahasiswa. Data tersebut apabila digali dengan  tepat  maka  dapat  diketahui  pola  atau  pengetahuan  untuk  mengambil  keputusan  [6].  Serangkaian  proses mendapatkan pengetahuan atau pola dari kumpulan data  disebut dengan data mining [7]. Data mining memecahkan masalah dengan menganalisis data yang telah ada dalam database. Perguruan tinggi perlu melakukan prediksi perilaku mahasiswa untuk  mencegah secara  dini  kegagalan  akademik  mahasiswa.  Penelitian  yang dilakukan  oleh  Kotsiantis, Pierrakeas dan Pintelas [12] menyebutkan bahwa sangat penting bagi dosen untuk mendeteksi mahasiswa yang cenderung drop out sebelum mereka memasuki pertengahan masa studi. Beberapa algoritma klasifikasi data mining telah digunakan untuk memprediksi perilaku mahasiswa yang berpotensi drop out diantaranya decision tree, neural network, naïve bayes, instance-based learning, logistic regression dan support vector machine. Hasilnya, naïve bayes menunjukkan hasil yang paling akurat. Penelitian yang dilakukan oleh Gerben W. Dekker [11] menyebutkan bahwa monitoring dan dukungan terhadap mahasiswa di tahun pertama sangat penting dilakukan. Mahasiswa jurusan teknik elektro Universitas Eindhoven yang berhenti studi pada tahun pertama mencapai hingga 40%. Kurikulum yang sulit dianggap sebagai salah satu penyebab tingginya jumlah mahasiswa drop out. Selain itu, nilai, prestasi, kepribadian,latar belakang sosial mempunyai peran dalam kesuksesan akademik mahasiswa. Dekker menggunakan algoritma Decision tree, Bayesian classifiers, logistic models, rule-based learner dan random forest.Dalam penelitian ini, dilakukan analisis komparasi empat algoritma klasifikasi data mining yaitu  logistic regression, decision tree, naïve bayes dan neural network dengan menggunakan 3681 data set  mahasiswa yang terdiri atas data demografi dan akademik mahasiswa sehingga dapat diketahui algoritma yang paling akurat untuk memprediksi mahasiswa non-aktif.Data mining Menurut Witten [7], serangkaian proses mendapatkan pengetahuan atau pola dari kumpulan data disebut dengan data mining. Data mining memecahkan masalah dengan menganalisis data yang telah ada dalam database. Penelitian tentang klasifikasi  algoritma  data  mining  untuk prediksi  mahasiswa  yang  memiliki  potensi  drop-out dilakukan  oleh  Sotiris Kotsiantis [13] dengan    menggunakan 354 mahasiswa Hellenic Open University sebagai data set. Kotsiantis mengelompokkan  2  kelompok  atribut  yaitu:  berbasis  kurikulum dan  kinerja  mahasiswa.  Atribut  kelompok  berbasis kurikulum terdiri atas:  jenis kelamin, usia, status marital,  jumlah  anak,  pekerjaan, kemampuan komputer, hubungan pekerjaan dengan komputer. Adapun atribut dalam kelompok kinerja mahasiswa terdiri atas: tatap muka ke-1, tugas ke-1, tatap muka ke-2, tugas ke-2. Kotsiantis menggunakan 6 (enam) algoritma yaitu: decision tree, neural network, naïve bayes, instance-based learning, logistic regression dan support vector machine.

c.       Implementasi algoritma C4.5 dalam aplikasi untuk memprediksi jumlah mahasiswa yang mengulang mata kuliah di stimik amikom yogyakarta

Perkembangan   dunia   pendidikan   saat   ini   sangat   pesat,   itu   dikarenakan kesadaran masyarakat akan manfaat dari pendidikan sudah tinggi sehingga peningkatannya setiap tahun selalu mengalami kenaikan. Dengan perkembangan yang pesat itu dapat menimbulkan masalah bagi setiap perguruan tinggi dalam memanajemen mahasiswa dengan baik. STMIK  AMIKOM  Yogyakarta  merupakan  salah  satu  perguruan  tinggi  yang sukses menarik banyak mahasiswa disetiap tahunnya, terbukti dengan meningkatnya jumlah pendaftar calon mahasiswa baru disetiap periode. Maka dengan peningkatan ini pihak akedemik harus meningkatkan juga kualitas dan kenyamanan  bagi mahasiswa dalam menjalini studinya. Oleh karena itu dibutuhkan sebuah sistem yang bisa mambantu dalam memanajemen mata kuliah, namun pihak akademik selalu mendapat kesulitan dalam memprediksi jumlah mahasiswa yang akan mengulang mata kuliah pada setiap semesternya atau setiap periode. Sehingga dalam   mengatur jumlah kelas yang akan diadakan bagi mahasiswa yang ingin mengulang mata kuliah tertentu masih dilakukan dengan manual. Data Mining didefinisikan sebagai sebuah proses untuk menemukan hubungan, pola dan trend baru yang bermakna dengan menyaring data yang sangat besar, yang tersimpan  dalam penyimpanan,  menggunakan  teknik  pengenalan  pola  seperti  teknik statistik dan matematika (Larose, 2005). Data mining bukanlah suatu bidang yang sama sekali baru. Salah satu kesulitan untuk mendefinisikan data mining adalah kenyataan bahawa data mining mewarisis banyak aspek dan teknik dari bidang-bidang ilmu yang sudah mapan terlebih dahulu. Berawal dari beberapa disiplin ilmu, data mining bertujuan untuk memperbaiki teknik tradisional sehingga bisa menangani :

1.   Jumlah data yang sangat besar

2.   Dimensi data yang tinggi

3.   Data yang heterogen dan berbede sifat

                     

1.2        TEORI PENDUKUNG

Data mining bukanlah suatu bidang yang sama sekali baru. Salah satu kesulitan untuk mendefinisikan data mining adalah kenyataan bahawa data mining mewarisis banyak aspek dan teknik dari bidang-bidang ilmu yang sudah mapan terlebih dahulu. Menurut para ahli, data mining merupakan sebuah analisa dari observasi data dalam jumlah besar untuk menemukan hubungan yang tidak diketahui sebelumnya dan metode  baru  untuk meringkas  data  agar mudah  dipahami  serta  kegunaannya  untuk pemilih data ( David Hand,2001 ).Data mining didefinisikan sebagai proses menemukan pola dalam data.   Proses ini harus otomatis atau biasanya secara semi-otomatis.Pola yang dihasilkan harus berarti bahwa pola tersebut memberikan beberapa keuntungan.Pola tersebut diidentifikasi, divalidasi, dan digunakan untuk membuat sebuah prediksi,Witten, Frank, dan Hall[8]. Berawal dari beberapa disiplin ilmu, data mining bertujuan untuk memperbaiki teknik tradisional sehingga bisa menangani :

1.   Jumlah data yang sangat besar

2.   Dimensi data yang tinggi

3.   Data yang heterogen dan berbede sifat

Pohon Keputusan (Decision Tree) 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. Aturan ini juga dapat diekspresikan dalam bentuk bahasa basis data seperti SQL untuk mencari record pada kategori tertentu. Pohon keputusan juga berguna untuk mengeksplorasi data, menemukan hubungan tersembunyi antara sejumlah calon variabel input dengan sebuah variabel target. Karena pohon keputusan memadukan antara eksplorasi data dan pemodelan, pohon keputusan ini sangat bagus sebagai langkah awal dalam proses pemodelan bahkan ketika dijadikan sebagai model akhir dari beberapa teknik lain (J R Quinlan, 1993).

Dalam situasi lain kemampuan untuk menjelaskan alasan pengambilan keputusan adalah sesuatu yang sangat penting. Misalnya pada perusahaan asuransi ada larangan resmi untuk mendeskriminasi berdasarkan variabel-variabel tertentu. Perusahaan asuransi dapat mencari sendiri keadaan yang mencerminkan bahwa mereka tidak menggunakan deskriminasi yang ilegal dalam memutuskan seseorang diterima atau ditolak. Sebuah pohon keputusan adalah sebuah struktur yang dapat digunakan untuk membagi kumpulan data yang besar menjadi himpunan-himpunan record yang lebih kecil dengan menerapkan serangkaian aturan keputusan. Anggota himpunan hasil menjadi mirip satu dengan yang lain dengan masing-masing rangkaian pembagian. Sebuah model pohon keputusan terdiri dari sekumpulan aturan untuk membagi sejumlah populasi yang heterogen menjadi lebih kecil, lebih homogen dengan memperhatikan pada variabel 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 terklarifikasi (Tan dkk, 2004).

Variabel tujuan biasanya dikelompokkan dengan pasti dan model pohon keputusan lebih mengarah pada perhitungan probabilitas dari masing-masing record terhadap kategori-kategori tersebut, atau untuk mengklasifikasi record dengan mengelompokkannya dalam satu kelas. Pohon keputusan juga dapat digunakan untuk mengestimasi nilai dari variabel kontinyu, meskipun ada beberapa teknik yang lebih sesuai . Kelebihan dari metode pohon keputusan adalah:

1.      Daerah pengambilan keputusan yang sebelumnya kompleks dan sangat global, dapat diubah menjadi lebih simpel dan spesifik

2.      Eliminasi perhitungan-perhitungan yang tidak diperlukan, karena ketika menggunakan metode pohon keputusan maka sampel diuji hanya berdasarkan kriteria atau kelas tertentu

3.      Fleksibel untuk memilih fitur dari node internal yang berbeda, fitur yang terpilih akan membedakan suatu kriteria dibandingkan kriteria yang lain dalam node yang sama. Kefleksibelan metode pohon keputusan ini meningkatkan kualitas keputusan yang dihasilkan jika dibandingkan ketika menggunakan metode penghitungan satu tahap yang lebih konvensional

4.      Dalam analisis multivarian, dengan kriteria dan kelas yang jumlahnya sangat banyak, seorang penguji biasanya perlu mengestimasikan baik itu distribusi dimensi tinggi ataupun parameter tertentu dari distribusi kelas tersebut. Metode pohon keputusan dapat menghindari munculnya permasalahan ini dengan menggunakan kriteria yang jumlahnya lebih sedikit pada setiap node internal tanpa banyak mengurangi kualitas keputusan yang dihasilkan.

Kekurangan pada pohon keputusan adalah:

1.      Terjadi overlapping terutama ketika kelas-kelas dan kriteria yang digunakan jumlahnya sangat banyak. Hal tersebut juga dapat menyebabkan meningkatnya waktu pengambilan keputusan dan jumlah memori yang diperlukan

2.      Pengakumulasian jumlah kesalahan dari setiap tingkat dalam sebuah pohon keputusan yang besar

3.      Kesulitan dalam mendesain pohon keputusan yang optimal

4.      Hasil kualitas keputusan yang didapatkan dari metode pohon keputusan sangat tergantung pada bagaimana pohon tersebut didesain.

Pohon keputusan adalah model prediksi menggunakan struktur pohon atau struktur berhirarki (Pramudiono,2008). Setiap percabangan menyatakan kondisi yang harus dipenuhi dan tiap ujung pohon menyatakan kelas data. Contoh pada Gambar diatas adalah identifikasi pembeli komputer. Dari pohon keputusan tersebut diketahui bahwa salah satu kelompok yang potensial membeli komputer adalah orang yang berusia di bawah 30 tahun dan juga pelajar. Setelah sebuah pohon keputusan dibangun maka dapat digunakan untuk mengklasifikasikan record  yang belum ada kelasnya. Dimulai dari node root,  menggunakan tes terhadap atribut dari record yang belum ada kelasnya ini lalu mengikuti cabang yang sesuai dengan hasil dari tes tersebut, yang akan membawa kepada internal node (node yang memiliki satu cabang masuk dan dua atau lebih cabang yang keluar), dengan cara harus melakukan tes lagi terhadap atribut atau node leaf. Record yang kelasnya tidak diketahui kemudian diberikan kelas yang sesuai dengan kelas yang ada pada node leaf. Pada pohon keputusan setiap simpul leaf menandai label kelas. Proses dalam pohon keputusan yaitu mengubah bentuk data (tabel) menjadi model pohon (tree) kemudian mengubah model pohon tersebut menjadi aturan (rule) (J R Quinlan, 1993).

Salah satu algoritma induksi pohon keputusan yaitu ID3 (Iterative Dichotomiser 3). ID3 dikembangkan oleh J. Ross Quinlan. Dalam prosedur algoritma ID3, input berupa sampel training, label training dan atribut. Algoritma Decision Tree C4.5 merupakan pengembangan dari ID3. Sedangkan pada perangkat lunak open source WEKA mempunyai versi sendiri dari C4.5 yang dikenal sebagai J48..

Algoritma C4.5 adalah algoritma klasifikasi data dengan teknik pohon keputusan yang terkenal dan disukai karena memiliki kelebihan-kelebihan. Kelebihan ini misalnya dapat mengolah data numerik (kontinyu) dan diskret, dapat menangani nilai atribut yang hilang, menghasilkan aturan-aturan yang mudah diintrepetasikan dan tercepat diantara algoritma-algoritma yang lain. Keakuratan prediksi yaitu kemampuan model untuk dapat memprediksi label kelas terhadap data baru atau yang belum diketahui sebelumnya dengan baik

Dalam hal kecepatan atau efisiensi waktu komputasi yang diperlukan untuk membuat dan menggunakan model.  Kemampuan model untuk memprediksi dengan benar walaupun data ada nilai dari atribut yang hilang.  Dan juga skalabilitas yaitu kemampuan untuk membangun model secara efisien untuk data berjumlah besar (aspek ini akan mendapatkan penekanan). Terakhir interpretabilitas yaitu model yang dihasilkan mudah dipahami.

Berikut langkah- langkahnya :

1.      Mempersiapkan data training. Data training biasanya diambil dari data histori yang pernah terjadi sebelumnya atau disebut data masa lalu dan sudah dikelompokkan dalam kelas-kelas tertentu.

2.      Menghitung akar dari pohon. Akar akan diambil dari atribut yang akan terpilih, dengan  cara  menghitung  nilai  gain  dari  masing-masing  atribut,  nilai  gain  yang paling tinggi yang akan menjadi akar pertama. Sebelum menghitung nilai gain dari atribut,  hitung  dahulu  nilai  entropy Untuk  menghitung  nilai  entropy  digunakan rumus :

                

Keterangan :

S= Himpunan kasus n = jumlah partisi S

Pi = proporsi Si terhadap S

Kemudian hitung nilai gain menggunakan rumus :

                       

Keterangan :

S = Himpunan Kasus

A = Fitur        

n = jumlah partisi atribut A

|Si| = Proporsi Si terhadap S

|S| = jumlah kasus dalam S

3.      Ulangi langkah ke 2 dan langkah ke 3 hingga semua record terpatisi Proses partisi pohon keputusan akan berhenti saat :

a.       semuarecord dalam simpul N mendapat kelas yang sama.

b.      Tidak ada atribut di dalamrecord yang dipartisi lagi

c.       Tidak ada record di dalam cabang yang kosong