Wydajny algorytm do obliczania krzywej ROC dla klasyfikatora składającego się z zestawu rozłącznych klasyfikatorów

Załóżmy, że mam klasyfikatory C_1 ... C_n, które są rozłączne w tym sensie, że żadne dwa nie zwrócą wartości true na tym samym wejściu (np. Węzły w drzewie decyzyjnym). Chcę zbudować nowy klasyfikator, który jest połączeniem niektórych jego podzbiorów (np. Chcę zdecydować, które liście drzewa decyzyjnego dają pozytywną klasyfikację). Oczywiście w ten sposób nastąpi kompromis między wrażliwością a pozytywną wartością predykcyjną. Chciałbym więc zobaczyć krzywą ROC. Zasadniczo mógłbym to zrobić, wyliczając wszystkie podzbiory klasyfikatorów i obliczając wynikową czułość i PPV. Jest to jednak zbyt drogie, jeśli n jest większe niż około 30. Z drugiej strony prawie na pewno istnieją pewne kombinacje, które nie są optymalne dla Pareto, więc może istnieć jakaś strategia rozgałęziona i powiązana, czy coś,

Chciałbym uzyskać porady na temat tego, czy to podejście może być owocne i czy jest jakaś praca lub czy masz jakieś pomysły na temat skutecznego obliczania krzywej ROC w powyższej sytuacji.

Jeśli dobrze zrozumiałem pytanie, nauczyłeś się algorytmu, który dzieli twoje dane na rozłącznych klastrów. Teraz chcesz przypisać predykcję 1 do niektórych podzbiorów klastrów, a 0 do pozostałych. A wśród tych podzbiorów chcesz znaleźć te optymalne dla pareto, tj. Takie, które maksymalizują prawdziwy współczynnik dodatni, biorąc pod uwagę stałą liczbę pozytywnych prognoz (jest to równoważne z ustaleniem PPV). Czy to jest poprawne?$N$$1$$0$

To brzmi jak problem z plecakiem ! Rozmiary klastra to „wagi”, a liczba próbek dodatnich w klastrze to „wartości”, a Ty chcesz wypełnić swój plecak o stałej pojemności możliwie największą wartością.

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

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

Oto przykład 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();

Ten kod narysuje dla Ciebie ładne zdjęcie:

$2^{10}$

A teraz odrobina soli: wcale nie musiałeś przejmować się podzbiorami ! To, co zrobiłem, to posortowanie liści drzew według ułamka próbek pozytywnych w każdym z nich. Ale otrzymałem właśnie krzywą ROC do probabilistycznego przewidywania drzewa. Oznacza to, że nie można przewyższyć drzewa, wybierając ręcznie liście na podstawie częstotliwości docelowych w zestawie treningowym.

Możesz się zrelaksować i nadal używać zwykłych prognoz probabilistycznych :)

Mogę zasugerować, że używasz chciwych metod. Daj klasyfikatorowi na początek, obejmiesz klasyfikator, dzięki któremu zespół uzyska najlepszą poprawę wydajności. Jeśli nie można uzyskać poprawy obejmującej więcej klasyfikatorów, to przestań. Zaczniesz od każdego klasyfikatora. Złożoność będzie wynosić co najwyżej N * N.

Mam jeszcze jedno pytanie, co rozumiesz przez „optymalne Pareto”, szczególnie w twoim kontekście? Znalazłem z wiki to wyjaśnienie, https://en.wikipedia.org/wiki/Pareto_fficiency

poprzez realokację, można dokonać poprawy dobrostanu przynajmniej jednego uczestnika bez zmniejszania dobrostanu innego uczestnika.

Poprawa wydajności Pareto dotyczy każdego uczestnika, co może odpowiadać każdemu klasyfikatorowi. Jak zdefiniujesz poprawę w stosunku do jednego klasyfikatora?