---

cluster.h

Go to the documentation of this file.

#ifndef fl_cluster_h
#define fl_cluster_h


#include "fl/matrix.h"
#include "fl/socket.h"
#include "fl/descriptor.h"

#include <iostream>
#include <vector>

#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>


namespace fl
{
  // Generic clustering interface ---------------------------------------------

  class ClusterMethod
  {
  public:
        virtual void          run (const std::vector< Vector<float> > & data) = 0;  
        virtual int           classify (const Vector<float> & point) = 0;  
        virtual Vector<float> distribution (const Vector<float> & point) = 0;  
        virtual int           classCount () = 0;  
        virtual Vector<float> representative (int group) = 0;  

        // The read () and write () methods should serialize enough data to either
        // resume clustering with a call to run () or to answer cluster queries via
        // classify () and representative ().
        virtual void read (std::istream & stream);
        virtual void write (std::ostream & stream, bool withName = false);

        bool stop;  
  };


  // Soft K-means -------------------------------------------------------------

  class ClusterGauss
  {
  public:
        ClusterGauss (Vector<float> & center, float alpha = 1.0);
        ClusterGauss (Vector<float> & center, Matrix<float> & covariance, float alpha = 1.0);
        ClusterGauss (std::istream & stream);  
        ~ClusterGauss ();

        void prepareInverse ();  
        float probability (const Vector<float> & point, float * scale = NULL, float * minScale = NULL);  
        void read (std::istream & stream);
        void write (std::ostream & stream);

        float alpha;
        Vector<float> center;
        Matrix<float> covariance;
        Matrix<float> eigenvectors;
        Vector<float> eigenvalues;
        Matrix<float> eigenverse;
        float det;  
  };

  class KMeans : public ClusterMethod
  {
  public:
        KMeans (float maxSize, float minSize, int initialK, int maxK, const std::string & clusterFileName = "");  
        KMeans (std::istream & stream, const std::string & clusterFileName = "");  

        virtual void          run (const std::vector< Vector<float> > & data);
        virtual int           classify (const Vector<float> & point);
        virtual Vector<float> distribution (const Vector<float> & point);
        virtual int           classCount ();
        virtual Vector<float> representative (int group);
        virtual void          read (std::istream & stream);
        virtual void          write (std::ostream & stream, bool withName = false);

        void initialize (const std::vector< Vector<float> > & data);
        void estimate (const std::vector< Vector<float> > & data, Matrix<float> & member, int jbegin, int jend);
        float maximize (const std::vector< Vector<float> > & data, const Matrix<float> & member, int i);
        bool convergence (const std::vector< Vector<float> > & data, const Matrix<float> & member, float largestChange);

        // State of clustering process
        float maxSize;  
        float minSize;  
        int initialK;  
        int maxK;  
        std::vector<ClusterGauss> clusters;
        std::vector<float> changes;
        std::vector<float> velocities;

        // Control information
        std::string clusterFileName;
        time_t clusterFileTime;  
        off_t clusterFileSize;
  };

  class KMeansParallel : public KMeans
  {
  public:
        KMeansParallel (float maxSize, float minSize, int initialK, int maxK, const std::string & clusterFileName = "");
        KMeansParallel (std::istream & stream, const std::string & clusterFileName = "");

        virtual void run (const std::vector< Vector<float> > & data);

        static void * listenThread (void * arg);
        static void * proxyThread (void * arg);
        void client (std::string serverName);

        // Shared state for parallel processing
        int iteration;
        const std::vector<Vector<float> > * data;
        Matrix<float> member;
        float largestChange;
        enum EMstate
        {
          initializing,
          estimating,
          maximizing,
          checking
        };
        EMstate          state;
        pthread_mutex_t  stateLock;  
        std::vector<int> workUnits;  
        int              unitsPending;  

        struct ThreadDataHolder
        {
          KMeansParallel * kmeans;
          int connection;
          struct sockaddr_in peer;
        };
  };

  // Find a more elegant way to disseminate these constants!
#define workUnitSize 1000
#define portNumber   60000
  const float smallestNormalFloat = 1e-38;
  const float largestNormalFloat = 1e38;
  const float largestDistanceFloat = 87;  


  // Kohonen map --------------------------------------------------------------

  class ClusterCosine
  {
  public:
        ClusterCosine (int dimension);
        ClusterCosine (Vector<float> & center);
        ClusterCosine (std::istream & stream);

        float distance (const Vector<float> & point);
        float update (const Vector<float> & point, float weight);

        void read (std::istream & stream);
        void write (std::ostream & stream);

        Vector<float> center;
  };

  class Kohonen : public ClusterMethod
  {
  public:
        Kohonen (int width, float sigma = 1.0, float learningRate = 0.1, float decayRate = 0.5);
        Kohonen (std::istream & stream);

        virtual void          run (const std::vector< Vector<float> > & data);
        virtual int           classify (const Vector<float> & point);
        virtual Vector<float> distribution (const Vector<float> & point);
        virtual int           classCount ();
        virtual Vector<float> representative (int group);
        virtual void          read (std::istream & stream);
        virtual void          write (std::ostream & stream, bool withName = false);

        std::vector<ClusterCosine> map;
        int width;  
        float sigma;  
        float learningRate;  
        float decayRate;  
  };


  // Agglomerative clustering -------------------------------------------------

  class ClusterAgglomerative
  {
  public:
        ClusterAgglomerative (const Vector<float> & center, int count = 1);
        ClusterAgglomerative (std::istream & stream);

        void operator += (const ClusterAgglomerative & that);
        void read (std::istream & stream);
        void write (std::ostream & stream);

        Vector<float> center;
        int count;  
  };

  class Agglomerate : public ClusterMethod
  {
  public:
        Agglomerate (Comparison * comparison, float distanceLimit, int minClusters = 1);
        Agglomerate (std::istream & stream);
        ~Agglomerate ();

        virtual void          run (const std::vector< Vector<float> > & data);
        virtual int           classify (const Vector<float> & point);
        virtual Vector<float> distribution (const Vector<float> & point);
        virtual int           classCount ();
        virtual Vector<float> representative (int group);
        virtual void read (std::istream & stream);
        virtual void write (std::ostream & stream, bool withName = false);

        Comparison * comparison;
        float distanceLimit;  
        int minClusters;  
        std::vector<ClusterAgglomerative *> clusters;
  };
}


#endif

---