|
1
|
|
|
"""!
|
|
2
|
|
|
|
|
3
|
|
|
@brief Module provides various metrics - abstraction of the notion of distance in a metric space.
|
|
4
|
|
|
|
|
5
|
|
|
@authors Andrei Novikov ([email protected])
|
|
6
|
|
|
@date 2014-2018
|
|
7
|
|
|
@copyright GNU Public License
|
|
8
|
|
|
|
|
9
|
|
|
@cond GNU_PUBLIC_LICENSE
|
|
10
|
|
|
PyClustering is free software: you can redistribute it and/or modify
|
|
11
|
|
|
it under the terms of the GNU General Public License as published by
|
|
12
|
|
|
the Free Software Foundation, either version 3 of the License, or
|
|
13
|
|
|
(at your option) any later version.
|
|
14
|
|
|
|
|
15
|
|
|
PyClustering is distributed in the hope that it will be useful,
|
|
16
|
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
17
|
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
18
|
|
|
GNU General Public License for more details.
|
|
19
|
|
|
|
|
20
|
|
|
You should have received a copy of the GNU General Public License
|
|
21
|
|
|
along with this program. If not, see <http://www.gnu.org/licenses/>.
|
|
22
|
|
|
@endcond
|
|
23
|
|
|
|
|
24
|
|
|
"""
|
|
25
|
|
|
|
|
26
|
|
|
|
|
27
|
|
|
from enum import IntEnum;
|
|
28
|
|
|
|
|
29
|
|
|
|
|
30
|
|
|
class type_metric(IntEnum):
|
|
31
|
|
|
"""!
|
|
32
|
|
|
@brief Enumeration of supported metrics in the module for distance calculation between two points.
|
|
33
|
|
|
|
|
34
|
|
|
"""
|
|
35
|
|
|
|
|
36
|
|
|
## Euclidean distance, for more information see function 'euclidean_distance'.
|
|
37
|
|
|
EUCLIDEAN = 0;
|
|
38
|
|
|
|
|
39
|
|
|
## Square Euclidean distance, for more information see function 'euclidean_distance_square'.
|
|
40
|
|
|
EUCLIDEAN_SQUARE = 1;
|
|
41
|
|
|
|
|
42
|
|
|
## Manhattan distance, for more information see function 'manhattan_distance'.
|
|
43
|
|
|
MANHATTAN = 2;
|
|
44
|
|
|
|
|
45
|
|
|
## Chebyshev distance, for more information see function 'chebyshev_distance'.
|
|
46
|
|
|
CHEBYSHEV = 3;
|
|
47
|
|
|
|
|
48
|
|
|
## Minkowski distance, for more information see function 'minkowski_distance'.
|
|
49
|
|
|
MINKOWSKI = 4;
|
|
50
|
|
|
|
|
51
|
|
|
## User defined function for distance calculation between two points.
|
|
52
|
|
|
USER_DEFINED = 1000;
|
|
53
|
|
|
|
|
54
|
|
|
|
|
55
|
|
|
class distance_metric:
|
|
56
|
|
|
"""!
|
|
57
|
|
|
@brief
|
|
58
|
|
|
|
|
59
|
|
|
"""
|
|
60
|
|
|
def __init__(self, type, **kwargs):
|
|
61
|
|
|
"""!
|
|
62
|
|
|
@brief Creates distance metric instance for calculation distance between two points.
|
|
63
|
|
|
|
|
64
|
|
|
@param[in] type (type_metric):
|
|
65
|
|
|
@param[in] **kwargs: Arbitrary keyword arguments (available arguments: 'func' and corresponding additional argument for
|
|
66
|
|
|
for specific metric types).
|
|
67
|
|
|
|
|
68
|
|
|
Keyword Args:
|
|
69
|
|
|
func (callable): Callable object with two arguments (point #1 and point #2) that is used only if metric is 'type_metric.USER_DEFINED'.
|
|
70
|
|
|
degree (numeric): Only for 'type_metric.MINKOWSKI' - degree of Minkowski equation.
|
|
71
|
|
|
|
|
72
|
|
|
"""
|
|
73
|
|
|
self.__type = type;
|
|
74
|
|
|
self.__args = kwargs;
|
|
75
|
|
|
self.__func = self.__get('func', None, self.__args);
|
|
76
|
|
|
|
|
77
|
|
|
|
|
78
|
|
|
def __call__(self, point1, point2):
|
|
79
|
|
|
"""!
|
|
80
|
|
|
@brief Calculates distance between two points.
|
|
81
|
|
|
|
|
82
|
|
|
@param[in] point1 (list): The first point.
|
|
83
|
|
|
@param[in] point2 (list): The second point.
|
|
84
|
|
|
|
|
85
|
|
|
@return (double) Distance between two points.
|
|
86
|
|
|
|
|
87
|
|
|
"""
|
|
88
|
|
|
if self.__type == type_metric.EUCLIDEAN:
|
|
89
|
|
|
return euclidean_distance(point1, point2);
|
|
90
|
|
|
|
|
91
|
|
|
elif self.__type == type_metric.EUCLIDEAN_SQUARE:
|
|
92
|
|
|
return euclidean_distance_square(point1, point2);
|
|
93
|
|
|
|
|
94
|
|
|
elif self.__type == type_metric.MANHATTAN:
|
|
95
|
|
|
return manhattan_distance(point1, point2);
|
|
96
|
|
|
|
|
97
|
|
|
elif self.__type == type_metric.CHEBYSHEV:
|
|
98
|
|
|
return chebyshev_distance(point1, point2);
|
|
99
|
|
|
|
|
100
|
|
|
elif self.__type == type_metric.MINKOWSKI:
|
|
101
|
|
|
return minkowski_distance(point1, point2, self.__get('degree', 2, self.__args));
|
|
102
|
|
|
|
|
103
|
|
|
elif self.__type == type_metric.USER_DEFINED:
|
|
104
|
|
|
return self.__func(point1, point2);
|
|
105
|
|
|
|
|
106
|
|
|
else:
|
|
107
|
|
|
raise ValueError("Unknown type of metric: '%d'", self.__type);
|
|
108
|
|
|
|
|
109
|
|
|
|
|
110
|
|
|
def __get(self, key, default_value, container):
|
|
111
|
|
|
"""!
|
|
112
|
|
|
@brief Returns value from container by key if key is contained by 'container' otherwise default value.
|
|
113
|
|
|
|
|
114
|
|
|
@param[in] key (string): Argument name (key in 'container') whose value is required.
|
|
115
|
|
|
@param[in] default_value (any): Value that is returned if argument is not found in 'container'.
|
|
116
|
|
|
@param[in] container (dict): Dictionary with arguments (key, value).
|
|
117
|
|
|
|
|
118
|
|
|
@return (any) Value from container by key if key is contained by 'container' otherwise default value.
|
|
119
|
|
|
|
|
120
|
|
|
"""
|
|
121
|
|
|
if key in container:
|
|
122
|
|
|
return container[key];
|
|
123
|
|
|
|
|
124
|
|
|
return default_value;
|
|
125
|
|
|
|
|
126
|
|
|
|
|
127
|
|
|
def euclidean_distance(point1, point2):
|
|
128
|
|
|
"""!
|
|
|
|
|
|
|
129
|
|
|
@brief Calculate Euclidean distance between two vectors.
|
|
130
|
|
|
@details The Euclidean between vectors (points) a and b is calculated by following formula:
|
|
131
|
|
|
|
|
132
|
|
|
\f[
|
|
133
|
|
|
dist(a, b) = \sqrt{ \sum_{i=0}^{N}(a_{i} - b_{i})^{2} };
|
|
134
|
|
|
\f]
|
|
135
|
|
|
|
|
136
|
|
|
Where N is a length of each vector.
|
|
137
|
|
|
|
|
138
|
|
|
@param[in] point1 (list): The first vector.
|
|
139
|
|
|
@param[in] point2 (list): The second vector.
|
|
140
|
|
|
|
|
141
|
|
|
@return (double) Euclidean distance between two vectors.
|
|
142
|
|
|
|
|
143
|
|
|
@see euclidean_distance_square, manhattan_distance, chebyshev_distance
|
|
144
|
|
|
|
|
145
|
|
|
"""
|
|
146
|
|
|
distance = euclidean_distance_square(point1, point2);
|
|
147
|
|
|
return distance ** 0.5;
|
|
148
|
|
|
|
|
149
|
|
|
|
|
150
|
|
|
def euclidean_distance_square(point1, point2):
|
|
151
|
|
|
"""!
|
|
|
|
|
|
|
152
|
|
|
@brief Calculate square Euclidean distance between two vectors.
|
|
153
|
|
|
|
|
154
|
|
|
\f[
|
|
155
|
|
|
dist(a, b) = \sum_{i=0}^{N}(a_{i} - b_{i})^{2};
|
|
156
|
|
|
\f]
|
|
157
|
|
|
|
|
158
|
|
|
@param[in] point1 (list): The first vector.
|
|
159
|
|
|
@param[in] point2 (list): The second vector.
|
|
160
|
|
|
|
|
161
|
|
|
@return (double) Square Euclidean distance between two vectors.
|
|
162
|
|
|
|
|
163
|
|
|
@see euclidean_distance, manhattan_distance, chebyshev_distance
|
|
164
|
|
|
|
|
165
|
|
|
"""
|
|
166
|
|
|
distance = 0.0;
|
|
167
|
|
|
for i in range(len(point1)):
|
|
168
|
|
|
distance += (point1[i] - point2[i]) ** 2.0;
|
|
169
|
|
|
|
|
170
|
|
|
return distance;
|
|
171
|
|
|
|
|
172
|
|
|
|
|
173
|
|
|
def manhattan_distance(point1, point2):
|
|
174
|
|
|
"""!
|
|
|
|
|
|
|
175
|
|
|
@brief Calculate Manhattan distance between between two vectors.
|
|
176
|
|
|
|
|
177
|
|
|
\f[
|
|
178
|
|
|
dist(a, b) = \sum_{i=0}^{N}\left | a_{i} - b_{i} \right |;
|
|
179
|
|
|
\f]
|
|
180
|
|
|
|
|
181
|
|
|
@param[in] point1 (list): The first vector.
|
|
182
|
|
|
@param[in] point2 (list): The second vector.
|
|
183
|
|
|
|
|
184
|
|
|
@return (double) Manhattan distance between two vectors.
|
|
185
|
|
|
|
|
186
|
|
|
@see euclidean_distance_square, euclidean_distance, chebyshev_distance
|
|
187
|
|
|
|
|
188
|
|
|
"""
|
|
189
|
|
|
distance = 0.0;
|
|
190
|
|
|
dimension = len(point1);
|
|
191
|
|
|
|
|
192
|
|
|
for i in range(dimension):
|
|
193
|
|
|
distance += abs(point1[i] - point2[i]);
|
|
194
|
|
|
|
|
195
|
|
|
return distance;
|
|
196
|
|
|
|
|
197
|
|
|
|
|
198
|
|
|
def chebyshev_distance(point1, point2):
|
|
199
|
|
|
"""!
|
|
|
|
|
|
|
200
|
|
|
@brief Calculate Chebyshev distance between between two vectors.
|
|
201
|
|
|
|
|
202
|
|
|
\f[
|
|
203
|
|
|
dist(a, b) = \max_{}i\left (\left | a_{i} - b_{i} \right |\right );
|
|
204
|
|
|
\f]
|
|
205
|
|
|
|
|
206
|
|
|
@param[in] point1 (list): The first vector.
|
|
207
|
|
|
@param[in] point2 (list): The second vector.
|
|
208
|
|
|
|
|
209
|
|
|
@return (double) Chebyshev distance between two vectors.
|
|
210
|
|
|
|
|
211
|
|
|
@see euclidean_distance_square, euclidean_distance, minkowski_distance
|
|
212
|
|
|
|
|
213
|
|
|
"""
|
|
214
|
|
|
distance = 0.0;
|
|
215
|
|
|
dimension = len(point1);
|
|
216
|
|
|
|
|
217
|
|
|
for i in range(dimension):
|
|
218
|
|
|
distance = max(distance, abs(point1[i] - point2[i]));
|
|
219
|
|
|
|
|
220
|
|
|
return distance;
|
|
221
|
|
|
|
|
222
|
|
|
|
|
223
|
|
|
def minkowski_distance(point1, point2, degree=2):
|
|
224
|
|
|
"""!
|
|
|
|
|
|
|
225
|
|
|
@brief Calculate Minkowski distance between two vectors.
|
|
226
|
|
|
|
|
227
|
|
|
\f[
|
|
228
|
|
|
dist(a, b) = \sqrt[p]{ \sum_{i=0}^{N}\left(a_{i} - b_{i}\right)^{p} };
|
|
229
|
|
|
\f]
|
|
230
|
|
|
|
|
231
|
|
|
@param[in] point1 (list): The first vector.
|
|
232
|
|
|
@param[in] point2 (list): The second vector.
|
|
233
|
|
|
@param[in] degree (numeric): Degree of that is used for Minkowski distance.
|
|
234
|
|
|
|
|
235
|
|
|
@return (double) Minkowski distance between two vectors.
|
|
236
|
|
|
|
|
237
|
|
|
@see euclidean_distance
|
|
238
|
|
|
|
|
239
|
|
|
"""
|
|
240
|
|
|
distance = 0.0;
|
|
241
|
|
|
for i in range(len(point1)):
|
|
242
|
|
|
distance += (point1[i] - point2[i]) ** degree;
|
|
243
|
|
|
|
|
244
|
|
|
return distance ** (1.0 / degree); |
annoviko /
pyclustering
Loading history...
Escape sequences in Python are generally interpreted according to rules similar to standard C. Only if strings are prefixed with
rorRare they interpreted as regular expressions.The escape sequence that was used indicates that you might have intended to write a regular expression.
Learn more about the available escape sequences. in the Python documentation.