第2期 齐小刚，等：基于MapReduce的并行异常检测算法 ·225· 的、不完全的、有噪声的、模糊的及随机的数据集 据集中存在大于或等于k个重复点而导致数据点 中提取隐含在其中的、事先不知道的但又潜在的 局部密度为无穷大的情况，重新定义了-邻近距 有用的信息和知识的过程。异常检测是数据挖 离。同时为了减少计算量，将整个数据集逻辑地 掘中的重要任务之一，目的是从给定的数据集中 划分为多个数据块，利用MapReduce原理并行处 发现异常的数据对象。异常检测又称为离群点 理各个数据块中的数据，使得每个数据点的k邻 检测、偏差检测、孤立点检测等，用于反作弊、故 近距离和LOF值的计算仅在单个块中执行；然 障诊断、金融诈骗等领域。随着移动通信、云计 后，将每个数据块中LOF值较高的数据点合并后 算等技术的快速发展，数据量的日渐增多)，传统 进一步计算，得到最终异常数据点，从而提高算 基于单机内存设计的异常检测算法面临着很大的 法的准确性和灵敏性。 挑战。因此研究适用于大规模数据的异常检测算 法具有重要的应用价值。 1 Hadoop技术 近年来，已经出现许多异常检测算法，主要包 Hadoop是Apache软件基金会开发的分布式 括两类：有监督性的6和无监督性的-11。有监 系统基础架构。其理论基础是Google在国际上 督性的异常检测算法在监测异常数据前需要大量 发表的关于MapReduce、GFSl和BigTablet的 的样本进行模型检测，但实际应用中往往无法事 三篇论文。Hadoop由HDFS、MapReduce、HBase、 先获取大量的训练样本。因此无监督的异常检测 Hive和Zookeeper等成员组成，其中HDFS和Map 算法具有更高的实用价值。 Reduce是两个最重要的成员。HDFS可以实现不 在无监督异常检测算法中，Breunig等o提出 同节点、不同类型计算机的数据整合，MapRe- 的Local Outlier Factor(LOF)算法，通过计算每个 duce通过Map函数和Reduce函数建模来实现可 点的局部异常因子(LOF值)从而判断一个数据 靠的分布式计算。实践证明，大量基于MapRe- 对象的异常程度。该算法与其他算法相比，理论 简单、适应性较高，并且能有效地检测全局异常 duce的并行算法的实现有效地提高了算法的计算 和局部异常。然而LOF算法是基于局部密度设 能力-20」 计的，算法复杂度较高且假设不存在大于或等于 1.1 Hadoop MapReduce k个重复点。在这个算法的基础上，Bhat等提 Hadoop MapReduce的实现采用了Master/ 出了一种改进的LOF算法，将k-distance修改为 Slave结构。MapReduce分布式计算框架主要包 m-distance以提高算法性能。其中，k-distance是数 含两个处理过程：Map阶段和Reduce阶段。Map 据点与其最近的第k个数据点之间的距离，而m 阶段的Map函数和Reduce阶段的Reduce函数都 distance是数据点与其k邻域内点距离的平均 由用户根据需求进行自定义。Map函数主要处理 值。Miao等提出了一种基于核密度的局部离 输入数据集并产生中间输出，然后通过某种方式 群因子算法(KLOF)来计算每个数据点离群程度。 将这些中间输出通过Reduce函数组合在一起导 Tang等I引入了相对密度的离群值用来度量数 出最终结果。此过程均以键值对(key/value)形式 据对象的局部异常，其中数据对象的密度分布是 成对地输入和输出数据，保证了数据的安全性和 根据数据对象的最近邻来估计的。此外，进一步 可靠性。当Reducer函数输出最后一个键值对 考虑了反向最近邻和共享最近邻估计对象的密度 时，MapReduce任务完成。图I为MapReduce详 分布。虽然以上算法一定程度上提高了LOF算 细流程。HDFS首先根据数据大小和块大小对数 法的有效性，但其处理数据规模受限于内存容量 据进行物理分割，用户可根据需求对数据进行逻 和数据的复杂性。因此，设计一种既能保证LOF 辑分割，经过Map阶段，对每一块数据执行Map 算法优点又能高效和有效地处理大量数据的异常 任务后，对数据进行排序后进人Reduce阶段合并 检测算法是件有意义的工作。 结果，最后将结果写入HDFS中。 本文主要针对算法的计算量和算法中重复点 1.2 Hadoop HDFS 对局部异常因子的影响这两个方面对LOF异常 Hadoop Distributed File System(HDFS)采用 检测算法进行了深人分析，并根据Hadoop作业调 Master/Slave结构，其作为一个高度容错且易扩展 度机制和MapReduce计算框架，设计了一种基于 的分布式文件系统，主要包含NameNode、Second: MapReduce和LOF思想的并行异常检测算法 ary NameNode和DataNode三类节点。图2详 (MR-DLOF)。在MR-DLOF算法中，为了避免数 细地描述了HDFS结构。ᄉNjʿ߸КᄉNjథ٩ܥᄉNjഴዹᄉԢᬣ఺ᄉஜ૵ᬶ ˖ଡԨᬤդڙФ˖ᄉNĵЎʿᅻ᥊ᄉͭԠ໷ڙᄉ థၸᄉζো֖ᅻខᄉ᣾ር[1] njऩ࣡฽೜௦ஜ૵્ ଇ˖ᄉ᧗᜵͉ҫ˧ʶὋᄫᄉ௦̯ፋ߿ᄉஜ૵ᬶ˖ Ԧဗऩ࣡ᄉஜ૵ࠪ៵[2] njऩ࣡฽೜Ԡሥ˝ሎᏅཁ ೜฽Njϟࢿ฽೜Njߣበཁ೜฽ኍὋၸ̅ԥͺभNj஋ ᬩងறNj᧚ᚷគᰔኍᮖ۪njᬣᅋሧҮ᤯ζNj̇᝟ ኪኍ੾శᄉঋᤳԦࡘὋஜ૵᧙ᄉ௅ຑܘ]ܲ3] Ὃ͛ፑ ۲̅Ӭ఺Юߚ᝟᝹ᄉऩ࣡฽೜ኪก᭦˙ᅋॡܷᄉ ૌੌnjځ൤ᆐቂ᤟ၸܷ̅᜺ഴஜ૵ᄉऩ࣡฽೜ኪ กХథ᧗᜵ᄉःၸ͈Ϙnj ᤂࣱ౎ὋࣂፂѢဗ᝴ܲऩ࣡฽೜ኪกὋ˞᜵Ӊ હˏዜ[4] Ὑథᄢᅕবᄉ[5-6] ֖௃ᄢᅕবᄉ[7-13] njథᄢ ᅕবᄉऩ࣡฽೜ኪกڙᄢ฽ऩ࣡ஜ૵ґᭉ᜵ܷ᧙ ᄉಧఴᤈᛠഴۋ฽೜Ὃͭࠃᬄःၸ˖ज़ज़௃ก̂ ЎᖌԨܷ᧙ᄉᝪጶಧఴnjځ௃൤ᄢᅕᄉऩ࣡฽೜ ኪกХథఝᰳᄉࠃၸ͈Ϙnj k k k ڙ௃ᄢᅕऩ࣡฽೜ኪก˖ὋBreunig ኍ[10] ଡѢ ᄉ Local Outlier Factor(LOF) ኪกὋ᤯᣾᝟ኪඇ˓ ཁᄉࡌᦉऩߔځ࣡) LOF Ϙ) ̯Ꮺѻறʶ˓ஜ૵ ࠪ៵ᄉऩ࣡ርऎnjឞኪกˀФ̴ኪกᄰඊὋူ᝶ ኤӬNj᤟ःবᣖᰳὋࣲ˄ᑞథ஌ڠ฽೜Кࡌऩ࣡ ֖ࡌᦉऩ࣡njཨᏪ LOF ኪก௦۲̅ࡌᦉࠚऎ᝹ ᝟ᄉὋኪกܬఽऎᣖᰳ˄ϛ᝹ʿڙߚ੊ܷ̅ኍ̅ ˓᧗ܬཁnjڙᤇ˓ኪกᄉ۲ᆨʼὋBhatt ኍ[11] ଡ Ѣ˿ʶሗஇᤈᄉ LOF ኪกὋ࠱ k-distance νஇ˝ m-distance ̾ଡᰳኪกবᑞnjФ˖Ὃk-distance ௦ஜ ૵ཁˀФణᤂᄉኃ ˓ஜ૵ཁ˧ᫍᄉᡯሎὋᏪ m￾distance ௦ஜ૵ཁˀФ ᥵۪Юཁᡯሎᄉڨࣰ ϘnjMiao ኍ[12] ଡѢ˿ʶሗ۲̅ನࠚऎᄉࡌᦉሎ Ꮕߔځኪก (KLOF) ౎᝟ኪඇ˓ஜ૵ཁሎᏅርऎnj Tang ኍ[13] लЙ˿ᄰࠪࠚऎᄉሎᏅϘၸ౎ऎ᧙ஜ ૵ࠪ៵ᄉࡌᦉऩ࣡ὋФ˖ஜ૵ࠪ៵ᄉࠚऎѫ࣊௦ ಩૵ஜ૵ࠪ៵ᄉణᤂ᥵౎ͤ᝟ᄉnj൤ܰὋᤈʶ൥ Ꮵᘼ˿ԥՓణᤂ᥵֖Р̙ణᤂ᥵ͤ᝟ࠪ៵ᄉࠚऎ ѫ࣊njᙉཨ̾ʼኪกʶ߿ርऎʼଡᰳ˿ LOF ኪ กᄉథ஌বὋͭФܪူஜ૵᜺ഴԩᬌ̅Юࠓߚ᧙ ֖ஜ૵ᄉܬఽবnjځ൤Ὃ᝹᝟ʶሗ௄ᑞγ᝼ LOF ኪก͕ཁԠᑞᰳ஌֖థ஌ܪڠܷူ᧙ஜ૵ᄉऩ࣡ ೜฽ኪก௦͇థ਒˦ᄉࢹͺnj ఴ஠˞᜵᧪ࠪኪกᄉ᝟ኪ᧙֖ኪก˖᧗ܬཁ ࠪࡌᦉऩߔځ࣡ᄉॕֽᤇˏ˓ழ᭦ࠪ LOF ऩ࣡ ೜฽ኪกᤈᛠ˿ຆЙѫౡὋࣲ ૵಩Hadoop ͺˉុ ऎ఺֖҃ MapReduce ᝟ኪಳ౵Ὃ᝹᝟˿ʶሗ۲̅ MapReduce ֖ LOF ধਆᄉࣲᛠऩ࣡฽೜ኪก (MR-DLOF)njڙ MR-DLOF ኪก˖Ὃ˝˿ᥗБஜ ૵ᬶ˖ڙߚ੊ܷ̅ኍ̅ k ˓᧗ܬཁᏪ࠭ᒰஜ૵ཁ ࡌᦉࠚऎ˝௃ቃܷᄉৰхὋ᧗ள߿ ˿˦k-᥵ᤂᡯ ሎnjՎௐ˝˿ђ࠵᝟ኪ᧙Ὃ࠱ஞ˓ஜ૵ᬶ᤾ᣣڠ Ѳѫ˝ܲ˓ஜ૵ڰὋѽၸ MapReduce ԓူࣲᛠܪ ူՉ˓ஜ૵ڰ˖ᄉஜ૵Ὃ΍३ඇ˓ஜ૵ཁᄉ k-᥵ ᤂᡯሎ֖ LOF Ϙᄉ᝟ኪ̨ڙӬ˓ڰ˖੯ᛠ὚ཨ ՐὋ࠱ඇ˓ஜ૵ڰ ˖LOF Ϙᣖᰳᄉஜ૵ཁՋࣲՐ ᤈʶ൥᝟ኪὋ३ҁణጻऩ࣡ஜ૵ཁὋ̯Ꮺଡᰳኪ กᄉэᆷব֖༦ஏবnj 1 Hadoop ੾శ Hadoop ௦ Apache ᣃ͇۲᧚͗धԦᄉѫ࣊य ጆፑ۲ᆨ౵ౝnjФူ᝶۲ᆨ௦ Google ڍڙᬄʼ ԦᛪᄉС̅ MapReduce[14] NjGFS[15] ֖ BigTable[16] ᄉ ʻኼ᝶஠njHadoop ၿ HDFSNjMapReduceNjHBaseNj Hive ֖ Zookeeper ኍ੆տጷ੆ὋФ˖ HDFS ֖ Map￾Reduce ௦ˏ˓ణ᧗᜵ᄉ੆տnjHDFS Ժ̾ࠃဗʿ ՎᓫཁNjʿՎዜۋ᝟ኪ఺ᄉஜ૵ஞՋὋMapRe￾duce ᤯᣾ Map ѥஜ֖ Reduce ѥஜतഴ౎ࠃဗԺ ᭤ᄉѫ࣊य᝟ኪnjࠃ௙᝼᡺Ὃܷ᧙۲̅ MapRe￾duce ᄉࣲᛠኪกᄉࠃဗథ஌ڠଡᰳ˿ኪกᄉ᝟ኪ ᑞҦ[17-20] nj 1.1 Hadoop MapReduce Hadoop MapReduce ᄉࠃဗ᧓ၸ˿ Master/ Slave ፆౝnjMapReduce ѫ࣊य᝟ኪಳ౵˞᜵Ӊ դˏ˓ܪ᣾ူርὙMap ᫼ൿ֖ Reduce ᫼ൿnjMap ᫼ൿᄉ Map ѥஜ֖ Reduce ᫼ൿᄉ Reduce ѥஜᦏ ၿၸਖ਼಩૵ᭉයᤈᛠᒬ߿˦njMap ѥஜ˞᜵ܪူ ᣤЙஜ૵ᬶࣲ̖ၶ˖ᫍᣤѢὋཨՐ᤯᣾౼ሗழय ࠱ᤇ̎˖ᫍᣤѢ᤯᣾ Reduce ѥஜጷՋڙʶᡐ࠭ Ѣణጻፆ౦nj൤᣾ርڨ̾᪃Ϙࠪ (key/value) ्य ੆ࠪڠᣤЙ֖ᣤѢஜ૵Ὃγ᝼˿ஜ૵ᄉ߶Кব֖ Ժ᭤বnjॆ Reducer ѥஜᣤѢణՐʶ˓᪃Ϙࠪ ௐὋMapReduce ͉ҫ߸੆njڎ 1 ˝ MapReduce ស ጹึርnjHDFS ᯪЎ಩૵ஜ૵ܷ࠴֖ڰܷ࠴ࠪஜ ૵ᤈᛠྫྷူѫҞὋၸਖ਼Ժ಩૵ᭉයࠪஜ૵ᤈᛠ᤾ ᣣѫҞὋፂ᣾ Map ᫼ൿὋࠪඇʶڰஜ૵੯ᛠ Map ͉ҫՐὋࠪஜ૵ᤈᛠଅࣿՐᤈЙ Reduce ᫼ൿՋࣲ ፆ౦ὋణՐ࠱ፆ౦зЙ HDFS ˖nj 1.2 Hadoop HDFS Hadoop Distributed File System (HDFS) ᧓ၸ Master/Slave ፆౝὋФͺ˝ʶ˓ᰳऎࠓᩱ˄௛ੰࡘ ᄉѫ࣊य஠͇ጆፑὋ˞᜵Ӊդ NameNodeNjSecond￾ary NameNode ֖ DataNode ʻዜᓫཁ[21] njڎ 2 ស ጹڠଠᤗ˿ HDFS ፆౝnj ኃ 2 య ᴎ࠴ѷὋኍὙ۲̅ MapReduce ᄉࣲᛠऩ࣡฽೜ኪก g225g