Algoritma yang efisien untuk menghitung kurva ROC untuk classifier yang terdiri dari ensemble dari classifier terpisah

Misalkan saya memiliki pengklasifikasi C_1 ... C_n yang terpisah dalam arti bahwa tidak ada dua akan mengembalikan true pada input yang sama (misalnya node dalam pohon keputusan). Saya ingin membangun classifier baru yang merupakan gabungan dari beberapa subset dari ini (misalnya saya ingin memutuskan daun pohon keputusan mana yang memberikan klasifikasi positif). Tentu saja, dalam melakukannya akan ada trade off antara sensitivitas dan nilai prediksi positif. Jadi saya ingin melihat kurva ROC. Pada prinsipnya saya bisa melakukan ini dengan menghitung semua himpunan bagian dari pengklasifikasi dan menghitung sensitivitas dan PPV yang dihasilkan. Namun, ini sangat mahal jika n lebih dari 30 atau lebih. Di sisi lain, hampir pasti ada beberapa kombinasi yang tidak optimal Pareto, jadi mungkin ada beberapa cabang dan strategi terikat, atau sesuatu,

Saya ingin saran tentang apakah pendekatan ini mungkin berhasil dan apakah ada pekerjaan atau jika Anda memiliki ide tentang menghitung secara efisien kurva ROC dalam situasi di atas.

Jika saya memahami pertanyaan dengan benar, Anda telah melatih suatu algoritma yang membagi data Anda menjadi cluster terpisah. Sekarang Anda ingin menetapkan prediksi 1 untuk beberapa bagian dari kluster, dan 0 untuk sisanya. Dan di antara himpunan bagian itu, Anda ingin menemukan himpunan bagian yang optimal-pareto, yaitu mereka yang memaksimalkan tingkat positif sejati dengan jumlah prediksi positif yang tetap (ini setara dengan memperbaiki PPV). Apakah itu benar?$N$$1$$0$

Ini kedengarannya seperti masalah ransel ! Ukuran cluster adalah "bobot" dan jumlah sampel positif dalam sebuah cluster adalah "nilai", dan Anda ingin mengisi ransel Anda dengan kapasitas tetap dengan nilai sebanyak mungkin.

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

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

Ini dia contoh 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();

Kode ini akan menghasilkan gambar yang bagus untuk Anda:

Titik biru adalah (FPR, TPR) tuple untuk semua $2^{10}$ himpunan bagian, dan garis merah menghubungkan (FPR, TPR) untuk himpunan optimal pareto.

Dan sekarang sedikit garam: Anda tidak perlu repot tentang himpunan bagian sama sekali ! Apa yang saya lakukan adalah menyortir daun pohon berdasarkan fraksi sampel positif di masing-masing. Tapi yang saya dapatkan adalah kurva ROC untuk prediksi probabilitas pohon. Ini berarti, Anda tidak dapat mengungguli pohon dengan memetik daunnya berdasarkan frekuensi target pada set pelatihan.

Anda dapat bersantai dan tetap menggunakan prediksi probabilistik biasa :)

Saya mungkin menyarankan agar Anda menggunakan metode serakah. Berikan classifier untuk memulai, Anda akan menyertakan classifier yang membuat ansambel mendapatkan peningkatan kinerja terbaik. Jika tidak ada peningkatan yang bisa dilakukan, termasuk lebih banyak pengklasifikasi, maka berhentilah. Anda akan mulai dengan setiap pengklasifikasi. Kompleksitas paling banyak adalah N * N.

Saya punya satu pertanyaan lagi, Apa yang Anda maksud dengan "Pareto optimal", terutama dalam konteks Anda? Saya menemukan dari wiki penjelasan ini, https://en.wikipedia.org/wiki/Pareto_efficiency

melalui realokasi, perbaikan dapat dilakukan untuk setidaknya satu kesejahteraan peserta tanpa mengurangi kesejahteraan peserta lainnya.

Peningkatan untuk efisiensi Pareto adalah untuk setiap peserta, yang mungkin sesuai dengan masing-masing pengklasifikasi. Bagaimana Anda mendefinisikan peningkatan lebih dari satu classifier?