svdd算法

‘壹’ 有人知道怎么把SVDD工具箱装到libsvm吗

1 先下载 libsvm-svdd-3.18.zip和 libsvm-3.18.zip，并解压得到文件夹 libsvm-svdd-3.18和libsvm-3.18；
2 将文件夹 libsvm-svdd-3.18根目录下的svm.cpp、svm.h和svm-train.c复制到 libsvm-3.18根目录下并覆盖原来的这3个文件；将文件夹 libsvm-svdd-3.18中 matlab里的文件 svmtrain.c 复制到 libsvm-3.18中的matlab文件夹中覆盖原来的c文件；
3 安装 libsvm-3.18，这个教程网上一大堆，主要是两步：mex -setup和 make；
4 测试安装是否成功。

‘贰’ 异常检测方法 二

  离群点是一个数据对象，它显着不同于其他数据对象，好像它是被不同的机制产生的一样。有时也称非离群点为“正常数据”，离群点为“异常数据”。
  离群点不同于噪声数据。噪声是被观测变量的随机误差或方差。一般而言，噪声在数据分析（包括离群点分析）中不是令人感兴趣的。如在信用卡欺诈检测，顾客的购买行为可以用一个随机变量建模。一位顾客可能会产生某些看上去像“随机误差”或“方差”的噪声交易，如买一份较丰盛的午餐，或比通常多要了一杯咖啡。这种交易不应该视为离群点，否则信用卡公司将因验证太多的交易而付出沉重代价。因此，与许多其他数据分析和数据挖掘任务一样，应该在离群点检测前就删除噪声。
  离群点检测是有趣的，因为怀疑产生它们的机制不同于产生其他数据的机制。因此，在离群点检测时，重要的是搞清楚为什么检测到的离群点被某种其他机制产生。通常，在其余数据上做各种假设，并且证明检测到的离群点显着违反了这些假设。

离群点可以分成三类：全局离群点、情境（或条件）离群点和集体离群点。

在给定的数据集中，一个数据对象是全局离群点，如果它显着的偏离数据集中的其他对象。全局离群点是最简单的一类离群点，大部分的离群点检测方法都旨在找出全局离群点。

在给定的数据集中，一个数据对象是情境离群点，如果关于对象的特定情境，它显着的偏离其他对象。情境离群点又称为条件离群点，因为它们条件的依赖于选定的情境。一般地，在情境离群点检测中，所考虑数据对象的属性划分成两组：
情境属性 ：数据对象的情境属性定义对象的情境。一般为静态属性变量，如信用卡欺诈检测中，不同年龄、不同地区的人消费情况是不同的，先按照静态属性将人群大致分类，再检测每一类的离群点，会得到更好的结果。
行为属性 ：定义对象的特征，并用来评估对象关于它所处的情境是否为离群点。在上述例子中，行为属性可以是消费金额，消费频率等
情境离群点分析为用户提供了灵活性，因为用户可以在不同情境下考察离群点，这在许多应用中都是非常期望的。

给定一个数据集，数据对象的一个子集形成集体离群点，如果这些对象作为整体显着的偏离整个数据集。如一家供应链公司，每天处理数以千计的订单和出货。如果一个订单的出货延误，则可能不是离群点，因为统计表明延误时常发生。然而，如果有一天有100个订单延误，则必须注意。这100个订单整体来看，形成一个离群点，尽管如果单个考虑，它们每个或许都不是离群点。你可能需要更详细地整个考察这些订单，搞清楚出货问题。
与全局和情境离群点检测不同，在集体离群点检测中，不仅必须考虑个体对象的行为，而且还要考虑对象组群的行为。因此，为了检测集体离群点，需要关于对象之间联系的背景知识，如对象之间的距离或相似性测量方法。

离群点检测的统计学方法对数据的正常性做假定。假定数据集中的正常对象由一个随机过程（生成模型）产生。因此，正常对象出现在该随机模型的高概率区域中，而低概率区域中的对象是离群点。
离群点检测的统计学方法的一般思想是：学习一个拟合给定数据集的生成模型，然后识别该模型低概率区域中的对象，把它们作为离群点。有许多不同方法来学习生成模型，一般而言，根据如何指定和如何学习模型，离群点检测的统计学方法可以划分成两个主要类型： 参数方法和非参数方法。
参数方法: 假定正常的数据对象被一个以为参数的参数分布产生。该参数分布的概率密度函数给出对象被该分布产生的概率。该值越小，越可能是离群点。
非参数方法: 并不假定先验统计模型，而是试图从输入数据确定模型。非参数方法的例子包括直方图和核密度估计。

  假定数据集由一个正态分布产生，然后，可以由输入数据学习正态分布的参数，并把低概率的点识别为离群点。
  在正态分布的假定下，区域包含99.7%的数据，包含95.4%的数据，包含68.3%的数据。视具体情况而定，将其区域外的数据视为离群点。
  这种直截了当的统计学离群点检测方法也可以用于可视化。例如盒图方法使用五数概况绘制一元输入数据：最小的非离群点值（Min）、第一个四分位数（Q1）、中位数（Q2）、第三个四分位数（Q3）和最大的非离群点值（Max）。
  四分位数极差（IQR）定义为Q3-Q1。比Q1小1.5倍的IQR或者比Q3大1.5倍的IQR的任何对象都视为离群点，因为Q1-1.5 IQR和Q3+1.5 IQR之间的区域包含了99.3%的对象。

（1）使用马哈拉诺比斯距离检测多元离群点。
对于一个多元数据集，设为均值向量。对于数据集中的对象，从到的马哈拉诺比斯（Mahalanobis）距离为其中S是协方差矩阵。是一元数据，可以对它进行离群点检测。如果被确定为离群点，则也被视为离群点。
（2）使用统计量的多元离群点检测。
在正态分布的假设下，统计量可以用来捕获多元离群点。对于对象，统计量是
其中，是在第维上的值，是所有对象在第维上的均值，而是维度。如果对象的统计量很大，则该对象是离群点。
（3）使用混合参数分布
在许多情况下，数据是由正态分布产生的假定很有效。然而，当实际数据很复杂时，这种假定过于简单。在这种情况下，假定数据是被混合参数分布产生的。
混合参数分布中用期望最大化（EM）算法来估计参数。具体情况比较复杂，可以参考韩家炜的《数据挖掘：概念与技术》一书。

在离群点检测的非参数方法中，“正常数据”的模型从输入数据学习，而不是假定一个先验。通常，非参数方法对数据做较少假定，因而在更多情况下都可以使用。

使用直方图检测离群点
包括如下两步：
步骤1： 构造直方图。尽管非参数方法并不假定任何先验统计模型，但是通常确实要求用户提供参数，以便由数据学习。如指定直方图的类型（等宽或等深的）和其他参数（如直方图中的箱数或每个箱的大小）。与参数方法不同，这些参数并不指定数据分布的类型（如高斯分布）。
步骤2： 检测离群点。为了确定一个对象是否是离群点，可以对照直方图检验它。在最简单的方法中，如果该对象落入直方图的一个箱中，则该对象被看做是正常的，否则被认为是离群点。

对于更复杂的方法，可以使用直方图赋予每个对象一个离群点得分。一般可以令对象的离群点得分为该对象落入的箱的容积的倒数。得分越高，表明是离群点的概率越大。

使用直方图作为离群点检测的非参数模型的一个缺点是，很难选择一个合适的箱尺寸。一方面，如箱尺寸太小，则由很多正常对象都会落入空的或稀疏箱，因而被误识别为离群点。这将导致很高的假正例率或低精度。相反，如果箱尺寸太大，则离群点对象可能渗入某些频繁的箱中，这将导致很高的假负例率或召回率。为了解决这些问题，使用核密度估计来估计数据的概率密度分布。具体参考韩家炜的《数据挖掘：概念与技术》。

  给定特征空间中的对象集，可以使用距离度量来量化对象间的相似性。基于邻近性的方法假定：离群点对象与它最近邻的邻近性显着偏离数据集中其他对象与它们近邻之间的邻近性。
  有两种类型的基于邻近性的离群点检测方法：基于距离的和基于密度的方法。基于距离的离群点检测方法考虑对象给定半径的邻域。一个对象被认为是离群点，如果它的邻域内没有足够多的其他点。基于密度的离群点检测方法考察对象和它近邻的密度。这里，一个对象被识别为离群点，如果它的密度相对于它的近邻低得多。

对于待分析的数据对象集D，用户可以指定一个距离阈值r来定义对象的合理邻域。对于每个对象o，可以考察o的r-邻域中的其他对象的个数。如果D中大多数对象都远离o，即都不在o的r-邻域中，则o可以被视为一个离群点。
令是距离阈值，是分数阈值。对象是一个离群点，如果
其中是距离度量。
如何计算-离群点？一是嵌套循环方法，时间复杂度为。当数据集很大时，该方法的开销很大。为了改进性能，可以用基于网格的方法来实现。具体见韩家炜《数据挖掘》一书。

基于距离的离群点检测从全局考虑数据集。由于以下两个原因，这种离群点被看成“全局离群点”：
l 例如，一个-离群点至少远离（用参数r定量）数据集中的对象。换言之，这种离群点远离数据的大多数。
l 为了检测基于距离的离群点，需要两个距离参数，它们用于每个离群点对象。
现实世界的许多数据集都呈现更复杂的结构，那里对象可能关于其局部邻域，而不是关于整个数据分布而被视为离群点。如下图，基于距离的离群点检测方法不能捕获像o1和o2这样的局部离群点。
那么，如何确切地定义如图所示的局部离群点？这里关键的思想是，需要把对象周围的密度与对象邻域周围的密度进行比较。基于密度的离群点检测方法的基本假定是：非离群点对象周围的密度与其邻域周围的密度类似，而离群点对象周围的密度显着不同于其邻域周围的密度。

基于聚类的方法通过考察对象与簇之间的关系检测离群点。直观地，离群点是一个对象，它属于小的偏远簇，或不属于任何簇。
这导致三种基于聚类的离群点检测的一般方法。考虑一个对象。
l 该对象属于某个簇吗？如果不，则它被识别为离群点。
l 该对象与最近的簇之间的距离很远吗？如果是，则它是离群点。
l 该对象是小簇或稀疏簇的一部分吗?如果是，则该簇中的所有对象都是离群点。

下面对每一种方法考察一个例子。

例1 把离群点检测为不属于任何簇的对象。如图1所示，使用基于密度的聚类方法，如DBSCAN,注意到黑色点都属于簇，白色点a不属于任何簇，因而被认为是离群点。

图1 对象a是离群点，因为 它不属于任何簇

图2 离群点（a,b,c）都（关于簇中心）远离距它们最近的簇

例2 使用到最近簇的距离的基于聚类的离群点检测。如图2所示，使用k-均值聚类方法，可以把图2中的数据点划分成3个簇，如图中不同符号所示，每个簇中心用“+”标记。对于每个对象o，都可以根据该对象与最近簇中心的距离，赋予该对象一个离群点得分。假设到o的最近中心为c,则o与c之间的距离为dist(o,c)，c与指派到c的对象之间的平均距离为L,比率度量与平均值的差异程度。在图2中，点a,b和c都相对远离它们的对应中心，因而被怀疑是离群点。

例3 检测小簇中的离群点

迄今为止我们看到的每种方法都只检测个体离群点，因为它们一次把一个对象与数据集中的簇进行比较。然而，在大型数据中，一些离群点可能是类似的，并且形成一个小簇。例如，在入侵检测中，使用相同手段攻击系统的黑客可能形成一个簇。迄今为止所讨论的方法可能被这种离群点所欺骗。
为了解决这一问题，第三种基于聚类的离群点检测方法识别小簇或稀疏簇，并宣告这些簇中的对象也是离群点。这种方法的一个例子是FindCBLOF算法，其方法如下。

（1） 找出数据集中的簇，并把它们按大小降序排列。该算法假定大部分数据点都不是离群点，它使用一个参数来区别大簇和小簇。任何至少包含数据集中百分之（如，=90%）数据点的簇都被视为大簇，而其余的簇被看成小簇。
（2） 对于每个数据点赋予基于簇的局部离群点因子（CBLOF），对于属于大簇的点，它的CBLOF是簇的大小和该点与簇的相似性的乘积。对于属于小簇的点，它的CBLOF用小簇的大小和该点与最近的大簇的相似性的乘积计算。
CBLOF用统计学方法定义点和簇之间的相似性，代表点属于簇的概率。该值越大，点与簇越相似。CBLOF值可以检测远离任何簇的离群点。
基于聚类的离群点检测方法具有如下优点。首先，它们可以检测离群点，而不要求数据是有标号的，即它们以无监督方式检测。它们对许多类型的数据都有效。簇可以看成是数据的概括，一旦得到簇，基于聚类的方法只需要把对象与簇进行比较，以确定该对象是否是离群点，这一过程通常很快，因为与对象总数相比，簇的个数通常很小。
基于聚类的方法的缺点是：它的有效性高度依赖于所使用的聚类方法。这些方法对于离群点检测而言可能不是最优的。对于大型数据集，聚类方法通常开销很大，这可能成为一个瓶颈。

如果训练数据具有类标号，则离群点检测可以看做分类问题。基于分类的离群点检测方法的一般思想是，训练一个可以区分“正常”数据和离群点的分类模型。
基于分类的离群点检测方法通常使用一类模型（单分类模型SVDD），即构造一个仅描述正常类的分类器，不属于正常类的任何样本都被视为离群点。
基于分类的方法和基于聚类的方法可以联合使用，以半监督的方式检测离群点。
例通过半监督学习检测离群点

如上图所示，其中对象被标记为“正常”或“离群点”，或者没有标号。使用基于聚类的方法，发现一个大簇C和一个小簇C1。因为C中的某些对象携带了标号“正常”，因此可以把该簇的所有对象（包括没有标号的对象）都看做正常对象。在离群点检测中，使用这个簇的一类模型来识别离群点。类似的，因为簇C1中的某些对象携带标号“离群点”，因此宣布C1中的所有对象都是离群点。未落入C模型中的任何对象（如a）也被视为离群点。

与一般的离群点检测相比，识别情境离群点需要分析对应的情境信息。情境离群点检测方法可以根据情境是否可以清楚地识别而分成两类。

这类方法适用于情境可以被清楚识别的情况，其基本思想是把情境离群点检测问题转换成典型的离群点检测问题。具体地说，对于给定的数据对象，用两步来评估该对象是否是离群点。第一步，使用对象的情境属性识别对象的情境。第二步，使用一种传统的离群点检测方法，估计该对象的离群点得分。

在某些应用中，清楚地把数据划分成情境是不方便的或不可行的。这时，可以关于情境对正常行为建模。使用一个训练数据集，这种方法训练一个模型，关于情境属性的值，预测期望的行为属性值。然后，为了确定一个数据对象是否是情境离群点，可以在该对象的情境属性上使用该模型。如果该对象的行为属性值显着地偏离该模型的预测值，则该对象被宣布为情境离群点。
通过使用连接情境和行为的预测模型，这些方法避免直接识别具体情境。许多分类和预测技术都可以用来构建这种模型，如回归、马尔科夫模型和有穷状态自动机等等。

与情境离群点检测一样，集体离群点检测方法也可以划分为两类。第一类方法把问题归结为传统的离群点检测。其策略是识别结构单元，把每个结构单元（例如，子序列、时间序列片段、局部区域或子图）看做是一个数据对象，并提取特征。这样，集体离群点检测问题就转换成在使用提取的特征构造的“结构化对象”集上的离群点检测。一个结构单元代表原数据集中的一组对象，如果该结构单元显着地偏离提取的特征空间中的期望趋势，则它是一个集体离群点。
为集体离群点检测预先定义结构单元可能是困难的，或者是不可能的。因此，第二类方法直接对结构单元的期望行为建模。例如，为了在时间序列中检测离群点，一种方法是从序列中学习马尔科夫模型。因此，一个子序列被宣布为集体离群点，如果它显着地偏离该模型。

一般地，高维数据的离群点检测方法应该应对以下挑战：

l 离群点的解释：不仅应该能够识别检测离群点，而且能够提供离群点的解释。离群点的解释可能是，例如，揭示离群点的特定子空间，或者关于对象的“离群点性”的评估。这种解释可以帮助用户理解离群点的含义和意义。
l 数据的稀疏性：这些方法应该能处理高维空间的稀疏性。随着维度的增加，对象之间的距离严重地被噪声所左右。因此，高维空间中的数据通常是稀疏的。
l 数据子空间：它们应该以合适的方式对离群点建模，例如，自适应现实离群点的子空间和捕获数据的局部变化。在所有的子空间上使用固定的距离阈值来检测离群点捕食一种好想法，因为两个对象之间的距离随着维度增加而单调增加。
l 关于维度的可伸缩性：随着维度的增加，子空间的数量指数增加。包含所有可能的子空间的穷举组合探索不是可伸缩的选择。
高维数据的离群点检测方法可以划分成三种主要方法，包括扩充的传统离群点检测、发现子空间中的离群点和对高维离群点建模。

一种高维数据离群点检测方法是扩充的传统离群点检测方法。它使用传统的基于邻近性的离群点模型。然而，为了克服高维空间中邻近性度量恶化问题，它使用其他度量，或构造子空间并在其中检测离群点。

HilOut算法就是这种方法的一个例子。HitOut找出基于距离的离群点，但在离群点检测中使用距离的秩，而不是绝对距离。具体地说，对于每个对象o，HitOut找出o的k个最近邻，记作nn1(o),nn2(o)……nnk(o),其中k是一个依赖于应用的参数。参数o的权重定义为

所有对象按权重递减序定秩。权重最高的top-p个对象作为离群点输出，其中p是另一个用户指定的参数。

HilOut算法计算每个对象的k-最近邻开销很大，当维度很高并且数据很大时不能伸缩。
另一种方法则是通过维归约，把高维离群点检测问题归结为较低维上的离群点检测。其基本思想是，把高维空间归约到低维空间，那里标准的距离度量仍然能够区分离群点。如果能够找到这样的较低维空间，则可以用传统的离群点检测方法。
为了降低维度，可以对离群点检测使用或扩充一般的特征特征选择和提取方法。例如，可以用主成分分析（PCA）来提取一个低维空间。

高维数据中离群点检测的另一种方法是搜索各种子空间中的离群点。其唯一的优点是，如果发现一个对象是很低维度的子空间的离群点，则该子空间提供了重要信息，解释该对象为什么和在何种程度上是离群点。
如何检测子空间中的离群点，一种方法是基于网格的子空间离群点检测。具体做法见韩家炜《数据挖掘》。

另一种方法是试图直接为高维离群点建立一个新模型。这种方法通常避免邻近性度量，而是采用新的启发式方法来检测离群点。具体做法见韩家炜《数据挖掘》。

‘叁’ sklearn之OneClassSVM

（1）无监督异常值检测

（2）解决非平衡样本分类

class  sklearn.svm.OneClassSVM( kernel=’rbf’ ,  degree=3 ,  gamma=’auto’ ,  coef0=0.0 ,  tol=0.001 ,  nu=0.5 ,  shrinking=True ,  cache_size=200 ,  verbose=False ,  max_iter=-1 ,  random_state=None )

kernel：

    典型的2类问题：识别邮件是否是垃圾邮件，一类“是”，另一类“不是”

    典型的多类问题：人脸识别，每个人对应的脸就是一个类，然后把待识别的脸分到对应的类中去

    而OneClassClassification，它只有一个类，属于该类就返回结果“是”，不属于就返回结果“不是”，乍一听感觉与2分类没什么区别，其实他们的思想有很大差异。在2分类问题中，训练集中就由两个类的样本组成，训练出的模型是一个2分类模型；而OneClassClassification中的训练样本只有一类，因此训练出的分类器将不属于该类的所有其他样本判别为“不是”即可，而不是由于属于另一类才返回的“不是”结果。

    现实场景中的OneClassClassification例子：现在有一堆某商品的历史销售数据，记录着买该产品的用户信息，此外还有一些没有购买过该产品的用户信息，想通过2分类来预测他们是否会买该产品，也就是弄两个类，一类是“买”，一类是“不买”。当我们要开始训练2分类器的时候问题来了，一般来说没买的用户数会远远大于已经买了的用户数，当将数量不均衡的正负样本投入训练时，训练出的分类器会有较大的bias（偏向值）。因此，这时可以使用OneCLassClassification方法来解决，即训练集中只有已经买过该产品的用户数据，在识别一个新用户是否会买该产品时，识别结果就是“会”或者“不会”。

多类Classification方法有很多，比如SVM寻找一个最优超平面把正负样本分开，总之都涉及到不止一个类的样本，相当于告诉算法“这种东西长什么样，那种东西长什么样”。于是训练出一个模型能够区分这些东西。

问题在于，OneCLassClassification只有一个类，该怎么办？

介绍一个方法：SVDD（support vector domain description），中文翻译为“支持向量域描述”

其基本思想是：既然只有一个class，那么我就训练出一个最小的超球面（超球面是指3维以上的空间中的球面，对应的2维空间中就是曲线，3维空间中就是球面），将这堆数据全部“包起来”，识别一个新的数据点时，如果这个数据点落在超球面内，就属于这个类，否则不是。

下面是在2维空间（实际情况中，如果提取的特征多，维数就高）中的例子，

更多原理公式推导，详见 http://blog.sina.com.cn/s/blog_4ff49c7e0102vlbv.html

‘肆’ 怎么在libsvm安装包基础上进行特征加权

一 安装
1. 下载
在LIBSVM的主页上下载最新版本的软件包，并解压到合适目录中。

2. 编译
如果你使用的是64位的操作的系统和Matlab，那么不需要进行编译步骤，因为自带软件包中已经包含有64位编译好的版本：libsvmread.mexw64、libsvmwrite.mexw64、svmtrain.mexw64、svmpredict.mexw64。否则，需要自己编译二进制文件。

首先在Mtlab中进入LIBSVM根目录下的matlab目录（如C:\libsvm-3.17\matlab），在命令窗口输入

>>mex –setup

然后Matlab会提示你选择编译mex文件的C/C++编译器，就选择一个已安装的编译器，如Microsoft Visual C++ 2010。之后Matlab会提示确认选择的编译器，输入y进行确认。

然后可以输入以下命令进行编译。

>>make

注意，Matlab或VC版本过低可能会导致编译失败，建议使用最新的版本。

编译成功后，当前目录下会出现若干个后缀为mexw64（64位系统）或mexw32（32位系统）的文件。

3. 重命名（可选，但建议执行）
编译完成后，在当前目录下回出现svmtrain.mexw64、svmpredict.mexw64（64位系统）或者svmtrain.mexw32、svmpredict.mexw32（32位系统）这两个文件，把文件名svmtrain和svmpredict相应改成libsvmtrain和libsvmpredict。

这是因为Matlab中自带有SVM的工具箱，而且其函数名字就是svmtrain和svmpredict，和LIBSVM默认的名字一样，在实际使用的时候有时会产生一定的问题，比如想调用LIBSVM的变成了调用Matlab SVM。

如果有进行重命名的，以后使用LIBSVM时一律使用libsvmtrain和libsvmpredict这两个名字进行调用。

4. 添加路径
为了以后使用的方便，建议把LIBSVM的编译好的文件所在路径（如C:\libsvm-3.17\matlab）添加到Matlab的搜索路径中。具体操作为：（中文版Matlab对应进行）

HOME -> Set Path -> Add Folder -> 加入编译好的文件所在的路径（如C:\libsvm-3.17\matlab）

当然也可以把那4个编译好的文件复制到想要的地方，然后再把该路径添加到Matlab的搜索路径中。

二 测试
LIBSVM软件包中自带有测试数据，为软件包根目录下的heart_scale文件，可以用来测试LIBSVM是否安装成功。这里的heart_scale文件不能用Matlab的load进行读取，需要使用libsvmread读取。

进入LIBSVM的根目录运行以下代码（因为heart_scale文件没有被添加进搜索路径中，其他路径下无法访问这个文件）：

[heart_scale_label, heart_scale_inst] = libsvmread('heart_scale');
model = libsvmtrain(heart_scale_label, heart_scale_inst, '-c 1 -g 0.07');
[predict_label, accuracy, dec_values] = libsvmpredict(heart_scale_label, heart_scale_inst, model);
如果LIBSVM安装正确的话，会出现以下的运行结果，显示正确率为86.6667%。

*
optimization finished, #iter = 134
nu = 0.433785
obj = -101.855060, rho = 0.426412
nSV = 130, nBSV = 107
Total nSV = 130
Accuracy = 86.6667% (234/270) (classification)
三 原理简介
使用SVM前首先得了解SVM的工作原理，简单介绍如下。

SVM(Support Vector Machine，支持向量机）是一种有监督的机器学习方法，可以学习不同类别的已知样本的特点，进而对未知的样本进行预测。

SVM本质上是一个二分类的算法，对于n维空间的输入样本，它寻找一个最优的分类超平面，使得两类样本在这个超平面下可以获得最好的分类效果。这个最优可以用两类样本中与这个超平面距离最近的点的距离来衡量，称为边缘距离，边缘距离越大，两类样本分得越开，SVM就是寻找最大边缘距离的超平面，这个可以通过求解一个以超平面参数为求解变量的优化问题获得解决。给定适当的约束条件，这是一个二次优化问题，可以通过用KKT条件求解对偶问题等方法进行求解。

对于不是线性可分的问题，就不能通过寻找最优分类超平面进行分类，SVM这时通过把n维空间的样本映射到更高维的空间中，使得在高维的空间上样本是线性可分的。在实际的算法中，SVM不需要真正地进行样本点的映射，因为算法中涉及到的高维空间的计算总是以内积的形式出现，而高维空间的内积可以通过在原本n维空间中求内积然后再进行一个变换得到，这里计算两个向量在隐式地映射到高维空间的内积的函数就叫做核函数。SVM根据问题性质和数据规模的不同可以选择不同的核函数。

虽然SVM本质上是二分类的分类器，但是可以扩展成多分类的分类器，常见的方法有一对多（one-versus-rest）和一对一（one-versus-one）。在一对多方法中，训练时依次把k类样本中的某个类别归为一类，其它剩下的归为另一类，使用二分类的SVM训练处一个二分类器，最后把得到的k个二分类器组成k分类器。对未知样本分类时，分别用这k个二分类器进行分类，将分类结果中出现最多的那个类别作为最终的分类结果。而一对一方法中，训练时对于任意两类样本都会训练一个二分类器，最终得到k*(k-1)/2个二分类器，共同组成k分类器。对未知样本分类时，使用所有的k*(k-1)/2个分类器进行分类，将出现最多的那个类别作为该样本最终的分类结果。

LIBSVM中的多分类就是根据一对一的方法实现的。

四 使用
关于LIBSVM在Matlab中的使用，可以参看软件包中matlab目录下的README文件，这里对里面内容做一个翻译和一些细节的讲解。

1. 训练
libsvm函数用于对训练集的数据进行训练，得到训练好的模型。

model = libsvmtrain(training_label_vector, training_instance_matrix [, 'libsvm_options']);

这个函数有三个参数，其中

-training_label_vector:训练样本的类标，如果有m个样本，就是m x 1的矩阵（类型必须为double）。这里可以是二分类和多分类，类标是（-1,1）、（1,2,3）或者其他任意用来表示不同的类别的数字，要转成double类型。
-training_instance_matrix:训练样本的特征，如果有m个样本，每个样本特征是n维，则为m x n的矩阵（类型必须为double）。
-libsvm_options:训练的参数，在第3点详细介绍。
2. 预测
libpredict函数用于对测试集的数据进行测试，还能对未知样本进行预测。

[predicted_label, accuracy, decision_values/prob_estimates]
= libsvmpredict(testing_label_vector, testing_instance_matrix, model [, 'libsvm_options']);

这个函数包括四个参数，其中

-testing_label_vector:测试样本的类标，如果有m个样本，就是m x 1的矩阵（类型必须为double）。如果类标未知，可以初始化为任意m x 1的double数组。
-testing_instance_matrix:测试样本的特征，如果有m个样本，每个样本特征是n维，则为m x n的矩阵（类型必须为double）。
-model:使用libsvmtrain返回的模型
-libsvm_options:预测的参数，与训练的参数形式一样。
3. 训练的参数
LIBSVM训练时可以选择的参数很多，包括：

-s svm类型：SVM设置类型（默认0)
0 — C-SVC； 1 –v-SVC； 2 – 一类SVM； 3 — e-SVR； 4 — v-SVR
-t 核函数类型：核函数设置类型（默认2）
0 – 线性核函数：u’v
1 – 多项式核函数：（r*u’v + coef0)^degree
2 – RBF(径向基)核函数：exp(-r|u-v|^2）
3 – sigmoid核函数：tanh(r*u’v + coef0)
-d degree：核函数中的degree设置（针对多项式核函数）（默认3）
-g r(gamma）：核函数中的gamma函数设置（针对多项式/rbf/sigmoid核函数）（默认1/k，k为总类别数)
-r coef0：核函数中的coef0设置（针对多项式/sigmoid核函数）（（默认0)
-c cost：设置C-SVC，e -SVR和v-SVR的参数（损失函数）（默认1）
-n nu：设置v-SVC，一类SVM和v- SVR的参数（默认0.5）
-p p：设置e -SVR 中损失函数p的值（默认0.1）
-m cachesize：设置cache内存大小，以MB为单位（默认40）
-e eps：设置允许的终止判据（默认0.001）
-h shrinking：是否使用启发式，0或1（默认1）
-wi weight：设置第几类的参数C为weight*C (C-SVC中的C) （默认1）
-v n: n-fold交互检验模式，n为fold的个数，必须大于等于2
以上这些参数设置可以按照SVM的类型和核函数所支持的参数进行任意组合，如果设置的参数在函数或SVM类型中没有也不会产生影响，程序不会接受该参数；如果应有的参数设置不正确，参数将采用默认值。

4. 训练返回的内容
libsvmtrain函数返回训练好的SVM分类器模型，可以用来对未知的样本进行预测。这个模型是一个结构体，包含以下成员：

-Parameters: 一个5 x 1的矩阵，从上到下依次表示：
-s SVM类型（默认0）；
-t 核函数类型（默认2）
-d 核函数中的degree设置(针对多项式核函数)(默认3)；
-g 核函数中的r(gamma）函数设置(针对多项式/rbf/sigmoid核函数) (默认类别数目的倒数)；
-r 核函数中的coef0设置(针对多项式/sigmoid核函数)((默认0)
-nr_class: 表示数据集中有多少类别，比如二分类时这个值即为2。
-totalSV: 表示支持向量的总数。
-rho: 决策函数wx+b中的常数项的相反数（-b）。
-Label: 表示数据集中类别的标签，比如二分类常见的1和-1。
-ProbA: 使用-b参数时用于概率估计的数值，否则为空。
-ProbB: 使用-b参数时用于概率估计的数值，否则为空。
-nSV: 表示每类样本的支持向量的数目，和Label的类别标签对应。如Label=[1; -1],nSV=[63; 67]，则标签为1的样本有63个支持向量，标签为-1的有67个。
-sv_coef: 表示每个支持向量在决策函数中的系数。
-SVs: 表示所有的支持向量，如果特征是n维的，支持向量一共有m个，则为m x n的稀疏矩阵。
另外，如果在训练中使用了-v参数进行交叉验证时，返回的不是一个模型，而是交叉验证的分类的正确率或者回归的均方根误差。

5. 预测返回的内容
libsvmtrain函数有三个返回值，不需要的值在Matlab可以用~进行代替。

-predicted_label：第一个返回值，表示样本的预测类标号。
-accuracy：第二个返回值，一个3 x 1的数组，表示分类的正确率、回归的均方根误差、回归的平方相关系数。
-decision_values/prob_estimates：第三个返回值，一个矩阵包含决策的值或者概率估计。对于n个预测样本、k类的问题，如果指定“-b 1”参数，则n x k的矩阵，每一行表示这个样本分别属于每一个类别的概率；如果没有指定“-b 1”参数，则为n x k*(k-1)/2的矩阵，每一行表示k(k-1)/2个二分类SVM的预测结果。
6. 读取或保存
libsvmread函数可以读取以LIBSVM格式存储的数据文件。

[label_vector, instance_matrix] = libsvmread(‘data.txt’);

这个函数输入的是文件的名字，输出为样本的类标和对应的特征。

libsvmwrite函数可以把Matlab的矩阵存储称为LIBSVM格式的文件。

libsvmwrite(‘data.txt’, label_vector, instance_matrix]

这个函数有三个输入，分别为保存的文件名、样本的类标和对应的特征（必须为double类型的稀疏矩阵）。

五 更新:svdd扩展安装（2014.10）
从libsvm官网下载svdd工具箱，目前使用libsvm3.18以及svdd3.18版本。

svdd工具箱里面有一个matlab文件夹和3个文件svm.cpp、svm.h、svm-train.c。
将matlab文件夹中的文件svmtrain.c覆盖原libsvm的matlab文件夹中的文件。
将svm.cpp、svm.h、svm-train.c这3个文件覆盖libsvm文件夹下的相同文件。
按本文刚开始讲述的方法进行mex -setup、make等完成安装，根据需要进行改名以及添加Path。

‘伍’ 小球大间隔模型存在的对偶问题

软间隔
在上文当中我们说了，在实际的场景当中，数据不可能是百分百线性可分的，即使真的能硬生生地找到这样的一个分隔平面区分开样本，那么也很有可能陷入过拟合当中，也是不值得追求的。

因此，我们需要对分类器的标准稍稍放松，允许部分样本出错。但是这就带来了一个问题，在硬间隔的场景当中，间隔就等于距离分隔平面最近的支持向量到分隔平面的距离。那么，在允许出错的情况下，这个间隔又该怎么算呢？

为了解决这个问题，我们需要对原本的公式进行变形，引入一个新的变量叫做松弛变量。松弛变量我们用希腊字母𝜉
ξ
来表示，这个松弛变量允许我们适当放松$y_i(\omega^T x_i + b) \ge 1 这个限制条件，我们将它变成
这
个
限
制
条
件
，
我
们
将
它
变
成
y_i(\omega^T x_i + b) \ge 1-\xi_i $。

也就是说对于每一条样本我们都会有一个对应的松弛变量𝜉𝑖
ξ
i
，它一共有几种情况。

𝜉=0
ξ
=
0
，表示样本能够正确分类
0<𝜉<1
0
<
ξ
<
1
，表示样本在分割平面和支持向量之间
𝜉=1
ξ
=
1
，表示样本在分割平面上
𝜉≥1
ξ
≥
1
，表示样本异常
我们可以结合下面这张图来理解一下，会容易一些：

松弛变量虽然可以让我们表示那些被错误分类的样本，但是我们当然不希望它随意松弛，这样模型的效果就不能保证了。所以我们把它加入损失函数当中，希望在松弛得尽量少的前提下保证模型尽可能划分正确。这样我们可以重写模型的学习条件：

min12||𝜔||2+𝐶∑𝑖=1𝑚𝜉𝑖𝑠.𝑡.𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏)≥1−𝜉𝑖,𝜉𝑖≥0,𝑖=1,2,3…,𝑛𝑖=1,2,3…,𝑛
min
1
2
|
|
ω
|
|
2
+C
∑
i
=
1
m
ξ
i
s.t.
y
i
(
ω
T
x
i
+b)≥1−
ξ
i
, i=1,2,3…,n
ξ
i
≥0, i=1,2,3…,n
这里的C是一个常数，可以理解成惩罚参数。我们希望||𝜔||2
|
|
ω
|
|
2
尽量小，也希望∑𝜉𝑖
∑
ξ
i
尽量小，这个参数C就是用来协调两者的。C越大代表我们对模型的分类要求越严格，越不希望出现错误分类的情况，C越小代表我们对松弛变量的要求越低。

从形式上来看模型的学习目标函数和之前的硬间隔差别并不大，只是多了一个变量而已。这也是我们希望的，在改动尽量小的前提下让模型支持分隔错误的情况。

模型推导
对于上面的式子我们同样使用拉格朗日公式进行化简，将它转化成没有约束的问题。

首先，我们确定几个值。第一个是我们要优化的目标：𝑓(𝑥)=min𝜔,𝑏,𝜉12||𝜔||2+𝐶∑𝑚𝑖=1𝜉𝑖
f
(
x
)
=
min
ω
,
b
,
ξ
1
2
|
|
ω
|
|
2
+
C
∑
i
=
1
m
ξ
i

第二个是不等式约束，拉格朗日乘子法当中限定不等式必须都是小于等于0的形式，所以我们要将原式中的式子做一个简单的转化：

𝑔(𝑥)=1−𝜉𝑖−𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏)≤0ℎ(𝑥)=−𝜉𝑖≤0
g(x)=1−
ξ
i
−
y
i
(
ω
T
x
i
+b)≤0 h(x)=−
ξ
i
≤0
最后是引入拉格朗日乘子: 𝛼=(𝛼1,𝛼2,⋯,𝛼𝑚),𝛽=(𝛽1,𝛽2,⋯,𝛽𝑚)
α
=
(
α
1
,
α
2
,
⋯
,
α
m
)
,
β
=
(
β
1
,
β
2
,
⋯
,
β
m
)

我们写出广义拉格朗日函数：𝐿(𝜔,𝑏,𝜉,𝛼,𝛽)=12||𝜔||2+𝐶∑𝑚𝑖=1𝜉𝑖,+∑𝑚𝑖=1𝛼𝑖(1−𝜉𝑖−𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏))−∑𝑚𝑖=1𝛽𝑖𝜉𝑖
L
(
ω
,
b
,
ξ
,
α
,
β
)
=
1
2
|
|
ω
|
|
2
+
C
∑
i
=
1
m
ξ
i
,
+
∑
i
=
1
m
α
i
(
1
−
ξ
i
−
y
i
(
ω
T
x
i
+
b
)
)
−
∑
i
=
1
m
β
i
ξ
i

我们要求的是这个函数的最值，也就是min𝜔,𝑏,𝜉max𝛼≥0,𝛽≥0𝐿(𝜔,𝑏,𝜉,𝛼,𝛽)
min
ω
,
b
,
ξ
max
α
≥
0
,
β
≥
0
L
(
ω
,
b
,
ξ
,
α
,
β
)
。

在处理硬间隔的时候，我们讲过对偶问题，对于软间隔也是一样。我们求L函数的对偶函数的极值。

对偶问题
原函数的对偶问题是max𝛼≥0,𝛽≥0min𝜔,𝑏,𝜉𝐿(𝜔,𝑏,𝜉,𝛼,𝛽)
max
α
≥
0
,
β
≥
0
min
ω
,
b
,
ξ
L
(
ω
,
b
,
ξ
,
α
,
β
)
，这个对偶问题要成立需要满足KKT条件。

我们先把这个KKT条件放一放，先来看一下对偶问题当中的内部的极小值。这个极小值没有任何约束条件，所以我们可以放心大胆地通过求导来来计算极值。这个同样是高中数学的内容，我们分别计算∂𝐿∂𝜔
∂
L
∂
ω
，∂𝐿∂𝑏
∂
L
∂
b
和∂𝐿∂𝜉
∂
L
∂
ξ
。

求导之后，我们可以得到：

∂𝐿∂𝜔=0∂𝐿∂𝑏=0∂𝐿∂𝜉=0→𝜔=∑𝑖=1𝑚𝛼𝑖𝑦𝑖𝑥𝑖→∑𝑖=1𝑚𝛼𝑖𝑦𝑖=0→𝛽𝑖=𝐶−𝛼𝑖
∂
L
∂
ω
=0 →ω=
∑
i
=
1
m
α
i
y
i
x
i
∂
L
∂
b
=0 →
∑
i
=
1
m
α
i
y
i
=0
∂
L
∂
ξ
=0 →
β
i
=C−
α
i

我们把这三个式子带入对偶函数可以得到：

𝐿(𝜔,𝑏,𝜉,𝛼,𝛽)=12∑𝑖=1𝑚∑𝑗=1𝑚𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗𝑥𝑇𝑖𝑥𝑗+𝐶∑𝑖=1𝑚𝜉𝑖+∑𝑖=1𝑚𝛼𝑖(1−𝜉𝑖)−∑𝑖=1𝑚(𝐶−𝛼𝑖)𝜉𝑖=∑𝑖=1𝑚𝛼𝑖−12∑𝑖=1𝑚∑𝑗=1𝑚𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗𝑥𝑇𝑖𝑥𝑗
L(ω,b,ξ,α,β) =
1
2
∑
i
=
1
m
∑
j
=
1
m
α
i
α
j
y
i
y
j
x
i
T
x
j
+C
∑
i
=
1
m
ξ
i
+
∑
i
=
1
m
α
i
(1−
ξ
i
)−
∑
i
=
1
m
(C−
α
i
)
ξ
i
=
∑
i
=
1
m
α
i
−
1
2
∑
i
=
1
m
∑
j
=
1
m
α
i
α
j
y
i
y
j
x
i
T
x
j

由于𝛽𝑖≥0
β
i
≥
0
，所以我们可以得到0≤𝛼𝑖≤𝐶
0
≤
α
i
≤
C
，所以最后我们可以把式子化简成：

max𝛼∑𝑖=1𝑚𝛼𝑖−12∑𝑖=1𝑚∑𝑗=1𝑚𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗𝑥𝑇𝑖𝑥𝑗𝑠.𝑡.∑𝑚𝑖=1𝛼𝑖𝑦𝑖=00≤𝛼𝑖≤𝐶,𝑖=1,2,3…,𝑚
max
α
∑
i
=
1
m
α
i
−
1
2
∑
i
=
1
m
∑
j
=
1
m
α
i
α
j
y
i
y
j
x
i
T
x
j
s.t.
∑
i
=
1
m
α
i
y
i
=0 0≤
α
i
≤C, i=1,2,3…,m
将原始化简了之后，我们再回过头来看KKT条件。KKT条件单独理解看起来有点乱，其实我们可以分成三个部分，分别是原始问题可行：

1−𝜉𝑖−𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏)≤0−𝜉𝑖≤0
1−
ξ
i
−
y
i
(
ω
T
x
i
+b)≤0 −
ξ
i
≤0
对偶问题可行：

𝛼𝑖≥0𝛽𝑖=𝐶−𝛼𝑖
α
i
≥0
β
i
=C−
α
i

以及松弛可行：

𝛼𝑖(1−𝜉−𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏))=0𝛽𝑖𝜉𝑖=0
α
i
(1−ξ−
y
i
(
ω
T
x
i
+b))=0
β
i
ξ
i
=0
我们观察一下倒数第二个条件：𝛼𝑖(1−𝜉−𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏))=0
α
i
(
1
−
ξ
−
y
i
(
ω
T
x
i
+
b
)
)
=
0
。

这是两个式子相乘并且等于0，无非两种情况，要么𝛼𝑖=0
α
i
=
0
，要么后面那串等于0。我们分情况讨论。

如果𝛼𝑖=0
α
i
=
0
，那么𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏)−1≥0
y
i
(
ω
T
x
i
+
b
)
−
1
≥
0
，样本分类正确，不会对模型产生影响。
如果𝛼𝑖>0
α
i
>
0
，那么𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏)=1−𝜉𝑖
y
i
(
ω
T
x
i
+
b
)
=
1
−
ξ
i
，则样本是支持向量。由于𝐶=𝛼𝑖+𝛽𝑖
C
=
α
i
+
β
i
，并且𝛽𝑖𝜉𝑖=0
β
i
ξ
i
=
0
。我们又可以分情况：
𝛼𝑖<𝐶
α
i
<
C
，那么𝛽𝑖>0
β
i
>
0
，所以𝜉𝑖=0
ξ
i
=
0
，那么样本在边界上
如果𝛼𝑖=𝐶
α
i
=
C
，那么𝛽𝑖=0
β
i
=
0
，如果此时𝜉≤1
ξ
≤
1
，那么样本被正确分类，否则样本被错误分类
经过了化简之后，式子当中只剩下了变量𝛼
α
，我们要做的就是找到满足约束条件并且使得式子取极值时的𝛼
α
，这个𝛼
α
要怎么求呢？我们这里先放一放，将在下一篇文章当中详解讲解。

‘陆’ 聚类算法概述及比较

其本质是：寻找联系紧密的事物进行区分，将数据划分为有意义或有用的簇

目标是：同簇内的数据对象的相似性尽可能大，不同簇间的数据对象的差异性尽可能大。

核心是：相似度计算

回顾一下：无监督学习(Unsupervised learning)：是否有监督（supervised），就看输入数据是否有标签（label）。输入数据有标签，则为有监督学习，没标签则为无监督学习。

具体包含：

K-means DIANA OPTICS Spectral STING COBWeb
K-medoids BIRCH DBSCAN CLIQUE CLASSIT
CLARANS Chameleon FDC WAVE-CLUSTER SOM

新发展的方法:

基于约束 基于模糊 基于粒度 量子聚类 核聚类 谱聚类
COD (Clustering
with Ob2structed
Distance) FCM SVDD/SVC 图论中的谱图

划分法（Partitioning methods）:

层次法（Hierarchical Clustering）:

基于密度的聚类（density-based methods）:

基于图的聚类（Graph-based methods）：

基于网格的方法（grid-based methods）:

基于模型的方法（model-based methods）:

map详细: http://scikit-learn.org/stable/tutorial/machine_learning_map/