高维数据的异常检测算法研究
发布时间：2021-06-27 07:40
异常检测旨在从给定数据中发现那些明显偏离常规模式或表现为异常行为的数据。由于在网络入侵、医疗健康、信用欺诈、文本异常、视频监控和社会突发事件监控等领域中有着广泛应用,异常检测已成为数据挖掘的研究热点,并出现了众多异常检测算法。随着现实数据的维数越来越高,异常检测面临两个困难亟待解决:一方面,数据的高维性不仅使得异常数据难以识别,而且加剧了学习模型的复杂度;另一方面,数据维数的增加导致数据之间的欧氏距离相差很小,即高维空间中任意数据之间距离非常接近,使得数据的邻域信息难以获取。因此,如何从高维空间中有效地获取数据的邻域信息是异常检测所面临的问题。针对以上问题,本文围绕高维数据的异常检测方法,从建立有效的空间映射机制、高效的获取邻域信息这两个方面开展研究,提出了三种高维数据的异常检测方法。这些方法包括基于哈希空间映射的高维数据异常检测方法、基于表征和重要度排序的异常数据检测方法以及基于稀疏表征的异常数据检测方法,实验分析表明这些方法有效提高了高维异常数据检测的性能。本论文主要工作和创新如下:1.针对在高维空间中数据的异常特性难以识别的问题,本文提出了基于哈希空间映射的异常数据检测方法。该方...
【文章来源】：浙江工业大学浙江省
【文章页数】：113 页
【学位级别】：博士
【部分图文】：
本文主要研究内容Figure1-1.Researchcontentsofthispaper
浙江工业大学博士学位论文23线表示对象之间的关系。图划分是指将图G完全划分为若干个子图G=1∪∪，各子图无交集∪=。划分时需要满足子图内的相似度高，不同子图的相似度低的条件。其损失函数可以定义为划分时各个子图之间被―分割‖的边的权重和：Cut(1,2)=∑1,1（2-34）在谱聚类方法中，将每个数据看成图中的顶点V，每个顶点之间使用边E来连接，边的权重值W表示数据之间的相关性或相似度，相关性高或相似度较高的两个数据之间的边权重值较高，相关度不高或相似度低的两个数据之间的边权重值较低，据此得到一个基于数据相似度的加权图G=(V,E),通过对该加权图进行划分，使划分后各个子图之间的区分度大，即相似度低，而属于同一个子图的数据之间的相似度尽可能高。例如图2-6中，设数据集包含A、B、C、D、E、F、G共7个数据，这7个数据可看成图中的顶点，它们之间的关系用线段连接，例如AB,AC,AD等，线段上显示的值为两个对象之间的相似度值，例如AB=0.8,BE=0.2。由图可知，B和E,D和G的相似度明显低于其他对象之间的相似度，故可以在B和E,D和G之间建立分割线，得到两个子图G1=(A,B,C,D),G2=(E,F,G),经此分割，两个子图内部的相似度高，而子图之间的相似度低。图2-6图划分例子Figure2-6.Exampleofthegraphsegmenting2.3.2图划分准则图聚类的方法将数据之间的关系使用图的形式来描述，并通过图的最优划分来实现数据的聚类。在图的划分过程中，其目标是将图G(V,E)划分成相互没有连接的k个子图，并且使划分以后每个子图内部的相似度高，而子图间的相似度低。设每个子图内点的集合为：1,2，它们满足∪=,且1∪2∪=，对于任意两个子图内点的集合,G,∩=，定义和B之间的图分割函数cut为：
浙江工业大学博士学位论文29图3-1基于哈希空间映射的异常数据检测算法框架Figure3-1.Outlierdetectionalgorithmbasedonnewspatialmapping3.2.2基于局部敏感哈希的空间映射正如第一章所述，随着数据挖掘的深入，数据中的异常值不只是作为数据分析例如分类或者聚类的附属产物而存在，在很多应用中，异常数据或者离群数据的检测已成为数据挖掘的重心[87]。在异常数据检测中，目前研究的一个难点是如何获取高维空间中数据之间的相关性信息。由于数据的相关性部分体现为邻域相关性，因此可通过数据的邻域信息得到数据之间的相关性。最近邻方法是常用的一种邻域搜索方法，它根据数据的相似性，从给定的数据集中寻找与目标数据最相似的数据项，根据这些相似的数据项构造算法来判断目标数据是否为异常数据。例如基于k近邻的异常检测中[26]，根据邻近的数据相似的特性，将不邻近的数据归为异常数据；基于密度的异常检测中[88]，根据近邻搜索构造邻域关系，以估算每个数据周围的密度，出现在极低密度的区域的数据被认为是异常数据。当数据维数较低时，用于精确最近邻搜索的数据结构非常有效，然而在当前的大数据环境下，最近邻搜索算法（NearestNeighborSearch，NN）在海量、高维数据的应用中面临着效率下降的问题。近似最近邻搜索技术（ApproximateNearestNeighborSearch，ANN[89-91]）是针对高维数据近邻检索的一种较好的策略，它在可接受的结果内以较小的精度损失得到快速搜索的目的，即在允许的范围内通过寻求近似解以提高查询速度。随着数据规模的增大，数据会逐渐形成簇状聚集的分布，根据这一特点，ANN利用聚类的方法对数据进行分类或编码后，对于要搜索的对象，ANN返回该对象所属的类别中的部分或全部数据作为检索结果。最常?
【参考文献】：
期刊论文
[1]AED-Net——异常事件检测网络[J]. Tian Wang,Zichen Miao,Yuxin Chen,Yi Zhou,Guangcun Shan,Hichem Snoussi. Engineering. 2019(05)
[2]一种基于快速k-近邻的最小生成树离群检测方法[J]. 朱利,邱媛媛,于帅,原盛. 计算机学报. 2017(12)
本文编号：3252428
【文章来源】：浙江工业大学浙江省
【文章页数】：113 页
【学位级别】：博士
【部分图文】：
本文主要研究内容Figure1-1.Researchcontentsofthispaper
浙江工业大学博士学位论文23线表示对象之间的关系。图划分是指将图G完全划分为若干个子图G=1∪∪，各子图无交集∪=。划分时需要满足子图内的相似度高，不同子图的相似度低的条件。其损失函数可以定义为划分时各个子图之间被―分割‖的边的权重和：Cut(1,2)=∑1,1（2-34）在谱聚类方法中，将每个数据看成图中的顶点V，每个顶点之间使用边E来连接，边的权重值W表示数据之间的相关性或相似度，相关性高或相似度较高的两个数据之间的边权重值较高，相关度不高或相似度低的两个数据之间的边权重值较低，据此得到一个基于数据相似度的加权图G=(V,E),通过对该加权图进行划分，使划分后各个子图之间的区分度大，即相似度低，而属于同一个子图的数据之间的相似度尽可能高。例如图2-6中，设数据集包含A、B、C、D、E、F、G共7个数据，这7个数据可看成图中的顶点，它们之间的关系用线段连接，例如AB,AC,AD等，线段上显示的值为两个对象之间的相似度值，例如AB=0.8,BE=0.2。由图可知，B和E,D和G的相似度明显低于其他对象之间的相似度，故可以在B和E,D和G之间建立分割线，得到两个子图G1=(A,B,C,D),G2=(E,F,G),经此分割，两个子图内部的相似度高，而子图之间的相似度低。图2-6图划分例子Figure2-6.Exampleofthegraphsegmenting2.3.2图划分准则图聚类的方法将数据之间的关系使用图的形式来描述，并通过图的最优划分来实现数据的聚类。在图的划分过程中，其目标是将图G(V,E)划分成相互没有连接的k个子图，并且使划分以后每个子图内部的相似度高，而子图间的相似度低。设每个子图内点的集合为：1,2，它们满足∪=,且1∪2∪=，对于任意两个子图内点的集合,G,∩=，定义和B之间的图分割函数cut为：
浙江工业大学博士学位论文29图3-1基于哈希空间映射的异常数据检测算法框架Figure3-1.Outlierdetectionalgorithmbasedonnewspatialmapping3.2.2基于局部敏感哈希的空间映射正如第一章所述，随着数据挖掘的深入，数据中的异常值不只是作为数据分析例如分类或者聚类的附属产物而存在，在很多应用中，异常数据或者离群数据的检测已成为数据挖掘的重心[87]。在异常数据检测中，目前研究的一个难点是如何获取高维空间中数据之间的相关性信息。由于数据的相关性部分体现为邻域相关性，因此可通过数据的邻域信息得到数据之间的相关性。最近邻方法是常用的一种邻域搜索方法，它根据数据的相似性，从给定的数据集中寻找与目标数据最相似的数据项，根据这些相似的数据项构造算法来判断目标数据是否为异常数据。例如基于k近邻的异常检测中[26]，根据邻近的数据相似的特性，将不邻近的数据归为异常数据；基于密度的异常检测中[88]，根据近邻搜索构造邻域关系，以估算每个数据周围的密度，出现在极低密度的区域的数据被认为是异常数据。当数据维数较低时，用于精确最近邻搜索的数据结构非常有效，然而在当前的大数据环境下，最近邻搜索算法（NearestNeighborSearch，NN）在海量、高维数据的应用中面临着效率下降的问题。近似最近邻搜索技术（ApproximateNearestNeighborSearch，ANN[89-91]）是针对高维数据近邻检索的一种较好的策略，它在可接受的结果内以较小的精度损失得到快速搜索的目的，即在允许的范围内通过寻求近似解以提高查询速度。随着数据规模的增大，数据会逐渐形成簇状聚集的分布，根据这一特点，ANN利用聚类的方法对数据进行分类或编码后，对于要搜索的对象，ANN返回该对象所属的类别中的部分或全部数据作为检索结果。最常?
【参考文献】：
期刊论文
[1]AED-Net——异常事件检测网络[J]. Tian Wang,Zichen Miao,Yuxin Chen,Yi Zhou,Guangcun Shan,Hichem Snoussi. Engineering. 2019(05)
[2]一种基于快速k-近邻的最小生成树离群检测方法[J]. 朱利,邱媛媛,于帅,原盛. 计算机学报. 2017(12)
本文编号：3252428
本文链接：https://www.wllwen.com/shoufeilunwen/xxkjbs/3252428.html
