Algoritmo eficiente para calcular a curva ROC de um classificador que consiste em um conjunto de classificadores disjuntos

13

Suponha que eu tenha os classificadores C_1 ... C_n disjuntos, no sentido de que nenhum dois retornará verdadeiro na mesma entrada (por exemplo, os nós em uma árvore de decisão). Eu quero construir um novo classificador que seja a união de alguns subconjuntos deles (por exemplo, eu quero decidir quais folhas de uma árvore de decisão darão uma classificação positiva). Obviamente, ao fazer isso, haverá uma troca entre sensibilidade e valor preditivo positivo. Então, eu gostaria de ver uma curva ROC. Em princípio, eu poderia fazer isso enumerando todos os subconjuntos dos classificadores e calculando a sensibilidade e o PPV resultantes. No entanto, isso é proibitivamente caro se n for superior a 30 ou mais. Por outro lado, há quase certamente algumas combinações que não são ideais de Pareto, portanto, pode haver alguma estratégia de ramificação e limite, ou algo assim,

Eu gostaria de receber conselhos sobre se essa abordagem provavelmente será proveitosa e se existe algum trabalho ou se você tem alguma idéia sobre como calcular com eficiência a curva ROC na situação acima.

Josh Brown Kramer
fonte
Você está classificando cada caso de entrada como verdadeiro ou falso?
Image_doctor 26/08/15
@image_doctor: yes
Josh Brown Kramer
Não estou claro "... que são disjuntos no sentido de que não haverá dois retornando verdadeiros na mesma entrada ..." e você está classificando em uma saída binária, como pode ter mais de dois classificadores no seu conjunto, provavelmente estou faltando alguma coisa?
image_doctor
@image_doctor: Você pode estar pensando que estou dizendo que não há dois classificadores retornando a mesma saída na mesma entrada. Estou dizendo que não haverá dois retornando verdade. Ambos podem retornar falso.
Josh Brown Kramer
1
Talvez este artigo sobre uma maneira teoricamente ideal de combinar classificadores para ROC (ou documentos que o citam) possa ajudá-lo a entender o estado da arte: M. Barreno, A. Cardenas, JD Tygar, curva ROC ideal para uma combinação de classificadores, Avanços nos sistemas de processamento de informações neurais, 2008.
Valentas 29/10

Respostas:

1

Se entendi a pergunta corretamente, você treinou um algoritmo que divide seus dados em clusters disjuntos. Agora você deseja atribuir a previsão 1 a algum subconjunto dos clusters e 0 ao restante deles. E entre esses subconjuntos, você deseja encontrar os pareto-ótimos, ou seja, aqueles que maximizam a taxa positiva verdadeira, dado um número fixo de previsões positivas (isso é equivalente à fixação do PPV). Está correto?N10 0

Isso parece muito com o problema da mochila ! Os tamanhos de cluster são "pesos" e o número de amostras positivas em um cluster é "valores", e você deseja encher sua mochila de capacidade fixa com o máximo de valor possível.

O problema da mochila possui vários algoritmos para encontrar soluções exatas (por exemplo, por programação dinâmica). Mas uma solução gananciosa útil é classificar seus clusters em ordem decrescente de (ou seja, compartilhamento de amostras positivas) e pegue o primeirok. Se você levarkde0aN, poderá fazer um croqui muito barato da sua curva ROC.vumaeuvocêeWeEughtkk0 0N

E se você atribuir aos primeiros clusters k - 1 e à fração aleatória p [ 0 , 1 ] de amostras no k- ésimo cluster, obterá o limite superior para o problema da mochila. Com isso, você pode desenhar o limite superior da sua curva ROC.1k-1p[0 0,1]k

Aqui está um exemplo 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();

Este código fará uma boa imagem para você:

TPR, FPR e curva ideal

Os pontos azuis são tuplas (FPR, TPR) para todos os subconjuntos e a linha vermelha se conecta (FPR, TPR) para os subconjuntos pareto-ideais.210

E agora o pouco de sal: você não precisava se preocupar com subconjuntos ! O que fiz foi classificar as folhas das árvores pela fração de amostras positivas em cada uma. Mas o que consegui é exatamente a curva ROC para a previsão probabilística da árvore. Isso significa que você não pode superar a árvore escolhendo manualmente suas folhas com base nas frequências alvo no conjunto de treinamento.

Você pode relaxar e continuar usando a previsão probabilística comum :)

David Dale
fonte
Boa ideia. Em teoria, ainda pode haver um número exponencial de números possíveis de "chamadas positivas", mas na prática provavelmente não é um problema.
Valentas
Por que número exponencial de chamadas? Calculo valor / peso para cada cluster (leva tempo linear), classifico-os (N * log (N)) e avalio o TPR e o FPR para cada um dos primeiros K clusters (também podem ser lineares).
David Dale
Você resolve a mochila para cada valor possível de previsões positivas e há um número exponencial de subconjuntos. Mas esse é um tecnicismo teórico, se você perguntar especificamente sobre os pontos dentro do casco convexo, o que não é interessante - essa deve ser a resposta aceita.
Valentas
@ Valentas, OK, entendo o seu ponto. Mas, ainda assim, se você der uma previsão aleatória em algumas folhas, poderá chegar a qualquer ponto do casco convexo. Portanto, neste caso, o casco é o próprio ROC.
David Dale
@DavidDale, para resumir: 1) Toda estratégia que é pareto ideal em relação a (sensibilidade, PPV) maximiza o número de verdadeiros positivos entre as estratégias com esse número de previsões positivas. 2) Esse é o problema da mochila. 3) Escolher os nós em ordem pelo número de exemplos positivos / número de exemplos é conhecido por ser uma boa solução aproximada para o problema da mochila. 4) Mas isso é o mesmo que escolher um limite para as probabilidades.
Josh Brown Kramer
0

Eu posso sugerir que você use métodos gananciosos. Dê um classificador para começar; você incluirá o classificador que faz com que o conjunto obtenha a melhor melhoria de desempenho. Se não for possível obter nenhuma melhoria, inclua mais classificadores, pare. Você começará com todos os classificadores. A complexidade será no máximo N * N.

Eu tenho mais uma pergunta: o que você quer dizer com "Pareto ideal", especialmente no seu contexto? Eu encontrei no wiki esta explicação, https://en.wikipedia.org/wiki/Pareto_efficiency

através da realocação, podem ser feitas melhorias no bem-estar de pelo menos um participante sem reduzir o bem-estar de qualquer outro participante.

A melhoria da eficiência de Pareto é para cada participante, o que pode corresponder a cada classificador. Como você define a melhoria em um classificador?

William
fonte
1
O que quero dizer é o seguinte: se eu tenho conjuntos 1 e 2, com (sensibilidade, valor preditivo positivo) = (0,90, 0,80) e (0,97, 0,93) respectivamente, então 1 não é o Pareto ideal, porque existe outro conjunto, ou seja, 2, que supera em todos os sentidos. Em relação ao algoritmo proposto: existe uma troca entre sensibilidade e PPV, portanto "o conjunto obtém a melhor melhoria de desempenho" não está bem definido.
Josh Brown Kramer