ann_test.cpp

c++实现的KNN库:建立高维度的K-d tree,实现K邻域搜索

const char distr_table[N_DISTRIBS][STRING_LEN] = {
		"uniform",						// UNIFORM
		"gauss",						// GAUSS
		"laplace",						// LAPLACE
		"co_gauss",						// CO_GAUSS
		"co_laplace",					// CO_LAPLACE
		"clus_gauss",					// CLUS_GAUSS
		"clus_orth_flats",				// CLUS_ORTH_FLATS
		"clus_ellipsoids",				// CLUS_ELLIPSOIS
		"planted"};						// PLANTED

//------------------------------------------------------------------------
//	Splitting rules for kd-trees (see ANN.h for types)
//------------------------------------------------------------------------

const int N_SPLIT_RULES = 6;
const char split_table[N_SPLIT_RULES][STRING_LEN] = {
		"standard",						// standard optimized kd-tree
		"midpt",						// midpoint split
		"fair",							// fair split
		"sl_midpt",						// sliding midpt split
		"sl_fair",						// sliding fair split
		"suggest"};						// authors' choice for best

//------------------------------------------------------------------------
//	Shrinking rules for bd-trees (see ANN.h for types)
//------------------------------------------------------------------------

const int N_SHRINK_RULES = 4;
const char shrink_table[N_SHRINK_RULES][STRING_LEN] = {
		"none",							// perform no shrinking (kd-tree)
		"simple",						// simple shrinking
		"centroid",						// centroid shrinking
		"suggest"};						// authors' choice for best

//----------------------------------------------------------------------
//	Short utility functions
//		Error - general error routine
//		printPoint - print a point to standard output
//		lookUp - look up a name in table and return index
//----------------------------------------------------------------------

void Error(								// error routine
	char				*msg,			// error message
	ANNerr				level)			// abort afterwards
{
	if (level == ANNabort) {
		cerr << "ann_test: ERROR------->" << msg << "<-------------ERROR\n";
		exit(1);
	}
	else {
		cerr << "ann_test: WARNING----->" << msg << "<-------------WARNING\n";
	}
}

void printPoint(						// print point
	ANNpoint			p,				// the point
	int					dim)			// the dimension
{
	cout << "[";
	for (int i = 0; i < dim; i++) {
		cout << p[i];
		if (i < dim-1) cout << ",";
	}
	cout << "]";
}

int lookUp(								// look up name in table
	const char	*arg,					// name to look up
	const char	(*table)[STRING_LEN],	// name table
	int			size)					// table size
{
	int i;
	for (i = 0; i < size; i++) {
		if (!strcmp(arg, table[i])) return i;
	}
	return i;
}

//------------------------------------------------------------------------
// Function declarations
//------------------------------------------------------------------------

void generatePts(						// generate data/query points
	ANNpointArray		&pa,			// point array (returned)
	int					n,				// number of points
	PtType				type,			// point type
	ANNbool				new_clust,		// new cluster centers desired?
	ANNpointArray		src = NULL,		// source array (for PLANTED)
	int					n_src = 0);		// source size (for PLANTED)

void readPts(							// read data/query points from file
	ANNpointArray		&pa,			// point array (returned)
	int					&n,				// number of points
	char				*file_nm,		// file name
	PtType				type);			// point type (DATA, QUERY)

void doValidation();					// perform validation
void getTrueNN();						// compute true nearest neighbors

void treeStats(							// print statistics on kd- or bd-tree
	ostream				&out,			// output stream
	ANNbool				verbose);		// print stats

//------------------------------------------------------------------------
//	Default execution parameters
//------------------------------------------------------------------------
const int		extra_nn		= 10;			// how many extra true nn's?

const int		def_dim			= 2;			// def dimension
const int		def_data_size	= 100;			// def data size
const int		def_query_size	= 100;			// def number of queries
const int		def_n_color		= 5;			// def number of colors
const ANNbool	def_new_clust	= ANNfalse;		// def new clusters flag
const int		def_max_dim		= 1;			// def max flat dimension
const Distrib	def_distr		= UNIFORM;		// def distribution
const double	def_std_dev		= 1.00;			// def standard deviation
const double	def_corr_coef	= 0.05;			// def correlation coef
const int		def_bucket_size = 1;			// def bucket size
const double	def_epsilon		= 0.0;			// def error bound
const int		def_near_neigh	= 1;			// def number of near neighbors
const int		def_max_visit	= 0;			// def number of points visited
const int		def_rad_bound	= 0;			// def radius bound
												// def number of true nn's
const int		def_true_nn		= def_near_neigh + extra_nn;
const int		def_seed		= 0;			// def seed for random numbers
const ANNbool	def_validate	= ANNfalse;		// def validation flag
												// def statistics output level
const StatLev	def_stats		= QUERY_STATS;
const ANNsplitRule								// def splitting rule
				def_split		= ANN_KD_SUGGEST;
const ANNshrinkRule								// def shrinking rule
				def_shrink		= ANN_BD_NONE;

//------------------------------------------------------------------------
//	Global variables - Execution options
//------------------------------------------------------------------------

int				dim;					// dimension
int				data_size;				// data size
int				query_size;				// number of queries
int				n_color;				// number of colors
ANNbool			new_clust;				// generate new clusters?
int				max_dim;				// maximum flat dimension
Distrib			distr;					// distribution
double			corr_coef;				// correlation coef
double			std_dev;				// standard deviation
double			std_dev_lo;				// low standard deviation
double			std_dev_hi;				// high standard deviation
int				bucket_size;			// bucket size
double			epsilon;				// error bound
int				near_neigh;				// number of near neighbors
int				max_pts_visit;			// max number of points to visit
double			radius_bound;			// maximum radius search bound
int				true_nn;				// number of true nn's
ANNbool			validate;				// validation flag
StatLev			stats;					// statistics output level
ANNsplitRule	split;					// splitting rule
ANNshrinkRule	shrink;					// shrinking rule

//------------------------------------------------------------------------
//	More globals - pointers to dynamically allocated arrays and structures
//
//		It is assumed that all these values are set to NULL when nothing
//		is allocated.
//
//		data_pts, query_pts				The data and query points
//		the_tree						Points to the kd- or bd-tree for
//										nearest neighbor searching.
//		apx_nn_idx, apx_dists			Record approximate near neighbor
//										indices and distances
//		apx_pts_in_range				Counts of the number of points in
//										the in approx range, for fixed-
//										radius NN searching.
//		true_nn_idx, true_dists			Record true near neighbor
//										indices and distances
//		min_pts_in_range, max_...		Min and max counts of the number
//										of points in the in approximate
//										range.
//		valid_dirty						To avoid repeated validation,
//										we only validate query results
//										once.  This validation becomes
//										invalid, if a new tree, new data
//										points or new query points have
//										been generated.
//		tree_data_size					The number of points in the
//										current tree.  (This will be the
//										same a data_size unless points have
//										been added since the tree was
//										built.)
//
//		The approximate and true nearest neighbor results are stored
//		in: apx_nn_idx, apx_dists, and true_nn_idx, true_dists.
//		They are really flattened 2-dimensional arrays. Each of these
//		arrays consists of query_size blocks, each of which contains
//		near_neigh (or true_nn) entries, one for each of the nearest
//		neighbors for a given query point.
//------------------------------------------------------------------------

ANNpointArray	data_pts;				// data points
ANNpointArray	query_pts;				// query points
ANNbd_tree*		the_tree;				// kd- or bd-tree search structure
ANNidxArray		apx_nn_idx;				// storage for near neighbor indices
ANNdistArray	apx_dists;				// storage for near neighbor distances
int*			apx_pts_in_range;		// storage for no. of points in range
ANNidxArray		true_nn_idx;			// true near neighbor indices
ANNdistArray	true_dists;				// true near neighbor distances
int*			min_pts_in_range;		// min points in approx range
int*			max_pts_in_range;		// max points in approx range

ANNbool			valid_dirty;			// validation is no longer valid

//------------------------------------------------------------------------
//	Initialize global parameters
//------------------------------------------------------------------------

void initGlobals()
{
	dim					= def_dim;				// init execution parameters
	data_size			= def_data_size;
	query_size			= def_query_size;
	distr				= def_distr;
	corr_coef			= def_corr_coef;
	std_dev				= def_std_dev;
	std_dev_lo			= def_std_dev;
	std_dev_hi			= def_std_dev;
	new_clust			= def_new_clust;
	max_dim				= def_max_dim;
	n_color				= def_n_color;
	bucket_size			= def_bucket_size;
	epsilon				= def_epsilon;
	near_neigh			= def_near_neigh;
	max_pts_visit		= def_max_visit;
	radius_bound		= def_rad_bound;
	true_nn				= def_true_nn;
	validate			= def_validate;
	stats				= def_stats;
	split				= def_split;
	shrink				= def_shrink;
	annIdum				= -def_seed;			// init. global seed for ran0()

	data_pts			= NULL;					// initialize storage pointers
	query_pts			= NULL;
	the_tree			= NULL;
	apx_nn_idx			= NULL;
	apx_dists			= NULL;
	apx_pts_in_range	= NULL;
	true_nn_idx 		= NULL;
	true_dists			= NULL;
	min_pts_in_range	= NULL;
	max_pts_in_range	= NULL;

	valid_dirty			= ANNtrue;				// (validation must be done)
}

//------------------------------------------------------------------------
// getDirective - skip comments and read next directive
//	Returns ANNtrue if directive read, and ANNfalse if eof seen.
//------------------------------------------------------------------------

ANNbool skipComment(				// skip any comments
    istream		&in)				// input stream
{
    char ch = 0;
						// skip whitespace
    do { in.get(ch); } while (isspace(ch) && !in.eof());
    while (ch == '#' && !in.eof()) {		// comment?
						// skip to end of line
	do { in.get(ch); } while(ch != '\n' && !in.eof());
						// skip whitespace
	do { in.get(ch); } while(isspace(ch) && !in.eof());
    }
    if (in.eof()) return ANNfalse;			// end of file
    in.putback(ch);				// put character back
    return ANNtrue;
}

ANNbool getDirective(
    istream		&in,			// input stream
    char		*directive)		// directive storage
{
    if (!skipComment(in))			// skip comments
    	return ANNfalse;			// found eof along the way?
    in >> directive;				// read directive
    return ANNtrue;
}


//------------------------------------------------------------------------
// main program - driver
//		The main program reads input options, invokes the necessary
//		routines to process them.
//------------------------------------------------------------------------

int main(int argc, char** argv)
{
	long		clock0;						// clock time
	char		directive[STRING_LEN];		// input directive
	char		arg[STRING_LEN];			// all-purpose argument

	cout << "------------------------------------------------------------\n"
		 << "ann_test: Version " << ANNversion << " " << ANNversionCmt << "\n"
		 << "    Copyright: " << ANNcopyright << ".\n"
		 << "    Latest Revision: " << ANNlatestRev << ".\n"
		 << "------------------------------------------------------------\n\n";

	initGlobals();								// initialize global values

	//--------------------------------------------------------------------
	//	Main input loop
	//--------------------------------------------------------------------
												// read input directive
	while (getDirective(cin, directive)) {
		//----------------------------------------------------------------
		//	Read options
		//----------------------------------------------------------------
		if (!strcmp(directive,"dim")) {
			cin >> dim;
		}
		else if (!strcmp(directive,"colors")) {
			cin >> n_color;
		}
		else if (!strcmp(directive,"new_clust")) {
			new_clust = ANNtrue;
		}
		else if (!strcmp(directive,"max_clus_dim")) {
			cin >> max_dim;
		}
		else if (!strcmp(directive,"std_dev")) {