假设我有分类器 C_1 ... C_n 是不相交的，因为没有两个会在相同的输入上返回 true（例如决策树中的节点）。我想建立一个新的分类器，它是其中一些子集的联合（例如，我想决定决策树的哪些叶子给出正分类）。当然，这样做会在敏感性和阳性预测值之间进行权衡。所以我想看看ROC曲线。原则上，我可以通过枚举分类器的所有子集并计算得到的灵敏度和 PPV 来做到这一点。但是，如果 n 大于 30 左右，这将非常昂贵。另一方面，几乎可以肯定有一些组合不是帕累托最优的，所以可能有一些分支定界策略，或者什么，
我想咨询一下这种方法是否有可能取得成果，是否有任何工作，或者您是否对在上述情况下有效计算 ROC 曲线有任何想法。
如果我正确理解了这个问题，那么您已经训练了一种算法，可以将您的数据拆分为不相交的集群。现在您要分配预测到集群的某个子集，以及对他们其余的人。在这些子集中，您希望找到帕累托最优的子集，即在给定固定数量的阳性预测的情况下最大化真阳性率的那些（这相当于固定 PPV）。这是正确的吗？
这听起来很像背包问题！集群大小是“权重”，集群中正样本的数量是“值”，您希望用尽可能多的值填充固定容量的背包。
背包问题有几种寻找精确解的算法（例如通过动态规划）。但是一个有用的贪婪解决方案是按降序对集群进行排序 （即正样本的份额），取第一个 . 如果你拿 从 到 ，您可以非常便宜地绘制您的 ROC 曲线。
如果你分配 到第一个 簇和随机分数 样本中的 th cluster，你得到了背包问题的上限。有了这个，您可以绘制 ROC 曲线的上限。
这是一个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();
此代码将为您绘制一张漂亮的图片：
蓝点是所有的 (FPR, TPR) 元组 子集，红线连接（FPR，TPR）的帕累托最优子集。
现在有点盐：您根本不必为子集而烦恼！我所做的是按每个树叶中正样本的比例对树叶进行排序。但我得到的正是树概率预测的 ROC 曲线。这意味着，您不能通过根据训练集中的目标频率手动挑选叶子来超越树。
您可以放松并继续使用普通的概率预测:)
我可能会建议你使用贪婪的方法。给一个分类器开始，您将包括使集成获得最佳性能改进的分类器。如果无法通过包含更多分类器获得改进，则停止。您将从每个分类器开始。复杂度最多为 N*N。
我还有一个问题，您所说的“帕累托最优”是什么意思，尤其是在您的上下文中？我从 wiki 中找到了这个解释，https://en.wikipedia.org/wiki/Pareto_efficiency
通过重新分配，可以改善至少一个参与者的幸福感，而不会降低任何其他参与者的幸福感。
帕累托效率的提高是针对每个参与者的，这可能对应于每个分类器。您如何定义对一个分类器的改进？