增强现实AR>> xmeasures>> 返回
项目作者： eXascaleInfolab

项目描述 ：
Extremely fast evaluation of the extrinsic clustering measures: various (mean) F1 measures and Omega Index (Fuzzy Adjusted Rand Index) for the multi-resolution clustering with overlaps/covers, standard NMI, clusters labeling
高级语言： C++
项目地址: git://github.com/eXascaleInfolab/xmeasures.git
创建时间： 2017-02-20T16:56:39Z
项目社区：https://github.com/eXascaleInfolab/xmeasures
开源协议：Apache License 2.0
下载


xmeasures - Extrinsic Clustering Measures

Extremely fast evaluation of accuracy (extrinsic quality) measures for the [overlapping/fuzzy] clusterings (collections of groups of items):
family of [mean] F1 measures (including Average F1-Score) and Omega Index (fuzzy version of the Adjusted Rand Index) for overlapping multi-resolution clusterings with unequal node base (and optional node base synchronization) using various matching policies (micro, macro and combined weighting),
and standard NMI for non-overlapping clustering on a single resolution. xmeasures also provides clusters labeling with the indices of the ground-truth clusters considering 1:n match and evaluating F1, precision and recall of the labeled clusters.

xmeasures evaluates F1 and NMI for collections of hundreds thousands [overlapping] clusters (covers, communities) withing a dozen seconds on an ordinary laptop using a single CPU core. The computational time is O(N)
unlike O(N * C)
of the existing state of the art implementations, where N is the number of nodes in the network and C is the number of clusters. Computational complexity for Omega Index is standard and equals O(N^2 * s/2), where s is the average sharing ratio (membership) of the nodes, typically s -> 1.
xmeasures is one of the utilities designed for the PyCaBeM clustering benchmark to evaluate clusterings of large networks.

The paper: Accuracy Evaluation of Overlapping and Multi-resolution Clustering Algorithms on Large Datasets

  1. @inproceedings{Xms19,
  2.     author={Artem Lutov and Mourad Khayati and Philippe Cudr{\'e}-Mauroux},
  3.     title={Accuracy Evaluation of Overlapping and Multi-resolution Clustering Algorithms on Large Datasets},
  4.     booktitle={6th IEEE International Conference on Big Data and Smart Computing (BigComp 2019)},
  5.     year={2019},
  6.     keywords={accuracy metrics, overlapping community evaluation, multi-resolution clustering evaluation, Generalized NMI, Omega Index, MF1, similarity of collections of sets}
  7. }

Related papers about the implemented measures:

  • Omega Index (fuzzy version of the Adjusted Rand Index), which equal to ARI when applied for the non-overlapping clusterings;
  • Mean F1 measures: F1a (Average F1-Score), F1p is much more indicative and discriminative than the presented there F1a but the respective paper has not been published yet;
  • NMI measure.

    Standard NMI is implemented considering overlapping and multi-resolution clustering only to demonstrate non-applicability of the standard NMI for such cases, where it yields unfair results. See GenConvNMI for the fair generalized NMI evaluation.

The execution time and the total processing time (relative power consumption) of xmeasures on a single CPU core vs ParallelComMetric on multiple SMP cores evaluated on the SNAP DBLP dataset and shown in the log scale demonstrates that xmeasures evaluates F1 family measures multiple orders of magnitude faster than other state-of-the-art solutions:
Clubmark_Poster-w1024

Author: (c) Artem Lutov artem@exascale.info

Content

Deployment

The target platform is NIX/Posix, the binary is compiled for Linux Ubuntu x64 and also should work on Windows 10+ x64 (see details in this article).

Requirements

There are no any requirements for the execution or compilation except the standard C++ library.

To run the prebuilt executable on Linux Ubuntu 16.04 x64, the standard library can be installed by: $ sudo apt-get install libstdc++6.

Compilation

Application Compilation

  1. $ make release

The following build errors might occur on some platforms and should be resolved as outlined.

  • If your default compiler is g++/gcc < 5.x, then g++-5 or higher should be installed and Makefile might need to be edited replacing g++, gcc with g++-5, gcc-5.
  • -fstack-clash-protection compiler flag is added since xmeasures v4.0.5, which might not be supported by Clang/LLVM and GCC < 8.2. This flag just hardens the application against some stack overflow attacks and should be excluded from the Makefile if not supported on your platform.

To update/extend the input parameters, modify args.ggo and run GenerateArgparser.sh (calls gengetopt) before running make. To install gengetopt, execute: $ sudo apt-get install gengetopt.

Library Compilation

Some core functionality of xmeasures is available as a library with C API, making it possible to link the library from Python and other scripting languages.
The interface is defined in include/interface_c.h.
To build the library, execute:

  1. $ make -f Makefile_lib release

Usage

Execution Options:

  1. $ ../xmeasures -h
  2. xmeasures 4.0.4
  4. Extrinsic measures evaluation: Omega Index (a fuzzy version of the Adjusted
  5. Rand Index, identical to the Fuzzy Rand Index) and [mean] F1-score (prob, harm
  6. and avg) for the overlapping multi-resolution clusterings, and standard NMI for
  7. the non-overlapping clustering on a single resolution. Unequal node base is
  8. allowed in the evaluating clusterings and optionally can be synchronized
  9. removing nodes from the clusters missed in one of the clusterings
  10. (collections).
  12. Usage: xmeasures [OPTIONS] clustering1 clustering2
  14.   clustering  - input file, collection of the clusters to be evaluated.
  16. Examples:
  17.   $ ./xmeasures -fp -kc networks/5K25.cnl tests/5K25_l0.825/5K25_l0.825_796.cnl
  18.   $ ./xmeasures -fh -kc -i tests/5K25.cll -ph -l networks/5K25.cnl
  19. tests/5K25_l0.825/5K25_l0.825_796.cnl
  20.   $ ./xmeasures -ox tests/clsevalsx/omega_c4.3-1.cnl
  21. tests/clsevalsx/omega_c4.3-2.cnl
  24. Extrinsic measures are evaluated, i.e. two input clusterings (collections of
  25. clusters) are compared to each other. Optionally, a labeling of the evaluating
  26. clusters with the specified ground-truth clusters is performed.
  27. NOTE:
  28.   - Multiple evaluating measures can be specified.
  29.   - Each cluster should contain unique members, which is ensured only if the
  30. 'unique' option is specified.
  31.   - All clusters should be unique to not affect Omega Index evaluation, which
  32. can be ensured by the [resmerge](https://github.com/eXascaleInfolab/resmerge)
  33. utility.
  34.   - Non-corrected unequal node base in the clusterings is allowed, it penalizes
  35. the match.Use [OvpNMI](https://github.com/eXascaleInfolab/OvpNMI) or
  36. [GenConvNMI](https://github.com/eXascaleInfolab/GenConvNMI) for NMI evaluation
  37. in the arbitrary collections (still each cluster should contain unique
  38. members).
  40. Evaluating measures are:
  41.   - OI  - Omega Index (a fuzzy version of the Adjusted Rand Index, identical to
  42. the Fuzzy Rand Index), which yields the same value as Adjusted Rand Index when
  43. applied to the non-overlapping clusterings.
  44.   - [M]F1  - various [mean] F1 measures of the Greatest (Max) Match including
  45. the Average F1-Score (suggested by J. Leskovec) with the optional weighting.
  46. NOTE: There are 3 matching policies available for each kind of F1. The most
  47. representative evaluation is performed by the F1p with combined matching
  48. policy (considers both micro and macro weighting).
  49.   - NMI  - Normalized Mutual Information, normalized by either max or also
  50. sqrt, avg and min information content denominators.
  51. ATTENTION: This is a standard NMI, which should be used ONLY for the HARD
  52. partitioning evaluation (non-overlapping clustering on a single resolution).
  53. It penalizes overlapping and multi-resolution structures.
  56.   -h, --help                    Print help and exit
  57.   -V, --version                 Print version and exit
  58.   -O, --ovp                     evaluate overlapping instead of the
  59.                                   multi-resolution clusters, where max matching
  60.                                   for any shared member between R overlapping
  61.                                   clusters is 1/R (the member is shared)
  62.                                   instead of 1 (the member fully belongs to
  63.                                   each [hierarchical  sub]group) for the member
  64.                                   belonging to R distinct clusters on R
  65.                                   resolutions.
  66.                                   NOTE: It has no effect for the Omega Index
  67.                                   evaluation.  (default=off)
  68.   -q, --unique                  ensure on loading that all cluster members are
  69.                                   unique by removing all duplicates.
  70.                                   (default=off)
  71.   -s, --sync=filename           synchronize with the specified node base
  72.                                   omitting the non-matching nodes.
  73.                                   NOTE: The node base can be either a separate,
  74.                                   or an evaluating CNL file, in the latter case
  75.                                   this option should precede the evaluating
  76.                                   filename not repeating it
  77.   -m, --membership=FLOAT        average expected membership of the nodes in the
  78.                                   clusters, > 0, typically >= 1. Used only to
  79.                                   facilitate estimation of the nodes number on
  80.                                   the containers preallocation if this number
  81.                                   is not specified in the file header.
  82.                                   (default=`1')
  83.   -d, --detailed                detailed (verbose) results output
  84.                                   (default=off)
  86. Omega Index:
  87.   -o, --omega                   evaluate Omega Index (a fuzzy version of the
  88.                                   Adjusted Rand Index, identical to the Fuzzy
  89.                                   Rand Index and on the non-overlapping
  90.                                   clusterings equals to ARI).  (default=off)
  91.   -x, --extended                evaluate extended (Soft) Omega Index, which
  92.                                   does not excessively penalize distinctly
  93.                                   shared nodes.  (default=off)
  95. Mean F1:
  96.   -f, --f1[=ENUM]               evaluate mean F1 of the [weighted] average of
  97.                                   the greatest (maximal) match by F1 or partial
  98.                                   probability.
  99.                                   NOTE: F1h <= F1a, where:
  100.                                    - p (F1p or Ph)  - Harmonic mean (F1) of two
  101.                                   [weighted] averages of the Partial
  102.                                   Probabilities, the most indicative as
  103.                                   satisfies the largest number of the Formal
  104.                                   Constraints (homogeneity, completeness and
  105.                                   size/quantity except the rag bag in some
  106.                                   cases);
  107.                                    - h (F1h)  - Harmonic mean (F1) of two
  108.                                   [weighted] averages of all local F1 (harmonic
  109.                                   means of the Precision and Recall of the best
  110.                                   matches of the clusters);
  111.                                    - a (F1a)  - Arithmetic mean (average) of
  112.                                   two [weighted] averages of all local F1, the
  113.                                   least discriminative and satisfies the lowest
  114.                                   number of the Formal Constraints.
  115.                                   Precision and recall are evaluated relative
  116.                                   to the FIRST clustering dataset
  117.                                   (ground-truth, gold standard).
  118.                                     (possible values="partprob",
  119.                                   "harmonic", "average" default=`partprob')
  120.   -k, --kind[=ENUM]             kind of the matching policy:
  121.                                    - w  - Weighted by the number of nodes in
  122.                                   each cluster (known as micro weighting,
  123.                                   MF1_micro)
  124.                                    - u  - Unweighed, where each cluster is
  125.                                   treated equally (known as macro weighting,
  126.                                   MF1_macro)
  127.                                    - c  - Combined(w, u) using geometric mean
  128.                                   (drops the value not so much as harmonic
  129.                                   mean)
  130.                                     (possible values="weighted",
  131.                                   "unweighed", "combined"
  132.                                   default=`weighted')
  134. Clusters Labeling & F1 evaluation with Precision and Recall:
  135.   -l, --label=gt_filename       label evaluating clusters with the specified
  136.                                   ground-truth (gt) cluster indices and
  137.                                   evaluate F1 (including Precision and Recall)
  138.                                   of the (best) MATCHED labeled clusters only
  139.                                   (without the probable subclusters).
  140.                                   NOTE: If 'sync' option is specified then the
  141.                                   file name of the clusters labels should be
  142.                                   the same as the node base (if specified) and
  143.                                   should be in the .cnl format. The file name
  144.                                   can be either a separate or an evaluating CNL
  145.                                   file, in the latter case this option should
  146.                                   precede the evaluating filename not repeating
  147.                                   it.
  148.                                   Precision and recall are evaluated relative
  149.                                   to the FIRST clustering dataset
  150.                                   (ground-truth, gold standard).
  152.   -p, --policy[=ENUM]           Labels matching policy:
  153.                                    - p  - Partial Probabilities (maximizes
  154.                                   gain)
  155.                                    - h  - Harmonic Mean (minimizes loss,
  156.                                   maximizes F1)
  157.                                     (possible values="partprob", "harmonic"
  158.                                   default=`harmonic')
  159.   -u, --unweighted              Labels weighting policy on F1 evaluation:
  160.                                   weighted by the number of instances in each
  161.                                   label by default (micro weighting, F1_micro)
  162.                                   or unweighed, where each label is treated
  163.                                   equally (i.e. macro weighting, F1_macro)
  164.                                   (default=off)
  165.   -i, --identifiers=labels_filename
  166.                                 output labels (identifiers) of the evaluating
  167.                                   clusters as lines of space-separated indices
  168.                                   of the ground-truth clusters (.cll - clusters
  169.                                   labels list)
  170.                                   NOTE: If 'sync' option is specified then the
  171.                                   reduced collection is outputted to the
  172.                                   <labels_filename>.cnl besides the
  173.                                   <labels_filename>
  175. NMI:
  176.   -n, --nmi                     evaluate NMI (Normalized Mutual Information),
  177.                                   applicable only to the non-overlapping
  178.                                   clusters  (default=off)
  179.   -a, --all                     evaluate all NMIs using sqrt, avg and min
  180.                                   denominators besides the max one
  181.                                   (default=off)
  182.   -e, --ln                      use ln (exp base) instead of log2 (Shannon
  183.                                   entropy, bits) for the information measuring
  184.                                   (default=off)

Empty lines and comments (lines starting with #) in the input file (cnl format) are omitted.

Examples
Evaluate harmonic mean of the weighted average of the greatest (maximal) match by partial probabilities (the most discriminative F1-measure) using macro weighting (default as the most frequently used, thought combined weighting is the most indicative one):

  1. $ ./xmeasures -f data/3cls5nds.cnl data/4cls6nds.cnl

Evaluate harmonic mean of the weighted average (by the cluster size) of the greatest (maximal) match by F1s and insure than all cluster members are unique (the duplicated members are removed):

  1. $ ./xmeasures -fh -q data/3cls5nds.cnl data/4cls6nds.cnl

Evaluate harmonic mean of the [unweighted] average of the greatest (maximal) match by partial probabilities and synchronize the node base with the first evaluating collection, and considering overlapping clusters instead of multi-resolutions (-O does not matter for the case of non-overlapping single resolution collections):

  1. $ ./xmeasures -sku -fp -O data/3cls5nds.cnl data/4cls6nds.cnl

Evaluate arithmetic mean of the weighted average (by the cluster size) of the greatest (maximal) match by F1s and NMI with all denominators synchronizing node base of the evaluating collections with 1lev4nds2cls.cnl:

  1. $ ./xmeasures -fa -na -s data/1lev4nds2cls.cnl data/3cls5nds.cnl data/4cls6nds.cnl

Evaluate combined weighed and unweighted F1h (harmonic mean of the average F1s), label the clusters with the indices of provided labels, evaluate standard F1, precision and recall of the labeled clusters and output the labels to the clslbs.cll:

  1. $ ./xmeasures -fh -kc -i clslbs.cll -l labels.cnl clusters.cnl

Evaluate extended Omega Index and mean F1h (harmonic mean of the weighted average of the greatest (maximal) match by F1):

  1. $ ./xmeasures -ox -fh omega_c4.3-1.cnl omega_c4.3-2.cnl

Note: Please, star this project if you use it.

Related Projects

  • GenConvNMI - Overlapping NMI evaluation that is compatible with the original NMI and suitable for both overlapping and multi resolution (hierarchical) clustering evaluation.
  • OvpNMI - NMI evaluation for the overlapping clusters (communities) that is not compatible with the standard NMI value unlike GenConvNMI, but it is much faster than GenConvNMI.
  • Clubmark - A parallel isolation framework for benchmarking and profiling clustering (community detection) algorithms considering overlaps (covers).
  • ParallelComMetric - A parallel toolkit implemented with Pthreads (or MPI) to calculate various extrinsic and intrinsic quality metrics (with and without ground truth community structure) for non-overlapping (hard, single membership) clusterings.
  • CluSim - A Python module that evaluates (slowly) various extrinsic quality metrics (accuracy) for non-overlapping (hard, single membership) clusterings.
  • resmerge - Resolution levels clustering merger with filtering. Flattens hierarchy/list of multiple resolutions levels (clusterings) into the single flat clustering with clusters on various resolution levels synchronizing the node base.
  • ExecTime - A lightweight resource consumption profiler.
  • TInfES - Type inference evaluation scripts and accessory apps used for the benchmarking.