util.cpp

apriori算法是数据挖掘的经典算法,它基于关联规则的思想.此为我的第3个收藏

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdlib.h>
#include <fcntl.h>
#include <string.h>
#include <sys/types.h>

#include "util.h"



//---------------------------------------------------------------------------
//    ItemSet Methods
//---------------------------------------------------------------------------

void ItemSet::add(Item theitem)
{
    Item *newitems;
    int i;

    if(!keeporder && (indexof(theitem) >= 0))
        return;

    newitems = (Item *) new Item[count+1];

    for(i = 0; i < count; i++)
        newitems[i] = m_items[i];
    newitems[i] = theitem;
    delete m_items;

    m_items = newitems;
    count++;

    return;
}


void ItemSet::clear()
{

    if(m_items != (Item *)NULL)
        delete m_items;
    m_items = (Item *)NULL;

    count = 0;

}



Item ItemSet::remove(int index)
{
    Item *newitems;
    int number = 0;
    Item result = -1;

    newitems = (Item *) new Item[count-1];

    for(int i = 0; i < count; i++)
    {
        if(i != index)
            newitems[number++] = m_items[i];
        else
            result = m_items[i];
    }

    delete m_items;
    m_items = newitems;
    count--;

    return(result);

}


int ItemSet::indexof(Item theitem)
{
    for(int i = 0; i < count; i++)
    {
        if(m_items[i] == theitem)
            return i;
    }

    return(-1);
}


Item ItemSet::itemof(int index)
{

    if((index >= 0) && (index < count))
        return m_items[index];
    else
        return(-1);

}


void ItemSet::insert(int index, Item theitem)
{
    Item *newitems;
    int i;

    if(!keeporder && (indexof(theitem) >= 0))
        return;

    if(index < 0)
        index = 0;
    else if(index >= count)
        index = count;

    newitems = (Item *) new Item[count+1];

    for(i = 0; i < index; i++)
        newitems[i] = m_items[i];
    newitems[index] = theitem;
    for(i = index; i < count; i++)
        newitems[i+1] = m_items[i];

    delete m_items;
    m_items = newitems;

    count++;

    return;
}



ItemSet * ItemSet::clone()
{
    ItemSet *theclone;
    int i;

    theclone = (ItemSet *) new ItemSet();

    if(count > 0)
    {
        theclone->m_items = (Item *) new Item[count];
        for (int i = 0; i < count; i++)
            theclone->m_items[i] = m_items[i];
    }

    theclone->count = count;
    theclone->support = support;

    return(theclone);
}


void ItemSet::cat(ItemSet *src)
{

    for(int i = 0; i < src->count; i++)
        add(src->itemof(i));

    return;
}


ItemSet * ItemSet::sub(int bgn, int end)
{
    ItemSet *result = (ItemSet *)NULL;

    if((bgn >= 0) && (bgn < count) && (end >= 0) && (end < count))
    {
        result = (ItemSet *) new ItemSet();
        for(int i = bgn; i <= end; i++)
            result->add(itemof(i));
    }

    return result;
}


int ItemSet::diff(ItemSet *theother)
{
    int numFound = 0, srcp, targetp, j;
    int result = TOTALDIFF;
    bool found;

    srcp = 0;
    targetp = -1;
    while(srcp < count)
    {
        found = false;
        for(j = targetp+1; j < theother->count; j++)
        {
            if(itemof(srcp) == theother->itemof(j))
            {
                numFound++;
                targetp = j;
                found = true;
                break;
            }
        }

        if(!found)
            break;
        else
            srcp++;
    }

    if(numFound > 0)
    {
        if((numFound == count) && (theother->count == count))
            result = TOTALEQUAL;
        else if((numFound == count) && (count < theother->count))
            result = MAKEUP;
        else
            result = CROSS;
    }

    return result;
}


ItemSet * ItemSet::substract(ItemSet *itemSet)
{
    ItemSet *result;
    int pos, oneitem;

    result = clone();

    for(int i = 0; i < itemSet->count; i++)
    {
        oneitem = itemSet->itemof(i);
        pos = result->indexof(oneitem);
        if(pos >= 0)
            result->remove(pos);
    }

    return(result);
}





//---------------------------------------------------------------------------
//    Class ItemSets

ItemSets::ItemSets()
{
    m_itemsethead = (ItemSetNode *) new ItemSetNode();
    m_itemsethead->next = m_itemsethead;
    m_itemsethead->priori = m_itemsethead;

    cur_pos = 0;
    cur_itemset = m_itemsethead;

    count = 0;
}

ItemSets::~ItemSets()
{
    ItemSetNode *browser;
    ItemSetNode *current;
    
    browser = m_itemsethead->next;
    while(browser != m_itemsethead)
    {
        current = browser;
        browser = browser->next;
        delete(current->m_data);
        delete(current);
    }

    delete m_itemsethead;
}

ItemSet * ItemSets::itemsetof(int order)
{
    ItemSet *result = (ItemSet *)NULL;
    ItemSet *itemsetpoint;

    if((itemsetpoint = pointof(order)) != NULL)
        result = itemsetpoint->clone();

    return(result);
}


ItemSet * ItemSets::pointof(int order)
{
    ItemSetNode *itemhead, *itemtail, *itembgn, *itemcur;
    int headoffset, curoffset, tailoffset, minoffset;
    bool forward;

    if(count == 0)
        return((ItemSet *)NULL);

    if(order < 0)
        order = 0;
    else if(order >= count)
        order = count - 1;

    itemhead = m_itemsethead->next;
    itemtail = m_itemsethead->priori;

    headoffset = order;
    if(headoffset == 0)
        return(itemhead->m_data);

    curoffset = order - cur_pos;
    if(curoffset == 0)
        return(cur_itemset->m_data);

    tailoffset = count - order - 1;
    if(tailoffset == 0)
        return(itemtail->m_data);

    minoffset = imin(headoffset, imin(abs(curoffset), tailoffset));
    if(minoffset == headoffset)
    {
        itembgn = itemhead;
        forward = true;
    }
    else if(minoffset == abs(curoffset))
    {
        itembgn = cur_itemset;
        if(curoffset < 0)
            forward = false;
        else
            forward = true;
    }
    else
    {
        itembgn = itemtail;
        forward = false;
    }

    itemcur = itembgn;
    for(int i = 0; i < minoffset; i++)
    {
        if(forward)
            itemcur = itemcur->next;
        else
            itemcur = itemcur->priori;
    }

    cur_pos = order;
    cur_itemset = itemcur;

    return(itemcur->m_data);
}


ItemSet * ItemSets::add(ItemSet *NewItemSet)
{
    ItemSetNode *newnode;
    ItemSetNode *tail;
    
    if(NewItemSet == (ItemSet *)NULL)
        return NULL;

    newnode = (ItemSetNode *)new ItemSetNode();
    newnode->m_data = NewItemSet->clone();

    tail = m_itemsethead->priori;
    newnode->next = tail->next;
    tail->next = newnode;
    newnode->priori = tail;
    newnode->next->priori = newnode;

    count++;

    return newnode->m_data;
}




ItemSetNode * ItemSets::nodeof(int order)
{
    ItemSetNode *itemhead, *itemtail, *itembgn, *itemcur;
    int headoffset, curoffset, tailoffset, minoffset;
    bool forward;

    if(count == 0)
        return((ItemSetNode *)NULL);

    if(order < 0)
        order = 0;
    else if(order >= count)
        order = count - 1;

    itemhead = m_itemsethead->next;
    itemtail = m_itemsethead->priori;

    headoffset = order;
    if(headoffset == 0)
        return(itemhead);

    curoffset = order - cur_pos;
    if(curoffset == 0)
        return(cur_itemset);

    tailoffset = count - order - 1;
    if(tailoffset == 0)
        return(itemtail);

    minoffset = imin(headoffset, imin(abs(curoffset), tailoffset));
    if(minoffset == headoffset)
    {
        itembgn = itemhead;
        forward = true;
    }
    else if(minoffset == abs(curoffset))
    {
        itembgn = cur_itemset;
        if(curoffset < 0)
            forward = false;
        else
            forward = true;
    }
    else
    {
        itembgn = itemtail;
        forward = false;
    }

    itemcur = itembgn;
    for(int i = 0; i < minoffset; i++)
    {
        if(forward)
            itemcur = itemcur->next;
        else
            itemcur = itemcur->priori;
    }

    cur_pos = order;
    cur_itemset = itemcur;

    return(itemcur);
}


bool ItemSets::remove(int order)
{
    ItemSetNode *opitemset;
    int counter = 0;

    if((opitemset = nodeof(order)) == (ItemSetNode *)NULL)
        return(false);

    if(order < cur_pos)
        cur_pos--;
    else if(order == cur_pos)
    {
        /* if the current itemset is the last one */
        if(cur_pos == count - 1)
            cur_itemset = opitemset->priori;
        else
            cur_itemset = opitemset->next;
    }

    opitemset->next->priori = opitemset->priori;
    opitemset->priori->next = opitemset->next;

    delete opitemset->m_data;
    delete opitemset;

    count--;

    return(true);
}



int ItemSets::indexof(ItemSet *test)
{
    ItemSetNode *itemsethead;
    int counter = 0;

    itemsethead = m_itemsethead->next;
    while(itemsethead != m_itemsethead)
    {
        if(itemsethead->m_data->diff(test) == TOTALEQUAL)
            return(counter);

        counter++;
        itemsethead = itemsethead->next;
    }

    return(-1);
}


void ItemSets::writeto(char *filename)
{
    FILE *fp;
    ItemSetNode *itemsethead;

    fp = fopen(filename,"wt");

    itemsethead = m_itemsethead->next;
    while(itemsethead != m_itemsethead)
    {
        for(int i = 0; i < itemsethead->m_data->count; i++)
            fprintf(fp, " %d ", itemsethead->m_data->itemof(i));

        fprintf(fp, "\n");

        itemsethead = itemsethead->next;
    }

    fclose(fp);
    return;
}

void ItemSets :: cat(ItemSets *Additions)
{
    ItemSet *current;
    ItemSet *exist;

    for(int i = 0; i < Additions->count; i++)
    {
        current = Additions->pointof(i);

        if(indexof(current) < 0)
            add(current);

    }

    return;
}