基于X*树的反k近邻流数据离群点挖掘算法研究

• 作 者: 梁永欣
• 机 构: 燕山大学
• 出 处: 燕山大学
• 发表日期: 2009年期
• 关键词: 数据挖掘 数据流 离群点 X*树 k近邻 反k近邻 滑动窗口

数据流数据挖掘技术是信息科学领域的前沿研究课题之一,被公认为是数据挖掘研究中一个极富应用前景的领域。在众多的数据流数据挖掘算法中,挖掘离群点是其中一个重要的研究内容,构建支持k近邻查询的高效索引结构又是挖掘流数据离群点的关键问题之一。迫切需要在有限运行空间上,通过对数据流进行一次或较少次数的扫描有效地进行流数据离群点挖掘。在这种情况下,本文对国内外关于数据流离群点研究现状进行了综合分析比较,主要在以下几个方面研究了基于X*树的反k近邻流数据离群点挖掘算法。首先,研究了支持k近邻查询的X*树索引结构。针对X树数据索引结构在进行k近邻查询时所需要的时间和空间开销存在着严重的效率问题,提出了适合进行k近邻查询的新的数据索引结构结点分裂算法,提出了X*树索引结构,它比X树需要更少的存储空间,不需要额外存储结点分裂的历史信息。其次,研究了流数据离群点的挖掘算法,通过对已有相关算法进行的全面深入地分析,发现它们不能及时地捕捉流数据的概念漂移信息,而且需要对数据集进行多遍扫描才能给出挖掘结果。因此,提出基于反k近邻的流数据离群点挖掘算法,该算法只需对当前窗口扫描一次。最后,选用真实数据和仿真数据进行实验,通过实验结果验证了本文所提出的支持k近邻查询的X*树索引结构和基于反k近邻的流数据离群点挖掘算法的可行性和有效性。