|
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
|
|
|
import collections;
|
|
30
|
|
|
|
|
31
|
|
|
|
|
32
|
|
|
class type_metric(IntEnum):
|
|
33
|
|
|
"""!
|
|
34
|
|
|
@brief Enumeration of supported metrics in the module for distance calculation between two points.
|
|
35
|
|
|
|
|
36
|
|
|
"""
|
|
37
|
|
|
|
|
38
|
|
|
## Euclidean distance, for more information see function 'euclidean_distance'.
|
|
39
|
|
|
EUCLIDEAN = 0;
|
|
40
|
|
|
|
|
41
|
|
|
## Square Euclidean distance, for more information see function 'euclidean_distance_square'.
|
|
42
|
|
|
EUCLIDEAN_SQUARE = 1;
|
|
43
|
|
|
|
|
44
|
|
|
## Manhattan distance, for more information see function 'manhattan_distance'.
|
|
45
|
|
|
MANHATTAN = 2;
|
|
46
|
|
|
|
|
47
|
|
|
## Chebyshev distance, for more information see function 'chebyshev_distance'.
|
|
48
|
|
|
CHEBYSHEV = 3;
|
|
49
|
|
|
|
|
50
|
|
|
## User defined function for distance calculation between two points.
|
|
51
|
|
|
USER_DEFINED = 1000;
|
|
52
|
|
|
|
|
53
|
|
|
|
|
54
|
|
|
def calculate_metric(point1, point2, metric, func=None):
|
|
55
|
|
|
"""!
|
|
56
|
|
|
@brief Calculates metric between two points in line with specified metric function.
|
|
57
|
|
|
|
|
58
|
|
|
@param[in] point1 (numeric|list): The first point.
|
|
59
|
|
|
@param[in] point2 (numeric|list): The second point.
|
|
60
|
|
|
@param[in] metric (type_metric): Metric that is used for distance calculation between two points.
|
|
61
|
|
|
@param[in] func (callable): Used only if metric is 'type_metric.USER_DEFINED' and represents callable object
|
|
62
|
|
|
with two arguments: 'point1' and 'point2', notation is: 'func(point1, point2)'.
|
|
63
|
|
|
|
|
64
|
|
|
@return (double) Distance between two points.
|
|
65
|
|
|
|
|
66
|
|
|
"""
|
|
67
|
|
|
if metric == type_metric.EUCLIDEAN:
|
|
68
|
|
|
return euclidean_distance(point1, point2);
|
|
69
|
|
|
|
|
70
|
|
|
elif metric == type_metric.EUCLIDEAN_SQUARE:
|
|
71
|
|
|
return euclidean_distance_square(point1, point2);
|
|
72
|
|
|
|
|
73
|
|
|
elif metric == type_metric.MANHATTAN:
|
|
74
|
|
|
return manhattan_distance(point1, point2);
|
|
75
|
|
|
|
|
76
|
|
|
elif metric == type_metric.CHEBYSHEV:
|
|
77
|
|
|
return chebyshev_distance(point1, point2);
|
|
78
|
|
|
|
|
79
|
|
|
elif metric == type_metric.USER_DEFINED:
|
|
80
|
|
|
return func(point1, point2);
|
|
81
|
|
|
|
|
82
|
|
|
else:
|
|
83
|
|
|
raise ValueError("Unknown type of metric: '%d'", metric);
|
|
84
|
|
|
|
|
85
|
|
|
|
|
86
|
|
|
def euclidean_distance(point1, point2):
|
|
87
|
|
|
"""!
|
|
|
|
|
|
|
88
|
|
|
@brief Calculate Euclidean distance between vectors.
|
|
89
|
|
|
@details The Euclidean between vectors (points) a and b is calculated by following formula:
|
|
90
|
|
|
|
|
91
|
|
|
\f[
|
|
92
|
|
|
dist(a, b) = \sqrt{ \sum_{i=0}^{N}(a_{i} - b_{i})^{2}) };
|
|
93
|
|
|
\f]
|
|
94
|
|
|
|
|
95
|
|
|
Where N is a length of each vector.
|
|
96
|
|
|
|
|
97
|
|
|
@param[in] point1 (numeric|list): The first vector.
|
|
98
|
|
|
@param[in] point2 (numeric|list): The second vector.
|
|
99
|
|
|
|
|
100
|
|
|
@return (double) Euclidean distance between two vectors.
|
|
101
|
|
|
|
|
102
|
|
|
"""
|
|
103
|
|
|
|
|
104
|
|
|
distance = euclidean_distance_square(point1, point2);
|
|
105
|
|
|
return distance ** 0.5;
|
|
106
|
|
|
|
|
107
|
|
|
|
|
108
|
|
|
def euclidean_distance_square(point1, point2):
|
|
109
|
|
|
"""!
|
|
|
|
|
|
|
110
|
|
|
@brief Calculate square Euclidean distance between vectors.
|
|
111
|
|
|
|
|
112
|
|
|
\f[
|
|
113
|
|
|
dist(a, b) = \sum_{i=0}^{N}(a_{i} - b_{i})^{2});
|
|
114
|
|
|
\f]
|
|
115
|
|
|
|
|
116
|
|
|
@param[in] point1 (numeric|list): The first vector.
|
|
117
|
|
|
@param[in] point2 (numeric|list): The second vector.
|
|
118
|
|
|
|
|
119
|
|
|
@return (double) Square Euclidean distance between two vectors.
|
|
120
|
|
|
|
|
121
|
|
|
"""
|
|
122
|
|
|
|
|
123
|
|
|
if isinstance(point1, collections.Iterable):
|
|
124
|
|
|
distance = 0.0;
|
|
125
|
|
|
for i in range(len(point1)):
|
|
126
|
|
|
distance += (point1[i] - point2[i]) ** 2.0;
|
|
127
|
|
|
|
|
128
|
|
|
return distance;
|
|
129
|
|
|
|
|
130
|
|
|
return (point1 - point2) ** 2.0;
|
|
131
|
|
|
|
|
132
|
|
|
|
|
133
|
|
|
def manhattan_distance(point1, point2):
|
|
134
|
|
|
"""!
|
|
|
|
|
|
|
135
|
|
|
@brief Calculate Manhattan distance between vector a and b.
|
|
136
|
|
|
|
|
137
|
|
|
\f[
|
|
138
|
|
|
dist(a, b) = \sum_{i=0}^{N}\left | a_{i} - b_{i} \right |;
|
|
139
|
|
|
\f]
|
|
140
|
|
|
|
|
141
|
|
|
@param[in] point1 (numeric|list): The first vector.
|
|
142
|
|
|
@param[in] point2 (numeric|list): The second vector.
|
|
143
|
|
|
|
|
144
|
|
|
@return (double) Manhattan distance between two vectors.
|
|
145
|
|
|
|
|
146
|
|
|
"""
|
|
147
|
|
|
|
|
148
|
|
|
if isinstance(point1, collections.Iterable):
|
|
149
|
|
|
distance = 0.0;
|
|
150
|
|
|
dimension = len(point1);
|
|
151
|
|
|
|
|
152
|
|
|
for i in range(dimension):
|
|
153
|
|
|
distance += abs(point1[i] - point2[i]);
|
|
154
|
|
|
|
|
155
|
|
|
return distance;
|
|
156
|
|
|
|
|
157
|
|
|
return abs(point1 - point2);
|
|
158
|
|
|
|
|
159
|
|
|
|
|
160
|
|
|
def chebyshev_distance(point1, point2):
|
|
161
|
|
|
"""!
|
|
|
|
|
|
|
162
|
|
|
@brief Calculate Chebyshev distance between vector a and b.
|
|
163
|
|
|
|
|
164
|
|
|
\f[
|
|
165
|
|
|
dist(a, b) = \max_{}i\left (\left | a_{i} - b_{i} \right |\right );
|
|
166
|
|
|
\f]
|
|
167
|
|
|
|
|
168
|
|
|
@param[in] point1 (numeric|list): The first vector.
|
|
169
|
|
|
@param[in] point2 (numeric|list): The second vector.
|
|
170
|
|
|
|
|
171
|
|
|
@return (double) Chebyshev distance between two vectors.
|
|
172
|
|
|
|
|
173
|
|
|
"""
|
|
174
|
|
|
if isinstance(point1, collections.Iterable):
|
|
175
|
|
|
distance = 0.0;
|
|
176
|
|
|
dimension = len(point1);
|
|
177
|
|
|
|
|
178
|
|
|
for i in range(dimension):
|
|
179
|
|
|
distance = max(distance, abs(point1[i] - point2[i]));
|
|
180
|
|
|
|
|
181
|
|
|
return distance;
|
|
182
|
|
|
|
|
183
|
|
|
return abs(point1 - point2); |
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.