#c #machine-learning #decision-tree #entropy
#c #машинное обучение #дерево решений #энтропия
Вопрос:
Я программирую уже несколько лет, но все еще не освоился с псевдокодированием или по-настоящему продумываю вещи в коде. Из-за этой проблемы у меня возникли проблемы с определением того, что именно делать при создании дерева решений обучения.
Вот несколько сайтов, которые я просмотрел и, поверьте мне, их было еще много
Учебные пособия по дереву решений
Наряду с несколькими книгами, такими как ИИ Иэна Миллингтона для игр, которая включает в себя приличное изложение различных алгоритмов обучения, используемых в деревьях решений, и поведенческую математику для программирования игр, которая в основном посвящена деревьям решений и теории. Я понимаю концепции дерева решений наряду с энтропией, 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;
}
Decision 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;
}
Комментарии:
1. Хороший вопрос, поэтому я поддержал. В зависимости от того, чего вы пытаетесь достичь, может представлять интерес библиотека, такая как castor, которая позволяет вам реализовать некоторые парадигмы логического программирования на c изначально. mpprogramming.com/cpp
2. Боже милостивый, это слишком много кода, чтобы ожидать, что случайные добровольцы прочитают его…
3. Да, но это показывает, что я вроде как знаю, что я делаю в некотором смысле. На многие из вопросов, которые я рассмотрел, было недостаточно ответов, или они не показывали, что они действительно работают. Я действительно работал! ха-ха. Я не ожидаю, что многие будут разбираться в каждой мелочи, просто чтобы понять, что происходит.
4. И это не выглядит таким уж большим для программы, ха!
5. Я не получаю ваш код «создать узел» в
searchAddNode. Это делает то же самое независимо отif..
Ответ №1:
Пожалуйста, поправьте меня, если я ошибаюсь, но, судя по изображениям на http://dms.irb.hr/tutorial/tut_dtrees.php и http://www.decisiontrees.net/?q=node/21 фактическая логика принятия решений должна находиться в узлах, а не в дереве. Вы могли бы смоделировать это, имея полиморфные узлы, по одному для каждого решения, которое необходимо принять. С небольшим изменением конструкции дерева и незначительной модификацией для делегирования решений ваш код должен быть в порядке.
Ответ №2:
По сути, вам нужно разбить все на этапы, а затем модулировать каждую часть алгоритма, который вы пытаетесь реализовать.
Вы можете сделать это в псевдокоде или в самом коде, используя функции / классы и заглушки.
Затем каждую часть алгоритма вы можете закодировать в какой-либо функции и даже протестировать эту функцию, прежде чем складывать все это вместе. В конечном итоге вы получите различные функции или классы, которые используются для определенных целей в реализации алгоритма. Итак, в вашем случае для построения дерева у вас будет одна функция, которая вычисляет энтропию в узле, другая, которая разбивает данные на подмножества в каждом узле и т.д.
Здесь я говорю в общем случае, а не конкретно в отношении построения дерева решений. Ознакомьтесь с книгой по машинному обучению Митчелла, если вам нужна конкретная информация об алгоритмах дерева решений и связанных с ними шагах.
Ответ №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