global.cpp

关联分类算法采用贪心算法发现高质量分类规则

#include "StdAfx.h"
#include "global.h"

int count_num_lines(FILE* f)
{
	fseek(f,0,SEEK_SET);
	int num_lines=0;
	char buf[1];
	while(fread(buf,1,1,f)>0)
	{
		if(buf[0]=='\n') num_lines++;
	}
	return num_lines;
}

int compare_double(const void* x,const void* y)
{
	if(*((double*)x)<*((double*)y)) return -1;
	return 1;
}

double entropy(int* a,int n_values,int size)
//a[] stores the original nomial data. n_values is the number of possible values. size is the number of samples.
//a[i] can only be 0 to n_values-1.
{
	int* counts=new int[n_values];
	memset(counts,0,n_values*sizeof(int));
	double* prob=new double[n_values];
	for(int i=0;i<size;i++)
		counts[a[i]]++;
	for(int i=0;i<n_values;i++)
		prob[i]=counts[i]/(double)size;
	double entropy=0.0;
	double log2=log(2.0);
	for(int i=0;i<n_values;i++)
	{
		if(prob[i]<INFINITE_SMALL)
			entropy+=prob[i]*log(INFINITE_SMALL)/log2;
		else
			entropy+=prob[i]*log(prob[i])/log2;
	}
	delete counts;
	delete prob;
	return -entropy;
}

double combination(int m,int n)
{
	if(n>m/2) n=m-n;

	double upper=1;
	for(int x=m;x>=m-n+1;x--)
		upper*=x;

	double down=1;
	for(int x=1;x<=n;x++)
		down*=x;

	return upper/down;
}

double x_to_y(double x,double y)
{
	return exp(y*log(x));
}

double error_rate(int m,int p)
//m is the number of examples satisfying a rule, p is the number of examples among them that are positive
//The algorithm is stupid. Just try from the minimum possible epsilon, and increase it little by little
{
	if(m==0||p==0) return 1.0;
	double comb=combination(m,p);

	double eps;
	for(eps=(double)(m-p)/m+0.00001;eps<0.999999;eps+=0.001)
	{
		double prob=comb*x_to_y(1-eps,p)*x_to_y(eps,m-p);
		if(prob<0.1) break;
	}

	return eps;
}