kmltest.cpp

高效的k-means算法实现

						// 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 false;			// end of file
    in.putback(ch);				// put character back
    return true;
}

static bool getDirective(
    istream		&in,			// input stream
    string		&directive)		// directive storage
{
    if (!skipComment(in))			// skip comments
	return false;				// found eof along the way?
    in >> directive;				// read directive
    return true;
}

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

int main(int argc, char **argv)
{
    string	directive;			// input directive
    string	strArg;				// string argument
    double	dblArg;				// double argument
    int		intArg;				// integer argument

    KMdata*	dataPts = NULL;			// the data points
    KMalg	alg;				// which algorithm to use

    initGlobals();				// initialize global values
    getCmdArgs(argc, argv);

    kmOut->precision(4);			// output precision
    *kmOut << "------------------------------------------------------------\n"
	 << "kmltest: " << KMlongName << "\n"
	 << "    Version: " << KMversion << " " << KMversionCmt << "\n"
	 << "    Copyright: " << KMcopyright << ".\n"
	 << "    Latest Revision: " << KMlatestRev << ".\n"
	 << "------------------------------------------------------------\n\n";

    //--------------------------------------------------------------------
    //  Main input loop
    //--------------------------------------------------------------------
						// read input directive
    while (getDirective(*kmIn, directive)) {
	//----------------------------------------------------------------
	//  Read options
	//----------------------------------------------------------------
	if (directive == "quit") {
	    kmExit();
	}
	else if (directive == "dim") {
	    *kmIn >> dim;
	    new_clust = true;			// force new clusters
	}
	else if (directive == "data_size") {
	    *kmIn >> data_size;
	}
	else if (directive =="kcenters") {
	    *kmIn >> kcenters;
	}
	else if (directive =="max_swaps") {
	    *kmIn >> max_swaps;
	}
	else if (directive =="damp_factor") {
	    *kmIn >> damp_factor;
	}
	else if (directive =="colors") {
	    *kmIn >> n_color;
	    new_clust = true;			// force new clusters
	}
	else if (directive =="new_clust") {
	    new_clust = true;
	}
	else if (directive =="max_clus_dim") {
	    *kmIn >> max_dim;
	}
	else if (directive =="std_dev") {
	    *kmIn >> std_dev;
	}
	else if (directive =="std_dev_lo") {
	    *kmIn >> std_dev_lo;
	}
	else if (directive =="std_dev_hi") {
	    *kmIn >> std_dev_hi;
	}
	else if (directive =="corr_coef") {
	    *kmIn >> corr_coef;
	}
	//----------------------------------------------------------------
	//  termination conditions
	//----------------------------------------------------------------
	else if (directive == "max_tot_stage") {
	    for (int i = 0; i < KM_TERM_VEC_LEN; i++) {
		*kmIn >> dblArg;
		term.setMaxTotStage(i, dblArg);
	    }
	}
	else if (directive =="min_consec_rdl") {
	    *kmIn >> dblArg;
	    term.setMinConsecRDL(dblArg);
	}
	else if (directive =="min_accum_rdl") {
	    *kmIn >> dblArg;
	    term.setMinAccumRDL(dblArg);
	}
	else if (directive =="max_run_stage") {
	    *kmIn >> intArg;
	    term.setMaxRunStage(intArg);
	}
	else if (directive =="init_prob_accept") {
	    *kmIn >> dblArg;
	    term.setInitProbAccept(dblArg);
	}
	else if (directive =="temp_run_length") {
	    *kmIn >> intArg;
	    term.setTempRunLength(intArg);
	}
	else if (directive =="temp_reduc_fact") {
	    *kmIn >> dblArg;
	    term.setTempReducFact(dblArg);
	}
	//----------------------------------------------------------------
	//  seed option
	//	The seed is reset by setting the global kmIdum to the
	//	negation of the seed value.  See rand.cc.
	//----------------------------------------------------------------
	else if (directive =="seed") {
	    *kmIn >> kmIdum;
	    kmIdum = -kmIdum;
	}
	//----------------------------------------------------------------
	//  print points option
	//----------------------------------------------------------------
	else if (directive =="print_points") {
	    *kmIn >> strArg;			// input argument
	    if (strArg == "yes") {
		print_points = true;
	    }
	    else if (strArg == "no") {
		print_points = false;
	    }
	    else {
		*kmErr << "Argument: " << strArg << "\n";
		kmError("print_points arg must be \"yes\" or \"no\"", KMabort);
	    }
	}
	//----------------------------------------------------------------
	//  show assignments option
	//----------------------------------------------------------------
	else if (directive =="show_assignments") {
	    *kmIn >> strArg;			// input argument
	    if (strArg == "yes") {
		show_assign = true;
	    }
	    else if (strArg == "no") {
		show_assign = false;
	    }
	    else {
		*kmErr << "Argument: " << strArg << "\n";
		kmError("show_assignments arg must be \"yes\" or \"no\"", KMabort);
	    }
	}
	//----------------------------------------------------------------
	//  validate assignments option
	//----------------------------------------------------------------
	else if (directive =="validate") {
	    *kmIn >> strArg;			// input argument
	    if (strArg == "yes") {
		validate = true;
	    }
	    else if (strArg == "no") {
		validate = false;
	    }
	    else {
		*kmErr << "Argument: " << strArg << "\n";
		kmError("validate arg must be \"yes\" or \"no\"", KMabort);
	    }
	}
	//----------------------------------------------------------------
	//  distribution option
	//----------------------------------------------------------------
	else if (directive =="distribution") {
	    *kmIn >> strArg;			// input name and translate
	    distr = (Distrib) lookUp(strArg, distr_table, N_DISTRIBS);
	    if (distr >= N_DISTRIBS) {		// not something we recognize
		*kmErr << "Distribution: " << strArg << "\n";
		kmError("Unknown distribution", KMabort);
	    }
	}
	//----------------------------------------------------------------
	//  stats option
	//----------------------------------------------------------------
	else if (directive =="stats") {
	    *kmIn >> strArg;			// input name and translate
	    kmStatLev = (StatLev) lookUp(strArg, stat_table, N_STAT_LEVELS);
	    if (kmStatLev >= N_STAT_LEVELS) {	// not something we recognize
		*kmErr << "Stats level: " << strArg << "\n";
		kmError("Unknown statistics level", KMabort);
	    }
	    if (kmStatLev > SILENT)
		*kmOut << "stats = " << strArg << "\n";
	}
	//----------------------------------------------------------------
	//  print operation
	//----------------------------------------------------------------
	else if (directive =="print") {
	    *kmIn >> strArg;
	    *kmErr << "<" << strArg << ">" << endl;
	}
	//----------------------------------------------------------------
	//  title operation
	//----------------------------------------------------------------
	else if (directive =="title") {
	    *kmIn >> strArg;
	    if (kmStatLev > SILENT) {
		*kmOut << "title = " << strArg << endl;
	    }
	}
	//----------------------------------------------------------------
	//  gen_data_pts operation
	//----------------------------------------------------------------
	else if (directive =="gen_data_pts") {
	    genDataPts(				// create data points
		dataPts,			// data points (modified)
		new_clust);			// new clusters flag
	    new_clust = false;			// reset flag
	    buildKcTree(dataPts);		// build the kc-tree
	}
	//----------------------------------------------------------------
	//  read_data_pts operation
	//----------------------------------------------------------------
	else if (directive =="read_data_pts") {
	    *kmIn >> strArg;			// input file name
	    readDataPts(
		dataPts,			// data points (modified)
		data_size,			// array size
		strArg);			// file name
	    buildKcTree(dataPts);		// build the kc-tree
	}
	//----------------------------------------------------------------
	//  run_kmeans operation
	//----------------------------------------------------------------
	else if (directive =="run_kmeans") {
	    *kmIn >> strArg;			// input algorithm name
	    alg = (KMalg) lookUp(strArg, kmAlgTable, N_KM_ALGS);
	    if (alg >= N_KM_ALGS) {		// not something we recognize
		*kmErr << "Algorithm: " << strArg << "\n";
		kmError("Unknown k-means algorithm", KMabort);
	    }
	    if (dataPts == NULL) {		// data points must exist
		kmError("No data set has been generated", KMabort);
	    }
	    runKmeans(alg, dataPts, term);	// do it
	}
	//----------------------------------------------------------------
	//  Unknown directive
	//----------------------------------------------------------------
	else {
	    *kmErr << "Directive: " << directive << "\n";
	    // kmError("Unknown directive", KMabort);
	    kmError("Unknown directive", KMwarn);
	}
    }
    //--------------------------------------------------------------------
    //  End of input loop (close up)
    //--------------------------------------------------------------------
    if (kmStatLev > SILENT) {
	*kmOut << "<END_OF_RUN>\n";		// end of output marker
    }
    if (dataPts != NULL)  {			// deallocate data points
	delete dataPts;
    }
    kmExit();                                   // terminate
}

//------------------------------------------------------------------------
//  Print header for start of an execution
//------------------------------------------------------------------------

static void printHeader(
    KMalg		alg,			// the algorithm
    KMdataPtr		dataPts,		// data points
    const KMterm	&term)			// termination condition
{
    if (kmStatLev > SILENT) {
	*kmOut << "\n[Run_k-means:\n"
	     << "  k-means_alg      = " << kmAlgTable[alg] << "\n"
	     << "  data_size        = " << dataPts->getNPts() << "\n"
	     << "  kcenters         = " << kcenters << "\n"
	     << "  dim              = " << dim << "\n"
	     << "  max_tot_stage    = " << term.getMaxTotStage(kcenters,
	 						data_size) << "\n";
	switch (alg) {
	case LLOYD:
	    *kmOut  << "  max_run_stage    = "
		    << term.getMaxRunStage() << "\n"
		    << "  min_accum_rdl    = "
		    << term.getMinAccumRDL() << "\n";
	    break;
	case SWAP:
	    *kmOut  << "  max_swaps        = " << max_swaps << "\n";
	    break;
	case HYBRID:
	    *kmOut  << "  min_consec_rdl   = "
		    << term.getMinConsecRDL() << "\n"
		    << "  init_prob_accept = "
		    << term.getInitProbAccept() << "\n"
		    << "  temp_run_length  = "
		    << term.getTempRunLength() << "\n"
		    << "  temp_reduc_fact  = "
		    << term.getTempReducFact() << "\n";
	    break;
	case EZ_HYBRID:
	    *kmOut  << "  min_consec_rdl   = "
		    << term.getMinConsecRDL() << "\n";
	    break;
	default:
	    assert(false);			// shouldn't get here
	}
	*kmOut << "]" << endl;
    }
}

//------------------------------------------------------------------------
//  validateAssignments - validate center assignments
//  This procedure is given the assignments of data points to their
//  closest center, and determines (through simple brute-force search)
//  whether this assignment is correct.  This is used primarily for
//  debugging purposes.
//------------------------------------------------------------------------