<commit_before>"""

Motivation
----------

The original motivation behind the given re-implementation of some clustering
metrics was to avoid the high memory usage of equivalent methods in
Scikit-Learn.  The Scikit-Learn implementations create an incidence matrix for
computation of these metrics resulting in O(n^2) memory usage, something that is
felt particularly strongly on large data sets and in multiprocessing environment
where each child process runnning on a multicore machine tries to allocate
memory for itself. This implementation uses sparse methods on dictionary maps
instead of building incidence matrices.

Secondly, it was interesting to investigate the type of confusion matrices
typically produced during pairwise cluster comparisons, and whether it has
any implications on the choice of overall quality measure. For example,
if sampled from a random pool of 500,000 clusterings, the following gives the
lowest Matthews' correlation coefficient (MCC) value:

>>> ltrue = [2, 2, 1, 2, 1, 1, 1, 4, 1, 1, 0, 1, 3, 1, 3]
>>> lpred = [5, 5, 2, 3, 0, 5, 3, 5, 4, 5, 5, 3, 5, 1, 3]

>>> cm = ClusteringMetrics.from_labels(ltrue, lpred)
>>> conf = cm.confusion_matrix_
>>> conf.as_tuple_ccw()
ConfMatCCW(TP=3.0, FP=24.0, TN=49.0, FN=29.0)

>>> mcc = conf.matthews_corr()
>>> round(mcc, 4)
-0.2475

Thridly, an attempt is made to provide a mutual information-based set of
correlation coefficients that can serve as an alternative to Cohen's Kappa
or MCC.


Why G-score
------------

G is a likelihood-ratio statistic and therefore should
be superior to chi-squre based statistics which rely on Taylor approximation of
likelihood. One direct benefit is that G statistic is additive while chi-square
is not. Simulation studies showed [4, 5] that G score outperforms Chi-square on
highly skewed tables used for word bigram collocations.


Validation vs Replication Studies, ARI, and Kappa
-------------------------------------------------

ARI has an equivalence to Cohen's Kappa described in [1].  Milligan [2]
suggested that the two measures (ARI and Kappa) be used in replication studies
when relevant. Note that replication studies like the ones proposed in [2]
correspond to Model I test for independence as described in [3]. In a Model I
study, random sampling occurs both row- and column-wise, and only the grand
total is fixed.  In a Model II study, one side (either row or column totals) is
fixed.  Simulation-based clustering evaluations that fix the number and size of
ground truth classes belong to Model II category. Finally, in a Model III study,
both rows and column totals are fixed. Model III studies require careful
experimental design but have potentially more discriminative power. An example
of a Model III study would be a tea tasting party (to follow Fisher's classic
example) where both the true class totals (the portion and number of tea cups
with milk poured first) are known and the respondees are told ahead of time,
that, for example, 50% of cups they will encounter have had milk poured first.

To sum up the above, in a replication study where two clusterings are compared
that were both created by the same algorithm, the Kappa score seems to be an
appropriate metric (it is independent of row/column assignemnts).
The same applies to Matthew's Correlation Coefficient. However it
seems that a better chance-corrected metric should exist that would be
appropriate for Model II studies where the true class portions are fixed.

To be exhaustive, a Model O study would be one where even the grand total is not
fixed. An example would be an astronomy study that, for example, tests a
hypothesis about a generalizable property such as dark matter content by looking
at all galaxies in the Local Group, and the researchers obviously don't get to
choose ahead of time how many galaxies there are near ours.

References
----------

[1] <NAME>. On the equivalence of Cohen's Kappa and the Hubert-Arabie
Adjusted Rand Index. 2008. J. Classif. 25: 177-183.
https://doi.org/10.1007/s00357-008-9023-7

[2] <NAME>. Clustering validation: results and implications for applied
analysis. In Arabie P., de <NAME>. (ed) Clustering and Classification, 1996:
358-369.  https://doi.org/10.1142/9789812832153_0010

[3] <NAME>. Biometry. <NAME> & Co. New York, 2012.  4th
ed. pp 742-744.

[4] <NAME>. Accurate methods for the statisitcs of surprise and coincidence.
1993. Computational Linguistics 19 (1). 61-74.
http://dl.acm.org/citation.cfm?id=972454

[5] Ted Dunning's personal blog
http://tdunning.blogspot.com/2008/03/surprise-and-coincidence.html

"""

import numpy as np
from math import log as logn, sqrt, copysign
from collections import defaultdict, Counter, Mapping, Set, namedtuple
from itertools import izip, chain
from operator import itemgetter, mul<commit_msg>citations<commit_after>"""

Motivation
----------

The original motivation behind the given re-implementation of some clustering
metrics was to avoid the high memory usage of equivalent methods in
Scikit-Learn.  The Scikit-Learn implementations create an incidence matrix for
computation of these metrics resulting in O(n^2) memory usage, something that is
felt particularly strongly on large data sets and in multiprocessing environment
where each child process runnning on a multicore machine tries to allocate
memory for itself. This implementation uses sparse methods on dictionary maps
instead of building incidence matrices.

Secondly, it was interesting to investigate the type of confusion matrices
typically produced during pairwise cluster comparisons, and whether it has
any implications on the choice of overall quality measure. For example,
if sampled from a random pool of 500,000 clusterings, the following gives the
lowest Matthews' correlation coefficient (MCC) value:

>>> ltrue = [2, 2, 1, 2, 1, 1, 1, 4, 1, 1, 0, 1, 3, 1, 3]
>>> lpred = [5, 5, 2, 3, 0, 5, 3, 5, 4, 5, 5, 3, 5, 1, 3]

>>> cm = ClusteringMetrics.from_labels(ltrue, lpred)
>>> conf = cm.confusion_matrix_
>>> conf.as_tuple_ccw()
ConfMatCCW(TP=3.0, FP=24.0, TN=49.0, FN=29.0)

>>> mcc = conf.matthews_corr()
>>> round(mcc, 4)
-0.2475

Thridly, an attempt is made to provide a mutual information-based set of
correlation coefficients that can serve as an alternative to Cohen's Kappa
or MCC. The coefficient is similar to the one described in [0], however it is
normalized to its maximum value and decomposed into two regression components.


Why G-score
------------

G is a likelihood-ratio statistic and therefore should
be superior to chi-squre based statistics which rely on Taylor approximation of
likelihood. One direct benefit is that G statistic is additive while chi-square
is not. Simulation studies showed [4, 5] that G score outperforms Chi-square on
highly skewed tables used for word bigram collocations.


Validation vs Replication Studies, ARI, and Kappa
-------------------------------------------------

ARI has an equivalence to Cohen's Kappa described in [1].  Milligan [2]
suggested that the two measures (ARI and Kappa) be used in replication studies
when relevant. Note that replication studies like the ones proposed in [2]
correspond to Model I test for independence as described in [3]. In a Model I
study, random sampling occurs both row- and column-wise, and only the grand
total is fixed.  In a Model II study, one side (either row or column totals) is
fixed.  Simulation-based clustering evaluations that fix the number and size of
ground truth classes belong to Model II category. Finally, in a Model III study,
both rows and column totals are fixed. Model III studies require careful
experimental design but have potentially more discriminative power. An example
of a Model III study would be a tea tasting party (to follow Fisher's classic
example) where both the true class totals (the portion and number of tea cups
with milk poured first) are known and the respondees are told ahead of time,
that, for example, 50% of cups they will encounter have had milk poured first.

To sum up the above, in a replication study where two clusterings are compared
that were both created by the same algorithm, the Kappa score seems to be an
appropriate metric (it is independent of row/column assignemnts).
The same applies to Matthew's Correlation Coefficient. However it
seems that a better chance-corrected metric should exist that would be
appropriate for Model II studies where the true class portions are fixed.

To be exhaustive, a Model O study would be one where even the grand total is not
fixed. An example would be an astronomy study that, for example, tests a
hypothesis about a generalizable property such as dark matter content by looking
at all galaxies in the Local Group, and the researchers obviously don't get to
choose ahead of time how many galaxies there are near ours.

References
----------

[0] <NAME>., & <NAME>. (2013). Comparing measures of association in
2x2 probability tables. arXiv preprint arXiv:1302.6161.
http://arxiv.org/pdf/1302.6161v1.pdf

[1] <NAME>. (2008). On the equivalence of Cohen's kappa and the
Hubert-Arabie adjusted Rand index. Journal of Classification, 25(2), 177-183.
https://doi.org/10.1007/s00357-008-9023-7

[2] <NAME>., <NAME>., & <NAME>. (1996). Clustering validation:
results and implications for applied analyses (p. 341). World Scientific Pub Co
Inc.  Chicago	https://doi.org/10.1142/9789812832153_0010

[3] <NAME>., & <NAME>. (2012). Biometry (4th edn). pp 742-744.

[4] <NAME>. (1993). Accurate methods for the statistics of surprise and
coincidence. Computational linguistics, 19(1), 61-74.
http://dl.acm.org/citation.cfm?id=972454

[5] Ted Dunning's personal blog
http://tdunning.blogspot.com/2008/03/surprise-and-coincidence.html

"""

import numpy as np
from math import log as logn, sqrt, copysign
from collections import defaultdict, Counter, Mapping, Set, namedtuple
from itertools import izip, chain
from operator import itemgetter, mul
{'fraction_non_alphanumeric': 0.08044004844570045, 'fraction_numerical': 0.035627775534921274, 'mean_word_length': 4.190675746464118, 'pattern_counts': {'":': 0, '<': 18, '<?xml version=': 0, '>': 60, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2803321', 'n_tokens_mistral': 3017, 'n_tokens_neox': 2614, 'n_words': 1432}