Эффективный алгоритм для вычисления кривой ROC для классификатора, состоящего из множества непересекающихся классификаторов

Предположим, у меня есть классификаторы C_1 ... C_n, которые не пересекаются в том смысле, что никакие два не вернут истину на одном входе (например, узлы в дереве решений). Я хочу создать новый классификатор, который объединяет некоторые их подмножества (например, я хочу решить, какие листья дерева решений дать положительную классификацию). Конечно, при этом будет достигнут компромисс между чувствительностью и положительной прогностической ценностью. Поэтому я хотел бы видеть кривую ROC. В принципе, я мог бы сделать это путем перечисления всех подмножеств классификаторов и вычисления результирующей чувствительности и PPV. Однако это непомерно дорого, если n больше 30 или около того. С другой стороны, почти наверняка есть некоторые комбинации, которые не являются оптимальными по Парето, поэтому может быть какая-то стратегия ветвления и ограничения или что-то в этом роде,

Я хотел бы получить совет о том, будет ли этот подход плодотворным и есть ли какая-либо работа или есть ли у вас какие-либо идеи относительно эффективного вычисления кривой ROC в описанной выше ситуации.

$N$$1$$0$

Это очень похоже на проблему с рюкзаком ! Размеры кластера - это «веса», а количество положительных выборок в кластере - это «значения», и вы хотите наполнить свой рюкзак фиксированной емкости как можно большим значением.

$\frac{value}{weight}$$k$$k$$0$$N$

$1$$k-1$$p\in[0,1]$$k$

Вот пример Python:

import numpy as np
from itertools import combinations, chain
import matplotlib.pyplot as plt
np.random.seed(1)
n_obs = 1000
n = 10

# generate clusters as indices of tree leaves
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_classification
from sklearn.model_selection import cross_val_predict
X, target = make_classification(n_samples=n_obs)
raw_clusters = DecisionTreeClassifier(max_leaf_nodes=n).fit(X, target).apply(X)
recoding = {x:i for i, x in enumerate(np.unique(raw_clusters))}
clusters = np.array([recoding[x] for x in raw_clusters])

def powerset(xs):
    """ Get set of all subsets """
    return chain.from_iterable(combinations(xs,n) for n in range(len(xs)+1))

def subset_to_metrics(subset, clusters, target):
    """ Calculate TPR and FPR for a subset of clusters """
    prediction = np.zeros(n_obs)
    prediction[np.isin(clusters, subset)] = 1
    tpr = sum(target*prediction) / sum(target) if sum(target) > 0 else 1
    fpr = sum((1-target)*prediction) / sum(1-target) if sum(1-target) > 0 else 1
    return fpr, tpr

# evaluate all subsets
all_tpr = []
all_fpr = []
for subset in powerset(range(n)):
    tpr, fpr = subset_to_metrics(subset, clusters, target)
    all_tpr.append(tpr)
    all_fpr.append(fpr)

# evaluate only the upper bound, using knapsack greedy solution
ratios = [target[clusters==i].mean() for i in range(n)]
order = np.argsort(ratios)[::-1]
new_tpr = []
new_fpr = []
for i in range(n):
    subset = order[0:(i+1)]
    tpr, fpr = subset_to_metrics(subset, clusters, target)
    new_tpr.append(tpr)
    new_fpr.append(fpr)

plt.figure(figsize=(5,5))
plt.scatter(all_tpr, all_fpr, s=3)
plt.plot(new_tpr, new_fpr, c='red', lw=1)
plt.xlabel('TPR')
plt.ylabel('FPR')
plt.title('All and Pareto-optimal subsets')
plt.show();

Этот код нарисует красивую картинку для вас:

$2^{10}$

А теперь немного соли: вам совсем не нужно было беспокоиться о подмножествах ! Я отсортировал листья деревьев по доле положительных образцов в каждом. Но то, что я получил, это точно кривая ROC для вероятностного предсказания дерева. Это означает, что вы не можете превзойти дерево, вручную подбирая его листья на основе целевых частот в тренировочном наборе.

Вы можете расслабиться и продолжать использовать обычный вероятностный прогноз :)

Я мог бы предложить вам использовать жадные методы. Дайте классификатору для начала, вы включите классификатор, который заставит ансамбль получить лучшее улучшение производительности. Если нельзя добиться улучшения, включите больше классификаторов, затем остановитесь. Вы начнете с каждого классификатора. Сложность будет не более N * N.

У меня есть еще один вопрос: что вы подразумеваете под «оптимальным по Парето», особенно в вашем контексте? Я нашел в вики это объяснение, https://en.wikipedia.org/wiki/Pareto_efficiency

с помощью перераспределения могут быть сделаны улучшения, по крайней мере, для благополучия одного участника без снижения благосостояния любого другого участника.

Повышение эффективности Парето касается каждого участника, который может соответствовать каждому классификатору. Как вы определяете улучшение по одному классификатору?