·226· 智能系统学报 第14卷 <k Map <k2,22 <k(v.>Reduce <kV Split 1 Map task Shuffle Reduce task Split 2 Map task Shuffle Reduce task Input Output Split n Map task Shuffle Reduce task Split n+1 Map task 图1 MapReduce framework处理过程 Fig.1 MapReduce framework process 元数据信息（名称，副本位置.） 域N:(p)即与点p的之间距离小于k-distance(p) HDFS Name node [Secondary client 的对象的集合。 (master) name node 3)可达距离(reachability distance)给定参数k 时，数据点p到数据点o的可达距离reach-dis(p,o) 为数据点o的k-distance(o)和数据点p与点o之 Data node ode 间距离的最大值，即 ■■ reach-dis(p,o)=max(k-distance(o),d(p,o) 图2HDFS结构 4)局部可达密度(local reachability density):数 Fig.2 HDFS structure 据点p的局部可达密度为它与k距离邻域内数据 NameNode为主节点且只有一个，负责接收用 点的平均可达距离的倒数，即 户的操作请求，记录每个文件数据块在各个Data- IW.(p川 rd(p)eah-dis (p) (1) Node上的位置和副本信息。Secondary Name- Node为可选节点，与NameNode进行通信，定期 5)局部异常因子(local outlier factor):数据p 保存HDFS元数据快照。DataNode为从节点且可 的局部相对密度（局部异常因子）为点p的邻域 以有多个，主要负责存储数据。同时为了保证数 内点的局部可达密度和数据点p的局部可达密度 据安全，文件会有多个副本（默认为3个）。Data 的比值的平均值，即 Node定期向NameNode上报心跳，NameNode通 Ird(o) 过心跳响应来控制DataNode. ∑Ird(p) LOF(P)=INA(P) (2) 2算法设计 根据局部异常因子的定义，如果数据点p的 LOF值在1附近，表明数据点p的局部密度跟它 2.1LOF算法 的邻居们差不多；如果数据p的LOF值小于1， LOF是基于密度的经典算法，其核心部分是 表明数据点p处在一个相对密集的区域，不是一 关于数据点密度的刻画。由数据点的k-邻近距 个异常点；如果数据点p的LOF得分远大于1， 离，计算各个数据点的局部可达密度和局部异常 表明数据点p跟其他点比较疏远，很可能是一个 因子，根据局部异常因子大小判断数据点的异常 异常点。 程度从而得到异常点。算法的基本概念如下： 2.2MR-DLOF算法 1)k-邻近距离(k-distance:对于任意正整数 LOF算法是基于密度的异常检测算法，计算 k,点p的k邻近距离定义为k-distance(p)=d(p,o), 量大，且在LOF算法中关于局部可达密度的定义 如果满足以下条件： 存在假设：不存在大于或等于k个重复点。当这 ①在样本空间中，至少存在k个点q,使得 样的重复点存在的时候，这些点的平均可达距离 dp,q)≤dp,o)。 为零，局部可达密度就变得无穷，从而影响了算 ②在样本空间中，至多存在k-1个点9，使 法的有效性。 得dp,q)<d(p,o)。 算法1MR-DLOF algorith 其中，d(p,o)为点p与点o之间的距离。 输入X=x1,x2,…,xw:data set 2)k-距离邻域(k-neighbor)):点p的k-距离邻 k:number of nearest neighbor,QSXW 0DSWDVN 0DSWDVN 0DSWDVN 0DSWDVN 6KXIIOH 6KXIIOH 6KXIIOH 5HGXFHWDVN 5HGXFHWDVN 5HGXFHWDVN 2XWSXW 6SOLW 6SOLW 6SOLWQ 6SOLWQ NY! NY! N^Y«`! 5HGXFH N 0DS Y! « « ప 1 MapReduce framework ะ⤲䓳⼷ Fig. 1 MapReduce framework process ٯ᪜ᢚԍᖛह⼜喏ޛ᱘ѹ㒚« +')6 FOLHQW 'DWDQRGH 'DWDQRGH 'DWDQRGH 'DWDQRGH « 1DPHQRGH PDVWHU 6HFRQGDU\ QDPHQRGH ప 2 HDFS ㏿Ჰ Fig. 2 HDFS structure NameNode ˝˞ᓫཁ˄Եథʶ˓Ὃ᠆᠉ଋஅၸ ਖ਼ᄉୱͺឯයὋ᝭ेඇ˓஠͇ஜ૵ڙڰՉ˓ Data￾Node ʼᄉͮᎵ֖ҝఴζোnjSecondary Name￾Node ˝ԺᤤᓫཁὋˀ NameNode ᤈᛠ᤯ζὋ߿య γߚ HDFS Њஜ૵ঋཱnjDataNode ˝̯ᓫཁ˄Ժ ̾థܲ˓Ὃ˞᜵᠆᠉ߚϱஜ૵njՎௐ˝˿γ᝼ஜ ૵߶КὋ஠͇͗థܲ˓ҝఴ (᳭ᝢ˝ 3 ˓)njData￾Node ߿యՓ NameNode ʼઐॶ᡹ὋNameNode ᤯ ᣾ॶ᡹ֽः౎ଌ҃ DataNodenj 2 ኪก᝹᝟ 2.1 LOF ッ∁ LOF ௦۲̅ࠚऎᄉፂЦኪกὋФನॶᦉѫ௦ С̅ஜ૵ཁࠚऎᄉ҈ႆnjၿஜ૵ཁᄉ k-᥵ᤂᡯ ሎὋ᝟ኪՉ˓ஜ૵ཁᄉࡌᦉԺ᣹ࠚऎ֖ࡌᦉऩ࣡ ࣡ཁᄉऩ૵ѻறஜ࠴ܷߔځ࣡ᦉऩࡌ૵಩Ὃߔځ ርऎ̯Ꮺ३ҁऩ࣡ཁnjኪกᄉ۲ఴഏএݟʽὙ k p k−distance(p) = d(p,o) 1) k-᥵ᤂᡯሎ (k-distance): ͉ࠪ̅਒ൣஞஜ Ὃཁ ᄉ k-᥵ᤂᡯሎ߿ ˝˦Ὃ ݟ౦໗ᡛ̾ʽ్͇Ὑ k q d(p,q) d(p,o) Ŀ ڙಧఴቆᫍ˖Ὃᒯڙߚ࠵˓ ཁ Ὃ΍३ nj k−1 q d(p,q) < d(p,o) ŀ ڙಧఴቆᫍ˖Ὃᒯܲڙߚ˓ ཁ Ὃ΍ ३ nj Ф˖Ὃd(p,o) ˝ཁ p ˀཁ o ˧ᫍᄉᡯሎnj 2) k-ᡯሎ᥵۪ (k-neighbor): ཁ p ᄉ k-ᡯሎ᥵ ۪ Nk(p) Ԁˀཁ p ᄉ˧ᫍᡯሎ࠴ ̅k−distance(p) ᄉࠪ៵ᄉᬶՋnj k p o reach−dis(p,o) o k−distance(o) p o 3) Ժ᣹ᡯሎ (reachability distance): ፋ߿ԟஜ ௐὋஜ૵ཁ ҁஜ૵ཁ ᄉԺ᣹ᡯሎ ˝ஜ૵ཁ ᄉ ֖ஜ૵ཁ ˀཁ ˧ ᫍᡯሎᄉణܷϘὋԀ reach−disk(p,o) = max{k−distance(o),d(p,o)} p 4) ࡌᦉԺ᣹ࠚऎ (local reachability density): ஜ ૵ཁ ᄉࡌᦉԺ᣹ࠚऎ˝߱ˀ k-ᡯሎ᥵۪Юஜ૵ ཁᄉڨࣰԺ᣹ᡯሎᄉχஜὋԀ lrdk(p) = |Nk(p)| o∈Nk (p) reach−disk(p,o)  p p p 5) ࡌᦉऩߔځ࣡) local outlier factor): ஜ૵ ᄉࡌᦉᄰࠪࠚऎ (ࡌᦉऩߔځ࣡˝ (ཁ ᄉ᥵۪ ЮཁᄉࡌᦉԺ᣹ࠚऎ֖ஜ૵ཁ ᄉࡌᦉԺ᣹ࠚऎ ᄉඊϘᄉڨࣰϘὋԀ LOFk(p) = o∈Nk (p) lrd(o) lrd(p) |Nk(P)|  p p p p p p ಩૵ࡌᦉऩߔځ࣡ᄉ߿˦Ὃݟ౦ஜ૵ཁ ᄉ LOF Ϙڙ 1 ᬃᤂὋᛪ௙ஜ૵ཁ ᄉࡌᦉࠚऎᡱ߱ ᄉ᥵ࡏ͂ࢿʿܲ὚ݟ౦ஜ૵ ᄉ LOF Ϙ࠴ ̅1Ὃ ᛪ௙ஜ૵ཁ ڙܪʶ˓ᄰࠪࠚᬶᄉӜ۪Ὃʿ௦ʶ ˓ऩ࣡ཁ὚ݟ౦ஜ૵ཁ ᄉ LOF ३ѫᤉܷ̅ 1Ὃ ᛪ௙ஜ૵ཁ ᡱФ̴ཁඊᣖ႟ᤉὋॡԺᑞ௦ʶ˓ ऩ࣡ཁnj 2.2 MR-DLOF ッ∁ k LOF ኪก௦۲̅ࠚऎᄉऩ࣡฽೜ኪกὋ᝟ኪ ᧙ܷὋ˄ڙ LOF ኪก˖С̅ࡌᦉԺ᣹ࠚऎᄉ߿˦ ڙߚϛ᝹Ὑʿڙߚ੊ܷ̅ኍ̅ ˓᧗ܬཁnjॆᤇ ಧᄉ᧗ܬཁڙߚᄉௐϊὋᤇ̎ཁᄉڨࣰԺ᣹ᡯሎ ˝ᭅὋࡌᦉԺ᣹ࠚऎࡂԪ३௃ቃὋ̯Ꮺॕֽ˿ኪ กᄉథ஌বnj 算法 1 MR-DLOF algorith 输入 X = x1, x2,··· , xN: data set k: number of nearest neighbor g226g ఄNJᑞNJጆNJፑNJߥNJઐ ኃ 14 ԃ