数据奔腾d925

软件学报ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,2015,26(5):10791095[doi:10.
13328/j.
cnki.
jos.
004659]http://www.
jos.
org.
cn中国科学院软件研究所版权所有.
Tel:+86-10-62562563基于MapReduce与相关子空间的局部离群数据挖掘算法张继福1,李永红1,秦啸2,荀亚玲11(太原科技大学计算机科学与技术学院,山西太原030024)2(DepartmentofComputerScienceandSoftwareEngineering,AuburnUniversity,Auburn,USA)通讯作者:张继福,E-mail:jifuzh@sina.
com,http://www.
tyust.
edu.
cn/摘要:针对高维海量数据,在MapReduce编程模型下,提出了一种基于相关子空间的局部离群数据挖掘算法.
该算法首先利用属性维上的局部稀疏程度,重新定义了相关子空间,从而能够有效地刻画各种局部数据集上的分布特征;其次,利用局部数据集的概率密度,给出了相关子空间中的局部离群因子计算公式,有效地体现了相关子空间中数据对象不服从局部数据集分布特征的程度,并选取离群程度最大的N个数据对象定义为局部离群数据;在此基础上,采用LSH分布式策略,提出了一种MapReduce编程模型下的局部离群数据挖掘算法;最后,采用人工数据集和恒星光谱数据集,实验验证了该算法的有效性、可扩展性和可伸缩性.
关键词:局部离群数据;相关子空间;MapReduce;局部稀疏度;概率密度中图法分类号:TP311中文引用格式:张继福,李永红,秦啸,荀亚玲.
基于MapReduce与相关子空间的局部离群数据挖掘算法.
软件学报,2015,26(5):10791095.
http://www.
jos.
org.
cn/1000-9825/4659.
htm英文引用格式:ZhangJF,LiYH,QinX,XunYL.
Related-Subspace-BasedlocaloutlierdetectionalgorithmusingMapReduce.
RuanJianXueBao/JournalofSoftware,2015,26(5):10791095(inChinese).
http://www.
jos.
org.
cn/1000-9825/4659.
htmRelated-Subspace-BasedLocalOutlierDetectionAlgorithmUsingMapReduceZHANGJi-Fu1,LIYong-Hong1,QINXiao2,XUNYa-Ling11(SchoolofComputerScienceandTechnology,TaiyuanUniversityofScienceandTechnology,Taiyuan030024,China)2(DepartmentofComputerScienceandSoftwareEngineering,AuburnUniversity,Auburn,USA)Abstract:Inthispaper,arelated-subspace-basedlocaloutlierdetectionalgorithmisproposedinMapReduceprogrammingmodelforhigh-dimensionalandmassivedataset.
Firstly,therelevantsubspace,whichcaneffectivelydescribethelocaldistributionofthevariousdatasets,isredefinedbyusinglocalsparsenessofattributedimensions.
Secondly,alocaloutlierfactorcalculationformulaintherelevantsubspaceisdefinedwithprobabilitydensityoflocaldatasets.
Theformulacannotonlyeffectivelyreflecttheoutliernessofdataobjectthatdoesnotobeythedistributionofthelocaldatasetinrelevantsubspace,butalsoselectNdataobjectswiththegreatest-outliernessaslocaloutliers.
Furthermore,arelated-subspace-basedlocaloutlierdetectionalgorithmisconstructedbyusingLSHdistributedstrategyinMapReduceprogrammingmodel.
Finally,experimentalresultsvalidatetheeffectiveness,scalabilityandextensibilityofthepresentedalgorithmsbyusingartificialdataandstellarspectraldataasexperimentaldatasets.
Keywords:localoutlier;relevantsubspace;MapReduce;localsparsity;probabilitydensity离群数据(outlier)就是明显偏离其他数据、不满足数据的一般模式或行为、与存在的其他数据不一致的数据[1],蕴含着大量的不易被人类发现却很有价值的信息.
离群挖掘作为数据挖掘的一个重要分支,已广泛的应用在天文光谱数据分析[2]、信用卡诈骗[3]、网络入侵挖掘[4,5]、数据清洗[6]等领域.
目前,离群数据挖掘大致分为基基金项目:国家自然科学基金(61272263)收稿时间:2013-12-19;修改时间:2014-02-17;定稿时间:2014-05-21;jos在线出版时间:2014-08-19CNKI网络优先出版:2014-08-1914:29,http://www.
cnki.
net/kcms/doi/10.
13328/j.
cnki.
jos.
004659.
html1080JournalofSoftware软件学报Vol.
26,No.
5,May2015于统计[7]、基于距离[8,9]、基于密度[10,11]、基于偏离[12]和基于角度的[3,13]等方法,然而,这些方法都假设各维对度量离群数据作用是相同的[14],无关维的存在会增加"维灾"对挖掘效果的影响,可能会无法挖掘一些隐藏在子空间中的离群数据.
在高维海量数据中,由于数据量大和维度高,严重地影响了离群数据挖掘效果和效率,可能无法发现隐藏在子空间中的一些离群数据.
在大多数情况下,离群数据是与局部数据集的分布特征明显不一致的数据对象.
但在有些属性维上,可以提供不一致的有价值信息,而在其他属性维上,则无法提供有价值的信息,对度量离群数据几乎是无关的[15].
因此,寻找和删除高维数据集中无法提供有价值信息的属性维,可以有效地降低"维灾"的干扰,并能有效地发现隐藏的离群数据.
本文针对高维海量数据,充分利用集群系统和MapReduce编程模型的强大数据处理能力,提出一种基于相关子空间的局部离群数据挖掘算法.
该算法首先从局部稀疏程度的角度,利用定义在局部数据集上的局部稀疏度因子,重新定义了相关子空间,从而有效地刻画各种局部数据集上的分布特征;其次,对相关子空间中的数据对象,利用局部数据集的概率密度和高斯误差函数给出了其局部离群因子的计算公式,从而有效地体现了相关子空间中数据对象与局部数据集分布特征不一致的程度;然后,选取离群程度最大的N个数据对象作为局部离群数据;在此基础上,采用分布Hash索引策略和近似K近邻方法,提出了一种MapReduce编程模型下的局部离群数据挖掘算法;最后,采用人工数据集和恒星光谱数据集,实验验证了该算法的有效性、可扩展性和可伸缩性.
1相关工作与分析由于传统的离群数据挖掘方法[713]大多数是在所有维构成的空间中挖掘离群数据,一些无关维的存在会对离群点的挖掘效率和精度带来影响.
将数据投影到子空间上进行离群挖掘[1517]是目前高维离群数据挖掘研究的热点之一,然而在寻找有意义的子空间时比较困难[16],具有维度指数级的复杂度[15].
针对数据挖掘任务,在高维数据中选择有意义子空间的典型方法主要有稀疏度子空间法[2,18,19]和相关子空间法[14,20,21]两大类.
稀疏度子空间法是根据用户设定稀疏系数阈值,将数据投影到稀疏子空间中,包含在该子空间中数据对象定义为离群数据,因此是一类基于全局的子空间方法.
典型工作有:Agarwal等人[18]采用遗传算法搜索稀疏子空间,但该算法受初始种群影响,离群挖掘结果的完备性和准确性等无法得到保证;张继福等人[2,19]针对文献[18]中存在的不足,采用概念格作为子空间描述工具,通过引入稠密度系数,在概念格内涵中确定稀疏子空间,进一步提高了挖掘结果的准确性和完备性,并已应用在天文光谱数据中,取得了较好效果,但由于概念格构造的复杂性,挖掘效率较低.
相关子空间法[14,15,17,20,21]是在数据集中寻找由有意义的属性维构成的相关子空间,从而在相关子空间中度量离群数据,主要采用的方法是基于局部参考数据集的线性相关性[14,20,21]以及基于局部参考数据集的统计模型[15,17]等.
典型工作有:Kriegel等人[20]提出了轴平行子空间离群挖掘(SOD)方法,该方法通过共享最近邻居(SNN)为每一个数据对象寻找一个相似子集,并在相似子集中确定轴平行线性相关子空间,在SOD中,仅仅在一个相关子空间中来刻画数据对象的离群程度,当数据对象分布在两个或两上以上的子空间中时,SOD将不能区分它们的离群程度[15],显然,在相关子空间中,采用欧式距离的维平均方法度量离群具有明显的不足;Muller等人[15]利用柯尔莫哥洛夫-斯米尔诺夫检验的统计方法,提出了在数据集上选择有意义的子空间方法,从低维到高维采用递归的方式逐步寻找非均匀分布的子空间,并将数据对象在各个相关子空间中的局部离群值累乘,作为该数据对象最终的离群程度,解决了不同子空间中的离群因数可比性问题,但在该算法中,确定所有相关子空间具有维度指数级的时间复杂性[3],因此其效率较低,对高维数据集的维度可扩展性差,无法适应于海量高维数据;Keller等人[17]利用蒙特卡洛方法寻找相关子空间集,该方法由数据对象对应在每个相关子空间中的局部数据子集确定该数据对象的离群程度,但该相关子空间实际上是从全局的角度考虑得到的;Kriegel等人[14]以主成分方法为理论依据,采用马氏距离结合伽玛分布的方法实现了离群数据挖掘,该方法得到的相关子空间是线性相关的任意子空间,相关子空间对线性分布的数据具有很好的适应性,但由于该方法是基于对局部数据分布趋势的偏离,当离群数据所在稀疏区域体现出一种不明显的相关性时,由最大似然估计得到的相关子空间容易出现张继福等:基于MapReduce与相关子空间的局部离群数据挖掘算法1081错误,因此需要足够的局部数据来体现明显的趋势,同时,该算法的时间复杂度是维度的三次方,难以适用于高维数据;此外,Bouguessa等人[21]利用稀疏度密度矩阵寻找相关子空间,并在该相关子空间中实现聚类分析.
针对离群挖掘任务,其并行与分布式算法尚不多见,一些相关的典型研究工作有:文献[22]将LSH(localitysensitivehashing)策略应用在MapReduce框架中,并有效地解决了在高维海量数据集中近似K近邻查询问题;文献[23,24]在MapReduce框架中提出了k-近邻连接算法,为大数据中的K-近邻查询处理提供了一种较为有效的方法,具有较好的实用价值;文献[25]在MPI编程模型下提出了一种基于距离的局部离群数据挖掘算法,但由于该算法是在所有属性维够成的空间中度量离群数据,很难适应于高维数据离群挖掘任务.
2基本概念2.
1相关子空间与局部离群概率针对不同的数据挖掘任务,数据集中的数据对象仅仅在特定属性维上能够体现出有价值的信息,而其他一些属性维可能很少甚至不会体现出有价值的信息[15].
设DS是任意一个d维数据集,属性集FS={A1,A2,…Ad},xij(i=1,2,…,n;j=1,2,…,d)表示第i个数据对象obji在第j个属性上的取值.
参照文献[15,26],相关子空间和局部离群概率的基本概念和定义描述如下:对于任意子空间SFS和数据对象o∈DS的最近邻N(o,S),如果S是相关子空间,则N(o,S)是不均匀分布的;如果S是不相关子空间,则N(o,S)是均匀分布的.
在文献[15]中,非均匀分布的子空间才能有效地体现出"离群数据"的有价值信息,均匀分布的属性维无法体现出"离群数据"的有价值信息.
因此,相关子空间有效地反映了"离群数据"的有价值信息,度量和寻找相关子空间成为离群数据挖掘的关键.
在文献[26]中,对于任意数据对象o∈DS,设SDS为关联数据集且o∈S,则o在S中的概率距离pdist(o,S)满足:s∈S:P[d(o,s)≤pdist(o,S)]≥.
直观地说,pdist(o,S)是在以o为球心和以pdist为半径的球中,包含在S中的数据对象个数的概率.
pdist(o,S)可以间接地用于估计S的密度,也就是说,S的密度可定义为1(,)(,)pdensoSpdistoS=(1)假设o处于S的中心,并且s∈S到o的距离集合近似服从半高斯分布,则类似于标准差,计算s到o的标准距离如下:2(,)(,)||sSdosoSSσ∈=∑(2)在公式(2)中,由于使用距离d(o,o)=0代替了平均值E[d(o,S)],o的标准距离与标准差Stddev(d(o,S))不同.
因此,不能假设s∈S到o的距离值集合是正态分布的,而可以假设S服从以o为中心的正态分布.
可以利用该假设确定关联数据集S,即,S=o与其K最近邻.
o到S的λ相关的概率数据集合距离定义如下:pdist(λ,o,S)=λσ(o,S)(3)其中,参数λ用于控制密度的近似值.
在公式(3)中,pdist(λ,o,S)用于估计关联集S的密度.
对于任意数据对象o∈DS,设SDS为o的关联数据集,则λ相关的概率局部离群因子(PLOF)定义如下:,()()1SsSopdistoSoPLOFoEpdistsSsλλλ∈=(4)其中,E表示均值,S(o)表示o的关联数据集.
采用高斯误差函数,表示数据对象o∈DS是离群数据的概率值(局部离群概率(LoOP))公式定义如下:1082JournalofSoftware软件学报Vol.
26,No.
5,May2015,()()max0,2SSPLOFoLoOPoerfnPLOFλ=(5)其中,nPLOF=λE[(PLOF)2].
2.
2LSH策略由于标准的KNN算法使用的是全局搜索方法,不适合应用于MapReduce框架.
文献[22]提出了一种LSH策略,并在MapReduce框架下处理大数据中的近似KNN问题,其关键思想是:使用一组哈希函数,使距离较近的两个数据对象以较高的概率分配到同一个哈希桶中;在查询每个数据对象obj的近似KNN时,通过obj对应的哈希值找到对应的哈希表中的对应哈希桶,并将哈希桶中的所有数据对象导入程序中,查询数据对象obj的近似KNN.
参照文献[22,27,28],哈希函数定义如下:,()aBvavBhW+=(6)其中,v为输入数据集中的任意一数据对象;a是d维随机向量,a中的每一维取值均是从p-Stable分布中独立地选择出来的;W∈R(实数集),B是从[0,W]中随机选出的一个实数.
每一个哈希函数将一个d维数据点映射到一个整数集.
如果有k个哈希函数,则最终是一个长度为k的向量函数g(v):11kkaBvaBvgvhh=(7)g(v)对应一个哈希表,为了获得近似KNN的较高的准确率,有必要建立多个哈希表,并且采用每个哈希表对应一个探针的策略.
3相关子空间、子空间定义向量与离群数据3.
1相关子空间由于真实数据集往往包含由多种不同机制产生的簇(cluster),不同机制可能作用于不同的属性维子集[14].
属性维子集体现了相应的机制可以生成对应的数据子集,并体现一种相似的局部分布特征,即,对于由特定机制生成的数据子集,属性维子集具有局部相关性(局部稀疏分布特征共性,即,有些属性维是非均匀分布的,有些是均匀分布的).
通常,由特定机制生成的数据子集达到一定的数量时,局部分布特征的共同特征才能变得明显.
离群数据可以认为不是由该种机制产生的数据对象,即,离群数据是与局部相关性明显不一致的数据对象.
对于任意数据对象obj,与局部稀疏分布特征共性不一致的属性维体现了一类有价值信息,并可由局部数据属性维取值不均匀分布来刻画;与局部稀疏分布特征共性一致的属性维则不能体现有价值信息,并可由局部数据属性维取值均匀分布来刻画.
参照文献[15],相关子空间重新定义如下:定义1.
针对离群数据挖掘,设DS是一个d维数据集,全空间FS=A(属性集A={A1,A2,…,Ad},数据对象obj的最近邻为N(obj,FS)(即,局部数据集LDS),如果N(obj,FS)在Ai属性维上的取值是均匀分布,则称Ai不能提供有价值的信息,属于不相关子空间中的属性维;反之,如果N(obj,FS)在Ai属性维上的取值是非均匀分布的,则称Ai可以提供有价值的信息,属于相关子空间中的属性维.
在文献[15]中,利用最近邻N(o,S)来确定每个子空间S是否为相关子空间,对于数据集DS,随着S的维度调整,包含S中的数据集的分布特征也会改变.
因此,当S不为FS时,N(o,S)会失去局部数据集的意义,不能有效地体现DS在FS中局部数据集的局部分布特征的共同特性.
而在定义1中,仅利用FS中的N(obj,FS),确定相关子空间,有效地避免了文献[15]中的上述不足.
3.
2子空间定义向量在局部数据集LDS中,均匀分布属性维的取值较均匀,稀疏程度(密度)相似,差异较小,因此可以采用局部数据属性维的稀疏差异程度来度量均匀分布属性.
因此,通过删除均匀分布的属性维,保留非均匀分布属性维,可张继福等:基于MapReduce与相关子空间的局部离群数据挖掘算法1083有效地确定数据对象的相关子空间.
设obj是数据集DS中第i个数据对象,LDS(obj)是由obj与其K-NN构成的局部数据集.
相对于LDS(obj),obj在各属性维上的局部稀疏程度(密度),可由如下局部稀疏因子λij来度量:2()()1ijijypxijyxKλ∈=+∑(8)其中,p(xij)是LDS(obj)在属性维Aj上的属性取值组成的取值序列,K是最近邻个数.
由公式(8)可知,局部稀疏因子λij是局部数据集LDS(obj)中属性维Aj上的各个取值到xij的欧式距离的平方均值.
类似于公式(2):λij越大,表明LDS(obj)在属性维Aj上越稀疏;反之,λij越小,表明LDS(obj)在属性维Aj上越稠密.
总之,λij可以体现局部数据集LDS在其属性维Aj上的局部稀疏程度(密度).
显然,由公式(8)可以确定所有数据对象的各属性维上的局部稀疏因子,并由此可生成数据集DS的稀疏因子矩阵[Zλ]n*d=[λij],其中,n=|DS|,d=DS的维度.
由[Zλ]n*d可构造出obj在LDS(obj)上的局部稀疏因子矩阵[ZLλ]k*d(obj),即,obj的局部稀疏因子矩阵[ZLλ]k*d(obj),其中,k=|LDS(obj)|.
为了刻画属性维的局部稀疏程度差异,可采用如下的局部稀疏差异因子dij,描述obj在LDS(obj)上第j个属性维的稀疏程度差异:()ijijijijCdCλλλ=(9)其中,ijCλ是[ZLλ]k*d(obj)在属性维Aj的对应维取值集的平均值的平方.
由公式(9)可知,dij刻画了局部稀疏因子λij相对于均值的差异程度.
dij越大,数据对象obj的局部稀疏因子矩阵[ZLλ]k*d(obj)在第j维上的局部稀疏因子差异越大,也就是说,obj的局部数据集LDS在属性维Aj上的取值的局部密度越不均匀,即,obj的局部数据集LDS在属性维Aj上的取值越不均匀;反之,dij越小,数据对象obj的局部稀疏因子矩阵[ZLλ]k*d(obj)在第j维上的局部稀疏因子差异越小,也就是说,obj的局部数据集LDS在属性维Aj上的局部密度越均匀,即,obj的局部数据集LDS在属性维Aj上的取值越均匀.
总之,采用dij可以度量obj的局部数据集LDS在属性维Aj上取值是否均匀的程度.
定义2.
设ε是局部稀疏差异因子阈值,dij是第i个数据对象obj第j维的局部稀疏差异因子,如果dij0时,PLOF值越大,表明obj的离群程度越高.
但采用PLOF度量方式,对于不同分布特征的数据集不具有可比性[26].
数据集DS存在各种维度的相关子空间,不同相关子空间中的数据分布特征也不同.
由此可见,不同相关子空间中的PLOF也不具可比性.
为了将PLOF值转化成一个概率值,文献[27]假设维之间相互独立,且各个维都对PLOF值产生影响.
根据中心极限定理,可假设在所有维组成的空间FS中的PLOF服从E[PLOF2](以0中心的方差)的正态分布[26].
根据定义2,小于ε时不能提供有价值的信息,即,在定义2确定的相关子空间中,其属性维才能对PLOF产生影响.
因此,可假设相关子空间中的PLOFo∈LDS(obj)(o)服从Eo∈LDS(obj)[(PLOFRS(o))2]的正态分布,并利用高斯误差函数来表示数据对象是离群数据的概率.
参照公式(5),obj在其相关子空间RS中的离群程度(离群因子)重新定义如下:2()()()max0,2RSoLDSobjobjRSPLOFobjFactorobjerfEPLOFo∈∪=(14)其中,erf同文献[26],表示高斯误差函数.
由于文献[26]中的参数λ不会影响到离群程度的排序,本质是将高斯误差函数的变量值除以λ,因此未考虑其值的选取,相当于文献[26]的λ取1.
由公式(12)~公式(14)可以看出:PLOFRS(loc_obj)并不是在loc_obj的相关子空间中确定,而是在obj的相关子空间RS中确定,因为确定Factor(obj)时,obj与局部的分布特征不一致的程度仅能在obj的相关子空间RS中体现.
在文献[26]中,假设各维对度量离群数据作用是相同的,且在所有维组成的空间中,计算数据对象的PLOF.
张继福等:基于MapReduce与相关子空间的局部离群数据挖掘算法1085但是,当将均匀分布的属性参与PLOF的计算且均匀分布的属性维较多时,有可能使公式(12)和公式(13)中的PLOF值趋近于0.
总之,均匀分布的属性维对于区分正常数据与离群数据不会提供有价值的信息,它的存在可能会将离群数据变成正常数据.
公式(14)是在相关子空间RS中确定数据对象离群程度,RS仅含有非均匀分布的属性维,有效地避免了均匀分布的属性维参与离群程度的计算过程.
同时,公式(14)可以适应不同的数据分布特征以及不同的子空间,即,可以作为相关子空间中确定离群数据的统一度量方式,有效地改善了文献[20]中度量方式在多个子空间中不具可比性的问题.
特别需要注意的是:文献[26]是从基于数据集角度归一化PLOF,假设整体数据集的PLOF服从正态分布;而公式(14)是从广义的角度,同时考虑数据集中不同聚集簇的归一化,仅假设局部数据集在相关子空间中的PLOF服从正态分布.
4离群数据挖掘的并行化由公式(14)可知,数据集DS中的任意数据对象obji(i=1,2,.
.
.
,n;n=|DS|)的离群因子Factor(obji)的计算步骤是:首先,由KNN方法确定obji的LDS(obji),并利用公式(8)计算obji对应的稀疏度因子λi,从而生成DS的稀疏因子矩阵[Zλ]n*d;其次,根据[Zλ]n*d,参照LDS(o)(LDS(obji)),生成对应的局部稀疏因子矩阵[ZLλ]k*d(o)(o∈LDS(obji)),并由公式(9)与定义2生成obji对应的子空间定义向量vi;最后,由公式(14)确定obji对应的离群因数Factor(obji).
因此在DS中,任意数据对象的离群因子计算过程如图1所示.
Fig.
1Calculatingoutlierfactor图1离群因子计算过程由于各个数据对象的离群程度是其对应的LDS(obji)在相关子空间下计算得到,由图1可以看出,在表A中,确定LDS(obji)时采用了KNN的操作,需要遍历DS中的所有数据对象;在表C中,确定[ZLλ]k*d(o)(o∈LDS(obji))时需要参照表A中的LDS(o)(o∈LDS(obji))以及表B中DS对应的稀疏因子矩阵[Zλ]n*d;其他计算步骤都不需要遍历与DS相关的全局数据结构,数据对象之间的计算过程相互独立,不需要进行通信,因此可以直接并行处理.
对于生成表A与表C,可采用文献[22]的LSH策略进行并行化处理,但是其主要思想不相同:在生成表A时,是文献[22]直接引用:首先,利用公式(7)将各个数据对象Hash散列到不同的哈希表的不同的哈希桶中;然后,在确定数据对象obji的近似KNN生成LDS(obji)时,将数据对象obji相关的哈希桶obj1.
.
.
obj1,LDS(obj1)objnobj1,LDS(objn)obj3obj1,LDS(obj3)obj2obj1,LDS(obj2).
.
.
.
.
.
.
.
.
表A表B表C表D.
.
.
obj1,Factor(obj1)obj2,Factor(obj2)obj3,Factor(obj3)objn,Factor(objn)Sort-By-FactorFactor(obj1),obj1Factor(obj2),obj2Factor(obj3),obj3Factor(objn),objn.
.
.
.
.
.
obj1,[ZLλ]k*d(o)(o∈LDS(obj1)obj2,[ZLλ]k*d(o)(o∈LDS(obj2)obj3,[ZLλ]k*d(o)(o∈LDS(obj3)objn,[ZLλ]k*d(o)(o∈LDS(objn)obj1,v1,[ZLλ]k*d(o)(o∈LDS(obj1)obj2,v2,[ZLλ]k*d(o)(o∈LDS(obj2)obj3,v3,[ZLλ]k*d(o)(o∈LDS(obj3)objn,vn,[ZLλ]k*d(o)(o∈LDS(objn)obj1,λ1obj2,λ2obj2,λ3objn,λn1086JournalofSoftware软件学报Vol.
26,No.
5,May2015导入程序中进行操作.
在生成表C时,对文献[22]的方法进行了调整:首先,利用公式(7)将各个数据对象Hash散列到不同的哈希表的不同的哈希桶中;然后,将数据对象obji相关的哈希桶导入程序中进行操作,不但确定数据对象obji的近似KNN生成LDS(obji),间接生成[ZLλ]k*d(obji),而且,还要同时在导入的数据集中确定LDS(o)(o∈LDS(obji)∩o≠obji),间接生成[ZLλ]k*d(o)(o∈LDS(obji)∩o≠obji).
由于对表A与表C的生成采用了文献[22]的LSH策略,不必将全部数据集放入内存进行查询,因此,整个离群因子计算计算过程可以并行化.
图1刻画和描述了离群因子的计算过程,当数据集DS较小时,表A与表B都较小,可以首先生成表A,并将其保存在内存中;然后由表A通过生成表B,并将其也保存在内存中.
由于表A与表B中都在内存,可采用索引技术,从表B中的对应项对应到表A的相应项来生成表C.
当数据集DS大到一定程度时,表A与表B都相当大.
在生成表C时,需将表A中的每一个数据对象和对应局部数据集LDS(obji)逐项输入,以及在表B中查找LDS(obji)对应的稀疏度因子,因此,表B必须被保留在各计算结点上的内存中.
当B表太大时,会耗尽各个计算结点的内存资源.
因此,为了生成表C,不再采用索引策略对应生成,而是从表B中查找LDS(obji)对应的局部稀疏因子,采用类似于表A中生成LDS(obji)的操作.
由图1可以看出:生成表A时,需要遍历DS中的全部数据对象;生成表C时,需要遍历表A中的全部数据对象.
因此,生成表A和表C是全局相关的,其他过程都与全局无关,各数据对象对应操作彼此之间不存在通信.
因此,可采用文献[22]的分布式策略对表A与表C的并行生成,且不需要将表B中的全部内容放在内存中.
MapReduce是一个编程模型,其主要操作分为Map和Reduce两个阶段,每个阶段的输入和输出都是基于键值对.
在Map阶段,Map函数将输入文件中的每一行变为键值对(K1,V1)的形式,经过map函数的处理,输出多个新的键值对List(K2,V2);在Reduce阶段,所有的Map阶段的输出按键分组(K2,List(V2)),该过程称为混洗(shuffle).
每组(K2,List(V2))作为Reduce函数的输入,经过Reduce函数的处理,输出最终的结果(K3,V3).
在计算局部稀疏因子矩阵[ZLλ]k*d(o)(o∈LDS(obji))时,可采用文献[22]的分布式策略LSH,但要改变步骤,即,在obji索引值关联的数据集中查询LDS(o)(o∈LDS(obji));在计算稀疏度因子λ和离群因子Factor时,都可由Map来实现;在按Factor大小进行全排序时,需要一个Map对Factor进行取样,进而实现决定各个(K2,V2)分配到哪个结点的Partition函数,从而有效地解决了数据分配不均匀问题和局部有序但全局无序问题.
需要一个Reduce来对分配到各个结点的(K2,V2)进行排序,其MapReduce编程模型的实现过程如图2所示.
Fig.
2ImplementationprocessofMapReduceprogram图2MapReduce程序的实现过程由图2可知,在MapReduce编程模型中,离群因子计算过程如下:Factor(obj1)Factor(obj2)Factor(obj3)…ValueKeyobj1obj2obj3…λ1…ValueKeyobj1obj2obj3…λ2λ3Factor(obj1)Factor(obj2)Factor(obj3)…ValueKeyobj1obj2obj3…Factor(obj1)Factor(obj2)Factor(obj3)…KeyValueobj1obj2obj3…obj4Factor(obj4)LDS(obj1)LDS(obj2)LDS(obj3)…ValueKeyobj1obj2obj3…[ZLλ]k*d(o)(o∈LDS(obj3)…ValueKeyobj1obj2obj3…[ZLλ]k*d(o)(o∈LDS(obj1)[ZLλ]k*d(o)(o∈LDS(obj2)ReduceLSHLSHMapMapMap张继福等:基于MapReduce与相关子空间的局部离群数据挖掘算法1087(1)采用文献[22]的分布式策略,确定各个数据对象的LDS(obji);(2)采用一个Map函数,计算各个数据对象对应的稀疏度因子λi;(3)采用文献[22]的分布式策略,确定LDS(o)(o∈LDS(obji))对应的局部稀疏因子矩阵:[ZLλ]k*d(o)(o∈LDS(obji));(4)采用一个Map函数,计算各个数据对象对应的子空间定义向量vi,结合[ZLλ]k*d(o)(o∈LDS(obji))计算对应的离群因子Factor;(5)采用一个Map函数和一个Reduce函数,将各个数据对象按对应的离群因子Factor进行全排序并输出结果.
5基于相关子空间的离群数据并行挖掘算法5.
1并行算法在图2中,采用LSH策略计算数据对象obj的近似K-NN,并确定DS中各个数据对象obji的局部数据集LDS(obji),可由两个MapReduce任务来实现;计算obji各属性值的局部稀疏因子λij,以(obji,λi)作为输出并保存,可由MapReduce任务中的Map阶段来实现;生成obji的LDS(o)(o∈LDS(obji))对应的局部稀疏因子矩阵[ZLλ]k*d(o)(o∈LDS(obji))也可采用LSH策略,并由两个MapReduce任务来实现;根据obji对应的局部稀疏因子矩阵[ZLλ]k*d(obji),由公式(9)计算obji各属性维对应的局部稀疏差异因子,并由定义2确定obji对应的子空间定义向量,并计算obji的离群因子,可由MapReduce任务中的Map阶段来实现;根据Factor值的大小对数据对象并行排序,可由一个MapReduce任务来实现;将离群程度明显较大的n个数据对象作为离群数据.
其并行算法描述如下:算法.
RSLODA(related-subspace-basedlocaloutlierdetectionalgorithmusingMapReduce).
输入:数据集DS(属性个数为d)、近邻数K、稀疏度差异因子阈值ε.
输出:n个离群数据.
(1)执行LSH中的MapReduce任务,生成{(obj,LDS(obj))};//*并行计算数据对象obj的LDS(obj)(2)以{(obj,LDS(obj))}作为输入,执行MapReduce任务,生成{(obj,λ)};//*确定DS中每个数据对象obj对应的稀疏度因子λ,见公式(8)(3)以{(obj,λ)}作为输入,执行LSH中的MapReduce任务,生成{(obj,([ZLλ]k*d(o)(o∈LDS(obji)确定DS中每个数据对象obj的LDS(obj)对应的局部稀疏因子矩阵[ZLλ]k*d(o)(o∈LDS(obji))(4)以{(obj,([ZLλ]k*d(o)(o∈LDS(obji))))}作为输入,执行MapReduce任务,生成{(obj,Factor(obj))};//*确定DS中每个数据对象obj对应的离群因子Factor(obj),见公式(14)(5)以{(obj,Factor(obj))}作为输入,执行MapReduce任务,对{(obj,Factor(obj))}按Factor大小进行全排序;//*确定DS中每个数据对象obj按对应的离群因子Factor(obj)的大小进行全排序(6)输出离群程度最大的n个数据对象.
//*选取Top(N)作为离群数据算法说明:1.
在上述RSLODA并行算法中,步骤(1)、步骤(3)中的MapReduce任务是实现文献[15]中的LSH策略,即查询各个数据对象的近似KNN,文献[15]对其处理过程给出了详细的分析;步骤(5)中的MapReduce对其结果先进行采样,然后进行并行全排序[30].
2.
在RSLODA中,步骤(2)的MapReduce任务执行流程是:1088JournalofSoftware软件学报Vol.
26,No.
5,May2015receive{(obj,LDS(obj))}Foreach(obj,LDS(obj))in{(obj,LDS(obj))}Map:1)For(m=1;m30时,RSLODA算法的准确率略有下降.
这是因为:当K取值较大时,由近似KNN得到的离群因1.
525K=10K=20K=30K=40201510501.
41.
31.
2ε时间(m)7050403020100503010K时间(m)ε=1.
2ε=1.
3ε=1.
4ε=1.
54510080604020353025KNN的个数K准确率(%)RSLODALoOPCOP402001008060402010050维度d准确率(%)150RSLODALoOPSOD1092JournalofSoftware软件学报Vol.
26,No.
5,May2015子可能会出现较小误差;RSLODA算法在K∈[30,40]时,其挖掘准确率都比LoOP算法和COP算法要高,其主要原因是:LoOP算法是在所有维构成的空间中采用高斯误差函数来度量离群程度,会找不到子空间中的离群数据,COP算法仅能发现局部数据集的线性相关子空间.
图6(b)是不同维度3000条人工数据集的实验结果,且K值均取30.
当维度增加时,LoOP的准确率会降低.
其主要原因是LoOP算法是在所有维构成的空间中挖掘离群数据,随着维度的增加,相应地无关维也会增加,有些离群数据可能被隐藏,且受"维灾"的影响也逐渐严重.
SOD和RSLODA的准确率不变,其主要原因是:它们都是相关子空间中的离群挖掘算法,只要人工数据的相关子空间维度不会发生较大的变化,其挖掘准确率就基本不受维度的影响.
RSLODA算法在任何数据维度下,其挖掘准确率都比LoOP和SOD算法要高.
其主要原因是:LoOP和RSLODA算法虽然都采用高斯误差函数来度量离群程度,可以有效地应用于不同分布的数据集,但LoOP受"维灾"影响较严重,而SOD算法当数据对象分布在两个或两上以上的子空间中时,将不能区分它们的离群程度[15].
6.
2天体光谱数据集采用天体光谱数据集作为测试数据,实验验证数据维度对RSLODA算法挖掘效率的影响以及RSLODA算法的可伸缩性和可扩展性.
6.
2.
1维度对算法效率的影响在图7中,随着维度的变化,图7(a)体现了RSLODA算法的挖掘耗时,图7(b)体现了RSLODA算法挖掘耗时的时间比值.
由图7可以看出,随着维度按比例增加,1)确定各个数据对象的哈希桶以及按索引值将其关联的哈希桶导入程序中时的计算量(见公式(7))、确定数据对象对应KNN中计算距离的计算量、计算局部稀疏因子的计算量(见公式(8))以及局部稀疏差异因子的计算量(见公式(9))都与数据维度d呈线性关系,也都会按比例增加;2)计算离群因子的计算量(见公式(14))仅与相关子空间维度dr呈线性关系;3)恒星光谱数据集与人工数据集不同,随着维度的增加,会有较大比例的属性维增加到相关子空间中.
因此,当计算结点与数据条数不变时,其挖掘效率按略高于线性趋势提高.
(a)(b)Fig.
7Efficiencyimpactofdimension(5*106stellarspectralrecords,K=30,ε=0.
1,node=16)图7维度对效率的影响(500万条光谱数据集,K=30,ε=0.
1,计算结点=16)6.
2.
2伸缩性在图8中,随着数据量的变化,图8(a)体现了RSLODA算法的挖掘耗时,图8(b)体现了RSLODA算法挖掘耗时的时间比值.
由图8可知:当计算结点不变时,随数据量的增加,其挖掘效率降低.
其主要原因是:首先,随着数据量的增加,数据对象个数的增多,各结点上分配的数据对象个数基本按计算结点比例线性增加;同时,各个数据对象在计算其离群因子的整个过程中的计算量会随着数据对象的增加,分配到各个计算结点的数据对象也按平均比例增多;由于各个数据对象的散列值相同的数据对象数也可能20010864210050维度d时间(m)150200141210864210050维度d时间比150张继福等:基于MapReduce与相关子空间的局部离群数据挖掘算法1093增多,LSH策略是按数据对象与其散列值相同的数据对象中查询KNN,每个数据对象对应的KNN查询的时间与散列值相同的数据对象集的个数n是o(n)的关系,即使借助索引也只能降到o(logn),其他计算过程的计算量与数据对象个数的比值近似是定值,对应的计算量可以按计算结点比例线性分配.
其次,数据量的增加还会增加Shuffle的消耗.
总之,随数据量的增加,其挖掘效率曲线的倾斜程度要略高于线性.
(a)(b)Fig.
8Efficiencyimpactofdatarecord(dimensions=200,K=30,ε=0.
1,node=6)图8数据量对挖掘效率的影响(200维光谱数据,K=30,ε=0.
1,计算结点=6)6.
2.
3可扩展性在图9中,随着计算结点数的增加,图9(a)体现了RSLODA算法挖的掘耗时,图9(b)体现了RSLODA算法的加速比值.
(a)(b)Fig.
9Efficiencyimpactofcomputernode(5*106stellarspectralrecords,dimensions=200,K=30,ε=0.
1)图9计算结点对挖掘效率的影响(500万条光谱数据,200维,K=30,ε=0.
1)由图9可以看出,当数据量一定时,随着集群计算结点个数的增加,RSLODA算法的挖掘耗时基本按计算结点比例减小,体现了RSLODA算法具有较好的并行程度.
其主要原因是:首先,算法RSLODA中各个数据对象的离群因子的所有计算过程完全可以并行化,各计算结点的数据对象个数可以按计算结点比例分配.
由于RSLODA算法采用LSH策略寻找K最近邻,计算结点的增加并不会影响到各数据对象对应的索引值,即,每个结点对应的查询近似KNN的计算量不会改变.
因此,近似KNN的计算量随着数据对象分配,基本按比例分配到各计算结点.
同样,其他计算过程的计算量与数据对象个数呈线性关系,数据对象也按比例分配到各计算结点;其次,随着计算结点的增加也会增加一些网络传输量,但RSLODA算法只有一个Shuffle过程,受其影响相当小;随着计算结点的增加,由于Hadoop已逐渐无法有效地为各计算结点均匀地划分任务,因此并123530252015105416结点数时间(m)8124416结点数加速比8321302520151051050数据量(*105条光谱)时间(m)204030876543211050数据量(*105条光谱)时间比20401094JournalofSoftware软件学报Vol.
26,No.
5,May2015行化效果会逐渐降低.
7结束语在高维海量数据数据集中,从由有意义维构成的相关子空间中实现数据挖掘挖掘任务是数据挖掘领域研究热点和难点之一.
本文利用MapReduce编程模型的强大数据处理能力,提出一种基于相关子空间的局部离群数据挖掘算法.
该算法利用属性维在局部数据集上的稀疏程度,重新定义了相关子空间,有效地避免了无关属性维对离群数据的影响,并能有效地发现隐藏在子空间中的局部离据数据;充分利用了集群系统和MapReduce编程模型的数据处理能力,具有较好挖掘效果以及可扩展性和可伸缩性等,并能有效地适应于海量高维数据.
下一步研究的工作是:局部数据集较难体现聚集簇的分布特征时,其离群程度值偏小的问题.
References:[1]KnoxEM,NgRT.
Algorithmsforminingdistance-basedoutliersinlargedatasets.
In:Proc.
oftheInt'lConf.
onVeryLargeDataBases.
1998.
392403.
[2]ZhangJF,JiangYY,HuLH,CaiJH,ZangSL.
Aconceptlatticebasedrecognitionmethodofcelestialspectraoutliers.
ActaAutomaticaSinica,2008,34(9):10601066(inChinesewithEnglishabstract).
[3]PhamN,PaghR.
Anear-lineartimeapproximationalgorithmforangle-basedoutlierdetectioninhigh-dimensionaldata.
In:Proc.
ofthe18thACMSIGKDDInt'lConf.
onKnowledgeDiscoveryandDataMining.
ACMPress,2012.
877885.
[doi:10.
1145/2339530.
2339669][4]SequeiraK,ZakiM.
ADMIT:Anomaly-Baseddataminingforintrusions.
In:Proc.
ofthe8thACMSIGKDDInt'lConf.
onKnowledgeDiscoveryandDataMining.
ACMPress,2002.
386395.
[doi:10.
1145/775047.
775103][5]LazarevicA,ErtozL,KumarV,OzgurA,SrivastavaJ.
Acomparativestudyofanomalydetectionschemesinnetworkintrusiondetection.
TechnicalReport,UniversityofMinnesota,2003.
[6]LiuH,ShahS,JiangW.
On-Lineoutlierdetectionanddatacleaning.
Computers&ChemicalEngineering,2004,28(9):16351647.
[7]BarnettV,LewisT.
OutliersinStatisticalData.
NewYork:Wiley,1994.
[doi:10.
1016/j.
compchemeng.
2004.
01.
009][8]TaoY,XiaoX,ZhouS.
Miningdistance-basedoutliersfromlargedatabasesinanymetricspace.
In:Proc.
ofthe12thACMSIGKDDInt'lConf.
onKnowledgeDiscoveryandDataMining.
ACM,2006.
394403.
[9]RamaswamyS,RastogiR,ShimK.
Efficientalgorithmsforminingoutliersfromlargedatasets.
ACMSIGMODRecord,2000,29(2):427438.
[doi:10.
1145/335191.
335437][10]BreunigMM,KriegelHP,NgRT,SanderJ.
LOF:Identifyingdensity-basedlocaloutliers.
ACMSIGMODRecord,2000,29(2):93104.
[doi:10.
1145/335191.
335388][11]PapadimitriouS,KitagawaH,GibbonsPB,FaloutsosC.
Loci:Fastoutlierdetectionusingthelocalcorrelationintegral.
In:Proc.
ofthe19thInt'lConf.
onDataEngineering(ICDE).
IEEE,2003.
315326.
[doi:10.
1109/ICDE.
2003.
1260802][12]SarawagiS,AgrawalR,MegiddoN.
Discovery-DrivenExplorationofOLAPDataCubes.
Berlin,Heidelberg:Springer-Verlag,1998.
[doi:10.
1007/BFb0100984][13]KriegelHP,ZimekA.
Angle-Basedoutlierdetectioninhigh-dimensionaldata.
In:Proc.
ofthe14thACMSIGKDDInt'lConf.
onKnowledgeDiscoveryandDataMining.
ACMPress,2008.
444452.
[doi:10.
1145/1401890.
1401946][14]KriegelHP,KrogerP,SchubertE,ZimekA.
Outlierdetectioninarbitrarilyorientedsubspaces.
In:Proc.
ofthe2012IEEE12thInt'lConf.
onDataMining.
IEEEComputerSociety,2012.
379388.
[doi:10.
1109/ICDM.
2012.
21][15]MullerE,SchifferM,SeidlT.
Statisticalselectionofrelevantsubspaceprojectionsforoutlierranking.
In:Proc.
oftheIEEE27thInt'lConf.
onDataEngineering(ICDE).
IEEE,2011.
434445.
[doi:10.
1109/ICDE.
2011.
5767916][16]AggarwalCC,YuPS.
Outlierdetectionforhighdimensionaldata.
ACMSigmodRecord,2001,30(2):3746.
[doi:10.
1145/376284.
375668][17]KellerF,MullerE,BohmK.
HiCS:Highcontrastsubspacesfordensity-basedoutlierranking.
In:Proc.
ofthe28thInt'lConf.
onDataEngineering(ICDE).
IEEE,2012.
10371048.
[doi:10.
1109/ICDE.
2012.
88]张继福等:基于MapReduce与相关子空间的局部离群数据挖掘算法1095[18]AggarwalCC,PhilipSY.
Aneffectiveandefficientalgorithmforhigh-dimensionaloutlierdetection.
TheVLDBJournal,2005,14(2):211221.
[doi:10.
1007/s00778-004-0125-5][19]ZhangJF,JiangYY,ChangKH,ZhangSL,CaiJH,HuLH.
Aconceptlatticebasedoutlierminingmethodinlow-dimensionalsubspaces.
PatternRecognitionLetters,2009,30(15):14341439.
[doi:10.
1016/j.
patrec.
2009.
07.
016][20]KriegelHP,KrgerP,SchubertE,ZimekA.
Outlierdetectioninaxis-parallelsubspacesofhighdimensionaldata.
In:Proc.
ofthe13thPacific-AsiaConf.
onAdvancesinKnowledgeDiscoveryandDataMining.
Berlin,Heidelberg:Springer-Verlag,2009.
831838.
[doi:10.
1007/978-3-642-01307-2_86][21]BouguessaM,WangS.
Miningprojectedclustersinhigh-dimensionalspaces.
IEEETrans.
onKnowledgeandDataEngineering,2009,21(4):507522.
[doi:10.
1109/TKDE.
2008.
162][22]StuparA,MichelS,SchenkelR.
RankReduce—Processingk-nearestneighborqueriesontopofMapReduce.
In:Proc.
ofthe8thWorkshoponLarge-ScaleDistributedSystemsforInformationRetrieval.
2010.
1520.
[23]LuW,ShenYY,ChenS,OoiBC.
Efficientprocessingofknearestneighborjoinsusingmapreduce.
Proc.
oftheVLDBEndowment,2012,5(10):10161027.
[doi:10.
14778/2336664.
2336674][24]LiuY,JingN,ChenL,XiongW.
Algorithmforprocessingk-nearestjoinbasedonR-treeinMapReduce.
RuanJianXueBao/JournalofSoftware,2013,24(8):18361851(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/4377.
htm[doi:10.
3724/SP.
J.
1001.
2013.
04377][25]AngiulliF,BastaS,LodiS,SartoriC.
Distributedstrategiesforminingoutliersinlargedatasets.
IEEETrans.
onKnowledgeandDataEngineering,2013,25(7):15201532.
[doi:10.
1109/TKDE.
2012.
71][26]KriegelHP,KrgerP,SchubertE,ZimekA.
LoOP:Localoutlierprobabilities.
In:Proc.
ofthe18thACMConf.
onInformationandKnowledgeManagement.
ACMPress,2009.
16491652.
[doi:10.
1145/1645953.
1646195][27]ZhangC,LiF,JestesJ.
EfficientparallelkNNjoinsforlargedatainMapReduce.
In:Proc.
ofthe15thInt'lConf.
onExtendingDatabaseTechnology.
ACMPress,2012.
3849.
[doi:10.
1145/2247596.
2247602][28]DatarM,ImmorlicaN,IndykP,MirrokniVS.
Locality-Sensitivehashingschemebasedonp-stabledistributions.
In:Proc.
ofthe20thAnnualSymp.
onComputationalGeometry.
ACMPress,2004.
253262.
[doi:10.
1145/997817.
997857][29]HouleME,KriegelHP,KrgerP,SchubertE,ZimekA.
Canshared-neighbordistancesdefeatthecurseofdimensionality.
In:Proc.
oftheScientificandStatisticalDatabaseManagement.
Berlin,Heidelberg:Springer-Verlag,2010.
482500.
[doi:10.
1007/978-3-642-13818-8_34][30]WhiteT.
Hadoop:TheDefinitiveGuide.
O'Reilly,2012.
附中文参考文献:[2]张继福,蒋义勇,胡立华,蔡江辉,张素兰.
基于概念格的天体光谱离群数据识别方法.
自动化学报,2008,34(9):10601066.
[24]刘义,景宁,陈荦,熊伟.
MapReduce框架下基于R-树的k-近邻连接算法.
软件学报,2013,24(8):18361851.
http://www.
jos.
org.
cn/1000-9825/4377.
htm[doi:10.
3724/SP.
J.
1001.
2013.
04377]张继福(1963-),男,山西平遥人,博士,教授,博士生导师,CCF高级会员,主要研究领域为数据挖掘与人工智能,并行与分布式计算.
秦啸(1974-),男,博士,副教授,博士生导师,主要研究领域为并行与分布式计算,数据密集型计算,存储器节能.
李永红(1988-),男,硕士生,主要研究领域为数据挖掘,并行计算.
荀亚玲(1980-),女,博士生,讲师,主要研究领域为数据挖掘,并行计算.