ID3--simple test
A. First Edition
This is just a simple demo of ID3 algorithms in AI. It is actually a top-down decision tree construction program. However,
I just tried the very simple first step because I am really hungry after 9:00pm.
Alternate: another suitable restaurant nearby
Bar: comfortable bar for waiting
Fri/Sat: true on Fridays and Saturdays
Hungry: whether one is hungry
Patrons: how many people are present (none, some, full)
Price: price range ($, $$, $$$)
Raining: raining outside
Reservation: reservation made
Type: kind of restaurant (French, Italian, Thai, Burger)
WaitEstimate: estimated wait by host (0-10 mins, 10-30, 30-60,
You are asked a question "under what circumstance would you decide to wait"?
C.The idea of programThis is a rather straight forward, simple, trivial partition problem. However, it gives me a good chance of practicing STL.
กก
E.Further improvement
F.File listing
1. ID3.cpp
กก
file name: ID3.cpp
#include <iostream> #include <vector> #include <set> #include <string> using namespace std; const int DataCount=12; const int CategoryCount=10; const int GoalFeatureIndex=CategoryCount; char* propertyName[CategoryCount]= { "alternative", "bar", "Friday", "hungry", "patron", "price", "rain", "reservation", "type", "estimate" }; typedef vector<string> PropertySet; typedef set<string> Property; typedef set<PropertySet> DataSet; //typedef set<PropertySet> Component; typedef set<DataSet> Partition; char* rawData[DataCount][CategoryCount+1]= { {"yes", "no", "no", "yes", "some", "$$$", "no", "yes", "french", "0-10", "yes"}, {"yes", "no", "no", "yes", "full", "$", "no", "no", "thai", "30-60", "no"}, {"no", "yes", "no", "no", "some", "$", "no", "no", "burger", "0-10", "yes"}, {"yes", "no", "yes", "yes", "full", "$", "no", "no", "thai", "10-30", "yes"}, {"yes", "no", "yes", "no", "full", "$$$", "no", "yes", "french", ">60", "no"}, {"no", "yes", "no", "yes", "some", "$$", "yes", "yes", "italian", "0-10", "yes"}, {"no", "yes", "no", "no", "none", "$", "yes", "no", "burger", "0-10", "no"}, {"no", "no", "no", "yes", "some", "$$", "yes", "yes", "thai", "0-10", "yes"}, {"no", "yes", "yes", "no", "full", "$", "yes", "no", "burger", ">60", "no"}, {"yes", "yes", "yes", "yes", "full", "$$$", "no", "yes", "italian", "10-30", "no"}, {"no", "no", "no", "no", "none", "$", "no", "no", "thai", "0-10", "no"}, {"yes", "yes", "yes", "yes", "full", "$", "no", "no", "burger", "30-60", "yes"} }; void initialize(DataSet& dataset); bool isUniform(const DataSet& dataset); Partition decomposite(const DataSet& theData, int index); //bool newPropertyValue(Property& property, const string& value); void addPartition(Partition& partition, const PropertySet& propertySet, int index); void displayProperty(const PropertySet& property); void displayDataSet(const DataSet& dataset); void displayPartition(const Partition& partition); void ID3(const DataSet& dataSet, int* proceedList, int length); int proceedList[8]={4, 9, 0, 3, 7, 2, 1, 6}; int main() { DataSet dataset; initialize(dataset); displayDataSet(dataset); ID3(dataset, proceedList, 8); //displayPartition(decomposite(dataset, 4)); return 0; } bool isUniform(const DataSet& dataset) { if (dataset.size()==1) { return true; } DataSet::const_iterator it=dataset.begin(); string result=(*it)[GoalFeatureIndex]; for (it++; it!=dataset.end(); it++) { if (result!=(*it)[GoalFeatureIndex]) { return false; } } return true; } void ID3(const DataSet& dataSet, int* proceedList, int length) { bool result=false; Partition partition; if (length==0) { return ; } partition=decomposite(dataSet, proceedList[0]); cout<<"the decomposite on property of "<<propertyName[proceedList[0]]<<endl; displayPartition(partition); for (Partition::const_iterator it=partition.begin(); it!=partition.end(); it++) { if (!isUniform((*it))) { ID3((*it), proceedList+1, length-1); } } } void initialize(DataSet& dataset) { PropertySet property; for (int r=0; r<DataCount; r++) { property.clear(); for (int c=0; c<CategoryCount+1; c++) { property.push_back(string(rawData[r][c])); } dataset.insert(property); } } void displayPartition(const Partition& partition) { cout<<"partition is:\n"; for (Partition::const_iterator it=partition.begin(); it!=partition.end(); it++) { displayDataSet(*it); } } /* bool newPropertyValue(Property& property, const string& value) { for (Property::iterator it=property.begin(); it!=property.end(); it++) { if (*it==value) { return false; } } property.insert(value); return true; } */ void addPartition(Partition& partition, const PropertySet& propertySet, int index) { DataSet newDataSet; for (Partition::iterator it=partition.begin(); it!=partition.end(); it++) { DataSet::iterator ptr=it->begin(); if ((*ptr)[index]==propertySet[index]) { (*it).insert(propertySet); return; } } newDataSet.insert(propertySet); partition.insert(newDataSet); } Partition decomposite(const DataSet& theData, int index) { //Property property; Partition partition; for (DataSet::const_iterator it=theData.begin(); it!=theData.end(); it++) { //newPropertyValue(property, (*it)[index]); addPartition(partition, (*it), index); } return partition; } void displayProperty(const PropertySet& property) { cout<<"("; for (PropertySet::const_iterator it=property.begin(); it!=property.end(); it++) { cout<<*it<<", "; } cout<<")\n"; } void displayDataSet(const DataSet& dataset) { for (int i=0; i<CategoryCount; i++) { cout<<propertyName[i]<<" "; } cout<<"goal\n"; for (DataSet::const_iterator it=dataset.begin(); it!=dataset.end(); it++) { displayProperty(*it); } }
กก
How to run?
alternative bar Friday hungry patron price rain reservation type estimate goal (no, no, no, no, none, $, no, no, thai, 0-10, no, ) (no, no, no, yes, some, $$, yes, yes, thai, 0-10, yes, ) (no, yes, no, no, none, $, yes, no, burger, 0-10, no, ) (no, yes, no, no, some, $, no, no, burger, 0-10, yes, ) (no, yes, no, yes, some, $$, yes, yes, italian, 0-10, yes, ) (no, yes, yes, no, full, $, yes, no, burger, >60, no, ) (yes, no, no, yes, full, $, no, no, thai, 30-60, no, ) (yes, no, no, yes, some, $$$, no, yes, french, 0-10, yes, ) (yes, no, yes, no, full, $$$, no, yes, french, >60, no, ) (yes, no, yes, yes, full, $, no, no, thai, 10-30, yes, ) (yes, yes, yes, yes, full, $, no, no, burger, 30-60, yes, ) (yes, yes, yes, yes, full, $$$, no, yes, italian, 10-30, no, ) the decomposite on property of patron partition is: alternative bar Friday hungry patron price rain reservation type estimate goal (no, no, no, no, none, $, no, no, thai, 0-10, no, ) (no, yes, no, no, none, $, yes, no, burger, 0-10, no, ) alternative bar Friday hungry patron price rain reservation type estimate goal (no, no, no, yes, some, $$, yes, yes, thai, 0-10, yes, ) (no, yes, no, no, some, $, no, no, burger, 0-10, yes, ) (no, yes, no, yes, some, $$, yes, yes, italian, 0-10, yes, ) (yes, no, no, yes, some, $$$, no, yes, french, 0-10, yes, ) alternative bar Friday hungry patron price rain reservation type estimate goal (no, yes, yes, no, full, $, yes, no, burger, >60, no, ) (yes, no, no, yes, full, $, no, no, thai, 30-60, no, ) (yes, no, yes, no, full, $$$, no, yes, french, >60, no, ) (yes, no, yes, yes, full, $, no, no, thai, 10-30, yes, ) (yes, yes, yes, yes, full, $, no, no, burger, 30-60, yes, ) (yes, yes, yes, yes, full, $$$, no, yes, italian, 10-30, no, ) the decomposite on property of estimate partition is: alternative bar Friday hungry patron price rain reservation type estimate goal (no, yes, yes, no, full, $, yes, no, burger, >60, no, ) (yes, no, yes, no, full, $$$, no, yes, french, >60, no, ) alternative bar Friday hungry patron price rain reservation type estimate goal (yes, no, no, yes, full, $, no, no, thai, 30-60, no, ) (yes, yes, yes, yes, full, $, no, no, burger, 30-60, yes, ) alternative bar Friday hungry patron price rain reservation type estimate goal (yes, no, yes, yes, full, $, no, no, thai, 10-30, yes, ) (yes, yes, yes, yes, full, $$$, no, yes, italian, 10-30, no, ) the decomposite on property of alternative partition is: alternative bar Friday hungry patron price rain reservation type estimate goal (yes, no, no, yes, full, $, no, no, thai, 30-60, no, ) (yes, yes, yes, yes, full, $, no, no, burger, 30-60, yes, ) the decomposite on property of hungry partition is: alternative bar Friday hungry patron price rain reservation type estimate goal (yes, no, no, yes, full, $, no, no, thai, 30-60, no, ) (yes, yes, yes, yes, full, $, no, no, burger, 30-60, yes, ) the decomposite on property of reservation partition is: alternative bar Friday hungry patron price rain reservation type estimate goal (yes, no, no, yes, full, $, no, no, thai, 30-60, no, ) (yes, yes, yes, yes, full, $, no, no, burger, 30-60, yes, ) the decomposite on property of Friday partition is: alternative bar Friday hungry patron price rain reservation type estimate goal (yes, no, no, yes, full, $, no, no, thai, 30-60, no, ) alternative bar Friday hungry patron price rain reservation type estimate goal (yes, yes, yes, yes, full, $, no, no, burger, 30-60, yes, ) the decomposite on property of alternative partition is: alternative bar Friday hungry patron price rain reservation type estimate goal (yes, no, yes, yes, full, $, no, no, thai, 10-30, yes, ) (yes, yes, yes, yes, full, $$$, no, yes, italian, 10-30, no, ) the decomposite on property of hungry partition is: alternative bar Friday hungry patron price rain reservation type estimate goal (yes, no, yes, yes, full, $, no, no, thai, 10-30, yes, ) (yes, yes, yes, yes, full, $$$, no, yes, italian, 10-30, no, ) the decomposite on property of reservation partition is: alternative bar Friday hungry patron price rain reservation type estimate goal (yes, no, yes, yes, full, $, no, no, thai, 10-30, yes, ) alternative bar Friday hungry patron price rain reservation type estimate goal (yes, yes, yes, yes, full, $$$, no, yes, italian, 10-30, no, ) Press any key to continue