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

13

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.

Josh Brown Kramer
sumber
Apakah Anda mengklasifikasikan setiap kasus input menjadi benar atau salah?
image_doctor
@image_doctor: ya
Josh Brown Kramer
Saya "tidak jelas," ... yang terpisah dalam arti bahwa tidak ada dua akan kembali benar pada input yang sama ... "dan Anda mengklasifikasikan ke output biner, bagaimana Anda dapat memiliki lebih dari dua pengklasifikasi di Anda ansambel, saya mungkin melewatkan sesuatu?
image_doctor
@ image_doctor: Anda mungkin berpikir bahwa saya mengatakan bahwa tidak ada dua pengklasifikasi mengembalikan output yang sama pada input yang sama. Saya mengatakan tidak ada dua yang akan kembali benar. Keduanya dapat kembali salah.
Josh Brown Kramer
1
Mungkin makalah ini tentang cara yang secara teoritis optimal menggabungkan penggolong untuk ROC (atau makalah yang mengutipnya) dapat membantu Anda untuk memahami keadaan seni: M. Barreno, A. Cardenas, JD Tygar, Kurva ROC Optimal untuk Kombinasi Penggolong, Kemajuan dalam Sistem Pemrosesan Informasi Saraf Tiruan, 2008.
Valentas

Jawaban:

1

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?N10

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.

vSebuahlkamuewesayaghtkk0N

1k-1hal[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:

TPR, FPR, dan kurva optimal

Titik biru adalah (FPR, TPR) tuple untuk semua 210 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 :)

David Dale
sumber
Ide yang hebat. Secara teori masih ada banyak kemungkinan "panggilan positif", tetapi dalam praktiknya itu mungkin bukan masalah.
Valentas
Mengapa jumlah panggilan eksponensial? Saya menghitung nilai / berat untuk setiap kluster (membutuhkan waktu linier), mengurutkannya (N * log (N)), dan mengevaluasi TPR dan FPR untuk setiap kluster K pertama (dapat juga dibuat linier).
David Dale
Anda memecahkan ransel untuk setiap nilai prediksi positif yang mungkin, dan ada sejumlah himpunan bagian eksponensial. Tetapi ini adalah teknis teoretis jika Anda meminta secara khusus poin-poin di dalam cembung cembung, yang tidak menarik - ini harus menjadi jawaban yang diterima.
Valentas
@Valentas, OK, saya mengerti maksud Anda. Tapi tetap saja, jika Anda memberikan prediksi acak dalam beberapa daun, Anda bisa sampai ke titik mana pun di cembung lambung. Jadi dalam hal ini lambung adalah ROC itu sendiri.
David Dale
@DavidDale, untuk meringkas: 1) Setiap strategi yang optimal pareto sehubungan dengan (sensitivitas, PPV) memaksimalkan jumlah positif sebenarnya di antara strategi dengan jumlah prediksi positif. 2) Ini adalah masalah ransel. 3) Memilih simpul secara berurutan dengan jumlah contoh positif / jumlah contoh diketahui sebagai solusi perkiraan yang baik untuk masalah ransel. 4) Tapi itu sama saja dengan memilih ambang pada probabilitas.
Josh Brown Kramer
0

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?

William
sumber
1
Yang saya maksud adalah ini: jika saya memiliki ensemble 1 dan 2, dengan (sensitivitas, nilai prediksi positif) = (0,90, 0,80) dan (0,97, 0,93) masing-masing, maka 1 tidak optimal Pareto, karena ada ansambel lain, yaitu 2, yang mengalahkannya dengan segala cara. Mengenai algoritma yang Anda usulkan: ada tradeoff antara sensitivitas dan PPV, sehingga "ansambel mendapatkan peningkatan kinerja terbaik" tidak terdefinisi dengan baik.
Josh Brown Kramer