C++ Arbre De Décision De Mise En Œuvre De Question: Pensez Au Code

J'ai été codant pour quelques années, mais je n'ai toujours pas eu le coup de pseudo-codage ou en train de penser les choses dans le code encore. En raison de ce problème, j'ai du mal à comprendre exactement quoi faire dans la création de l'apprentissage d'un Arbre de Décision.

Voici quelques sites que j'ai regardé et croyez-moi, il y avait beaucoup plus de

Arbre De Décision Tutoriels

DMS Tutoriels

Avec plusieurs livres tels que Ian Millington de l'IA pour les Jeux qui comprend un décent de l'exécution des divers algorithmes d'apprentissage utilisés dans les arbres de décision et de comportement Mathématiques pour la Programmation de Jeu qui est à peu près tout sur les Arbres de Décision et de la théorie. Je comprends les concepts pour un arbre de décision avec l'Entropie, ID3 et un peu sur la façon de mêler un algorithme génétique et un arbre de décision, de décider les nœuds de l'AG.
Ils donnent un bon aperçu, mais pas ce que je recherche vraiment.

J'ai quelques base de code qui crée les nœuds de l'arbre de décision, et je crois que je sais comment mettre en œuvre effective de la logique, mais il ne sert à rien si je n'ai pas de but pour le programme ou l'entropie ou un algorithme d'apprentissage impliqués.

Ce que je demande est, quelqu'un peut-il m'aider à comprendre ce que je dois faire pour créer cet apprentissage arbre de décision. J'ai mes nœuds dans une classe de leur propre qui coule à travers les fonctions de création de l'arbre, mais comment pourrais-je mettre de l'entropie dans ce et doit-il disposer d'une classe, d'un struct je ne suis pas sûr de la façon de les mettre ensemble. Pseudo-code et une Idée d'où je vais avec toute cette théorie et les chiffres. Je peux mettre le code si seulement je savais ce que je devais code. Des conseils seraient appréciés.

Comment Pourrais-Je Aller Sur Ça, En Fait.

L'ajout d'un algorithme d'apprentissage telles que les tags ID3 et de l'Entropie. Comment devrait-il être mis en place?

Une fois que j'ai ce compris sur la façon d'aller sur tout cela,j'ai l'intention de mettre en œuvre ce dans une machine d'état qui passe par différents états dans un jeu de simulation de format. Tout cela est déjà en place, je viens de comprendre ce qui pourrait être autonome et une fois que je l'ai trouver je peux juste passer à l'autre du projet.

Voici le code source que j'ai pour l'instant.

Merci d'avance!

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;
}

Arbre De Décision.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;
}

OriginalL'auteur CodingImagination | 2011-04-13