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