06 October 2011


1. Pendahuluan
Decision Tree (DT) adalah sebuah struktur data pohon (tree) yang mampu mengambil kesimpulan dari permasalahan yang didefinisikan di root node melalui sejumlah decision node yang juga telah didefinisikan sebelumnya.
DT  merupakan teknik decision making yang paling sederhana serta merupakan salah satu teknik AI di game programming yang cukup populer. 

funny-pictures-mtv-cribs-squirrel-tree


 ======================================================================
Sekedar warning saja: Source code untuk Decision Tree ini sudah saya revisi lumayan banyak, udah jauh beda dari yg saya post di sini, jadi bagi yang mau pake yang terbaru sebaiknya donlot saja di GitHub. Contoh implementasinya juga sudah disertakan
======================================================================

Bentuk DT yang paling populer yaitu Binary Decision Tree (BDT). Ciri khasnya yaitu hanya mempunyai dua cabang: yes atau no, true atau false, ya atau tidak, dll. Kelebihannya yaitu sangat simple dan mudah dioptimasi.

2. Struktur

Struktur Decision Tree

image

1. Root Node, sumber dari segala permasalahan…
2. Decision Node, permasalahan2x yang didefinisikan selanjutnya antara root node dengan action node
3. Action Node, akhir dari tree, di mana konklusi sudah didapatkan dan selanjutnya seuatu aksi akan diambil

Class Diagram untuk Decision Tree

image

Untuk struktur class nya tidak terlalu rumit, hanya ada 3 class dan satu interface.
1. Interface INode
Interface ini hanya punya satu method yaitu makeDecision() yang nantinya akan diimplement oleh ketiga class lainnya.

2. Decision Node
Mendefinisikan percabangan menuju node-node selanjutnya, mendefinisikan query, serta menjalankan method makeDecision() yang akan menentukan ke cabang mana keputusan akan diambil.

3. Action Node
Berisi aksi yang akan dijalankan ketika node ini telah dicapai

4. Decision Tree
Class yang akan digunakan untuk membangun tree dari action node dan decision node, serta mendefinisikan query untuk tiap-tiap decision node.
Class ini juga mengimplement INode, agar bisa dibuat sub-tree dalam tree, Jaga2x kalau tree sudah mulai rumit dan kompleks. Jadi bisa dipecah menjadi bagian yang lebih kecil

3. Into the Code!
Sebelum masuk ke code, sekali lagi kita bahas dulu permasalahannya….
Untuk contoh di sini saya mengambil contoh implementasi BDT dari www.generation5.com, tentunya udah saya buat dalam versi AS3.0. Tree yang akan dibuat adalah seperti ini:

image

Untuk jalan ceritanya kyknya tidak perlu dijelaskan lagi, dari diagramnya harusnya udah self-explanatory lah…
Intinya ya kayak di game2x gitu, biar AI bisa merespon keadaan di sekitarnya…

pc_shiveringi_s3

Okey, kita mulai dari membuat interface INode nya:
1. Interface INode
   1: package com.pzuh.decisiontree
   2: {
   3:     public interface INode
   4:     {
   5:         function makeDecision():void;
   6:     }
   7: }

Very simple, hanya ada satu method makeDecision()



2. Decision Node


   1: package com.pzuh.decisiontree
   2: {
   3:     public class DecisionNode implements INode
   4:     {
   5:         public var falseNode:INode;
   6:         public var trueNode:INode;
   7:         
   8:         public var query:Boolean;
   9:         
  10:         public function DecisionNode()
  11:         {
  12:             
  13:         }
  14:         
  15:         public function makeDecision():void
  16:         {
  17:             if (query == true)
  18:             {
  19:                 if (trueNode != null) 
  20:                 {
  21:                     trueNode.makeDecision();    
  22:                 }    
  23:                 else
  24:                 {
  25:                     return;
  26:                 }
  27:             }
  28:             else
  29:             {                
  30:                 if (falseNode != null) 
  31:                 {
  32:                     falseNode.makeDecision();    
  33:                 }
  34:                 else
  35:                 {
  36:                     return;
  37:                 }
  38:             }
  39:         }
  40:     }
  41: }

5-8: Mendefinisikan variabel falseNode untuk menuju cabang ‘no’, 'false’, ‘tidak’, dll. Variabel trueNode untuk ke cabang sebaliknya. Variabel query menyimpan data boolean hasil pemrosesan pertanyaan di suatu decision node

15: Method makeDecision() akan bekerja secara rekursif, di mana ketika variabel query bernilai true maka trueNode dari decisionNode ini akan menjalankan method makeDecision() juga, begitu seterusnya sampai dicapai sebuah konklusi atau ditemukan node bernilai null. Untuk query yang bernilai false, cara kerjanya juga sama


3. Action Node

Dari diagram yang di atas tadi, berarti ada 3 buah Action Node yaitu: AttackNode, DontAttackNode, dan FleeNode

Berikut ini AttackNode isi dari class AttackNode


   1: package tree.node 
   2: {
   3:     import com.pzuh.decisiontree.INode;
   4:     
   5:     public class AttackNode implements INode 
   6:     {
   7:         private var myMainClass:Main;
   8:         
   9:         public function AttackNode(mainClass:Main) 
  10:         {
  11:             myMainClass = mainClass;
  12:         }
  13:         
  14:         /* INTERFACE com.pzuh.decisiontree.INode */
  15:         
  16:         public function makeDecision():void 
  17:         {
  18:             myMainClass.getOutputText().text = "Attack!!";
  19:         }        
  20:     }
  21: }

16: method makeDecision() hanya akan mengeluarkan output text “Attack!”. Masih text based, maklum cm buat contoh aja…

Untuk class DontAttackNode dan FleeNode, isinya juga sama, hanya textnya saja yang beda. Jadi ga perlu sy post juga di sini….


4. MainClass

Sebelum masuk ke Tree nya, ada baiknya kalo dibuat dulu MainClassnya, coz ada beberapa data dari mainClass yang harus dipakai di Tree (Sebenernya di ActionNode juga sih)


   1: package 
   2: {
   3:     import flash.display.*;
   4:     import flash.events.*;
   5:     import flash.text.*;
   6:     
   7:     import fl.controls.*;
   8:     import fl.data.*;
   9:     
  10:     import tree.Tree;
  11:     
  12:     public class Main extends MovieClip
  13:     {
  14:         private var query1:Boolean;
  15:         private var query2:Boolean;
  16:         private var query3:Boolean;
  17:         
  18:         private var myTree:Tree;
  19:         
  20:         public function Main():void 
  21:         {
  22:             myTree = new Tree(this);
  23:             
  24:             submitBtn.addEventListener(MouseEvent.CLICK, submitBtnClicked, false, 0, true);
  25:             
  26:             comboBox3.visible = false;
  27:             label3.visible = false;
  28:             comboBox1.addEventListener(Event.CHANGE, comboBox1Handler, false, 0, true);
  29:         }        
  30:         
  31:         private function submitBtnClicked(event:MouseEvent):void
  32:         {
  33:             query1 = getComboBoxVal(comboBox1.selectedLabel);
  34:             query2 = getComboBoxVal(comboBox2.selectedLabel);
  35:             query3 = getComboBoxVal(comboBox3.selectedLabel);
  36:             
  37:             myTree.makeDecision();            
  38:         }
  39:         
  40:         private function comboBox1Handler(event:Event):void
  41:         {
  42:             var comboBox:Object = event.target;
  43:             
  44:             switch(comboBox.selectedLabel)
  45:             {
  46:                 case "Yes":
  47:                     comboBox2.visible = true;
  48:                     label2.visible = true;
  49:                     
  50:                     comboBox3.visible = false;
  51:                     label3.visible = false;
  52:                     break;
  53:                 
  54:                 case "No":
  55:                     comboBox2.visible = false;
  56:                     label2.visible = false;
  57:                     
  58:                     comboBox3.visible = true;
  59:                     label3.visible = true;
  60:                     break;
  61:             }
  62:         }
  63:         
  64:         private function getComboBoxVal(val:String):Boolean
  65:         {
  66:             switch(val)
  67:             {
  68:                 case "Yes":
  69:                     return true;
  70:                     break;
  71:                 
  72:                 case "No":
  73:                     return false;
  74:                     break;
  75:             }
  76:             
  77:             return false;
  78:         }
  79:         
  80:         public function getQueryVal(nodeNum:int):Boolean
  81:         {
  82:             switch(nodeNum)
  83:             {
  84:                 case 1:
  85:                     return query1;
  86:                     break;
  87:                     
  88:                 case 2:
  89:                     return query2;
  90:                     break;
  91:                     
  92:                 case 3:
  93:                     return query3;
  94:                     break
  95:             }
  96:             
  97:             return false;
  98:         }
  99:         
 100:         public function getOutputText():TextField
 101:         {
 102:             return outputTxt;
 103:         }
 104:     }    
 105: }

Yang akan sy jelaskan di mainClass ini cuma yg penting2x aja, krn selebihnya cm code2x untuk bikin UI nya aja, kalo yg itu males gw ngejelasinnya….

14-16: Mendefinisikan query2x dari tiap decision node, ada 3 query masing2x untuk root node, dan 2 decision node. Berhubung ini cuma contoh, nantinya nilai query ini akan diambil dari combo box.

31: Method submitBtnClicked() dipanggil ketika submit button diklik. DI sini nilai variabel query akan diisi dengan nilai2x yang ada pada combo box. Selanjutnya mehod makeDecision() dari instance myTree dipanggil.


5. Tree

Sebelumnya dibuat sebuah base class untuk tree, Class ini kemudian akan diextends ketika akan membangun sebuah decision tree lain.


   1: package com.pzuh.decisiontree
   2: {
   3:     public class DecisionTree implements INode
   4:     {
   5:         protected var decisionNodeArray:Array;
   6:         protected var actionNodeArray:Array;
   7:         
   8:         protected var decisionNodeNum:int;
   9:         
  10:         public function DecisionTree() 
  11:         {
  12:             decisionNodeArray = new Array();
  13:             actionNodeArray = new Array();
  14:             
  15:             init();
  16:         }
  17:         
  18:         protected function init():void
  19:         {
  20:             for (var i:int = 0; i < decisionNodeNum; i++)
  21:             {
  22:                 decisionNodeArray.push(new DecisionNode());
  23:             }    
  24:             
  25:             constructTree();
  26:         }
  27:         
  28:         protected function constructTree():void
  29:         {
  30:             //must be overriden
  31:             throw new Error("ERROR: Method constructTree() cannot empty and must be overriden");
  32:         }
  33:         
  34:         protected function defineQuery():void
  35:         {
  36:             //must be overriden
  37:             throw new Error("ERROR: Method defineQuery() cannot empty and must be overriden");
  38:         }
  39:         
  40:         public function makeDecision():void
  41:         {
  42:             defineQuery();
  43:             
  44:             decisionNodeArray[0].makeDecision();
  45:         }
  46:     }
  47: }

5-6: buat array yang nantinya akan digunakan untuk menyimpan decisionNode dan actionNode

8: variabel decisionNodeNum berisi informasi jumlah decisionNode yang dimiliki oleh sebuah tree

18: method init() akan memasukkan sejumlah decision node ke dalam decisionNodeArray sesuai nilai decisionNodeNum kemudian akan memanggil method costructTree() untuk membangun tree nya

28-38: method constructTree() dan defineQuery() kosong karena akan dioverride dan didefinisikan isinya oleh kelas turunannya. Di sini akan mengeluarkan output error jika ternyata oleh turunannya tidak dioverride

40: method makeDecision() akan memanggil method defineQuery() yang akan menentukan nilai query di tiap decision node, dan kemudian memanggil method makeDecision() dari root node (decisionNodeArray yang berindex 0) yang selanjutnya akan berjalan rekursif sampai sebuah keputusan diambil.


   1: package tree 
   2: {
   3:     import com.pzuh.decisiontree.DecisionTree;
   4:     import tree.node.FleeNode;
   5:     
   6:     import tree.node.AttackNode;
   7:     import tree.node.DontAttackNode;
   8:     
   9:     public class Tree extends DecisionTree 
  10:     {
  11:         private var myMainClass:Main;
  12:         
  13:         public function Tree(mainClass:Main) 
  14:         {
  15:             myMainClass = mainClass;
  16:             
  17:             super();            
  18:         }
  19:         
  20:         override protected function init():void
  21:         {
  22:             //tentukan jumlah decision node yang ada dalam tree
  23:             decisionNodeNum = 3;
  24:             
  25:             super.init();
  26:         }
  27:         
  28:         override protected function defineQuery():void
  29:         {
  30:             //definisikan kondisi tiap decision node
  31:             decisionNodeArray[0].query = myMainClass.getQueryVal(1);
  32:             decisionNodeArray[1].query = myMainClass.getQueryVal(2);
  33:             decisionNodeArray[2].query = myMainClass.getQueryVal(3);
  34:         }
  35:         
  36:         override protected function constructTree():void
  37:         {
  38:             //masukkan action node ke dalam array
  39:             actionNodeArray[0] = new AttackNode(myMainClass);
  40:             actionNodeArray[1] = new DontAttackNode(myMainClass);
  41:             actionNodeArray[2] = new FleeNode(myMainClass);
  42:             
  43:             //tentukan percabangan dari tiap2x decision node
  44:             //decision node #1: "Have you got a weapon?"
  45:             decisionNodeArray[0].trueNode = decisionNodeArray[1]; //Yes
  46:             decisionNodeArray[0].falseNode = decisionNodeArray[2]; //No
  47:             
  48:             //decision node #2: "Are You close enough to the enemy?"
  49:             decisionNodeArray[1].trueNode = actionNodeArray[0]; //Yes
  50:             decisionNodeArray[1].falseNode = actionNodeArray[1]; //No
  51:             
  52:             //decision node #3: "Can you tackle the enemy bare-handed?"
  53:             decisionNodeArray[2].trueNode = actionNodeArray[0]; //Yes
  54:             decisionNodeArray[2].falseNode = actionNodeArray[2]; //No
  55:         }        
  56:     }
  57: }

20: Meng-override method init() untuk memasukkan jumlah decision node ke variabel decisionNodeNum

28: Meng-override defineQuery(), bisa dilihat sendiri isinya adalah mengisi variabel query milik tiap2x decisionNode dengan query yang didefinisikan di mainClass

38-41: Menginstatiating object AttackNode, DontAttackNode, dan FleeNode, yang kemudian ketiganya dimasukkan ke dalam actionNodeArray

45-54: Mengisi nilai variabel trueNode dan falseNode dari tiap2x decisionNode dengan node2x selanjutnya sesuai dengan struktur di gambar yang udah dibahas sebelumnya



4. Test and Run!

Dan ini adalah sampel implementasi DT yang telah sy buat, silahkan di test:







5. Source Code

Untuk source codenya silakan donlot di link di bawah ini.






6. Referensi


0 comments:

Post a Comment