Algorithme efficace pour calculer la courbe ROC d'un classificateur composé d'un ensemble de classificateurs disjoints

Supposons que j'ai des classificateurs C_1 ... C_n qui sont disjoints dans le sens où aucun ne retournera vrai sur la même entrée (par exemple les nœuds dans un arbre de décision). Je veux construire un nouveau classificateur qui est l'union d'un sous-ensemble de ceux-ci (par exemple, je veux décider quelles feuilles d'un arbre de décision donner une classification positive). Bien sûr, ce faisant, il y aura un compromis entre la sensibilité et la valeur prédictive positive. Je voudrais donc voir une courbe ROC. En principe, je pourrais le faire en énumérant tous les sous-ensembles des classificateurs et en calculant la sensibilité et le PPV résultants. Cependant, cela est prohibitif si n est supérieur à 30 environ. D'un autre côté, il existe presque certainement des combinaisons qui ne sont pas optimales pour Pareto, il peut donc y avoir une stratégie de branche et de limite, ou quelque chose,

Je voudrais savoir si cette approche est susceptible d'être fructueuse et s'il y a du travail ou si vous avez des idées sur le calcul efficace de la courbe ROC dans la situation ci-dessus.

$N$$1$$0$ au reste d'entre eux. Et au-dessus de ces sous-ensembles, vous voulez trouver ceux pareto-optimaux, c'est-à-dire ceux qui maximisent le vrai taux positif étant donné un nombre fixe de prédictions positives (cela équivaut à fixer PPV). Est-ce correct?

Cela ressemble beaucoup à un problème de sac à dos ! Les tailles de grappe sont des "poids" et le nombre d'échantillons positifs dans une grappe sont des "valeurs", et vous souhaitez remplir votre sac à dos de capacité fixe avec autant de valeur que possible.

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

$1$$k-1$$p\in[0,1]$$k$ du problème du sac à dos. Avec cela, vous pouvez dessiner la limite supérieure de votre courbe ROC.

Voici un exemple de 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();

Ce code dessinera une belle image pour vous:

$2^{10}$

Et maintenant, le peu de sel: vous n'avez pas du tout à vous soucier des sous-ensembles ! Ce que j'ai fait, c'est trier les feuilles des arbres en fonction de la fraction d'échantillons positifs dans chacune. Mais ce que j'ai obtenu est exactement la courbe ROC pour la prédiction probabiliste de l'arbre. Cela signifie que vous ne pouvez pas surpasser l'arbre en cueillant à la main ses feuilles en fonction des fréquences cibles dans l'ensemble d'entraînement.

Vous pouvez vous détendre et continuer à utiliser la prédiction probabiliste ordinaire :)

Je pourrais vous suggérer d'utiliser des méthodes gourmandes. Donnez un classificateur pour commencer, vous inclurez le classificateur qui permet à l'ensemble d'obtenir la meilleure amélioration de performance. Si aucune amélioration ne peut être obtenue, incluez plus de classificateurs, puis arrêtez. Vous commencerez par tous les classificateurs. La complexité sera au maximum N * N.

J'ai une autre question, que voulez-vous dire par "Pareto optimal", surtout dans votre contexte? J'ai trouvé sur wiki cette explication, https://en.wikipedia.org/wiki/Pareto_efficiency

grâce à la réaffectation, des améliorations peuvent être apportées au bien-être d'au moins un participant sans réduire le bien-être d'un autre participant.

L'amélioration de l'efficacité de Pareto concerne chaque participant, ce qui peut correspondre à chaque classificateur. Comment définissez-vous l'amélioration par rapport à un classifieur?