SHOGUN  6.0.0
KDTreeKNNsolver.cpp
Go to the documentation of this file.
1 /* This software is distributed under BSD 3-clause license (see LICENSE file).
2  *
3  * Copyright (c) 2012-2013 Sergey Lisitsyn
4  */
5 
8 #include <shogun/lib/Signal.h>
9 
10 using namespace shogun;
11 
12 CKDTREEKNNSolver::CKDTREEKNNSolver(const int32_t k, const float64_t q, const int32_t num_classes, const int32_t min_label, const SGVector<int32_t> train_labels, const int32_t leaf_size):
13 CKNNSolver(k, q, num_classes, min_label, train_labels)
14 {
15  init();
16 
17  m_leaf_size=leaf_size;
18 }
19 
20 CMulticlassLabels* CKDTREEKNNSolver::classify_objects(CDistance* knn_distance, const int32_t num_lab, SGVector<int32_t>& train_lab, SGVector<float64_t>& classes) const
21 {
22  CMulticlassLabels* output=new CMulticlassLabels(num_lab);
23  CFeatures* lhs = knn_distance->get_lhs();
24  CKDTree* kd_tree = new CKDTree(m_leaf_size);
25  kd_tree->build_tree(dynamic_cast<CDenseFeatures<float64_t>*>(lhs));
26  SG_UNREF(lhs);
27 
28  CFeatures* query = knn_distance->get_rhs();
29  kd_tree->query_knn(dynamic_cast<CDenseFeatures<float64_t>*>(query), m_k);
30  SGMatrix<index_t> NN = kd_tree->get_knn_indices();
31  for (int32_t i=0; i<num_lab && (!CSignal::cancel_computations()); i++)
32  {
33  //write the labels of the k nearest neighbors from theirs indices
34  for (int32_t j=0; j<m_k; j++)
35  train_lab[j] = m_train_labels[ NN(j,i) ];
36 
37  //get the index of the 'nearest' class
38  int32_t out_idx = choose_class(classes.vector, train_lab.vector);
39  //write the label of 'nearest' in the output
40  output->set_label(i, out_idx + m_min_label);
41  }
42  SG_UNREF(query);
43  SG_UNREF(kd_tree);
44  return output;
45 }
46 
47 SGVector<int32_t> CKDTREEKNNSolver::classify_objects_k(CDistance* knn_distance, const int32_t num_lab, SGVector<int32_t>& train_lab, SGVector<int32_t>& classes) const
48 {
49  SGVector<int32_t> output(m_k*num_lab);
50 
51  //allocation for distances to nearest neighbors
52  SGVector<float64_t> dists(m_k);
53 
54  CFeatures* lhs = knn_distance->get_lhs();
55  CKDTree* kd_tree = new CKDTree(m_leaf_size);
56  kd_tree->build_tree(dynamic_cast<CDenseFeatures<float64_t>*>(lhs));
57  SG_UNREF(lhs);
58 
59  CFeatures* data = knn_distance->get_rhs();
60  kd_tree->query_knn(dynamic_cast<CDenseFeatures<float64_t>*>(data), m_k);
61  SGMatrix<index_t> NN = kd_tree->get_knn_indices();
62  for (index_t i=0; i<num_lab && (!CSignal::cancel_computations()); i++)
63  {
64  //write the labels of the k nearest neighbors from theirs indices
65  for (index_t j=0; j<m_k; j++)
66  {
67  train_lab[j] = m_train_labels[ NN(j,i) ];
68  dists[j] = knn_distance->distance(NN(j,i), i);
69  }
70  CMath::qsort_index(dists.vector, train_lab.vector, m_k);
71 
72  choose_class_for_multiple_k(output.vector+i, classes.vector, train_lab.vector, num_lab);
73  }
74 
75  SG_UNREF(data);
76  SG_UNREF(kd_tree);
77 
78  return output;
79 }
int32_t m_k
the k parameter in KNN
Definition: KNNSolver.h:94
Class Distance, a base class for all the distances used in the Shogun toolbox.
Definition: Distance.h:87
SGVector< int32_t > m_train_labels
Definition: KNNSolver.h:106
int32_t index_t
Definition: common.h:72
CFeatures * get_lhs()
Definition: Distance.h:218
SGMatrix< index_t > get_knn_indices()
Definition: NbodyTree.cpp:155
static void qsort_index(T1 *output, T2 *index, uint32_t size)
Definition: Math.h:2223
int32_t choose_class(float64_t *classes, const int32_t *train_lab) const
Definition: KNNSolver.cpp:35
CFeatures * get_rhs()
Definition: Distance.h:224
virtual SGVector< int32_t > classify_objects_k(CDistance *d, const int32_t num_lab, SGVector< int32_t > &train_lab, SGVector< int32_t > &classes) const
void build_tree(CDenseFeatures< float64_t > *data)
Definition: NbodyTree.cpp:45
bool set_label(int32_t idx, float64_t label)
Multiclass Labels for multi-class classification.
void query_knn(CDenseFeatures< float64_t > *data, int32_t k)
Definition: NbodyTree.cpp:59
void choose_class_for_multiple_k(int32_t *output, int32_t *classes, const int32_t *train_lab, const int32_t step) const
Definition: KNNSolver.cpp:62
double float64_t
Definition: common.h:60
This class implements KD-Tree. cf. http://www.autonlab.org/autonweb/14665/version/2/part/5/data/moore...
Definition: KDTree.h:45
static bool cancel_computations()
Definition: Signal.h:111
int32_t m_min_label
smallest label, i.e. -1
Definition: KNNSolver.h:103
virtual CMulticlassLabels * classify_objects(CDistance *d, const int32_t num_lab, SGVector< int32_t > &train_lab, SGVector< float64_t > &classes) const
virtual float64_t distance(int32_t idx_a, int32_t idx_b)
Definition: Distance.cpp:183
#define SG_UNREF(x)
Definition: SGObject.h:53
all of classes and functions are contained in the shogun namespace
Definition: class_list.h:18
The class Features is the base class of all feature objects.
Definition: Features.h:68

SHOGUN Machine Learning Toolbox - Documentation