附录B 外文原文
11.1 Introduction
Outlier detection is an important subject in machine learning and data analysis. The term Outlier refers to abnormal observations that are inconsistent with the bulk of the data distribution [16, 32, 98, 242, 267, 268, 289]. Some sample applications are as follows.
- Detection of imposters or rejection of unauthorized access to computer networks.
- Genomic research – identifying abnormal gene or protein sequences.
- Biomedical, e.g. ECG arrythmia monitoring.
- Environmental safety detection, where outliers indicate abnormality.
- Personal safety, with security aids embedded in mobile devices.
For some real-world application examples, see e.g. Hodge and Austin [98].
The standard approach to outlier detection is density-based, whereby the detection depends on the outlierrsquo;s relationship with the bulk of the data. Many algorithms use concepts of proximity and/or density estimation in order to find outliers. However, in high-dimensional spaces the data become increasingly sparse and the notion of proximity/density has become less meaningful, and consequently model-based methods have become more appealing [1, 39]. It is also a typical assumption that a model must be learned from only one type of (say, positive) training pattern, making it a fundamentally different problem, and thereby creating a new learning paradigm leading to one-class-based learning models.
SVM-type learning models are naturally amenable to outlier detection since certain support vectors can be identified as outliers. This chapter will address the following topics.
- Section 11.2 explores an important variant of SVM, i.e. support vector regression (SVR), which is intended for regression analysis whose aim is to find an approximating function to fit a set of training data.
- Sections 11.3, 11.4, and 11.5 respectively explore three other SVM-based learning models (hyperplane OCSVM, hypersphere OCSVM, and SVC), which are useful for outlier-detection applications. It will be shown that, for Gaussian kernels, all three algorithms coincide with each other. In addition, we shall also probe into critical issues such as the fraction of outliers and translation-invariance properties.
Fig. 11.1. An ε-insensitive penalty function with “grace interval” ε.
11.2 Support vector regression (SVR)
Support vector regression (SVR), which was proposed by Vapnik et al. [52, 281], is an important variant of SVM. It is meant for regression analysis whose aim is to find an approximating function to fit a set of training data. Its formulation is largely similar to that of SVM for classification, except for the introduction of the new notion of an -insensitive loss function, which will be explained below.
Given the training dataset , the kernel-induced training dataset is denoted as , where for simplicity we shall denote
The estimation error corresponding to each training vector , denoted by
will dictate the penalty function.
The -insensitive penalty
As shown in Figure 11.1, there will be no penalty if the violation is within a given grace margin . If does exceed , the penalty imposed will be linearly proportional to the exceeding amount only, i.e. . More exactly, the penalty function is
(11.1)
where denotes a pre-specified and positive “grace interval”. Taking into account the grace interval , the primal optimization formulation in the intrinsic space becomes
subject to the adjusted soft-constraints
(11.2)
where C is a user-specified constant.
The optimizer satisfies the LSP condition in Theorem 1.1; therefore, the learning model has a kernelized formulation. For the two sets of non-negative slack variables and used to characterize the -insensitive loss function, two corresponding sets of Lagrange multipliers and need to be incorporated into the optimizer in the dual domain. This leads to the following learning model in the empirical space.
ALGORITHM 11.1 (SVR learning model) Given the kernel matrix K and the teacher vector y, the SVR learning model aims at finding the coefficients and such that
(11.3)
By application of the LSP,
where . Hence the discriminant function is
(11.4)
where the threshold value b may be derived from Eq. (11.2), pursuant to the KKT conditions.
Note that SVR is more intricate than SVM, since one needs to simultaneously pre-select two design parameters, namely the penalty factor C and the tolerance .
SVR has successfully been applied to the detection of outliers in industrial use [116] and financial prediction [311]. In addition, there are other varieties of applications, for example, time-series prediction and modeling problems [186, 188].
11.3 Hyperplane-based one-class SVM learning models
Outlier detection is an important subject in machine learning and data analysis. Various outlier-detecting learning models have been proposed by Tax and Duin [267, 268], Schouml;lkopf et al. [239, 242], and Campbell and Bennett [32], all being inspired by the prior works by Vapnik [282, 283] and Ben-David and Lindenbaum [14].
11.3.1 Hyperplane-based -SV classifiers
In this section, we shall first derive an SV-based learning model for two-class classification, named the -SV classifier, in which the support vectors are characterized by the decision hyperplane in the kernel-induced intrinsic space. The two-class -SV classifier can then be converted into a one-class variant, which is then applicable to outlier detection and related applications.
A
剩余内容已隐藏，支付完成后下载完整资料
附录C 译文
用于离群点检测的支持向量学习模型
11.1 简介
离群点检测是机器学习和数据分析领域的一个重要的话题，离群点指的是违反大量数据分布的反常观测点。以下是一些应用案例。
·检测非授权登陆的计算机网络的冒名或是黑名单
·染色体组的研究，识别反常的基因或蛋白质的序列
·生物医学，例如心电图监测心律失常
·环境安全检测，其中离散点就意味着反常
·个人安全问题，移动嵌入式的安全救助
对于一些生活中的应用例子，可以参考Hodge和Austin的例子。
离群点检测的标准的方法是基于深度信息，许多算法为了找到离群点使用距离或是深度预测的概念。但是，随着高维空间数据变得越来越系数，距离/深度的概念变得越来越无意义，因此基于模型的检测方法变得越来越受欢迎。支持向量回归也是一个模型必须只能从一种类型的训练模式中学习训练的一种典型设想，使其变为一种完全不同的问题，因此支持向量回归是一个新的机器学习在基于单类学习模型的范例。
支持向量机类型的学习模型是经得起检验的离散点检测的方法，因为我们可以认为确定的支持向量为离群点。这章会讨论以下几个问题。
(i) 11.2节阐述了支持向量机（SVM）的一个重要变体，支持向量回归（SVR），其目的是为了找到一组数据的训练集的一个近似的函数关系从而做到数据的回归分析。
(ii) 11.3至11.5节分别阐述了三种其他的基于支持向量机的学习模型（超平面OCSVM，超球面OCSVM和SVC），这些都是可以用来检测离群点的方法。研究表明，对于高斯核，三种算法都差不多。另外，我们也可以探究关键问题例如离群点的分数和平衡不变特性。
图11.1. 宽限幅度值为的漠视惩罚函数
11.2 支持向量回归（SVR）
由Vapnik等人提出的支持向量回归(SVR)是支持向量机的一个重要的变体。它的目的是为了做回归分析，就是找到一组数据训练集的一个近似的函数关系。其构想与用来分类的SVM很相似，除了引入一个新的，接下来会解释这个。
对于给定的数据训练集，核诱导数据训练集可以记为，为了简化我们也可以记为
对于每一个训练向量的预测误差，记作
这个决定了惩罚函数。
漠视惩罚函数
由图11.1所示，若变量在给定的宽限幅度之内，便没有惩罚。若超出了，惩罚只是与超出的部分即成线性比例。更加准确地，乘法函数为
(11.1)
其中，为预定的正的宽限幅度值。将其考虑在内，在固有空间的主要的优化表达式变为
受以下调整过的软约束
(11.2)
其中，C是一个用户指定的常数。
优化控制器满足了定理1.1中的LSP环境，因此，学习模型有一个核表达式。对于用来描绘漠视的损失函数的两组非负的松垂变量和，两组相对应的拉格朗日乘子和在双重域中需要被纳入优化控制器。这导致了接下来所描述的在实践经验空间的学习模型。
算法11.1 (SVR学习模型) 若给出核矩阵K和教师向量y，SVR学习模型的目的在于找出和这两个系数，例如
(11.3)
通过LSP的应用,
其中. 因此判别式方程为
(11.4)
其中根据KKT条件，阈值b或许是由式11.2得到的。
注意SVR学习模型要比SVM复杂，因为他需要同时预选两个设计参数，即惩罚因子C和容忍值。
SVR在工业和金融预测中被成功的用来检测离群点。此外，有其他各种各样的应用，例如，时间序列的预测和模型问题。
11.3 基于超平面的单类别SVM学习模型
离群点检测是机器学习和数据分析邻域的一个重要的主题。各种各样的离群点检测的学习模型被Tax与Duin，Schouml;lkopf等，和Campbell和Bennett。这些都是基于Vapnik和Ben-David与Lindenbaum先前的工作。
11.3.1 基于超平面的-SV分类器
在这节中，我们可以先获得一个基于SV的用于双类别分类的学习模型，称为-SV分类器，其中支持向量是用核诱导固有空间内的判定超平面描绘的。双类别-SV分类器可以被转换为单类别的变体，这可被应用于离群点检测和相关的应用。
-SV分类器是由可调节的教师值得概念引出的:
(11.5)
正负超平面（用超平面各自的支持向量所描绘）的分离面被认为是
为了的到最佳的分离面，我们的目的在于同时满足两个要求：（1）一个是使得最小，（2）另一个要求是使得最大。因为两个目的内部存在矛盾，他们可以通过一个正的权重因子来平衡。这导致了一下的在固有空间的主要优化器。
收到以下硬约束
(11.6)
注意这个表达式类似于式(10.4)，式(10.4)是用在另外的SVM上的。这接下来得到了双重优化器是
(11.7)
在固有空间的主要的优化器
在两个类别间的清晰分类的设想在现实世界的应用中是不切实际的。就像模糊SVM的想法一样，通常有软约束去取代硬约束。更加精确地说，通过引入一个正的松垂变量，，硬约束可以被放松得到软约束，为了防止取代中的过度放松，一个惩罚项目，必须被加入到消耗函数中，导致了
此外，若没有一般的损失，我们可以简单的设置。这样得到了以下的主要的优化器：
(11.8)
这个表达式类似于式(10.35)，式(10.35)经常被用于传统的模糊SVM。事实上，式(10.35)可变为式11.8当教师值的大小被设置为。
更加明确的是，两个类别的amp;－SV分类器的主要表达式可以如下表达：
(11.9)
在经验空间的双重优化器
对于非负的松垂变量，一组拉格朗日乘子可以被用做导致一下双重优化的表达式：
(11.10)
LSP清晰的被封为双类别的-SV分类器，事实上
这里歧视的函数是
(11.11)
最终，决定边界被给出为。
11.3.2 基于超平面的单类别SVM
在双类别SVM的背后的基础准则是给予独立的正负训练举证。但是对于离群点检测，我们可以只得到单类别的训练向量。因为没有给出负类别的信息，事情的第一个项目是描绘或识别一个负的训练向量的合理的表达。有很多种可能的方法，其中一个可能的方法是假设一个完全随机的负模式的分布。另外一个比较常用的模型是已知的模式大概围绕在一个球面，因此潜在的负模式可能被发现在球的边缘之外。这个假设引出了基于超球面的单类别SVM模型，这是由Tax和Duin提出的。
另一个模型将镜像图片的方法应用在了创建负训练数据集。如图11.2所示，真实的数据集与虚拟的数据集各自为对方的镜像图片。更加准确的说，给定的正训练数据集中的训练向量
和负训练数据集中的虚拟训练向量
都结合到一起，有2N个训练向量，N个正的和N个负的。使用双类别的-SV分类器，变引出了接下来会提到的基于超平面的单类别SVM（OCSVM）的表达式。
在固有空间的主要的优化器
将式(11.8)应用到新创建的正负数据集，我们可以得到一下的主要优化程序：
(11.12)
在固有空间的主要的优化器
将式(11.8)应用到新创建的正负数据集，我们可以得到一下的主要优化程序：
(11.12)
图11.2. 虚拟训练向量可以引出由Schouml;lkopf等人提出的基于超平面的OCSVM学习模型
让我们探索一下式(11.12)中的正约束条件，我们可以得到
即
同样地，从式(11.12)中的负约束条件中，我们可以得到
即
结合以上公式，我们可以得到
显然对于任何一个非零常数b（正或负），只会将的大小减小，这可能会影响最大化的目的。因此，为了得到最优，有必要设置b为0。
通过设置b为0，式(11.12)中的正约束可以简化为
同样地，式(11.12)中的负约束可以简化为
两组约束明显相同，因此可以合并为一组。这引出了接下来的超平面OCSVM的主要优化表达式。
(11.13)
在经验空间的双重优化器
通过前面使用的典型的流程，双重优化表达式可以得到如下
(11.14)
注意式（11.10）中的双类别-SV分类器的约束（即）和式（11.14）中的OCSVM的约束（即）有细微的不同。对于Mercer核，这个变化是因为在OCSVM中，越小，可以得到越好的解决办法。因此，只有满足（而不是），才能得到最优。
类似地，对于双类别的案例，结果判别函数为
(11.15)
其中，根据KKT条件，自适应的教师值可以由式(11.13)得到，即
(11.16)
其中对任意一个整数i， 。最终，类别（或群边界）将由描绘，且当，测试向量将被看作一个离群点。
算法11.2 (超平面的单类别SVM学习模型) 对于给定的由但类别训练向量组成的核矩阵K，超球面OCSVM许熙模型的目的在于找到系数，得到
(11.17)
判别函数为
(11.18)
其中，根据KKT条件，自适应的教师值可以由式(11.13)得到，即
(11.19)
其中对任意一个整数i， 。最终，类别（或群边界）将由描绘，且当，测试向量将被看作一个离群点。
OCSVM的一个重要的优势在于离群点（或支持向量）的数量可以通过调整参数C来控制见式(11.25)。关于OCSVM的平移不变性，将在11.5节中提及。
图11.3. 由Tax和Duin提出的超球面的单类别SVM
11.4 基于超球面的单类别SVM
Tax和Duin提出的超球面的单类别SVM（超球面OCSVM）的原理由图11.3阐述。它的目的在于找到最小半径的球面（或超球面）来包围大多数数据，允许一小部分离群点在球面外。为了控制这部分在外面的离群点的数量，一个对离群点的惩罚必须纳入超球面OCSVM学习模型的目标函数。
在固有空间的主要的优化器
对于给定的训练数据集，核诱导训练数据集被记作，其中为了简化我们可以记为
在核诱导固有空间内，我们在被记作为的球面中心周围寻找最小半径R的包围球面。这个在图11.3中可以看出。使用一些软约束，我们可以得到一下主要优化器。
(11.20)
经过轻微的修改，在固有空间的相等地位的优化器为：
(11.21)
在经验空间的双重优化器
上述的在固有空间的优化器满足了定理1.1中的LSP条件，因此，学习模型有一个核表达式。这引出了一下的在经验空间的学习模型。
算法11.3 （超球面的单类别SVM学习模型）对于给定的由单类别训练向量组成的核矩阵K，超球面OCSVM学习模型的目的在于找到一个系数使得
(11.22)
通过应用LSP，可以得到
(11.23)
判定函数为
(11.24)
最终，只有当<!-- 剩余内容已隐藏，支付完成后下载完整资料
资料编号：[497889]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
