论文部分内容阅读
近年来,随着数据收集与存储技术的提高,人们收集到的数据量呈指数速度增长,传统的离群点检测方法在处理大规模数据集时已开始表现出极大的局限性。大规模数据集具有数据数量大、类型繁多等特点,同时蕴藏着大量的信息或知识,而这些信息或知识只有被及时地从数据中检测出来才有可能给人们带来效益。因此,需要研究从大规模数据集中快速检测离群点的新方法,为决策提供支持。 现有的从大规模数据集中检测离群点的加速方法存在的主要局限是:(1)在进行数据划分时大多没有考虑数据之间的关联性,致使每个数据最近邻的确定涉及整个数据集;实际上,数据的最近邻只存在于某个较小范围内。(2)在分布式检测方法中,未能给出有效的终止规则和合理的数据传递模式,导致节点间的通信量大,降低了算法的总运行效率。 针对以上两个问题,本文采用BIRCH(Balanced Iterative Reducing andClustering using Hierarchies,BIRCH)聚类方法对原始数据集进行划分,并在此基础上利用簇中所包含的统计概要信息计算簇与簇之间的距离,再根据该距离给出缩小数据块查找范围的方法、数据块处理的优化方法、簇内索引的构建方法以及数据传递和数据处理顺序的优化策略。本文的主要工作如下: (1)分析比较了几种具有代表性的传统离群点检测方法;归纳总结了现有针对大规模数据集离群点检测技术的现状和发展趋势。 (2)针对现有大规模数据集中检测离群点的加速方法没有将数据集进行合理划分导致离群点检测过程计算量大、磁盘I/O频繁等问题,提出基于聚类划分的离群点检测算法。算法采用BIRCH聚类方法对数据集进行划分后,根据簇与簇之间的距离给出缩小数据块查找范围的方法和数据块处理的优化方法。缩小数据块的查找范围可以减少数据点之间的比较次数从而减少距离的计算量,优化的数据块处理方法可以减少磁盘I/O次数,两者相结合可有效提高算法的检测效率。 (3)针对现有基于分布式的离群点检测方法没有对原始数据集进行合理划分,且未能给出合理的终止规则和有效的数据传递模式的问题。本文提出一种基于聚类和索引的分布式离群点检测算法(Distributed Outlier Detection based onClustering and Indexing,DODCI)。该算法既考虑了数据的划分,又考虑了数据的处理顺序以使后续剪枝过程的剪枝因子能在初始阶段获得一个较高的值,进而提高剪枝效率。同时,算法在分布计算的过程中还结合了两个优化策略和两条剪枝规则,以减少节点之间的通信消耗。 (4)为了方便测试本文所提算法,设计并实现了一个简单的离群点检测原型系统。该系统是在Visual C++6.0平台上,使用C++语言并结合面向对象的编程思想来实现的。