kmlocal.h

高效的k-means算法实现

//		random choice.  If it rejects, then we have ended the
//		swapping process and are transitioning to Lloyd's
//		algorithm.  In either case, return false.
//
//		If we are doing Lloyd's, return true if the consecutive
//		RDL is less than minConsecRDL, meaning that Lloyd's
//		algorithm has converged.
//	endRun()
//		If temperature run is done then do processing for the
//		end of a temperature run.  Set areSwapping to true.
//	tryAcceptance()
//		At this point we have completed all the swaps and all
//		the Lloyd's iterations.  If the distortion has improved
//		or if the simulated annealing random choice says to,
//		save the current solution (and update the overall best
//		if needed).  Otherwise, restore the previously saved
//		solution.
//------------------------------------------------------------------------

template <typename T>				// min function
T kmMin(const T& x, const T& y) 
{  return (x < y ? x : y); }

template <typename T>				// max function
T kmMax(const T& x, const T& y) 
{  return (x > y ? x : y); }

class KMlocalHybrid : public KMlocal {
private:
    double	temperature;			// temperature used in SA
    int		initTempRunStage;		// stage when temp run started
    bool	areSwapping;			// are we swapping? (or Lloyd's)
    double	prevDist;			// distortion from prev stage
    double	sumTrials;			// sum of RDL's over trials
    int		trialCt;			// trial count
    KMfilterCenters save;			// saved solution
protected:					// local utilities
    double accumRDL()				// accumulated RDL
      { return (save.getDist() - curr.getDist()) /  save.getDist(); }

    double consecRDL()				// consecutive RDL
      { return (prevDist - curr.getDist()) / prevDist; }

    virtual void printStageStats() {		// print end of stage info
	if (kmStatLev >= STAGE) {
	    *kmOut << "    <stage: "	<< stageNo
         	 << " curr: "		<< curr.getAvgDist()
         	 << " best: "		<< best.getAvgDist()
         	 << " save: "		<< save.getAvgDist()
         	 << " consecRDL: "	<< consecRDL()
		 << " >" << endl;
	}
    }
    virtual void printRunStats() {		// print end of run info
	if (kmStatLev >= STAGE) {
	    *kmOut << "    <End of Run>" << endl;
	}
    }
protected:					// SA utilities
    int nTrials()				// number of trials
      { return kmMax(20, term.getTempRunLength()); }

    bool simAnnealAccept(double rdl) {		// random accept choice
      double prob;
      if (--trialCt >= 0) {			// still in trial phase?
        sumTrials += fabs(rdl);			// increment sum of RDLs
	if (trialCt == 0) {			// last trial?  get temp
	  temperature = -sumTrials/(nTrials()*log(term.getInitProbAccept()));
	  initTempRunStage = stageNo;		// start counting stages
	}
	prob = term.getInitProbAccept();	// use initial probability
      }
      else {					// use SA probability
        prob = kmMin(term.getInitProbAccept(), exp(rdl/temperature));
      }
      return prob > kmRanUnif();
    }

    void initTempRuns() {			// initialize for temp runs
      sumTrials = 0;
      trialCt = nTrials();
      initTempRunStage = KM_HUGE_INT;		// not counting stages
    }

    bool isTempRunDone()			// end of temperature run?
      { return stageNo - initTempRunStage >= term.getTempRunLength(); }

    void endTempRun() {				// process end of temp run
      temperature *= term.getTempReducFact();	// reduce temperature
      initTempRunStage = stageNo;
    }

public:
    						// constructor
    KMlocalHybrid(const KMfilterCenters &sol, const KMterm &t)
	  : KMlocal(sol, t), save(sol) { }
protected:					// overridden methods
    virtual void reset() {
      KMlocal::reset();				// reset base class
      save = curr;				// save initial centers
      areSwapping = true;			// start with swapping
      initTempRuns();				// initialize sim. annealing
      printStageStats();
    }
    virtual void beginStage() {			// start of stage processing
      prevDist = curr.getDist();		// save previous distortion
    }
    virtual KMalg selectMethod() {		// select method
      return (areSwapping ? SWAP : LLOYD );
    }
    virtual void endStage() {			// end of stage processing
      stageNo++;				// increment stage number
      curr.getDist();				// get distortion
      printStageStats();
    }
    virtual bool isRunDone() { 			// run is done
      if (areSwapping) {			// swapping?
        if (!simAnnealAccept(consecRDL())) {	// check SA acceptance
	  areSwapping = false;			// transition to Lloyd's
	}
	return false;
      }
      else {					// doing Lloyd's algorithm
        return consecRDL() <= term.getMinConsecRDL();  // test for convergence
      }
    }
    virtual void endRun() { 			// end of run processing
      if (isTempRunDone()) endTempRun();	// check/process end of temp run
      areSwapping = true;			// return to swapping
      printRunStats();
    }
    virtual void tryAcceptance() { 		// test acceptance
      if (accumRDL() > 0) {			// improvement over saved?
        save = curr;				// save this one
	if (save.getDist() < best.getDist()) {	// new best?
	  best = save;
	}
      }
      else if (simAnnealAccept(accumRDL())) {	// SA says save anyway
        save = best;
      }
      else {					// reject, restore old solution
        curr = save;
      }
    }
};

//------------------------------------------------------------------------
// KMlocalEZ_Hybrid - a simpler hybrid combination of Lloyd's and swaps.
//
//	Overview
//	--------
//	This implements a simpler hybrid algorithm, than the previous
//	one.  The algorithm performs only one swap, followed by some
//	number of iterations of Lloyd's algorithm.  Lloyd's algorithm
//	is repeated until the consecutive RDL falls below a given
//	threshold.
//
//	Stage:	One invocation of the Swap or Lloyd's algorithm.
//	Run:	A run consists of a single swap followed by a consecutive
//		sequence of Lloyd's steps.  A graphical representation
//		of one run is presented below.
//
//	                         +---+
//	                         |   |
//	                         V   |
//	    ----> Swap -------> Lloyd's ----->
//
//	Decisions
//	---------
//	Make another pass through Lloyd's or go to acceptance?
//	    This is based on whether the relative improvement since the
//	    last stage (consecutive relative distortion loss) is above a
//	    certain fixed threshold (minConsecRDL).
//
//	Parameters (in term)
//	--------------------
//	minConsecRDL
//		Minimum consecutive RDL needed to keep Lloyd's algorithm
//		going.
//
//	State variables
//	---------------
//	areSwapping
//		True if we are still in swapping portion of a run, and
//		false if we are in the Lloyd's portion of the run.
//	prevDist
//		In order to compute the consecutive RDL we need to save
//		the distortion at the start of each trip through Lloyd's
//		algorithm.
//
//	Overridden methods
//	------------------
//	reset()
//		Do base class resetting.  Initialize areSwapping to
//		true.
//	beginStage()
//		Save current distortion in prevDist (for computing
//		consecutive RDL).
//	selectMethod()
//		If we are swapping, use Swap, and otherwise use Lloyd's.
//	endStage()
//		Increment the stage number, get the distortion, and print
//		the end-of-stage information.
//	isRunDone()
//		If we are swapping, transition to Lloyd's and return
//		false.  If we are doing Lloyd's, return true if the
//		consecutive RDL is less than minConsecRDL, meaning that
//		Lloyd's algorithm has converged.
//	endRun()
//		Set areSwaping to true.
//	tryAcceptance()
//		At this point we have completed the swap and the Lloyd's
//		iterations.  Update the overall best if appropriate.
//------------------------------------------------------------------------

class KMlocalEZ_Hybrid : public KMlocal {
private:
    bool	areSwapping;			// are we swapping? (or Lloyd's)
    double	prevDist;			// distortion from prev stage
protected:					// local utilities
    double consecRDL()				// consecutive RDL
      { return (prevDist - curr.getDist()) / prevDist; }

    virtual void printStageStats() {		// print end of stage info
	if (kmStatLev >= STAGE) {
	    *kmOut << "    <stage: "	<< stageNo
         	 << " curr: "		<< curr.getAvgDist()
         	 << " best: "		<< best.getAvgDist()
         	 << " consecRDL: "	<< consecRDL()
		 << " >" << endl;
	}
    }
    virtual void printRunStats() {		// print end of run info
	if (kmStatLev >= STAGE) {
	    *kmOut << "    <Swapping Centers>" << endl;
	}
    }
public:
    						// constructor
    KMlocalEZ_Hybrid(const KMfilterCenters &sol, const KMterm &t)
	  : KMlocal(sol, t) { }
protected:					// overridden methods
    virtual void reset() {
      KMlocal::reset();				// reset base class
      areSwapping = true;			// start with swapping
      printStageStats();
    }
    virtual void beginStage() {			// start of stage processing
      prevDist = curr.getDist();		// save previous distortion
    }
    virtual KMalg selectMethod() {		// select method
      return (areSwapping ? SWAP : LLOYD );
    }
    virtual void endStage() {			// end of stage processing
      stageNo++;				// increment stage number
      curr.getDist();				// get distortion
      printStageStats();
    }
    virtual bool isRunDone() { 			// run is done
      if (areSwapping) {			// swapping?
	areSwapping = false;			// transition to Lloyd's
	return false;
      }
      else {					// doing Lloyd's algorithm
        return consecRDL() <= term.getMinConsecRDL();  // test for convergence
      }
    }
    virtual void endRun() { 			// end of run processing
      areSwapping = true;			// return to swapping
      printRunStats();
    }
    virtual void tryAcceptance() { 		// test acceptance
      if (curr.getDist() < best.getDist()) {	// new best?
	best = curr;
      }
    }
};

#endif