evaluation.c

C++蚂蚁实现/C++蚂蚁实现 C++蚂蚁实现

/*  Ant-based Clustering
    Copyright (C) 2004 Julia Handl
    Email: [e-mail]

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

*/

#include "evaluation.h"
#include <time.h>

evaluation::evaluation(conf * c) {
    par = c;
    docindex = NULL;


}

evaluation::~evaluation() {

  if (docindex != NULL) {
    for (int i=0; i<par->binsize; i++) {
      delete docindex[i];
    }
    delete [] docindex;
  }

	    

}

void evaluation::init(databin<USED_DATA_TYPE> * b, clustering * cl) {
    bin = b;
    clust = cl;
    docindex = NULL;
}


void evaluation::init(databin<USED_DATA_TYPE> * b, grid * g, clustering * cl, position<double> ** index) {
    bin = b;
    env = g;
    clust = cl;


    if (index != NULL) {
	docindex = index;
    }

    else {
	if (env != NULL) {
	
	    // store the positions for all data elements
	    docindex = new position<double>*[par->binsize];
	    for (int i=0; i<par->binsize; i++) {
		docindex[i] = NULL;
	    }
	    
	    for (int i=0; i<par->imax; i++) {
		for (int j=0; j<par->jmax; j++) {
		    
		    if ((*env)(i,j) != FREE) {
			docindex[(*env)(i,j)] = new position<double>(i,j);
		    }
		    
		}
	    }
	}
        else docindex = NULL;
    }
}


double evaluation::square(double x) {
    return x*x;
}



double evaluation::spatialdistance(position<int> * p1, position<int> * p2, int torus) {
    int dx = abs((*p1)[0]-(*p2)[0]);
    if (torus == TRUE) dx = min(dx, par->imax - dx);
    int dy = abs((*p1)[1]-(*p2)[1]);
    if (torus == TRUE) dy = min(dy, par->jmax - dy);
    return sqrt(square(dx)+square(dy));
}

double evaluation::spatialdistance(position<double> * p1, position<double> * p2, int torus) {
    double dx = abs((*p1)[0]-(*p2)[0]);
    if (torus == TRUE) dx = min(dx, par->imax - dx);
    double dy = abs((*p1)[1]-(*p2)[1]);
    if (torus == TRUE) dy = min(dy, par->jmax - dy);
    return sqrt(square(dx)+square(dy));
}



/****************************************************************************************

 Evaluation measures for unsupervised clustering, i.e. when the real partitions are NOT known 

 - Variance
 - Dunn index

 Both were used in the final experiments
 
****************************************************************************************/


double evaluation::dunn_av() {

    if (clust->num <= 1) {
	//cerr << "Dunn Index cannot be computed for one single cluster" << endl;
	return 0;
    }
    double diam = 0.0;
    double diamold  = 0.0;

    int ** assignment = new int * [clust->num];
    int * ctr = new int[clust->num];


    for (int i=0; i<clust->num; i++) {
    	ctr[i] = 0;
	assignment[i] = new int[par->binsize+1];
	for (int j=0; j<=par->binsize; j++) {
	    assignment[i][j] = FREE;
	}
    }
    for (int i=0; i<par->binsize; i++) {
	int index = (*clust)[i];
	assignment[index][ctr[index]] = i;
	ctr[index]++;
    }

    // find maximum cluster diameter based on average distance
    for (int i=0; i<clust->num; i++) {
	int j = 0;
	diam = 0.0;
	int ctr = 0;
	while (assignment[i][j] != FREE) {
	    int k = j+1;
	    while (assignment[i][k] != FREE) {
		diam += bin->precomputed_d(assignment[i][j],assignment[i][k]);
		ctr++;
		k++;
	    }
	    j++;
	}
	diam /= double(ctr);

	diam = max(diam, diamold);
	diamold = diam;
    }

    // find minimal cluster distance
    double mind = 0;
    for (int i=0; i<clust->num; i++) {
	data<USED_DATA_TYPE> di(par, clust->centres[i]);
	for (int j=0; j<i; j++) {
	    data<USED_DATA_TYPE> dj(par, clust->centres[j]);
	    if ((i == 1) && (j == 0)) mind = di.distanceto(dj) / par->max;
	    mind = min(mind, di.distanceto(dj) / par->max);
	}
    }

    for (int i=0; i<clust->num; i++) {
      delete [] assignment[i];
    }
    delete [] assignment;
    delete [] ctr;



    return mind / diam;
}



double evaluation::variance() {

    double * var = new double[clust->num];
    int * ctr = new int[clust->num];

    // initialisation

    for (int i=0; i<clust->num; i++) {
	var[i] = 0.0;
	ctr[i] = 0;
    }

    for (int i=0; i<par->binsize; i++) {

	double diff = 0.0;
	int p = clust->partition[i];
	data<USED_DATA_TYPE> di(par, clust->centres[p]);

	diff = (*bin)[i].distanceto(di);
	var[p] += diff*diff;
    }

   
    double totalvariance = 0.0;
    for (int i=0; i<clust->num; i++) {
	totalvariance += var[i];

    }
    totalvariance /= double(par->binsize);
    
    delete [] var;
    delete [] ctr;

    return sqrt(totalvariance);
}



/****************************************************************************************

 Evaluation measures for supervised clustering, i.e. when the real partitions are known 

 - Number of identified clusters
  - F-Measure
 - Rand-Index

 In the final experiments only the F-Measure and the Rand-Index were used.
 
****************************************************************************************/


double evaluation::number() {
    return double(clust->num);
}

double evaluation::clusternumber() {
    return double(clust->num);
}
 

double evaluation::fmeasure(int b) {

    int ** assignments = new int* [clust->num];
    for (int i=0; i<clust->num; i++) {
	assignments[i] = new int [par->kclusters];
	for (int j=0; j<par->kclusters; j++) {
	    assignments[i][j] = 0;
	}
    }

    for (int i=0; i<par->binsize; i++) {
	int p = clust->partition[i];
	int real_p = (*bin)[i].cluster;
	assignments[p][real_p]++;
    }

    double totalf = 0.0;
    int num = clust->num;
    double ** f = new double *[clust->num];
    for (int i=0; i<clust->num; i++) {
	f[i] = new double[par->kclusters];
    }
    for (int i=0; i<clust->num; i++) {
	int max = 0;
	int maxnum = 0;
	int size = 0;
	for (int j=0; j<par->kclusters; j++) {

	    // determine n_j
	    size += assignments[i][j];
	}

		
	for (int j=0; j<par->kclusters; j++) {
	    if ((size != 0) && (assignments[i][j] != 0)){

		// n_ij / n_i
		double r = double(assignments[i][j]) / double(par->size_cluster[j]);

		// n_ij / n_j
		double p = double(assignments[i][j]) / double(size);

		// F-value for class j and cluster i
		f[i][j] = (double(b*b)+1.0)*p*r / (double(b*b)*p + r);
	    }
	    else f[i][j] = 0;
	}
    }
    for (int j=0; j<par->kclusters; j++) {

	// find max{F(i,j)}
	double maxf = 0.0;
	for (int i=0; i<clust->num; i++) {
	    maxf = max(maxf, f[i][j]);
	}
	totalf += double(par->size_cluster[j]) / double(par->binsize) * maxf;
    } 

    for (int i=0; i<clust->num; i++) {
	delete [] assignments[i];
	delete [] f[i];
    }
    delete [] assignments;
    delete [] f;
    return totalf;

} 







double evaluation::randindex() {
    int a = 0;
    int b = 0;
    int c = 0;
    int d = 0;

    double r = 0.0;
    for (int i=0; i<par->binsize; i++) {
	int p1 = clust->partition[i];
	int q1 = (*bin)[i].cluster;
	for (int j=0; j<par->binsize; j++) {
	    int p2 = clust->partition[j];
	    int q2 = (*bin)[j].cluster;
	    if ((p1 == p2) && (q1 == q2)) a++;
	    if ((p1 == p2) && !(q1 == q2)) b++;
	    if (!(p1 == p2) && (q1 == q2)) c++;
	    if (!(p1 == p2) && !(q1 == q2)) d++;
	}
    }


    r = double(a+d)/double(a+b+c+d);
    return r;
}


double evaluation::randindex(clustering * c1, clustering * c2, int size) {
    int a = 0;
    int b = 0;
    int c = 0;
    int d = 0;

    double r = 0.0;
    for (int i=0; i<size; i++) {
	int p1 = c1->partition[i];
	int q1 = c2->partition[i];
	for (int j=0; j<size; j++) {
	    int p2 = c1->partition[j];
	    int q2 = c2->partition[j];
	    if ((p1 == p2) && (q1 == q2)) a++;
	    if ((p1 == p2) && !(q1 == q2)) b++;
	    if (!(p1 == p2) && (q1 == q2)) c++;
	    if (!(p1 == p2) && !(q1 == q2)) d++;
	}
    }


    r = double(a+d)/double(a+b+c+d);
    return r;
}