77 lines
2.6 KiB
C
77 lines
2.6 KiB
C
|
/*
|
||
|
|
----
|
||
|
|
This file is NOT part of SECONDO.
|
||
|
|
* Authors: Greg Hamerly and Jonathan Drake
|
||
|
|
* Feedback: hamerly@cs.baylor.edu
|
||
|
|
* See: http://cs.baylor.edu/~hamerly/software/kmeans.php
|
||
|
|
* Copyright 2014
|
||
|
|
*
|
||
|
|
* DrakeKmeans implements Drake's k-means algorithm that uses a user-defined
|
||
|
|
* number of lower bounds.
|
||
|
|
----
|
||
|
|
|
||
|
|
//paragraph [1] Title: [{\Large \bf \begin{center}] [\end{center}}]
|
||
|
|
//[TOC] [\tableofcontents]
|
||
|
|
|
||
|
|
[1] Declarations for the Drake's k-means algorithm
|
||
|
|
|
||
|
|
|
||
|
|
1 Declarations for the Drake's k-means algorithm
|
||
|
|
|
||
|
|
*/
|
||
|
|
|
||
|
|
#ifndef DRAKE_KMEANS_H
|
||
|
|
#define DRAKE_KMEANS_H
|
||
|
|
|
||
|
|
/* Authors: Greg Hamerly and Jonathan Drake
|
||
|
|
* Feedback: hamerly@cs.baylor.edu
|
||
|
|
* See: http://cs.baylor.edu/~hamerly/software/kmeans.php
|
||
|
|
* Copyright 2014
|
||
|
|
*
|
||
|
|
* DrakeKmeans implements Drake's k-means algorithm that uses a user-defined
|
||
|
|
* number of lower bounds.
|
||
|
|
*/
|
||
|
|
|
||
|
|
#include "triangle_inequality_base_kmeans.h"
|
||
|
|
#include <utility>
|
||
|
|
#include <sstream>
|
||
|
|
|
||
|
|
class DrakeKmeans : public TriangleInequalityBaseKmeans {
|
||
|
|
public:
|
||
|
|
DrakeKmeans(int aNumBounds);
|
||
|
|
virtual ~DrakeKmeans() { free(); }
|
||
|
|
virtual void free();
|
||
|
|
virtual void initialize(Dataset const *aX, unsigned short aK,
|
||
|
|
unsigned short *initialAssignment, int aNumThreads);
|
||
|
|
virtual std::string getName() const { return "drake"; }
|
||
|
|
|
||
|
|
protected:
|
||
|
|
virtual int runThread(int threadId, int maxIterations);
|
||
|
|
|
||
|
|
// For each point, the indexes of the closest centers other than the
|
||
|
|
// assigned center. Size is n * numLowerBounds.
|
||
|
|
unsigned short **closestOtherCenters;
|
||
|
|
|
||
|
|
// Find the centers that are nearest point i. The parameter "order" is
|
||
|
|
// an array of pairs that will contain the closest
|
||
|
|
// numLowerBoundsRemaining centers and their distances. This method is
|
||
|
|
// called when all bounds failed to prune distance calculations, and the
|
||
|
|
// algorithm must look at all centers.
|
||
|
|
void find_near_centers(int i, int numLowerBoundsRemaining,
|
||
|
|
std::pair<double, int> *order, int threadId);
|
||
|
|
|
||
|
|
// If the nearest centers need reordering, this method handles that.
|
||
|
|
// This method is called when one of the bounds succeeded in pruning a
|
||
|
|
// distance calculation, but we need to discover the true order of the
|
||
|
|
// nearest centers.
|
||
|
|
void reorder_near_centers(int i, int nearIndex,
|
||
|
|
std::pair<double, int> *order, int threadId);
|
||
|
|
|
||
|
|
// Update the upper and lower bounds for the given points. Assumes that
|
||
|
|
// centerMovement has been computed.
|
||
|
|
void update_bounds(int startNdx, int endNdx,
|
||
|
|
int numLowerBoundsRemaining);
|
||
|
|
};
|
||
|
|
|
||
|
|
#endif
|