scikit-learn · kathyxchen · Oct 12, 2016 · Oct 13, 2016 · Oct 13, 2016 · Oct 19, 2016
diff --git a/doc/modules/model_evaluation.rst b/doc/modules/model_evaluation.rst
@@ -252,15 +252,16 @@ Some also work in the multilabel case:
    precision_recall_fscore_support
    precision_score
    recall_score
+   roc_auc_score
    zero_one_loss
 
-And some work with binary and multilabel (but not multiclass) problems:
+
+Some work with binary and multilabel (but not multiclass) problems:
 
 .. autosummary::
    :template: function.rst
 
    average_precision_score
-   roc_auc_score
 
 
 In the following sub-sections, we will describe each of those functions,
@@ -976,10 +977,41 @@ In multi-label classification, the :func:`roc_auc_score` function is
 extended by averaging over the labels as :ref:`above <average>`.
 
 Compared to metrics such as the subset accuracy, the Hamming loss, or the
-F1 score, ROC doesn't require optimizing a threshold for each label. The
-:func:`roc_auc_score` function can also be used in multi-class classification,
-if the predicted outputs have been binarized.
+F1 score, ROC doesn't require optimizing a threshold for each label.
+
+The :func:`roc_auc_score` function can also be used in multi-class
+classification. [F2009]_ Two averaging strategies are currently supported: the
+one-vs-one algorithm computes the average of the pairwise
+ROC AUC scores, and the one-vs-rest algorithm
+computes the average of the ROC AUC scores for each class against
+all other classes. In both cases, the predicted class labels are provided in
+an array with values from 0 to ``n_classes``, and the scores correspond to the
+probability estimates that a sample belongs to a particular class.
+
+**One-vs-one Algorithm**
+The AUC of each class against each other, computing
+the AUC of all possible pairwise combinations :math:`c(c-1)` for a
+:math:`c`-dimensional classifier.
+
+[HT2001]_ Using the uniform class distribution:
+
+.. math:: \frac{1}{c(c-1)}\sum_{j=1}^c\sum_{k \neq j}^c \textnormal{AUC}(j, k)
+
+[F2009]_ Weighted by the prevalence of classes `j` and `k`:
+
+.. math:: \frac{1}{c-1}\sum_{j=1}^c\sum_{k \neq j}^c p(j \cup k)\textnormal{AUC}(j, k)
 
+**One-vs-rest Algorithm**
+AUC of each class against the rest. This treats
+a :math:`c`-dimensional classifier as :math:`c` two-dimensional classifiers.
+
+[F2006]_ Using the uniform class distribution:
+
+.. math:: \frac{\sum_{j=1}^c \textnormal{AUC}(j, \textnormal{rest}_j)}{c}
+
+[F2001]_ Weighted by the a priori class distribution:
+
+.. math:: \frac{\sum_{j=1}^c p(j)\textnormal{AUC}(j, \textnormal{rest}_j)}{c}
 
 .. image:: ../auto_examples/model_selection/images/sphx_glr_plot_roc_002.png
    :target: ../auto_examples/model_selection/plot_roc.html
@@ -1000,6 +1032,24 @@ if the predicted outputs have been binarized.
     for an example of using ROC to
     model species distribution.
 
+.. topic:: References:
+
+    .. [F2001] Fawcett, T., 2001. `Using rule sets to maximize 
+       ROC performance <http://ieeexplore.ieee.org/document/989510/>`_
+       In Data Mining, 2001.
+       Proceedings IEEE International Conference, pp. 131-138.
+    .. [F2006] Fawcett, T., 2006. `An introduction to ROC analysis.
+       <http://www.sciencedirect.com/science/article/pii/S016786550500303X>`_
+       Pattern Recognition Letters, 27(8), pp. 861-874.
+    .. [F2009] Ferri, C., Hernandez-Orallo, J., and Modroiu, R., 2009.
+       `An experimental comparison of performance measures for classification.
+       <http://www.sciencedirect.com/science/article/pii/S0167865508002687>`_
+       Pattern Recognition Letters, 30(1), pp. 27-38.
+    .. [HT2001] Hand, D.J. and Till, R.J., 2001. `A simple generalisation
+       of the area under the ROC curve for multiple class classification problems.
+       <http://link.springer.com/article/10.1023/A:1010920819831>`_
+       Machine learning, 45(2), pp.171-186.
+
 .. _zero_one_loss:
 
 Zero one loss

diff --git a/examples/model_selection/plot_roc.py b/examples/model_selection/plot_roc.py
@@ -19,16 +19,39 @@
 -------------------
 
 ROC curves are typically used in binary classification to study the output of
-a classifier. In order to extend ROC curve and ROC area to multi-class
-or multi-label classification, it is necessary to binarize the output. One ROC
-curve can be drawn per label, but one can also draw a ROC curve by considering
+a classifier. Extensions of ROC curve and ROC area to multi-class
+or multi-label classification can use the One-vs-Rest or One-vs-One scheme.
+
+One-vs-Rest
+-----------
+
+The output is binarized and one ROC curve is drawn per label,
+where label is set to be the positive class and all other labels (the "rest")
+are considered the negative class.
+
+The ROC area can be approximated by taking the average--unweighted or weighted
+by the a priori class distribution--of the one-vs-rest ROC areas.
+
+One can also draw a ROC curve by considering
 each element of the label indicator matrix as a binary prediction
 (micro-averaging).
 
-Another evaluation measure for multi-class classification is
+Another evaluation measure for one-vs-rest multi-class classification is
 macro-averaging, which gives equal weight to the classification of each
 label.
 
+One-vs-One
+----------
+
+Two ROC curves can be drawn per pair of labels because either of the two
+labels can be considered the positive class (and the other the negative
+class). The ROC area of a label pair is approximated taking the average of
+these two ROC AUC scores.
+
+The One-vs-One approximation of a multi-class ROC AUC score is the average--
+unweighted or weighted by class prevalence--across all of the pairwise
+approximate ROC AUC scores.
+
 .. note::
 
     See also :func:`sklearn.metrics.roc_auc_score`,
@@ -39,10 +62,10 @@
 
 import numpy as np
 import matplotlib.pyplot as plt
-from itertools import cycle
+from itertools import combinations, cycle
 
 from sklearn import svm, datasets
-from sklearn.metrics import roc_curve, auc
+from sklearn.metrics import roc_curve, auc, roc_auc_score
 from sklearn.model_selection import train_test_split
 from sklearn.preprocessing import label_binarize
 from sklearn.multiclass import OneVsRestClassifier
@@ -53,9 +76,8 @@
 X = iris.data
 y = iris.target
 
-# Binarize the output
-y = label_binarize(y, classes=[0, 1, 2])
-n_classes = y.shape[1]
+classes = np.unique(y)
+n_classes = len(classes)
 
 # Add noisy features to make the problem harder
 random_state = np.random.RandomState(0)
@@ -72,17 +94,17 @@
 y_score = classifier.fit(X_train, y_train).decision_function(X_test)
 
 # Compute ROC curve and ROC area for each class
+
+# Binarize y_test to compute the ROC curve
+y_test_binarized = label_binarize(y_test, classes=classes)
+
 fpr = dict()
 tpr = dict()
 roc_auc = dict()
 for i in range(n_classes):
-    fpr[i], tpr[i], _ = roc_curve(y_test[:, i], y_score[:, i])
+    fpr[i], tpr[i], _ = roc_curve(y_test_binarized[:, i], y_score[:, i])
     roc_auc[i] = auc(fpr[i], tpr[i])
 
-# Compute micro-average ROC curve and ROC area
-fpr["micro"], tpr["micro"], _ = roc_curve(y_test.ravel(), y_score.ravel())
-roc_auc["micro"] = auc(fpr["micro"], tpr["micro"])
-
 
 ##############################################################################
 # Plot of a ROC curve for a specific class
@@ -101,7 +123,12 @@
 
 
 ##############################################################################
-# Plot ROC curves for the multiclass problem
+# Plot ROC curves for the multiclass problem using One vs. Rest classification.
+
+# Compute micro-average ROC curve and ROC area
+fpr["micro"], tpr["micro"], _ = roc_curve(
+    y_test_binarized.ravel(), y_score.ravel())
+roc_auc["micro"] = auc(fpr["micro"], tpr["micro"])
 
 # Compute macro-average ROC curve and ROC area
 
@@ -143,6 +170,63 @@
 plt.ylim([0.0, 1.05])
 plt.xlabel('False Positive Rate')
 plt.ylabel('True Positive Rate')
-plt.title('Some extension of Receiver operating characteristic to multi-class')
+plt.title('An extension of ROC to multi-class '
+          'using One-vs-Rest')
 plt.legend(loc="lower right")
 plt.show()
+
+# Compute the One-vs-Rest ROC AUC score, weighted and unweighted
+unweighted_roc_auc_ovr = roc_auc_score(y_test, y_score, multiclass="ovr")
+weighted_roc_auc_ovr = roc_auc_score(
+    y_test, y_score, multiclass="ovr", average="weighted")
+print("One-vs-Rest ROC AUC scores: {0} (unweighted), {1} (weighted)".format(
+      unweighted_roc_auc_ovr, weighted_roc_auc_ovr))
+
+##############################################################################
+# Plot ROC curves for the multiclass problem using One vs. One classification.
+
+for a, b in combinations(range(n_classes), 2):
+    # Filter `y_test` and `y_score` to only consider the current
+    # `a` and `b` class pair.
+    ab_mask = np.logical_or(y_test == a, y_test == b)
+    y_true_filtered = y_test[ab_mask]
+    y_score_filtered = y_score[ab_mask]
+
+    # Compute ROC curve and ROC area with `a` as the positive class
+    class_a = y_true_filtered == a
+    fpr[(a, b)], tpr[(a, b)], _ = roc_curve(
+        class_a, y_score_filtered[:, a])
+    roc_auc[(a, b)] = auc(fpr[(a, b)], tpr[(a, b)])
+
+    # Compute ROC curve and ROC area with `b` as the positive class
+    class_b = y_true_filtered == b
+    fpr[(b, a)], tpr[(b, a)], _ = roc_curve(
+        class_b, y_score_filtered[:, b])
+    roc_auc[(b, a)] = auc(fpr[(b, a)], tpr[(b, a)])
+
+plt.figure()
+for a, b in combinations(range(n_classes), 2):
+    plt.plot(fpr[(a, b)], tpr[(a, b)], lw=lw,
+             label='ROC curve: class {0} vs. {1} '
+                   '(area = {2:0.2f})'.format(
+        a, b, roc_auc[(a, b)]))
+    plt.plot(fpr[(b, a)], tpr[(b, a)], lw=lw,
+             label='ROC curve: class {0} vs. {1} '
+                   '(area = {2:0.2f})'.format(
+        b, a, roc_auc[(b, a)]))
+plt.plot([0, 1], [0, 1], 'k--', lw=lw)
+plt.xlim([0.0, 1.0])
+plt.ylim([0.0, 1.05])
+plt.xlabel('False Positive Rate')
+plt.ylabel('True Positive Rate')
+plt.title('An extension of ROC to multi-class '
+          'using One-vs-One')
+plt.legend(bbox_to_anchor=(1.1, 0.30))
+plt.show()
+
+# Compute the One-vs-One ROC AUC score, weighted and unweighted
+unweighted_roc_auc_ovo = roc_auc_score(y_test, y_score, multiclass="ovo")
+weighted_roc_auc_ovo = roc_auc_score(
+    y_test, y_score, multiclass="ovo", average="weighted")
+print("One-vs-One ROC AUC scores: {0} (unweighted), {1} (weighted)".format(
+      unweighted_roc_auc_ovo, weighted_roc_auc_ovo))
diff --git a/sklearn/metrics/base.py b/sklearn/metrics/base.py
@@ -13,6 +13,7 @@
 # License: BSD 3 clause
 
 from __future__ import division
+import itertools
 
 import numpy as np
 
@@ -131,3 +132,69 @@ def _average_binary_score(binary_metric, y_true, y_score, average,
         return np.average(score, weights=average_weight)
     else:
         return score
+
+
+def _average_multiclass_ovo_score(binary_metric, y_true, y_score, average):
+    """Uses the binary metric for one-vs-one multiclass classification,
+    where the score is computed according to the Hand & Till (2001) algorithm.
+
+    Parameters
+    ----------
+    y_true : array, shape = [n_samples]
+        True multiclass labels.
+        Assumes labels have been recoded to 0 to n_classes.
+
+    y_score : array, shape = [n_samples, n_classes]
+        Target scores corresponding to probability estimates of a sample
+        belonging to a particular class
+
+    average : 'macro' or 'weighted', default='macro'
+        ``'macro'``:
+            Calculate metrics for each label, and find their unweighted
+            mean. This does not take label imbalance into account. Classes
+            are assumed to be uniformly distributed.
+        ``'weighted'``:
+            Calculate metrics for each label, taking into account the a priori
+            distribution of the classes.
+
+    binary_metric : callable, the binary metric function to use.
+        Accepts the following as input
+            y_true_target : array, shape = [n_samples_target]
+                Some sub-array of y_true for a pair of classes designated
+                positive and negative in the one-vs-one scheme.
+            y_score_target : array, shape = [n_samples_target]
+                Scores corresponding to the probability estimates
+                of a sample belonging to the designated positive class label
+
+    Returns
+    -------
+    score : float
+        Average the sum of pairwise binary metric scores
+    """
+    n_classes = len(np.unique(y_true))
+    n_pairs = n_classes * (n_classes - 1) // 2
+    prevalence = np.empty(n_pairs)
+    pair_scores = np.empty(n_pairs)
+
+    ix = 0
+    for a, b in itertools.combinations(range(n_classes), 2):
+        a_mask = y_true == a
+        ab_mask = np.logical_or(a_mask, y_true == b)
+
+        prevalence[ix] = np.sum(ab_mask) / len(y_true)
+
+        y_score_filtered = y_score[ab_mask]
+
+        a_true = a_mask[ab_mask]
+        b_true = np.logical_not(a_true)
+
+        a_true_score = binary_metric(
+                a_true, y_score_filtered[:, a])
+        b_true_score = binary_metric(
+                b_true, y_score_filtered[:, b])
+        binary_avg_score = (a_true_score + b_true_score) / 2
+        pair_scores[ix] = binary_avg_score
+
+        ix += 1
+    return (np.average(pair_scores, weights=prevalence)
+            if average == "weighted" else np.average(pair_scores))