Skip to content

Commit

Permalink
* convention and naming fixes
Browse files Browse the repository at this point in the history
  • Loading branch information
@iglesias
iglesias committed Apr 6, 2012
1 parent 5a74fa5 commit fbc2f8f
Show file tree
Hide file tree
Showing 2 changed files with 55 additions and 56 deletions.
94 changes: 46 additions & 48 deletions src/shogun/classifier/KNN.cpp
View file
Expand Up @@ -7,6 +7,7 @@
* Written (W) 2006 Christian Gehl
* Written (W) 2006-2009 Soeren Sonnenburg
* Written (W) 2011 Sergey Lisitsyn
* Written (W) 2012 Fernando José Iglesias García, cover tree support
* Copyright (C) 2011 Berlin Institute of Technology and Max-Planck-Society
*/

Expand Down Expand Up @@ -47,27 +48,27 @@ void CKNN::init()

m_k=3;
m_q=1.0;
m_use_coverTree=false;
m_use_covertree=false;
num_classes=0;
m_coverTree=NULL;
m_built_coverTree=false;
m_covertree=NULL;
m_built_covertree=false;

/** TODO not really sure here if these two first guys should be MS_AVAILABLE or
* MS_NOT_AVAILABLE
*/
SG_ADD(&m_k, "m_k", "Parameter k", MS_AVAILABLE);
SG_ADD(&m_q, "m_q", "Parameter q", MS_AVAILABLE);
SG_ADD(&m_use_coverTree, "m_use_covertree", "Parameter use_covertree", MS_NOT_AVAILABLE);
SG_ADD(&m_built_coverTree, "m_built_covertree", "Parameter built_covertree", MS_NOT_AVAILABLE);
SG_ADD(&m_use_covertree, "m_use_covertree", "Parameter use_covertree", MS_NOT_AVAILABLE);
SG_ADD(&m_built_covertree, "m_built_covertree", "Parameter built_covertree", MS_NOT_AVAILABLE);
SG_ADD(&num_classes, "num_classes", "Number of classes", MS_NOT_AVAILABLE);
SG_ADD((CSGObject**) &m_coverTree, "m_coverTree", "Member cover tree", MS_NOT_AVAILABLE);
SG_ADD((CSGObject**) &m_covertree, "m_covertree", "Member cover tree", MS_NOT_AVAILABLE);
}

CKNN::~CKNN()
{
SG_FREE(train_labels.vector);
if ( m_use_coverTree )
delete m_coverTree;
if ( m_use_covertree )
delete m_covertree;
}

bool CKNN::train_machine(CFeatures* data)
Expand All @@ -91,14 +92,13 @@ bool CKNN::train_machine(CFeatures* data)
int32_t max_class=train_labels.vector[0];
int32_t min_class=train_labels.vector[0];

int32_t i;
for (i=1; i<train_labels.vlen; i++)
for (int32_t i=1; i<train_labels.vlen; i++)
{
max_class=CMath::max(max_class, train_labels.vector[i]);
min_class=CMath::min(min_class, train_labels.vector[i]);
}

for (i=0; i<train_labels.vlen; i++)
for (int32_t i=0; i<train_labels.vlen; i++)
train_labels.vector[i]-=min_class;

min_label=min_class;
Expand All @@ -109,33 +109,35 @@ bool CKNN::train_machine(CFeatures* data)

// If cover tree is to be used, populate it with training vectors
// assuming that distance(train_vectors, train_vectors)
if ( m_use_coverTree )
if ( m_use_covertree )
{
// Ensure that distance has the same features lhs and rhs
if ( ! distance->lhs_equals_rhs() )
{
SG_ERROR("Features lhs and rhs must be equal to train KNN "
"with CoverTree support\n");

int32_t j;
"with covertree support\n");
}

// Look for the max distance among training vectors
float64_t max_dist = 0.0;
for (i=0; i<train_labels.vlen; i++)
for (j=i+1; j<train_labels.vlen; j++)
for (int32_t i=0; i<train_labels.vlen; i++)
{
for (int32_t j=i+1; j<train_labels.vlen; j++)
max_dist = CMath::max(max_dist, distance->distance(i, j));
}

// Create cover tree
m_coverTree = new CoverTree<KNN_COVERTREE_POINT>(max_dist);
m_covertree = new CoverTree<KNN_COVERTREE_POINT>(max_dist);

// Insert training vectors
for (i=0; i<train_labels.vlen; i++)
m_coverTree->insert(KNN_COVERTREE_POINT(i, distance));
for (int32_t i=0; i<train_labels.vlen; i++)
m_covertree->insert(KNN_COVERTREE_POINT(i, distance));

m_built_coverTree = true;
m_built_covertree = true;
}
else
{
m_built_coverTree = false;
m_built_covertree = false;
}

return true;
Expand All @@ -147,8 +149,8 @@ CLabels* CKNN::apply()
ASSERT(distance);
ASSERT(distance->get_num_vec_rhs());

if ( m_use_coverTree && ! m_built_coverTree )
SG_ERROR("The CoverTree must have been built during training to use "
if ( m_use_covertree && ! m_built_covertree )
SG_ERROR("The cover tree must have been built during training to use "
"it for classification\n");

int32_t num_lab=distance->get_num_vec_rhs();
Expand All @@ -161,7 +163,7 @@ CLabels* CKNN::apply()
//vector of neighbors used for the cover tree support
int32_t* nearest_neighbors;
//distances to train data and working buffer of train_labels
if ( ! m_use_coverTree )
if ( ! m_use_covertree )
{
dists=SG_MALLOC(float64_t, train_labels.vlen);
train_lab=SG_MALLOC(int32_t, train_labels.vlen);
Expand All @@ -182,14 +184,12 @@ CLabels* CKNN::apply()
{
SG_PROGRESS(i, 0, num_lab);

int32_t j;

if ( ! m_use_coverTree )
if ( ! m_use_covertree )
{
//lhs idx 1..n and rhs idx i
distances_lhs(dists,0,train_labels.vlen-1,i);

for (j=0; j<train_labels.vlen; j++)
for (int32_t j=0; j<train_labels.vlen; j++)
train_lab[j]=train_labels.vector[j];

//sort the distance vector for test example j to all train examples
Expand All @@ -198,20 +198,20 @@ CLabels* CKNN::apply()
}
else
{
//get the k nearest neighbors to test vector i using the CoverTree
//get the k nearest neighbors to test vector i using the cover tree
get_neighbors(nearest_neighbors, i);

//translate from indices to labels of the nearest neighbors
for (j=0; j<m_k; j++)
for (int32_t j=0; j<m_k; j++)
train_lab[j]=train_labels.vector[ nearest_neighbors[j] ];
}

//compute histogram of class outputs of the first k nearest neighbours
for (j=0; j<num_classes; j++)
for (int32_t j=0; j<num_classes; j++)
classes[j]=0.0;

float64_t multiplier = m_q;
for (j=0; j<m_k; j++)
for (int32_t j=0; j<m_k; j++)
{
classes[train_lab[j]]+= multiplier;
multiplier*= multiplier;
Expand All @@ -221,7 +221,7 @@ CLabels* CKNN::apply()
int32_t out_idx=0;
float64_t out_max=0;

for (j=0; j<num_classes; j++)
for (int32_t j=0; j<num_classes; j++)
{
if (out_max< classes[j])
{
Expand All @@ -234,7 +234,7 @@ CLabels* CKNN::apply()

SG_FREE(classes);
SG_FREE(train_lab);
if ( ! m_use_coverTree )
if ( ! m_use_covertree )
SG_FREE(dists);
else
SG_FREE(nearest_neighbors);
Expand Down Expand Up @@ -304,8 +304,8 @@ SGMatrix<int32_t> CKNN::classify_for_multiple_k()
ASSERT(distance);
ASSERT(distance->get_num_vec_rhs());

if ( m_use_coverTree && ! m_built_coverTree )
SG_ERROR("The CoverTree must have been built during training to use "
if ( m_use_covertree && ! m_built_covertree )
SG_ERROR("The cover tree must have been built during training to use "
"it for classification\n");

int32_t num_lab=distance->get_num_vec_rhs();
Expand All @@ -318,7 +318,7 @@ SGMatrix<int32_t> CKNN::classify_for_multiple_k()
//vector of neighbors used for the cover tree support
int32_t* nearest_neighbors;
//distances to train data and working buffer of train_labels
if ( ! m_use_coverTree )
if ( ! m_use_covertree )
{
dists=SG_MALLOC(float64_t, train_labels.vlen);
train_lab=SG_MALLOC(int32_t, train_labels.vlen);
Expand All @@ -339,13 +339,11 @@ SGMatrix<int32_t> CKNN::classify_for_multiple_k()
{
SG_PROGRESS(i, 0, num_lab);

int32_t j;

if ( ! m_use_coverTree )
if ( ! m_use_covertree )
{
// lhs idx 1..n and rhs idx i
distances_lhs(dists,0,train_labels.vlen-1,i);
for (j=0; j<train_labels.vlen; j++)
for (int32_t j=0; j<train_labels.vlen; j++)
train_lab[j]=train_labels.vector[j];

//sort the distance vector for test example j to all train examples
Expand All @@ -354,19 +352,19 @@ SGMatrix<int32_t> CKNN::classify_for_multiple_k()
}
else
{
//get the k nearest neighbors to test vector i using the CoverTree
//get the k nearest neighbors to test vector i using the cover tree
get_neighbors(nearest_neighbors, i);

//translate from indices to labels of the nearest neighbors
for (j=0; j<m_k; j++)
for (int32_t j=0; j<m_k; j++)
train_lab[j]=train_labels.vector[ nearest_neighbors[j] ];
}

//compute histogram of class outputs of the first k nearest neighbours
for (j=0; j<num_classes; j++)
for (int32_t j=0; j<num_classes; j++)
classes[j]=0;

for (j=0; j<m_k; j++)
for (int32_t j=0; j<m_k; j++)
{
classes[train_lab[j]]++;

Expand All @@ -388,7 +386,7 @@ SGMatrix<int32_t> CKNN::classify_for_multiple_k()

SG_FREE(train_lab);
SG_FREE(classes);
if ( ! m_use_coverTree )
if ( ! m_use_covertree )
SG_FREE(dists);
else
SG_FREE(nearest_neighbors);
Expand Down Expand Up @@ -427,7 +425,7 @@ bool CKNN::save(FILE* dstfile)
void CKNN::get_neighbors(int32_t* out, int32_t idx)
{
std::vector<KNN_COVERTREE_POINT> neighbors =
m_coverTree->kNearestNeighbors(KNN_COVERTREE_POINT(idx, distance), m_k);
m_covertree->kNearestNeighbors(KNN_COVERTREE_POINT(idx, distance), m_k);

for (std::size_t m=0; m<unsigned(m_k); m++)
out[m] = neighbors[m].m_point_index;
Expand Down
17 changes: 9 additions & 8 deletions src/shogun/classifier/KNN.h
View file
Expand Up @@ -7,6 +7,7 @@
* Written (W) 2006 Christian Gehl
* Written (W) 1999-2009 Soeren Sonnenburg
* Written (W) 2011 Sergey Lisitsyn
* Written (W) 2012 Fernando José Iglesias García, cover tree support
* Copyright (C) 2011 Berlin Institute of Technology and Max-Planck-Society
*/

Expand Down Expand Up @@ -149,17 +150,17 @@ class CKNN : public CDistanceMachine
inline float64_t get_q() { return m_q; }

/* set whether to use cover trees for fast KNN
* @param use_coverTree
* @param use_covertree
*/
inline void set_use_coverTree(bool use_coverTree)
inline void set_use_covertree(bool use_covertree)
{
m_use_coverTree = use_coverTree;
m_use_covertree = use_covertree;
}

/** get whether to use cover trees for fast KNN
* @return use_covertree parameter
*/
inline bool get_use_coverTree() const { return m_use_coverTree; }
inline bool get_use_covertree() const { return m_use_covertree; }

/** @return object name */
inline virtual const char* get_name() const { return "KNN"; }
Expand Down Expand Up @@ -193,7 +194,7 @@ class CKNN : public CDistanceMachine

/** get the m_k nearest neighbors to the test vector indexed by "idx"
* these neighbors are found within the set of training vectors. This
* function makes use of CoverTree support
* function makes use of cover tree support
*
* @param idx index of the test vector for which to find NN
* @return out vector with indices to the NN
Expand All @@ -211,13 +212,13 @@ class CKNN : public CDistanceMachine
float64_t m_q;

/// parameter to enable cover tree support
bool m_use_coverTree;
bool m_use_covertree;

/// parameter to tell if the cover tree has been built during training
bool m_built_coverTree;
bool m_built_covertree;

/// class member cover tree
CoverTree<KNN_COVERTREE_POINT>* m_coverTree;
CoverTree<KNN_COVERTREE_POINT>* m_covertree;

/// number of classes (i.e. number of values labels can take)
int32_t num_classes;
Expand Down

0 comments on commit fbc2f8f

Please sign in to comment.