SHOGUN  6.1.3
KDTree.cpp
Go to the documentation of this file.
1 /*
2  * Copyright (c) The Shogun Machine Learning Toolbox
3  * Written (w) 2014 Parijat Mazumdar
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions are met:
8  *
9  * 1. Redistributions of source code must retain the above copyright notice, this
10  * list of conditions and the following disclaimer.
11  * 2. Redistributions in binary form must reproduce the above copyright notice,
12  * this list of conditions and the following disclaimer in the documentation
13  * and/or other materials provided with the distribution.
14  *
15  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
16  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
17  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
18  * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
19  * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
20  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
21  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
22  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  *
26  * The views and conclusions contained in the software and documentation are those
27  * of the authors and should not be interpreted as representing official policies,
28  * either expressed or implied, of the Shogun Development Team.
29  */
30 
32 
33 using namespace shogun;
34 
35 CKDTree::CKDTree(int32_t leaf_size, EDistanceType d)
36 : CNbodyTree(leaf_size,d)
37 {
38 }
39 
41 {
42 }
43 
44 float64_t CKDTree::min_dist(bnode_t* node,float64_t* feat, int32_t dim)
45 {
46  float64_t dist=0;
47  for (int32_t i=0;i<dim;i++)
48  {
49  float64_t dim_dist=(node->data.bbox_lower[i]-feat[i])+CMath::abs(feat[i]-node->data.bbox_lower[i]);
50  dim_dist+=(feat[i]-node->data.bbox_upper[i])+CMath::abs(feat[i]-node->data.bbox_upper[i]);
51  dist+=add_dim_dist(0.5*dim_dist);
52  }
53 
54  return actual_dists(dist);
55 }
56 
57 float64_t CKDTree::min_dist_dual(bnode_t* nodeq, bnode_t* noder)
58 {
59  SGVector<float64_t> nodeq_lower=nodeq->data.bbox_lower;
60  SGVector<float64_t> nodeq_upper=nodeq->data.bbox_upper;
61  SGVector<float64_t> noder_lower=noder->data.bbox_lower;
62  SGVector<float64_t> noder_upper=noder->data.bbox_upper;
63  float64_t dist=0;
64  for(int32_t i=0;i<noder_lower.vlen;i++)
65  {
66  float64_t d1=nodeq_lower[i]-noder_upper[i];
67  float64_t d2=noder_lower[i]-nodeq_upper[i];
68  dist+=add_dim_dist(0.5*(d1+CMath::abs(d1)+d2+CMath::abs(d2)));
69  }
70 
71  return actual_dists(dist);
72 }
73 
74 float64_t CKDTree::max_dist_dual(bnode_t* nodeq, bnode_t* noder)
75 {
76  SGVector<float64_t> nodeq_lower=nodeq->data.bbox_lower;
77  SGVector<float64_t> nodeq_upper=nodeq->data.bbox_upper;
78  SGVector<float64_t> noder_lower=noder->data.bbox_lower;
79  SGVector<float64_t> noder_upper=noder->data.bbox_upper;
80  float64_t dist=0;
81  for(int32_t i=0;i<noder_lower.vlen;i++)
82  {
83  float64_t d1=CMath::abs(nodeq_lower[i]-noder_upper[i]);
84  float64_t d2=CMath::abs(noder_lower[i]-nodeq_upper[i]);
85  dist+=add_dim_dist(CMath::max(d1,d2));
86  }
87 
88  return actual_dists(dist);
89 }
90 
91 void CKDTree::min_max_dist(float64_t* pt, bnode_t* node, float64_t &lower,float64_t &upper, int32_t dim)
92 {
93  lower=0;
94  upper=0;
95  for(int32_t i=0;i<dim;i++)
96  {
97  float64_t low_dist=node->data.bbox_lower[i]-pt[i];
98  float64_t high_dist=pt[i]-node->data.bbox_upper[i];
99  lower+=add_dim_dist(0.5*(low_dist+CMath::abs(low_dist)+high_dist+CMath::abs(high_dist)));
100  upper+=add_dim_dist(CMath::max(CMath::abs(low_dist),CMath::abs(high_dist)));
101  }
102 
103  lower=actual_dists(lower);
104  upper=actual_dists(upper);
105 }
106 
107 void CKDTree::init_node(bnode_t* node, index_t start, index_t end)
108 {
109  SGVector<float64_t> upper_bounds(m_data.num_rows);
110  SGVector<float64_t> lower_bounds(m_data.num_rows);
111 
112  for (int32_t i=0;i<m_data.num_rows;i++)
113  {
114  upper_bounds[i]=m_data(i,m_vec_id[start]);
115  lower_bounds[i]=m_data(i,m_vec_id[start]);
116  for (int32_t j=start+1;j<=end;j++)
117  {
118  upper_bounds[i]=CMath::max(upper_bounds[i],m_data(i,m_vec_id[j]));
119  lower_bounds[i]=CMath::min(lower_bounds[i],m_data(i,m_vec_id[j]));
120  }
121  }
122 
123  float64_t radius=0;
124  for (int32_t i=0;i<m_data.num_rows;i++)
125  radius=CMath::max(radius,upper_bounds[i]-lower_bounds[i]);
126 
127  node->data.bbox_upper=upper_bounds;
128  node->data.bbox_lower=lower_bounds;
129  node->data.radius=0.5*radius;
130  node->data.start_idx=start;
131  node->data.end_idx=end;
132 }
The node of the tree structure forming a TreeMachine The node contains pointer to its parent and poin...
static T max(T a, T b)
Definition: Math.h:149
int32_t index_t
Definition: common.h:72
float64_t add_dim_dist(float64_t d)
Definition: NbodyTree.h:194
CKDTree(int32_t leaf_size=1, EDistanceType d=D_EUCLIDEAN)
Definition: KDTree.cpp:35
virtual ~CKDTree()
Definition: KDTree.cpp:40
SGMatrix< float64_t > m_data
Definition: NbodyTree.h:314
EDistanceType
Definition: Distance.h:32
double float64_t
Definition: common.h:60
index_t num_rows
Definition: SGMatrix.h:495
This class implements genaralized tree for N-body problems like k-NN, kernel density estimation...
Definition: NbodyTree.h:50
float64_t actual_dists(float64_t dists)
Definition: NbodyTree.h:172
all of classes and functions are contained in the shogun namespace
Definition: class_list.h:18
SGVector< index_t > m_vec_id
Definition: NbodyTree.h:317
static T min(T a, T b)
Definition: Math.h:138
index_t vlen
Definition: SGVector.h:571
static T abs(T a)
Definition: Math.h:161

SHOGUN Machine Learning Toolbox - Documentation