不确定数据流上的离群点检测处理

提出了一种快速不确定数据流上的离群点检测算法. 采用分层次划分思想给出了适用于流式数据的索引构建方法,并为索引结构中的叶子结点增加了部分存储信息,使得在数据更新时新流入的数据点可以利用中间结果信息直接完成批量过滤,降低计算成本. 通过分析离群概率值求解的递推规律,给出了一种全新的离群概率值求解方案,该方案可以最大可能地避免全近邻集合的迭代计算,减少了大量的非离群点计算代价,从而加快处理速度. 实验结果表明,快速不确定数据流上的离群点检测算法能够有效地提高检测效率.     

PSP：一种高效的偏序域上skyline查询处理方法

为解决偏序域上的skyline查询问题,本文提出一种高效的偏序域上的skyline查询处理方法,来满足人们对查询效率日益增长的需求.首先,为提高偏序域上skyline的查询效率,将倒排索引引入skyline查询,提出一种基于倒排的索引结构.其次,提出基础算法(Basic Partially-ordered Skyline Processing based on inverted index,PSP_B),PSP_B包含两个阶段:第一阶段,能够通过映射将偏序域转化成全序域,并建立倒排索引;第二阶段,通过倒排索引提前找到扫描结束点,得到最终的skyline结果.再次,在PSP_B的基础上,进一步提出优化算法(Improved Partially-ordered Skyline Processing based on inverted index,PSP_I).PSP_I通过先分组再建索引的方法能够进一步提高计算效率.最后,用大量的实验证明本文所提算法的正确性和高效性.     

异构分布式环境中的并行离群点检测算法

离群点检测是数据挖掘领域研究的热点之一,主要目的是识别出数据集中异常但有价值的数据点. 随着数据规模不断扩大,使得处理海量数据的效率降低,随即引入分布式算法. 目前现有的分布式算法大都用于解决同构分布式的处理环境,但在实际应用中,由于参与分布式计算的处理机配置的差异,现有的分布式离群点检测算法不能很好地适用于异构分布式环境. 针对上述问题,本文提出一种面向异构分布式环境的离群点检测算法. 首先提出基于网格的动态数据划分方法（Gird-based Dynamic Data Partitioning,GDDP）,充分利用各处理机的计算资源,同时根据数据点的空间位置信息进行数据划分,可有效减少网络通信. 其次基于GDDP算法,提出了异构分布式环境中并行的离群点检测算法（GDDP-based Outlier Detection Algorithm,GODA）. 该算法包括2个阶段：在每个处理机本地,按照索引中数据点的顺序进行过滤,通过2次扫描得到离群点候选集;判断候选离群点需要进行网络通信的处理机,使用较低网络开销得出全局离群点. 最后,通过大量实验验证了本文提出的GDDP和GODA算法的有效性.