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.
fonte
Respostas:
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?N 1 0 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.v a l u ew e i gh t k k 0 0 N
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.1 k - 1 p ∈ [ 0 , 1 ] k
Aqui está um exemplo de python:
Este código fará uma boa imagem para você:
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 :)
fonte
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
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?
fonte