Kamis, 03 Januari 2013

Ringkasan Materi Mata Kuliah Algoritma dan Struktur Data



Tipe Data


Dalam algoritma, kita harus bias menentukan tipe-tipe data yang sesuai digunakan dalam penyelesaian masalah. Sehingga computer dapat mengolah dan mendapatkan hasil yang sesuai menurut kebutuhan data.
Ada beberapa tipe data yang harus kita ketahui antara lain :
1. Tipe data Char dan String
Ini merupakan tipe data dasar, tipe data ini didefinisikan pada deklarsi var dibagian algoritma/program.

Var Nama : String
Nilai : Char

Keterangan :

* Nama merupakan sebuah variabel didefinisikan sebagai variabel bertipe string, maksudnya pada variabel tersebut digunakan untuk menerima masukan sebuah nama yang terdiri dari sekumpulan huruf, dapat berupa huruf besar, kecil, atau campuran kedua-duanya.
* Nilai, didefinisikan sebagai variabel yang bertipe data char, maksudnya variabel tersebut hanya dapat digunakan untuk memasukkan sebuah huruf dari huruf besar, seperti A, B, C,.. atau huruf kecil, a, b, c, ….

2. Tipe data Boolean
Tipe data ini digunakan untuk pengambilan keputusan dalam operasi logika. Terdiri dari true disimbolkan ‘T’ dan False yang disimbolkan ‘F’. Ketika kita ingin mendapatklan hasil yang valid/pasti, kita menggunakan tipe data boolean untuk memperoleh keputusan dalam suatu penyelesaian yang pasti.

3. Tipe Data Integer
Merupakan tipe data bilangan bulat.Contoh:
Byte 0…255 1 byte
Word 0…65.555 1 byte
Integer -32.768 s.d 32.767 2 byte
Long Integer -2.147.483.648 4 byte
4. Tipe Data Real
Merupakan tipe data bilangan pecahan seperti real, single, double, comp, extend.

5. Tipe Data Subrange
Merupakan tipe data bilangan yang punya jangkauan nilai tertentu sesuai dengan definisi pada pemrogram.
Example:
Type Variabel=Nilai_awal…Nilai_akhir

6. Tipe Data Enumerasi
Merupakan tipe data yang memiliki elemen-elemen tertentu yang disebut satu/satu dari bernilai konstanta integer sesuai dengan urutannya. Pada tipe data ini elemen masukan diwakili oleh suatu nama variable yang ditlis di dalam kurung.
Example :
Indeks_Hari = (Nol, Minggu, Senin, Selasa, Rabu, Kamis, Jumat, Sabtu)

7. Tipe Data Array (Larik)
Tipe data ini sudah terstruktur dengan baik, walaupun masih sederhana. Tipe data ini menampung sejumlah data dengan tipe data sama (homogen) dalam sebuah variabel.

* Cara mendefinisikan tipe data array

Berdimensi satu

Var

Nama_Variabel_Array[1...N]of tipe_data

1 Nomor Indeks

* Berdimensi dua

Var

Nama_Variabel_Array=Array[1...N,1...M]of tipe_data

2 buah Nomor Indeks

8. Tipe Data Record
Tipe data komposit yang sudah terstruktur denagn baik. Tipe data ini digunakan untuk menampung data suatu obyek. Datanya berupa campuran dari tipe data seperti string, numerik, char, boolean, atau tipe data lainnya. Tipe data ini merupakan struktur dasar dari suatu sistem database.

9. Tipe Data Array Record
Tipe data array yang dibangun dari tipe data record.

10. Tipe Data Citra
Berisi grafik/gambar yang banyak digunakan pada aplikasi video.

Example :
Grafik perkembangan jumlah penduduk.

Perbedaan variabel dengan konstanta
Variabel adalah peubah, suatu nama lokasi yang diinginkan untuk menampung tipe data tertentu yang akan diolah komputer. Sedangkan konstanta adalah suatu harga yang diberikan pada sebuah variabel dengan harga/nilai tidak berubah/selalu tetap.



Decision tree


Decision tree merupakan salah satu metode klasifikasi yang menggunakan representasi struktur pohon (tree) dimana setiap node merepresentasikan atribut, cabang nya 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 populer 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 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.

  1. Algoritma C4.5
    Algoritma C4.5 adalah salah satu metode untuk membuat decision tree berdasarkan training data yang telah disediakan. C45 merupakan pengembangan dari ID3. Beberapa pengembangan yang dilakukan pada C45 adalah sebagai antara lain bisa mengatasi missing value, bisa mengatasi data kontinu, dan pruning. Berikut ini algoritma dasar dari C4.5:
    1. Membangun decision tree dari training set
      Nama Proses generate_decision_tree
      Input training_samples, samples
      Output decision_tree
      Logika proses Create a node N as a root;
      If samples are all of the same class, C then return N as a leaf node labeled with the class C;
      If attribute-list is empty then return N as a leaf node labeled with the most common class in samples; //majority voting
      Select test-attribute, the attribute among attribute-list with the highest information gain;
      Label node N with test-attribute;
      For each known value ai of test-attribute //partition the samples grow a branch from node N for the condition test-attribute = ai
      Let si be the set of samples in i samples for which test-attribute ai // a partition
      If si is empty then attach a leaf labeled with the most common class in samples;
      Else attach the node returned by Generate_decision_tree(si, attribute-list-test-attribute);

    2. Melakukan pruning untuk menyederhanakan tree.
    3. Mengubah tree yang dihasilkan dalam beberapa rule. Jumlah rule sama dengan jumlah path yang mungkin dapat dibangun dari root sampai leaf node.

  2. Tree Pruning
    Tree Pruning dilakukan untuk menyederhanakan tree sehingga akurasi dapat bertambah. Pruning ada dua pendekatan, yaitu :
    1. Pre-pruning, yaitu menghentikan 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 diantara subset sampel.
    2. Post-pruning, yaitu menyederhanakan 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.

  3. WEKA dan J48
    J48 adalah salah satu kelas di paket classifier pada sistem weka yang mengimplementasikan algoritma C45. Weka adalah program mesin belajar open source dalam java. Weka mengorganisasi kelas-kelas ke dalam paket-paket dan setiap kelas di paket dapat mereferensi kelas lain di paket lain. Paket classifiers berisi implementasi dari hampir semua algoritma untuk klasifikasi dan prediksi. Kelas yang paling penting di paket ini adalah Classifier, yang mendeklarasikan struktur umum dari skema klasifikasi dan prediksi. Kelas ini memiliki dua metoda, yaitu buildClassifier dan classifyInstance, yang harus diimplementasikan oleh kelas-kelas yang menginduk ke kelas ini. Semua kelas yang mengimplementasikan algoritma klasifikasi menginduk ke kelas Classifier, termasuk kelas J48. J48, yang menangani himpunan data dalam format ARFF, tidak mengandung kode untuk mengkonstruksi pohon keputusan. Kelas ini mereferensi kelas-kelas lain, kebanyakan di paket weka.classifiers.j48, yang mengerjakan semua proses konstruksi pohon.

  4. Ekstraksi Rule dari Decision tree
    Pengetahuan yang diperoleh dari decission tree dapat direpresentasikan dalam bentuk klasifikasi IF-THEN rules. Nilai suatu atribut akan menjadi bagian anticendent (bagian IF), sedang daun (leaf) dari sebuah decission tree akan menjadi bagian consequent (THEN). Aturan seperti ini akan menjadi sangat membantu manusia dalam memahami model klasifikasi terutama jika ukuran decission tree terlalu besar .

  5. Small disjunct
    Small disjunct adalah aturan yang mencakup data training yang jumlahnya sedikit. Dengan kata lain aturan hanya diperoleh dari data yang jumlahnya sedikit sehingga seringkali menyebabkan error dalam proses klasifikasi. Small disjunct ini juga merupakan problem yang dilematis. Dalam beberapa kasus tentang small disjunct menunjukkan bahwa ketika small disjunct dihilangkan atau tidak dihilangkan bisa menyebakan pengaruh yang negatif dalam model klasifikasi yang dibuat. Ketika small disjunct ini dihilangkan masalah yang timbul adalah berkurangnya akurasi rule yang dihasilkan oleh large disjunct. Namun, ketika tidak dihilangkan sering menyebabkan misclasification pada rule yang diperoleh dari small disjunct itu sendiri.

    Berbagai cara digunakan untuk mengatasi problem small disjunct ini. Diantaranya adalah memperbaiki algoritma pruning pada decesion tree yaitu dengan tidak melakukan pruning pada semua small disjunct. Hanya beberapa small disjunct yang sering menyebabkan misclasification yang di-prunning. Cara yang lain adalah melakukan perbaikan pada pemilihan data sample (data training), sehingga dari sejak

    awal sistem sudah berusaha meminimalkan terbentuknya small disjunct. Berbeda dengan dua cara yang sebelumnya cara yang ketiga menggunakan pendekatan lain. Yaitu bagaimana memanfaatkan small disjunct dari decision tree yang terbentuk dari proses pembelajaran (training) sehingga bisa menghasilkan clasifier yang tetap akurat atau bahkan lebih baik

Tidak ada komentar:

Posting Komentar