C++決策樹實現問題：在代碼中考慮

Question

我已經編寫了幾年，但是我仍然沒有弄懂僞代碼或者實際上在代碼中思考問題。由於這個問題，我很難確定在創建學習決策樹時如何做。

這裏是我已經看過幾個網站，相信我還有很多更

Decision Tree Tutorials

DMS Tutorials

隨着幾本書，比如伊恩·米林的AI進行遊戲，其中包括在決策樹和行爲數學中用於遊戲編程的不同學習算法的體面衰減基本上都是關於決策樹和理論。我理解了決策樹的概念以及熵，ID3，以及如何交織遺傳算法並使決策樹決定GA的節點。 他們給予很好的洞察力，但不是我真正在尋找的東西。

我確實有一些基本代碼可以爲決策樹創建節點，並且我相信我知道如何實現實際的邏輯，但如果我沒有目的程序或者有熵或學習，這是沒有用的涉及的算法。

我在問的是，有人能幫我弄清楚我需要做什麼來創建這個學習決策樹。我在自己的類中創建了一個節點，通過函數來​​創建樹，但是如何將熵放入此類中，並且它應該有一個類，一個結構，我不知道如何將它放在一起。僞代碼和一個想法，我將與所有這些理論和數字一起去。如果我知道我需要編碼，我可以將代碼放在一起。任何指導將不勝感激。

基本上我該如何去解決這個問題。

添加一個學習算法，如ID3和熵。應該如何設置？

一旦我找到了解決這個問題的方法，我打算將這個實現成一個狀態機，以遊戲/模擬格式通過不同的狀態。所有這些已經建立起來了，我只是想這可能是獨立的，一旦我弄明白了，我可以將它移到其他項目中。

這裏是我現在的源代碼。

提前致謝！

Main.cpp的：

int main() 
{ 
    //create the new decision tree object 
    DecisionTree* NewTree = new DecisionTree(); 

    //add root node the very first 'Question' or decision to be made 
    //is monster health greater than player health? 
    NewTree->CreateRootNode(1); 

    //add nodes depending on decisions 
    //2nd decision to be made 
    //is monster strength greater than player strength? 
    NewTree->AddNode1(1, 2); 

    //3rd decision 
    //is the monster closer than home base? 
    NewTree->AddNode2(1, 3); 

    //depending on the weights of all three decisions, will return certain node result 
    //results! 
    //Run, Attack, 
    NewTree->AddNode1(2, 4); 
    NewTree->AddNode2(2, 5); 
    NewTree->AddNode1(3, 6); 
    NewTree->AddNode2(3, 7); 

    //Others: Run to Base ++ Strength, Surrender Monster/Player, 
    //needs to be made recursive, that way when strength++ it affects decisions second time around DT 

    //display information after creating all the nodes 
    //display the entire tree, i want to make it look like the actual diagram! 
    NewTree->Output(); 

    //ask/answer question decision making process 
    NewTree->Query(); 

    cout << "Decision Made. Press Any Key To Quit." << endl; 

    //pause quit, oh wait how did you do that again...look it up and put here 

    //release memory! 
    delete NewTree; 

    //return random value 
    //return 1; 
} 

決策tree.h中：

//the decision tree class 
class DecisionTree 
{ 
public: 
    //functions 
    void RemoveNode(TreeNodes* node); 
    void DisplayTree(TreeNodes* CurrentNode); 
    void Output(); 
    void Query(); 
    void QueryTree(TreeNodes* rootNode); 
    void AddNode1(int ExistingNodeID, int NewNodeID); 
    void AddNode2(int ExistingNodeID, int NewNodeID); 
    void CreateRootNode(int NodeID); 
    void MakeDecision(TreeNodes* node); 

    bool SearchAddNode1(TreeNodes* CurrentNode, int ExistingNodeID, int NewNodeID); 
    bool SearchAddNode2(TreeNodes* CurrentNode, int ExistingNodeID, int NewNodeID); 

    TreeNodes* m_RootNode; 

    DecisionTree(); 

    virtual ~DecisionTree(); 
}; 

Decisions.cpp：

int random(int upperLimit); 

//for random variables that will effect decisions/node values/weights 
int random(int upperLimit) 
{ 
    int randNum = rand() % upperLimit; 
    return randNum; 
} 

//constructor 
//Step 1! 
DecisionTree::DecisionTree() 
{ 
    //set root node to null on tree creation 
    //beginning of tree creation 
    m_RootNode = NULL; 
} 

//destructor 
//Final Step in a sense 
DecisionTree::~DecisionTree() 
{ 
    RemoveNode(m_RootNode); 
} 

//Step 2! 
void DecisionTree::CreateRootNode(int NodeID) 
{ 
    //create root node with specific ID 
    // In MO, you may want to use thestatic creation of IDs like with entities. depends on how many nodes you plan to have 
    //or have instantaneously created nodes/changing nodes 
    m_RootNode = new TreeNodes(NodeID); 
} 

//Step 5.1!~ 
void DecisionTree::AddNode1(int ExistingNodeID, int NewNodeID) 
{ 
    //check to make sure you have a root node. can't add another node without a root node 
    if(m_RootNode == NULL) 
    { 
     cout << "ERROR - No Root Node"; 
     return; 
    } 

    if(SearchAddNode1(m_RootNode, ExistingNodeID, NewNodeID)) 
    { 
     cout << "Added Node Type1 With ID " << NewNodeID << " onto Branch Level " << ExistingNodeID << endl; 
    } 
    else 
    { 
     //check 
     cout << "Node: " << ExistingNodeID << " Not Found."; 
    } 
} 

//Step 6.1!~ search and add new node to current node 
bool DecisionTree::SearchAddNode1(TreeNodes *CurrentNode, int ExistingNodeID, int NewNodeID) 
{ 
    //if there is a node 
    if(CurrentNode->m_NodeID == ExistingNodeID) 
    { 
     //create the node 
     if(CurrentNode->NewBranch1 == NULL) 
     { 
      CurrentNode->NewBranch1 = new TreeNodes(NewNodeID); 
     } 
     else 
     { 
      CurrentNode->NewBranch1 = new TreeNodes(NewNodeID); 
     } 
     return true; 
    } 
    else 
    { 
     //try branch if it exists 
     //for a third, add another one of these too! 
     if(CurrentNode->NewBranch1 != NULL) 
     { 
      if(SearchAddNode1(CurrentNode->NewBranch1, ExistingNodeID, NewNodeID)) 
      { 
       return true; 
      } 
      else 
      { 
       //try second branch if it exists 
       if(CurrentNode->NewBranch2 != NULL) 
       { 
        return(SearchAddNode2(CurrentNode->NewBranch2, ExistingNodeID, NewNodeID)); 
       } 
       else 
       { 
        return false; 
       } 
      } 
     } 
     return false; 
    } 
} 

//Step 5.2!~ does same thing as node 1. if you wanted to have more decisions, 
//create a node 3 which would be the same as this maybe with small differences 
void DecisionTree::AddNode2(int ExistingNodeID, int NewNodeID) 
{ 
    if(m_RootNode == NULL) 
    { 
     cout << "ERROR - No Root Node"; 
    } 

    if(SearchAddNode2(m_RootNode, ExistingNodeID, NewNodeID)) 
    { 
     cout << "Added Node Type2 With ID " << NewNodeID << " onto Branch Level " << ExistingNodeID << endl; 
    } 
    else 
    { 
     cout << "Node: " << ExistingNodeID << " Not Found."; 
    } 
} 

//Step 6.2!~ search and add new node to current node 
//as stated earlier, make one for 3rd node if there was meant to be one 
bool DecisionTree::SearchAddNode2(TreeNodes *CurrentNode, int ExistingNodeID, int NewNodeID) 
{ 
    if(CurrentNode->m_NodeID == ExistingNodeID) 
    { 
     //create the node 
     if(CurrentNode->NewBranch2 == NULL) 
     { 
      CurrentNode->NewBranch2 = new TreeNodes(NewNodeID); 
     } 
     else 
     { 
      CurrentNode->NewBranch2 = new TreeNodes(NewNodeID); 
     } 
     return true; 
    } 
    else 
    { 
     //try branch if it exists 
     if(CurrentNode->NewBranch1 != NULL) 
     { 
      if(SearchAddNode2(CurrentNode->NewBranch1, ExistingNodeID, NewNodeID)) 
      { 
       return true; 
      } 
      else 
      { 
       //try second branch if it exists 
       if(CurrentNode->NewBranch2 != NULL) 
       { 
        return(SearchAddNode2(CurrentNode->NewBranch2, ExistingNodeID, NewNodeID)); 
       } 
       else 
       { 
        return false; 
       } 
      } 
     } 
     return false; 
    } 
} 

//Step 11 
void DecisionTree::QueryTree(TreeNodes* CurrentNode) 
{ 
    if(CurrentNode->NewBranch1 == NULL) 
    { 
     //if both branches are null, tree is at a decision outcome state 
     if(CurrentNode->NewBranch2 == NULL) 
     { 
      //output decision 'question' 
      /////////////////////////////////////////////////////////////////////////////////////// 
     } 
     else 
     { 
      cout << "Missing Branch 1"; 
     } 
     return; 
    } 
    if(CurrentNode->NewBranch2 == NULL) 
    { 
     cout << "Missing Branch 2"; 
     return; 
    } 

    //otherwise test decisions at current node 
    MakeDecision(CurrentNode); 
} 

//Step 10 
void DecisionTree::Query() 
{ 
    QueryTree(m_RootNode); 
} 

//////////////////////////////////////////////////////////// 
//debate decisions create new function for decision logic 

// cout << node->stringforquestion; 

//Step 12 
void DecisionTree::MakeDecision(TreeNodes *node) 
{ 
    //should I declare variables here or inside of decisions.h 
    int PHealth; 
    int MHealth; 
    int PStrength; 
    int MStrength; 
    int DistanceFBase; 
    int DistanceFMonster; 

    ////sets random! 
    srand(time(NULL)); 

    //randomly create the numbers for health, strength and distance for each variable 
    PHealth = random(60); 
    MHealth = random(60); 
    PStrength = random(50); 
    MStrength = random(50); 
    DistanceFBase = random(75); 
    DistanceFMonster = random(75); 

    //the decision to be made string example: Player health: Monster Health: player health is lower/higher 
    cout << "Player Health: " << PHealth << endl; 
    cout << "Monster Health: " << MHealth << endl; 
    cout << "Player Strength: " << PStrength << endl; 
    cout << "Monster Strength: " << MStrength << endl; 
    cout << "Distance Player is From Base: " << DistanceFBase << endl; 
    cout << "Disntace Player is From Monster: " << DistanceFMonster << endl; 

    //MH > PH 
    //MH < PH 
    //PS > MS 
    //PS > MS 
    //DB > DM 
    //DB < DM 

    //good place to break off into different decision nodes, not just 'binary' 

    //if statement lower/higher query respective branch 
    if(PHealth > MHealth) 
    { 
    } 
    else 
    { 
    } 
    //re-do question for next branch. Player strength: Monster strength: Player strength is lower/higher 
    //if statement lower/higher query respective branch 
    if(PStrength > MStrength) 
    { 
    } 
    else 
    { 
    } 

    //recursive question for next branch. Player distance from base/monster. 
    if(DistanceFBase > DistanceFMonster) 
    { 
    } 
    else 
    { 
    } 
    //DECISION WOULD BE MADE 
    //if statement? 
    // inside query output decision? 
    //cout << << 

     //QueryTree(node->NewBranch2); 

     //MakeDecision(node); 
} 

//Step.....8ish? 
void DecisionTree::Output() 
{ 
    //take repsective node 
    DisplayTree(m_RootNode); 
} 

//Step 9 
void DecisionTree::DisplayTree(TreeNodes* CurrentNode) 
{ 
    //if it doesn't exist, don't display of course 
    if(CurrentNode == NULL) 
    { 
     return; 
    } 

    ////////////////////////////////////////////////////////////////////////////////////////////////// 
    //need to make a string to display for each branch 
    cout << "Node ID " << CurrentNode->m_NodeID << "Decision Display: " << endl; 

    //go down branch 1 
    DisplayTree(CurrentNode->NewBranch1); 

    //go down branch 2 
    DisplayTree(CurrentNode->NewBranch2); 
} 

//Final step at least in this case. A way to Delete node from tree. Can't think of a way to use it yet but i know it's needed 
void DecisionTree::RemoveNode(TreeNodes *node) 
{ 
    //could probably even make it to where you delete a specific node by using it's ID 
    if(node != NULL) 
    { 
     if(node->NewBranch1 != NULL) 
     { 
      RemoveNode(node->NewBranch1); 
     } 

     if(node->NewBranch2 != NULL) 
     { 
      RemoveNode(node->NewBranch2); 
     } 

     cout << "Deleting Node" << node->m_NodeID << endl; 

     //delete node from memory 
     delete node; 
     //reset node 
     node = NULL; 
    } 
} 

TreeNodes。^ h：

using namespace std; 
//tree node class 
class TreeNodes 
{ 
public: 
    //tree node functions 
    TreeNodes(int nodeID/*, string QA*/); 
    TreeNodes(); 

    virtual ~TreeNodes(); 

    int m_NodeID; 

    TreeNodes* NewBranch1; 
    TreeNodes* NewBranch2; 
}; 

TreeNodes.cpp：

//contrctor 
TreeNodes::TreeNodes() 
{ 
    NewBranch1 = NULL; 
    NewBranch2 = NULL; 

    m_NodeID = 0; 
} 

//deconstructor 
TreeNodes::~TreeNodes() 
{ } 

//Step 3! Also step 7 hah! 
TreeNodes::TreeNodes(int nodeID/*, string NQA*/) 
{ 
    //create tree node with a specific node ID 
    m_NodeID = nodeID; 

    //reset nodes/make sure! that they are null. I wont have any funny business #s -_- 
    NewBranch1 = NULL; 
    NewBranch2 = NULL; 
} 

Answer 1

請糾正我，如果我錯了，但在http://dms.irb.hr/tutorial/tut_dtrees.php和http://www.decisiontrees.net/?q=node/21從圖像中判斷實際的決策邏輯應該在節點，不在樹中。你可以通過使用多態節點來對它進行建模，每一個決策都會有一個節點。通過對樹形結構進行一些更改，並對決策委派稍作修改，您的代碼應該沒問題。

Answer 2

基本上你需要把所有東西都分解成幾個階段，然後模塊化你試圖實現的算法的每個部分。

您可以使用函數/類和存根在僞代碼或代碼本身中執行此操作。

算法的每個部分都可以在某些函數中進行編碼，甚至可以在將所有函數加在一起之前對其進行測試。基本上，最終會得到用於算法實現中的特定目的的各種函數或類。所以你的情況爲樹型結構，你將有一個功能，在一個節點計算熵，另一種在每個節點的數據劃分爲子集等

我在一般情況下，這裏所說的，而不是專門針對決策樹建設。如果您需要關於決策樹算法和涉及的步驟的特定信息，請參閱Mitchell的「機器學習」一書。

Answer 3

僞代碼來實現的決策樹如下

createdecisiontree(data, attributes) 

Select the attribute a with the highest information gain 

for each value v of the attribute a 

    Create subset of data where data.a.val==v (call it data2) 

    Remove the attribute a from the attribute list resulting in attribute_list2 

    Call CreateDecisionTree(data2, attribute_list2) 

你必須在每個級別有一些代碼來存儲節點像

decisiontree [ATTR] [VAL] = new_node