jubatus::core::clustering::compressor::kmeans_compressor Class Reference

#include <kmeans_compressor.hpp>

Inheritance diagram for jubatus::core::clustering::compressor::kmeans_compressor:

Collaboration diagram for jubatus::core::clustering::compressor::kmeans_compressor:

Public Member Functions
void	compress (const wplist &src, size_t bsize, size_t dstsize, wplist &dst)
virtual double	get_probability (const weighted_point &p, double min_dist, const weighted_point &nearest_bp, double bp_score, double weight_sum, double squared_min_dist_sum)
	kmeans_compressor (const clustering_config &cfg)
	~kmeans_compressor ()
Public Member Functions inherited from jubatus::core::clustering::compressor::compressor
	compressor (const clustering_config &cfg)
	MSGPACK_DEFINE (config_)
virtual	~compressor ()

Private Member Functions
void	bicriteria_to_coreset (const wplist &src, const wplist &bicriteria, size_t dstsize, wplist &dst)
void	get_bicriteria (const wplist &src, size_t bsize, size_t dstsize, wplist &dst)

Detailed Description

Definition at line 27 of file kmeans_compressor.hpp.

Constructor & Destructor Documentation

jubatus::core::clustering::compressor::kmeans_compressor::kmeans_compressor ( const clustering_config &  cfg )

explicit

Definition at line 107 of file kmeans_compressor.cpp.

  : compressor(cfg) {
}

jubatus::core::clustering::compressor::kmeans_compressor::~kmeans_compressor

(

)

Definition at line 111 of file kmeans_compressor.cpp.

                                      {
}

Member Function Documentation

void jubatus::core::clustering::compressor::kmeans_compressor::bicriteria_to_coreset ( const wplist &  src, const wplist &  bicriteria, size_t  dstsize, wplist &  dst  )

private

Definition at line 194 of file kmeans_compressor.cpp.

References get_probability(), jubatus::core::clustering::min_dist(), and jubatus::core::clustering::weighted_point::weight.

Referenced by compress().

                 {
  if (bicriteria.size() == 0) {
    dst = src;
    return;
  }
  double weight_sum = 0;
  double squared_min_dist_sum = 0;
  std::vector<size_t> nearest_indexes(src.size());
  std::vector<double> nearest_distances(src.size());
  std::vector<double> bicriteria_scores(bicriteria.size());
  for (size_t i = 0; i < src.size(); ++i) {
    double weight = src[i].weight;
    std::pair<int, double> m = min_dist(src[i], bicriteria);
    nearest_indexes[i] = m.first;
    nearest_distances[i] = m.second;

    bicriteria_scores[m.first] += weight;
    squared_min_dist_sum += m.second * m.second * weight;
    weight_sum += weight;
  }
  squared_min_dist_sum = std::max(squared_min_dist_sum,
                                  std::numeric_limits<double>::min());
  std::vector<double> weights;
  double sumw = 0;
  for (size_t i = 0; i < src.size(); ++i) {
    double prob = get_probability(
        src[i],
        nearest_distances[i],
        bicriteria[nearest_indexes[i]],
        bicriteria_scores[nearest_indexes[i]],
        weight_sum,
        squared_min_dist_sum);
    weights.push_back(prob);
    sumw += prob;
  }

  discrete_distribution d(weights.begin(), weights.end());

  std::vector<size_t> ind(dstsize);
  std::generate(ind.begin(), ind.end(), d);

  for (std::vector<size_t>::iterator it = ind.begin(); it != ind.end(); ++it) {
    size_t index = *it;
    weighted_point sample = src[index];
    double prob = weights[index] / sumw;
    sample.weight *= 1.0 / dstsize / prob;
    dst.push_back(sample);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void jubatus::core::clustering::compressor::kmeans_compressor::compress ( const wplist &  src, size_t  bsize, size_t  dstsize, wplist &  dst  )

virtual

Implements jubatus::core::clustering::compressor::compressor.

Definition at line 114 of file kmeans_compressor.cpp.

References bicriteria_to_coreset(), jubatus::core::clustering::concat(), and get_bicriteria().

                 {
  if (dstsize >= src.size()) {
    concat(src, dst);
    return;
  }
  wplist bicriteria;
  get_bicriteria(src, bsize, dstsize, bicriteria);
  if (bicriteria.size() < dstsize) {
    wplist srcclone = src;
    bicriteria_to_coreset(
        srcclone,
        bicriteria,
        dstsize - bicriteria.size(),
        dst);
  }
  bicriteria_as_coreset(src, bicriteria, dstsize, dst);
}

Here is the call graph for this function:

void jubatus::core::clustering::compressor::kmeans_compressor::get_bicriteria ( const wplist &  src, size_t  bsize, size_t  dstsize, wplist &  dst  )

private

Definition at line 136 of file kmeans_compressor.cpp.

References jubatus::core::clustering::min_dist().

Referenced by compress().

                 {
  dst.clear();
  wplist resid = src;
  vector<double> weights(src.size());
  double r =
    (1 - std::exp(bsize * (std::log(bsize) - std::log(src.size())) / dstsize))
      / 2;
  r = max(0.1, r);
  std::vector<size_t> ind(bsize);
  while (resid.size() > 1 && dst.size() < dstsize) {
    weights.resize(resid.size());
    for (wplist::const_iterator it = resid.begin(); it != resid.end(); ++it) {
      weights[it - resid.begin()] = it->weight;
    }

    // Sample `bsize` points and insert them to the result
    discrete_distribution d(weights.begin(), weights.end());
    std::generate(ind.begin(), ind.end(), d);

    std::sort(ind.begin(), ind.end());
    ind.erase(std::unique(ind.begin(), ind.end()), ind.end());

    for (std::vector<size_t>::iterator it = ind.begin();
         it != ind.end(); ++it) {
      dst.push_back(resid[*it]);
    }

    // Remove `r` nearest points from `resid`
    std::vector<double> distances;
    for (wplist::iterator itr = resid.begin(); itr != resid.end(); ++itr) {
      distances.push_back(-min_dist(*itr, dst).second);
    }
    // TODO(unno): Is `r` lesser than 1.0?
    size_t size = std::min(resid.size(),
                           static_cast<size_t>(resid.size() * r));
    if (size == 0) {
      size = 1;
    }

    partial_sort_by(distances, resid, size);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

double jubatus::core::clustering::compressor::kmeans_compressor::get_probability ( const weighted_point &  p, double  min_dist, const weighted_point &  nearest_bp, double  bp_score, double  weight_sum, double  squared_min_dist_sum  )

virtual

Reimplemented in jubatus::core::clustering::compressor::gmm_compressor.

Definition at line 183 of file kmeans_compressor.cpp.

References jubatus::core::clustering::weighted_point::weight.

Referenced by bicriteria_to_coreset().

                                 {
  return std::ceil(weight_sum * (
      min_dist * min_dist * p.weight / squared_min_dist_sum)) + 1;
}

Here is the caller graph for this function:

---

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

• jubatus/core/clustering/kmeans_compressor.hpp
• jubatus/core/clustering/kmeans_compressor.cpp