-
Notifications
You must be signed in to change notification settings - Fork 0
/
dissimilarity.py
246 lines (202 loc) · 7.72 KB
/
dissimilarity.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
"""Computation of the dissimilarity representation of a set of objects
(streamlines) from a set of prototypes (streamlines) given a distance
function. Some prototype selection algorithms are available.
See Olivetti E., Nguyen T.B., Garyfallidis, E., The Approximation of
the Dissimilarity Projection, http://dx.doi.org/10.1109/PRNI.2012.13
Copyright Emanuele Olivetti, 2017
MIT License
"""
from __future__ import division
import numpy as np
from dipy.tracking.distances import bundles_distances_mam
try:
from joblib import Parallel, delayed, cpu_count
joblib_available = True
except:
joblib_available = False
def furthest_first_traversal(tracks, k, distance, permutation=True):
"""This is the farthest first traversal (fft) algorithm which
selects k streamlines out of a set of streamlines (tracks). This
algorithms is known to be a good sub-optimal solution to the
k-center problem, i.e. the k streamlines are sequentially selected
in order to be far away from each other.
Parameters
----------
tracks : list or array of objects
an iterable of streamlines.
k : int
the number of streamlines to select.
distance : function
a distance function between groups of streamlines, like
dipy.tracking.distances.bundles_distances_mam
permutation : bool
True if you want to shuffle the streamlines first. No
side-effect.
Return
------
idx : array of int
an array of k indices of the k selected streamlines.
Notes
-----
- Hochbaum, Dorit S. and Shmoys, David B., A Best Possible
Heuristic for the k-Center Problem, Mathematics of Operations
Research, 1985.
- http://en.wikipedia.org/wiki/Metric_k-center
See Also
--------
subset_furthest_first
"""
if permutation:
idx = np.random.permutation(len(tracks))
tracks = tracks[idx]
else:
idx = np.arange(len(tracks), dtype=np.int)
T = [0]
while len(T) < k:
z = distance(tracks, tracks[T]).min(1).argmax()
T.append(z)
return idx[T]
def subset_furthest_first(tracks, k, distance, permutation=True, c=2.0):
"""The subset furthest first (sff) algorithm is a stochastic
version of the furthest first traversal (fft) algorithm. Sff
scales well on large set of objects (streamlines) because it
does not depend on len(tracks).
Parameters
----------
tracks : list or array of objects
an iterable of streamlines.
k : int
the number of streamlines to select.
distance : function
a distance function between groups of streamlines, like
dipy.tracking.distances.bundles_distances_mam
permutation : bool
True if you want to shuffle the streamlines first. No
side-effect.
c : float
Parameter to tune the probability that the random subset of
streamlines is sufficiently representive of tracks. Typically
2.0-3.0.
Return
------
idx : array of int
an array of k indices of the k selected streamlines.
See Also
--------
furthest_first_traversal
Notes
-----
See: E. Olivetti, T.B. Nguyen, E. Garyfallidis, The Approximation
of the Dissimilarity Projection, Proceedings of the 2012
International Workshop on Pattern Recognition in NeuroImaging
(PRNI), pp.85,88, 2-4 July 2012 doi:10.1109/PRNI.2012.13
"""
size = int(max(1, np.ceil(c * k * np.log(k))))
if permutation:
idx = np.random.permutation(len(tracks))[:size]
else:
idx = range(size)
return idx[furthest_first_traversal(tracks[idx],
k, distance,
permutation=False)]
def dissimilarity(tracks, prototypes, distance, n_jobs=-1, verbose=False):
"""Compute the dissimilarity (distance) matrix between tracks and
given prototypes. This function supports parallel (multicore)
computation.
Parameters
----------
tracks : list or array of objects
an iterable of streamlines.
prototypes : iterable of objects
The prototypes.
distance : function
Distance function between groups of streamlines.
prototype_policy : string
Shortname for the prototype selection policy. The default
value is 'sff'.
n_jobs : int
If joblib is available, split the dissimilarity computation
in n_jobs. If n_jobs is -1, then all available cpus/cores
are used. The default value is -1.
verbose : bool
If true prints some messages. Deafault is True.
Return
------
dissimilarity_matrix : array (N, num_prototypes)
See Also
--------
furthest_first_traversal, subset_furthest_first
Notes
-----
"""
if verbose:
print("Computing the dissimilarity matrix.")
if joblib_available and n_jobs != 1:
if n_jobs is None or n_jobs == -1:
n_jobs = cpu_count()
if verbose:
print("Parallel computation of the dissimilarity matrix: %s cpus." % n_jobs)
if n_jobs > 1:
tmp = np.linspace(0, len(tracks), n_jobs).astype(np.int)
else: # corner case: joblib detected 1 cpu only.
tmp = (0, len(tracks))
chunks = zip(tmp[:-1], tmp[1:])
dissimilarity_matrix = np.vstack(Parallel(n_jobs=n_jobs)(delayed(distance)(tracks[start:stop], prototypes) for start, stop in chunks))
else:
dissimilarity_matrix = distance(tracks, prototypes)
if verbose:
print("Done.")
return dissimilarity_matrix
def compute_dissimilarity(tracks, num_prototypes=40,
distance=bundles_distances_mam,
prototype_policy='sff',
n_jobs=-1,
verbose=False):
"""Compute the dissimilarity (distance) matrix between tracks and
prototypes, where prototypes are selected among the tracks with a
given policy.
Parameters
----------
tracks : list or array of objects
an iterable of streamlines.
num_prototypes : int
The number of prototypes. In most cases 40 is enough, which
is the default value.
distance : function
Distance function between groups of streamlines. The
default is bundles_distances_mam
prototype_policy : string
Shortname for the prototype selection policy. The default
value is 'sff'.
n_jobs : int
If joblib is available, split the dissimilarity computation
in n_jobs. If n_jobs is -1, then all available cpus/cores
are used. The default value is -1.
verbose : bool
If true prints some messages. Deafault is True.
Return
------
dissimilarity_matrix : array (N, num_prototypes)
See Also
--------
furthest_first_traversal, subset_furthest_first
Notes
-----
"""
if verbose:
print("Generating %s prototypes with policy %s." % (num_prototypes, prototype_policy))
if prototype_policy == 'random':
prototype_idx = np.random.permutation(len(tracks))[:num_prototypes]
elif prototype_policy == 'fft':
prototype_idx = furthest_first_traversal(tracks,
num_prototypes, distance)
elif prototype_policy == 'sff':
prototype_idx = subset_furthest_first(tracks, num_prototypes, distance)
else:
if verbose:
print("Prototype selection policy not supported: %s" % prototype_policy)
raise Exception
prototypes = [tracks[i] for i in prototype_idx]
dissimilarity_matrix = dissimilarity(tracks, prototypes, distance,
n_jobs=n_jobs, verbose=verbose)
return dissimilarity_matrix, prototype_idx