|| || || || || || || ||

---

KmeansClustering.h

Go to the documentation of this file.

#ifndef Impala_Core_Matrix_KmeansClustering_h
#define Impala_Core_Matrix_KmeansClustering_h

#include "Core/Matrix/MatFunc.h"
#include "Core/Matrix/Mat.h"
#include "Core/Matrix/MatDrawRandomRows.h"
#include "Core/Matrix/MatKeepSpecificRows.h"
#include "Core/Matrix/VectorQuantize.h"

namespace Impala
{
namespace Core
{
namespace Matrix
{


Mat*
KmeansClustering(Mat* clusterInput, int k)
{
    ILOG_VAR(Impala.Core.Matrix.KmeansClustering);
    Timer totalTimer;

    // initialize codebook by random drawing
    Mat* codebook = MatDrawRandomRows(clusterInput, k);

    double threshold = 1e-5;
    double diff = threshold + 1.0;
    std::vector<Real64> averageDistances;
    int n = MatNrRow(clusterInput);
    int d = MatNrCol(clusterInput);
    int* numberAssigned = new int[k];
    while(diff > threshold)
    {
        Timer iterTimer;
        // assignment will contain indices and distortion/distance
        Mat* assignment = VectorQuantize(clusterInput, codebook);

        Real64 averageDist = 0.0;
        for(int j = 0; j < n; j++)
        {
            averageDist += *MatE(assignment, j, 1);
        }
        averageDist = averageDist / MatNrRow(clusterInput);
        averageDistances.push_back(averageDist);

        // reset the codebook to all zeros, to prepare for update
        SetVal(codebook, 0.0);

        for(int i = 0; i < k; i++) numberAssigned[i] = 0;

        // sum the observations of the different clusters
        for(int j = 0; j < n; j++)
        {
            int cluster = static_cast<int>(*MatE(assignment, j, 0));
            numberAssigned[cluster]++;
            for(int i = 0; i < d; i++)
            {
                *MatE(codebook, cluster, i) += *MatE(clusterInput, j, i);
            }
        }

        std::vector<int> usedClusters;
        usedClusters.reserve(MatNrRow(codebook));
        for(int cluster = 0; cluster < MatNrRow(codebook); cluster++)
        {
            if(numberAssigned[cluster] > 0)
            {
                for(int i = 0; i < d; i++)
                {
                    *MatE(codebook, cluster, i) /= numberAssigned[cluster];
                }
                usedClusters.push_back(cluster);
            }
        }

        if(usedClusters.size() < MatNrRow(codebook))
        {
            // one of the clusters has no elements: remove it
            Mat* temp = MatKeepSpecificRows(codebook, usedClusters);
            delete codebook;
            codebook = temp;
        }

        if(averageDistances.size() > 1)
        {
            diff = averageDistances[averageDistances.size()-2] - averageDistances[averageDistances.size()-1];
            ILOG_INFO("K-means progress: " << averageDistances[averageDistances.size()-2] << " " << averageDistances[averageDistances.size()-1] << " " << diff << " " << MatNrRow(codebook) << " iterTime=" << iterTimer.SplitTimeStr() << " totalTimer=" << totalTimer.SplitTimeStr());
        }
        delete assignment;
    }
    delete numberAssigned;
    return codebook;
}


} // namespace Matrix
} // namespace Core
} // namespace Impala

#endif

---