SHOGUN
4.2.0
Main Page
Related Pages
Modules
Classes
Files
File List
File Members
All
Classes
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Friends
Macros
Modules
Pages
src
shogun
multiclass
tree
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
31
#include <
shogun/multiclass/tree/KDTree.h
>
32
33
using namespace
shogun
;
34
35
CKDTree::CKDTree
(int32_t leaf_size,
EDistanceType
d)
36
:
CNbodyTree
(leaf_size,d)
37
{
38
}
39
40
CKDTree::~CKDTree
()
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
}
node
Definition:
JLCoverTree.h:42
shogun::CBinaryTreeMachineNode
The node of the tree structure forming a TreeMachine The node contains pointer to its parent and poin...
Definition:
BinaryTreeMachineNode.h:50
index_t
int32_t index_t
Definition:
common.h:62
shogun::CNbodyTree::add_dim_dist
float64_t add_dim_dist(float64_t d)
Definition:
NbodyTree.h:194
KDTree.h
shogun::CKDTree::CKDTree
CKDTree(int32_t leaf_size=1, EDistanceType d=D_EUCLIDEAN)
Definition:
KDTree.cpp:35
shogun::CKDTree::~CKDTree
virtual ~CKDTree()
Definition:
KDTree.cpp:40
shogun::SGMatrix::num_rows
index_t num_rows
Definition:
SGMatrix.h:374
shogun::CNbodyTree::m_data
SGMatrix< float64_t > m_data
Definition:
NbodyTree.h:314
shogun::SGVector::vlen
index_t vlen
Definition:
SGVector.h:494
shogun::EDistanceType
EDistanceType
Definition:
Distance.h:32
shogun::SGVector< float64_t >
float64_t
double float64_t
Definition:
common.h:50
shogun::CTreeMachineNode::data
T data
Definition:
TreeMachineNode.h:194
shogun::CMath::max
static T max(T a, T b)
Definition:
Math.h:168
shogun::CNbodyTree
This class implements genaralized tree for N-body problems like k-NN, kernel density estimation...
Definition:
NbodyTree.h:50
shogun::CNbodyTree::actual_dists
float64_t actual_dists(float64_t dists)
Definition:
NbodyTree.h:172
shogun
all of classes and functions are contained in the shogun namespace
Definition:
class_list.h:18
shogun::CNbodyTree::m_vec_id
SGVector< index_t > m_vec_id
Definition:
NbodyTree.h:317
shogun::CMath::min
static T min(T a, T b)
Definition:
Math.h:157
shogun::CMath::abs
static T abs(T a)
Definition:
Math.h:179
SHOGUN
Machine Learning Toolbox - Documentation