densitymap.c

Entropy-based CLIQUE算法改进

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include "Param.h"
#include "NPoint.h"
#include "NArray.h"
#include "IntList.h"
#include "HashTree.h"
#include "DensityMap.h"
#include "HashForest.h"

// Constructor
// Set subspaces in the DensityMap using a HashTree
DensityMap::DensityMap(const Param& prm, const HashTree& ht)
:total_dim(prm.dim)
{
  cur_dim = ht.get_dim();
  ht.convert2array(ss,no_ss);
  
  na = new NArray(cur_dim, prm);
}

// Destructor
DensityMap::~DensityMap()
{
  delete[] ss;
  delete na;
}

// Set a subspace in the DensityMap
void DensityMap::setSubspace(int i, const IntList& s)
{
  ss[i].copy(s);
}

// Read cluster file and build grid
void DensityMap::build_grid(float** dataset, HashForest& hf, HashTree& ht)
{
  NPoint rp(cur_dim);    // reduced vector
  int i,j,count; 

  assert(READ_ONCE);
  
  // Process subspace by subspace
  for (i=0; i<no_ss; i++) {
    na->clear();

    // Process row by row
    for (count = 0; count < hf.get_data_row(); count++) {
      // Project the complete vector to reduced vector
      for (j=0; j<ss[i].get_len(); j++)
        rp[j] = dataset[count][ss[i][j]];

      na->inc_value(rp); // Increase the count for reduced vector
    }
    cal_stat(i,hf,ht);  // calculate the stat from the grid
  }
}

// Calculate the entropy of all subspaces under counting
void DensityMap::cal_stat(int ss_no, HashForest& hf, HashTree& ht)
{
  int i,j;
  EntStat es;
  IntList tmp_ss;
  float tmp_interest, max_interest;

  assert(cur_dim == ht.get_dim());
  
  i = ss_no;  // We now process only the subspace with ss_no
  
  // Calculate entropy                                                       
  es.entropy = na->cal_entropy();                                            
                                                                             
  // Calculate interest                                                      
  if (cur_dim==1)                                                            
    es.interest = 0;                                                         
  else {                                                                     
    es.interest = -es.entropy;                                               
    for (j=0; j<ss[i].get_len(); j++)                                        
      es.interest += hf.entropy_dim(ss[i][j]);                               
  }                                                                          
                                                                             
  // Calculate interest gain                                                 
  if (cur_dim==1)                                                            
    es.interest_gain = 0;  // it is 0 by definition                          
  else {                                                                     
    // For higher dimensions,wWe need to find the highest entropy among      
    // the k-1 projection                                                    
    max_interest = 0;                                                        
    for (j=0; j<ss[i].get_len(); j++) {                                      
      tmp_ss.copy(ss[i]);                                                    
      tmp_ss.remove(j);                                                      
      tmp_interest = hf.findStat(tmp_ss).interest;                           
      if (tmp_interest > max_interest) {                                     
        max_interest = tmp_interest;                                         
      }                                                                      
    }                                                                        
    // Calculate interest gain                                               
    es.interest_gain = es.interest - max_interest;                           
  }                                                                          
                                                                             
  ht.setStat(ss[i],es);  // Store the calculated stat in the hash tree
}