项目github地址：bitcarmanlee easy-algorithm-interview-and-practice
欢迎大家star，留言，一起学习进步

SVM是一种典型的两类分类器，即它只回答属于正类还是负类的问题。而现实中要解决的问题，往往是多类的问题（少部分例外，例如垃圾邮件过滤，就只需要确定“是”还是“不是”垃圾邮件），比如文本分类，比如数字识别。如何由两类分类器得到多类分类器，就是一个值得研究的问题。

其中一种一劳永逸的方法，就是真的一次性考虑所有样本，并求解一个多目标函数的优化问题，一次性得到多个分类面。多个超平面把空间划分为多个区域，每个区域对应一个类别，给一篇文章，看它落在哪个区域就知道了它的分类。

看起来很美对不对？只可惜这种算法还基本停留在纸面上，因为一次性求解的方法计算量实在太大，大到无法实用的地步。

稍稍退一步，我们就会想到所谓“一类对其余”的方法，就是每次仍然解一个两类分类的问题。比如我们有5个类别，第一次就把类别1的样本定为正样本，其余2，3，4，5的样本合起来定为负样本，这样得到一个两类分类器，它能够指出一篇文章是还是不是第1类的；第二次我们把类别2 的样本定为正样本，把1，3，4，5的样本合起来定为负样本，得到一个分类器，如此下去，我们可以得到5个这样的两类分类器（总是和类别的数目一致）。到了有文章需要分类的时候，我们就拿着这篇文章挨个分类器的问：是属于你的么？是属于你的么？哪个分类器点头说是了，文章的类别就确定了。这种方法的好处是每个优化问题的规模比较小，而且分类的时候速度很快（只需要调用5个分类器就知道了结果）。但有时也会出现两种很尴尬的情况，例如拿一篇文章问了一圈，每一个分类器都说它是属于它那一类的，或者每一个分类器都说它不是它那一类的，前者叫分类重叠现象，后者叫不可分类现象。分类重叠倒还好办，随便选一个结果都不至于太离谱，或者看看这篇文章到各个超平面的距离，哪个远就判给哪个。不可分类现象就着实难办了，只能把它分给第6个类别了……更要命的是，本来各个类别的样本数目是差不多的，但“其余”的那一类样本数总是要数倍于正类（因为它是除正类以外其他类别的样本之和嘛），这就人为的造成了上一节所说的“数据集偏斜”问题。

因此我们还得再退一步，还是解两类分类问题，还是每次选一个类的样本作正类样本，而负类样本则变成只选一个类（称为“一对一单挑”的方法，哦，不对，没有单挑，就是“一对一”的方法，呵呵），这就避免了偏斜。因此过程就是算出这样一些分类器，第一个只回答“是第1类还是第2类”，第二个只回答“是第1类还是第3类”，第三个只回答“是第1类还是第4类”，如此下去，你也可以马上得出，这样的分类器应该有5 X 4/2=10个（通式是，如果有k个类别，则总的两类分类器数目为k(k-1)/2）。虽然分类器的数目多了，但是在训练阶段（也就是算出这些分类器的分类平面时）所用的总时间却比“一类对其余”方法少很多，在真正用来分类的时候，把一篇文章扔给所有分类器，第一个分类器会投票说它是“1”或者“2”，第二个会说它是“1”或者“3”，让每一个都投上自己的一票，最后统计票数，如果类别“1”得票最多，就判这篇文章属于第1类。这种方法显然也会有分类重叠的现象，但不会有不可分类现象，因为总不可能所有类别的票数都是0。看起来够好么？其实不然，想想分类一篇文章，我们调用了多少个分类器？10个，这还是类别数为5的时候，类别数如果是1000，要调用的分类器数目会上升至约500,000个（类别数的平方量级）。这如何是好？

看来我们必须再退一步，在分类的时候下功夫，我们还是像一对一方法那样来训练，只是在对一篇文章进行分类之前，我们先按照下面图的样子来组织分类器（如你所见，这是一个有向无环图，因此这种方法也叫做DAG SVM）

这样在分类时,我们就可以先问分类器“1对5”（意思是它能够回答“是第1类还是第5类”），如果它回答5，我们就往左走，再问“2对5”这个分类器，如果它还说是“5”，我们就继续往左走，这样一直问下去，就可以得到分类结果。好处在哪？我们其实只调用了4个分类器（如果类别数是k，则只调用k-1个），分类速度飞快，且没有分类重叠和不可分类现象！缺点在哪？假如最一开始的分类器回答错误（明明是类别1的文章，它说成了5），那么后面的分类器是无论如何也无法纠正它的错误的（因为后面的分类器压根没有出现“1”这个类别标签），其实对下面每一层的分类器都存在这种错误向下累积的现象。

不过不要被DAG方法的错误累积吓倒，错误累积在一对其余和一对一方法中也都存在，DAG方法好于它们的地方就在于，累积的上限，不管是大是小，总是有定论的，有理论证明。而一对其余和一对一方法中，尽管每一个两类分类器的泛化误差限是知道的，但是合起来做多类分类的时候，误差上界是多少，没人知道，这意味着准确率低到0也是有可能的，这多让人郁闷。
　　而且现在DAG方法根节点的选取（也就是如何选第一个参与分类的分类器），也有一些方法可以改善整体效果，我们总希望根节点少犯错误为好，因此参与第一次分类的两个类别，最好是差别特别特别大，大到以至于不太可能把他们分错；或者我们就总取在两类分类中正确率最高的那个分类器作根节点，或者我们让两类分类器在分类的时候，不光输出类别的标签，还输出一个类似“置信度”的东东，当它对自己的结果不太自信的时候，我们就不光按照它的输出走，把它旁边的那条路也走一走，等等。

大Tips：SVM的计算复杂度
　　使用SVM进行分类的时候，实际上是训练和分类两个完全不同的过程，因而讨论复杂度就不能一概而论，我们这里所说的主要是训练阶段的复杂度，即解那个二次规划问题的复杂度。对这个问题的解，基本上要划分为两大块，解析解和数值解。
　　解析解就是理论上的解，它的形式是表达式，因此它是精确的，一个问题只要有解（无解的问题还跟着掺和什么呀，哈哈），那它的解析解是一定存在的。当然存在是一回事，能够解出来，或者可以在可以承受的时间范围内解出来，就是另一回事了。对SVM来说，求得解析解的时间复杂度最坏可以达到O(Nsv3)，其中Nsv是支持向量的个数，而虽然没有固定的比例，但支持向量的个数多少也和训练集的大小有关。
数值解就是可以使用的解，是一个一个的数，往往都是近似解。求数值解的过程非常像穷举法，从一个数开始，试一试它当解效果怎样，不满足一定条件（叫做停机条件，就是满足这个以后就认为解足够精确了，不需要继续算下去了）就试下一个，当然下一个数不是乱选的，也有一定章法可循。有的算法，每次只尝试一个数，有的就尝试多个，而且找下一个数字（或下一组数）的方法也各不相同，停机条件也各不相同，最终得到的解精度也各不相同，可见对求数值解的复杂度的讨论不能脱开具体的算法。
一个具体的算法，Bunch-Kaufman训练算法，典型的时间复杂度在O(Nsv3+LNsv2+dLNsv)和O(dL2)之间，其中Nsv是支持向量的个数，L是训练集样本的个数，d是每个样本的维数（原始的维数，没有经过向高维空间映射之前的维数）。复杂度会有变化，是因为它不光跟输入问题的规模有关（不光和样本的数量，维数有关），也和问题最终的解有关（即支持向量有关），如果支持向量比较少，过程会快很多，如果支持向量很多，接近于样本的数量，就会产生O(dL2)这个十分糟糕的结果（给10，000个样本，每个样本1000维，基本就不用算了，算不出来，呵呵，而这种输入规模对文本分类来说太正常了）。
　　这样再回头看就会明白为什么一对一方法尽管要训练的两类分类器数量多，但总时间实际上比一对其余方法要少了，因为一对其余方法每次训练都考虑了所有样本（只是每次把不同的部分划分为正类或者负类而已），自然慢上很多。

%matplotlib inline

训练分类器

就是这个。您已经了解了如何定义神经网络，计算损耗并更新网络权重。

现在你可能在想

数据怎么样？

通常，当您必须处理图像，文本，音频或视频数据时，您可以使用标准的python包将数据加载到numpy数组中。然后你可以将这个数组转换成一个torch.*Tensor。

• 对于图像，Pillow，OpenCV等软件包很有用
• 对于音频，包括scipy和librosa
• 对于文本，无论是原始Python还是基于Cython的加载，还是NLTK和SpaCy都很有用
  特别是对于视觉，我们创建了一个名为的包 torchvision，其中包含用于常见数据集的数据加载器，如Imagenet，CIFAR10，MNIST等，以及用于图像的数据转换器，即 torchvision.datasets和torch.utils.data.DataLoader。

这提供了极大的便利并避免编写样板代码。

在本教程中，我们将使用CIFAR10数据集。它有类：‘飞机’，‘汽车’，‘鸟’，‘猫’，‘鹿’，‘狗’，‘青蛙’，‘马’，‘船’，‘卡车’。CIFAR-10中的图像尺寸为3x32x32，即尺寸为32x32像素的3通道彩色图像。

cifar10

训练图像分类器

我们将按顺序执行以下步骤：

• 使用加载和标准化CIFAR10训练和测试数据集 torchvision
• 定义卷积神经网络
• 定义损失函数
• 在训练数据上训练网络
• 在测试数据上测试网络

加载和标准化CIFAR10

使用torchvision，加载CIFAR10非常容易。

import torch
import torchvision
import torchvision.transforms as transforms

torchvision数据集的输出是范围[0,1]的PILImage图像。我们将它们转换为归一化范围的张量[-1,1]

transform = transforms.Compose(
    [transforms.ToTensor(),
     transforms.Normalize((0.5, 0.5, 0.5), (0.5, 0.5, 0.5))])

trainset = torchvision.datasets.CIFAR10(root='./data', train=True,##数据集的数据加载器，train=True时使用训练集，False时为使用测试集
                                        download=True, transform=transform)##获取分类任务所需要的数据集，transform给输入图像施加变换
trainloader = torch.utils.data.DataLoader(trainset, batch_size=4,
                                          shuffle=True, num_workers=2)

testset = torchvision.datasets.CIFAR10(root='./data', train=False,
                                       download=True, transform=transform)
testloader = torch.utils.data.DataLoader(testset, batch_size=4,
                                         shuffle=False, num_workers=2)

classes = ('plane', 'car', 'bird', 'cat',
           'deer', 'dog', 'frog', 'horse', 'ship', 'truck')

Downloading http://www.cs.toronto.edu/~kriz/cifar-10-python.tar.gz to ./data\cifar-10-python.tar.gz
Files already downloaded and verified

让我们展示一些训练图像，以获得乐趣。

import matplotlib.pyplot as plt
import numpy as np

# functions to show an image


def imshow(img):
    img = img / 2 + 0.5     # unnormalize
    npimg = img.numpy()
    plt.imshow(np.transpose(npimg, (1, 2, 0)))
    plt.show()


# get some random training images
dataiter = iter(trainloader)
images, labels = dataiter.next()

# show images
imshow(torchvision.utils.make_grid(images))
# print labels
print(' '.join('%5s' % classes[labels[j]] for j in range(4)))

[外链图片转存失败(img-tdbXaAP1-1568109363235)(output_7_0.png)]

 ship plane  ship  deer

定义卷积神经网络

从神经网络部分复制神经网络并修改它以获取3通道图像（而不是定义的1通道图像）。

import torch.nn as nn
import torch.nn.functional as F


class Net(nn.Module):
    def __init__(self):
        super(Net, self).__init__()
        self.conv1 = nn.Conv2d(3, 6, 5)
        self.pool = nn.MaxPool2d(2, 2)
        self.conv2 = nn.Conv2d(6, 16, 5)
        self.fc1 = nn.Linear(16 * 5 * 5, 120)
        self.fc2 = nn.Linear(120, 84)
        self.fc3 = nn.Linear(84, 10)

    def forward(self, x):
        x = self.pool(F.relu(self.conv1(x)))
        x = self.pool(F.relu(self.conv2(x)))
        x = x.view(-1, 16 * 5 * 5)
        x = F.relu(self.fc1(x))
        x = F.relu(self.fc2(x))
        x = self.fc3(x)
        return x


net = Net()

定义Loss函数和优化器

让我们使用分类交叉熵损失和SGD动量。

import torch.optim as optim

criterion = nn.CrossEntropyLoss()
optimizer = optim.SGD(net.parameters(), lr=0.001, momentum=0.9)

训练网络

事情开始变得有趣了。我们只需循环遍历数据迭代器，并将输入提供给网络并进行优化。

for epoch in range(2):  # loop over the dataset multiple times

    running_loss = 0.0
    for i, data in enumerate(trainloader, 0):
        # get the inputs; data is a list of [inputs, labels]
        inputs, labels = data

        # zero the parameter gradients
        optimizer.zero_grad()

        # forward + backward + optimize
        outputs = net(inputs)
        loss = criterion(outputs, labels)
        loss.backward()
        optimizer.step()

        # print statistics
        running_loss += loss.item()
        if i % 2000 == 1999:    # print every 2000 mini-batches
            print('[%d, %5d] loss: %.3f' %
                  (epoch + 1, i + 1, running_loss / 2000))
            running_loss = 0.0

print('Finished Training')

[1,  2000] loss: 2.168
[1,  4000] loss: 1.833
[1,  6000] loss: 1.693
[1,  8000] loss: 1.589
[1, 10000] loss: 1.527
[1, 12000] loss: 1.488
[2,  2000] loss: 1.418
[2,  4000] loss: 1.371
[2,  6000] loss: 1.355
[2,  8000] loss: 1.331
[2, 10000] loss: 1.300
[2, 12000] loss: 1.292
Finished Training

在测试数据上测试网络

我们已经在训练数据集上训练了2次。但我们需要检查网络是否已经学到了什么。

我们将通过预测神经网络输出的类标签来检查这一点，并根据地面实况进行检查。如果预测正确，我们将样本添加到正确预测列表中。

好的，第一步。让我们从测试集中显示一个图像以熟悉。

dataiter = iter(testloader)
images, labels = dataiter.next()

# print images
imshow(torchvision.utils.make_grid(images))
print('GroundTruth: ', ' '.join('%5s' % classes[labels[j]] for j in range(4)))

[外链图片转存失败(img-NPfLQZwH-1568109363236)(output_15_0.png)]

GroundTruth:    cat  ship  ship plane

好的，现在让我们看看神经网络认为上面这些例子是什么：

outputs = net(images)

输出是10类的精度。一个类的精度越高，网络认为图像是特定类的越多。那么，让我们得到最高精度的指数：

_, predicted = torch.max(outputs, 1)

print('Predicted: ', ' '.join('%5s' % classes[predicted[j]]
                              for j in range(4)))

Predicted:    cat  ship  ship  ship

结果似乎很好。

让我们看看网络如何在整个数据集上执行。

correct = 0
total = 0
with torch.no_grad():
    for data in testloader:
        images, labels = data
        outputs = net(images)
        _, predicted = torch.max(outputs.data, 1)
        total += labels.size(0)
        correct += (predicted == labels).sum().item()

print('Accuracy of the network on the 10000 test images: %d %%' % (
    100 * correct / total))

Accuracy of the network on the 10000 test images: 52 %

这看起来好于偶然，这是10％的准确性（从10个班级中随机挑选一个班级）。似乎网络学到了一些东西。

嗯，什么是表现良好的类，以及表现不佳的类：

class_correct = list(0. for i in range(10))
class_total = list(0. for i in range(10))
with torch.no_grad():
    for data in testloader:
        images, labels = data
        outputs = net(images)
        _, predicted = torch.max(outputs, 1)
        c = (predicted == labels).squeeze()
        for i in range(4):
            label = labels[i]
            class_correct[label] += c[i].item()
            class_total[label] += 1


for i in range(10):
    print('Accuracy of %5s : %2d %%' % (
        classes[i], 100 * class_correct[i] / class_total[i]))

Accuracy of plane : 34 %
Accuracy of   car : 43 %
Accuracy of  bird : 38 %
Accuracy of   cat : 39 %
Accuracy of  deer : 57 %
Accuracy of   dog : 57 %
Accuracy of  frog : 58 %
Accuracy of horse : 55 %
Accuracy of  ship : 73 %
Accuracy of truck : 67 %

之前说要用SVM实现表情识别来着，所以找个简单例子练练手。

惯例开始放结果，实现结果如下：

//这里简单对四个点分了四类，图片显示得很直观。

//支持向量总共6个。

//最后测试了两个点进行分类。

只需要配置好Opencv3的环境即可运行。

这里用到的是cv::SVM, 老版本Opencv2410之前用的是CvSvm,推荐用最新的Opencv310。

下面就是简单粗暴的代码啦：

#include<opencv2\opencv.hpp> 

using namespace std;
using namespace cv;
using namespace cv::ml;

int main()
{


	//训练需要用到的数据
	int 标签[4] = { 1, 2, 3, 4 };
	float 训练数据[4][2] = { { 31, 12 },{ 65, 220 },{ 440, 350 },{ 400, 400 } };
	//转为Mat以调用
	Mat 训练Mat(4, 2, CV_32FC1, 训练数据);
	Mat 标签label(4, 1, CV_32SC1, 标签);
	//训练的初始化
	Ptr<SVM> svm = SVM::create();
	svm->setType(SVM::C_SVC);
	svm->setKernel(SVM::LINEAR);
	svm->setTermCriteria(TermCriteria(TermCriteria::MAX_ITER, 100, 1e-6));
	//开始训练
	svm->train(训练Mat, ROW_SAMPLE, 标签label);

	//-----------无关紧要的美工的部分-----------------------	
	//----其实对每个像素点的坐标也进行了分类----------------
	int 宽 = 512, 高 = 512;
	Mat 演示图片 = Mat::zeros(高, 宽, CV_8UC3);
	Vec3b green(0, 255, 0), blue(255, 0, 0), red(0, 0, 255), black(0, 0, 0);
	for (int i = 0; i < 演示图片.rows; ++i)
		for (int j = 0; j < 演示图片.cols; ++j)
		{
			Mat sampleMat = (Mat_<float>(1, 2) << j, i);
			float response = svm->predict(sampleMat);

			if (response == 1)
				演示图片.at<Vec3b>(i, j) = green;
			else if (response == 2)
				演示图片.at<Vec3b>(i, j) = blue;
			else if (response == 3)
				演示图片.at<Vec3b>(i, j) = red;
			else if (response == 4)
				演示图片.at<Vec3b>(i, j) = black;
		}
	//--------把初始化训练的点画进图片------------
	int thickness = -1;
	int lineType = 8;
	for (int 画点 = 0; 画点 < sizeof(标签) / sizeof(int); 画点++) {
		circle(演示图片, Point(训练数据[画点][0], 训练数据[画点][1]), 10, Scalar(255, 255, 255), thickness, -1);
	}
	// 把 support vectors  cout粗来看看……
	Mat sv = svm->getSupportVectors();
	cout << "Support Vectors为：" << endl;
	for (int i = 0; i < sv.rows; ++i)
	{
		const float* v = sv.ptr<float>(i);
		cout << v[0] << " " << v[1] << endl;
	}

	//测试测试

	Mat 结果;
	float teatData[2][2] = { { 20, 11 },{ 310, 411 } };
	Mat query(2, 2, CV_32FC1, teatData);

	svm->predict(query, 结果);
	cout << "分类结果为：" << endl;
	cout << 结果;
	imshow("SVM显示", 演示图片);
	waitKey(-1);

}