fptree.cpp

数据挖掘中的一个很重要的算法

/*----------------------------------------------------------------------
  File    : fptree.cpp
  Contents: fpgrowth algorithm for finding frequent sets
  Author  : Bart Goethals
  Update  : 08/04/2003 - single prefix path bug fixed (Thanks to Xiaonan Wang)
  ----------------------------------------------------------------------*/

#include <iostream>
#include <stdio.h>
#include <set>
using namespace std;
#include "data.h"
#include "item.h"
#include "fptree.h"

int *FPtree::remap = 0;
set<Element> *FPtree::relist = 0;

FPtree::FPtree()
{
  root = new set<Item>;
  nodes = 0;
  singlepath=true;
}

FPtree::~FPtree()
{
  set<Item>::iterator it;

  for(it = root->begin(); it != root->end(); it++)
    it->removeChildren();
  delete root;
}

int FPtree::processItems(Transaction *t, int times)//times计算支持数
{
  set<Item>::iterator head;
  int added=0;

  for(int depth=0; depth < t->length; depth++) 
  {
    head = header.find(Item(t->t[depth], 0));
    if(head == header.end())
	{
      head = header.insert(Item(t->t[depth], 0)).first;//构造Item对象，仅赋值id
      added++;
    }
    head->Increment(times);
  }

  return added;
}

int FPtree::processTransaction(Transaction *t, int times)
{
  set<Item>::iterator it, head;
  set<Item>* items = root;
  Item_ *current = 0;
  int added=0;
	
  for(int depth=0; depth < t->length; depth++) 
  {
    head = header.find(Item(t->t[depth], 0));
    if(head != header.end()) 
	{
      it = items->find(Item(t->t[depth], 0));//root集合中有无项

      if(it == items->end()) 
	  {
		it = items->insert(Item(t->t[depth], current)).first;//fp树无该节点，则创建该节点 
		it->setNext(head->getNext());
		head->setNext(it->getItem());//数据结构中的链表添加节点
		nodes++;
		added++;
		if(singlepath && (items->size()>1)) singlepath=false; 	//判断节点数大于1或单路径为真	
      }

      it->Increment(times);
      current = it->getItem();
      items = it->makeChildren();//替换root集合，即遍历字节点
    }
  }

  return added;
}

int FPtree::grow(int *current, int depth)
{
  int added=0, factor=1;
  if(header.size() == 0) return 0;

  if(singlepath) //
  { 
    int *comb = new int[header.size()];
    int cl=0;
    for(set<Item>::iterator it=header.begin(); it != header.end(); it++) 
	{
      current[depth-1] = it->getId(); 
      print(current,depth,comb,cl,it->getSupport());
      comb[cl++] = it->getId();
      added += factor;
      factor *= 2;
    }
    delete [] comb;
  }
  else 
  {
    for(set<Item>::iterator it=header.begin(); it != header.end(); it++) 
	{
      Item_ *i;
      current[depth-1] = it->getId(); 
      FPtree *cfpt = new FPtree();
      cfpt->setMinsup(minsup);
      cfpt->setOutput(out);

      int *tmp = new int[header.size()];
      for(i = it->getNext(); i != NULL; i = i->nodelink) 
	  {
		int l=0;
		for(Item_ *p=i->parent; p; p = p->parent)
		{
			tmp[l++] = p->id;
		}
		Transaction *t = new Transaction(l);
		for(int j=0; j<l; j++) 
		{
			t->t[j] = tmp[l-j-1];
		}
		cfpt->processItems(t,i->supp);
		delete t;
      }
      cfpt->Prune();
      for(i = it->getNext(); i; i = i->nodelink)
	  {
		int l=0;
		for(Item_ *p=i->parent; p; p = p->parent)
		{
			tmp[l++] = p->id;
		}
		Transaction *t = new Transaction(l);
		for(int j=0; j<l; j++)
		{
			t->t[j] = tmp[l-j-1];
		}
		cfpt->processTransaction(t,i->supp);
		delete t;
      }
      delete [] tmp;
      print(current,depth,0,0,it->getSupport());
      added ++;
      added += cfpt->grow(current,depth+1);
      delete cfpt;
    }
  }
  return added;
}

int FPtree::Prune()
{
  int left=0;
	
  for(set<Item>::iterator it = header.begin();it != header.end(); ) 
  {
    if(it->getSupport() < minsup) 
	{
      set<Item>::iterator tmp = it++;
      header.erase(tmp);
    }
    else 
	{
      left++;
      it++;
    }
  }
  return left;
}

void FPtree::ReOrder()
{
  set<Item>::iterator itI;//集合中项的类型定义的对象，可以操作集合读写
  multiset<Element>::iterator itE;
  multiset<Element> list;
	
  for(itI = header.begin(); itI != header.end(); itI++)
    list.insert(Element(itI->getSupport(), itI->getId()));
	
  remap = new int[list.size()+1];
  relist = new set<Element>;
  header.clear();
  int i=1;
  for(itE=list.begin(); itE!=list.end(); itE++)
  {
    if(itE->support >= minsup) 
	{
      remap[i] = itE->id;//频繁1-项集的序号
      relist->insert(Element(itE->id,i));//？
      Item a(i,0);//构造函数中参数i代表id，0代表父结点
      itI = header.insert(a).first;//header保存值由候选1-项集变为频繁1-项集
      itI->Increment(itE->support);//itE的支持数输入itI
      i++;
    }
  }
}

void FPtree::print(int *itemset, int il, int *comb, int cl, int support, int spos, int depth, int *current)
{
  if(current==0)
  {
    if(out) 
	{
      set<int> outset;
      for(int j=0; j<il; j++) outset.insert(remap[itemset[j]]); 
      for(set<int>::iterator k=outset.begin(); k!=outset.end(); k++) fprintf(out, "%d ", *k);
      fprintf(out, "(%d)\n", support);
      if(cl) 
	  {
		current = new int[cl];
		print(itemset,il,comb,cl,support,0,1,current);
		delete [] current;
      }
    }
  }
  else {
    int loper = spos;
    spos = cl;
    while(--spos >= loper) 
	{
      set<int> outset;
      current[depth-1] = comb[spos];//
      for(int i=0; i<depth; i++) outset.insert(remap[current[i]]); 
      for(int j=0; j<il; j++) outset.insert(remap[itemset[j]]); 
      for(set<int>::iterator k=outset.begin(); k!=outset.end(); k++) fprintf(out, "%d ", *k);
      fprintf(out, "(%d)\n", support);
      print(itemset, il, comb, cl, support, spos+1, depth+1, current);
    }
  }
}