KMeansAnalyzer Performs k-means classification on a set of input images (shape/size arbitrary) returned result is a set of classification vectors. More...

#include <analyzer.h>

Inheritance diagram for EMAN::KMeansAnalyzer:

[legend]

Collaboration diagram for EMAN::KMeansAnalyzer:

[legend]

Public Member Functions
	KMeansAnalyzer ()

virtual int	insert_image (EMData *image)
	insert a image to the list of input images More...

virtual vector< EMData * >	analyze ()
	main function for Analyzer, analyze input images and create output images More...

string	get_name () const
	Get the Analyzer's name. More...

string	get_desc () const
	Get the Analyzer's description. More...

void	set_params (const Dict &new_params)
	Set the Analyzer parameters using a key/value dictionary. More...

TypeDict	get_param_types () const
	Get Analyzer parameter information in a dictionary. More...

Public Member Functions inherited from EMAN::Analyzer
	Analyzer ()

virtual	~Analyzer ()

virtual int	insert_images_list (vector< EMData * > image_list)
	insert a list of images to the list of input images More...

virtual Dict	get_params () const
	Get the Reconstructor's parameters in a key/value dictionary. More...

Static Public Member Functions
static Analyzer *	NEW ()

Static Public Attributes
static const string	NAME = "kmeans"

Protected Member Functions
void	update_centers (int sigmas=0)

void	reclassify ()

void	reseed ()

void	resort ()

Protected Attributes
vector< EMData * >	centers

int	ncls

int	nclstot

int	verbose

int	minchange

int	maxiter

int	mininclass

int	nchanged

int	slowseed

int	calcsigmamean

int	outlierclass

Protected Attributes inherited from EMAN::Analyzer
Dict	params

vector< EMData * >	images

Detailed Description

KMeansAnalyzer Performs k-means classification on a set of input images (shape/size arbitrary) returned result is a set of classification vectors.

Author: Steve Ludtke

Date: 03/02/2008

Parameters

verbose	Display progress if set, more detail with larger numbers (9 max)
ncls	number of desired classes
maxiter	maximum number of iterations
minchange	Terminate if fewer than minchange members move in an iteration
mininclass	Minumum number of particles to keep a class as good (not enforced at termination
slowseed	Instead of seeding all classes at once, it will gradually increase the number of classes by adding new seeds in groups with large standard deviations
outlierclass	The last class will be reserved for outliers. Any class containing fewer than n particles will be permanently moved to the outlier group. default = disabled
calcsigmamean	Computes standard deviation of the mean image for each class-average (center), and returns them at the end of the list of centers

Definition at line 236 of file analyzer.h.

Constructor & Destructor Documentation

◆ KMeansAnalyzer()

EMAN::KMeansAnalyzer::KMeansAnalyzer ( )

inline

Definition at line 239 of file analyzer.h.

239: ncls(0),verbose(0),minchange(0),maxiter(100),mininclass(2),slowseed(0) {}

EMAN::KMeansAnalyzer::mininclass

int mininclass

Definition: analyzer.h:294

EMAN::KMeansAnalyzer::maxiter

int maxiter

Definition: analyzer.h:293

EMAN::KMeansAnalyzer::verbose

int verbose

Definition: analyzer.h:291

EMAN::KMeansAnalyzer::slowseed

int slowseed

Definition: analyzer.h:296

EMAN::KMeansAnalyzer::minchange

int minchange

Definition: analyzer.h:292

EMAN::KMeansAnalyzer::ncls

int ncls

Definition: analyzer.h:289

Referenced by NEW().

Member Function Documentation

◆ analyze()

vector< EMData * > KMeansAnalyzer::analyze ( )

virtual

main function for Analyzer, analyze input images and create output images

Returns: vector<EMData *> result os images analysis

Implements EMAN::Analyzer.

Definition at line 174 of file analyzer.cpp.

{
if (ncls<=1) return vector<EMData *>();
//srandom(time(0));
 
// These are the class centers, start each with a random image
int nptcl=images.size();
if (calcsigmamean) centers.resize(nclstot*2);
else centers.resize(nclstot);
if (mininclass<1) mininclass=1;
 
int seedmode=params.set_default("seedmode",(int)0);
 
// in outlier mode we don't use the bad center concept
if (outlierclass==0) {
        for (int i=0; i<nptcl; i++) images[i]->set_attr("is_ok_center",(int)5);  // if an image becomes part of too small a set, it will (eventually) be marked as a bad center
}
 
if (slowseed) {
        if (ncls>25) ncls=slowseed=ncls/25+1;   // this becomes the number to seed in each step
//      if (maxiter<ncls*3+20) maxiter=ncls*3+20;       // We need to make sure we have enough iterations to seed all of the classes
//      ncls=2;
}
 
if (seedmode==0) {
        for (int i=0; i<ncls; i++) {
                // Fixed by d.woolford, Util.get_irand is inclusive (added a -1)
                centers[i]=images[Util::get_irand(0,nptcl-1)]->copy();
        }
}
else if (seedmode==1) {
        // find the images with the largest and smallest sum
        EMData *max;
        float maxv=-1.0e27;
        EMData *min;
        float minv=1.0e27;
        for (int i=0; i<nptcl; i++) {
                float m = images[i]->get_attr("mean");
                if (m<minv) { minv=m; min=images[i]; }
                if (m>maxv) { maxv=m; max=images[i]; }
        }
        centers[0]=min->copy();
        centers[ncls-1]=max->copy();
 
        // now fill in linear interpolates in between
        for (int i=1; i<ncls-1; i++) {
                centers[i]=centers[0]->copy();
                centers[i]->mult((ncls-i-1.0f)/(ncls-1.0f));
                EMData *tmp=max->copy();
                tmp->mult(i/(ncls-1.0f));
                centers[i]->add(*tmp);
                delete tmp;
        }
}
 
if (calcsigmamean) {
        for (int i=nclstot; i<nclstot*2; i++) centers[i]=new EMData(images[0]->get_xsize(),images[0]->get_ysize(),images[0]->get_zsize());
}
 
 
for (int i=0; i<maxiter; i++) {
        nchanged=0;
        resort();
        reclassify();
        update_centers();
        if (verbose) printf("iter %d>  %d (%d)\n",i,nchanged,ncls);
        if (nchanged<minchange && ncls==nclstot) break;
 
        if (slowseed && i%3==2 && ncls<nclstot) {
                for (int j=0; j<slowseed && ncls<nclstot; j++) {
                        centers[ncls]=0;
                        ncls++;
                }
                reseed();
        }
}
update_centers(calcsigmamean);
 
return centers;
}

References calcsigmamean, centers, EMAN::Util::get_irand(), get_xsize(), get_ysize(), get_zsize(), EMAN::Analyzer::images, maxiter, minchange, mininclass, nchanged, ncls, nclstot, outlierclass, EMAN::Analyzer::params, reclassify(), reseed(), resort(), set_attr(), EMAN::Dict::set_default(), slowseed, update_centers(), and verbose.

◆ get_desc()

string EMAN::KMeansAnalyzer::get_desc ( ) const

inlinevirtual

Get the Analyzer's description.

Returns: The Analyzer's description.

Implements EMAN::Analyzer.

Definition at line 253 of file analyzer.h.

                {
                        return "k-means classification";
                }

◆ get_name()

string EMAN::KMeansAnalyzer::get_name ( ) const

inlinevirtual

Get the Analyzer's name.

Each Analyzer is identified by a unique name.

Returns: The Analyzer's name.

Implements EMAN::Analyzer.

Definition at line 248 of file analyzer.h.

                {
                        return NAME;
                }

References NAME.

◆ get_param_types()

TypeDict EMAN::KMeansAnalyzer::get_param_types ( ) const

inlinevirtual

Get Analyzer parameter information in a dictionary.

Each parameter has one record in the dictionary. Each record contains its name, data-type, and description.

Returns: A dictionary containing the parameter info.

Implements EMAN::Analyzer.

Definition at line 265 of file analyzer.h.

                {
                        TypeDict d;
                        d.put("verbose", EMObject::INT, "Display progress if set, more detail with larger numbers (9 max)");
                        d.put("seedmode",EMObject::INT, "How to generate initial seeds. 0 - random element (default), 1 - max sum, min sum, linear");
                        d.put("ncls", EMObject::INT, "number of desired classes");
                        d.put("maxiter", EMObject::INT, "maximum number of iterations (default=100)");
                        d.put("minchange", EMObject::INT, "Terminate if fewer than minchange members move in an iteration");
                        d.put("mininclass", EMObject::INT, "Minumum number of particles to keep a class as good (not enforced at termination");
                        d.put("slowseed",EMObject::INT, "Instead of seeding all classes at once, it will gradually increase the number of classes by adding new seeds in groups with large standard deviations");
                        d.put("outlierclass",EMObject::INT, "The last class will be reserved for outliers. Any class containing fewer than n particles will be permanently moved to the outlier group. default = disabled");
                        d.put("calcsigmamean",EMObject::INT, "Computes standard deviation of the mean image for each class-average (center), and returns them at the end of the list of centers");
                        return d;
                }

References EMAN::EMObject::INT, and EMAN::TypeDict::put().

◆ insert_image()

virtual int EMAN::KMeansAnalyzer::insert_image ( EMData * image )

inlinevirtual

insert a image to the list of input images

Parameters

image

Returns: int 0 for success, <0 for fail

Implements EMAN::Analyzer.

Definition at line 241 of file analyzer.h.

                                                        {
                        images.push_back(image);
                        return 0;
                }

References EMAN::Analyzer::images.

◆ NEW()

static Analyzer * EMAN::KMeansAnalyzer::NEW ( )

inlinestatic

Definition at line 258 of file analyzer.h.

                {
                        return new KMeansAnalyzer();
                }

References KMeansAnalyzer().

◆ reclassify()

void KMeansAnalyzer::reclassify ( )

protected

Definition at line 429 of file analyzer.cpp.

                                {
int nptcl=images.size();
 
//Cmp *c = Factory < Cmp >::get("sqeuclidean");
for (int i=0; i<nptcl; i++) {
        if (outlierclass && (int)images[i]->get_attr_default("class_id",0)==nclstot-1) continue;        // outliers are forever
        float best=1.0e38f;
        int bestn=0;
        int lim=ncls;
        if (outlierclass) lim=ncls-1;   // particles don't join the outliers based on distance
        for (int j=0; j<lim; j++) {
//              float d=c->cmp(images[i],centers[j]);
                float d=qsqcmp(images[i],centers[j]);
                if (d<best) { best=d; bestn=j; }
        }
        int oldn=images[i]->get_attr_default("class_id",0);
        if (oldn!=bestn) nchanged++;
        images[i]->set_attr("class_id",bestn);
        images[i]->set_attr("class_cendist",best);              // store this for reseeding
}
//delete c;
}

References centers, get_attr_default(), EMAN::Analyzer::images, nchanged, ncls, nclstot, outlierclass, and qsqcmp().

Referenced by analyze().

◆ reseed()

void KMeansAnalyzer::reseed ( )

protected

Definition at line 329 of file analyzer.cpp.

                            {
int nptcl=images.size();
int i,j;
 
// if no classes need reseeding just return
for (i=0; i<ncls; i++) {
        if (!centers[i]) break;
}
if (i==ncls) return;
 
// make a list of all particles which could be centers
vector<int> goodcen;
if (outlierclass) {
        for (int i=0; i<nptcl; i++) { if ((int)images[i]->get_attr("class_id")!=nclstot-1) goodcen.push_back(i); }
}
else {
//      printf("c%d\n",outlierclass);
        for (int i=0; i<nptcl; i++) { if ((int)images[i]->get_attr("is_ok_center")>0) goodcen.push_back(i); }
}
 
if (goodcen.size()==0) {
        printf("Kmeans ran out of valid center particles, disabling outlier mode and finishing. Results not valid.\n");
        for (int i=0; i<nptcl; i++) goodcen.push_back(i);
        outlierclass=0;
        return;
}
//      throw UnexpectedBehaviorException("Kmeans ran out of valid center particles with the provided parameters");
 
// pick a random particle for the new seed
// for (i=0; i<ncls; i++) {
//      if (centers[i]) continue;               // center doesn't need reseeding
//      j=Util::get_irand(0,goodcen.size()-1);
//      centers[i]=images[j]->copy();           // Isn't this wrong? Should it be looking in goodcen?
//      centers[i]->set_attr("ptcl_repr",1);
//      printf("reseed %d -> %d\n",i,j);
// }
 
// use a valid center with a large distance for the new seed
for (i=0; i<ncls; i++) {
        if (centers[i]) continue;               // center doesn't need reseeding
        if (outlierclass) j=Util::get_irand(0,ncls-2);  // don't reuse particles identified as outliers
        else j=Util::get_irand(0,ncls-1);       // pick a random class
        // The worst particle method with outliers often 'eats' all of the particles
        if (!outlierclass && centers[j] && centers[j]->has_attr("worst_ptcl")) {                // try to use the worst particle from that class
                centers[i]=images[(int)centers[j]->get_attr("worst_ptcl")]->copy();
                printf("reseed %d -> worst (cls %d)\n",i,j);
        }
        else {
                j=Util::get_irand(0,goodcen.size()-1);
                centers[i]=images[goodcen[j]]->copy();
                printf("reseed %d -> %d\n",i,j);
        }
        centers[i]->set_attr("ptcl_repr",1);
}
 
 
}

References centers, get_attr(), EMAN::Util::get_irand(), has_attr(), EMAN::Analyzer::images, ncls, nclstot, and outlierclass.

Referenced by analyze(), and update_centers().

◆ resort()

void KMeansAnalyzer::resort ( )

protected

Definition at line 400 of file analyzer.cpp.

                            {
 
//      Cmp *c = Factory < Cmp >::get("sqeuclidean");
 
        // The first center remains first, we proceed from that starting point
        // simple shells sort to an out-of-place reference
        int sortmax=ncls;
        if (outlierclass && ncls==nclstot) sortmax--;   // outlier class must not get resorted!
        
        for (int i=1; i<sortmax; i++) {
                float bst=1.0e22;
                for (int j=i; j<sortmax; j++) {
//                      float d=c->cmp(centers[i-1],centers[j]);
                        float d=qsqcmp(centers[i-1],centers[j]);
                        if (d<bst) {
                                bst=d;
                                if (j!=i) {
                                        EMData *tmp=centers[j];
                                        centers[j]=centers[i];
                                        centers[i]=tmp;
                                }
                        }
                }
        }
 
//      delete c;
}

References centers, ncls, nclstot, outlierclass, and qsqcmp().

Referenced by analyze().

◆ set_params()

void KMeansAnalyzer::set_params ( const Dict & new_params )

virtual

Set the Analyzer parameters using a key/value dictionary.

Parameters

new_params A dictionary containing the new parameters.

Reimplemented from EMAN::Analyzer.

Definition at line 161 of file analyzer.cpp.

{
        params = new_params;
        if (params.has_key("ncls")) ncls = nclstot = params["ncls"];
        if (params.has_key("maxiter"))maxiter = params["maxiter"];
        if (params.has_key("minchange"))minchange = params["minchange"];
        if (params.has_key("mininclass"))mininclass = params["mininclass"];
        if (params.has_key("slowseed"))slowseed = params["slowseed"];
        if (params.has_key("verbose"))verbose = params["verbose"];
        if (params.has_key("calcsigmamean")) calcsigmamean=params["calcsigmamean"];
        if (params.has_key("outlierclass")) outlierclass=params["outlierclass"];        
}

References calcsigmamean, EMAN::Dict::has_key(), maxiter, minchange, mininclass, ncls, nclstot, outlierclass, EMAN::Analyzer::params, slowseed, and verbose.

◆ update_centers()

void KMeansAnalyzer::update_centers ( int sigmas = 0 )

protected

Definition at line 255 of file analyzer.cpp.

                                              {
int nptcl=images.size();
//int repr[ncls];
vector<int> repr(ncls);
 
for (int i=0; i<ncls; i++) {
        centers[i]->to_zero();
        if (sigmas) centers[i+ncls]->to_zero();
        repr[i]=0;
        centers[i]->set_attr("worst_ptcldist",0.0f);
}
 
// compute new position for each center
for (int i=0; i<nptcl; i++) {
        int cid=images[i]->get_attr("class_id");
        // outlier mode disables is_ok_center functionality
        if (outlierclass || (int)images[i]->get_attr("is_ok_center")>0) {
                centers[cid]->add(*images[i]);
                if (sigmas) centers[cid+ncls]->addsquare(*images[i]);
                repr[cid]++;
                float imdist=images[i]->get_attr("class_cendist");
                if (imdist>(float)centers[cid]->get_attr("worst_ptcldist")) {
                        centers[cid]->set_attr("worst_ptcldist",imdist);
                        centers[cid]->set_attr("worst_ptcl",i);
                }
        }
}
 
for (int i=0; i<ncls; i++) {
        // If this class is too small, outlier class is never reseeded
        if (repr[i]<mininclass && (outlierclass==0||i<nclstot-1)) {
                // find all of the particles in the class, and decrement their "is_ok_center" counter.
                // when it reaches zero the particle will no longer participate in determining the location of a center
                if (outlierclass) {     // outliers are relegated to the outlier class permanently
                        for (int j=0; j<nptcl; j++) {
                                if ((int)images[j]->get_attr("class_id")==i) {
                                        if (verbose) printf("outlier: %d\n",j);
                                        images[j]->set_attr("class_id",nclstot-1);
                                        //nchanged++;   // should happen automatically below
                                }
                        }
                }
                // if not using outlier class, we use "is_ok_center" concept to reduce influence of outliers
                else {
                        for (int j=0; j<nptcl; j++) {
                                if ((int)images[j]->get_attr("class_id")==i) images[i]->set_attr("is_ok_center",(int)images[i]->get_attr("is_ok_center")-1);
                        }
                }
                // Mark the center for reseeding
                delete centers[i];
                centers[i]=0;
                repr[i]=0;
        }
        // finishes off the statistics we started computing above
        else {
                centers[i]->mult((float)1.0/(float)(repr[i]));
                centers[i]->set_attr("ptcl_repr",repr[i]);
                if (sigmas) {
                        centers[i+ncls]->mult((float)1.0/(float)(repr[i]));             // sum of squares over n
                        centers[i+ncls]->subsquare(*centers[i]);                                        // subtract the mean value squared
                        centers[i+ncls]->process("math.sqrt");                                  // square root
                        centers[i+ncls]->mult((float)1.0/(float)sqrt((float)repr[i]));          // divide by sqrt(N) to get std. dev. of mean
                }
 
        }
        if (verbose>1) printf("%d(%d)\t",i,(int)repr[i]);
}
 
if (verbose>1) printf("\n");
 
reseed();
}

References centers, get_attr(), EMAN::Analyzer::images, mininclass, ncls, nclstot, outlierclass, reseed(), sqrt(), and verbose.

Referenced by analyze().

Member Data Documentation

◆ calcsigmamean

int EMAN::KMeansAnalyzer::calcsigmamean

protected

Definition at line 297 of file analyzer.h.

Referenced by analyze(), and set_params().

◆ centers

vector<EMData *> EMAN::KMeansAnalyzer::centers

protected

Definition at line 288 of file analyzer.h.

Referenced by analyze(), reclassify(), reseed(), resort(), and update_centers().

◆ maxiter

int EMAN::KMeansAnalyzer::maxiter

protected

Definition at line 293 of file analyzer.h.

Referenced by analyze(), and set_params().

◆ minchange

int EMAN::KMeansAnalyzer::minchange

protected

Definition at line 292 of file analyzer.h.

Referenced by analyze(), and set_params().

◆ mininclass

int EMAN::KMeansAnalyzer::mininclass

protected

Definition at line 294 of file analyzer.h.

Referenced by analyze(), set_params(), and update_centers().

◆ NAME

const string EMAN::KMeansAnalyzer::NAME = "kmeans"

static

Definition at line 280 of file analyzer.h.

Referenced by get_name().

◆ nchanged

int EMAN::KMeansAnalyzer::nchanged

protected

Definition at line 295 of file analyzer.h.

Referenced by analyze(), and reclassify().

◆ ncls

int EMAN::KMeansAnalyzer::ncls

protected

Definition at line 289 of file analyzer.h.

Referenced by analyze(), reclassify(), reseed(), resort(), set_params(), and update_centers().

◆ nclstot

int EMAN::KMeansAnalyzer::nclstot

protected

Definition at line 290 of file analyzer.h.

Referenced by analyze(), reclassify(), reseed(), resort(), set_params(), and update_centers().

◆ outlierclass

int EMAN::KMeansAnalyzer::outlierclass

protected

Definition at line 298 of file analyzer.h.

Referenced by analyze(), reclassify(), reseed(), resort(), set_params(), and update_centers().

◆ slowseed

int EMAN::KMeansAnalyzer::slowseed

protected

Definition at line 296 of file analyzer.h.

Referenced by analyze(), and set_params().

◆ verbose

int EMAN::KMeansAnalyzer::verbose

protected

Definition at line 291 of file analyzer.h.

Referenced by analyze(), set_params(), and update_centers().

The documentation for this class was generated from the following files:

Public Member Functions

Static Public Member Functions

Static Public Attributes

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ KMeansAnalyzer()

Member Function Documentation

◆ analyze()

◆ get_desc()

◆ get_name()

◆ get_param_types()

◆ insert_image()

◆ NEW()

◆ reclassify()

◆ reseed()

◆ resort()

◆ set_params()

◆ update_centers()

Member Data Documentation

◆ calcsigmamean

◆ centers

◆ maxiter

◆ minchange

◆ mininclass

◆ NAME

◆ nchanged

◆ ncls

◆ nclstot

◆ outlierclass

◆ slowseed

◆ verbose