Chinaunix首页 | 论坛 | 博客

竹子

首页　| 　博文目录　| 　关于我

bl竹子

  • 博客访问： 488553
  • 博文数量： 25
  • 博客积分： 111
  • 博客等级： 民兵
  • 技术积分： 1279
  • 用 户 组： 普通用户
  • 注册时间： 2012-10-26 20:51
文章分类

全部博文（25）

文章存档

2014年（17）

2013年（8）

我的朋友
最近访客
推荐博文
相关博文
SVM总结及SMO简单实现

分类： 大数据

2014-05-22 16:57:16

在这篇博客中，我们首先简单的介绍SVM，包括：线性可分支持向量机、线性支持向量机和非线性支持向量机。之后，给出一个SMO的简单python实现代码。最后，给出我们简单的算法和scikit中的LinearSVC方法进行比较。

我们知道，在机器学习算法中用于分类问题的方法有很多，比如：logistic分类法、贝叶斯分类法等。他们都有一个共同特点就是：分类误差最小化。但是，分类误差最小化存在了两个问题：1、我们无法判断此次划分正确的数据的可信程度(这个与正确率是两个概念)；2、通过分类误差最小化，可能得到多个解(甚至无穷多个解)，我们无法判断这些解的好坏。因此，我们需要一个新方法可以解决上面的两个问题。于是，SVM就被开发出来了。首先了解下SVM是如何解决上面两个问题的，这也是SVM的核心思想:)。如下图：

如果仅仅已误差最小化进行划分，满足条件的直线有很多。同时，我们也无法判断A、B和C在此次划分中，哪个更可信。SVM为了解决这个问题，引入了间隔（margin）的概念，也就是A、B和C三点到直线的距离。我们通过上图可以清楚地看到，A的划分的可信性远大于B和C。SVM的主要思想就是：使各个点的价格最大化，这样就解决了上面的两个问题。如果，输入数据的特征大于二，那么的到的就不再是一条直线，一般叫它超平面。我们如何表示间隔这个量呢？从上图中我们可以看出，间隔就是点到直线的距离。于是，上面的问题可以转化为下面的优化问题：

上面的优化问题可以转化为如下形式：
具体的公式推导可以参看斯坦福公开课课件或李航的统计学习方法。上面的最优化问题其实就是一个凸二次规划问题。为了使我们的求解尽量的简单，我们一般会求解上述问题的对偶问题。我们将有如下解的形式：

最终，我们得到分类决策函数(中间省略了一些过程)：

其中，f(x)符号表示分类的准确性，而f(x)的大小反应可信的程度，并且是唯一的。这样一来，就解决了开始提出的两个问题。

上面就是线性可分支持向量机方法，但是这种方法很多时候得不到很好的结果。如下图所示：

上图就是无法用直线进行分割的。为了处理这种情形 ，人们对上面的优化问题进行了修改，即：加入了松弛和惩罚量。于是上面的最优化问题，变为了如下形式：

这种优化问题叫做线性支持向量机。我们可以看到，线性支持向量机的数据是一种近似现行可分的。它与线性可分支持向量机很相似。

然而，即使引入了松弛变量和惩罚量，能解决的问题也是非常有限的的。在实际情形中，还有很多情形与下图相似：



颜色不同的点，代表不同的类。为了处理这种情形，人们又引入了核函数的概念。简单来说核函数的作用就是一种内积映射，可能在当前的特种空间无法对数据进行线性分类 ，但是当将它映射到更高位的空间中之后，可能就可以很好的对数据进行划分。注意：核函数是一种比SVM应用更广泛的方法，例如：在局部线性加权回归中，就曾经用到过，见：http://blog.chinaunix.net/uid-28311809-id-4164781.html。这也就是，非线性可分支持向量机，它的求解过程与上面很相似，如下：

我们接下来，说一个重要的概念，就是支持向量。什么是支持向量呢，说白了就是一些点，它们到超平面的距离相等，且在所有节点中是最小的。如下图所示：

在虚线上的点就是支持向量，支持向量机就是在寻找这些点。

支持向量机，就简单的说这么多吧，下面简单的介绍下SMO。SMO又叫序列最小最优化方法。其基本思想就是，首先随机的选取两个变量，使它们发生变化，以便使优化函数不断变大，但是选取的两个变量的和保持不变。因为是凸规划问题，所以最终肯定收敛于最优解。这就像爬一座只有一个山头的山一样，只要你往上爬，最终肯定会走到山顶的。其过程与下图相似：

注意上图中的折线是与坐标轴平行的。SMO的详细过程可以参见斯坦福公开课或者李航的统计学习方法。下面，给出一个简单的实现代码(部分参照机器学习与实践一书)。

点击(此处)折叠或打开

  1. # -*- coding: utf-8 -*
  2. from numpy import *
  3. import pylab as pl
  4. class my_svm(object):
  5.     def __init__(self,filename,c=6,tol=0.001,miter=30):
  6.         self.filename = filename;
  7.         self.C = c;
  8.         self.tol = tol;
  9.         self.miter = miter;
  10.         self.support_vector = [];
  11.     def loadDataSet(self):
  12.         dataMat = []; labelMat = [];
  13.         fr = open(self.filename);
  14.         for line in fr.readlines():
  15.             lineArr = line.strip().split('\t');
  16.             dataMat.append([float(lineArr[0]), float(lineArr[1])]);
  17.             labelMat.append(float(lineArr[2]));
  18.         return mat(dataMat),mat(labelMat).transpose();
  19.     def rand_select_j(self,i):
  20.         j=i;
  21.         while j==i:
  22.             j = int(random.uniform (self.m));
  23.         return j;
  24.     def sample_svm(self):
  25.         '''alphs*Y*<X,Xi>+b'''
  26.         self.X,self.Y = self.loadDataSet();
  27.         self.m,self.n = shape(self.X);
  28.         self.alpha = mat(zeros((self.m,1)));
  29.         self.b=iter=0;
  30.         while iter<self.miter:
  31.             alpha_change=0;
  32.             for i in range(self.m):
  33.                 '''求解Xi的预测值和误差'''
  34.                 '''multiply和矩阵乘法是不一样的'''
  35.                 Xi = float(multiply(self.alpha,self.Y).T*(self.X*self.X[i,:].T))+self.b;
  36.                 err_i = Xi - float(self.Y[i]);
  37.                 if (err_i*self.Y[i]<-self.tol and self.alpha[i]<self.C) or (err_i*self.Y[i]>self.tol and self.alpha[i]>0):
  38.                     j = self.rand_select_j(i);
  39.                     '''随机选择另一个确定其误差，SMO的关键就是选择两个变量同时变化'''
  40.                     Xj = float(multiply(self.alpha,self.Y).T*(self.X*self.X[j,:].T))+self.b;
  41.                     err_j = Xj - float(self.Y[j]);
  42.                     alpha_i_old,alpha_j_old = self.alpha[i].copy(), self.alpha[j].copy();
  43.                     '''求解H和L'''
  44.                     if self.Y[i] == self.Y[j]:
  45.                         L = float(max(0,self.alpha[i]+self.alpha[j]-self.C));
  46.                         H = float(min(self.C,self.alpha[i]+self.alpha[j]));
  47.                     else:
  48.                         L = float(max(0,self.alpha[j]-self.alpha[i]));
  49.                         H = float(min(self.C,self.C+self.alpha[j]-self.alpha[i]));
  50.                     if L == H:
  51.                         continue;
  52.                     '''alpha的增量为：Y2*(err_1-err_2)/(K11+K22-2K12)统计学习方法上有详细的证明，其中K是核函数'''
  53.                     eta = float(self.X[i,:]*self.X[i,:].T+self.X[j,:]*self.X[j,:].T-2.0*self.X[i,:]*self.X[j,:].T);
  54.                     if 0==eta:
  55.                         continue;
  56.                     self.alpha[j] += self.Y[j]*(err_i-err_j)/eta;
  57.                     '''根据限制条件：0<=alpha_j<=C,确定最终的alpha_j'''
  58.                     if self.alpha[j] > H:
  59.                         self.alpha[j] = H;
  60.                     if self.alpha[j] < L:
  61.                         self.alpha[j] = L;
  62.                     #print("alpha[j]: ",float(alpha[j]),"alpha_j_old: ",float(alpha_j_old));
  63.                     if (abs(float(self.alpha[j])-float(alpha_j_old))<0.00001):
  64.                         '''alpha的变化太小'''
  65.                         #print("alpha的变化太小");
  66.                         continue;
  67.                     '''两个alpha变化大小相同，单方向相反'''
  68.                     self.alpha[i] += self.Y[j]*self.Y[i]*(alpha_j_old-self.alpha[j]);
  69.                     '''下面确定b，主要是通过新的alpha_i和alpha_j来确定b,主要运用两个公式，统计学习方法（130）'''
  70.                     b1 = self.b - err_i- self.Y[i]*(self.alpha[i]-alpha_i_old)*self.X[i,:]*self.X[i,:].T - self.Y[j]*(self.alpha[j]-alpha_j_old)*self.X[i,:]*self.X[j,:].T
  71.                     b2 = self.b - err_j- self.Y[i]*(self.alpha[i]-alpha_i_old)*self.X[i,:]*self.X[j,:].T - self.Y[j]*(self.alpha[j]-alpha_j_old)*self.X[j,:]*self.X[j,:].T
  72.                     if (0 < self.alpha[i]) and (self.C > self.alpha[i]):
  73.                         b = b1
  74.                     elif (0 < self.alpha[j]) and (self.C > self.alpha[j]):
  75.                         self.b = b2
  76.                     else:
  77.                         self.b = (b1 + b2)/2.0
  78.                     alpha_change = alpha_change + 1;
  79.             if 0 == alpha_change:
  80.                 iter+=1;
  81.             else:
  82.                 iter = 0;
  83.         self.__calculate_support_vector_and_weight_();
  84.     def __calculate_support_vector_and_weight_(self):
  85.         '''我们根据KKT条件给出支持向量，也就是alpha不等于0的项'''
  86.         '''我们根据公式为：alpha*Y*X求解w'''
  87.         self.w = zeros((self.n,1));
  88.         for i in range(self.m):
  89.             if self.alpha[i]:
  90.                 self.support_vector.append([self.X[i].getA()[0][0],self.X[i].getA()[0][1]]);
  91.                 self.w += multiply(self.alpha[i]*self.Y[i],self.X[i,:].T);
  92.         self.support_vector = mat(self.support_vector);
  93.     def plot_svm(self):
  94.         X = []; Y = [];
  95.         fr = open(self.filename);
  96.         for line in fr.readlines():
  97.             lineArr = line.strip().split('\t');
  98.             X.append([float(lineArr[0]), float(lineArr[1])]);
  99.             Y.append(float(lineArr[2]));
  100.         X=mat(X);
  101.         a = -self.w[0]/self.w[1];
  102.         XX = linspace(-5, 15);
  103.         YY = a * XX - (self.b[0].getA1()[0])/self.w[1];
  104.         pl.plot(XX, YY, 'k-');
  105.         pl.scatter(X[:, 0], X[:, 1], c=Y, cmap=pl.cm.Paired);
  106.         pl.axis('tight');
  107.         pl.show();

上面的代码只是简单的实现，有些地方并没有做处理，比如:权重为了0或者eta为0时等。

下面我们将上述简单实现和scikit中的LinearSVC进行简单的比较，因为没有找到合适的数据集，所以两个算法的划分结果都不怎么好，但是同样可以看出，我们的简单方法和LinearSVC的结果相差无几。

左图是scikit的结果，右图是我们的结果。






阅读(17343) | 评论(1) | 转发(0) |
1

上一篇：NGINX中常用的数据结构

下一篇：基本的图算法

给主人留下些什么吧！~~

CU博客助理2014-07-11 15:36:28

专家点评：是博主bl竹子在探索机器学习算法的分类方法所做的总结，使用SVM改进Logistic分类法及贝叶斯分类法等现存的问题，可以看得出，博主文章写得很用心，一般人在接触机器学习算法会感到头疼，博主的文章能降低这种疼痛感。（感谢参与原创评选活动，结果即将公布）

回复 | 举报
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6