Laporkan Masalah

ANALISIS DAN PENINGKATAN KINERJA ALGORITME C4.5 MENGGUNAKAN ALGORITME C4.5+WEIGHTING VALUE

HANDOYO WIDI NUGROHO, Teguh Bharata Adji, S. T., M. T., M. Eng., Ph. D.; Noor Akhmad Setiawan, S. T., M. T., Ph. D.

2021 | Disertasi | DOKTOR TEKNIK ELEKTRO

Algoritme pohon keputusan (decision tree) C4.5 merupakan salah satu algoritme klasifikasi data yang mudah untuk diintepretasikan dan mempunyai struktur yang sederhana. Beberapa penelitian menjadikan decision tree sebagai objek kajian, yaitu pada proses pemilihan split atribut dan proses pruning. Pemilihan Split atribut merupakan proses utama dalam pembentukan decision tree. Metode-metode yang dikembangkan untuk pemilihan split atribut diantaranya Gini Index, Information Gain, Simplifying Decision Tree, Gain Ratio, Imprecise Info Gain (IIG), Imprecise Information Gain Ratio (IIGR), dan AdaptiveCC4.5. Setelah dilakukan pemilihan split atribut, proses selanjutnya adalah pruning. Pruning adalah proses yang dilakukan untuk memotong atau menghilangkan beberapa cabang (node) yang tidak diperlukan. Node yang tidak diperlukan dapat menyebabkan ukuran decision tree menjadi sangat besar dan hal ini disebut over-fitting. Metode-metode yang dikembangkan untuk pruning diantaranya menggunakan post pruning, yaitu Pessimistic Error Pruning, Cost complexity pruning (CCP), Reduce Error Pruning (REP), dan Error Base Pruning (EBP). Beberapa penelitian yang dikembangkan untuk proses pruning masih memiliki kelemahan, yaitu memungkinkan pemangkasan terhadap node dengan nilai informasi yang tinggi dan kontribusi dalam pembentukan rule. Penelitian ini mengusulkan metode untuk memodifikasi proses pruning menggunakan perhitungan nilai delta, certainty factor (CF) dan weighting value. Nilai delta ini diterapkan dengan memanfaatkan perbedaan jumlah anggota objek antar node. Apabila perbedaan jumlah anggota objek antar node (selisih) kecil menunjukkan bahwa node tersebut adalah node yang tidak kontributif. Nilai CF diperoleh dari nilai entropi yang dikalikan dengan selisih dari entropi maksimum dengan nilai Gain_Ratio. Perhitungan nilai CF digunakan untuk memastikan bahwa node yang akan dilakukan proses pruning adalah node yang benar-benar tidak kontributif. Sedangkan weighting value digunakan untuk memperbaiki proses pruning dengan memberikan nilai bobot pada setiap atribut yang terpilih sebagai Split. Nilai bobot ini akan membatasi pohon keputusan yang dibentuk. Pengembangan yang dilakukan pada penelitian ini adalah dengan memanfaatkan resources yang sudah ada pada C4.5, yaitu dengan menggunakan fungsi entropi untuk menentukan cabang (node) yang akan di-pruning, sehingga tambahan beban komputasi sangat kecil, yaitu pada proses pemangkasannya saja. Dataset yang digunakan untuk eksperimen dan menjelaskan metode peningkatan nilai akurasi Algoritme C4.5 ini adalah dataset dari University of California at Irvine�s (UCI) machine learning repository. Setelah dilakukan pengukuran nilai akurasi terhadap seluruh dataset yang digunakan, kemudian dilakukan perbandingan nilai akurasi yang dihasilkan oleh masing-masing metode. Hasil eksperimen pada penelitian ini menunjukkan bahwa C4.5+Weighting value memiliki performa yang paling baik dibandingkan dengan metode lainnya. Hal ini ditunjukkan dengan peningkatan nilai akurasi sebesar 8,48% (C4.5+REP), 2,87% (CF), dan 1,9% (Delta). Hasil dari penelitian ini dapat digunakan sebagai acuan untuk memilih metode yang tepat sesuai dengan kasus-kasus dalam data mining khususnya proses klasifikasi data.

C4.5 decision tree algorithm is one of the most frequently used data classification algorithms, is easy to interpret, and has a simple structure. Several studies have made the decision tree of object study, namely split attribute selection process, and pruning process. The selection of split attributes is the main process in forming a decision tree. The developed methods for selecting split attributes included Gini Index, Information Gain, Simplifying Decision Tree, Gain Ratio, Imprecise Info Gain (IIG), Imprecise Information Gain Ratio (IIGR), and Adaptive CC4.5. After selecting split attributes, the next process was pruning. Pruning was a process carried out to cut or remove some unnecessary branches (nodes). Unnecessary nodes led to a very large decision tree size. Therefore, it was called the over-fitting. The methods developed for pruning included post pruning, namely Pessimistic Error Pruning, Cost complexity pruning (CCP), Reduce Error Pruning (REP), and Error Base Pruning (EBP). A number of developed studies for the pruning process still had weaknesses, namely, they allowed the pruning of nodes with high information value and contribute to rule formation. This condition affected the decline of the classification results in the decision tree. In this study, the proposed method was to use the calculation of delta value, certainty factor (CF), and weighting value. The different number utilization of object members stated between nodes implemented this delta value. The difference in the number of object members was substantial. It indicated that the node with the smallest object value was a non-contributive node. Thus, the node was carried out as a pruning process. CF value was obtained from the entropy value multiplied by the difference between maximum entropy and Gain_Ratio value. The non-contributive nodes to be trimmed in the CF value Calculation were used. Meanwhile, the split selected for each attribute gives a weight value to improve the trimming process on the used weighting value. This weight value was able to limit the formed decision tree. If the weighting value was small, it was indicated as a non-contributive node. Meanwhile, it was greater than the threshold. Furthermore, it indicated a contributive node. The dataset for experiments and explaining the method to improve the performance of C4.5 algorithm was a dataset from the University of California at Irvine's (UCI) machine learning repository. After measuring the accuracy value of the entire dataset used, each method was compared to produce an accuracy value. The experimental results in this study indicated that C4.5 + weighting value had the recommended performance compared to other methods. Furthermore, it indicated that there was an increment in the average accuracy of 8.48% (C4.5 + REP), 2.87% (CF), and 1.9% (Delta). Finally, the result of this study stated that it can be used as a reference for choosing the right method according to cases in data mining, especially the data classification process.

Kata Kunci : peningkatan nilai akurasi Algoritme C4.5, pruning, cabang kontributif

  1. S3-2015-389926-abstract.pdf  
  2. S3-2015-389926-bibliography.pdf  
  3. S3-2015-389926-tableofcontent.pdf  
  4. S3-2015-389926-title.pdf