离群点是数据集中极少数与主流数据显著不同的数据点,它们往往比主流数据更具价值。离群检测在许多领域都有着广泛的应用,吸引了包括数据挖掘、知识学习、统计学和信息论等众多学科研究人员的共同关注。多年来,已有基于各种技术针对各类数据的离群检测算法提出,但针对高维海量数据离群点检测的时间复杂度间题,始终没有得到较好的解决。基于近邻检测技术虽具有无需监督,不需要对数据的分布作任何假设等优点,但需搜索每个数据点的近邻,导致O(n2)的时间复杂度,限制了算法在高维海量数据上的应用。设计既有效又高效的针对高维海量数据的离群点检测算法有着重要的理论和实际意义。剪枝非离群点,减小目标数据集的大小是降低时间复杂度的有效手段。如果数据对象的r邻域内邻居的个数达到K个以上,则该数据对象不是DB(k, r)离群点。进一步地,如果数据对象的r/2邻域内邻居的个数达到K个以上,则该邻域内的所有对象都不是DB(k, r)离群点。利用这一剪枝规则,可以排除大量的非离群点,从而大大减小目标数据集的大小。只需通过对数据集的一次扫描即可作到这一点：以第1个点为组中心开始,顺序扫描数据集,凡与某个组中心的距离小于r/2的即被标记为该组,凡与任何组中心的距离都不小于r/2的,自动成为新的组中心。扫描结束后,凡组的大小达到K的,组内所有数据点都被剪枝掉。在检测TOP n离群点时,剪枝不必要的近邻搜索,是减小时间复杂度的第二种有效手段。以迄今为止找到的n个候选离群点中的最小K距离为闽值,一旦发现某个数据点迄今为止已搜索到的k距离比这个阈值还小时,立即停止k近邻的搜索,因为该点没有机会成为TOP n离群点。抽样也可以减小数据空间,是减小时间复杂度的第三种有效手段。但传统的均匀抽样技术,缺乏伸缩性。密度偏倚的抽样技术可以用更小的样本代表相同的数据集,且更具灵活性。如果样本由离群偏倚抽样方法所得,则可仅在样本空间内检测离群点,这等于缩小了目标空间的大小。如果样本由密度偏倚方法抽样所得,则可仅在样本空间探索一个k值较小的近邻,这等于缩小了k近邻的搜索空间。此外,数据集中的两个点关于同一样本的距离差一定小于这两个点间的距离,利用这一性质,还可以估算K距离的下界,甚至取代K距离的计算,以获得较小的时间复杂度。基于抽样的离群检测算法仅需对数据集进行三次扫描即完成离群点的识别：第一遍,密度估计；第二遍,完成抽样；第三遍识别离群点。条件离群点是近年来提出的一类新的离群点,已提出的基于近邻的条件离群点检测算法,因参数设置过多,且检测结果受参数影响太大,有一定操作难度,缺乏应用性。通过对现有算法的改进,去掉不易设置的参数,提高了算法的应用性。从本质上讲,一个数据点是否为离群点,与数据点值的大小无关,与两个数据点的距离也无关,仅与其值在数据集中的分布概率有关。数据点的值在数据集中出现的概率越低,其离群程度越大,反之,离群程度则越小。信息熵正是刻画这一特性的工具。从数据集中删除正常数据后熵变大,删除离群数据后熵变小,变小的幅度越大,离群程度越高。但目前已提出的基于信息熵的离群检测算法其熵计算方法过于复杂,为计算一个数据对象的离群度,需两次计算熵,再计算熵的变化量。而计算熵需首先计算数据集在各维度上所有属性值的概率分布,这通常需要一定的时间复杂度。然而,可以证明,删除数据对象后引起熵的变化量,可由删除前的熵以及数据对象自身各属性值的概率分布计算得出。而数据对象的离群度仅与后者有关。为此,将该值定义为熵离群度。基于熵离群度的算法仅需扫描数据集两次即可识别出离群点,进一步降低了时间复杂度。