第八章 多类SVMs

吴天晖/译

SVMs可以生成二分分类器。然而，我们经常面对的数据集多于两类。举例，原葡萄酒数据集实际上包含三种不同的产品。有很多种方法可以让SVMs在多类下工作。在这章里，我们将介绍一些非常流行的多类分类方法和讨论它们的细节。

这一章里的所有代码，我们将用代码表41产生的数据集(如图51所示)。

代码表41import numpy as np def load_X():return np.array([[1, 6], [1, 7], [2, 5], [2, 8],[4, 2], [4, 3], [5, 1], [5, 2],[5, 3], [6, 1], [6, 2], [9, 4],[9, 7], [10, 5], [10, 6], [11, 6],[5, 9], [5, 10], [5, 11], [6, 9],[6, 10], [7, 10], [8, 11]])def load_y():return np.array([1, 1, 1, 1,2, 2, 2, 2, 2, 2, 2,3, 3, 3, 3, 3,4, 4, 4, 4, 4, 4, 4])

图51:4个类的分类问题

解多类二分问题

一对多（One-against-all ）

也叫一对所有（one-versus-the-rest），这可能是最简单的方法。

为了分类K个类，我们构造K个不同的二分分类器。对于一个给出的类，这个类中的所有示例点都为正，不在这个类里的所有示例点都为负（代码表42)。

代码表42

import numpy as npfrom sklearn import svm# Create a simple datasetX = load_X()y = load_y()# Transform the 4 classes problem# in 4 binary classes problems.y_1 = np.where(y == 1, 1, -1)y_2 = np.where(y == 2, 1, -1)y_3 = np.where(y == 3, 1, -1)y_4 = np.where(y == 4, 1, -1)

所有的问题我们用二分分类器来训练（代码表43）。结果，我们每一个分类器都得到一个决策边缘（如图52）。

代码表43# Train one binary classifier on each problem.y_list = [y_1, y_2, y_3, y_4]classifiers = []for y_i in y_list:clf = svm.SVC(kernel='linear', C=1000)clf.fit(X, y_i)classifiers.append(clf)

图52:一对多方法为每一个类建一个分类器

为了做一个新的预测，我们用分类器去预测分类器中返回正值的类（代码表44)。然而，这可能会给出不一致的结果，因为一个标量可能同时分配给多类或为空(Bishop, 2006)。图53显示了这个问题；一对多分类器不能预测分类分布在每一角落的蓝色区域中的数据,因为两个分类器都同时给出正值预测。这将返回一个示例数据同时属于两个类。同样的问题会发生在中间，因为每一个分类器都给出正值。结果，在这个区域没有类可以用来分配。

代码表44def predict_class(X, classifiers):predictions = np.zeros((X.shape[0], len(classifiers)))for idx, clf in enumerate(classifiers):predictions[:, idx] = clf.predict(X)# returns the class number if only one classifier predicted it 	# returns zero otherwise. 	return np.where((predictions == 1).sum(1) == 1,(predictions == 1).argmax(axis=1) + 1,0)

图53:一对多导致模糊的决策

作为一个替代方案，Vladimir Vapnik 建议哪一个决策函数返回的值最大分类器就将其分到哪个类（Vapnik V. N., 1998 ）。代码表45演示了这个建议。注意这里我们用decision_function 代替分类器中的predict方法。这个方法返回一个正的真实值当这个示例被分类器分类到正确的一边时，如果在另一边则返回负值。有趣的是注意到它用的是最大值，而不是最大的绝对值，如果所有分类器有争执的情况下这个方法将选择分给最接近的超平面的类。举例，示例点（6,4)在图中将被分配给这个蓝星类。

代码表45def predict_class(X, classifiers):predictions = np.zeros((X.shape[0], len(classifiers)))for idx, clf in enumerate(classifiers):predictions[:, idx] = clf.decision_function(X)# return the argmax of the decision function as suggested by Vapnik.return np.argmax(predictions, axis=1) + 1

如图54所示，应用了这个启发式让我们的分类结果没有模糊值。这个方法的主要缺点是不同的分类器要训练不同的任务，所以不能但保decision_function 方法在相同变形下返回的质量。如果一个决策方法比其他方法返回大值多10次，这个类将对同一个示例数据做错误的分配。

图54:应用一个简单的启发式避免模糊决策问题

一对多方法另一个问题是训练集是不均衡的(Bishop, 2006) 。如果一个问题有100类，每个类有10个示例数据，每一个分类器将被10个正值示例数据和990个负值示例数据训练。因此，负值示例数据将大大影响决策边缘。

尽管如此，一对多仍是一个流行的多类分类方法，因为它容易实现和理解。

注意："[…]实际上一对多方法被广泛用尽管它有特制性和实际局限。" (Bishop, 2006)

当我们使用的sklean,linearSVC自动机把一对多作为默认策略时。你也可以明确指定multi_class参数使用ovr(one-vs-the-rest),如代码表46所示。

代码表46from sklearn.svm import LinearSVCimport numpy as npX = load_X()y = load_y()clf = LinearSVC(C=1000, random_state=88, multi_class='ovr')clf.fit(X,y)# Make predictions on two examples.X_to_predict = np.array([[5,5],[2,5]])print(clf.predict(X_to_predict)) # prints [2 1]

一对一(one-against-one)

在这个方法中，我们试着去找区分一个类与另一个类来代替区分一个类与所有的类来代替。结果，我们用每对类去试验一个分类器，会导致K个类有K(K-1)/2个分类器。每一个分类器训练数据子集而产生它自己的决策边缘（图）。

预测使用一个简单的投票策略。每一个希望预测的示例通过每一个分类器后，这个预测类被记录下来。然后，这个具有最多的票数的类被分配给示例数据（代码表47)。

代码表47from itertools import combinationsfrom scipy.stats import modefrom sklearn import svmimport numpy as np# Predict the class having the max number of votes.def predict_class(X, classifiers, class_pairs):predictions = np.zeros((X.shape[0], len(classifiers)))for idx, clf in enumerate(classifiers):class_pair = class_pairs[idx]prediction = clf.predict(X)predictions[:, idx] = np.where(prediction == 1,class_pair[0], class_pair[1])return mode(predictions, axis=1)[0].ravel().astype(int)X = load_X()y = load_y()# Create datasets.training_data = []class_pairs = list(combinations(set(y), 2))for class_pair in class_pairs:class_mask = np.where((y == class_pair[0]) | (y == class_pair[1]))y_i = np.where(y[class_mask] == class_pair[0], 1, -1)training_data.append((X[class_mask], y_i))# Train one classifier per class.classifiers = [] for data in training_data:clf = svm.SVC(kernel='linear', C=1000)clf.fit(data[0], data[1]) classifiers.append(clf)# Make predictions on two examples.X_to_predict = np.array([[5,5],[2,5]])print(predict_class(X_to_predict, classifiers, class_pairs))# prints [2 1]

图55:一对一为所有分类中的每对类构造一个分类器

使用这个方法，我们仍然要面临模糊分类的问题。如果两个类有完全相同的票数，算法建议选择序号小的可行的（不见得是最好的）策略（Hsu & Lin, A Comparison of Methods for Multi-class Support Vector Machines, 2002 ）。

图56: 使用投票框架预测

上图显示一对一策略生成的决策区域与一对多所生成的不同。在图57中，注意一对一分类器所生成的区域，区域的颜色变化仅在超平面内（注意黑色直线），这不同于一对多。

图57:一对多（左）与一对一（右）的对比

一对多（左）与一对一（右）的对比一对一方法是sklearn默认的多类分类方法。作为取代代码表47，在代码表48中你将得到更精确的同样的结果。

代码表48from sklearn import svmimport numpy as npX = load_X()y = load_y()# Train a multi-class classifier.clf = svm.SVC(kernel='linear', C=1000)clf.fit(X,y)# Make predictions on two examples.X_to_predict = np.array([[5,5],[2,5]])print(clf.predict(X_to_predict)) # prints [2 1]

一对多方法的有一个主要缺点是分类器容易趋向过拟合。然而，大量的类会使分类器的数量超线性增长，所以这个方法在解决大问题时必然会变慢(Platt, Cristianini, & Shawe-Taylor, 2000 )。

DAGSVM

DAGSVM的名字为单向无环图SVM（Directed Acyclic Graph SVM）的缩写。由John Platt 等在2000年提出用来提升一对一方法(Platt, Cristianini, & Shawe-Taylor, 2000) 。

注意：John C. Platt 发明了SMO算法和普拉特校准算法（Platt Scaling)，还提出了DAGSVM。给SVMs作出巨大贡献。

DAGSVM背后的目标是用和一对一相同的训练方法，但是它用单向无环图（DAG）来选择可用分类器使检测速度大幅提高。

如果我们有4个类A,B,C和D,则每对类组合需要六个分类器：(A, B); (A, C); (A, D); (B, C); (B, D); 和 (C, D)。我们先用分类器（A，D），它预测类A，也就是预测非D的数据，每二个分类器同样预测A(非C）。它的意思是分类器(B, D), (B, C) 或者 (C, D)可以略过，因为我们已经知道数据不会在类C或D中。最后用到分类器（A，B），如果我们要预测B，我们分配数据点到类B。这个示例的技巧用红色路径标在图58中。图中的每一个节点表示一对类。

图58:预测路径显示为一个有向无环图

四个类，我们用三个分类器做预测，代替一对一的六个。通常，平均K个类可用K-1个决策节点。

我们用代码表49来取代代码表47的predict_class 方法可得出同样的结果，但是好处是少用了很多分类器。

在代码表49中，我们用一个List实现了DAGSVM方法。我们从这个List中的可用类开始，经过每一次预测，我们移去一些不需要的。最后，留下一个类是我们要给它分配示例数据的。

注意代码表49,这里显示的代码不能用于生产环境，因为当数据集（X）特别大时它会变慢。

代码表49def predict_class(X, classifiers, distinct_classes, class_pairs):results = []for x_row in X:class_list = list(distinct_classes)# After each prediction, delete the rejected class# until there is only one class.while len(class_list) > 1:# We start with the pair of the first and# last element in the list.class_pair = (class_list[0], class_list[-1])classifier_index = class_pairs.index(class_pair)y_pred = classifiers[classifier_index].predict(x_row)if y_pred == 1:class_to_delete = class_pair[1]else:class_to_delete = class_pair[0]class_list.remove(class_to_delete)results.append(class_list[0])return np.array(results)

注意：DAGSVM平均比投票方法快1.6到2.3倍。(Platt, Cristianini, & Shawe-Taylor, 2000) 。

解单独优化问题

不是试着解多个二分问题，而是去解一个单独优化问题，这个方法这些年来被很多人提出。

Vapnik, Weston, 和 Watkins

这个方法是用泛化的SVMs优化问题直接去解多类分类问题。它们被Vapnik (Vapnik V. N., 1998) 和 Weston & Watkins (Weston & Watkins, 1999)独立发现。对每个类，就是增加约束的优化问题。结果，随着类的增加问题的数量也成比例增加导致训练越来越慢。

Crammer 和 Singer

Crammer 和 Singer (C&S) 提出另一可用的多类SVMs方法。如同Weston 和 Watkins，他们解单独优化问题用到了太多的斯莱克(slack)变量(Crammer & Singer, 2001)。 这个方法优点是能减少内存的占用和训练时间，然而，比较这两种算法，Hsu 和Lin发现当正交参数C的值较大时C&S 方法特别慢(Hsu & Lin, A Comparison of Methods for Multi-class Support Vector Machines, 2002) 。

在sklear里，当用到LinearSVC 时你可以选择C&S算法（如代码表50所示）。在图59中，我们能看到C&S预测不同于一对多和一对一方法。

代码表50from sklearn import svmimport numpy as npX = load_X()y = load_y()clf = svm.LinearSVC(C=1000, multi_class='crammer_singer')clf.fit(X,y)# Make predictions on two examples.X_to_predict = np.array([[5,5],[2,5]])print(clf.predict(X_to_predict)) # prints [4 1]

图59: Crammer&Singer算法预测

你将要用那一种方法呢？

对于这么多的可选项，选择哪一个多类方法比较适合你的问题是因难的。

Hsu和Lin写了一个不错的文章介绍不同的SVMs的多类方法(Hsu & Lin, A Comparison of Methods for Multi-class Support Vector Machines, 2002)。它们判断一对一和DAG方法比其他方法要适用和实用。增强的一对一方法在sklearn中可用，所以它可能是你默认的选择。

请记住在linearSVC中默认使用一对多方法，也许用Crammer&Singer算法能更好的帮你达到目的。基于这个主题，Dogan等发现尽管比其他算法要快，但是一对多假设函数在统计学上精确度明显更差(Dogan, Glasmachers, & Igel, 2011) 。表1展示了这一章中的方法的简介希望能帮你做出选择。

表1: 多类SVM方法简介

小结

感谢这些年来众多的改进，现在有大量的方法用来给SVMs做多类分类。每一个方法有优点和缺点，你使用类库中的方法，它们绝大部份都可以在有效的时间结束。然而，有必要，你现在知道哪一个方法能更好的解决你的独特问题。

多类SVMs的研究还没有结束。最近的研究集中在分布式训练。例如，Han & Berg 发布了一个新算法叫做多类分布式统一优化SVM（Distributed Consensus Multiclass SVM） ，它是Crammer 和 Singer公式的变形用来统一优化。