英语原文共 35 页，剩余内容已隐藏，支付完成后下载完整资料

基于流数据的奇异值检测

摘要

在大数据分析中，数据通常是以流的形式出现。近几年一些研究在流数据方面研究奇异值检测。多种方法在各领域被提出并验证。这些研究的核心方法可以为提高现有方法的性能提供帮助，并兼容新的应用，以及为今后的研究明确关键问题。本文提出并分析了基于流数据的奇异值检测的各方面问题，包括离线和在线层面、各层的级数、集成与单一分类器、监督学习与非监督学习、模型更新的决策信息、过时信息的遗忘机制、特征漂移的处理、从奇异值中区分噪声和离群值的方法、未知标签的分类策略、如何解决重现类。同时，本文也描述了文学研究领域中流数据奇异值检测的几个应用，探讨了关键的挑战点和未来的研究方向。

关键字

奇异值检测 流数据 检查 分类器

1 简介

奇异值检测（ND）是从未知领域对明显不同的无标签样本数据进行分类的方法。由于它是学习系统中很重要的功能，所以收到了机器学习和数据挖掘研究者的极大关注。从文献中，能找到奇异值检测的很多定义，比如：

找到一个输入与之前输入的不同点（Perner 2008）。

奇异值检测关注的是找到系统的异常行为和从一个规律到另一种规律的突变（Lee and Roberts 2008）。

异常值检测能识别新奇的特征，这个特征可能是新出现的，还能识别已知特征和噪声中出现的新特征（Gama 2010）。

之前的研究着重从批处理层面开展，这些数据都是已存在并可以直接读取的。然而，如今奇异值检测在流数据领域出现重大挑战。

流数据（DS）是持续到达的数据段，他是持续不断的、无限的、高速流动的、有不断改变的数据类型。在流数据领域，新特征不断出现，现有的特征可能消失或不断演进。

由于特征不是不改变的，所以基于流数据的奇异值检测技术的应用有诸多挑战，包括：

特征漂移，很难区分新特征与已知特征的改变；

噪声与离群值，很难与新特征进行区分；

特征重现，很难与新特征进行区分；

特征演进，当同类问题的数量随着时间的推移增加，这些新的类需要被纳入决策模型。

许多奇异值检测在流数据应用中是很重要的，比如：干扰检测、错误检测、医疗诊断、图像特殊部位的检测、欺诈检测、森林覆盖类型检测、垃圾邮件过滤、信息检索和文本分类等。

本文的研究主要是描述和分析基于流数据的奇异值检测的主要算法。重要的研究包括奇异值检测、异常检测和孤立点检测。但是，这些都是针对批处理数据，没有着重解决流数据问题。同时，这些研究仅关注奇异值检测的分类器技术这一个方面。

近几年，一些研究者发表了几种基于流数据的奇异值检测的方法。这些研究的主要成就可能为新技术的发展带来有价值的灵感。例如，这个研究包括几个不同的基于数据流的奇异值检测层面：

流数据分析的主要方法；

格式化基于流数据的奇异值分析，明确区分离线和在线阶段；

基于流数据的奇异值分析的主要方法分类；

学习任务；

两个阶段的类和分类器的数量；

模型更新的外部反馈；

遗忘机制；

处理噪声与离群值；

处理复现的类；

进化策略。

本文组织结构如下。

第2.1节，指明奇异值检测、异常检测和离群值检测的主要区别。

第2.2节，解释流数据的两个重要方面，特征漂移和特征进化。

第3节，形式化基于流数据的奇异值检测。

第4节，阐述基于流数据的奇异值检测方法的分类。

第5节，阐明离线学习的细节。

第6节，阐明在线学习的细节并讨论实践中的三个任务：新样本数据的分类，奇异值特征的检测和决策模型的更新。

第7节，讨论基于流数据的奇异值检测在处理噪声和离群值的其他关联方面，复现片段和进化策略的检测。

第8节，讨论本文的主要优缺点。

第9节，描述基于流数据的奇异值检测的主要应用。

第10节，讨论未来工作的主要挑战。

2 关键定义

本节阐明我们理解的奇异值、异常和离群值检测的主要区别，包括，奇异值检测的关键概念，比如：特征漂移和特征演进。

2.1 奇异值检测（Novelty Detection）、异常值检测（Anomaly Detection）和离群值检测（Outlier Detection）

奇异值检测、异常值检测和离群值检测是相互关联的概念。在某些情况下，他们三个代表同一种意思，用法完全相同，在这里我们来区分一下。一般地，后两个术语更相似，经常用来表达很接近的问题。

事实上，奇异值检测、异常值检测和离群值检测与模式寻找相关联，不同在异常、常见和模式。异常和离群值代表非预期的值，奇异值代表新出现的需要和标准模式关联的特征。

根据Chandola et al. (2009)，异常检测代表从非预期行为的数据中寻找模式。这些模式涉及异常、极端值、不和谐的观察、期望值、象变、惊喜、奇异或污染物。奇异值检测目标是从数据中探测未发现的模式（突然的、新奇的）。但是，这个术语不同于异常检测，因为，首先，奇异模式典型和标准模式相关联。

在文章Aggarwal (2013)，作者把极端值定义为一个数据点，可以把这个值看作异常值或噪声，然而一个异常值代表一个特殊类别的离群值，这是一个有趣的研究点。根据Gogoi et al. (2011)，离群值可能是一种对系统有害的突变数据，比如通过产生不正确的结果、错误的模型和有偏差的参数估计。离群值导致的后果包括有害的活动、方法错误、环境的改变、人为错误等。需要一组简洁的例子作为奇异数据出现的证据。另一方面，少量与规定的标准值有较大特性差异的孤立值可能被视为离群值，因为没有代表其合理的规则。

根据Marsland et al. (2002)，奇异值检测在训练集中存在未发现的类别时是非常有用的。Markou and Singh (2003a)表明，对于许多问题，我们不知道当前训练集数据中是否包含所有可能的类别，所以奇异值检测是一项很重要的任务。根据Gama (2010)，奇异值检测能识别非标签数据的奇异特征。

在本研究中，我们把奇异值当做紧密相关且有代表性的数据集，他们产生的新特征与决策模型相关联。这个新特征与已知特征不同，他代表着特征进化，例如，新类别的出现。不能被现有特征解释的孤立的、无代表性的、无关联性的元素集被视作离群值。所以，这些值需要被识别分类，但不是添加到现有模型中。

2.2 特征漂移（Concept Drift）和特征进化（Concept Evolution）

在特征学习中，特征是通过学习算法得出的方法，用来定义一组训练数据集，把输入值映射到有关联的输出值。在流数据方面，这些特征表示不稳定的环境，这些特征非静态的，会随着时间进化改变。所以，可能产生两种重要的现象就是特征漂移和特征进化。

根据Dries and Ruuml;ckert (2009)，特征漂移在机器学习和数据挖掘中是非常重要的问题，被描述为数据分布的重大意义的改变。特征可能依赖于一些隐藏的上下文，隐藏在上下文中的特征可能引起目标特征的改变，从而产生特征漂移。有多种类型的特征漂移，具有突发性、增长性、渐进性和重现性。

Tsymbal (2004)表明，处理特征漂移的一个困难是区分真是的特征漂移与噪声。举个例子，如果特征是特定空间的图像，他坑你改变形状、大小和位置。特征漂移的例子有疾病特征的改变、气候的改变、多年采购特征的改变等。

为了处理特征漂移，blind和informed两种方法被用来适应决策模型。Blind方法以固定时间间隔更新决策模型，而不论改变是否真的发生。一般地，决策模型使用最新的数据重训练。Informed方法仅在改变被发现时采取更新决策模型。大多数奇异值检测算法使用blind方法去确定特征漂移。

流数据的另一个方面是特征进化。传统的机器学习算法假设类别被事先定义，每一个示例数据属于其中的一个类别。然而，这个假设不适合真实的流数据，因为可能并不知道离线训练阶段所有的类别，而新到来的数据可能不能与已存在的类别匹配。Masud et al. (2011a)认为，数据流中出现新类别将引起特征进化。特征进化也称为类别出现，这项研究就像网络干涉侦测，垃圾邮件分类和文本分类。

很重要的一点是异常值检测必须处理特征漂移，新类别的出现和离群值。奇异值检测算法应该能探测特征漂移，并更新据测模型来表示已知特征的改变，探测出现的类别，以及使用新类别更新决策模型，识别并舍弃噪声和离群值。

3 问题形式化

数据流是高速不间断到达的一系列数据，且其分布会随时间不断变化。

定义1 数据流（Data Stream）一个数据流S是大量无穷尽达到的多维度数据，如在时间T₁,T₂,T₃hellip;,T_Nhellip;有N维数据x₁,x₂,x₃hellip;,x_Nhellip;每一个x_i被描述为一个n维向量(Aggarwal et al. 2003)。

数据流是时间序列上一系列数据集。Han (2005)认为，一个序列数据集是一个按时间排列的序列，可能没有准确的时间概念。数据流是典型的多变量序列,时间的概念并不总是存在。网页浏览过程和用户消费交易过程是一个数据序列例子，但可能不是时间序列的数据。一个时间序列是随机变量连续观测的数字序列，它代表一种相邻数据间依赖的内在特性的例子。在数据流中，这种依赖并不一致发生，有时相邻示例完全不相关。但是，持续高速到达的时间序列可以被视作数据流。

一般地，基于流数据的奇异值检测算法分为离线和在线两个阶段。离线阶段，一个被标记的数据集可以生成一个分类器。这些被标记的数据代表已知的特性。从此，我们把这个已知特性成为简单特性。通常，已知特性是由标准类的样本数据组成。在线阶段，不论新的数据何时到达，他被归类到某个标准类或被拒绝（归类为异常、奇异、离群值）。这是单一分类器的通常设置。

近来，几位学者将此框架拓展到多类别。在此情况下，之前的形式化必须推演到多类情形。在新一代离线阶段中，每一个训练集中的样本数据都有一个标签yi，yi isin; Ytr, 其中Ytr = {Cknw1, Cknw2, . . . , CknwL}，Cknwi代表第i个已知类，L是已知类的数量。在线阶段，新数据到达时，可能产生新的类别，将扩展类别集为Yall = {Cknw1, Cknw2, . . . , CknwL, Cnov1 . . . , CnovK }, 其中Cnovi 代表第i个新奇类，K为已知的新类数量。

定义2新奇类（Novel Class）仅在线阶段能发现，不能在离线训练阶段发现。

图1 新奇类检测示例

初始，一个分类器只能有效处理已训练类中的样本数据，当数据流中的样本数据不属于已知类，而属于新奇类时，这些数据将被暂时归类为未知。

定义3未知类（Unknown）是数据不能被已知模型解释的类。在单类分类器中被称为反常类、异常类或奇异类，比如样本数据不符合标准特性时。有些情况下，这是充分的。基于多类分类器任务，一组未知数据可以归纳为新特性。

未知数据输入奇异值检测任务是为了生成不同的奇异模型，如图1。

定义4奇异值模式（Novelty Pattern）被识别为未标记的样本数据，初始被分类系统归类为未知类别。

尤其要强调的是，在流数据分类任务中，除了奇异类的出现，被称为特性进化，另特性漂移现象也需要注意。在此情况下，已知特性会随时间迁移而改变。

定义5特性漂移（Concept Drift）每一个样本x_t是从相应数据流D_t产生的。如果在t₁,t₂时间产生的数据x₁,x₂对应的数据流D₁,D₂不相等，则说明产生了特性漂移。

从已知类别的改变中区分新类的产生式流数据研究中很关键的问题。为了找到流数据中发生的每一次改变，而不是识别特性漂移去更新决策模型，奇异值检测算法通常能直接更新决策模型。如果没有处理特性漂移的方法，那么已知特性的每次改变都将检测为奇异值模式。相应的，有必要舍弃过时的特性。

同时，噪声和离群值都应被视为奇异值模式，因为他们代表孤立的或无关联的数据集。

下一节将概述本文在文本领域基于流数据的奇异值检测的主要研究。

4 基于流数据的奇异值检测的概述

本节将介绍一个对流数据的奇异值检测算法分类的分类系统。这个分类系统主要对文本进行研究，如要特性如下：

- 离线阶段

- 类型数量（一个或多个）

- 分类器数量（单一或全体）

- 学习任务（监督式或分监督式）

- 在线阶段

- 分类

- 未知标签分类（是或否）

- 分类器数量（单一或全体）

- 奇异模式检测

- 奇异类别的数量（一个或多个）

- 模型更新策略

- 外部反馈（有或无）
- 分类器数量（单一或全体）

- 遗忘机制（有或无）

- 其他

- 处理离群值

- 处理复现上下文

- 方法演进

相关算法罗列在表

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[137202]，资料为PDF文档或Word文档，PDF文档可免费转换为Word