可扩展或在线的多标签分类器（Out-of-Core Multi-Label Classifiers）

Question

在过去的2-3周中，我一直在为这个问题苦苦思索。我的问题是多标签（而不是多类）问题，其中每个样本可以属于几个标签。

我有大约450万个文本文档作为训练数据，以及约100万个文本文档作为测试数据。标签数约为35K。

我正在使用scikit-learn。对于特征提取，我之前使用的是TfidfVectorizer，但它根本无法扩展，现在我正在使用HashVectorizer，但由于我拥有的文档数量，它并不是那么可扩展。

vect = HashingVectorizer(strip_accents='ascii', analyzer='word', stop_words='english', n_features=(2 ** 10))

SKlearn提供了一个OneVsRestClassifier，可以将任何估计器输入其中。对于多标签问题，我发现只有LinearSVC和SGDClassifier能够正确工作。根据我的基准测试，SGD在内存和时间方面都优于LinearSVC。所以，我有类似这样的代码：

clf = OneVsRestClassifier(SGDClassifier(loss='log', penalty='l2', n_jobs=-1), n_jobs=-1)

但是它存在一些严重问题：

1. OneVsRest没有partial_fit方法，这使得它无法进行 out-of-core 学习。有其他的替代方法吗？
2. HashingVectorizer/Tfidf 都只能在单核上运行，并且没有 n_jobs 参数。哈希文档需要太长时间。有其他的方案/建议吗？另外，n_features 的值是否正确？
3. 我测试了100万个文档。哈希需要15分钟，当进行 clf.fit(X, y) 时，会收到 MemoryError 错误，因为 OvR 内部使用 LabelBinarizer 并尝试分配一个(y x 类别数)维度的矩阵，这几乎不可能分配。该怎么办？
4. 还有其他可靠且可扩展的多标签算法库吗？我知道 genism 和 mahout，但它们都没有针对多标签情况的任何内容？

- Gaurav Kumar

---

当你说“HashVectorizer更好但不太可扩展”时，只是一个备注：HashVectorizer是完全可扩展的：如果你投入两倍的计算资源，你将以两倍的速度处理数据（你可以通过分区数据并运行处理来并行使用它的无状态和有限内存使用）。这就是可扩展性的确切定义。我同意HashVectorizer可能可以更优化，以在相同的计算资源上更快地工作，但这与可扩展性问题无关。 - ogrisel

感谢澄清。我确实同意 HV 相对于 Tfidf 的优势，只是在数据分区方面不是很确定。现在我进行了一个小型 POC 来分割数据并单独运行 HV 然后将结果合并。我最初的意思是算法部分的工作是巨大的成就，但仍有可能像你建议的那样更具可扩展性地进行分割和并行运行。 （完成后，我将提交 PR，以便 HV 也具有 n_jobs 参数） - Gaurav Kumar

很不幸，在 scikit-learn 中使用的 joblib 的当前实现中，我们使用了 multiprocessing，因此输入数据必须被复制以便发送到子进程。因此，这样的 n_jobs 参数会增加显着的开销，可能根本没有好处。如果您确实有大型数据集，最好处理许多并行的 out-of-core 循环，这些循环处理数据访问（磁盘、数据库、网络...）本身并避免任何内存复制。然而，这样的样板代码可能永远不会包含在 scikit-learn 中，因为它太特定于项目 / 框架。 - ogrisel

Answer 1

我会手动处理多标签部分。 OneVsRestClassifier无论如何都将它们视为独立的问题。您只需创建n_labels个分类器，然后对它们调用partial_fit。如果您只想哈希一次（我建议这样做），则不能使用管道。不确定如何加速哈希向量化器。您需要问@Larsmans和@ogrisel；）

在OneVsRestClassifier上拥有partial_fit将是一个不错的补充，实际上我并没有看到任何特定的问题。您也可以尝试自己实现并发送PR。

- Andreas Mueller

---

我不感到惊讶 ;) - Andreas Mueller

谢谢，如果我要手动编写OvR，您会推荐哪种估计器来解决这个问题？另外，假设我启动了35K个估计器（n_labels），并在训练数据上逐个拟合它们。我该如何从中计算标签？那些具有单独的predict_proba > 0.5的估计器将与该样本相关联的标签。这种方法可行吗？ （抱歉，我只学习了3周的ML和sklearn） - Gaurav Kumar

你可以尝试训练SGDClassifier、 PassiveAggressiveClassifier 和 MultinomialNB 作为二元分类器（每个标签一个）的独立实例。然后，你可以根据 predict_proba 或 decision_function 的值对顶部预测进行排名，并选择前五个标签（如果它们的预测概率低于0.5或决策函数为负，则选择较少的标签）。你还可以训练第二个回归模型，该模型使用二元分类模型的概率预测并预测每个实例保留的正标签数的期望值（即top k中的k）。 - ogrisel

线性模型加1（为什么要使用多项式而不是伯努利奥利维尔？）。我会首先尝试阈值处理，看看效果如何。如果标签非常不平衡，您可能需要调整类别权重。顺便说一句，35k相当多。您可能会遇到内存问题。请记住，您需要存储n_labels * n_features个系数。 - Andreas Mueller

非常感谢您提供的宝贵建议。我目前正在手动构建一个自定义的多标签包装器，覆盖了SGDClassifier。我使用decision_function，因为它们只有一个浮点值，而predict_proba有两个值-一个用于0类，另一个用于1类。如果遇到任何问题，我会尽快报告我的进展或问题。 - Gaurav Kumar

@AndreasMueller：MultinomialNB是文本分类的默认选项。BernoulliNB更适用于布尔变量问题或非常短的文本。 - Fred Foo

Answer 2

1. OneVsRestClassifier实现的算法非常简单：当有K个分类时，它只是拟合K个二进制分类器。您可以在自己的代码中执行此操作，而不是依赖于OneVsRestClassifier。您还可以在最多K核心并行运行：只需运行K个进程。如果您的类比计算机处理器更多，则可以使用GNU parallel等工具安排训练。
2. scikit-learn中的多核支持正在进行中；在Python中进行细粒度并行编程相当棘手。对于HashingVectorizer存在潜在的优化方法，但是作者之一（我）尚未想到。
3. 如果按照我的（和Andreas的）建议执行自己的一对多，则不应再出现此问题。
4. (1.)中的技巧适用于任何分类算法。

至于特征数量，这取决于问题，但对于大规模文本分类，2 ^ 10 = 1024似乎非常小。我会尝试使用约2 ^ 18 - 2 ^ 22左右的数字。如果使用L1惩罚训练模型，则可以对训练好的模型调用sparsify，以将其权重矩阵转换为更节省空间的格式。

- Fred Foo

---

谢谢，我会尝试手动实现OvR并且尝试避免可扩展性问题。我忘了提到每个文件的长度非常小（大约200个单词）。因此，我认为1024个特征应该足够，因为2 ^ 18会给我带来很多内存问题。我甚至启动了一个具有30 GB RAM的AWS实例，但也没有解决问题。 - Gaurav Kumar

如果您有35K个二进制分类器和2 ** 18个特征，仅存储聚合模型就需要73GB的空间。在权重学习后，可能可以稀疏化模型以节省预测时的内存，但据我所知，scikit-learn尚未实现此功能。您可以使用safe_sparse_dot手动实现decision_function来完成这一操作。 - ogrisel

为了训练具有许多零权重的模型，从而在将coef_属性存储为scipy.sparse矩阵时可以改善内存使用情况，您应该使用带有penalty="elasticnet"或"l1"的SGDClassifier。 - ogrisel

@ogrisel：线性分类器有一个“sparsify”方法，可以将“coef_”转换为稀疏矩阵格式（CSR）。 - Fred Foo

@GauravKumar：你需要两者。问题在于在系数稀疏的情况下无法进行训练，因此你需要在训练后（例如，在序列化之前）进行稀疏化。 - Fred Foo

Answer 3

我的可伸缩性论点是，不要使用OneVsRest，因为它只是最简单的基准之一，你应该使用更高级的问题转换方法集合。在我的论文中，我提供了一种将标签空间划分为子空间并使用Label Powerset将子问题转换为多类单标签分类的方案。要尝试这个方案，请使用以下代码，该代码利用建立在scikit-learn之上的多标签库 - scikit-multilearn：

from skmultilearn.ensemble import LabelSpacePartitioningClassifier
from skmultilearn.cluster import IGraphLabelCooccurenceClusterer
from skmultilearn.problem_transform import LabelPowerset

from sklearn.linear_model import SGDClassifier

# base multi-class classifier SGD
base_classifier = SGDClassifier(loss='log', penalty='l2', n_jobs=-1)

# problem transformation from multi-label to single-label multi-class
transformation_classifier = LabelPowerset(base_classifier)

# clusterer dividing the label space using fast greedy modularity maximizing scheme
clusterer = IGraphLabelCooccurenceClusterer('fastgreedy', weighted=True, include_self_edges=True) 

# ensemble
clf = LabelSpacePartitioningClassifier(transformation_classifier, clusterer)

clf.fit(x_train, y_train)
prediction = clf.predict(x_test)

- niedakh

Answer 4

sklearn 最近新增了 partial_fit() 方法，希望它会在即将发布的版本中可用（它已经在主分支中了）。

你的问题规模很大，使用神经网络来解决非常吸引人。看一下 magpie，相信它会比线性分类器给出更好的结果。

- stpk