C++ Entscheidungsbaum Umsetzung Frage: Denke, Dass Im Code
Ich habe die Kodierung für ein paar Jahre, aber ich noch nicht dazu gekommen die hängen von pseudo-Code oder tatsächlich mit dem Gedanken, die Sachen im code noch. Wegen diesem problem, ich habe Schwierigkeiten, herauszufinden, genau, was zu tun, bei der Schaffung einer Lern-Entscheidungsbaum.
Hier sind ein paar Seiten, die ich angeschaut haben und Vertrauen Sie mir, es waren viel mehr
Zusammen mit mehrere Bücher wie Ian Millington AI für Spiele, einen anständigen run-down der verschiedenen Lern-algorithmen von Entscheidungsbäumen und Verhaltens-Mathematik für das Spiel Programmieren, das ist im Grunde alles über Entscheidungsbäume und-Theorie. Ich verstehe die Konzepte, die für eine Entscheidung Baum zusammen mit Entropie ID3 und ein wenig wie zu verweben einem genetischen Algorithmus und eine Entscheidung Baum zu entscheiden, den Knoten für die GA.
Sie geben einen guten Einblick, aber nicht das, was ich bin auf der Suche nach wirklich.
Habe ich einige basic-code, der erstellt wird, die die Knoten für die Entscheidung Baum, und ich glaube, ich weiß, wie die Umsetzung der tatsächlichen Logik, aber es nützt nichts, wenn ich nicht einen Zweck haben, um das Programm oder die Entropie oder ein Lern-Algorithmus beteiligt.
Was ich Frage ist, kann jemand mir helfen herauszufinden, was muss ich tun, um das lernen eines entscheidungsbaumes. Ich habe meine Knoten in einer eigenen Klasse, die durch fließt, Funktionen zu erstellen, die den Baum, aber wie würde ich die Entropie in dieses, und sollte es haben, eine Klasse, eine Struktur, die ich bin mir nicht sicher, wie Sie Sie zusammenbringen. Pseudo-code und eine Idee, wo ich mit der Theorie und den zahlen. Ich kann den code zusammen, wenn ich nur wüsste, was ich brauchte, um code. Jede Beratung wäre geschätzt.
Wie Würde Ich Mich Über Diese, Im Grunde.
Hinzufügen eines Lern-Algorithmus, wie ID3 und Entropie. Wie sollte es eingerichtet sein?
Sobald ich haben dies herausgefunden, wie man über all dies,ich plan zur Umsetzung dieser in eine state-machine, das geht durch verschiedene Zustände in einem Spiel/simulation-format. Dies alles ist schon eingerichtet, ich habe gerade diese Figur sein könnte, stand-alone und sobald ich es herausfinden ich kann nur verschieben Sie es in das andere Projekt.
Hier ist der source-code habe ich jetzt.
Vielen Dank im Voraus!
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;
}
Entscheidungsbaum.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;
}
}
TreeNode-Objekte.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;
}
- Gute Frage, also ich von Ihnen positiv bewertet werden. Je nachdem, was Sie versuchen, zu erreichen, eine Bibliothek wie castor, der Ihnen erlaubt, mit der Umsetzung einiger Logik-Programmierung Paradigma Dinge in c++ nativ von Interesse sein können. mpprogramming.com/cpp
- Guter Herr, das ist eine Menge code zu erwarten, dass zufällige Freiwilligen durch zu Lesen...
- Ja, schon, aber es nicht zeigen ich weiß, was ich Tue, einen Sinn. Viele der Fragen, die ich angeschaut habe nicht genug zu gehen oder Sie nicht zeigen, Sie hat funktioniert. Ich habe Arbeit! haha. Ich erwarte nicht, viele gehen durch jede Kleinigkeit, nur um zu begreifen, was Los ist.
- Und es sieht nicht so groß auf dem Programm-ha!
- Ich nicht bekommen, Ihre "erstellen Sie den Knoten" code in
searchAddNode
. Es tut die gleiche Sache unabhängig von derif
.. - C++ ist nicht Java, Sie brauchen nicht zu
new
alles (für Beispiel, es ist unnötig zunew
NewTree
immain
), nur nicht mit einem Zeiger, um mit zu beginnen. - Mein Vorschlag: Schreiben Sie einige tests (ein-vs. erwarteten Ergebnissen der decision tree) und kommen zurück, wenn Sie erkennen, dass Sie Ihre besten Anstrengungen produziert ein Falsches Ergebnis. Ansonsten, das beste aus dieser Frage ist, "hier ist eine Referenz-Implementierung."
Du musst angemeldet sein, um einen Kommentar abzugeben.
Bitte korrigieren Sie mich, wenn ich falsch bin, aber ausgehend von den Bildern auf http://dms.irb.hr/tutorial/tut_dtrees.php und http://www.decisiontrees.net/?q=node/21 die tatsächliche Entscheidung Logik gehen sollte der Knoten nicht im Baum. Sie könnten Modell, durch polymorphe Knoten, einen für jede Entscheidung, die dort gemacht werden. Mit ein wenig änderung an der Konstruktion des Baums und eine kleine Modifikation für die Entscheidung, die delegation der code sollte in Ordnung sein.
Grundsätzlich müssen Sie brechen alles ab in die Stadien und dann modularise jeden Teil des Algorithmus, den Sie versuchen, zu implementieren.
Dazu können Sie in pseudo-code oder im code selbst mit Funktionen/Klassen und stubs.
Jeden Teil des Algorithmus können Sie dann code in eine Funktion und auch testen Sie die Funktion, bevor Sie es alle zusammen. Sie wird grundsätzlich am Ende mit verschiedenen Funktionen oder Klassen, die für spezifische Zwecke in die Algorithmus-Implementierung. Also in deinem Fall für die Baum-Konstruktion Sie haben eine Funktion, die berechnet die Entropie, die in einem Knoten, eine andere, dass die Partitionen, die Daten in Teilmengen an jedem Knoten, etc.
Ich spreche im Allgemeinen hier eher als speziell mit Bezug auf die Entscheidung Baum Bau. Schauen Sie sich das Buch auf maschinelles Lernen von Mitchell, wenn Sie brauchen gezielte Informationen über Entscheidungsbaum-algorithmen und der einzelnen Schritte.
Den pseudocode zu implementieren, wird ein Entscheidungsbaum wie folgt
Haben Sie zum speichern von Knoten auf jeder Ebene mit code wie
decisiontree[attr][val]=new_node