hashtree.cpp

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

// HashTree.cpp: implementation of the CHashTree class.
//
//////////////////////////////////////////////////////////////////////
#include "hashTree.h"
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CHashTree::CHashTree()
{

    root = newnode(LEAF);
    return;

}

CHashTree::~CHashTree()
{

    freenode(root);
    root = (HashNode *)NULL;
    return;

}

//  Produces a hash code for a item set.
int CHashTree::hash(itemSet *itemset, int level)
{

    return((int)(itemset->get(level) % TABLE_SIZE)); //得到指定位置level的小项,然后hash

}


/* creates a new cell accordint to the desired type (t) and fill it with null values*/
HashNode* CHashTree::newnode(int nodetype)
{
    HashNode *node;

    node = (HashNode*) new HashNode();
    node->nodetype = nodetype;
    
    if (nodetype == INTERNAL)
    {
        for (int i = 0; i < TABLE_SIZE; i++)
            node->vp.tab[i] = (HashNode *)NULL;   //生成子节点
    }
    else
    {
		node->vp.largeset= (list *)new list();         //做为叶结点，没有孩子，而是存放项集
    }

    return(node);
};



/* free the sub hash tree with the root node */
void CHashTree::freenode(HashNode *node)
{

    if (node->nodetype == INTERNAL)
    {
        for (int i = 0; i < TABLE_SIZE; i++)			//级联删除
        {
            if(node->vp.tab[i] != (HashNode *)NULL)
                freenode(node->vp.tab[i]);
        }
    }
    else
        delete node->vp.largeset;

    delete node;

    return;
}


/*inserts a new itemset - s in the hash tree - cp according to the level lev*/
void CHashTree :: insert( HashNode **hp, itemSet *s, int level )
{
    HashNode *c1;
    HashNode *head = (HashNode *) *hp;
    list *prev;
    itemSet *pset;
    int i;

    s->support(0);                        //支持度设为0

    if (head == (HashNode *)NULL)       //在一个空的叶子节点中插入itemset
    {
        head = newnode(LEAF);
        head->vp.largeset->add(s);     //把itemset放到这个空的list中
    }
    else if(head->nodetype == INTERNAL)
    {
        c1 = head->vp.tab[hash(s, level)];       //如果不是叶子节点，则对s的第level个小项hash，再进行递归的插入
        insert(&c1, s, level+1);				//递归
    }
    else if( (head->vp.largeset->size() < BUCKET_SIZE) || (level >= (s->size() - 1)) )  //当前叶子节点中已经有存放的itemset，而且还有空间存放
    {																					//或者已经不能再hash了
        head->vp.largeset->add(s);
    }
    else																//head->vp.largeset->size() > BUCKET_SIZE
    {
        prev = head->vp.largeset;

        for (i = 0; i < TABLE_SIZE; i++)
            head->vp.tab[i] = (HashNode *)newnode(LEAF);       //从head向下再生成一层

        head->nodetype = INTERNAL;                            //修改head类型

        for(i = 0; i < prev->size(); i++)
        {
            pset = (itemSet *)prev->get(i);					//找到list的第i个itemSet
            c1 = head->vp.tab[hash(pset, level)];           //找到hash后对应的子节点
            c1->vp.largeset->add((itemSet *)pset->clone());   //子叶结点上插入相应的itemSet
        }

        delete prev;                                         //释放空间
        c1 = head->vp.tab[hash(s, level)];                  //再将给定的itemSet放到相应的新生成的叶子中
        c1->vp.largeset->add(s);
    }
    
    return;
}



/* increments the counts of each subset of transaction t which are in the hash tree cp (candidate sets)*/
void CHashTree :: subset(HashNode *head, itemSet *t, int m)  //t is a transaction itemSet
{
    itemSet *node;
    itemSet *visited;
    int i;
	Item j;                          //j是小项，所以类型最好不要是 int ，改成Item ****************************8

    if(m >= t->size())
        return;

    if(head != (HashNode *)NULL)
    {
        if (head->nodetype == INTERNAL ) 
        {
            visited = new itemSet();

            for (i = m; i < t->size(); i++)
            {
                j = t->get(i);                 //j is the ith item in itemSet t;
                j = j%TABLE_SIZE;				//hash
                if(visited->indexOf(j) < 0)      ///itemSet->indexOf(Item true),若这个小项j并不在visited里面，则添加之!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
                {					
                    visited->add(j);
                    subset(head->vp.tab[(int)j], t, i+1);   //递归，下个位置
                }
            }

            delete visited;
        }
        else
        {
            for(i = 0; i < head->vp.largeset->size(); i++)
            {
                node = (itemSet *)head->vp.largeset->get(i);   //遍历list中的每个itemSet，
        
                if((node->compare(t) == MAKEUP) || (node->compare(t) == TOTALEQUAL))  //满足条件，更改支持度
                    node->support(node->support() + 1);
            }
        }
    }

    return;
}





/* 
   traverses the hash tree - cp, collects the itemsets in a list of itemsets - p1
   and frees the cells of the hash trees********** stands for go and release
*/
//找到给定树中支持度大于等于minsup的所有itemSet，并放到result中,利用递归的方法
void  CHashTree :: scan(HashNode *head, list *result, long minsup) 
{
    itemSet *node;
    int i;
    
    if(head == (HashNode *)NULL)
        return;

    if(head->nodetype == INTERNAL)
    {
        for (i = 0; i < TABLE_SIZE; i++)
            scan(head->vp.tab[i], result, minsup);
    }
    else
    {
        for(i = 0; i < head->vp.largeset->size(); i++)
        {
            node = (itemSet *)head->vp.largeset->get(i);

            if(node->support() >= minsup)
                result->add((itemSet *)node->clone());
        }
    }
    
    return;
}