memulai Data kembali..[ - Struktur dari Clasification Data mining -]

Proses analisa data dengan menggunakan perangkat lunak untuk menemukan
suatu pola dan aturan dalam himpunan data di sebut sebagai data Mining yang mampu
menganalisa data yang besar menjadi informasi berupa pola yang mempunyai arti bagi
pendukung keputusan. Salah satu teknik yang ada pada data mining adalah classification
yaitu proses untuk menemukan model atau fungsi yang menjelaskan atau membedakan
konsep atau kelas data, dengan tujuan untuk dapat memperkirakan kelas dari suatu objekyang labelnya tidak diketahui.
Suatu perangkat lunak yang mengimplementasikan salah satu metode dalam
classification yaitu decision tree dengan algoritma C4.5 kemudian menganalisa nilai
prosentase kebenaran tree dan hasil klasifikasi yang dibuat serta membandingkankannya
dengan menggunakan tool WEKA J48 yang membantu. Alat bantu yang digunakan untuk implementasi adalah Microsoft Visual Basic dan DBMS (Database Management
System). Hasil pengujian menunjukkan bahwa tree yang dihasilkan dari perangkat lunak
yang dibuat dengan metode decition tree dengan algoritma C4.5 mempunyai prosentase
kebenaran tree antara 66.67% sampai 100%. Besar prosentase kebenaran tree tersebut
sangat dipengaruhi oleh data training yang digunakan untuk membangun model tree
tersebut.

Secara umum ada dua jenis task pada data mining yaitu :

- Metode Predictive
Menggunakan beberapa variabel untuk memprediksikan variabel lain yang tidak
diketahui jenis atau nilainya.

- Metode Descriptive
Mencari suatu pola yang mudah dipahami oleh manusia yang mendeskripsikan
data.Yang akan digunakan dalam tugas akhir ini adalah metode predictive, karena
metode classification yang digunakan pada tugas akhir ini termasuk dalam metode
predictive.

Fungsi dari data Mining

Data Mining dapat diklasifikasikan dengan fungsi yang dilakukan atau berdasar kelas aplikasi yang digunakan :

1. Association

Tipe pola yang penting yang dapat ditemukan dari basis data adalah sebuah aturan. Association Rule mempunyai bentuk LHS  RHS dengan interpretasi jika setiap item dalam LHS ( Left Hand Side) dibeli maka item dalam RHS (RightHand Side) juga dibeli.

2. Pola Sequantial

Sequantial Patern adalah sequence dari intemset yang dibeli oleh pembeli yang sama.

3. Bayesian Network

4. Tipe dari rule yang dibahas menggambarkan asosiasi dalam basis data dan tidak implisit relasi kausal. Bayesian Network adalah model grafis yang dapat merepresentasikan relasi kausal.

5. Classification dan Regression

Classification dan regression rule adalah rule umum yang melibatkan atribut numerik dan kategori.

6. Decission tree

Classification dan dan regression rule sering direpresentasikan dalam bentuk tree. Jika sebuah tree merepresentasaikan koleksi classification tree sering disebut decission tree. Decission Tree dibangun secara greedy top-down.

7. Clustering

Tujuan clustering untuk partisi sebuah koleksi record dalam group yang disebut cluster dimana record sejenis itu terdapat dalam cluster yang sama dan record yang tidak mirip terdapat dalam cluster yang beda. Kemiripan biasanya berdasar dalam fungsi jarak.

8.Pencarian Kemiripan dalam sequence

Kemiripan queri dalam sequence artinya kita melakukan queri secara tepat yang dan juga mendapatkan hasil yang agak berbeda dari hasil queri yang tepat. Sebuah sequence adalah rangkaian terurut dari angka. Pengukuran perbedaan diantara dua sequence dapat dilakukan dengan menghitung jarak Eucladian diantara sequence.

Metode – Metode Pada Data mining Classification

Metode-metode yang ada pada Data Mining Classification antara lain adalah :

1. Decision Tree

Merupakan salah satu fungsional dari Data Mining yang menggunakan representasi tree untuk menentukan aturan-aturan klasifikasi. Ada dua tipe yaitu :

• Classification tree

Memberi label dan memasukan record-record ke dalam kelas-kelas yang telah disediakan

• Regression tree

Membuat estimasi nilai dari sebuah variabel target yang berdasar pada nilai numerik.

Yang akan digunakan dalam penelitian ini adalah classification tree, karena penelitian ini hanya mengklasifikasikan data-data ke dalam kelas-kelas yang telah tersedia. Data mining classification dengan decission tree akan dibahas lebih detil.

2. Neural Networks

Neural networks atau sering disebut dengan jaringan syaraf merupakan salah satu representasi buatan dari otak manusia yang selalu mencoba untuk mensimulasikan proses pembelajaran pada otak manusia tersebut.

Komponen-komponen pada jaringan syaraf terdiri dari 8 :

1. Neuron. Neuron-neuron akan mentranformasikan informasi yang diterima melalui sambungan keluarnya menuju ke neuron-neuron yang lain.

2. Bobot, adalah hubungan yang ada pada jaringan syaraf. Informasi-informasi yang ditransformasikan melalui neuron disimpan pada suatu nilai tertentu pada bobot tertentu.

Informasi (disebut dengan: input) akan dikirim ke neuron dengan bobot kedatangan tertentu. Input ini akan diproses oleh suatu fungsi perambatan yang akan menjumlahkan nilai-nilai semua bobot yang datang. Hasil penjumlahan ini kemudian akan dibandingkan dengan suatu nilai ambang (threshold) tertentu melalui fungsi aktivasi setiap neuron. Apabila, input tersebut melewati suatu nilai ambang tertentu, maka neuron tersebut akan diaktifkan, tapi kalau tidak, maka neuron tersebut tidak akan diaktifkan. Apabila neuron tersebut diaktifkan, maka neuron tersebut akan mengirimkan output melalui bobot-bobot outputnya ke semua neuron yang berhubungan dengannya. Demikian seterusnya.

1. k-Nearest Neighbor Classifiers

Nearest Neighbor Classifiers berdasarkan pada proses pembelajaran menggunakan analogi / learning by analogi [1]. Training sampelnya dideskripsikan dalam bentuk atribut numerik n-dimensi. Tiap sampel mewakili sebuah titik pada ruang n-dimensi. Dengan cara ini, semua training sampel disimpan pada pola ruang n-dimensi. Ketika diberikan “unknown” sampel, k-nearest neighbor classifier mencari pola ruang K training sampel yang paling dekat “unknown” sampel tersebut. K training sampel ini adalah k nearest neighbor dari unknown sampel.

“Closeness: dinyatakan dengan Euclidean Distance, dimana Euclidean Distance antara 2 titik, X = (x1, x2, ….., xn) dan Y = (y1,y2,….,yn) adalah d(X,Y) =

Unknown sampel ditetapkan dengan class yang paling umum diantara k nearest neighborsnya. Ketika k = 1, unknown sampel ditetapkan dengan class dari training sampel yang paling dekat dengan pola ruang-nya. Nearest Neighbor menyimpan semua training sampel dan tidak membangun classifier sampai sampel baru (unlabeled) perlu diklasifikasikan, sehingga Nearest Neighbor Classifiers sering disebut dengan instance-
based atau lazy learners. Lazy learners dapat menyebabkan biaya penghitungan (computational cost) nya mahal ketika jumlah dari neighbor yang potensial (yakni, training sampel yang disimpan) dengan unlabeled sampel yang akan dibandingkan sangat besar. Oleh karena itu, diperlukan teknik pengindeksan yang efisien. Kenyataannya, metode lazy learning lebih cepat pada saat training daripada metode eager, tetapi lebih lambat pada saat classification karena semua penghitungan ditunda sampai pada saat itu.

1. Algoritma Genetika

Algoritma genetika didasarkan pada analogi pada evolusi biologi. Pada algoritma ini, teknik pencarian dilakukan sekaligus atas sejumlah solusi yang mungkin dikenal dengan istilah populasi 8. Individu yang terdapat dalam satu populasi disebut dengan istilah kromosom. Kromosom ini merupakan suatu solusi yang masih berbentuk simbol. Populasi awal dibangun secara acak, sedangkan populasi berikutnya merupakan hasil evolusi kromosom-kromosom melalui iterasi yang disebut dengan istilah generasi. Pada setiap generasi, kromosom akan melalui proes evaluasi dengan menggunakan alat ukur yang disebut dengan fungsi fitness. Nilai fitness dari suatu kromosom akan menunjukkan kualitas kromosom dalam populasi tersbut. Generasi berikutnya dikenal dengan istilah anak (offspring) terbentuk dari gabungan 2 kromosom generasi sekarang yang bertindak sebagai induk (parent) dengan menggunakan operator penyilangan (crossover). Selain operator penyilangan, suatu kromosom dapat juga dimodifikasi dengan menggunakan operator mutasi. Populasi generasi yag baru dibentuk dengan cara menyeleksi nilai fitness dari kromosom induk (parent) dan nilai fitness dari kromosom anak (offspring), serta menolak kromosom-kromosom yang lainnya sehingga ukuran populasi (jumlah kromosom dalam populasi) konstan. Setelah melalui beberapa generasi, maka algoritma ini akan konvergen ke kromosom terbaik.

Secara umum pembelajaran genetik dimulai sebagai berikut :

Sebuah populasi awal dibuat yang terdiri dari aturan-aturan yang digenarate secara acak. Tiap rule dapat diwakilkan dengan bit-bit string. Contohnya, sampel-sampel pada training set yang diberikan digambarkan dengan dua atribut boolean, A1 dan A2, dan ada 2 class, C1 dan C2. Aturan “IF A1 AND NOT A2 THEN C2” dapat dikodekan dengan bit string “100”, dimana dua leftmost bit merepresentasikan atribut A1 dan A2, dan rightmost bit merepresentasikan class. Untuk aturan “IF NOT A1 AND NOT A2

THEN C1 dapat dikodekan dengan “001”. Jika atribut mempunyai K nilai, dimana k > 2, maka k bit digunakan untuk mengkodekan nilai-nilai atribut. Class-class dapat dikodekan dengan cara yang sama.

2.4 Decision tree

Decision tree adalah flow-chart seperti struktur tree, dimana tiap internal node menunjukkan sebuah test pada sebuah atribut, tiap cabang menunjukkan hasil dari test, dan leaf node menunjukkan class-class atau class distribution [6].

2.4.1 Algoritma ID3 dan Algoritma C4.5

Sebelum membahas algoritma C4.5 perlu dijelaskan terlebih dahulu algoritma ID3 karena C4.5 adalah ekstensi dari algoritma decision-tree ID3. Algoritma ID3/C4.5 ini secara rekursif membuat sebuah decision tree berdasarkan training data yang telah disiapkan. Algoritma ini mempunyai inputan berupa training samples dan samples. Training samples berupa data contoh yang akan digunakan untuk membangun sebuah tree yang telah diuji kebenaranya. Sedangkan samples merupakan field-field data yang nantinya akan kita gunakan sebagai parameter dalam melakukan klasifikasi data. Berikut adalah algoritma dasar dari ID3 dan C4.5

• Algoritma ID3 [6]

Input : Training samples, samples

Output : Decision tree

Method :

1. Create node N;

2. If samples are all of the same class, C then

3. Return N as a leaf node labeled with the class C;

4. if atribute-list is empty then

5. Return N as a leaf node labeled with the most common class in samples; // majority voting

6. select test-atribute, atribute among atribute-list with the highest information gain;

7. label node N with test-atribute;

8. for each known value a_i of test-atribute // partition the samples

9. grow a branch from node N for the condition test-atribute = a_i;

10. let s_i be the set of samples in samples for which test-atribute = a_i; // a partition

11. if s_i is empty then

12. attach a leaf labeled with the ,most common class in samples;

13. else attach the node returned by Generate_decision_tree(s_i, attriute-list-test-atribute);

• Algoritma C4.5 [15]

1. Build the decision tree form the training set (conventional ID3).

2. Convert the resulting tree into an equivalent set of rules. The number of rules is equivalent to the number of possible paths from the root to a leaf node.

3. Prune (generalize) each rule by removing preconditions that increase classification accuracy.

4. Sort pruned rules by their accuracy, and use them in this order when classifying future test examples.

2.4.2 Information Gain

Information gain adalah salah satu atribute selection measure yang digunakan untuk memilih test atribute tiap node pada tree. Atribut dengan information gain tertinggi dipilih sebagai test atribut dari suatu node [6]. Ada 2 kasus berbeda pada saat penghitungan Information Gain, pertama untuk kasus penghitungan atribut tanpa missing value dan kedua, penghitungan atribut dengan missing value.

• Penghitungan Information Gain tanpa missing value

Misalkan S berisi s data samples. Anggap atribut untuk class memiliki m nilai yang berbeda, C_i (untuk i = 1, …,I). anggap s_i menjadi jumlah samples S pada class C_i. Maka besar information-nya dapat dihitung dengan :

I ( s₁, s₂,…,s_m ) = -

Dimana p_i = adalah probabilitas dari sample yang mempunyai class C_i.

Misalkan atribut A mempunyai v nilai yang berbeda, {a₁, a₂,...,a_v}. Atribut A dapat digunakan untuk mempartisi S menjadi v subset, {S₁, S₂,...,S_v}, dimana S_j berisi samples pada S yang mempunyai nilai a_j dari A. Jika A terpilih menjadi test atribut (yaitu, best atribut untuk splitting), maka subset-subset akan berhubungan dengan pertumbuhan node-node cabang yang berisi S. Anggap s_ij sebagai jumlah samples class Ci pada subset S_j. Entropy, atau nilai information dari subset A adalah :

E(A) = I ( s₁, s₂,…,s_m )

adalah bobot dari subset jth dan jumlah samples pada subset (yang mempunyai nilai a_j dari A) dibagi dengan jumlah total samples pada S. Untuk subset S_j,

I ( s_1j, s_2j,…,s_mj) = -

Dimana p_ij = adalah probabilitas sample S_j yang mempunyai class Ci.

Maka nilai information gain atribut A pada subset S adalah

Gain(A) = I ( s₁, s₂,…,s_m ) – E(A)

Sebagai contoh : kita ingin mencari apakah pegolf akan masuk class play atau don’t play berdasarkan data berikut:

Tabel 2.1. Contoh data play tennis

Outlook	Temperature	Humidity	Windy	Play
Sunny	85	85	False	Don’t Play
Sunny	80	90	True	Don’t Play
Overcast	83	78	False	Play
Rain	70	96	False	Play
Rain	68	80	False	Play
Rain	65	70	True	Don’t Play
Overcast	64	65	True	Play
Sunny	72	95	False	Don’t Play
Sunny	69	70	False	Play
Rain	75	80	False	Play
Sunny	75	70	True	Play
Overcast	72	90	True	Play
Overcast	81	75	False	Play
Rain	71	80	True	Don’t Play

Dari data-data pada tabel kita akan mencoba untuk membangun sebuah classifier yang berdasarkan atribut Outlook, Temperature, Humidity dan Windy. Disana ada dua kelas yaitu Play dan Don’t play. Dan ada 14 examples, 5 examples menyatakan Don’t Play dan 9 examples menyatakan Play. Maka,

I (s₁,s₂) = I (9,5) = - log₂ - log₂= 0,940

Entropy untuk atribut Outlook adalah :

E( Outlook ) = * I (2,3) + * I (4,0) + * I (3,2)

= 0,694

Dengan nilai Gain( Outlook) yaitu:

Gain ( Outlook ) = I ( s₁, s₂ ) – E(Outlook)

= 0,94 – 0,694

= 0,246

dengan menggunakan cara yang sama, Gain dari semua atribut dapat dicari.

Gain ( Outlook) = 0,246

Gain ( Humidity ) = 0,151

Gain ( Windy ) = 0,048

Gain ( Temperature) = 0,029

Setelah nilai information gain pada semua atribut dihitung, maka atribut yang mempunyai nilai information gain terbesar yang dipilih menjadi test atribut.

• Penghitungan Information Gain dengan missing value

Untuk atribut dengan missing value penghitungan information gain-nya diselesaikan dengan Gain Ratio. Sebelum menghitung gain ratio terlebih dahulu dihitung I ( s₁, s₂,…,s_m ) dan E(A).

I ( s₁, s₂,…,s_m ) = -

E(A) = I ( s₁, s₂,…,s_m )

Dimana penghitungan I ( s₁, s₂,…,s_m ) dan E(A) hanya dilakukan pada atribut yang ada nilainya.

Kemudian untuk mencari gain dari atribut A dihitung dengan rumus sebagai berikut :

Gain (A) = Prob S yang diketahui * E(A)

Dimana,

A = atribut dengan missing value yang sedang dicari nilai gain-nya,

S = jumlah samples pada subset A yang diketahui nilainya.

Sedangkan nilai split pada atribut A dinyatakan dengan :

Split(A) = -u * log₂ u -

Dimana,

u adalah prob samples pada atribut A yang merupakan missing values.

p_j = adalah probabilitas sample S_j yang diketahui nilainya.

Nilai Gain Ratio pada atribut A :

Gain Ratio(A) = Gain(A) / Split(A)

Sebagai contoh : kita ingin mencari apakah pegolf akan masuk class play atau don’t play berdasarkan data berikut:

Tabel 2.2. data play tennis dengan missing value

Outlook	Temp	Humidity	Windy	Class
sunny	75	70	yes	play
sunny	80	90	yes	don’t play
sunny	85	85	no	don’t play
sunny	72	95	no	don’t play
sunny	69	70	no	play
?	72	90	yes	play
cloudy	83	78	no	play
cloudy	64	65	yes	play
cloudy	81	75	no	play
rain	71	80	yes	don’t play
rain	65	70	yes	don’t play
rain	75	80	no	play
rain	68	80	no	play
rain	70	96	no	play

Sedangkan nilai split pada atribut A dinyatakan dengan :

Split(A) = -u * log₂ u -

Dimana,

u adalah prob samples pada atribut A yang merupakan missing values.

p_j = adalah probabilitas sample S_j yang diketahui nilainya.

Nilai Gain Ratio pada atribut A :

Gain Ratio(A) = Gain(A) / Split(A)

Sebagai contoh : kita ingin mencari apakah pegolf akan masuk class play atau don’t play berdasarkan data berikut:

Tabel 2.2. data play tennis dengan missing value

Outlook	Temp	Humidity	Windy	Class
sunny	75	70	yes	play
sunny	80	90	yes	don’t play
sunny	85	85	no	don’t play
sunny	72	95	no	don’t play
sunny	69	70	no	play
?	72	90	yes	play
cloudy	83	78	no	play
cloudy	64	65	yes	play
cloudy	81	75	no	play
rain	71	80	yes	don’t play
rain	65	70	yes	don’t play
rain	75	80	no	play
rain	68	80	no	play
rain	70	96	no	play

Pertama, kita menghitung frekuensi pada OUTLOOK sebagai berikut :

	Play	Don’t play	Total
Sunny	2	3	5
Cloudy	3	0	3
Rain	3	2	5
Total	8	5	13

Untuk data pada tabel 2.2 maka penghitungan information gainnya adalah sebagai berikut :

I (s₁,s₂) = I (8,5) = - log₂ - log₂= 0.961

I(outlook) = * (- * log₂-* log₂) + * (- * log₂-* log₂) + *

(-* log₂-* log₂) = 0.747

Gain (Outlook) = * (0.961-0.747) = 0.199

Split = -*log₂-*log₂-*log₂-*log₂= 1.809

Gain ratio = = 0.110

Setelah semua Gain diketahui maka dapat ditentukan atribut mana yang layak menjadi root. Atribut yang layak adalah atribut yang mempunyai Gain terbesar

2.4.3 Penanganan Atribut Kontinyu

Algoritma C4.5 juga menangani masalah atribut kontinyu. Salah satu cara adalah dengan Entropy-Based Discretization yang melibatkan penghitungan class entropy.

Misalkan T membagi S example menjadi subset S1 dan S2. Umpakan ada k class C1, C2, …,Ck. Misal P(Ci, Sj) menjadi perbandingan dari example pada Sj yang mempunyai class i.

Maka class entropy dari subset Sj didefinisikan dengan :

Ent(S) = - P(Ci, S) log(P(Ci, S))

Dan class information entropy E(A, T;S)

E(A, T;S) = Ent(S1) + Ent(S2)

Dimana Ent(Sj) = class entropy dari subset Sj

Sj = subset dari S

Ci = class i

P(Ci, Sj) = perbandingan instance dari Sj yang berada pada class Ci

E(A, TA;S) = class information entropy partisi dengan cut point T_A di A

A = atribut

|Sk| = jumlah instance di Sk

Cut point yang terbaik adalah yang memberikan class information entropy yang paling kecil diantara semua kandidat cut point.

2.4.4 Pruning Tree

Pruning tree adalah melakukan suatu kegiatan untuk mengganti suatu subtree dengan suatu leaf. Penggantian dilakukan jika error rate pada subtree lebih besar jika dibandingkan dengan single leaf.

Pada C4.5 perkiraan error untuk satu node dihitung dengan :

e =

Jika c = 25% (default untuk C4.5) maka z = 0,69 (dari distribusi normal)

f : error pada data training

N : jumlah instance pada satu leaf

Contoh :

Gambar : Tree Pruning