论文部分内容阅读
近年来,随着传感器技术和数据库技术的迅猛发展,数据挖掘技术得到了广泛的应用,影响着人们生活的各个领域。数据挖掘技术就是从海量的、有噪声的数据集中提取新颖的、有价值的潜在知识。离群点检测作为数据挖掘的一个热门分支,主要致力于查找出相对于其他大量数据对象产生显著偏离,或不符合一般对象的行为特征的对象。目前,离群点检测主要应用于网络攻击行为检测,信用卡诈骗检测,极端天气预报,电信话费诈骗分析等领域。离群点检测的应用越来越受到关注,现有的离群点检测算法遭遇到极大挑战。主要存在如下不足：(1)数据量越来越大,数据维数越来越高,甚至达到成百上千维,而现有的离群点挖掘算法主要针对中低维的小规模的数据集,难以有效地挖掘高维海量的数据集,并且检测出的离群点是全局的,而非局部的；(2)简单的将离群点看作是一种“非此即彼”的二元属性,未能对离群点的离群程度进行评估。本文针对传统的基于密度的离群点检测算法LOF、ELSC存在的不足,主要局限在难以适应高维大数据量的挖掘,并且没有充分考虑数据对象与其邻域内对象的相对关系,挖掘过程中重复计算的步骤过多。从而提出了改进算法NELSC。本文的主要工作有：(1)针对海量的大规模数据集,本文提出了基于DBSCAN算法的剪枝策略。根据DBSCAN算法对参数敏感的特点,通过使用多组不同的数据参数,得到不同的DBSCAN聚类结果,然后对结果进行分析整合,将簇数据剪枝,得到初步的离群数据集。使用多组不同的参数是为了避免误将簇边缘的数据对象错剪,这样可以最大程度地减小数据量,降低计算复杂度,同时又可以保证检测的精确度。(2)针对传统算法对高维数据集检测低效的问题,文中提出基于信息熵的离群子空间策略,通过使用该策略,对不同的对象属性赋予不同的权值,根据不同属性权值生成不同的属性权向量,进而计算得到对象之间的熵权距离,有效地解决了高维数据挖掘中存在的“维度灾难”问题,实现了在高维空间中基于密度的局部离群点挖掘。(3)在DBSCAN算法聚类的过程中和计算局部离群系数时,传统算法的邻域查询过程中对象p的邻域查询信息仅仅用来处理当前数据对象p,该邻域查询结束后就彻底丢弃这些信息,而实际上,这些信息对p的邻域中对象的邻域查询非常有用。根据该特点,文中采用了基于记忆效应的邻域查询优化策略,有效地缩小了邻域查询范围。(4)理论证明和实验结果均表明本文改进算法的有效性和检测离群点的高效性。