摘要：在数据密集型计算环境中，数据的海量、高维、分布存储等特点，为数据挖掘算法的设计与实现带来了新的挑战。基于MapReduce模型提出网格技术与基于密度的方法相结合的离群点挖掘算法，该算法分为两步：Map阶段采用网格技术删除大量不可能成为离群点的正常数据，将代表点信息发送给主节点;Reduce阶段采用基于密度的聚类方法，通过改进其核心对象选取，可以挖掘任意形状的离群点。实验结果表明，在数据密集型计算环境中，该方法能有效的对离群点进行挖掘。
　　引言：
　　随着数据海量增长、数据类型日益增多，如何快速处理数据密集型计算环境中数据是目前急需解决的问题。我们把以高效的方式获取、管理、分析和理解海量且高速变化的数据来满足目标需求的计算过程称为数据密集型计算[1]。数据可能以极高的速度生成，对数据的过滤、整合和存储等一系列操作必须能适应数据的生成速度。另外，数据密集型计算任务需要在合理的时间内分析和处理数据。但是，大多数情况下，数据以分布方式存储。因此，决定因素不再是计算能力，而是传输速度能否跟得上系统收集、处理和分析数据的速度[2]。Google基于大规模数据集的并行运算编程模型MapReduce将所有数据操作类型通过统一的编程模型连接起来，使海量、高速变化、异构和分布存储的数据能够在由普通计算机组成的集群中运行，在一定程度上实现了全局化的资源管理与调度。
　　数据密集型计算环境中数据的海量、快速变化、分布、异构等特点给离群点数据的挖掘带来了新的挑战。数据量的增长速度甚至超过了单个主存储器或硬盘容量增长的速度[3，4]， 地理位置的分布性和网络传输速度限制了大量数据在不同机器间的自由移动[5]。通过只传输中间处理结果等少量信息减小数据传输量以提高网络传输速度。采用分布式集群进行离群点挖掘成为了一种趋势。
　　相关工作：现有的方法大多是基于统计分布、深度、距离、聚类或网格等的离群点挖掘方法。文献[6]基于统计分布提出了100多种针对不同数据分布的离群点挖掘方法。为减少距离计算，引进空间索引结构KD-树、R-树和X-树等查找数据点的k邻近[7]。这些方法在低维空间中时间复杂度接近O（NlogN）。但是，随着维度的增加，方法失效。基于聚类的DBScan[8]算法检测出聚类的同时也检测出了离群点。缺点是数据量增大时，对内存容量要求高，I/0开销很大。张净等人提出的IGDLOF算法根据邻居网格[9]中数据分布情况判断该单元格是否为稀疏单元，依次进行数据筛选。基于网格的OMAGT[10]算法，降低了挖掘大数据集时对内存的要求，但是需计算局部可达密度。基于网格和密度思想的FOMAUC[11]算法能有效提高算法效率和挖掘准确度，但是该算法不适用于高维大数据集，其整个过程都是在内存中进行的，对内存要求比较高。目前，基于MapReduce模型的离群点挖掘算法研究相对较少。
　　MapReduce是由Google提出的主要用于海量数据处理的软件框架。它将数据看作一系列的