面向大数据的高效Top-n局部异常检测方法

发布时间：2021-01-15 06:15

　　近年来,随着各类智能移动设备的广泛普及,社交网络、网上购物、移动支付、位置服务等新兴应用不断涌现,各类海量大数据被采集和处理,而面向这些大数据的挖掘分析服务已俨然成为一大独具特色的新兴产业。异常检测作为数据挖掘最重要的任务之一,在网络监控、信用卡欺诈等各种应用领域都被认为是至关重要的内容。此外,在实际生活中,数据分布往往是倾斜的,而局部异常检测能够有效解决数据倾斜分布下的异常检测问题,在很多应用领域具有较好的检测效果。因此,局部异常检测在学术界和工业界都受到了越来越多的关注,本文为了更加高效快速地检测出海量大数据中的异常对象,提出了两个基于密度的局部异常检测方法,主要研究内容如下:（1）在面向静态大数据异常检测方面,提出了一种快速的top-n局部异常点检测算法,融合索引结构和多层LOF上界设计了多粒度的剪枝策略,以快速发现top-n局部异常点。首先,提出了四个更接近真实LOF值的上界,以避免直接计算LOF值,并对它们的计算复杂度进行了理论分析;其次,结合索引结构和UB1、UB2上界,提出了两层的Cell剪枝策略,不仅采用全局Cell剪枝策略,还引入了基于Cell内部数据对象分布的局部剪... 

【文章来源】：烟台大学山东省

【文章页数】：83 页

【学位级别】：硕士

【部分图文】：

图３．１两与ｄｉ５ｔ（ｇ，ｏ）的关系示例??

３＿基子密度的ｔｏｐ＊局部异常点快速裣测算濃??索引和ＬＯＦ上界的剪枝方法，无需对每个数据对象进行计算即可剪枝掉高密度ｇ域??内的所有数据对象。??基于Ｃｅｌｌ的全局剪枝．对于某一高密度区域内的数据对象，如果能够保证所有??数据对象的ＬＯＦ值上界小于临界值ｃ／，则该区域内的所有数据对象都可以直接??被剪枝掉。给定边长／ｅ？ｓｉｄｅ，将整个数据空间按照／？；＿为单位长度划分，得到的每??个子空间划分称为一个Ｃｅｌｌ，如图３．３所示，包括了?９个Ｃｅｌｌ，中间Ｃｅｌｌ记为Ｃ。??考虑使甩上界册咖），给定一个高密度的Ｃｅｌｌ?如果对于Ｖｐ?ｅ?Ｃ，Ｌ＾（ｐ）?＜?ｃｔ，??则该Ｃｅｌｌ中所有的数据对象都可以直接被剪枝掉Ｄ??引理３．１〔基于Ｃｅｌｌ的全局剪枝）．给定一个Ｃｅｌｌ，记为Ｃ，?ＬＯＦ剪枝临界值成??如果Ｃ包含的数据对象多于々个，弁且其边长Ｚｅｎｓｉｄｅ?Ｓ?为数据的维度），??那么Ｃ中所有的数据对象可以直接被剪枝。??证明．由定理?３．１?可知，ＬＯＦ（ｐ）?Ｓ?ｆ／Ｓｊｐ）?＝?ｄｉｓｔｆｃｒ＾／ｊｊＡ＾ｐ）卜?ｃｐｍｉｎ］，只：需??证明Ｖｐ?Ｇ?Ｃ，ｆ／ＳＪｐ）幺?Ｃｔ即可，也就是证明ｄｉｓｔｆｃｒ（ｐ）／｜ｉＶｆｃ（ｐ）丨幺?Ｃｔ＊?ｃｐｍｉｎ．。??，．．．Ｂ，??ｌｅｎｓｉｄｅ?－?？?ｒｊ?？?２＾ｄｎｅｒｉｓｉｄｅ??ｒｊ?＊?？??图３．３?．暴矛Ｃｅｌｌ素：引的剪枝示例??由于Ｃ包括多于Ａ？个对象，所以对于任一对象ｐ?ｅ?Ｃ都可以在Ｃｅｌｌ对角线Ｗ?＊??Ｚｅｎｓｉｄｅ范围内找到众近邻，即ｄｉｓｔｆｃ（ｐ）?Ｓ?Ｗ?＊?Ｚｅｎｓｉｄｅ；对于ｐ的众近邻，在：最坏情??况下．，都可以在

?烟台大＿硕士学位论文???如果ｉｅｎｓｉｄｅ?幺?ｃｔ?＊?ｃｐｍｉｎ／２Ｖ＾，则?２Ｖ＾?＊?Ｚｅｎｓｉｄｅ?幺?ｃｔ?＊?ｃｐｍｉｎ，那么??ｄｉｓｔｋｒ（ｐ）／＼Ｎｋ（ｐ）＼?＜ｃｔ＊?ｃｐｍｉｎ〇??？?－?＊?？??？?？?？?？?？??Ｊ?？?＊??＾１?９??？?＾４?參??图３．４区域划分示例??传统Ｃｅｌｌ划分方法将整个数据空间按照全局的边长划分，从引理３．１可知，高??密度区域的剪枝条件除了与Ｃｅｌｌ内的数据对象数量有关，还要求Ｃｅｌｌ的边长不大于??ｃｔ＊ｃｐｍｉｎ／（２Ｖ＾）。很麗，该边长条伴与ｃｐｍｉｎ较小时．，将严童影响被剪枝掉的高??密度Ｅ域的数量。??基于上述考虑，本章采用文献［５０］提出的均匀区域生成方法，首先将整个数据??集按照数据对象分布划分成几个相对独立的数据分布相对均匀的区域，每个区域独??自处理数据对象，即分区自治。具体的划分方法分为两步，１）首先将整个数据空间??看成根节点，然后按照二叉树迭代地划分数据空间，直到每个叶子节点至少包括々??个数据对象且不可再分；２）从叶子节点向上合并节点，如果两个子节点内部数据对??象间最小的距离ｃｐ＾ｉｎ和ｃｐ＾ｉｎ的大小比例小于ｄｉｆｆ，即??ｍａｘ｛ｃｐ＾ｉｎ，?ｃｐ＾ｊＪ／ｍｉｎｔｃｐ＾ｊ＾ｃｐ＾ｎ｝?＜?ｄｉ／／，则合弁这两个子节点，直到不能再向??上合并，一个独立的区域被生成。通过设定适：３的比例＾■，可以将两个分布相似??的子节点合并，■此，可以得到相对分布均匀的区域。如图３．４所示，根据数据密??度分布生成４个均匀．区域，每个区域内即可采用一个ｃＰ］＾ｉｎｉ行基于Ｃｅｌｌ的全局剪??枝策略。??虽

【参考文献】：
期刊论文
[1]一种基于快速k-近邻的最小生成树离群检测方法[J]. 朱利,邱媛媛,于帅,原盛.  计算机学报. 2017(12)
[2]不确定数据基于密度的局部异常点检测[J]. 曹科研,栾方军,孙焕良,丁国辉.  计算机学报. 2017(10)
[3]促进大数据发展行动纲要[J].   成组技术与生产现代化. 2015(03)
[4]BOD:一种高效的分布式离群点检测算法[J]. 王习特,申德荣,白梅,聂铁铮,寇月,于戈.  计算机学报. 2016(01)
[5]基于动态网格的数据流离群点快速检测算法[J]. 杨宜东,孙志挥,朱玉全,杨明,张柏礼.  软件学报. 2006(08)



本文编号：2978394