论文总字数：29826字

摘 要

离群点是数据集中与大部分数据对象显著不同的数据对象。在一些应用中，离群点蕴含着很大的研究价值，例如网络入侵检测、金融诈骗分析等。因此，离群点检测算法的研究具有十分重要的意义。传统的离群点检测算法对稀疏数据检测的效果并不好，以大域分类数据为例，计算数据对象之间的真实距离是困难的。

因子分解机（Factorization Machines）对稀疏数据具有良好的学习能力。针对稀疏数据离群点检测，本论文设计了使用因子分解机检测离群点的FM-Outlier算法，并通过传统数值数据向稀疏数据的转化，将该算法拓展到传统数值数据的离群点检测中。其中，本论文设计了参数学习部分的LearnParameters算法，该算法使用步长自适应的随机梯度下降法。

本论文在实验中，通过使用多个数据集，对比多种算法，验证了FM-Outlier算法在有效性和效率上的双重优势。其中，验证了该算法对于稀疏数据中非零值的数目具有线性时间复杂度，当处理大数据集时，效率优势明显。

关键词：离群点检测，因子分解机，稀疏数据，随机梯度下降法

ABSTRACT

Outliers are data objects which are significantly different from most data objects in the data set. In some applications, outliers contain much research value, such as network intrusion detection, financial fraud analysis. Therefore, the study of outlier detection algorithms is very important. Traditional algorithms for outlier detection typically fail in dealing with sparse data. Take massive-domain categorical data for example, it is difficulty to compute the true distances between the data objects.

Factorization machines have a good learning ability for sparse data. To solve outlier detection problem for sparse data, this paper designs an outlier detection algorithm called FM-Outlier with factorization machines. Through converting the numerical data set to a sparse representation, this algorithm can be extended to conventional numerical data. Among them, the part of learning parameters is designed in detail as LearnParameters algorithm. This algorithm adapts stochastic gradient descent algorithm with an adaptive step-size.

This paper experimentally shows that FM-Outlier algorithm has the dual advantages of effectiveness and efficiency through using many data sets and many comparison algorithms. It shows that the algorithm has a linear complexity in the number of non-zero values in the sparse representation. That is to say, the advantage of efficiency is obvious when the data set is large.

KEY WORDS: Outlier Detection, Factorization Machines, Sparse Data, Stochastic Gradient Descent

目 录

摘 要 I

ABSTRACT II

第一章 绪论 1

1.1研究背景和意义 1

1.2研究现状 2

1.3研究目标和内容 3

1.4论文组织结构 3

第二章 使用因子分解机检测离群点 4

2.1数据预处理 4

2.1.1大域分类数据(Massive-Domain Categorical Data) 4

2.1.2传统数值数据(Conventional Numerical Data) 5

2.2使用因子分解机建模 5

2.2.1因子分解机 6

2.2.2建模过程 7

2.3FM-Outlier算法 9

2.4本章小结 10

第三章 模型计算和算法分析 11

3.1模型计算 11

3.1.1随机梯度下降法 11

3.1.2LearnParameters算法 12

3.2时间复杂度分析 13

3.3本章小结 13

第四章 实验研究 14

4.1稀疏数据存储方案 14

4.2实验设置 15

4.2.1数据集 15

4.2.2对比算法 16

4.2.3实现 16

4.3实验结果 16

4.3.1有效性实验 17

4.3.2效率实验 18

4.3.3实验总结 20

4.4本章小结 20

第五章 总结和展望 21

5.1论文总结 21

5.2工作展望 21

致 谢 22

参考文献 23

第一章 绪论

1.1研究背景和意义

随着数据时代的到来以及信息处理技术的迅速发展，人们得到的数据越来越多，大量的数据需要转化为有用的知识才能被人们有效利用。这些数据具有数据量大、数据类型多、价值密度低的特点，传统的数据分析技术已经无法对它们进行处理，因此数据挖掘作为一种新技术应运而生。离群点检测是数据挖掘的基本任务之一，它的目的是从数据集中发现与大部分数据对象显著不同的数据对象。在很多情况下，离群点都被视为无用的数据丢弃。然而在一些应用中，离群点蕴含着很大的研究价值。离群点检测已经被广泛应用到许多领域，例如网络入侵检测、金融诈骗检测、故障检测^[1]等。

传统的离群点检测算法大部分是基于距离的，这些算法对稀疏数据检测的效果并不好。稀疏数据是指那些大部分属性值都取0值的数据，本文讨论的大域分类数据是一种间接的稀疏数据，需要将其表示为二进制的形式。以大域分类数据为例，首先，计算稀疏数据中两个数据对象之间的距离是意义不大的，因为两个数据对象同一属性取值相同的概率很小，计算得到的所有Hamming距离值基本相同。再者，各种距离计算方法都无法使用属性值之间的潜在相关性。以一个电影数据集为例，它的属性中有男演员、女演员和电影类型，假如男演员Bob和女演员Alice总是出演同一类型的电影，那么两个人同时出演某一类型电影的数据记录不应该被视为离群点，这是因为属性值“Bob”和“Alice”之间存在潜在、固有的相关性，这种相关性是距离计算方法无法学习出来的。

剩余内容已隐藏，请支付后下载全文，论文总字数：29826字