论文部分内容阅读
异常点挖掘，是一种寻找给定数据集中潜在反常对象的重要数据挖掘技术，它在网络入侵检测，诈骗行为分析与预警，以及病症分析等领域中有着广泛的应用。异常点挖掘同分类技术、聚类技术和关联规则挖掘技术，并称为数据挖掘的四个主要研究领域。异常点挖掘的研究非常重要，主要是由于:1.它对数据分析的结果有一定的影响，异常点的存在影响了数据分析结果的准确度;2.在实际应用中，异常点挖掘可以帮助人们发现潜在的、反常的甚至是有害的对象，正确识别出异常点有利于做出较为全面和合理的决策;3.异常点挖掘经常导致新的知识的发现。 异常点还没有普遍接受的定义，对异常点的研究都是在一定的定义下进行的。异常点挖掘技术与特定的数据类型和数据环境联系紧密，具体解决方案也因各类数据的不同特征而不同。已有的异常点挖掘研究主要涉及以下几种类型的数据:流数据，时间序列数据，传感器数据和移动对象轨迹数据等，然而对空间网络中受限数据的异常点挖掘的研究较少。分析发现，已有的异常点挖掘技术并不适用于受限空间网络中的数据。空间网路中受限数据的异常点挖掘技术可用于交通拥堵分析，基础设施布局等实际应用。 已有的异常点挖掘算法中，大多是假定数据集中分布在一张单表上的，而实际应用中很多数据是分布式的。某些情况下，由于数据规模和传输距离的原因，将数据集中起来是不现实的。已有分布式异常点挖掘的研究成果是监督的(supervised)、基于合奏(ensemble)的技术，需要预先知道分布式节点各自的数据模型，然后分布式节点的数据模型被合奏起来，分布式节点使用合奏模型对其内的每个对象计算异常值。而非监督的(unsupervised)、适用于大数据量的分布式数据的异常点挖掘的研究较少。 在本文中，引入了空间网络中全局异常点的定义。并在此基础上提出了一种聚类-剪枝的策略来高效发现受限空间网络中的全局异常点。空间网络中，由于在同一条边上的受限对象呈现线性特征，使用聚类算法将在同一条边上的邻近对象压缩到聚类中，并通过一个有效的两路搜索算法KNNC估算每个聚类的K个近邻，同时，结合全局异常点的定义，能够以聚类为单位淘汰那些不可能包含top-n全局异常点的对象，将全局异常点挖掘的目标限制在一个较小的范围内，提高了全局异常点挖掘的效率。 空间网络中的局部异常点挖掘能够反映空间网络中受限数据呈现的局部特征。在空间网络中全局异常点挖掘的基础之上，引入了空间网络中局部异常点的定义。在挖掘局部异常点时，同全局异常点挖掘类似，采用聚类技术压缩空间网络中的受限数据，并以聚类为单位估量其内对象异常值的范围，剪枝不可能包含top-n局部异常点的聚类，将局部异常点挖掘的目标限制在较小的数据范围内，提高了局部异常点挖掘的效率。 针对水平分布的数据集上异常点挖掘的问题，提出了一个改进的基于Birch聚类的分布式数据集上top-n异常点挖掘的算法MOD。MOD算法中，首先各分支节点同步地构造特征向量树CF-tree，并使用K-Means算法对CF-tree的叶结点聚类生成聚类，将聚类结果发送到查询节点。在查询节点估量各个聚类异常值的范围，并排除大量的不包含top-n异常点的聚类，最后对剩余的候选聚类中的对象做具体异常值计算。MOD能够避免大量数据的传输和集中，在不太影响检测结果的准确度的前提下，较好地提高了异常点挖掘的效率。