Algoritmo eficiente para calcular la curva ROC para un clasificador que consiste en un conjunto de clasificadores disjuntos

13

Supongamos que tengo clasificadores C_1 ... C_n que son disjuntos en el sentido de que no habrá dos verdaderos en la misma entrada (por ejemplo, los nodos en un árbol de decisión). Quiero construir un nuevo clasificador que sea la unión de algún subconjunto de estos (por ejemplo, quiero decidir qué hojas de un árbol de decisión darán una clasificación positiva). Por supuesto, al hacerlo habrá una compensación entre la sensibilidad y el valor predictivo positivo. Entonces me gustaría ver una curva ROC. En principio, podría hacer esto enumerando todos los subconjuntos de clasificadores y calculando la sensibilidad resultante y el PPV. Sin embargo, esto es prohibitivamente costoso si n es más de 30 más o menos. Por otro lado, es casi seguro que hay algunas combinaciones que no son óptimas para Pareto, por lo que puede haber alguna estrategia de ramificación y unión, o algo así,

Me gustaría recibir consejos sobre si es probable que este enfoque sea fructífero y si hay algún trabajo o si tiene alguna idea sobre el cálculo eficiente de la curva ROC en la situación anterior.

Josh Brown Kramer
fuente
¿Está clasificando cada caso de entrada como verdadero o falso?
image_doctor
@image_doctor: sí
Josh Brown Kramer
No estoy claro, "... que son disjuntos en el sentido de que no habrá dos verdaderos en la misma entrada ..." y está clasificando a una salida binaria, cómo puede tener más de dos clasificadores en su ensemble, probablemente estoy perdiendo algo?
image_doctor
@image_doctor: Quizás esté pensando que estoy diciendo que no hay dos clasificadores que devuelvan la misma salida en la misma entrada. Estoy diciendo que no dos volverán a ser verdad. Ambos pueden devolver falso.
Josh Brown Kramer
1
Quizás este documento sobre una forma teóricamente óptima de combinar clasificadores para ROC (o documentos que lo citan) puede ayudarlo a comprender el estado del arte: M. Barreno, A. Cardenas, JD Tygar, Curva ROC óptima para una combinación de clasificadores, Avances en los sistemas de procesamiento de información neuronal, 2008.
Valentas

Respuestas:

1

Si entendí la pregunta correctamente, has entrenado un algoritmo que divide tus datos en grupos disjuntos. Ahora desea asignar la predicción a algún subconjunto de los clústeres y al resto de ellos. Y en esos subconjuntos, desea encontrar los pareto-óptimos, es decir, aquellos que maximizan la tasa positiva verdadera dado un número fijo de predicciones positivas (esto es equivalente a fijar PPV). ¿Es correcto?norte10 0

¡Esto suena muy parecido al problema de la mochila ! Los tamaños de los conglomerados son "pesos" y el número de muestras positivas en un conglomerado son "valores", y desea llenar su mochila de capacidad fija con el mayor valor posible.

El problema de la mochila tiene varios algoritmos para encontrar soluciones exactas (por ejemplo, mediante programación dinámica). Pero una solución codiciosa útil es ordenar los grupos en orden decreciente de (es decir, compartir muestras positivas) y tomar la primera . Si lleva de a , puede dibujar su curva ROC de forma muy económica.vunltumiwmiyosolhtkk0 0norte

Y si asigna a los primeros grupos de y a la fracción aleatoria de muestras en el grupo , obtendrá el límite superior del problema de la mochila. Con esto, puede dibujar el límite superior de su curva ROC.1k-1pag[0 0,1]k

Aquí va un ejemplo 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 dibujará una buena imagen para ti:

TPR, FPR y curva óptima

210

Y ahora un poco de sal: ¡no tenía que preocuparse por los subconjuntos en absoluto ! Lo que hice fue ordenar las hojas de los árboles por la fracción de muestras positivas en cada una. Pero lo que obtuve es exactamente la curva ROC para la predicción probabilística del árbol. Esto significa que no puede superar el rendimiento del árbol seleccionando manualmente sus hojas en función de las frecuencias objetivo en el conjunto de entrenamiento.

Puedes relajarte y seguir usando predicciones probabilísticas ordinarias :)

David Dale
fuente
Gran idea. En teoría, podría haber un número exponencialmente posible de "llamadas positivas", pero en la práctica probablemente no sea un problema.
Valentas
¿Por qué número exponencial de llamadas? Calculo valor / peso para cada grupo (toma tiempo lineal), los ordeno (N * log (N)) y evalúo TPR y FPR para cada primer grupo de K (también puede hacerse lineal).
David Dale
Resuelve la mochila para cada valor posible de predicciones positivas, y hay un número exponencial de subconjuntos. Pero este es un tecnicismo teórico si pregunta específicamente por los puntos dentro del casco convexo, lo cual no es interesante, esta debería ser la respuesta aceptada.
Valentas
@Valentas, OK, veo tu punto. Pero aún así, si proporciona predicciones aleatorias en algunas hojas, puede llegar a cualquier punto del casco convexo. Entonces, en este caso, el casco es el ROC mismo.
David Dale
@DavidDale, para resumir: 1) Cada estrategia que es pareto óptima con respecto a (sensibilidad, VPP) maximiza el número de verdaderos positivos entre las estrategias con ese número de predicciones positivas. 2) Este es el problema de la mochila. 3) Se sabe que elegir los nodos en orden por número de ejemplos positivos / número de ejemplos es una buena solución aproximada al problema de la mochila. 4) Pero eso es lo mismo que elegir un umbral en las probabilidades.
Josh Brown Kramer
0

Podría sugerirle que use métodos codiciosos. Dé un clasificador para comenzar, incluirá el clasificador que hace que el conjunto obtenga la mejor mejora de rendimiento. Si no puede lograrse ninguna mejora, incluya más clasificadores, luego deténgase. Comenzarás con todos los clasificadores. La complejidad será como máximo N * N.

Tengo una pregunta más, ¿Qué quieres decir con "Pareto óptimo", especialmente en tu contexto? Encontré en wiki esta explicación, https://en.wikipedia.org/wiki/Pareto_efficiency

a través de la reasignación, se pueden realizar mejoras en el bienestar de al menos un participante sin reducir el bienestar de ningún otro participante.

La mejora en la eficiencia de Pareto es para cada participante, que podría corresponder a cada clasificador. ¿Cómo define la mejora sobre un clasificador?

William
fuente
1
Lo que quiero decir es esto: si tengo los conjuntos 1 y 2, con (sensibilidad, valor predictivo positivo) = (.90, .80) y (.97, .93) respectivamente, entonces 1 no es óptimo de Pareto, porque hay otro conjunto, a saber, 2, que lo supera en todos los sentidos. Con respecto a su algoritmo propuesto: existe una compensación entre la sensibilidad y el PPV, por lo que "el conjunto obtiene la mejor mejora del rendimiento" no está bien definido.
Josh Brown Kramer