Apa itu teori tree ??

TEORI TREE DAN PENERAPANNYA

Dalam matematika, dan lebih khusus dalam teori graf, pohon merupakan graf tak berarah di mana setiap dua simpul dihubungkan dengan tepat satu jalan sederhana. Dengan kata lain, setiap grafik terhubung tanpa siklus sederhana adalah pohon. Hutan adalah suatu kesatuan menguraikan pohon.

Berbagai macam struktur data disebut sebagai pohon dalam ilmu komputer yang setara sebagai grafik diarahkan dengan pohon dalam teori graf, meskipun struktur data tersebut umumnya berakar pohon, sehingga pada kenyataannya diarahkan grafik, dan mungkin juga memiliki memesan tambahan cabang.

           

Pohon (tree) merupakan salah satu bentuk khusus dari struktur suatu graf. Misalkan A merupakan sebuah himpunan berhingga simpul (vertex) pada suatu graf G yang terhubung. Untuk setiap pasangan simpul di A dapat ditentukan suatu lintasan yang menghubungkan pasangan simpul tersebut. Suatu graf terhubung yang setiap pasangan simpulnya hanya dapat dihubungkan oleh suatu lintasan tertentu, maka graf tersebut dinamakan pohon (tree). Dengan kata lain, pohon (tree) merupakan graf tak-berarah yang terhubung dan tidak memiliki sirkuit. 

Berikut adalah beberapa sifat pohon : 

• Misalkan G merupakan suatu graf dengan n buah simpul dan tepat n – 1 buah sisi. Jika G tidak mempunyai sirkuit maka G merupakan pohon. 

• Suatu pohon dengan n buah simpul mempunyai n – 1 buah sisi. 

• Setiap pasang simpul di dalam suatu pohon terhubung dengan lintasan tunggal. 

• Misalkan G adalah graf sederhana dengan jumlah simpul n, jika G tidak mengandung sirkuit maka penambahan satu sisi pada graf hanya akan membuat satu sirkuit. 

 Pohon keputusan dibangun untuk membuat aturan klasifikasi dari beberapa atribut yang diasosiasikan ke dua kelas atau lebih melalui perhitungan entropy dan information gain, serta perhitungan seleksi atribut lainnya.

    

     Sebuah pohon keputusan dg konsep membeli komputer, mengindikasikan apakah pelanggan di AllElectronics membeli komputer atau tidak. Setiap node internal mewakili pengujian pada atribut . Setiap node daun (terminal) mewakili kelas (buys computer = yes atau buys computer = no)

Dari pohon keputusan di atas maka didapatkan aturan klasifikasi sebagai berikut :
R1: IF age = youth AND student = no THEN buys computer = no
R2: IF age = youth AND student = yes THEN buys computer = yes
R3: IF age = middle aged THEN buys computer = yes
R4: IF age = senior AND credit rating = excellent THEN buys computer = yes
R5: IF age = senior AND credit rating = fair THEN buys computer = no

Pohon Berakar 

       Pada suatu pohon, yang sisi-sisinya diberi arah sehingga menyerupai graf berarah, maka simpul yang terhubung dengan semua simpul pada pohon tersebut dinamakan akar. Suatu pohon yang satu buah simpulnya diperlakukan sebagai akar maka pohon tersebut dinamakan pohon berakar (rooted tree). Simpul yang berlaku sebagai akar mempunyai derajat masuk sama dengan nol. Sementara itu, simpul yang lain pada pohon itu memiliki derajat masuk sama dengan satu. Pada suatu pohon berakar, Simpul yang memiliki derajat keluar sama dengan nol dinamakan daun. 

1. Anak (child atau children) dan Orangtua (parent) b, c, dan d adalah anak-anak simpul a, a adalah orangtua dari anak-anak itu 
2. Lintasan (path) Lintasan dari a ke h adalah a, b, e, h. dengan pnjang lintasannya adalah 3. f adalah saudara kandung e, tetapi, g bukan saudara kandung e, karena orangtua mereka berbeda. 
3. Subtree 
4. Derajat (degree) 

Derajat sebuah simpul adalah jumlah anak pada simpul tersebut. 
Contoh : 
Simpul yang berderajat 0 adalah simpul c, f, h, I, j, l, dan m. 
Simpul yang berderajat 1 adalah simpul d dan g. 
Simpul yang berderajat 2 adalah simpul b dan k. 
Simpul yang berderajat 3 adalah simpul a dan e. abkgjfcdmlieh abkgjfcdmlieh 

       Pohon keputusan merupakan himpunan aturan IF…THEN. Setiap path dalam tree dihubungkan dengan sebuah aturan, di mana premis terdiri atas sekumpulan node-node yang ditemui, dan kesimpulan dari aturam terdiri atas kelas yang terhubung dengan leaf dari path.

Gambar: Konsep Dasar Pohon Keputusan

Bagian awal dari pohon keputusan ini adalah titik akar (root), sedangkan setiap cabang dari pohon keputusan merupakan pembagian berdasarkan hasil uji, dan titik akhir (leaf) merupakan pembagian kelas yang dihasilkan.

Pohon keputusan mempunyai 3 tipe simpul yaitu:

1. Simpul akar, dimana tidak memiliki cabang yang masuk dan memiliki cabang lebih dari satu, terkadang tidak memiliki cabang sama sekali. Simpul ini biasanya berupa atribut yang paling memiliki pengaruh terbesar pada suatu kelas tertentu.
2. Simpul internal, dimana hanya memiliki 1 cabang yang masuk, dan memiliki lebih dari 1 cabang yang keluar.
3. Simpul daun, atau simpul akhir dimana hanya memiliki 1 cabang yang masuk, dan tidak memiliki cabang sama sekali dan menandai bahwa simpul tersebut merupakan label kelas.

Tahap awal dilakukan pengujian simpul akar, jika pada pengujian simpul akar menghasilkan sesuatu maka proses pengujian juga dilakukan pada setiap cabang berdasarkan hasil dari pengujian. Hal ini berlaku juga untuk simpul internal dimana suatu kondisi pengujian baru akan diterapkan pada simpul daun. Pada umumnya proses dari sistem pohon keputusan adalah mengadopsi strategi pencarian top-down untuk solusi ruang pencariannya. Pada proses mengklasifikasikan sampel yang tidak diketahui, nilai atribut akan diuji pada pohon keputusan dengan cara melacak jalur dari titik akar sampai titik akhir, kemudian akan diprediksikan kelas yang ditempati sampel baru tersebut.
Pohon keputusan banyak digunakan dalam proses data mining karena memiliki beberapa kelebihan, yaitu:
1. Tidak memerlukan biaya yang mahal saat membangun algoritma.
2. Mudah untuk diinterpetasikan.
3. Mudah mengintegrasikan dengan sistem basis data.
4. Memiliki nilai ketelitian yang lebih baik.
5. Dapat menemukan hubungan tak terduga dan suatu data.
6. Dapat menggunakan data pasti/mutlak atau data kontinu.
7. Mengakomodasi data yang hilang.

Berikut contoh penerapan pohon keputusan studi kasus mengenai uji kelayakan kredit:

Gambar: Contoh Pohon Keputusan dalam Identifikasi Kelayakan Kredit

Dari pohon tersebut diketahui bahwa pemohon yang layak menerima kredit adalah pemohon yang penghasilannya sama dengan 2- 3x angsuran dan kepemilikan rumahnya adalah milik sendiri.

Kesimpulan

Penggunaan teori graf dan pohon pada suatu kegiatan pengambilan keputusan memang berguna untuk beberapa kondisi. Seperti yang sudah dijelaskan sebelumnya bahwa teori pohon ini mempunyai beberapa keuntungan diantara lainnya adalah mudah untuk diinterpetasikan, mudah mengintegrasikan dengan sistem basis data, memiliki nilai ketelitian yang lebih baik, dapat menemukan hubungan tak terduga dan suatu data, dan keuntungan lainnya.

Dengan menyajikan pohon keputusan untuk memilih sesuatu, kita dapat tahu skema langkah yang harus diambil dan yang tidak perlu diambil sehingga keputusan yang ktia ambil tidak asal melainkan berdasarkan analisis yang sudah kita lakukan dan kita sajikan dalam pohon keputusan. Maka itu pentingnya kita untuk mempelajari teori pohon ini.