KMeans Class Reference

Public Member Functions
	KMeans (int K, int total_points, int total_values, int maxIterations, int maxObjects)
std::vector< Cluster >	run (std::vector< KPoint > &points, FileName fnClusters, FileName fnPoints)

Detailed Description

Definition at line 193 of file classify_kmeans_2d.cpp.

Constructor & Destructor Documentation

KMeans()

KMeans::KMeans ( int  K, int  total_points, int  total_values, int  maxIterations, int  maxObjects  )

inline

Definition at line 234 of file classify_kmeans_2d.cpp.

    {
        this->K = K;
        this->total_points = total_points;
        this->total_values = total_values;
        this->maxIterations = maxIterations;
        this->maxObjects = maxObjects;
    }

Member Function Documentation

run()

std::vector<Cluster> KMeans::run ( std::vector< KPoint > &  points, FileName  fnClusters, FileName  fnPoints  )

inline

Definition at line 244 of file classify_kmeans_2d.cpp.

    {
        // create clusters and choose K points as their centers centers
        std::vector<int> prohibited_indexes;
        std::random_device rd;  // Will be used to obtain a seed for the random number engine
        std::mt19937 gen(rd()); // Standard mersenne_twister_engine seeded with rd()
        std::uniform_int_distribution<> udistr(0,total_points-1);

        if (total_points == 0)
        {
            std::ostringstream msg;
            msg << "Division by zero: total_points == 0";
            throw std::runtime_error(msg.str()); 
        }

        for (int i = 0; i < K; i++)
        {
            while (true)
            {
                int index_point = udistr(gen);

                if (find(prohibited_indexes.begin(), prohibited_indexes.end(),
                    index_point) == prohibited_indexes.end())
                {
                    prohibited_indexes.push_back(index_point);
                    points[index_point].setCluster(i);
                    Cluster cluster(i, points[index_point]);
                    clusters.push_back(cluster);
                    break;
                }
            }
        }

        // if clusters already exists, load their computed centers
        std::fstream savedClusters(fnClusters.c_str());
        if (savedClusters.good())
        {
            std::string line;
            for (int i = 0; i < K; i++)
            {
                std::getline(savedClusters, line);
                std::stringstream ss(line);
                double point_value;
                for (int j = 0; j < total_values; j++)
                {
                    ss >> point_value;
                    clusters[i].setCentralValue(j, point_value);
                }
            }
        }

        int iter = 1;
        while(true)
        {
            bool done = true;

            // when total_points is larger than threshold value maxObjects
            // we only assign labels to point based on nearest center
            if ((maxObjects != -1) && (total_points > maxObjects))
            {
                for (int i = 0; i < total_points; i++)
                {
                    int nearest_center = getIDNearestCenter(points[i]);
                    points[i].setCluster(nearest_center);
                    clusters[nearest_center].addPoint(points[i]);
                }
            }
            else  // perform k-means clustering
            {
                // associates each point to the nearest center
                for (int i = 0; i < total_points; i++)
                {
                    int old_cluster = points[i].getCluster();
                    int nearest_center = getIDNearestCenter(points[i]);

                    if (old_cluster != nearest_center)
                    {
                        if (old_cluster != -1)
                            clusters[old_cluster].removePoint(points[i].getID());

                        points[i].setCluster(nearest_center);
                        clusters[nearest_center].addPoint(points[i]);
                        done = false;
                    }
                }

                // recalculating the center of each cluster
                for (int i = 0; i < K; i++)
                {
                    for (int j = 0; j < total_values; j++)
                    {
                        int total_points = clusters[i].getTotalPoints();
                        double sum = 0.0;

                        if (total_points > 0)
                        {
                            for (int p = 0; p < total_points; p++)
                                sum += clusters[i].getPoint(p).getValue(j);

                            clusters[i].setCentralValue(j, sum / total_points);
                        }
                    }
                }
            }
            if (done == true || iter >= maxIterations) break;
            iter++;
        }

        // This code is removing outliers, whose distance from centroid is
        // 1.5*stddev, its efficiency depends strongly on feature extraction
        /*
        double dist, sum, stddev;
        std::vector<double> cluster_point_dist;
        for (int i = 0; i < K; i++)
        {
            dist = 0.0;
            int points_orig_total = clusters[i].getTotalPoints();

            for (int p = 0; p < points_orig_total; p++)
            {
                sum = 0.0;
                for (int j = 0; j < total_values; j++)
                    sum += pow(clusters[i].getCentralValue(j) -
                           clusters[i].getPoint(p).getValue(j), 2.0);

                cluster_point_dist.push_back(sqrt(sum));
                dist += sqrt(sum) / points_orig_total;
            }

            for (int p = 0; p < points_orig_total; p++)
                stddev += pow(cluster_point_dist[p] - dist, 2.0);

            stddev = sqrt(stddev / points_orig_total);

            int pp = 0;
            for (int p = 0; p < points_orig_total; p++)
            {
                // Swich this condition for taking only eliminated particles
                if ((cluster_point_dist[p] > (dist + 1.5*stddev)) ||
                    (cluster_point_dist[p] < (dist - 1.5*stddev)))
                    clusters[i].removePoint(clusters[i].getPoint(pp).getID());
                else pp++;
            }
        }
        */

        std::ofstream saveData;

        // saving clusters
        saveData.open(fnClusters.c_str());
        for (int i = 0; i < K; i++)
        {
            for (int j = 0; j < total_values; j++)
                saveData << clusters[i].getCentralValue(j) << " ";
            saveData << std::endl;
        }
        saveData.close();

        // saving points
        saveData.open(fnPoints.c_str());
        for (int i = 0; i < total_points; i++)
        {
            for (int j = 0; j < total_values; j++)
                saveData << points[i].getValue(j) << " ";
            saveData << std::endl;
        }
        saveData.close();

        return clusters;
    }

---

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

• xmipp/legacy/libraries/reconstruction/classify_kmeans_2d.cpp