ann_test.cpp

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

			cin >> std_dev;
		}
		else if (!strcmp(directive,"std_dev_lo")) {
			cin >> std_dev_lo;
		}
		else if (!strcmp(directive,"std_dev_hi")) {
			cin >> std_dev_hi;
		}
		else if (!strcmp(directive,"corr_coef")) {
			cin >> corr_coef;
		}
		else if (!strcmp(directive, "data_size")) {
			cin >> data_size;
		}
		else if (!strcmp(directive,"query_size")) {
			cin >> query_size;
		}
		else if (!strcmp(directive,"bucket_size")) {
			cin >> bucket_size;
		}
		else if (!strcmp(directive,"epsilon")) {
			cin >> epsilon;
		}
		else if (!strcmp(directive,"max_pts_visit")) {
			cin >> max_pts_visit;
			valid_dirty = ANNtrue;				// validation must be redone
		}
		else if (!strcmp(directive,"radius_bound")) {
			cin >> radius_bound;
			valid_dirty = ANNtrue;				// validation must be redone
		}
		else if (!strcmp(directive,"near_neigh")) {
			cin >> near_neigh;
			true_nn = near_neigh + extra_nn;	// also reset true near neighs
			valid_dirty = ANNtrue;				// validation must be redone
		}
		else if (!strcmp(directive,"true_near_neigh")) {
			cin >> true_nn;
			valid_dirty = ANNtrue;				// validation must be redone
		}
		//----------------------------------------------------------------
		//	seed option
		//		The seed is reset by setting the global annIdum to the
		//		negation of the seed value.  See rand.cpp.
		//----------------------------------------------------------------
		else if (!strcmp(directive,"seed")) {
			cin >> annIdum;
			annIdum = -annIdum;
		}
		//----------------------------------------------------------------
		//	validate option
		//----------------------------------------------------------------
		else if (!strcmp(directive,"validate")) {
			cin >> arg;							// input argument
			if (!strcmp(arg, "on")) {
				validate = ANNtrue;
				cout << "validate = on   "
					 << "(Warning: this may slow execution time.)\n";
			}
			else if (!strcmp(arg, "off")) {
				validate = ANNfalse;
			}
			else {
				cerr << "Argument: " << arg << "\n";
				Error("validate argument must be \"on\" or \"off\"", ANNabort);
			}
		}
		//----------------------------------------------------------------
		//	distribution option
		//----------------------------------------------------------------
		else if (!strcmp(directive,"distribution")) {
			cin >> arg;							// input name and translate
			distr = (Distrib) lookUp(arg, distr_table, N_DISTRIBS);
			if (distr >= N_DISTRIBS) {			// not something we recognize
				cerr << "Distribution: " << arg << "\n";
				Error("Unknown distribution", ANNabort);
			}
		}
		//----------------------------------------------------------------
		//	stats option
		//----------------------------------------------------------------
		else if (!strcmp(directive,"stats")) {
			cin >> arg;							// input name and translate
			stats = (StatLev) lookUp(arg, stat_table, N_STAT_LEVELS);
			if (stats >= N_STAT_LEVELS) {		// not something we recognize
				cerr << "Stats level: " << arg << "\n";
				Error("Unknown statistics level", ANNabort);
			}
			if (stats > SILENT)
				cout << "stats = " << arg << "\n";
		}
		//----------------------------------------------------------------
		//	split_rule option
		//----------------------------------------------------------------
		else if (!strcmp(directive,"split_rule")) {
			cin >> arg;							// input split_rule name
			split = (ANNsplitRule) lookUp(arg, split_table, N_SPLIT_RULES);
			if (split >= N_SPLIT_RULES) {		// not something we recognize
				cerr << "Splitting rule: " << arg << "\n";
				Error("Unknown splitting rule", ANNabort);
			}
		}
		//----------------------------------------------------------------
		//	shrink_rule option
		//----------------------------------------------------------------
		else if (!strcmp(directive,"shrink_rule")) {
			cin >> arg;							// input split_rule name
			shrink = (ANNshrinkRule) lookUp(arg, shrink_table, N_SHRINK_RULES);
			if (shrink >= N_SHRINK_RULES) {		// not something we recognize
				cerr << "Shrinking rule: " << arg << "\n";
				Error("Unknown shrinking rule", ANNabort);
			}
		}
		//----------------------------------------------------------------
		//	label operation
		//----------------------------------------------------------------
		else if (!strcmp(directive,"output_label")) {
			cin >> arg;
			if (stats > SILENT)
				cout << "<" << arg << ">\n";
		}
		//----------------------------------------------------------------
		//	gen_data_pts operation
		//----------------------------------------------------------------
		else if (!strcmp(directive,"gen_data_pts")) {
			if (distr == PLANTED) {				// planted distribution
				Error("Cannot use planted distribution for data points", ANNabort);
			}
			generatePts(						// generate data points
				data_pts,						// data points
				data_size,						// data size
				DATA,							// data points
				new_clust);						// new clusters flag
			valid_dirty = ANNtrue;				// validation must be redone
			new_clust = ANNfalse;				// reset flag
		}
		//----------------------------------------------------------------
		//	gen_query_pts operation
		//		If the distribution is PLANTED, then the query points
		//		are planted near the data points (which must already be
		//		generated).
		//----------------------------------------------------------------
		else if (!strcmp(directive,"gen_query_pts")) {
			if (distr == PLANTED) {				// planted distribution
				if (data_pts == NULL) {
					Error("Must generate data points before query points for planted distribution", ANNabort);
				}
				generatePts(					// generate query points
					query_pts,					// point array
					query_size,					// number of query points
					QUERY,						// query points
					new_clust,					// new clusters flag
					data_pts,					// plant around data pts
					data_size);
			}
			else {								// all other distributions
				generatePts(					// generate query points
					query_pts,					// point array
					query_size,					// number of query points
					QUERY,						// query points
					new_clust);					// new clusters flag
			}
			valid_dirty = ANNtrue;				// validation must be redone
			new_clust = ANNfalse;				// reset flag
		}
		//----------------------------------------------------------------
		//	read_data_pts operation
		//----------------------------------------------------------------
		else if (!strcmp(directive,"read_data_pts")) {
			cin >> arg;							// input file name
			readPts(
				data_pts,						// point array
				data_size,						// number of points
				arg,							// file name
				DATA);							// data points
			valid_dirty = ANNtrue;				// validation must be redone
		}
		//----------------------------------------------------------------
		//	read_query_pts operation
		//----------------------------------------------------------------
		else if (!strcmp(directive,"read_query_pts")) {
			cin >> arg;							// input file name
			readPts(
				query_pts,						// point array
				query_size,						// number of points
				arg,							// file name
				QUERY);							// query points
			valid_dirty = ANNtrue;				// validation must be redone
		}
		//----------------------------------------------------------------
		//	build_ann operation
		//		We always invoke the constructor for bd-trees.  Note
		//		that when the shrinking rule is NONE (which is true by
		//		default), then this constructs a kd-tree.
		//----------------------------------------------------------------
		else if (!strcmp(directive,"build_ann")) {
			//------------------------------------------------------------
			//	Build the tree
			//------------------------------------------------------------
			if (the_tree != NULL) {				// tree exists already
				delete the_tree;				// get rid of it
			}
			clock0 = clock();					// start time

			the_tree = new ANNbd_tree(			// build it
					data_pts,					// the data points
					data_size,					// number of points
					dim,						// dimension of space
					bucket_size,				// maximum bucket size
					split,						// splitting rule
					shrink);					// shrinking rule

			//------------------------------------------------------------
			//	Print summary
			//------------------------------------------------------------
			long prep_time = clock() - clock0;	// end of prep time

			if (stats > SILENT) {
				cout << "[Build ann-structure:\n";
				cout << "  split_rule    = " << split_table[split] << "\n";
				cout << "  shrink_rule   = " << shrink_table[shrink] << "\n";
				cout << "  data_size     = " << data_size << "\n";
				cout << "  dim           = " << dim << "\n";
				cout << "  bucket_size   = " << bucket_size << "\n";

				if (stats >= EXEC_TIME) {		// output processing time
					cout << "  process_time  = "
						 << double(prep_time)/CLOCKS_PER_SEC << " sec\n";
				}

				if (stats >= PREP_STATS)		// output or check tree stats
					treeStats(cout, ANNtrue);	// print tree stats
				else
					treeStats(cout, ANNfalse);	// check stats

				if (stats >= SHOW_STRUCT) {		// print the whole tree
					cout << "  (Structure Contents:\n";
					the_tree->Print(ANNfalse, cout);
					cout << "  )\n";
				}
				cout << "]\n";
			}
		}
		//----------------------------------------------------------------
		//	dump operation
		//----------------------------------------------------------------
		else if (!strcmp(directive,"dump")) {
			cin >> arg;							// input file name
			if (the_tree == NULL) {				// no tree
				Error("Cannot dump.  No tree has been built yet", ANNwarn);
			}
			else {								// there is a tree
												// try to open file
				ofstream out_dump_file(arg);
				if (!out_dump_file) {
					cerr << "File name: " << arg << "\n";
					Error("Cannot open dump file", ANNabort);
				}
												// dump the tree and points
				the_tree->Dump(ANNtrue, out_dump_file);
				if (stats > SILENT) {
					cout << "(Tree has been dumped to file " << arg << ")\n";
				}
			}
		}
		//----------------------------------------------------------------
		//	load operation
		//		Since this not only loads a tree, but loads a new set
		//		of data points.
		//----------------------------------------------------------------
		else if (!strcmp(directive,"load")) {
			cin >> arg;							// input file name
			if (the_tree != NULL) {				// tree exists already
				delete the_tree;				// get rid of it
			}
			if (data_pts != NULL) {				// data points exist already
				delete data_pts;				// get rid of them
			}

			ifstream in_dump_file(arg);			// try to open file
			if (!in_dump_file) {
				cerr << "File name: " << arg << "\n";
				Error("Cannot open file for loading", ANNabort);
			}
												// build tree by loading
			the_tree = new ANNbd_tree(in_dump_file);

			dim = the_tree->theDim();			// new dimension
			data_size = the_tree->nPoints();	// number of points
			data_pts = the_tree->thePoints();	// new points

			valid_dirty = ANNtrue;				// validation must be redone

			if (stats > SILENT) {
					cout << "(Tree has been loaded from file " << arg << ")\n";
			}
			if (stats >= SHOW_STRUCT) {			// print the tree
				cout << "  (Structure Contents:\n";
				the_tree->Print(ANNfalse, cout);
				cout << "  )\n";
			}
		}
		//----------------------------------------------------------------
		//	run_queries operation
		//		This section does all the query processing.  It consists
		//		of the following subsections:
		//
		//		**	input the argument (standard or priority) and output
		//			the header describing the essential information.
		//		**	allocate space for the results to be stored.
		//		**	run the queries by invoking the appropriate search
		//			procedure on the query points.  Print nearest neighbor
		//			if requested.
		//		**	print final summaries
		//
		//	The approach for processing multiple nearest neighbors is
		//	pretty crude.  We allocate an array whose size is the
		//	product of the total number of queries times the number of
		//	nearest neighbors (k), and then use each k consecutive
		//	entries to store the results of each query.
		//----------------------------------------------------------------
		else if (!strcmp(directive,"run_queries")) {

			//------------------------------------------------------------
			//	Input arguments and print summary
			//------------------------------------------------------------
			enum {STANDARD, PRIORITY} method;

			cin >> arg;							// input argument