itemset.cpp

关联规则挖掘数据产生程序.VISUAL C++ 可产生满足要求的挖掘数据.

// ItemSet.cpp: implementation of the ItemSet class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "ItemSet.h"

#include <iomanip.h>

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

//------------------------------- ItemSet -------------------------------


ItemSet::ItemSet(int num_items, 	// number of items
		 Taxonomy *ptax		// taxonomy (optional)
		 )
  : tax(ptax), nitems(num_items)
{
  ExpDist freq;
  int i, j;

  cum_prob = new float [nitems];
  if (tax)
    tax_prob = new float [nitems];
  else
    tax_prob = NULL;
  for (i = 0; i < nitems; i++)
    cum_prob[i] = freq();	// prob. that this pattern will be picked

  if (tax) {			// weight(itm) += wieght(children)
    // normalize probabilities for the roots and for children
    normalize(cum_prob, 0, tax->num_roots()-1);
    for (i = 0; i < nitems && tax->num_children(i) > 0; i++)
      normalize(cum_prob, tax->first_child(i), tax->last_child(i));

    // calulate cumulative probabilities for children
    for (i = 0; i < nitems; i++)
      tax_prob[i] = cum_prob[i];
    for (i = 1; i < nitems; i++)
      if (tax->num_children(i) > 0)
	for (j = tax->first_child(i); j < tax->last_child(i); j++)
	  tax_prob[j+1] += tax_prob[j];

    // set real probabilities
    for (i = tax->num_roots(); i < nitems; i++)
      cum_prob[i] *= cum_prob[ tax->parent(i) ] * tax->depth_ratio();
  }

  // normalize probabilites (why -- see get_pat)
  normalize(cum_prob, 0, nitems-1);
  for (i = 1; i < nitems; i++)	// calulate cumulative probabilities
    cum_prob[i] += cum_prob[i-1];
}


ItemSet::~ItemSet()
{
  delete [] cum_prob;
}


//  normalize probabilities between low and high
//
void ItemSet::normalize(float prob[], int low, int high)
{
  float tot;
  int i;

  // normalize probabilites
  tot = 0;
  for (i = low; i <= high; i++)
    tot += prob[i];
  for (i = low; i <= high; i++)
    prob[i] /= tot;
}


// returns a pattern chosen at random
//
int ItemSet::get_item(void)
{ 
  float r;
  int i;

  // find the desired pattern using cum_prob table
  r = rand();
  // want item i such that cum_prob[i-1] < r <= cum_prob[i];
  i = r * nitems;			// guess location of item
  i += (r-cum_prob[i]) * nitems;	// refine guess
  if (i >= nitems)			// check boundaries
    i = nitems-1;
  if (i < 0)
    i = 0;
  while ( i < (nitems-1) && r > cum_prob[i] )	// find item
    i++;
  while ( i > 0 && r <= cum_prob[i-1] )
    i--;
  return i;
};


// if no taxonomy, returns itm
//
int ItemSet::specialize(int itm)
{
  float r;
  int i, nchildren;
  int first, last;

  if (!tax) 		// no taxonomy
    return itm;

  nchildren = tax->num_children(itm);
  if (nchildren == 0)		// no children
    return itm;  

  first = tax->child(itm, 0);
  last = tax->child(itm, nchildren-1);

  // find the desired pattern using cum_prob table
  r = rand();
  i = first + r * nchildren;
  if (i == last)
    i--;
  while ( i < last && r > tax_prob[i] )
    i++;
  while ( i > first && r < tax_prob[i-1] )
    i--;
  return specialize(i);
}  


float ItemSet::weight(int itm)	// returns prob. of choosing item
{
  if (itm == 0)
    return cum_prob[itm];
  else
    return cum_prob[itm] - cum_prob[itm-1];
}


void ItemSet::display(ofstream &fp)
{
//  if (tax != NULL)
//    tax->display(fp);

  fp << "Items:" << endl;
  fp << setprecision(3);

  if (tax != NULL) {
    if (cum_prob[0] * nitems > 10)
      fp << 0 << "  " << cum_prob[0] * nitems << " "
	<< tax->first_child(0) << " " << tax->last_child(0) << endl;
    for (int i = 1; i < nitems; i++)
      if ((cum_prob[i]-cum_prob[i-1]) * nitems > 10)
	fp << i << "  " << (cum_prob[i]-cum_prob[i-1]) * nitems << " "
	  << tax->first_child(i) << " " << tax->last_child(i) << endl;
  }
  else {
    if (cum_prob[0] * nitems > 5)
      fp << 0 << "  " << cum_prob[0] * nitems << endl;
    for (int i = 1; i < nitems; i++)
      if ((cum_prob[i]-cum_prob[i-1]) * nitems > 5)
	fp << i << "  " << (cum_prob[i]-cum_prob[i-1]) * nitems << endl;
  }

  fp << setprecision(0);
  fp << endl;
}