Debian Codegraph @

doc/clmdist.azm

raw ◀ ▶
Source reconstructed at patch state 0 of 1 — not the installed (fully patched) source.
1 Debian patch touch this file
1 \import{mcx.zmm}
2
3 \begin{pud::man}{
4
5 {name}{clm dist}
6 {html_title}{The clm dist manual}
7 {author}{Stijn van Dongen}
8 {section}{1}
9 {synstyle}{long}
10 {defstyle}{long}
11
12 \man_share
13 }
14
15 \${html}{\"pud::man::maketoc"}
16
17 \def{p1}{\bf{P1}}
18 \def{p2}{\bf{P2}}
19 \def{D}{\bf{D}}
20 \def{N}{\bf{N}}
21 \def{d1}{\bf{d1}}
22 \def{d2}{\bf{d2}}
23 \def{sjd}{\bf{sjd}}
24
25 \sec{name}{NAME}
26 \NAME{clm dist}{compute the distance between two or more partitions\
27 (clusterings).}
28
29 \par{
30 The distance that is computed can be any of
31 \it{split/join distance}, \it{variance of information},
32 or \it{Mirkin metric}.}
33
34 \disclaim_clm{dist}
35
36 \sec{synopsis}{SYNOPSIS}
37 \par{
38 \clm{dist} [options] <file name> <file name>+}
39
40 \par{
41 \clm{dist}
42 \synoptopt{-mode}{<sj|vi|mk|sc>}{distance type}
43 \synoptopt{-o}{fname}{output file}
44 \synoptopt{--chain}{only compare consecutive clusterings}
45 \synoptopt{--one-to-many}{compare first clustering to all others}
46 \synoptopt{--sort}{sort clusterings based on coarseness}
47 \synoptopt{--index}{output Rand, adjusted Rand and Jaccard indices}
48 \synoptopt{-digits}{k}{output decimals}
49 \stdsynopt
50 <file name> <file name>+}
51
52 \sec{description}{DESCRIPTION}
53
54 \par{
55 \clm{dist} computes distances between clusterings. It can compute the
56 \it{split/join distance} (described below), the \it{variance of information
57 measure}, and the \it{Mirkin metric}. By default it computes the chosen distance
58 for all pairs of distances in the clusterings provided. Clusterings must be in
59 the mcl matrix format (cf. \mysib{mcxio}), and are supplied on the command
60 line as the names of the files in which they are stored.
61 It is possible to compare only consecutive clusterings by using
62 the \genopt{--chain} option.
63 }
64
65 \par{
66 Currently, \clm{dist} cannot compute different distance types simultaneously.}
67
68 \par{
69 The output is linewise, each line giving information about
70 the distance between a pair of clusterings. A line has the
71 following format:}
72
73 \verbatim{\:/
74 d d1 d2 N v name1 name2 [v50,v75,v90,v95,v99]}
75
76 \car{
77 where \v{dT} is the distance between the two clusterings, \v{d1} is the
78 distance from the first clustering to the greatest common subclustering
79 (alternatively called GCS, intersection, or meet) of the two clusterings,
80 \v{d2} is similarly the distance from the second clustering to the GCS,
81 \v{N} is the number of nodes in the set over which the clusterings are
82 defined, \v{name1} is the name of the file containing the first clustering,
83 \v{name2} is the name of the file containing the second clustering, and
84 \v{vXX} is the number of \it{volatile nodes} at stringency factor \v{0.XX}
85 (i.e. 0.5 for \v{v50}). Refer to \clmref{vol} for a definition of
86 \it{volatile node}.
87
88 }
89
90 \sec{options}{OPTIONS}
91
92 \'begin{itemize}{\mcx_itemopts}
93
94 \item{\defopt{-mode}{<sj|vi|mk>}{distance type}}
95 \car{
96 Use \bf{sj} for the \it{split/join distance} (described below), \bf{vi} for
97 the \it{variance of information measure} and \bf{mk} for the \it{Mirkin metric}.}
98
99
100 \item{\defopt{--chain}{only compare consecutive clusterings}}
101 \car{
102 This option can be used if you know that the clusterings are nested
103 clusterings (or appoximately so) and ordered from coarse to fine-grained
104 or vice versa. An example of this is the set of clusterings resulting
105 from applying \mcl with a range of inflation parameters.
106 }
107
108 \item{\defopt{--one-to-many}{compare first clustering to all others}}
109 \car{
110 Use this option for example to compare a gold standard classification
111 to a collection of clusterings.
112 Bear in mind that sub-clustering and super-clustering are also
113 ways for a clustering to be compatible with a gold standard.
114 This means that the simple numerical criterion of distance between
115 clusters (by whatever method) is only partially informative.
116 For the Mirkin, variation of information and split/join metrics
117 it pays to take into account the constituent distances \v{d1}
118 and \v{d2} (see above). Assuming that the first clustering
119 given as argument represents a gold standard, a small value
120 for \v{d1} implies that the second clustering is (nearly) a superclustering,
121 and similarly a small value for \v{d2} implies that it is (nearly)
122 a subclustering.
123 }
124
125
126 \item{\defopt{--sort}{sort clusterings based on coarseness}}
127 \car{
128 This option can be useful in conjunction with the \genopt{--chain}
129 option, in case the list of clusterings supplied is not necessarily
130 ordered by granularity.
131 }
132
133 \item{\defopt{--index}{output Rand, adjusted Rand and Jaccard indices}}
134 \car{
135 As described.
136 }
137
138 \item{\defopt{-o}{fname}{output file}}
139
140 \item{\defopt{-digits}{k}{output decimals}}
141 \car{
142 The number of decimals printed when using the variance of information measure.}
143
144 \stddefopt
145
146 \end{itemize}
147
148 \sec{}{SPLIT/JOIN DISTANCE}
149 \par{
150 For each pair of clusterings \bf{C1}, \bf{C2}, two numbers are given,
151 say \bf{d1} and \bf{d2}. Then \bf{d1} + \bf{d2} equals the number
152 of nodes that have to be exchanged in order to transform any of the two
153 clusterings into the other, and you can think of (\bf{d1}+\bf{d2})/\bf{2N}
154 as the percentage that the two clusterings differ. The split/join
155 distance has a linearity property with respect to the meet of \bf{C1} and
156 \bf{C2}, see below.}
157
158 \par{
159 The split/join distance \sjd is very handy in computing the consistency of
160 two or more clusterings of the same graph, or comparing clusterings made
161 with different resource (but otherwise identical) parameters. The latter is
162 for finding out whether you can settle for cheaper mcl settings, or whether
163 you need to switch to more expensive settings. The former is for finding out
164 whether clusterings are identical, conflicting, or whether one is (almost) a
165 subclustering of the other - mostly for comparing a set of clusterings of
166 different granularity, made by letting the mcl parameter \genopt{-I} vary.
167 The \secref{examples} section contains examples of all these \clm{dist} uses,
168 and the use of \clm{info} and \clm{meet} is also discussed there.}
169
170 \par{
171 \sjd is a metric distance on the space of partitions of
172 a set of a given fixed cardinality. It has the following linearity
173 property. Let \p1 and \p2 be partitions, then}
174
175 \par{
176 \sjd(\p1, \p2) = \sjd(\p1, \D) + \sjd(\p2, \D)}
177
178 \par{
179 where \D (for Dutch Doorsnede)
180 is the intersection of \p1 and \p2, i.e. the unique clustering
181 that is both a subclustering of \p1 and \p2 \it{and} a superclustering of
182 all other subclusterings of \p1 and \p2. Sloppily worded, \D is the largest
183 subclustering of both \p1 and \p2. See the \secref{references} section for
184 a pointer to the technical report in which \sjd was first defined (and in
185 which the non-trivial triangle inequality is proven).}
186
187 \par{
188 Because it is useful to know whether one partition (or clustering)
189 is almost a subclustering of the other, \clm{dist} returns the
190 two constituents \sjd(\p1,\D) and \sjd(\p2,\D).}
191
192 \par{
193 Let \p1 and \p2 be two clusterings of a graph of cardinality \N,
194 and suppose \clm{dist} returns the integers \d1 and \d2. You can think of
195 \bf{100 * (d1 + d2) / N} as the percentage that \p1 and \p2 differ.
196
197 This interpretation is in fact slightly conservative.
198 The numerator is the number of nodes that need to be exchanged in order to
199 transform one into the other. This number may grow as large as
200 \bf{2*N - 2*sqrt(N)}, so it would be justified to take 50 as a scaling
201 factor rather than 100.}
202
203 \par{
204 For example, if \bf{A} and \bf{B} are both clusterings of a graph
205 on a set of 9058 nodes and \clm{dist} returns [38, 2096], this conveys
206 that \bf{A} is almost a subclustering of \bf{B} (by splitting 38 nodes
207 in \bf{A} we obtain a clustering \bf{D} that is a subclustering of \bf{B}),
208 and that \bf{B} is much less granular than \bf{A}. The latter is
209 because we can obtain \bf{B} from \bf{D} by \it{joining} 2096 nodes
210 in some way.}
211
212
213 \sec{examples}{EXAMPLES}
214
215 \: todo: different resource levels on huge for -I 1.4
216 \: comparing different clusterings of huge.
217 \: comparing the latter with \clm{meet}.
218
219 \par{
220 The following is an example of several mcl validation tools
221 applied to a set of clusterings on a protein graph of 9058 nodes.
222 In the first experiment, six
223 different clusterings were generated for different values of the inflation
224 parameter, which was respectively set to 1.2, 1.6, 2.0, 2.4, 2.8, and 3.2.
225 It should be noted that protein graphs seem somewhat special in that an
226 inflation parameter setting as low as 1.2 still produces a very acceptable
227 clustering. The six clusterings are scrutinized using \clm{dist},
228 \clm{info}, and \clm{meet}.
229 In the second experiment, four different clusterings were generated
230 with identical flow (i.e. inflation) parameter, but
231 with different resource parameters. \clm{dist} is used to choose
232 a sufficient resource level.}
233
234 \par{
235 High \genopt{-P/-S/-R} values make \mcl more accurate but also
236 more time and memory consuming. Run \mcl with different settings for these
237 parameters, holding other parameters fixed. If the expensive and supposedly
238 more accurate clusterings are very similar to the clusterings resulting from
239 cheaper settings, the cheaper setting is sufficient. If the distances
240 between cheaper clusterings and more expensive clusterings are large, this
241 is an indication that you need the expensive settings. In that case, you may
242 want to increase the \genopt{-P/-S/-R} parameters (or simply the
243 \genopt{-scheme} parameter) until associated
244 clusterings at nearby resource levels are very similar.}
245
246 \par{
247 In this particular example, the validation tools do not reveal that one
248 clustering in particular can be chosen as 'best', because all clusterings
249 seem at least acceptable. They do aid however in showing the relative
250 merits of each clusterings. The most important issue in this respect is
251 cluster granularity. The table below shows the output of \clm{info}.}
252
253 \verbatim{
254 Efficiency Mass frac Area frac Cl weight Mx link weight
255 1.2 0.42364 0.98690 0.02616 52.06002 50.82800
256 1.6 0.58297 0.95441 0.01353 55.40282 50.82800
257 2.0 0.63279 0.92386 0.01171 58.09409 50.82800
258 2.4 0.65532 0.90702 0.01091 59.58283 50.82800
259 2.8 0.66854 0.84954 0.00940 63.19183 50.82800
260 3.2 0.67674 0.82275 0.00845 66.10831 50.82800}
261
262 \car{
263 This data shows that there is exceptionally strong cluster structure present
264 in the input graph. The 1.2 clustering captures almost all edge mass using
265 only 2.5 percent of 'area'. The 3.2 clustering still captures 82 percent of
266 the mass using less than 1 percent of area. We continue with looking at the
267 mutual consistency of the six clusterings. Below is a table that shows all
268 pairwise distances between the clusterings.}
269
270 \verbatim{
271 | 1.6 | 2.0 | 2.4 | 2.8 | 3.2 | 3.6
272 -----------------------------------------------------------.
273 1.2 |2096,38 |2728,41 |3045,48 |3404,45 |3621,43 |3800, 42 |
274 -----------------------------------------------------------|
275 1.6 | | 797,72 |1204,76 |1638,78 |1919,70 |2167, 69 |
276 -----------------------------------------------------------|
277 2.0 | | | 477,68 | 936,78 |1235,85 |1504, 88 |
278 -----------------------------------------------------------|
279 2.4 | | | | 498,64 | 836,91 |1124,103 |
280 -----------------------------------------------------------|
281 2.8 | | | | | 384,95 | 688,119 |
282 -----------------------------------------------------------|
283 3.2 | | | | | | 350,110 |
284 -----------------------------------------------------------.
285 }
286
287 \par{
288 The table shows that the different clusterings are pretty consistent with
289 each other, because for two different clusterings it is generally true that
290 one is almost a subclustering of the other. The interpretation for the
291 distance between the 1.6 and the 3.2 clustering for example, is that by
292 rearranging 43 nodes in the 3.2 clustering, we obtain a subclustering of the
293 1.6 clustering. The table shows that for any pair of clusterings, at most
294 119 entries need to be rearranged in order to make one a subclustering of
295 the other.}
296
297 \par{
298 The overall consistency becomes all the more clear by looking at the meet of
299 all the clusterings:}
300
301 \verbatim{
302 clm meet -o meet out12 out16 out20 out24 out28 out32
303 clm dist meet out12 out16 out20 out24 out28 out32}
304
305 \car{
306 results in the following distances between the respective clusterings
307 and their meet.}
308
309 \verbatim{
310 | 1.2 | 1.6 | 2.0 | 2.4 | 2.8 | 3.2 |
311 -------------- --------------------------------------------.
312 meet| 0,3663| 0,1972| 0,1321 | 0,958 | 0,559 | 0,283 |
313 -------------- --------------------------------------------.}
314
315 \car{
316 This shows that by rearranging only 283 nodes in the 3.2 clustering,
317 one obtains a subclustering of all other clusterings.}
318
319 \par{
320 In the last experiment, \mcl was run with inflation parameter 1.4,
321 for each of the four different preset pruning schemes \v{k=1,2,3,4}.
322 The \clm{dist} distances between the different clusterings
323 are shown below.}
324
325 \verbatim{
326 | k=2 | k=3 | k=4 |
327 -------------------------------.
328 k=1 | 17,17 | 16,16 | 16,16 |
329 -------------------------------.
330 k=2 | | 3,3 | 5,5 |
331 -------------------------------.
332 k=3 | | | 4,4 |
333 -------------------------------.}
334
335 \car{
336 This example is a little boring in that the cheapest scheme seems adequate.
337 If anything, the gaps between the \v{k=1} scheme and the rest are a little
338 larger than the three gaps between the \v{k=2}, \v{k=3}, and \v{k=4}
339 clusterings. Had all distances been much larger, then such an observation
340 would be reason to choose the \v{k=2} setting.}
341
342 \par{
343 Note that you need not feel uncomfortable with the clusterings
344 still being different at high resource levels, if ever so slightly.
345 In all likelihood, there are anyway nodes which are not in any core of
346 attraction, and that are on the boundary between two or more clusterings.
347 They may go one way or another, and these are the nodes which
348 will go different ways even at high resource levels.
349 Such nodes may be stable in clusterings obtained for lower inflation
350 values (i.e. coarser clusterings), in which the different clusters
351 to which they are attracted are merged.}
352
353 \sec{author}{AUTHOR}
354 \par{
355 Stijn van Dongen.}
356
357
358 \sec{seealso}{SEE ALSO}
359 \par{
360 \mysib{mclfamily} for an overview of all the documentation
361 and the utilities in the mcl family.}
362
363 \sec{references}{REFERENCES}
364
365 \par{
366 Stijn van Dongen. \it{Performance criteria for graph clustering and Markov
367 cluster experiments}. Technical Report INS-R0012, National Research
368 Institute for Mathematics and Computer Science in the Netherlands,
369 Amsterdam, May 2000.\|
370 \httpref{http://www.cwi.nl/ftp/CWIreports/INS/INS-R0012.ps.Z}}
371
372 \par{
373 Marina Meila. \it{Comparing Clusterings \- An Axiomatic View}.
374 In \it{Proceedings of the 22nd International Conference on Machine Learning},
375 Bonn, Germany, 2005.}
376
377 \par{
378 Marina Meila. \it{Comparing Clusterings},
379 UW Statistics Technical Report 418.\|
380 \httpref{http://www.stat.washington.edu/www/research/reports/2002/tr418.ps}}
381
382 \end{pud::man}
383