论文部分内容阅读
离群检测技术是数据挖掘的关键任务之一,主要目标是挖掘新奇的数据点及其生成模型或机制,为用户深入分析和理解数据提供支撑。离群数据点往往蕴含着重要的有意义的信息,需要结合数据挖掘、数据分析和大数据等理论和技术方法来深入的探索和挖掘。近年来,离群检测在信用卡盗刷、股票内幕交易、网络入侵、医疗健康、军事侦察和关键系统保障等多个领域都有着愈来愈多的应用需求。随着现代网络技术发展和移动应用的广泛普及,人类社会产生并存储了海量的高维数据、不确定数据,流数据等非结构化复杂结构类型的数据。面对这些爆炸式增长的复杂数据集,如何有效的挖掘出其中隐藏的离群数据点并分析其背后的机制是一个极具挑战性的课题。本文针对离群检测任务中不确定性数据和高维数据呈现的问题进行探讨,并进行了相关实验验证。主要内容和成果如下:(1).针对不确定数据中增加概率维度使得数据存储、处理和结果展现都变得模糊,无法直观感知等问题,提出基于局部信息的离群检测模型(ULOF):结合数据点局部不确定性程度和局部密度信息来计算不确定数据集中每个数据点的不确定性局部离群因子(ULOF)。该模型有效的利用了数据的不确定性程度信息来挖掘数据集中的离群点,用最小二乘法拟合的高次多项式来表示数据点之间距离值的概率密度分布函数,泛化了经典LOF算法的定义、概念和公式表达。为优化计算,提出:1)用动态规划的计算方法在多项式时间内评估Po(k_d)(在k_d距离内点o有至少k个邻居的概率),避免了指数级别时间复杂度的困难;2)估算K-η-distance距离的尽可能窄的可能取值区间,并在区间内用迭代算法进一步计算其精确取值;3)用剪枝策略来减小数据点近邻的候选集规模。在多个人工和真实数据集上进行算法性能评估,并与当前最先进的不确定数据离群检测技术比较,实验结果显示ULOF算法在检测精度和时间性能都有明显的优势。(2).针对高维数据中是“维度灾难”让距离度量不能表达原有的物理意义,在全维度空间直接建立离群挖掘模型的计算效率低下等问题,提出以相关近邻数为局部权重的角度余弦方差作为数据点离群因子的高维离群检测模型(LW-ABOD)。通过增加数据点的局部信息权重,能够有效的避免把聚簇边缘的数据点误判为离群点而遗漏了不同聚簇之间的离群点。为优化执行效率,提出:1)采用随机投影技术把原始数据集投影到低维空间中,在新的空间中建索引结构并搜索数据点的-近邻;2)用累加计算的形式(ACC-ABOF)来优化原有多层循环计算的角度方差的方法,时间复杂度可降低近一个数量级;3)进一步地提出增量计算模型(FU-ABOD),避免新的数据插入时需要重新计算整个数据集。在多组实验验证和比较证实了该算法非常适用于流数据和有实时性需求的应用。(3).针对高维数据分布非常稀疏且子空间数目和维度数成指数增长等问题,提出在多个相关子空间中来挖掘高维离群数据点(RSub)。该方法的核心是通过属性之间的协方差矩阵对应的正交特征向量和特征根进而推断评估属性之间的依赖和相关关系。与寻找最大方差所表示的主要成份相反,较小的特征根所对应的特征向量表示的属性之间冗余度比较高,相关性比较强。子空间相关性强弱和维度数量不同对检测结果影响程度也不尽相同:1)子空间的相关性越强对挖掘离群数据点的作用也就越大,因此子空间相关性强度可作为计算离群程度的权重因子;2)子空间的维度越大数据分布也越稀疏,因此要根据维度数量来调整计算近邻的距离值,使不同维度子空间中计算结果具有可比性。RSub算法能够在多项式时间内直接找到相关子空间,避免了指数数量级子空间的遍历,实验结果显示其时间效率远远优于其它基于子空间的离群检测算法。