第２７卷第５期２０１３年９月
山东理工大学学报（自然科学版）
ＪｏｕｒｎａｌｏｆＳｈａｎｄｏｎｇＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ）Ｖｏｌ．２７Ｎｏ．５Ｓｅｐ．２０１３文章编号：１６７２－６１９７（２０１３）０５－００３２－０４
数据密集型计算环境下离群点挖掘算法设计与实现
陈亚丽，张龙波，李彩虹，张树森，刘希昱
（山东理工大学计算机科学与技术学院，山东淄博２５５０９１）
摘 要：在数据密集型计算环境中，数据具有海量、高速变化、分布存储和异构等特征，对数据挖掘
算法的设计与实现提出了新的挑战．基于ＭａｐＲｅｄｕｃｅ模型，提出了一种网格技术与基于ＬＯＦ方法相结合的离群点挖掘算法ＭＲ＿ＬＯＦ．Ｍａｐ阶段采用网格进行数据约简，将代表点信息发送给主节点；Ｒｅｄｕｃｅ阶段使用基于密度的离群点挖掘算法，借助网格期望值Ｅ筛选出稠密区域．该算法只需计算稀疏区域对象的ＬＯＦ值，降低了算法的时间复杂度．实验结果表明，在数据密集型计算环境中，该方法能有效的对离群点进行挖掘．
关键词：数据挖掘；离群点；数据密集型；ＭａｐＲｅｄｕｃｅ；ＭＲ＿ＬＯＦ中图分类号：ＴＰ３９１文献标志码：Ａ
Ｄｅｓｉｇｎａｎｄａｐｐｌｉｃａｔｉｏｎｏｆｏｕｔｌｉｅｒｍｉｎｉｎｇａｌｇｏｒｉｔｈｍｉｎ
ｄａｔａ‐ｉｎｔｅｎｓｉｖｅｃｏｍｐｕｔｉｎｇｅｎｖｉｒｏｎｍｅｎｔｓ
（ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＳｈａｎｄｏｎｇＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｚｉｂｏ２５５０９１，Ｃｈｉｎａ）
ＣＨＥＮＹａ‐ｌｉ，ＺＨＡＮＧＬｏｎｇ‐ｂｏ，ＬＩＣａｉ‐ｈｏｎｇ，ＺＨＡＮＧＳｈｕ‐ｓｅｎ，ＬＩＵＸｉ‐ｙｕ
Ａｂｓｔｒａｃｔ：Ｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｄａｔａ，ｓｕｃｈａｓｈｕｇｅａｍｏｕｎｔｓ，ｈｉｇｈｄｉｍｅｎｓｉｏｎａｎｄｄｉｓｔｒｉｂｕｔｅｄｓｔｏｒａｇｅｅｔｃ，ｈａｖｅｂｒｏｕｇｈｔｎｅｗｃｈａｌｌｅｎｇｅｓｆｏｒｔｈｅｄｅｓｉｇｎｏｆｏｕｔｌｉｅｒｍｉｎｉｎｇａｌｇｏｒｉｔｈｍｉｎｄａｔａ‐ｉｎｔｅｎ‐ｓｉｖｅｃｏｍｐｕｔｉｎｇｅｎｖｉｒｏｎｍｅｎｔｓ．Ｉｎｔｈｉｓｐａｐｅｒ，ｏｕｔｌｉｅｒｓｍｉｎｉｎｇａｌｇｏｒｉｔｈｍＭＲ＿ＬＯＦｂａｓｅｄｏｎｄｅｎｓｉｔｙｃｏｍｂｉｎｅｄｗｉｔｈｇｒｉｄｗａｓｐｕｔｆｏｒｗａｒｄｏｎａｃｃｏｕｎｔｏｆＭａｐＲｅｄｕｃｅｍｏｄｅｌ．ＤｕｒｉｎｇＭａｐｐｈａｓｅ，ｇｒｉｄｗａｓｕｓｅｄｔｏｓｉｍｐｌｉｆｙｄａｔａ，ｔｈｅｎｒｅｐｒｅｓｅｎｔａｔｉｖｅｉｎｆｏｒｍａｔｉｏｎｗａｓｓｅｎｔｔｏｐｒｉｍａｒｙｎｏｄｅ．ＩｎＲｅｄｕｃｅｐｈａｓｅ，ｏｕｔｌｉｅｒｓｍｉｎｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｄｅｎｓｉｔｙｗａｓｅｍｐｌｏｙｅｄ，ｄｅｎｓｅａｒｅａｗａｓｓｅｌｅｃｔｅｄｂｙｔｈｅｇｒｉｄ’ｓＥ．ＴｈｉｓａｌｇｏｒｉｔｈｍｗａｓｕｓｅｄｔｏｏｎｌｙｃａｌｃｕｌａｔｅＬＯＦｏｆｄａｔａｉｎｓｐａｒｓｅａｒｅａｔｏｒｅｄｕｃｅｔｉｍｅ
ｃｏｍｐｌｅｘｉｔｙ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｉｓａｌｇｏｒｉｔｈｍｉｓｅｆｆｅｃｔｉｖｅｆｏｒｍｉｎｉｎｇｏｕｔｌｉｅｒｓｉｎｄａｔａ‐ｉｎｔｅｎｓｉｖｅｃｏｍｐｕｔｉｎｇｅｎｖｉｒｏｎｍｅｎｔｓ．
Ｋｅｙｗｏｒｄｓ：ｄａｔａｍｉｎｉｎｇ；ｏｕｔｌｉｅｒ；ｄａｔａ‐ｉｎｔｅｎｓｉｖｅ；ＭａｐＲｅｄｕｃｅ；ＭＲ＿ＬＯＦ 数据密集型计算作为大规模分布式计算的一种计算方式，在科学研究、商业智能、生物信息、环境监控等众多邻域有着广泛的应用．在数据密集型计算中，数据大多数情况下以分布方式存储，网络传输速度了大量数据在不同机器间的自由移动，传输速度能否跟得上系统收集、处理和分析数据的速度
［１］
成了算法是否可行的决定因素之一．由于离群点
收稿日期：２０１３
０６
０８
数据只占总体数据的很少一部分，因此在各分节点
进行数据预处理，将大量非离群数据删除，然后将少量的代表信息发送给主节点，在主节点进行全局离群点挖掘．
Ｇｏｏｇｌｅ基于大规模数据集的ＭａｐＲｅｄｕｃｅ并行运算模型，有利于大量数据输入和输出操作．Ｍａｐ对＜ｋｅｙ，ｖａｌｕｅ＞键值对进行处理，将产生的中间键
基金项目：山东省自然科学基金资助项目（ＺＲ２０１１ＦＬ０１３）；山东省高等学校科技计划项目（Ｊ１３ＬＮ２７）作者简介：陈亚丽，女，ｙｌｃｈｅｎ８７０３２９＠１６３．ｃｏｍ；通信作者：张龙波，男，ｚｈａｎｇｌｂ＠ｓｄｕｔ．ｅｄｕ．ｃｎ
第５期 陈亚丽，等：数据密集型计算环境下离群点挖掘算法设计与实现３３
值对＜ｋｅｙ，ｌｉｓｔ＜ｖａｌｕｅｓ＞＞传递给Ｒｅｄｕｃｅ．Ｒｅｄｕｃｅ将并行子任务的中间数据合并，并进行相应的处理，最后输出结果．该模型将所有数据操作类型用统一的编程模型连接起来，使数据能够在由普通计算机组成的集群中运行，在一定程度上实现了全局化的
［２］
资源管理与调度．
现有的基于离群度的离群点挖掘算法主要不同在于离群度的计算方法设置不同．ＬＯＦ［３］算法以局部离群点因子作为离群点关于其局部领域内密度的点因子值．根据离群点因子值的大小来判断数据对象是否为离群点．
ｌｒｄｋ（ｏ′）∑ｏ′∈Ｎｋ（Ｏ）ｌｒｄｋ（ｏ）ＬＯＦ＝（１）
‖Ｎｋ（ｏ）‖
‖Ｎｋ（ｏ）‖ｌｒｄｋ（ｏ）＝（２）
ｋ（ｏｒｅａｃｈｄｉｓｔ′ｏ）←∑ｒｅａｃｈｄｉｓｔｋ（ｏ←ｏ′）＝
ｍａｘ｛ｄｉｓｔｋ（ｏ），ｄｉｓｔ（ｏ，ｏ′）｝（３）ｏ′∈Ｎｋ（ｏ）
异常程度度量，对离群点挖掘有显著的作用．但是该方法需要对每个数据计算局部离群因子值，花费的代价很大，了其在数据密集型计算环境中的应
用．ＣＯＦ［４］
算法根据参数ｋ和数据对象的连接性确定邻域，与其邻域的平均连接距离比作为基于连接
的离群系数ＣＯＦ，但时间复杂度高于ＬＯＦ．ＳＬＯＦ［５］
算法通过计算邻域距离和空间局部离群系数，解决空间数据的自相关性和异质性约束性．该方法采用了Ｒ倡树的索引方法查找邻域，在高维大规模数据
中，算法的执行效率不高．ＧＤＬＯＦ［６］
算法通过证明稠密单元和稠密区域中的点不可能成为离群点，减小了ＯＤＲＫＮＮ数据ＬＯＦ值的计算量，提高了执行效率．［７］算法用每个数据点的反向Ｋ近邻数来衡量偏离程度．反向Ｋ近邻数越少，越有可能是一个离群点．大量数据点离群度的计算和邻域查询在某种程度上增加了算法的计算复杂度，降低了算法在高维大规模数据集中的可扩展性．
本文基于ＭａｐＲｅｄｕｃｅ模型，根据对象的局部离群点因子值（ＬＯＦ）与１的接近程度，只需计算部分可能会成为离群点数据的ＬＯＦ值，弥补了ＬＯＦ算法需要计算所有点的邻域和局部密度的不足．各分节点使用网格进行数据约简，将中间结果等少量信息发送给主节点，进而减少数据传输量，提高网络传输速度．主节点使用网格期望值做参考值，筛选出位于高密度区的数据ＬＯＦ，只对分布在边缘的数据进行作为离群点值计算．
，最后统计出具有较高ＬＯＦ值的数据１ 算法分析与描述
１．１ ＬＯＦ算法
邻距离来确定邻域ＬＯＦ算法由给定参数的最少邻居数，通过对象ｋ‐距离、可达距离和ｋ和最近可达密度的计算，确定数据对象邻域的平均可达密度与数据对象自身的可达密度比为对象的局部离群
其中Ｎｋ（ｏ）为对象ｏ的ｋ‐距离范围内数据总数
公式（１）、（２）、（３）分别给出了ｏ的局部离群点因子、对象ｏ的局部可达密度和从ｏ’到ｏ的可达距离的计算方法．该算法能很好地解决局部离群点的挖掘问题，但是存在计算量大等缺点，不适用于对数据密集型计算环境中离群点数据的挖掘１．２ ＭＲ＿ＬＯＦ算法
．ＬＯＦ网络传输量大ＬＯＦ用ＭａｐＲｅｄｕｃｅ算法基础上提出一种算法在数据密集型计算环境下可用性、计算复杂度高等因素了模型在各分节点采用网格进行数据ＭＲ‐ＬＯＦ算法，该算法利．本文在筛选，将代表点信息发送给主节点，主节点进行全局离群点挖掘．其中ｋｅｙ为网格ＩＤ，ｖａｌｕｅ为网格五元组信息。主节点将网格期望值ｋ邻近中距离最远的点确定为检测对象，因数据的ＬＯＦ值在簇内约等于１，簇边缘略大于１，离簇越远值越大，根据其ＬＯＦ值与１的关系判断是否需要对ｋ邻近中其他点进行检测．该算法只需计算部分稀疏区域数据的ＬＯＦ值，很大程度上加快了离群点挖掘速度．
定义：Ｕ（Ｔ，Ｐ，Ｅ，Ｍａｘ，Ｍｉｎ）为网格单元五元组
Ｔ：网格类型；Ｐ：网格单元中数据点数，设为单元格密度；Ｅ：Ｕ中去掉最大值、最小值，剩余数据的期望值；
Ｍａｘ：数据中最大值；Ｍｉｎ：数据中最小值．
若Ｕ中Ｐ不小于某一给定阈值Ｎ，即｜Ｐ｜Ｎ，Ｕ为稠密单元Ｕｄｅｎｓｅ；若Ｕ中Ｐ小于某一给定阈值Ｎ，即｜Ｐ｜＜Ｎ，该Ｕ为稀疏单元Ｕｓｐａｒｓｅ；Ｐ为０的网格单元表示为Ｕｎｕｌｌ。若｜Ｌ‐Ｕ｜＝１，Ｌ为Ｕ的邻居网格单元．如果Ｕ的Ｌ均为空，则Ｕ为Ｕｏｕｔｌｒ．
输入：ｄ维数据集Ｄ、网格阈值Ｎ；输出：离群点的集合Ｏｕｔｌｉｅｒ；算法形式化描述如下：
３４山东理工大学学报（自然科学版）２０１３年
１）ＭａｐＲｅｄｕｃｅ框架对任务进行统一调度．２）Ｕ中各维空间划分，每一维的划分由相邻数据点间的分布情况决定．
３）根据预先设定的维度间隔距离值计算数据所属的网格单元．输入数据的同时，计算Ｕ的五元组信息．
４）若Ｕ为Ｕｄｅｎｓｅ，且其Ｌ均为Ｕｄｅｎｓｅ，保存Ｕ和Ｌ的五元组信息，Ｌ放入Ｃ（候选集合）中．对Ｃ中网格的Ｌ进行遍历查询，直到所有Ｌ均为空，将Ｕ及所有２ 实验结果与分析
采用三组实验来验证本文算法的有效性．实验１在数据量递增时，通过对三种算法离群点挖掘时间的比较来验证ＭＲ＿ＬＯＦ算法对海量数据的处理能力．实验２伴随数据处理节点的增加，分析了三种算法的离群点挖掘时间变化趋势．实验３中数据维度增加时，通过比较来验证ＭＲ＿ＬＯＦ算法对高维数Ｌ中数据全部删除；Ｌ均为Ｕｎｕｌｌ，标记Ｕ和Ｕｎｕｌｌ并删除Ｕ中数据．若Ｕ为Ｕｓｐａｒｓｅ，其Ｌ均为空，则Ｕ为Ｕｏｕｔｌｒ并删除Ｕ中数据，否则将其保留．位于数据分区边界的单元格不为空时，全部保留．
５）将代表点和拟离群点信息发送给主节点．６）主节点将不同分节点发送的代表点划分到相应的Ｕ中，实时更新Ｕ的五元组信息，直到所有数据全部录入网格．
７）重复４）中步骤，得候选离群数据集及离群点．
８）主节点进行全局离群点挖掘，流程图如图１所示．
图１主节点算法流程图
９）将４）、７）、８）步骤中检测出的离群点信息汇总输出．
主节点执行任务的总体分配和调度，分节点通过步骤２）、３）、４）、５）进行数据约简，并将代表信息发送给主节点为全局离群点挖掘做准备．主节点执行步骤６）、７）、８）、９）对分节点发送的数据做全局离群点挖掘．改进的算法能快速的检测到稠密区域，通过只计算稀疏区域数据的ＬＯＦ值，加快了对离群点的挖掘．
据的处理是否具有良好的可扩展性．
实验平台配置如下：１０台相同配置的ＰＣ机（通过局域网连接），ＣＰＵＰｅｎｔｉｕｍＤｕａｌ‐ＣｏｒｅＥ６５００，内存２Ｇ，ＹＬＭＦＯＳ（Ｕｂｕｎｔｕ）操作系统，Ｈａｄｏｏｐ０．２０，１个主节点ｍａｓｔｅｒ，９个分节点ｓｌａｖｅｓ，用装有测试数据来自Ｈａｄｏｏｐ插件的ＫＤＤｅｃｌｉｐｓｅＣｕｐ进行代码编辑１９９９，共有４１，个属性编译ｊｄｋ，３４１．７个．为连续属性，７个为离散属性．包括五大类数据，正常连接、ｄｏｓ、ｕ２ｒ、ｒ２ｌ、ｐｒｏｂｅ入侵和攻击．
实验１ 实验节点数和数据维度分别为１０台和ＧＤＬＯＦ４０维，同一数据集数据递增时，进行ＬＯＦ算法、对比．图算法和２为离群点挖掘时间随数据量递增的变化ＭＲ＿ＬＯＦ算法离群点挖掘运行时间情况．
图２ 检测时间随数据量递增变化情况
由图可知，随着数据量的增加算法的运行时间均增大，但ＭＲ＿ＬＯＦ算法的曲线增长速度相对其他算法较缓慢。当数据量急剧增大时，一定程度上能够降低算法执行的时间复杂度，性能优于ＬＯＦ算法和基于网格的ＧＤＬＯＦ算法．
ＬＯＦ实验２ 数据量相同情况下的变化情况如图算法、ＧＤＬＯＦ３所示算法离群点挖掘时间随节点数，ＭＲ＿ＬＯＦ算法、．
当数据量和数据维度数不变时，节点数越多，离群点挖掘花费的时间越少．考虑实际应用中数据处
第５期 陈亚丽，等：数据密集型计算环境下离群点挖掘算法设计与实现３５
３ 结束语
针对数据密集型计算环境下离群点挖掘问题，
本文提出网格与基于密度的算法相结合的ＭＲ＿ＬＯＦ算法，将单元期望值ｋ邻近中距离最远的点作为检测对象，根据其ＬＯＦ值与１的相差程度判图３ 检测时间与节点数目间关系
理终端数目远大于实验中节点数，该算法适用于数
据密集型计算环境下的离群点挖掘．
实验３ 数据量一定时，ＭＲ＿ＬＯＦ算法、基于
单元格的ＦＯＲＭＡＵＣ算法［８］
和ＧＤＬＯＦ算法离群点挖掘时间随数据维度的变化情况如图４所示．
图４ 随数据维度增加检测时间变化曲线
所有算法的检测时间随着数据维度的增加均呈
现增长趋势．ＭＲ＿ＬＯＦ算法类似于模糊查询的方法在高维数据中具有明显的优势，同等条件下检测时间增长与其他算法相比较缓慢．因此，ＭＲ＿ＬＯＦ算法用于挖掘高维数据中的离群点是可行的．
断数据稀疏区域．该算法不用计算所有数据的ＬＯＦ值，只需计算稀疏区域中数据的ＬＯＦ值．通过筛选稠密区域数据，加快了离群点检测速度，提高了算法的执行效率．实验结果分析可知，ＭＲ＿ＬＯＦ算法能有效地解决海量、分布、高速变化的数据密集型环境中离群点挖掘问题．参考文献：
［１］ＫｏｕｚｅｓＲＴ，ＡｎｄｅｒｓｏｎＧＡ，ＥｌｂｅｒｔＳＴ，ｅｔａｌ．ＴｈｅＣｈａｎｇｉｎｇ
Ｐａｒａｄｉｇｍ（１）：２６‐３４ｏｆ．
Ｄａｔａ‐ＩｎｔｅｎｓｉｖｅＣｏｍｐｕｔｉｎｇ［Ｊ］．Ｃｏｍｐｕｔｅｒ，２００９，４２［２］ＤｅａｎＪ，ＧｈｅｍａｗａｔＳ．ＭａｐＲｅｄｕｃｅ：ａｆｌｅｘｉｂｌｅｄａｔａｐｒｏｃｅｓｓｉｎｇ［３］Ｂｒｅｕｎｉｇｔｏｏｌ［Ｊ］Ｍ．ＣｏｍｍｕｎｉｃａｔｉｏｎｓＭ，ＫｒｉｅｇｅｌＨＰｏｆ，ＲａｙｍｏｎｄｔｈｅＡＣＭＴ，２０１０Ｎ，ｅｔ，５３（１）ａｌ．ＬＯＦ：７２‐７７：ｉｄｅｎｔｉｆ．
‐
ｙ２０００ｉｎｇｄｅｎｓｉｔｙ，２９（２）－：９３‐１０４ｂａｓｅｄｌｏｃａｌ．
ｏｕｔｌｉｅｒｓ［Ｊ］．ＡＣＭＳＩＧＭＯＤＲｅｃｏｒｄ，［４］ＴａｎｇＪ，ＣｈｅｎＺ，ＦｕＡ，ｅｔａｌ．ＥｎｈａｎｃｉｎｇＥｆｆｅｃｔｉｖｅｎｅｓｓｏｆＯｕｔｌｉｅｒ
ｐＤｅｔｅｃｔｉｏｎｓｕｔｅｒＳｃｉｅｎｃｅｆｏｒ，２００２ＬｏｗＤｅｎｓｉｔｙ，
２３３６：５３５‐５４８Ｐａｔｔｅｒｎｓ．［Ｊ］．ＬｅｃｔｕｒｅＮｏｔｅｓｉｎＣｏｍ‐［５］薛安荣，鞠时光，何伟华，等．局部离群点挖掘算法研究［Ｊ］．计算
机学报，２００７，３０（８）：１４５５‐１４６３．
［６］张净，孙志挥．ＧＤＬＯＦ：基于网格和稠密单元的快速局部离群点
探测算法［Ｊ］．东南大学学报：自然科学版，２００５，３５（６）：８６３‐８６６．
［７］岳峰，邱保志．基于反向Ｋ近邻的孤立点检测算法［Ｊ］．计算机工
程与应用，２００７，４３（７）：１８２‐１８４．
［８］崔贯勋，李梁，王勇，等．快速的基于单元格的离群数据挖掘算法
［Ｊ］．计算机应用，２００９，２９（１２）：３０００‐３３０２．
（编辑：刘宝江）
数据密集型计算环境下离群点挖掘算法设计与实现
作者：作者单位：刊名：
陈亚丽， 张龙波， 李彩虹， 张树森， 刘希昱， CHEN Ya-li， ZHANG Long-bo， LICai-hong， ZHANG Shu-sen， LIU Xi-yu
山东理工大学计算机科学与技术学院,山东淄博,255091山东理工大学学报（自然科学版）
Journal of Shandong University of Technology (Natural Science Edition)
2013(5)
英文刊名：
年，卷(期)：
本文链接：http://d.g.wanfangdata.com.cn/Periodical_sdgcxyxb201305008.aspx
