Algoritma CART & C4.5 & K-Means

Algoritma CART (Classification and Regression Tress ), C4.5 dan K-Means adalah salah satu algoritma yang digunakan di dalam Data Mining. Kalau berbicara Data Mining saya teringat salah satu dosen ( DR.Sani ) Data Mining ini seperti bermain-main dengan data atau berbicara Data Mining "Discovering Knowledge in Data" bahwa sebuah data itu baiknya kita olah untuk bisa menghasilkan pengetahuan dan dari pengetahuan ini bisa menjadi Informasi untuk kita. 

Classification and Regression Trees (CART) adalah  salah satu metode atau algoritma dari teknik pohon keputusan. CART adalah suatu metode statistik nonparametrik yang dapat menggambarkan hubungan antara variabel respon (variabel dependen) dengan satu atau lebih variabel prediktor (variabel independen). Menurut Breiman dkk (1993), apabila variabel respon berbentuk kontinu maka metode yang digunakan adalah metode regresi pohon (regression trees), sedangkan apabila variabel respon  memiliki skala kategorik maka metode yang digunakan adalah metode klasifikasi pohon (classification trees). Variabel respon dalam penelitian ini berskala kategorik, sehingga metode yang akan digunakan adalah metode klasifikasi pohon. Pembentukan pohon klasifikasi terdiri atas 3 tahap yang memerlukan learning sample L. Tahap pertama adalah pemilihan pemilah. Setiap pemilahan hanya bergantung pada nilai yang berasal dari satu variabel independen [9]. Untuk variabel independen kontinu Xj dengan ruang sampel berukuran n dan terdapat n nilai amatan sampel yang berbeda, maka akan terdapat n - 1 pemilahan yang berbeda.

Sedangkan untuk Xj adalah variabel kategori nominal bertaraf L , maka akan diperoleh pemilahan sebanyak

2 ^{L- 1} - 1. Tetapi jika variabel X adalah kategori ordinal maka akan diperoleh L - 1 pemilahan yang mungkin.

Algoritma C4.5

Secara umum algoritma C4.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 kelasyang sama.

K-Means

K-means merupakan salah satu algoritma clustering ^[1]. Tujuan algoritma ini yaitu untuk membagi data menjadi beberapa kelompok. Algoritma ini menerima masukan berupa data tanpa label kelas. Hal ini berbeda dengan supervised learning yang menerima masukan berupa vektor (­x­₁ , y₁) , (­x­₂ , y₂) , …, (­x­_i , y_i), di mana x_imerupakan data dari suatu data pelatihan dan y_i merupakan label kelas untuk x_i ^[2].

Pada algoritma pembelajaran ini, komputer mengelompokkan sendiri data-data yang menjadi masukannya tanpa mengetahui terlebih dulu target kelasnya^[1]. Pembelajaran ini termasuk dalam unsupervised learning. Masukan yang diterima adalah data atau objek dan k buah kelompok (cluster) yang diinginkan.  Algoritma ini akan mengelompokkan data atau objek ke dalam k buah kelompok tersebut. Pada setiap cluster terdapat titik pusat (centroid) yang merepresentasikan clustertersebut.

K-means ditemukan oleh beberapa orang yaitu Lloyd (1957, 1982), Forgey (1965) , Friedman and Rubin (1967) , and McQueen (1967) ^[1]. Ide dari clustering pertama kali ditemukan oleh Lloyd pada tahun 1957, namun hal tersebut baru dipublikasi pada tahun 1982. Pada tahun 1965, Forgey juga mempublikasi teknik yang sama sehingga terkadang dikenal sebagai Lloyd-Forgy pada beberapa sumber.

Algoritma untuk melakukan K-Means clustering adalah sebagai berikut^[3]:

1. Pilih K buah titik centroid secara acak
2. Kelompokkan data sehingga terbentuk K buah cluster dengan titik centroid dari setiap cluster merupakan titik centroid yang telah dipilih sebelumnya
3. Perbaharui nilai titik centroid
4. Ulangi langkah 2 dan 3 sampai nilai dari titik centroid tidak lagi berubah

Proses pengelompokkan data ke dalam suatu cluster dapat dilakukan dengan cara menghitung jarak terdekat dari suatu data ke sebuah titik centroid. Perhitungan jarak Minkowski dapat digunakan untuk menghitung jarak antar 2 buah data. Rumus untuk menghitung jarak tersebut adalah^[4]:

${\displaystyle d(x_{i},x_{j})=(|x_{i1}-x_{j1}|^{g}+|x_{i2}-x_{j2}|^{g}+...+|x_{ip}-x_{jp}|^{g})^{1/g}}$

Di mana:

g = 1, untuk menghitung jarak Manhattan

g = 2, untuk menghitung jarak Euclidean

g = ∞, untuk menghitung jarak Chebychev

x_i , x_j adalah dua buah data yang akan dihitung jaraknya

p = dimensi dari sebuah data

Pembaharuan suatu titik centroid dapat dilakukan dengan rumus berikut^[4]:

${\displaystyle \mu _{k}={\frac {1}{N_{k}}}\sum _{q=1}^{N_{k}}x_{q}}$

Di mana:

µ_k = titik centroid dari cluster ke-K

N_k = banyaknya data pada cluster ke-K

x_q = data ke-q pada cluster ke-K

Ada beberapa kelebihan pada algoritma k-means, yaitu ^[2]:

1. Mudah untuk diimplementasikan dan dijalankan.
2. Waktu yang dibutuhkan untuk menjalankan pembelajaran ini relatif cepat.
3. Mudah untuk diadaptasi.
4. Umum digunakan.

Algoritma k-means memiliki beberapa kelebihan, namun ada kekurangannya juga. Kekurangan dari algoritma tersebut yaitu :

1. Sebelum algoritma dijalankan, k buah titik diinisialisasi secara random sehingga pengelompokkan data yang dihasilkan dapat berbeda-beda ^[1]. Jika nilai random untuk inisialisasi kurang baik, maka pengelompokkan yang dihasilkan pun menjadi kurang optimal.
2. Dapat terjebak dalam masalah yang disebut curse of dimensionality. Hal ini dapat terjadi jika data pelatihan memiliki dimensi yang sangat tinggi (Contoh jika data pelatihan terdiri dari 2 atribut maka dimensinya adalah 2 dimensi. Namun jika ada 20 atribut, maka akan ada 20 dimensi). Salah satu cara kerja algoritma ini adalah mencari jarak terdekat antara k buah titik dengan titik lainnya. Jika mencari jarak antar titik pada 2 dimensi, masih mudah dilakukan. Namun bagaimana mencari jarak antar titik jika terdapat 20 dimensi. Hal ini akan menjadi sulit.
3. Jika hanya terdapat beberapa titik sampel data, maka cukup mudah untuk menghitung dan mencari titik terdekat dengan k titik yang diinisialisasi secara random. Namun jika terdapat banyak sekali titik data (misalnya satu milyar buah data), maka perhitungan dan pencarian titik terdekat akan membutuhkan waktu yang lama. Proses tersebut dapat dipercepat, namun dibutuhkan struktur data yang lebih rumit seperti kD-Tree atau hashing.

K-means sebagai algoritma clustering memiliki banyak aplikasi. Aplikasi-aplikasi tersebut dapat dikelompokkan sesuai tujuannya.

Pengelompokan untuk pemahaman bertujuan menghasilkan kelompok-kelompok yang terdiri dari objek-objek dengan karakteristik yang serupa, seperti halnya manusia mengelompokkan objek-objek.

• Aplikasi di Bidang Biologi

K-means dapat digunakan untuk mengelompokkan gen berdasarkan polanya^[5]. Hal ini diperlukan untuk menemukan gen yang memiliki fungsi serupa.

• Aplikasi di Bidang Bisnis

K-means dapat digunakan untuk melakukan segementasi pasar. Segementasi pasar adalah pengelompokan pelanggan sesuai karakteristik mereka (misalnya: gaya hidup, kebutuhan). K-means juga dapat digunakan dalam sistem pemberi rekomendasi untuk mengelompokkan objek-objek yang saling terkait.

• Aplikasi di Bidang Temu Kembali Informasi

K-means dapat digunakan untuk mengelompokkan dokumen sehingga memudahkan temu kembali dokumen berdasarkan topiknya.

Pengelompokkan bertujuan untuk mengelompokkan himpunan data yang besar untuk memudahkan analisis data atau pemrosesan data lebih lanjut. Untuk tujuan ini, centroid dari cluster memegang peran lebih berarti.

• Kompresi Data Multimedia

K-means dapat digunakan untuk kompresi data multimedia (citra, audio, video). Setiap objek dalam data (misalnya pixel dari citra) direpresentasikan dengan centroiddari cluster yang memuat objek tersebut. Teknik kompresi ini disebut juga kuantisasi vektor.

• Rangkuman Data

K-means dapat digunakan untuk mengelompokkan data sebelum menerapkan teknik analisis data lainnya seperti regresi, tetangga terdekat, atau PCA. K-means dapat digunakan untuk terlebih dahulu mengelompokkan data ke dalam cluster-cluster. Kemudian teknik analisis data hanya perlu diterapkan pada centroid dari setiap clustersehingga lebih efisien dalam hal penggunaan waktu dan ruang.

Terdapat beberapa algoritma yang merupakan pengembangan/variasi dari algoritma k-means.

• K-means++

Algoritma untuk memilih nilai awal untuk algoritma k-means^[6]. Algoritma ini digunakan untuk mengurangi dampak buruk algoritma k-means yang sangat tergantung dari nilai awalnya.

• K-medoids

Algoritma clustering yang berbasiskan prototype/model dari cluster. K-means menggunakan centroid (rata-rata) sebagai model dari cluster, sedangkan K-medoids menggunakan medoid (median).

• Bisecting K-means

Ide dasarnya adalah menggunakan K-means untuk membagi dua suatu cluster. Awalnya setiap objek tergabung dalam satu cluster. Pada tiap iterasi, pilih satu clusteruntuk dibagi dua menggunakan K-means. Hal ini dilakukan hingga terbentuk K cluster. Algoritma bisecting K-means bekerja lebih cepat dari K-means karena mengurangi jumlah objek yang diperbandingkan pada setiap iterasi. (sumber : wikipedia)

Untuk materi lengkapnya tentang Data Mining bisa di download disini 

Untuk mempermudah pembelajaran klasifikasi menggunakan Algoritma CART. C4.5 dan Clustering K-Means ini bisa kita lakukan dengan cara.

1. Menggunakan Microsoft Excel, dimana beberapa fungsi perhitungan bisa kita sesuaikan dengan Algoritmanya. Berikut Contoh Algoritma dari CART, C4.5 untuk penerapan dalam Klasifikasi, yang bisa Download disni  
2. Kemudian untuk Algoritma K-Means, berikut contoh penerapannya untuk permasalahan Cluster. Download disini 
3. Menggunakan Tools atau Software yang sudah disediakan, yaitu Clementine, kemudian untuk membuat datanya kita bisa menggunakan SPSS. Karena ukurannya yang cukup besar Anda bisa Download di blog atau alamat website yang lain yang sudah cukup banyak tersedia. Berikut beberapa penjelasan penggunaan dari Clementine dan SPSS yang mudah-mudahan bisa membantu Download disini

Demikian penjelasan secara garis besar mengenai Algoritma CART, C4.5 dan KMeans, untuk bisa memahami penerapannya diperlukan ketelitian dan minimal untuk materinya juga dibaca ( masih dalam versi English ).

Terima kasih

Mr.Dicsr