ID3

              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.
B.The problem
If you are given a database, can you do some induction from the data? One way is by this very old decision-tree algorithms. It is like this:

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 program
กก

This is a rather straight forward, simple, trivial partition problem. However, it gives me a good chance of practicing STL.

D.The major functions
กก
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









                                                               
                      







                       back.gif (341 bytes)       

up.gif (335 bytes)                                       
next.gif (337 bytes)