FuzzyCMeans Class Reference

#include <fcmeans.h>

Inheritance diagram for FuzzyCMeans:

Collaboration diagram for FuzzyCMeans:

Public Member Functions
	FuzzyCMeans (double _m, double _epsilon, unsigned _epochs)
virtual	~FuzzyCMeans ()
virtual void	train (FuzzyCodeBook &_xmippDS, TS &_examples) const
virtual double	fuzzyTest (const FuzzyCodeBook &_xmippDS, const TS &_examples) const
virtual double	test (const FuzzyCodeBook &_xmippDS, const TS &_examples) const
double	F (const FuzzyCodeBook &_xmippDS) const
double	H (const FuzzyCodeBook &_xmippDS) const
double	S (const FuzzyCodeBook &_xmippDS, const TS &_examples) const
Public Member Functions inherited from ClassificationAlgorithm< FuzzyCodeBook >
	ClassificationAlgorithm (const std::string &_ID="")
virtual	~ClassificationAlgorithm ()
virtual void	train (DS &_ds, const TS &_examples) const
virtual void	train (DS &_ds, TS &_examples) const
virtual double	test (const DS &_ds, const TS &_examples) const=0
virtual const std::string &	setID () const
virtual std::string &	setID ()
void	setListener (BaseListener *_listener)

Protected Member Functions
void	printSelf (std::ostream &_os) const
	print itself on standard output More...

Protected Attributes
double	m
double	epsilon
unsigned	epochs
Protected Attributes inherited from ClassificationAlgorithm< FuzzyCodeBook >
std::string	ID
BaseListener *	listener

Additional Inherited Members
Public Types inherited from ClassificationAlgorithm< FuzzyCodeBook >
typedef FuzzyCodeBook	DS
typedef DS::TS	TS

Detailed Description

This class implements Fuzzy c-means clustering method (Bezdeck) an unsupervised clustering algorithm.

Definition at line 46 of file fcmeans.h.

Constructor & Destructor Documentation

FuzzyCMeans()

FuzzyCMeans::FuzzyCMeans ( double  _m, double  _epsilon, unsigned  _epochs  )

inline

Big mega ctor. Creates a Fuzzy c-means codebook, and initializes it Parameter: _m Fuzzy constant Parameter: _epsilon Stopping criterion Parameter: _epochs Number of epochs or iterations

Definition at line 57 of file fcmeans.h.

            : ClassificationAlgorithm< FuzzyCodeBook >("xmippFCMeans"),
            m(_m), epsilon(_epsilon),
            epochs(_epochs)
    {}

~FuzzyCMeans()

virtual FuzzyCMeans::~FuzzyCMeans ( )

inlinevirtual

Definition at line 75 of file fcmeans.h.

    {}

Member Function Documentation

F()

double FuzzyCMeans::F

(

const FuzzyCodeBook &

_xmippDS

)

const

Calculates Partition Coefficient (F) validity functional Parameter: _xmippDS Data structure to train, a codeBook in this case (It should be maximum) For more information see: J.C. Bezdek, "Pattern Recognition with Fuzzy Objective Function Algorithms", Plenum Press, New York, 1981.

Calculates Partition Coefficient (F) validity functional Parameter: _xmippDS Data structure to train, a codeBook in this case

Notes on F: For U in Mfc (fuzzy partition space) 1/C <= F <= 1 for F = 1, U is hard (zeros and ones only) for F = 1/C, U = 1/C*ones(C,n);

(max)

For more information see: J.C. Bezdek, "Pattern Recognition with Fuzzy Objective Function Algorithms", Plenum Press, New York, 1981.

Definition at line 262 of file fcmeans.cpp.

{
    double F = 0.;
    for (unsigned k = 0; k < _xmippDS.membVectors(); k++)
        for (unsigned i = 0; i < _xmippDS.membClusters(); i++)
            F += pow((double)(_xmippDS.memb[k][i]), 2);
    return (F / (double)(_xmippDS.membVectors()));
}

fuzzyTest()

double FuzzyCMeans::fuzzyTest ( const FuzzyCodeBook &  _xmippDS, const TS &  _examples  ) const

virtual

Tests with the training set using for training. Fuzzy membership is used for testing Parameter: _xmippDS Data structure to train, a codeBook in this case Parameter: _examples The training set returns the quantization error

Tests with the training set using for training. Parameter: _examples The training set

Definition at line 218 of file fcmeans.cpp.

{

    // Defines verbosity

    int verbosity = listener->getVerbosity();
    if (verbosity)
    {
        listener->OnReportOperation((std::string) "Testing....\n");
        listener->OnInitOperation(_examples.size());
    }

    double distortion = 0;
    for (unsigned i = 0; i < _examples.size(); i ++)
    {
        unsigned best = _xmippDS.fuzzyOutput(i);
        distortion += euclideanDistance(_xmippDS.theItems[best], _examples.theItems[i]);
        if (verbosity)
            listener->OnProgress(i);
    };
    if (verbosity)
        listener->OnProgress(_examples.size());

    return distortion / (double)_examples.size();
}

H()

double FuzzyCMeans::H

(

const FuzzyCodeBook &

_xmippDS

)

const

Calculates Partition Entropy (H) validity functional Parameter: _xmippDS Data structure to train, a codeBook in this case (It should be minimum) For more information see: J.C. Bezdek, "Pattern Recognition with Fuzzy Objective Function Algorithms", Plenum Press, New York, 1981.

Calculates Partition Entropy (H) validity functional Parameter: _xmippDS Data structure to train, a codeBook in this case

Notes on H: For U in Mfc 0 <= H <= log(C) for H = 0, U is hard for H = log(C), U = 1/C*ones(C,n); 0 <= 1 - F <= H (strict inequality if U not hard)

(min)

For more information see: J.C. Bezdek, "Pattern Recognition with Fuzzy Objective Function Algorithms", Plenum Press, New York, 1981.

Definition at line 289 of file fcmeans.cpp.

{
    double H = 0.;
    for (unsigned k = 0; k < _xmippDS.membVectors(); k++)
        for (unsigned i = 0; i < _xmippDS.membClusters(); i++)
            if (_xmippDS.memb[k][i] != 0.)
                H += (double)(_xmippDS.memb[k][i]) * log((double)(_xmippDS.memb[k][i]));
    return (-H / (double)(_xmippDS.membVectors()));
}

printSelf()

void FuzzyCMeans::printSelf ( std::ostream &  _os ) const

protectedvirtual

print itself on standard output

Reimplemented from ClassificationAlgorithm< FuzzyCodeBook >.

Definition at line 382 of file fcmeans.cpp.

{
    // Call base class, which will print ID
    _os << "Class (Algorithm): " << std::endl;
    ClassificationAlgorithm<FuzzyCodeBook>::printSelf(_os);
    _os << std::endl;
    // Print parameters in the same order they are declared
    _os << "Fuzzy constant m = " << m << std::endl;
    _os << "Epsilon eps = " << epsilon << std::endl;
    _os << "Iterations iter = " << epochs << std::endl << std::endl;
}

S()

double FuzzyCMeans::S	(	const FuzzyCodeBook &	_xmippDS,
		const TS &	_examples
	)		const

Calculates Compactness and separation index (S) validity functional Parameter: _xmippDS Data structure to train, a codeBook in this case Parameter: _examples A training set with the training examples (It should be minimum) For more information see: X.L. Xie and G. Beni, "A Validity Measure for Fuzzy Clustering", IEEE Trans. PAMI, 13(8):841-847, 1991.

Calculates Compactness and separation index (S) validity functional Parameter: _xmippDS Data structure to train, a codeBook in this case Parameter: _examples A training set with the training examples

(min)

For more information see: X.L. Xie and G. Beni, "A Validity Measure for Fuzzy Clustering", IEEE Trans. PAMI, 13(8):841-847, 1991.

Definition at line 337 of file fcmeans.cpp.

{

    std::vector< std::vector< floatFeature > > ICD;       // Intercluster distance
    std::vector< std::vector< floatFeature > > D;         // Distance from each data to cluster centers

    unsigned i;
    D.resize(_xmippDS.membClusters());
    for (i = 0; i < _xmippDS.membClusters(); i++)
    {
        std::vector <floatFeature> d;
        d.resize(_xmippDS.membVectors());
        for (unsigned k = 0; k < _xmippDS.membVectors(); k++)
            d[k] = (floatFeature)euclideanDistance(_xmippDS.theItems[i], _examples.theItems[k]);
        D[i] = d;
    } // for i

    ICD.resize(_xmippDS.membClusters());
    for (i = 0; i < _xmippDS.membClusters(); i++)
    {
        std::vector <floatFeature> v;
        v.resize(_xmippDS.membVectors());
        for (unsigned j = 0; j < _xmippDS.membClusters(); j++)
            v[j] = (floatFeature)euclideanDistance(_xmippDS.theItems[i], _xmippDS.theItems[j]);
        ICD[i] = v;
    } // for i

    floatFeature auxSum = 0;
    for (i = 0; i < _xmippDS.membClusters(); i++)
        for (unsigned k = 0; k < _xmippDS.membVectors(); k++)
            auxSum += (floatFeature) pow((double)(D[i][k] * _xmippDS.memb[k][i]), (double)m);

    floatFeature auxMin = MAXFLOAT;
    for (i = 0; i < _xmippDS.membClusters(); i++)
        for (unsigned j = i + 1; j < _xmippDS.membClusters(); j++)
            if (auxMin > ICD[i][j])
                auxMin = ICD[i][j];

    double S = auxSum / (double)(_xmippDS.membVectors()) / (double)(auxMin);
    return S;

}

test()

double FuzzyCMeans::test ( const FuzzyCodeBook &  _xmippDS, const TS &  _examples  ) const

virtual

Tests the Algorithm in a conventional way. Parameter: _xmippDS Data structure to train, a codeBook in this case Parameter: _examples A training set with the training examples

Test the Algorithm in a conventional way Parameter: _examples A training set with the training examples

Definition at line 184 of file fcmeans.cpp.

{

    // Defines verbosity

    int verbosity = listener->getVerbosity();
    if (verbosity)
    {
        listener->OnReportOperation((std::string) "Testing....\n");
        listener->OnInitOperation(_examples.size());
    }

    double distortion = 0;
    for (unsigned i = 0; i < _examples.size(); i ++)
    {
        const FeatureVector& auxS = _examples.theItems[i];
        unsigned best = _xmippDS.output(auxS);
        distortion += euclideanDistance(_xmippDS.theItems[best], _examples.theItems[i]);
        if (verbosity)
            listener->OnProgress(i);
    };

    if (verbosity)
        listener->OnProgress(_examples.size());

    return distortion / (double) _examples.size();
}

train()

void FuzzyCMeans::train ( FuzzyCodeBook &  _xmippDS, TS &  _examples  ) const

virtual

Trains the Algorithm Parameter: _xmippDS Data structure to train, a codeBook in this case Parameter: _examples A training set with the training examples

Ctor from stream Parameter: _is Must have the parameters in the same order than the previous ctor. check out this ************ Trains the Algorithm Parameter: _xmippDS Data structure to train, a codeBook in this case Parameter: _examples A training set with the training examples

Definition at line 50 of file fcmeans.cpp.

{

    // Defines verbosity

    int verbosity = listener->getVerbosity();
    if (verbosity)
        listener->OnReportOperation((std::string) "Training....\n");
    if (verbosity == 1 || verbosity == 3)
        listener->OnInitOperation(epochs);

    // Create auxiliar Codebook

    FuzzyCodeBook auxCB;


    // Create auxiliar stuff

    unsigned numClusters = _xmippDS.size();
    unsigned numVectors = _examples.size();
    unsigned i;
    unsigned j;
    unsigned k;
    double stopError = 0;
    double auxError = 0;
    double auxDist;
    double auxProd;
    double tmp;
    double auxExp;
    double auxSum;
    unsigned t = 0;  // Iteration index
    FeatureVector zero(_xmippDS.theItems[0].size()) ;
    fill(zero.begin(), zero.end(), 0.0);


    // Initialize auxiliary Codebook

    auxCB = _xmippDS;

    // Set auxExp

    auxExp = 2 / (m - 1);

    // This is the main code of the algorithm. Iterates "epochs" times


    stopError = epsilon + 1; // Initially must be higher

    while ((stopError > epsilon) && (t < epochs))
    {

        // Update Membership matrix

        for (k = 0; k < numVectors; k++)
        {

            auxProd = 1;
            for (j = 0; j < numClusters; j++)
                auxProd *= euclideanDistance(_xmippDS.theItems[j], _examples.theItems[k]);

            if (auxProd == 0.)
            { // Apply k-means criterion (Data-CB) must be > 0
                for (j = 0; j < numClusters; j ++)
                    if (euclideanDistance(_xmippDS.theItems[j], _examples.theItems[k]) == 0.)
                        _xmippDS.memb[k][j] = 1.0;
                    else
                        _xmippDS.memb[k][j] =  0.0;
            }
            else
            {
                for (i = 0; i < numClusters; i ++)
                {
                    auxDist = 0;
                    for (j = 0; j < numClusters; j ++)
                    {
                        tmp = euclideanDistance(_xmippDS.theItems[i], _examples.theItems[k]) /
                              euclideanDistance(_xmippDS.theItems[j], _examples.theItems[k]);
                        auxDist += pow(tmp, auxExp);
                    } // for j
                    _xmippDS.memb[k][i] = (floatFeature) 1.0 / auxDist;
                } // for i
            } // if auxProd
        } // for k


        // Update code vectors (Cluster Centers)

        for (i = 0; i < numClusters; i++)
        {
            _xmippDS.theItems[i] = zero;
            auxSum = 0;
            for (k = 0; k < numVectors; k++)
            {
                _xmippDS.theItems[i] += (floatFeature) pow((double)(_xmippDS.memb[k][i]), m) * _examples.theItems[k];
                auxSum += pow((double)(_xmippDS.memb[k][i]), m);
            } // for i
            _xmippDS.theItems[i] /= (floatFeature) auxSum;
        } // for k

        // Compute stopping criterion
        stopError = 0;
        for (i = 0; i < numClusters; i ++)
        {
            auxError = euclideanDistance(_xmippDS.theItems[i], auxCB.theItems[i]);
            stopError += auxError * auxError;
        } // for i


        // Update iteration index

        t++;
        auxCB = _xmippDS;

        if (verbosity == 1 || verbosity == 3)
            listener->OnProgress(t);
        if (verbosity >= 2)
        {
            char s[100];
            sprintf(s, "Iteration %d of %d. Code vectors variation: %g\n", t + 1, epochs, stopError);
            listener->OnReportOperation((std::string) s);
        }

    } // while

    if (verbosity == 1 || verbosity == 3)
        listener->OnProgress(epochs);

}// FuzzyCMeans::train

Member Data Documentation

epochs

unsigned FuzzyCMeans::epochs

protected

Definition at line 165 of file fcmeans.h.

epsilon

double FuzzyCMeans::epsilon

protected

Definition at line 164 of file fcmeans.h.

m

double FuzzyCMeans::m

protected

Definition at line 163 of file fcmeans.h.

---

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

• xmipp/libraries/classification/fcmeans.h
• xmipp/libraries/classification/fcmeans.cpp