一种高维数据基于角度的离群数据检测近线性时间近似算法.docxVIP

一种高维数据基于角度的离群数据检测近线性时间近似算法Ninh PhamRasmus Pagh哥本哈根大学哥本哈根大学丹麦哥本哈根丹麦哥本哈根ndap@itu.dkpagh@itu.dk摘要：d维点集离群数据挖掘技术因其应用广泛而成为数据挖掘领域的一项重要课题，得到人们的深入研究。这些应用多集中在高维数据领域。当前技术的瓶颈之一就是基于距离或最近邻概念进行离群数据挖掘在高维数据情况下，效果会有所下降。根据Kriegel等人的工作(KDD ’08)，我们尝试将基于角度的离群因子应用到高维离群数据挖掘中。他们的算法有三次方复杂度（及二次方时间的逼近过程），因此我们提出一种新的基于随机投影算法，用时间近线性方法预测所有数据点的基于角度的离群因子。同时，本文方法可以用于并行环境进行并行加速。我们对近似质量进行了理论分析，以保证估计算法的可靠性。合成和真实数据集实验表明，对超高维数据集，我们的方法效率高、可伸缩性强。分类和主题描述H.2.8 [数据库管理]：数据库应用-数据挖掘泛称算法关键词：离群数据检测，高维，基于角度，随机投影，AMSSketch如果出于非商业目的复制或传播本文，且在首页携带本通知和完整注释，则允许复制本文全部或部分内容用于个人目的或课堂教学。否则，不得复制和印刷，不得存储于服务器上；若欲用于商业目的，必须获得事先批准或交费。KDD’12,中国，北京，2012年8月12-16日版权 2012 ACM 978-1-4503-1462-6 /12/08 ...10.00美元一、引言离群数据挖掘技术广泛应用于信用卡欺诈检测、网络流量入侵检测、视频监控异常行为检测等领域，因而成为数据挖掘领域的一项重要课题得到人们的深入研究。离群数据检测就是发现严重偏离数据总体分布范围的离群数据。由于与数据总体分布情况不同，因此这些数据可以看成是可疑数据。例如，对于信用卡诈骗检测问题，数据集包括卡片主人的交易信息。交易记录记载了每名用户消费行为的卡片使用情况。如果卡片被盗，用户消费行为往往会发生变化。如果交易记录消费额度高、消费频率高、消费项目重复，则可认定出现异常消费模式。离群数据挖掘技术多应用于超高维数据领域。例如，信用卡数据集交易记录有100多个属性【21】。为了对视频监控进行异常行为轨迹检测，我们必须处理连续视频帧的超高维像素特征【16】。由于众所周知的“维度灾难”问题，当前大多数算法都或多或少地需要在全维空间对欧几里德距离进行考察，因此效果欠佳。传统的基于距离【13,19】和基于密度【6,18】的离群数据检测算法，需要进行高维数据最近邻有哪些信誉好的足球投注网站，因此计算复杂度较大。此外，数据维度越高，最近邻和最远邻数据就越难以区分【1】。此时，如果还是根据高维空间距离和最近邻概念来考察数据的相邻点，就会出现大部分数据都被判定为离群数据的情况。在KDD 2008中，Kriegel等人【14】提出一种新的基于数据与其他数据角度差异的离群数据分级算法。这一算法根据角度频谱的宽度来考察各数据的离群程度，因此称为基于角度的离群数据检测算法(ABOD)。某数据相对其他数据对的角度越小，被判为离群数据的可能性就越大。由于“角度在高维空间中比距离更加稳定”【15】，因此该方法面对高维数据，性能也不会有大的波动。该算法还弱化了“维度灾难”影响，考察指标不含参数，但是对于d维n组数据，ABOD计算复杂度为。为避免三次方的时间复杂度，该算法作者也提出了一种逼进式ABOD算法版本，以提高计算效率。然而，这些近似手段仍然依赖最近邻，依次有哪些信誉好的足球投注网站相邻数据时计算复杂度仍然达到。另外，该文献没有任何相关分析以证明这些近似方法的精度。本文中，我们提出一种近线性时间算法，对各数据对象的角度方差进行近似。对d维空间的n组数据，本文算法的计算时间为，可输出各数据对象角度方差非偏估计量。本文主要技术创新就是将随机超平面投影【11，7】和乘积域AMS Sketch【12, 5】结合在一起，使得我们可以将原方法的三次方时间复杂度降低到本文近似方法的近线性复杂度。本文算法另一个优点就是支持并行处理。实际上，我们的运行时间并行加速比可以达到准线性（根据使用的处理器数量而定）水平。我们还对近似方法进行了理论分析，以保证本文估计算法的可靠性。基于实际数据和仿真数据的实验表明，我们的方法应用于超高维数据，效率高、可扩展性强。本文结构如下：第2节简要回顾相关工作，第3节介绍预备知识后给出本文算法，第4节对本文算法精度进行分析，第5节基于实际数据和仿真数据对本文算法进行实验评估，第6节对本文工作进行总结。二、相关工作对离群数据挖掘，一个良好的离群指标是保证数据挖掘效果和效率的关键。人们提出了大量离群指标，包括全局和局部离群模型。一般而言，全局离群模型对总体数据加以考虑，局部离群模型只考虑各数据对象周边部分相邻区域。K