EMAN::KMeansAnalyzer Class Reference

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]

List of all members.

Public Member Functions
	KMeansAnalyzer ()
virtual int	insert_image (EMData *image)
	insert a image to the list of input images
virtual vector< EMData * >	analyze ()
	main function for Analyzer, analyze input images and create output images
string	get_name () const
	Get the Analyzer's name.
string	get_desc () const
	Get the Analyzer's description.
void	set_params (const Dict &new_params)
	Set the Analyzer parameters using a key/value dictionary.
TypeDict	get_param_types () const
	Get Analyzer parameter information in a dictionary.
Static Public Member Functions
static Analyzer *	NEW ()
Protected Member Functions
void	update_centers (int sigmas=0)
void	reclassify ()
void	reseed ()
Protected Attributes
vector< EMData * >	centers
int	ncls
int	verbose
int	minchange
int	maxiter
int	mininclass
int	nchanged
int	slowseed
int	calcsigmamean

---

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
	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 138 of file analyzer.h.

---

Constructor & Destructor Documentation

EMAN::KMeansAnalyzer::KMeansAnalyzer

(

)

[inline]

Definition at line 141 of file analyzer.h.

Referenced by NEW().

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

---

Member Function Documentation

virtual int EMAN::KMeansAnalyzer::insert_image

(

EMData *

image

)

[inline, virtual]

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 143 of file analyzer.h.

References EMAN::Analyzer::images.

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

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 84 of file analyzer.cpp.

References calcsigmamean, centers, EMAN::Util::get_irand(), get_xsize(), get_ysize(), get_zsize(), EMAN::Analyzer::images, maxiter, minchange, mininclass, nchanged, ncls, reclassify(), reseed(), slowseed, update_centers(), and verbose.

{
if (ncls<=1) return vector<EMData *>();
//srandom(time(0));

// These are the class centers, start each with a random image
int nptcl=images.size();
int nclstot=ncls;
if (calcsigmamean) centers.resize(nclstot*2);
else centers.resize(nclstot);
if (mininclass<1) mininclass=1;

if (slowseed) {
        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;
}

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();

}

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;
        reclassify();
        if (verbose) printf("iter %d>  %d (%d)\n",i,nchanged,ncls);
        if (nchanged<minchange && ncls==nclstot) break;
        update_centers();

        if (slowseed && i%3==2 && ncls<nclstot) {
                centers[ncls]=0;
                ncls++;
                reseed();
        }
}
update_centers(calcsigmamean);

return centers;
}

string EMAN::KMeansAnalyzer::get_name

(

)

const [inline, virtual]

Get the Analyzer's name.

Each Analyzer is identified by a unique name.

Returns:

The Analyzer's name.

Implements EMAN::Analyzer.

Definition at line 150 of file analyzer.h.

                {
                        return "kmeans";
                }

string EMAN::KMeansAnalyzer::get_desc

(

)

const [inline, virtual]

Get the Analyzer's description.

Returns:

The Analyzer's description.

Implements EMAN::Analyzer.

Definition at line 155 of file analyzer.h.

                {
                        return "k-means classification";
                }

static Analyzer* EMAN::KMeansAnalyzer::NEW

(

)

[inline, static]

Definition at line 160 of file analyzer.h.

References KMeansAnalyzer().

Referenced by EMAN::Factory< T >::Factory().

                {
                        return new KMeansAnalyzer();
                }

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 71 of file analyzer.cpp.

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

{
        params = new_params;
        if (params.has_key("ncls")) ncls = 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"];

}

TypeDict EMAN::KMeansAnalyzer::get_param_types

(

)

const [inline, virtual]

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 167 of file analyzer.h.

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

                {
                        TypeDict d;
                        d.put("verbose", EMObject::INT, "Display progress if set, more detail with larger numbers (9 max)");
                        d.put("ncls", EMObject::INT, "number of desired classes");
                        d.put("maxiter", EMObject::INT, "maximum number of iterations");
                        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("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;
                }

void KMeansAnalyzer::update_centers

(

int

sigmas = 0

)

[protected]

Definition at line 130 of file analyzer.cpp.

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

Referenced by analyze().

                                              {
int nptcl=images.size();
//int repr[ncls];
int * repr = new int[ncls];

for (int i=0; i<ncls; i++) {
        centers[i]->to_zero();
        if (sigmas) centers[i+ncls]->to_zero();
        repr[i]=0;
}

for (int i=0; i<nptcl; i++) {
        int cid=images[i]->get_attr("class_id");
        centers[cid]->add(*images[i]);
        if (sigmas) centers[cid+ncls]->addsquare(*images[i]);
        repr[cid]++;
}

for (int i=0; i<ncls; i++) {
        if (repr[i]<mininclass) {
                delete centers[i];
                centers[i]=0;
                repr[i]=0;
        }
        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();

delete [] repr;
}

void KMeansAnalyzer::reclassify

(

)

[protected]

Definition at line 230 of file analyzer.cpp.

References centers, EMAN::Cmp::cmp(), EMAN::Analyzer::images, nchanged, and ncls.

Referenced by analyze().

                                {
int nptcl=images.size();

Cmp *c = Factory < Cmp >::get("sqeuclidean");
for (int i=0; i<nptcl; i++) {
        float best=1.0e38f;
        int bestn=0;
        for (int j=0; j<ncls; j++) {
                float d=c->cmp(images[i],centers[j]);
//images[i]->cmp("sqeuclidean",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);
}
delete c;
}

void KMeansAnalyzer::reseed

(

)

[protected]

Definition at line 176 of file analyzer.cpp.

References centers, EMAN::Cmp::cmp(), get_attr(), EMAN::Util::get_irand(), EMAN::Analyzer::images, and ncls.

Referenced by analyze(), and update_centers().

                            {
// if no classes need reseeding just return
int nptcl=images.size();
int i,j;
for (i=0; i<ncls; i++) {
        if (!centers[i]) break;
}
if (i==ncls) return;

int * best = new int[ncls];     // particles in the average
float *sigmas = new float[ncls]; // array of deviations

for (int i=0; i<ncls; i++) { sigmas[i]=0; best[i]=0; }

// compute the deviation of each class
Cmp *c = Factory < Cmp >::get("sqeuclidean");
for (int i=0; i<nptcl; i++) {
        int cid=images[i]->get_attr("class_id");
        if (!centers[cid]) continue;
//      sigmas[cid]+=(float)imc->get_attr("square_sum");
        float d=c->cmp(images[i],centers[cid]);
        if (d>sigmas[cid]) {
                sigmas[cid]=d;  // Instead of using sigma, use the largest distance in the class
                best[cid]=i;
        }
}
delete c;
//for (i=0; i<ncls; i++) sigmas[i]/=repr[i];    //since we aren't doing a sigma now...

//we could sort the list, but for this use we just search
for (i=0; i<ncls; i++) {
        if (centers[i]) continue;

        float maxsig=0;
        int maxi=0;
        // find the class with the largest sigma
        for (j=0; j<ncls; j++) {
                if (sigmas[j]>maxsig) { maxsig=sigmas[j]; maxi=j; }
        }

        // find an image in that class
        for (j=0; j<ncls; j++) if ((int)images[j]->get_attr("class_id")==maxi) break;
        if (Util::get_irand(0,1)==0) centers[i]=images[best[maxi]]->copy();
        else centers[i]=images[j]->copy();
        centers[i]->set_attr("ptcl_repr",1);
        sigmas[maxi]=0;         // if we get another one to reseed, pick the next largest set (zero out the current one)
        printf("reseed %d -> %d (%d or %d)\n",i,maxi,best[maxi],j);
}

delete [] sigmas;
delete [] best;
}

---

Member Data Documentation

vector<EMData *> EMAN::KMeansAnalyzer::centers [protected]

Definition at line 185 of file analyzer.h.

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

int EMAN::KMeansAnalyzer::ncls [protected]

Definition at line 186 of file analyzer.h.

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

int EMAN::KMeansAnalyzer::verbose [protected]

Definition at line 187 of file analyzer.h.

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

int EMAN::KMeansAnalyzer::minchange [protected]

Definition at line 188 of file analyzer.h.

Referenced by analyze(), and set_params().

int EMAN::KMeansAnalyzer::maxiter [protected]

Definition at line 189 of file analyzer.h.

Referenced by analyze(), and set_params().

int EMAN::KMeansAnalyzer::mininclass [protected]

Definition at line 190 of file analyzer.h.

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

int EMAN::KMeansAnalyzer::nchanged [protected]

Definition at line 191 of file analyzer.h.

Referenced by analyze(), and reclassify().

int EMAN::KMeansAnalyzer::slowseed [protected]

Definition at line 192 of file analyzer.h.

Referenced by analyze(), and set_params().

int EMAN::KMeansAnalyzer::calcsigmamean [protected]

Definition at line 193 of file analyzer.h.

Referenced by analyze(), and set_params().

---

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

• analyzer.h
• analyzer.cpp