python计算机视觉学习-图像内容分类 计算机视觉

python计算机视觉学习图像内容分类

图像内容分类

8.1K邻近分类法KNN

概述：K最近邻(k-NearestNeighbor,KNN),指导思想是“近朱者赤，近墨者黑”，由你的邻居来推断出你的类别。

原理：从训练集中找到和新数据最接近的k条记录，然后根据多数类来决定新数据类别，本质上，KNN是使用距离来计算相似度。

算法涉及3个主要因素：训练数据集；距离或相似度的计算衡量；k的大小。

已知两类“先验”数据，分别是蓝方块和红三角，他们分布在一个二维空间中；有一个未知类别的数据(绿点)，需要判断它是属于"蓝方

块”还是“红三角”类；考察离绿点最近的3个(或k个)数据点的类别，占多数的类别即为绿点判定类别。

计算步骤

1.算距离：给定测试对象，计算它与训练集中的每个对象的距离；

2.找邻居：圈定距离最近的k个训练对象，作为测试对象的近邻；

3.做分类：根据这k个近邻归属的主要类别，来对测试对象分类。

相似度的衡量

距离越近应该意味着这两个点属于一个分类的可能性越大。

距离不能代表一切，有些数据的相似度衡量并不适合用距离。

相似度衡量方法：包括欧式距离、夹角余弦等。

简单应用中，一般使用欧氏距离，但对于文本分类来说，使用余弦(cosine)来计算相似度就比欧式(Euclidean)距离更合适。

类别判定

简单投票法：少数服从多数，近邻中哪个类别的点最多就分为该类。

加权投票法：根据距离的远近，对近邻的投票进行加权，距离越近则权重越大(权重为距离平方的倒数)

实现最基本的KNN形式非常简单。给定训练样本集和对应的标记列表，下面的代码可以用来完成这一工作。这些训练样本和标记可以在一

个数组里成行摆放或者干脆摆放列表里，训练样本可能是数字、字符串等任何你喜欢的形状。将定义的类对象添加到名为的文件里：

classKnnClassifier(object):

def_init_(self,labels,samples):

使用训练数据初始化分类器…

self.labels=labels

self.samples=samples

defclassify(self,point,k=3):

…在训练数据上采用k近邻分类，并返回标记"""

#计算所有训练数据点的距离

dist=array([L2dist(point,s)forsinself.samples])

#对它们进行排序

ndx=dist.argsort()

#用字典存储k近邻

votes={}

foriinrange(k):

label=self.labels[ndx[i]]

votes.setdefault(label,0)

votes[label]+=1

returnmax(votes)

defL2dist(p1,p2):

returnsqrt(sum((p1-p2)**2))

定义一个类并用训练数据初始化非常简单；每次想对某些东西进行分类时，用KNN方法，我们就没有必要存储并将训练数据作为参数来传

递。用一个字典来存储邻近标记，我们便可以用文本字符串或数字来表示标记。

8.1.1一个简单的二维示例

首先建立一些简单的二维示例数据集来说明并可视化分类器的工作原理，下面的脚本将创建两个不同的二维点集，每个点集有两类，用

Pickle模块来保存创建的数据：

fromnumpy.randomimportrandn

importpickle

#创建二维样本数据

n=200

#两个正态分布数据集

class_1=0.6*randn(n,2)

class_2=1.2*randn(n,2)+array([5,1])

labels=hstack((ones(n),-ones(n)))

#用Pickle模块保存

withopen('points_normal.pkr,'w')asf:

pickle.dump(class_1,f)

pickle.dump(class_2,f)

pickle.dump(labels,f)

#正态分布,并使数据成环绕状分布

class_1=0.6*randn(n,2)

r=0.8*randn(n,1)+5

angle=2*pi*randn(n,1)

class_2=hstack((r*cos(angle),r*sin(angle)))

labels=hstack((ones(n),-ones(n)))

#用Pickle保存

withopen('points_ring.pkr,'w')asf:

pickle.dump(class_1,f)

pickle.dump(class_2,f)

pickle.dump(labels,f)

用不同的保存文件名运行该脚本两次，例如第一次用代码中的文件名进行保存，第二次将代码中的points_normal_tpkl和

points_ring_pkl分别改为points_normal_test.pkl和points_ring_testpkl进行保存。你将得到4个二维数据集文件，每个分布都有两

个文件，我们可以将一个用来训练，另一个用来做测试。

#coding:utf-8

importpickle

fromPCV.classifiersimportknn

fromPCV.toolsimportimtools

frompylabimport*

fromnumpyimport*

withopen('points_normal_t.pkr,'r')asf:

class_1=pickle.load(f)

class_2=pickle.load(f)

labels=pickle.load(f)

model=knn.KnnClassifier(labels,vstack((class_1,class_2)))

withopen('points_normal_test.pkl','r')asf:

class_1=pickle.load(f)

class_2=pickle.load(f)

labels=pickle.load(f)

printmodel.classify(class_1[0])

#定义绘图函数

defclassify(x,y,model=model):

returnarraydmodel.classifydxx.yy])for(xx,yy)inzip(x,y)])

#绘制分类边界

imtools.plot_2D_boundary([-6,6,-6,6],[class_1,class_2],classify,[1,-1])

show()

在控制台上打印第一个数据点估计出来的类标记。

1.0

创建了一个简短的辅助函数以获取x和y二维坐标数组和分类器，并返回

一个预测的类标记数组。现在我们把函数作为参数传递给实际的绘图函数。把下面

的函数添加到文件imtools中：

defplot_2D_boundary(plot_range,points,decisionfcn,labels,values=[0]):

""TIoLrange为(xmin,xmax,ymin,ymax),points是类数据点列表，

decisionfcn是评估函数，labels是函数decidionfcn关于每个类返回的标记列表

clist=['b'/r'/g'/k'/m','/]#不同的类用不同的颜色标识

#在一个网格上进行评估，并画出决策函数的边界

x=arange(plot_range[0],plot_range[1],.1)

y=arange(plot_range[2],plot_range[3],.1)

xx,yy=meshgrid(x.y)

xxx,yyy=xx.flatten(),yy.flatten()#网格中的x,y坐标点列表

zz=array(decisionfcn(xxx,yyy))

zz=zz.reshape(xx.shape)

#以values画出边界

contour(xx,yy,zz,values)

#对于每类，用*画出分类正确的点，用。画出分类不正确的点

foriinrange(len(points)):

d=decisionfcn(points[i][:,0],points[i][:,1])

correct_ndx=labels[i]==d

incorrect_ndx=labels[i]!=d

plot(points[iMcorrect_ndx,0],points[i][correct_ndx,1J,*,color=clist[i])

plot(points[i][incorrect_ndx,OLpoints[i][incorrect_ndxjro',color=clist[i])

axis('equal')

4-

示例中，不同颜色代表类标记，正确分类的点用星号表示，分类错误的点用圆点表示，曲线是分类器的决策边界。正如所看到的，kNN决

策边界适用于没有任何明确模型的类分布。

8.1.2用稠密的SIFT作为图像特征

在整幅图像上用一个规则的网格应用SIFT描述子可以得到稠密SIFT的表示形式通过添加一些额外的参数来得到稠密SIFT特征。创建一

个名为的文件，并添加下面代码到该文件中：

importsift

defprocess_image_dsift(imagename,resultname,size=20,steps=10,

force_orientation=False,resize=None):

…用密集采样的SIFT描述子处理一幅图像，并将结果保存在一个文件中。可选的输入:

特征的大小size,位置之间的步长steps,是否强迫计算描述子的方位force_orientation

(False表示所有的方位都是朝上的)，用于调整图像大小的元组加"

im=Image.open(imagename).convert(,L')

ifresize!=None:

im=im.resize(resize)

m,n=im.size

ifimagename[3:]!='pgm':

#创建一个pgm文件

im.save('tmp.pgm')

imagename='tmp.pgm'

#创建帧，并保存到临时文件

scale=size/3.0

x,y=meshgrid(range(steps,m,steps),range(steps,n,steps))

xx,yy=x.flatten(),y.flatten()

frame=array([xx,yy,scale*ones(xx.shape⑼),zeros(xx.shape⑼)])

savetxt('tmp.frame',frame.T,fmt='%03.3f')

ifforce_orientation:

cmmd=str("sift"+imagename+"-output=M+resultname+

"-read-frames=tmp.frame-orientations")

else:

cmmd=str("sift"+imagename+"-output=,,+resultname+

"-read-frames=tmp.frame,')

os.system(cmmd)

print'processed',imagename,'to',resultname

对比process_image()函数，为了使用命令行处理，我们用savetxt()函数

将帧数组存储在一个文本文件中，该函数的最后一个参数可以在提取描述子之前对

图像的大小进行调整，例如，传递参数imsize=(100,100)会将图像调整为100x100

像素的方形图像。最后，如果force_orientation为真，则提取出来的描述子会基于

局部主梯度方向进行归一化；否则，则所有的描述子的方向只是简单地朝上。

在一幅图像上应用稠密SIFT描述子的例子

可视化代码：

fromPCV.Iocaldescriptorsimportds说,sift

fromnumpyimport*

fromPILimportImage

frompylabimport*

cessJmage-dsiftCshangdalou.jpg'/shangdalou.sift'.SO.AOJrue)

l.d=sift.readjeaturesjromjilefshangdalou.sift')

im=array(lmage.open('shangdalou.jpg,))

sift.plot_features(im,l,True)

show()

而

目

“

dtd*A「

「

it。U

启.！«

：

”

胃

H&：

“

启7t;«

1i・

H“

[€»二

皆

启r&5-

H”

u-4>b？

启1'•

“

)以T

.|“L

，

启?l

II-T16H»1J

I启:t6l"N*.1Bml

"“6%w

启

>g:r二u3.,&,»

M-昼

启vfE•

:|」

.uotv:?=-

•t?:r>»1

江

[€*・<^|mtrm

•nk:):i

・

『»

!?•1l

启.;'»

倡!!>x

广

E:■■)”1^Bwl

启^

：

门

■<rr蔓

启RJ»

:>“

eJ*l,

;0一

ls5■'*>:4

■亘v«»!

!?tl/1:,''

一"»•

“.

TI?«|.:

!£"««?»

[€露»

唬

-"

8.1.3图像分类：手势2“识别

计算手势图像稠密SIFT描述子，并可视化:

#coding:utf-8

importos

fromPCV.localdescriptorsimportsift,dsift

frompylabimport*

fromPILimportImage

imlist=['D-/uniform/train/C-uniform01.ppm1,'D:/uniform/train/B-uniform01.ppm',

'D:/uniform/train/A-uniform01.ppm','D:/uniform/train/Five-uniform01.ppm1,

'Di/uniform/train/Point-uniformOI.ppm','Di/uniform/train/V-uniformOI.ppm']

figure。

fori,iminenumerate(imlist):

print(im)

cessJmage_dsift(im,im[:-3]+'dsift',50,20,Tnje)

I,d=sift.read_features_from_file(im[:-3]+'dsift')

dirpath,filename=os.path.split(im)

im=array(lmage.open(im))

#显示手势含义title

titlename=filename[:-14]

subplot(2,3,i+1)

sift.plot_features(im,ltTrue)

title(titlename)

show()

#--coding:utf-8--

fromPCV.localdescriptorsimportdsift

importos

fromPCV.localdescriptorsimportsift

frompylabimport*

fromPCV.classifiersimportknn

defgetjmagelist(path):

"""Returnsalistoffilenamesfor

alljpgimagesinadirectory.""M

return[os.path.join(path,f)forfinos.listdir(path)iff.endswith('.ppm')]

defread_gesture_features_labels(path):

#createlistofallfilesendingin.dsift

featlist=[os.path.join(path,f)forfinos.listdir(path)iff.endswithf.dsift')]

#readthefeatures

features=0

forfeatfileinfeatlist:

Ld=sift.read_features_from_file(featfile)

features.append(d.flatten())

features=array(features)

#createlabels

labels=[featfile.split(7')[-1][O]forfeatfileinfeatlist]

returnfeatures,array(labels)

defprint_confusion(res,labels,classnames):

n=len(classnames)

#confusionmatrix

class_ind=dict([(classnames[i],i)foriinrange(n)])

confuse=zeros((n,n))

foriinrange(len(test_labels)):

confuse[class_ind[res[i]],classjnd[test_labels[i]]]+=1

print'Confusionmatrixfor'

printclassnames

printconfuse

filelist_train=getJmagelistCDzWuniformWtrain')

filelist_test=getJmagelist(*D:\\uniformWtest)

imlist=filelist_train+filelist_test

#processimagesatfixedsize(50,50)

forfilenameinimlist:

featfile=filename[:-3]+,dsift,

cess_image_dsift(filename,featfile,10,5,resize=(50,50))

features,labels=read_gesture_features_labels('D:\\uniform\\train\\')

testjeatures,test_labels=read_gesture_features_labels('D:\\uniform\\test\\')

classnames=unique(labels)

#testkNN

k=1

knn_classifier=knn.KnnClassifier(labels,features)

res=array([knn_classifier.classify(test_features[i],k)foriin

range(len(test_labels))])

#accuracy

acc=sum(1.O*(res==test_labels))/len(testjabels)

print'Accuracy:',acc

print_confusion(res,test_labels,classnames)

用训练数据及其标记作为输入，创建分类器对象；然后，我们在整个测试集

上遍历并用classifyO方法对每幅图像进行分类。将布尔数组和1相乘并求和，可

以计算出分类的正确率。由于该例中真值为1,所以很容易计算出正确分类数。它

应该会打印出一个类似下面的结果：

0.811518324607

这说明该例中有81%的图像是正确的。该结果会随k值及稠密SIFT图像描述子参

数的选择而变化。

而控制台输出结果不理想，有待解决。

(,Accurajr：*,1.0)

Confusionmatrixfor

CD']

[[382.]]

8.2贝叶斯分类器

朴素贝叶斯分类器是分类算法集合中基于贝叶斯理论的一种算法。它不是单一存在的，而是一个算法家族，在这个算法家族中它们都有共同

的规则。例如每个被分类的特征对与其他的特征对都是相互独立的。

开始之前，先看一下数据集。

这是一个虚构的数据集，这个数据集描述的是天气是否适合打高尔夫球。已知天气情况，每个元组都分成合适（“Yes”）或者不合适

（“NO”）打高尔夫。

下面的截图就是表示的数据集表格：

OutlookTemperatureHumidityWindyPlaygolf

0RainyHotHighFalseNo

1RainyHotHighTrueNo

2OvercastHotHighFalseYes

3SunnyMiklHighFalseYes

4SunnyCoolNormalFalseYes

5SunnyCoolNormalTrueNo

6OvercastCoolNormalTrueYes

7RainyMildHighFalseNO

8RainyCOOINormalFalseYes

9SunnyMildNormalFalseYes

10RainyMildNormalTrueYes

11OvercastMildHighTrue微

数据集分为两个部分，也就是说，特征矩阵（featurematrix）和响应向量（responsevector）<.

1.特征矩阵包含数据集中所有的向量（行），每个向量是由依赖特征组成的。在上面的数据集中，特征就是“天气"，“温度”，“湿

度”还有“刮风”。

2.响应向量包含的是特征矩阵每一行的类变量（预测或者输出）值。在上述的数据集中，类变量名为Tlaygolf"0

假设

朴素贝叶斯基础假设是，对于每一个特征都有：独立，相等

与我们的数据集关联起来，我们可以这样理解这个概念：

1,我们假设没有特征对是相互依赖的。温度热不热跟湿度没有任何关系，天气是否下雨也不影响是否刮风。因此，这就是假设特征相互独

立。

2,其次，每个特征都有相同的权重（或者是重要性）。例如，只知道温度和湿度是不能准确地推断出结果的。任何属性都与结果是有关系

的，并且影响程度是相同的。

注意：如果在现实情况中，这个假设就使得朴素贝叶斯不能一般性地正确了。实际上独立这个假设就根本不可能成立，但是又往往在实践中

能够很方便地计算。

贝叶斯理论

贝叶斯理论指的是，根据一个已发生事件的概率，计算另一个事件的发生概率。贝叶斯理论从数学上的表示可以写成这样：

P"网=产田⑷P⑷

在这里A和B都是事件，概率非0。

1,基本上，只要我们给出了事件B为真，那么就能算出事件A发生的概率，事件B也被称为证据。

2,P(A)是事件A的先验(先验概率，例如,在证据之前发生的概率)。证据是一个未知事件的一个属性值(在这里就是事件B)。

3,P(A|B)是B的后验概率，例如在证据之后发生的概率。

现在再考虑一下我们的数据集，我们可以这样用贝叶斯理论：

在这里y是类变量，X是依赖特征向量(大小为n):

为了更加清晰点，我们这个例子的特征向量和相关类变量是(数据集的第一行)：

X=(Rainy,Hot,High,False)

y=No

朴素假设

现在是时候为贝叶斯理论添加假设了，也就是每个特征之间都是相互独立的。所以我们可以将证据分成每个独立的部分。

如何两个事件A和B是相互独立的，那么有：

D/4r>\_D/4XD/r>\

因此我们可以得到以下结果:

尸(司1/)尸(nM)…尸(小松)尸(y)

尸你…,H”)=

于是又可以写成:

D/-.IJ\尸(M叫1PgM

因为分母与输入数据是常量相关的，所以我们可以除去这一项:

现在我们需要建立一个分类模型，我们用已知的类变量y的所有可能的值计算概率，并选择输出概率是最大的结果。数学表达式可以这么

写：

所以最后剩下的只有P(y)P(y)与P(xi|y)P(xi|y)的计算了。

请注意：P(y)也被称为类概率，P(xi|y)也被称为条件概率。

不同的朴素贝叶斯分类器差异主要在P(xi|y)分布的假设。

我们试着将上面的式子用在天气数据集上。这样，我们先对数据集做一些预处理。

我们得求出每一个X中的Xi,y中的yi。所有这些计算都被列在了下面的表格中:

直到现在我们已经完成了预处理工作，分类器也准备好了。

所以玩高尔夫的概率是：

P(SunnuOutlook\Yes)P(Ho^rcmpcrature\Yes)P(NormalHumiditv\Yes)P(NoWi7id\Yes)P(Yc3)

不打高尔夫的概率是:

D，-P(SuimyOutlook\No)P(HotTcmpcraturcNo)P(NormalUuniidity\No)P(NoWiiid\No)P(No)

22669

P(Yes\today)a0.0141

yjyj

P(No\today);xt.看.:1.工a0.0068

因为

P(Yes\today)4-P(No\today)=1

所以这些数字可以做一下归T：

0.0141

P{Yes\today)==0.67

0.01414-0.0068

.0.0068-co

代NolSd*=0.0141+0.0068=033

因为

(Yes\today)>P(No\today)

上述讨论的方法只能应用在离散数据上。如果是连续数据的话，我们需要对每个特征数据的分布做一些假设。

该分类器是通过将各个特征的条件概率相乘得到一个类的总概率，然后选取概率最

高的那个类构造出来的。使用高斯概率分布模型的贝叶斯分类器基本实现，也就是用从

训练数据集计算得到的特征均值和方差来对每个特征单独建模。把下面的Bayes

Classifier类添加到文件中：

DlassBayesClassifier(object):

def_init_(self):

…使用训练数据初始化分类器…

self.labels=[]#类标签

self.mean=[]#类均值

self.var=[]#类方差

self.n=0#类别数

deftrain(self,data,labels=None):

…在数据data(nxdim的数组列表)上训练，标记labels是可选的，默认为0…n-1

iflabels==None:

labels=range(len(data))

self.labels=labels

self.n=len(labels)

forcindata:

self.mean.append(mean(c,axis=O))

self.var.append(var(c,axis=O))

defclassify(self,points):

…通过计算得出的每一类的概率对数据点进行分类，并返回最可能的标记…

#计算每一类的概率

est_prob=array([gauss(m,v,points)form,vinzip(self.mean,self.var)])

#获取具有最高概率的索引，该索引会给出类标签

ndx=est_prob.argmax(axis=0)

estjabels=array([self.labels[n]forninndx])

returnestjabels,est_prob

该模型每一类都有两个变量，即类均值和协方差。train。方法获取特征数组列表

（每个类对应一个特征数组），并计算每个特征数组的均值和协方差。classifyO方

法计算数据点构成的数组的类概率，并选概率最高的那个类，最终返回预测的类标

记及概率值，同时需要一个高斯辅助函数：

defgauss(m,v,x):

用独立均值m和方差v评估d维高斯分布…

iflen(x.shape)==1:

n,d=1,x.shape[0]

else:

n,d=x.shape

#协方差矩阵，减去均值

S=diag(1/v)

x=x-m

#概率的乘积

y=exp(-0.5*diag(dot(x,dot(S,x.T))))

#归一化并返回

jeturny*(2*pi)**(-d/2.0)/(sqrt(prod(v))+1e-6)

该函数用来计算单个高斯分布的乘积，返回给定一组模型参数m和v的概率

在脚本中载入二维数据，并训练出一个分类器

importpickle

fromPCV.classifiersimportbayes

fromPCV.toolsimportimtools

frompylabimport*

withopen('points_normal_t.pkr,71)asf:

class]=pickle.load(f)

class_2=pickle.load(f)

labels=pickle.load(f)

be=bayes.BayesClassifier()

bc.train([class_1,class_2],[1.-1])

withopen('points_normal_test.pkl','r')asf:

class_1=pickle.load(f)

class_2=pickle.load(f)

labels=pickle.load(f)

printbc.classify(class_1[:10])[0]

defclassify(x,y,bc=bc):

points=vstack((x,y))

returnbc.classify(points.T)[0]

imtools.plot_2D_boundary([-6,6,-6,6],[class_1,class_2],classify,[1,-1])

show()

该脚本会将前10个二维数据点的分类结果打印输出到控制台，输出结果如下:

estprob(2L,10L)[1,

[1111111111]

estprob(2L,14400L)[1,-1]

estprob(2L,200L)[1一

estprob(2L,200L)[1,^1]

___________

用贝叶斯分类器对二维数据进行分类。每个例子中的颜色代表了类标记。正确分类

的点用星号表示，误错分类的点用圆点表示，曲线是分类器的决策边界

8.3支持向量机

支持向量机(supportvectormachines)是一种二分类模型，它的目的是寻找一个超平面来对样本进行分割，分割的原则是间隔最大

化，最终转化为一个凸二次规划问题来求解。

给定训练样本集D=(xl,yl),(x2,y2),…,(xm,ym)D=(xl,yl),(x2,y2),…,(xm,ym),其中讨€{—1,+1汹曰一1,+1),分类学习最基本的想

法就是基于训练集D在样本空间中找到一个划分超平面，将不同类别的样本分开。

直观看上去，能将训练样本分开的划分超平面有很多，但应该去找位于两类训练样本“正中间”的划分超平面，即图中红色的那条，因为该

划分超平面对训练样本局部扰动的“容忍”性最好，例如，由于训练集的局限性或者噪声的因素，训练集外的样本可能比图中的训练样本更

接近两个类的分隔界，这将使许多划分超平面出现错误。而红色超平面的影响最小，简言之，这个划分超平面所产生的结果是鲁棒性的。

那什么是线性可分呢?

如果一个线性函数能够将样本分开，称这些数据样本是线性可分的。那么什么是线性函数呢？其实很简单，在二维空间中就是一条直线，在

三维空间中就是一个平面，以此类推，如果不考虑空间维数，这样的线性函数统称为超平面。我们看一个简单的二维空间的例子，0代表正

类，X代表负类，样本是线性可分的，但是很显然不只有这一条直线可以将样本分开，而是有无数条，我们所说的线性可分支持向量机就对

应着能将数据正确划分并且间隔最大的直线。

为什么要间隔最大?

一般来说，一个点距离分离超平面的远近可以表示分类预测的确信度，如图中的AB两个样本点，B点被预测为正类的确信度要大于A点，所

以SVM的目标是寻找一个超平面，使得离超平面较近的异类点之间能有更大的间隔，即不必考虑所有样本点，只需让求得的超平面使得离

它近的点间隔最大。

怎么计算间隔?

只有计算出了间隔，才能使得间隔最大化。在样本空间中，划分超平面可通过如下线性方程来描述：

印7工+*=0

其中W为法向量，决定了超平面的方向，b为位移量，决定了超平面与原点的距离。

假设超平面能将训练样本正确地分类，即对于训练样本(xi,yi),满足以下公式：

防=+1

该公式被称为最大间隔假设，yi=+l表示样本为正样本，yi=-l表示样本为负样本，式子前面选择大于等于+1,小于等于-1只是为了计算

-t■病尚Mill-HTZ旦/王言百将/口不；△旦幺八、新HTI、八鬲"，亦用/古甘%.1«n1小皿I-注八一空心工•

I元，，小川」-1-力以7EIH回不姒,IhiyLLbzE-57^,向】力/AffiA217dW口VX1大I丈兄十ITM_Io大H小J-以A工l守川J.

yi(WTXi4-6)>+1

如下图，距离超平面最近的这几个样本点满足yi(WTxi+b)=l,它们被称为“支持向量”。虚线称为边界，两条虚线间的距离称为间隔

(margin)。

关于间隔的计算：它就等于两个异类支持向量的差在W方向上的投影，W方向是指图所示实线的法线方向。

f1*(1八++6)=1,乂=+1

I•T,、««

所以有：

,“了工=1-3

得到：

TT号

(Z4_-T-)W1-64-144>,

至此，我们求得了间隔，SVM的思想是使得间隔最大化，也就是：

显然，最大化2/||w||相当于最小化||w||,为了计算方便，将公式转化成如下公式，它即为支持向量机的基本型:

mm|||TF||2

该基本型是一个凸二次规划问题，可以采用拉格朗日乘子法对其对偶问题求解求解，拉格朗日函数：

1冽

T/1...\LII一Il2....I...L\\/C、

对W,b求导可得

[5L白

5L3

—=?a也

令其分别为0,可得:

吊(9)

w

yav,=0(10)

将其带入拉格朗日函数(8)中，可得:

m|wm

a)=26一5ZZa,agy产再

I//-Ij»\