| 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 |
|