Code: [Select]


#include "Apriori.h"

using namespace std;

/* FUNCTION: Apriori()
*  PURPOSE: Basic constructor
*  =========================================================== */
Apriori::Apriori()
{
L = new Queue<LinkedList<Item>>;
C = new Queue<LinkedList<Item>>;
}

void Apriori::appendItemsets(Item& item1, Item& item2, LinkedList<Item>& newFrequentItemset)
{
//This will be called in a loop, going through the list of frequent n itemsets
//Ex: 3-itemsets: check if the mDataArray[0] and [1] match between the 2 items
if(headersMatch(item1, item2, item1.getSize() - 1)) //Compare the headers (loops through all elements except the last one)
{
//Make a new item of size n + 1
Item newItem(item1.getSize() + 1);
//Fill newItem's mDataArray with either one of the original item's contents:
for(int i = 0; i < newItem.getSize() - 2; i++)
{
newItem.mDataArray[i] = item1.mDataArray[i];

}
//Append the last element of item2 to newItem
for (int i = newItem.getSize() - 2; i < newItem.getSize(); i++)
{
if (newItem.getSize() % 2 == 0)
{
if (i % 2 == 0)
newItem.mDataArray[i] = item2.mDataArray[i];
else
newItem.mDataArray[i] = item1.mDataArray[i - 1];
}
else
{
if (i % 2 == 0)
newItem.mDataArray[i] = item2.mDataArray[i - 1];
else
newItem.mDataArray[i] = item1.mDataArray[i];
}
}

newFrequentItemset.insert(newItem); //Add the item to the new frequent itemset
}
}

LinkedList<Item>* Apriori::apriori_gen(LinkedList<Item>* originalList)
{
timer.startClock();

LinkedList<Item> *newItemset = new LinkedList<Item>();

for (int i = 0; i < originalList->getCount(); i++)
{
Item temp1, temp2;

temp1 = originalList->getData(i);

for (int j = i + 1; j < originalList->getCount(); j++)
{
temp2 = originalList->getData(j);

appendItemsets(temp1, temp2, *newItemset);
}
}

countFrequency(newItemset);

prune(newItemset);

timeString = timer.getTime();

OutputResults(newItemset);

return newItemset;
}

void Apriori::calcMinSupport(float thresholdPercent, int numTransactions)
{
mMinSupport = (int)(numTransactions * (thresholdPercent / 100));
}


bool Apriori::transactionContains(Item theItem, LinkedList<int>& theTransaction)
{
int frequency = 0;

for(int j = 0; j < theItem.getSize(); j++) //Loop through the Itemset
{
if(theTransaction.isExist(theItem.mDataArray[j]))
{
frequency++; //Find out how many items in the transaction are in the itemset
}
}
if(frequency < theItem.getSize()) //If frequency isn't as big as the itemset, it went through the transaction and couldn't find all of the itemset's contents
{
return false;
}

return true;

}

void Apriori::countFrequency(LinkedList<Item> *tmpItemList)
{

for(int i = 0; i < tmpItemList->getCount(); i++) //Loop through every item in the set
{
for(int j = 0; j < mNumTransactions; j++) //Loop through all of the transactions
{
if(transactionContains(tmpItemList->getData(i), mTransactions[j]))
{
tmpItemList->getData(i).increaseFrequency();
}

}

}

}


LinkedList<Item>* Apriori::genOneItemsets()
{
timer.startClock();

LinkedList<Item> *Ltemp = new LinkedList<Item>();; //Stores unique item structures

Item *Itemp; //Dynamically allocated Item to popullate Ltemp with

bool found = false; //Used to tell whether or not a number from mDataSet is unique or not
int index; //Index at where a non-unique number can be "placed" in Ltemp

for (int i = 0; i < mNumTransactions; i++) //Runs through entire mDataSet list
{
for (int j = 0; j < mTransactions[i].getCount(); j++)
{
if (Ltemp->getCount() == 0) //If Ltemp is empty
{
if (mTransactions->getCount() == 0) //If mDataset is empty
{
return Ltemp; //Empty list
}

else
{
//Initialization of new dynamically allocated Item
Itemp = new Item(1);
Itemp->append(mTransactions[i].getData(j));
Itemp->increaseFrequency();

//Inserts new Item into Ltemp
Ltemp->insert(*Itemp);
}
}

else
{
for (int k = 0; k < Ltemp->getCount(); k++) //Runs through every Item in Ltemp
{
if (Ltemp->getData(k).mDataArray[0] == mTransactions[i].getData(j)) //Compares Ltemp Item numbers with current number in mDataSet
{
found = true;
index = k; //set index to current Item in Ltemp
k = Ltemp->getCount(); //jump out of loop
}
}

if (found)
{
Item temp = Ltemp->getData(index); //increase count
temp.increaseFrequency();
Ltemp->setData(index, temp);
}

else
{
//Initialization of new dynamically allocated Item
Itemp = new Item(1);
Itemp->append(mTransactions[i].getData(j));
Itemp->increaseFrequency();

//Inserts new Item into Ltemp
Ltemp->insert(*Itemp);
}
}
}

//reset found
found = false;
}

prune(Ltemp);

timeString = timer.getTime();

OutputResults(Ltemp);

return Ltemp;
}

LinkedList<Item>* Apriori::genTwoItemsets(LinkedList<Item>* tmpList)
{
timer.startClock();

Item *templateItem = new Item(2);
LinkedList<Item>* setArray = new LinkedList<Item>;

for (int i = 0; i < tmpList->getCount(); i++)
{
for (int j = i + 1; j < tmpList->getCount(); j++)
{
templateItem->mDataArray[0] = tmpList->getData(i).mDataArray[0];
templateItem->mDataArray[1] = tmpList->getData(j).mDataArray[0];
setArray->insert(*templateItem);
templateItem = new Item(2);
}
}

countFrequency(setArray);

prune(setArray);

timeString = timer.getTime();

OutputResults(setArray);

return setArray;
}

void Apriori::GetInput()
{
LinkedList<int> tmp;
string filename, filenameData, filenameInfo;
float thresholdPercent;

// First have the user input the dataset filename and the minimum threshold percent
cout << "Enter input file name (w/o file extension): ";
cin >> filename;
cout << "Enter minimum threshold percent: ";
cin >> thresholdPercent;


cout << "Enter output file name (w/o file extension):";
cin >> outputFile;

outputFile = outputFile + ".txt";
output.open(outputFile);

// The .dat file is the actual data, .input is the information about the data
filenameData = filename + ".dat";
filenameInfo = filename + ".input";


ifstream input;
input.open(filenameInfo);

int averageTransLength, numUniqueItems, numTransactions;

// retrieve info from .input file
input >> averageTransLength;
input >> numUniqueItems;
input >> numTransactions;

mTransactions = new LinkedList<int>[numTransactions];

input.close();

input.open(filenameData);

mNumTransactions = numTransactions;

calcMinSupport(thresholdPercent, numTransactions);

int i = 0;

// Load everything from .dat into a LinkedList in the Apriori class
if(input.good())
{
string temp;
while (!input.eof()) //!input.eof()
{
input >> temp;

tmp.insert(atoi(temp.c_str()));

mTransactions[i].insert(atoi(temp.c_str()));

if (input.peek() == '\n')
{
i++;
}
}

input.close();
}
else if(input.fail())
{
cout << "\nERROR READING FROM FILE\n";
}
}

bool Apriori::headersMatch(Item& item1, Item& item2, int headerSize)
{
for (int i = 0; i < headerSize; i++)
{
if(item1.mDataArray[i] != item2.mDataArray[i])
return false;
}
return true;
}

void Apriori::OutputResults(LinkedList<Item>* itemset)
{
if(output.good() && !itemset->isEmpty())
{
Item* tmp = new Item(itemset->getData(0).getSize());
for (int i = 0; i < itemset->getCount(); i++)
{
*tmp = itemset->getData(i);
output << *tmp << endl; //Write the item's contents on one line
}
output << "Time: " << timeString << endl;
}
}

void Apriori::prune(LinkedList<Item> *itemset)
{
for (int i = 0; i < itemset->getCount(); i++)
{
if (itemset->getData(i).getFrequency() < mMinSupport)
{
itemset->removeElementAt(i);
i--;
}
}
}

void Apriori::RunAlgorithm()
{
// put the frequent 1-itemsets into L
L->enqueue(genOneItemsets());

L->enqueue(genTwoItemsets(L->dequeue()));

while (L->mHead->mData.getCount() != 0) // this process will repeat until the pruning of C finds nothing frequent, at which point we have found all of our frequen itemsets
{
// take the current itemset, and in apriori_gen find all of its subsets, and then put that set of subsets into C
// in apriori_gen remember to call OutputResults(*1-itemset*) and append the time taken onto timeStrings, so that we have a record of it in our output file
C->enqueue(apriori_gen(L->dequeue()));

// prune C so that only the items that meet the min support remain, then put that into L
L->enqueue(C->dequeue());

}

output.close();
}
Bitches love data structures.