itemset.cpp

数据挖掘中的经典算法Apriori实现

//
// Implementation of itemSet class
//
//
#include <stdio.h>
#include <stdlib.h>
#include "itemSet.h"
//#include "items.h"

//---------------------------------------------------------------------------
//    itemSet Methods
//---------------------------------------------------------------------------

void itemSet::add(Item theitem)    //这里应当是增加一个新的小项，直接放到后边就是有序的,keeporder
{
    Item *newitems;
    int i;

    if(!m_keeporder && (indexOf(theitem) >= 0))     //what is indexOf(theitem)???？？？？？？？？？？？？？？？？
        return;

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

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

    m_items = newitems;
    count++;

    return;
}



void itemSet::add(int index, Item theitem)                    //在第几个位置（index）插入小项
{
    Item *newitems;
    int i;

    if(!m_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;
}


void itemSet::concat(itemSet *src)    //合并两个项集，这样合并以后还是有序的吗？
{

	for(int i = 0; i < src->size(); i++)
        add(src->get(i));

    return;
}


void itemSet::clear()           //清空
{
    if(m_items != (Item *)NULL)
        delete m_items;
    m_items = (Item *)NULL;

    count = 0;
    m_support = 0;
    m_weight = 0.0;
}


items *itemSet::clone()    ///deep clone
{
    itemSet *theclone;
    int i;

    theclone = (itemSet *) new itemSet();
	theclone->keeporder(m_keeporder);

    for (i = 0; i < count; i++)
        theclone->add(m_items[i]);

    theclone->support(m_support);
    theclone->weight(m_weight);

    return(theclone);
}


int itemSet::compare(items *item)                    //判断两个项集的关系：相同，根本不同（相互没有交叉小项），组成（当前）
{                                                   //项集是给定项集的子集，交叉（有共同的小项，但不完全相同）
    itemSet *theother = (itemSet *)item;
    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->size(); j++)
        {
            if(m_items[srcp] == theother->get(j))
            {
                numFound++;
                targetp = j;
                found = true;
                break;
            }
        }

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

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

    return result;
}



Item itemSet::get(int index)      //得到指定位置的小项
{

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


int itemSet::indexOf(Item theitem, bool ascend)   //从升序还是降序对给定的小项定位
{
	int i;

	if(ascend)
	{
	    for(i = 0; i < count; i++)
		{
			if(m_items[i] == theitem)
				return i;
	    }
	}
	else
	{
	    for(i = count-1; i >= 0; i--)
		{
			if(m_items[i] == theitem)
				return i;
		}
	}

    return(-1);
}


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);

}



itemSet * itemSet::left(int nCount)    //提取出项集的前nCount个小项组成的项集
{
    itemSet *result = (itemSet *)NULL;

    if((nCount >= 0) && (nCount < count))
    {
        result = (itemSet *) new itemSet();
        for(int i = 0; i < nCount; i++)
            result->add(m_items[i]);
    }

    return result;
}





itemSet * itemSet::sub(int bgn, int end)   //提取出bgn与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(m_items[i]);
    }

    return result;
}



itemSet * itemSet::substract(itemSet *aset)  //返回当前项集中除了aset项集以外的小项组成的子项集
{
    itemSet *result;
    int pos, oneitem;

    result = (itemSet *)clone();     

    for(int i = 0; i < aset->size(); i++)
    {
        oneitem = aset->get(i);
        pos = result->indexOf(oneitem);
        if(pos >= 0)
            result->remove(pos);
    }

    return(result);
}


void itemSet::dump()       //输出项集里的所有小项（整数）
{
    for(int i = 0; i < count; i++)
        printf(" %d ", m_items[i]);

    printf("\n");
}