论文部分内容阅读
随着互联网技术的进步,数据挖掘这一学术领域正在日益发展,离群点检测作为其重要组成部分之一,目的是找出异常的数据信息。迄今为止,离群点检测的相关技术已经在网络安全、社会分析等诸多领域中被应用。在离群点检测系统中,随着上层业务的不断拓展,系统在同一时间段内所接收到的查询请求不断增多,而处理的时效性要求也不断提高,这也对离群点检测算法的性能提出更高的要求。而现有的离群点检测算法绝大多数都是面向单个查询,这使得系统在短时间内处理大量查询请求时的性能不佳,降低了用户的使用体验感。因此,本文主要针对离群点检测的多查询问题展开了相关研究,主要贡献点如下:(1)提出了一种面向单查询的高效离群点检测算法——RODA_SQ(R-tree Outlier Detection Algorithm-Single Query)。首先,该算法对传统的空间索引R树进行扩展,即为R树中的每个结点添加了密度属性,并提出了一种估算数据点离群度的新型方法。然后将离群点在空间中的存在特性与扩展后的R树索引相结合,通过从R树中选出较小密度的结点,并优先计算该结点内离群度较大的数据点,能够快速地在初始时确定一个较好的阈值实现过滤。与此同时为了提高过滤的效果,将采用新型的批量过滤定理帮助实现过滤,从而加快检测的效率。(2)在RODA_SQ算法的基础上,提出了一种面向多查询的高效离群点检测算法——RODA_MQ(R-tree Outlier Detection Algorithm-Multiple Query)。首先将用户给定的多个查询任务进行分组,保证分组内的查询任务尽可能多地共享重复计算的部分,加快多查询处理的检测速度,并减少内存浪费;然后对于组内的多个查询任务进行查询处理操作,直到所有查询分组全部处理结束。RODA_MQ算法通过深入分析实现了多个查询之间的共享机制,经过一次处理可以完成多个检测任务,使用户的需求量得到满足并加快检测速度。(3)分别用真实数据集和人工合成数据集从多个方面验证本文提出的RODA_SQ算法和RODA_MQ算法。实验结果表明,与现有的相关算法相比较,无论是在面向单查询还是面向多查询进行处理时,本文提出的算法在运行效率上均有提高,而且具有良好的实用价值。