基于距离的不确定离群点检测

计算机研究与发展　ＩＳＳＮ　１０００—１２３９１ＣＮ　１１－１７７７门ｒＰ　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ　４７（３）：４７４－４８４，２０１０　基于距离的不确定离群点检测　于　浩　王　斌　肖　目４　杨晓春　（东北大学信息科学与工程学院沈阳　１１０００４）　（中国人民大学数据工程与知识工程教育部重点实验室　北京　１００８７２）　（ｙａｎｇｘｃ＠ｍａｉｌ．ｎｅｕ．ｅｄｕ．ｃｎ）　Ｄｉｓｔａｎｃｅ－Ｂａｓｅｄ　Ｏｕｔｌｉｅｒ　Ｄｅｔｅｃｔｉｏｎ　ｏｎ　Ｕｎｃｅｒｔａｉｎ　Ｄａｔａ　Ｙｕ　Ｈａｏ　，Ｗａｎｇ　Ｂｉｎ　，Ｘｉａｏ　Ｇａｎｇ　，ａｎｄ　Ｙａｎｇ　Ｘｉａｏｃｈｕｎ　，　（Ｃｏｌｌｅｇｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｎｏｒｔｈｅａｓｔｅｒｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈｅｎｙａｎｇ　１　１０００４）　（Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ｋｎｏｗｌｅｄｇｅ　Ｅｎｇｉｎｅｅｒｉｎｇ　ｆｏｒ　ｔｈｅ　Ｍｉｎｉｓｔｒｙ　ｏｆ　Ｅｄｕｃａｔｉｏｎ，Ｒｅｎｍｉｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｃｈｉｎａ，Ｂｅｉｊｉｎｇ　１００８７２）　Ａｂｓｔｒａｃｔ　Ｏｕｔｌｉｅｒ　ｄｅｔｅｃｔｉｏｎ　ｉｓ　ｏｎｅ　ｏｆ　ｔｈｅ　ｖａｌｕａｂｌｅ　ｔｅｃｈｎｉｑｕｅｓ　ｉｎ　ｍａｎｙ　ａｐｐｌｉｃａｔｉｏｎｓ，ｓｕｃｈ　ａｓ　ｎｅｔｗｏｒｋ　ｉｎｔｒｕｓｉｏｎ　ｄｅｔｅｃｔｉｏｎ，ｅｖｅｎｔ　ｄｅｔｅｃｔｉｏｎ　ｉｎ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋ（ＷＳＮ），ａｎｄ　ｓｏ　ｏｎ．Ｔｈｉｓ　ｔｅｃｈｎｉｑｕｅ　ｈａｓ　ｂｅｅｎ　ｗｅｌｌ　ｓｔｕｄｉｅｄ　ｏｎ　ｄｅｔｅｒｍｉｎｉｓｔｉｃ　ｄａｔａｂａｓｅｓ．Ｈｏｗｅｖｅｒ，ｉｔ　ｉｓ　ａ　ｎｅｗ　ｔａｓｋ　ｏｎ　ｅｍｅｒｇｉｎｇ　ｕｎｃｅｒｔａｉｎ　ｄａｔａｂａｓｅ．Ｕｓｉｎｇ　ｔｈｅ　ｎｅｗ　ｕｎｃｅｒｔａｉｎ　ｄａｔａ　ｍｏｄｅｌ，ｍａｎｙ　ｒｅａｌ　ａｐｐｌｉｃａｔｉｏｎｓ，ｓｕｃｈ　ａｓ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋ，ｄａｔａ　ｉｎｔｅｇｒａｔｉｏｎ，ａｎｄ　ｄａｔａ　ｍｉｎｉｎｇ，ｃａｎ　ｂｅ　ｂｅｔｔｅｒ　ｄｅｓｃｒｉｂｅｄ．Ｔｈｅ　ｆｅａｓｉｂｉｌｉｔｙ　ｏｆ　ｓｕｃｈ　ａｐｐｌｉｃａｔｉｏｎｓ　ｃａｎ　ｂｅ　ｆｕｒｔｈｅｒ　ｅｎｈａｎｃｅｄ．Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ａ　ｎｅｗ　ｄｅｆｉｎｉｔｉｏｎ　ｏｆ　ｏｕｔｌｉｅｒ　ｏｎ　ｕｎｃｅｒｔａｉｎ　ｄａｔａ　ｉｓ　ｄｅｆｉｎｅｄ．Ｂａｓｅｄ　ｏｎ　ｉｔ，ｓｏｍｅ　ｅｆｆｉｃｉｅｎｔ　ｆｉｌｔｅｒｉｎｇ　ａｐｐｒｏａｃｈｅｓ　ｆｏｒ　ｏｕｔｌｉｅｒ　ｄｅｔｅｃｔｉｏｎ　ａｒｅ　ｐｒｏｐｏｓｅｄ，ｉｎｃｌｕｄｉｎｇ　ａ　ｂａｓｉｃ　ｆｉｌｔｅｒｉｎｇ　ａｐｐｒｏａｃｈ，ｃａｌｌｅｄ　ｂ—ＲＦＡ，ａｎｄ　ａｎ　ｉｍｐｒｏｖｅｄ　ｆｉｌｔｅｒｉｎｇ　ａｐｐｒｏａｃｈ，ｃａｌｌｅｄ　ｏ—ＲＦＡ．Ｍｏｒｅｏｖｅｒ，　ａ　ｐｒｏｂａｂｉｌｉｔｙ　ａｐｐｒｏａｃｈ，ｃａｌｌｅｄ　ＤＰＡ，ｉｓ　ｐｒｏｐｏｓｅｄ　ｔｏ　ｅｆｆｉｃｉｅｎｔｌｙ　ｄｅｔｅｃｔ　ｏｕｔｔｉｅｒ　ｏｎ　ｕｎｃｅｒｔａｉｎ　ｄａｔａｂａｓｅ．　Ｔｈｅ　ａｐｐｒｏａｃｈ　ｂ—ＲＦＡ　ｕｔｉｌｉｚｅｓ　ｔｈｅ　ｐｒｏｐｅｒｔｙ　ｏｆ　ｎｏｎ—ｏｕｔｌｉｅｒ　ｔｏ　ｒｅｄｕｃｅ　ｔｈｅ　ｔｉｍｅｓ　ｏｆ　ｄｅｔｅｃｔｉｏｎ．Ｍｏｒｅｏｖｅｒ，　ｏ—ＲＦＡ　ｉｍｐｒｏｖｅｓ　ｂ—ＲＦＡ　ｂｙ　ｍｉｎｉｎｇ　ａｎｄ　ｕｓｉｎｇ　ｔｈｅ　ｄａｔａ　ｄｉｓｔｒｉｂｕｔｉｏｎ．Ｆｕｒｔｈｅｒｍｏｒｅ，ＤＰＡ　ｆｉｎｄｓ　ｔｈｅ　ｒｅｃｕｒｓｉｏｎ　ｒｕｌｅ　ｉｎ　ｐｒｏｂａｂｉｌｉｔｙ　ｃｏｍｐｕｔａｔｉｏｎ　ａｎｄ　ｇｒｅａｔｌｙ　ｉｍｐｒｏｖｅｓ　ｔｈｅ　ｅｆｆｉｃｉｅｎｃｙ　ｏｆ　ｓｉｎｇｌｅ　ｄａｔａ　ｄｅｔｅｃｔｉｏｎ．　Ｆｉｎａｌｌｙ，ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｐｐｒｏａｃｈｅｓ　ｃａｎ　ｅｆｆｉｃｉｅｎｔｌｙ　ｐｒｕｎｅ　ｔｈｅ　ｃａｎｄｉｄａｔｅｓ　ａｎｄ　ｒｅｄｕｃｅ　ｔｈｅ　ｃｏｒｒｅｓｐｏｎｄｉｎｇ　ｓｅａｒｃｈｉｎｇ　ｓｐａｃｅ，　ａｎｄ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｑｕｅｒｙ　ｐｒｏｃｅｓｓｉｎｇ　ｏｎ　ｕｎｃｅｒｔａｉｎ　ｄａｔａ．　Ｋｅｙ　ｗｏｒｄｓ　ｕｎｃｅｒｔａｉｎ　ｄａｔａ；ｏｕｔｌｉｅｒ　ｄｅｔｅｃｔｉｏｎ；ｐｒｕｎｉｎｇ　ｍｅｔｈｏｄ；ｅｆｆｉｃｉｅｎｃｙ；ｕｎｃｅｒｔａｉｎ　ｄａｔａ　ｍｏｄｅｌ　摘要在诸如网络入侵、无线传感器网络异常事件等检测应用中，离群点检测是一项具有很高应用价　值的技术．这项技术在确定性数据中已经得到了深入的研究，但在新兴的不确定数据领域却是一项新的　研究课题．在无线传感器网络、数据集成和数据挖掘等技术中使用不确定数据模型更能真实反映现实世　界，进一步提高这些技术的实际可行性．针对不确定数据，提出新的离群点定义．提出基于距离的不确定　数据离群点检测的高效过滤方法，包括基础过滤方法ｂ—ＲＦＡ和改进方法。一ＲＦＡ，最后提出高效概率计　算方法ＤＰＡ．ｂ—ＲＦＡ方法利用非离群点的过滤性质，减少检测次数．ｏ—ＲＦＡ方法通过挖掘数据分布信　息对ｂ—ＲＦＡ方法作出改进，进一步提高过滤效率．ＤＰＡ方法找到概率求解中的递推规律，极大提高了　单点检测效率．实验结果显示：提出的方法可以有效地减少候选集，降低搜索空间，改善在不确定数据上　的查询性能．　收稿日期：２００９—０６—２６；修回日期：２００９　０９　３０　基金项目：国家自然科学基金项目（６０８２８００４，６０９７３０２０）；教育部新世纪优秀人才支持计划基金项目（ＮＣＥＴ－０６—０２９０）；中国人民大学数据工　程与知识工程教育部重点实验室开放课题（２００８００２）　于浩等：基于距离的不确定离群点检测　４７５　关键词　不确定数据；离群点检测；过滤方法；高效；不确定数据模型　中图法分类号ＴＰ３９１　离群点检测用于寻找数据集中的噪声数据，是　出了对象ｔ　邻居区域内所有对象组成的可能世界　数据挖掘领域的一项重要技术．基于距离的离群点　实例，若对ｔ　作距离参数　一２０、邻居对象数量阈值　检测被广泛应用于网络入侵检测、银行信贷等领　ｋ一２的离群点检测，那么在前５个实例中ｔ　的邻居　域［１　］．现有的基于距离的离群点检测技术目前主要　应用在传统数据库中，其数据的存在性和可信性确　凿无疑．但在很多现实的应用领域中，数据的收集和　处理受到多种因素的影响，数据的不确定性逐渐受　到了人们的关注，比如在传感器网络中，数据准确性　和可信性会受到感知器件精度、感知结点能量和网　络传输质量等因素的制约；在数据集成领域，由于数　据源的不一致性和模式映射的复杂多样，集成后的　数据不可避免地会引入不确定性．由于数据项引入　了概率值（或称可信度），应用于传统数据的技术无　法直接应用于不确定数据．　表１为一个典型的不确定数据表，该表可视为　在某种应用中获得的原始数据经过某种处理得到的　抽象表，这里不考虑其数据来源，只用来说明概率维　度对离群点检测的影响．Ｔｕｐｌｅ—ＩＤ表示不确定元　组的唯一标识；Ｖａｌｕｅ一１和Ｖａｌｕｅ一２分别表示元组　值维度上的２个属性，与确定性数据一样，不确定数　据在值维度上是可以存在多属性的，这里为了方便　说明只用２个属性；Ｃｏｎｆ表示该元组的可信度．　Ｔａｂｌｅ　１　Ｕｎｃｅｒｔａｉｎ　Ｄａｔａ　表１不确定数据　ＶａｌｕｅＩ　Ｖａｌｕｅ２　‘‘・　Ｃｏｎｆ　０．６　０．４　０．８　Ｏ．６　在确定性数据中判断一个对象是否为基于距离　的离群点，需要根据用户给出的距离参数找出该对　象邻居（包含自身）数量是否满足数量阈值．暂时不　考虑表１的概率维度，该表为一个确定性数据表，若　用户给出距离参数为　一２０，数量阈值为志一４，则检　测对象ｔ　就不是离群点；若忌一５，则ｔ。就是离群点．　在不确定数据中评价一个对象是否为离群点的　最基本方法就是利用可能世界模型（ｐｏｓｓｉｂｌｅ　ｗｏｒｌｄ），将对象的邻居展开成为多个可能世界实例，　然后利用确定性数据的处理方法逐个处理．表２列　对象数量小于是，在后１１个实例中不小于忌．由此可　见，仅仅依靠距离参数和数量阈值无法判断检测是　否为离群点，必须衡量被检测对象是离群点和不是　离群点的可能性，因此对应上述２类实例的概率成　为判断不确定数据离群点的重要指标．　Ｔａｂｌｅ　２　Ｐｏｓｓｉｂｌｅ　Ｗｏｒｌｄ　ａｎｄ　Ｐｒｏｂａｂｉｌｉｔｙ　ｆｏｒ　ｔｈｅ　Ｎｅｉｇｈｂｏｒｓ　ｏｆ　ｔｌ　表２　ｔ。的邻居组成的可能世界及概率　Ｐｏｓｓｉｂｌｅ　Ｗｏｒｌｄ　Ｐｏｓｓｉｂｌｅ　Ｗｏｒｌｄ　Ｐｒｏｂａｂｉｌｉｔｙ　Ｐ　。ｂ　ｂｉｌｉｔｙ　Ｉｎｓｔａｎｃｅｓ　Ｉｎｓｔａｎｃｅｓ　∞ｏ一　０．０１９２　Ｗ８一｛ｔ２，ｔｓ｝０．０５１２　∞１一｛ｔ１）０．０２８８　Ｗ９一（ｔ２，ｔ４）０．０１９２　ｗ２一｛ｔ２｝０．０１２８　∞１０一（ｔ３，ｔ４）０．１１５２　ｔ蜥一｛ｔ３｝０．０７６８　”ｌｌ一｛ｔ】，ｔ２，ｔ３）０．０７６８　４一｛ｔ４）０．０２８８　Ｗ１２一｛ｔ１，ｔ２，ｔ４｝０．０２８８　Ｗ５一｛　１，ｔ２｝０．０１９２　Ｗ１３：｛ｔｌ，ｔ３，ｔ４）０．１７２８　６一｛ｔｌ，ｔ３｝０．１１５２　Ｗｌ４一｛ｔｚ，ｔ３，ｔ４｝０．０７６８　７一｛ｔ１，ｔ４）０．０４３２　＂Ｕ）１５一｛ｔｌ，ｔ２。ｔ３，ｔ４）０．１１５２　设元组相互独立，例如叫。出现的概率ｐ（ｗ。）＝＝＝　（１—０．６）×（１—０．４）×（１～．０．８）×（１—０．６）一　０．０１９２，同理，ｐ（ｗ１３）一０．１７２８．由ｔ１邻居对象组成　的可能世界实例及其概率如表２所示，所有实例的　概率和为１．由此可得ｔ　是离群点的概率为前５个　实例的概率和０．１６６４，不是离群点的概率为后１１　个实例的概率和０．８３３６．若ｔ　不是离群点的概率满　足用户要求，则ｔ　不是离群点．因此用户在提交不　确定数据离群点查询时，除了需要给出距离参数和　数量阈值之外还需给出概率阈值．　由于检测对象的数量巨大以及可能世界实例空　间的规模随指数级增长，上述这种原始方法并不可　行．面临的问题主要是如何利用不确定数据的特殊　性找到过滤方法，减少检测次数；概率求解中如何避　免实例空间的膨胀．　１　相关工作　确定性数据上的离群点检测技术主要分为基于　４７６　计算机研究与发展２０１０，４７（３）　统计、密度、深度、距离和偏差５类¨３　］，其中基于统　计、密度和距离的方法应用最广．基于统计的检测技　术＿４　是最早应用于离群点检测的，它通过对小概率　事件的判定来检测数据样本中的异常；基于密度的　言，则需要考查所有可能世界实例来判断数据对象　的　范围内的邻居数据是否有足够的数据对象．　定义２．（ｕｐ，ｕｄ，　）一离群点．不确定数据库　Ｄｕ一｛ｔ１，ｔ２，…，ｔ　｝，其中每个元组ｔ　一＜ｒ，Ｃｏｎｆ＞．为　Ｉ一　．１　检测技术［５　将记录值间的距离和给定范围内的记录　方便表达，令ｋ—ｌ（１一ｕｐ）Ｘ　　ＩＤｕ　Ｉ　Ｉ．设　（￡）　数作为２个参数，根据记录的密度判定是否为离群　点；基于距离的检测技术　通过检测数据记录在　多维空间的一定范围内是否有足够的其他数据记录　来判断该记录是否为离群点．出于算法复杂度和实　际可行性等原因，基于深度和偏差的技术较前面３　种技术相对较少使用．　不确定数据已经成为一个新兴的研究领　域口　“］，Ｐｒｏｂａｂｉｌｉｓｔｉｃ　Ｓｋｙｌｉｎｅ查询＿１。＿用以查找不确　定数据上的支配对象集；Ｔｏｐ一是查询根据对数据的　关注角度不同，分为Ｕ—Ｔｏｐｋ查询口　、Ｕ—ｋＲａｎｋｓ查　询［１　］和ＰＴ一是查询＿１。　等．Ａｇｇａｒｗａｌ等人在文献　［１４］中提出了不确定数据基于密度的离群点检测技　术，其中数据记录都是按照某概率密度函数（ＰＤＦ）　分布在一个不确定区域（ｕｎｃｅｒｔａｉｎ　ｒｅｇｉｏｎ）中，在这　个区域上的ＰＤＦ积分为１．Ｋｒｉｅｇｅｌ等人提出一种基　于密度的聚簇算法口　，采用与文献［１４］相同的不确　定数据模型．本文针对带有离散概率值的基于距离　的不确定数据离群点检测技术进行深入研究．在本　文讨论的不确定数据模型中，每个对象都附加了一　个离散的概率值而非ＰＤＦ．　２检测模型　不确定离群点的邻居对象定义有其特殊性，由　于检测点在某些实例中不出现，因此检测点在每个　实例中的邻居对象是以检测点所在位置为中心的一　定半径范围内的对象．　定义１．ｕｄ范围内的邻居数据．不确定数据库　Ｄｕ一｛ｔ１，ｔ２，…，ｔ　），每个元组ｔ　一＜ｒ，Ｃｏｎｆ＞，ｒ表示　数据记录，Ｃｏｎｆ表示ｒ的可信度．设Ｗ是一个可能　世界实例，并且对Ｖ　，ＥＷ，ｔ，．ｒ出现在以ｔ　．ｒ为中心　ｕｄ为半径的范围内．令Ｗ中所有的元组ｔ，组成集　合Ｔ（ｔ　，叫），即丁（￡　，叫）一｛ｔ，ｌ　Ｖ　Ｅ　Ｗ，ｄｉｓｔ（ｔ　．ｒ，ｔ，．　ｒ）≤ｕｄ｝．　所有满足上述条件的Ｗ组成Ｗ（ｔ　），由此得到ｔ　的ｕｄ范围内的邻居数据，Ｒ（ｔ　）一　Ｕ　Ｔ（ｔ　，　）．　”∈Ｗ（　ｉ）　在确定性数据中，如果一个数据对象的ｕｄ范围　内的邻居数据没有足够多的数据对象，那么这个数据　对象就是一个基于距离的离群点．就不确定数据而　满足　（ｆ）　Ｗ（　），对Ｖ叫　Ｅ　（￡），有ｌ　Ｔ（ｔ，Ｗｉ）Ｉ≥　ｋ．如果Ｗ　（　）当中的所有可能世界实例的概率之和　不大于　，则ｔ是一个（ｕｐ，ｕｄ，　）一离群点．　如果对应于ｔＥ　Ｄ　的Ｒ（￡）包含的元组数量少　于是，则Ｗ　（￡）一　，ｔ就一定是一个（ｕｐ，ｕｄ，ｉｔ）一离　群点．根据定义２将Ｗ　Ｅ　Ｗ　（　）的概率记作ＰＴ（￡，　Ｗ　），一个（ｕｐ，ｕｄ，ｉｔ）一离群点查询Ｑ（Ｄｕ，ｕｐ，ｕｄ，　）　如式（１）所示：　Ｑ（Ｄｕ，ｕｐ，ｕｄ，　）一　｛ｔ　ｌ∑ＰＴ（ｔ，Ｗ　）≤ｉｔ，ｔ　Ｅ　Ｄｕ）．　（１）　∈Ｗｋ（ｆ）　为简单起见，本文简称（ｕｐ，ｕｄ，　）一离群点为离　群点．　３基于过滤的离群点检测技术　判断Ｄ　中元组ｔ是否为离群点，需要计算　Ｒ（￡）中至少发生ｋ个元组的概率．如果对ＩＤ　１个元　组逐一检测，效率低下，因此本文提出了用于离群点　检测的过滤方法．　３．１过滤原理　在检测Ｄ　中某个元组ｔ时，对其Ｒ（　）内的元　组按与ｔ的距离升序排序，然后求解Ｒ（　）中至少发　生ｋ个元组的概率．如图１所示，当遍历到元组　Ｒ（　）［　］时，Ｔ一｛Ｒ（　）［Ｏ］，…，Ｒ（￡）Ｉ－ｊ］）中至少发生　ｋ个元组的概率大于　，那么对Ｖ　∈Ｄｕ，如果Ｔ　Ｒ（ｔ　），那么Ｒ（ｔ　）中至少发生走个元组的概率就一　定大于　，即ｆ　不是离群点（如图１中的ｔ　和ｔｚ）．　Ｆｉｇ．１　Ｅｘａｍｐｌｅ　ｏｆ　ｐｒｕｎｉｎｇ．　图１过滤举例　定理１．设元组集合丁一｛ｔ。，ｔ。，…，ｔ　），　≥矗，　元组集Ｔ中至少发生ｋ个元组的事件记为［Ｔ，忌］，　于浩等：基于距离的不确定离群点检测　符号・表示积事件．若该事件发生的概率Ｐ（［Ｔ，　忌］）＞　，那么对于ＹＴ　Ｔ，都有Ｐ（ＩＴ　，点］）＞　．　证明．对Ｔ　作划分，Ｔ　一Ｔ　Ｕ（Ｔ　一Ｔ），事件　［Ｔ　，忌］　［Ｔ，忌］・［Ｔ　一Ｔ，ｏ］，则：　Ｐ（ＩＴ　，志］）≥Ｐ（［Ｔ，忌］・［Ｔ　一Ｔ，Ｏ］）．　由于元组间相互独立，可得：　Ｐ（［Ｔ，忌］・［Ｔ　一Ｔ，ｏ］）一　Ｐ（［Ｔ，忌］）×Ｐ（［Ｔ　一Ｔ，Ｏ］）．　由于［Ｔ　一Ｔ，０］是必然事件，Ｐ（［Ｔ　一丁，ｏ］）一　１，于是可得Ｐ（Ｅ　，忌］）≥Ｐ（［Ｔ，忌］）．若尸（［丁，正］）＞　，可得Ｐ（［丁　，　］）≥尸（ＩＴ，　］）＞　．　证毕．　由定理１可见，当发生上述情形时，不仅ｔ本身　不是离群点，而且还可以过滤一部分其他元组．本文　对Ｒ（　）中的记录按照与ｔ的距离升序排序，由近及　远依次遍历．如图２所示，若遍历记录Ｒ（￡）［　］后，　集合丁一｛Ｒ（　）［０］，…，Ｒ（ｆ）［　］）中至少发生志个元　组的概率大于　，则可以得到以ｔ为圆心、　（ｔ）一　ｄｉｓｔ（ｔ，ｔ　）为半径的圆形区域　（￡），其包含的记录　记为Ｒ　（　）．　Ｆｉｇ．２　Ｐｒｉｎｃｉｐｌｅ　ｏｆ　ｐｒｕｎｉｎｇ．　图２过滤原理　定理２．所有以ｕｄ为半径，且包含　（　）的圆　０　（０）的圆心组成的轨迹是与　（　）同心的，半径为　ｒ　（￡）一ｕｄ—　（　）的圆面．　证明．设　（￡）的圆心为（Ｘ　，Ｙ　），０　（０）的圆　心为０（１ｚ，．ｙ）．　（￡）在＠　（ｏ）内部，则０（ｚ，　）到　（￡）的最大距离应该不大于“　．　设点ｏ（Ｊｃ，　）与点　（　，Ｙ　）确定的直线与　（　）　分别交于点Ａ（ＸＡ，Ｙａ）和点Ｂ（Ｘ　，Ｙ　），由相关几　何原理可知：点ｏ（ｘ，　）到圆　（ｔ）的最大距离为　—　ｍａｘ（ＯＡ，ＯＢ），该距离应满足：　ｄ一￣／（ｚ—Ｘ　）　＋（　—Ｙ　）　＋　（　）≤ｕｄ．　经整理可得：　（ｚ—Ｘ　）。＋（　—Ｙ　）　≤（ｕｄ—　（￡））　，　ｏ（ｏｃ，　）的轨迹是以ｔ（Ｘ，ｙ）为圆心、半径为ｕｄ～　４７７　（　）的圆面．　证毕．　因此，对Ｖ　∈＠　（　）都有Ｒ　（￡）　Ｒ（ｆ　），可得ｔ　一定不是离群点，本文称＠　（￡）为ｔ确定的过滤区　域．利用０　（ｔ）的过滤性，可减少需要检测的元组　数量．　３．２基于Ｇｒｉｄ的空间划分　为了提高寻找Ｒ（ｔ）的效率，本文引用了文献　［１］中基于Ｇｒｉｄ的空间划分，为简单起见，这里讨论　元组在２维空间下Ｇｒｉｄ的性质．２维Ｇｒｉｄ也可以扩　展到　维空间，具体方法参考文献［１］．　给定一个不确定数据库Ｄ　，先将其数据标准　化，再根据值维度信息将其映射到对应的单元格　（ｃｅｌ１）中．每个单元格对角线长度为ｕｄ／Ｚ的正方形，　单元格按其所在行列位置标记为Ｇ　，存放映射到　该单元格内的元组ＩＤ．以Ｇ　为中心向周围扩展ｍ　层所得单元格的集合标记为Ｇｍ　．如图３所示，节点　ｔ所在的阴影区域为Ｇ　即Ｇ　，　本身，全部阴影区　域是Ｇ　图３中所有单元格组成Ｇ　基于Ｇｒｉｄ的　划分有如下性质：对Ｖ　∈Ｇ　，Ｒ（ｔ）∈Ｇ　．，且Ｇ　∈　Ｒ（￡），则在寻找Ｒ（￡）时，只需对所有ｔ　∈Ｇ　　．—Ｇ　．，　进行遍历，而不需要遍历整个Ｄ　．　７　／　一——～　＼　／　＼。　∈　＼　／　／、　Ｆｉｇ．３　Ｇｒｉｄ—ｂａｓｅｄ　ｓｐａｃｅ　ｐａｒｔｉｔｉｏｎ．　图３基于Ｇｒｉｄ的空间划分　３．３　基于过滤的离群点检测基本算法ｂ—ＲＦＡ　基于上述过滤原理，在检测元组ｔ时，若在其　Ｒ（￡）中找不到元组Ｒ（￡）［力，使得Ｔ一｛Ｒ（￡）［ｏ３，…，　Ｒ（　）［　］）中至少发生是个元组的概率大于　，那么ｔ　就是离群点；否则，就可以找到以　为圆心、ｕｄ－ｄｉｓｔ　（　，Ｒ（　）［　］）为半径的过滤区域０　（￡），所有位于＠　（　）中的元组不必检测．本文首先设计了基于过滤的　基本算法ｂａｓｉｃ—ＲＦＡ（ｂ—ＲＦＡ）．该算法的基本描述　如下：对待检测的不确定数据库Ｄ　中的每个元组　设置标记；设置指针ｉ指向当前检测元组．　１）初始化阶段：初始化Ｄ　中所有元组标记为　ｕｎｐｒｕｎｅｄ；指针ｉ指向Ｄｕ首元组．　２）检测阶段：依据参数ｕｄ，找到ｔ　的Ｒ（ｔ　），　４７８　对Ｒ（ｔ　）中的元组按与ｔ　的距离升序排序，若找到　元组Ｒ（　）［力，使得Ｒ（　）Ｅｏ－Ｉ，…，Ｒ（￡）ＥＪ３中至少发　生ｋ个元组的概率大于　，ｔ　就不是离群点，找到　＠ｐ（￡　），对＠　（￡　）中所有元组的标记设为ｐｒｕｎｅｄ；否　则ｔ　就是离群点，设ｔ　的标记为ｏｕｔｌｉｅｒ．寻找下一　个标记为ｕｎｐｒｕｎｅｄ的元组继续按上述方法检测，直　到所有元组的标记都不为ｕｎｐｒｕｎｅｄ．　ｂ—ＲＦＡ算法的执行过程简单，寻找过滤区域的　过程受到元组的位置分布和元组概率的影响．　３．４基于过滤的离群点检测改进算法ｏ－ＲＦＡ　若Ｄｕ中产生多个过滤区域＠ｐ（￡　），…＠　（ｆ　），　且它们不完全重合，则可以进一步减少检测点数量．　多个过滤区域的最理想分布是　达到最小，同时多　个过滤区域覆盖的总面积最大．可以对Ｄ　的每个　元组逐一检测，计算相应的过滤区域，综合考虑各个　过滤区域的组合情形，最后得到一个最优解．但是，　逐点检测后Ｄ　的检测结果已经得出，寻求最优过　滤区域覆盖已毫无意义．因此，只能寻求一个尽可能　优化的方法寻找过滤区域．要得到一个好的过滤区　域分布，就要使单个过滤区域有尽可能大的面积，同　时使多个过滤区域的重叠面积尽可能小．　由定理２可知，影响单个过滤区域面积的因素　为表达式　—　（￡）的值，　为常量，因此ｎ（ｆ）值　越大过滤区域越小，反之过滤区域越大越受元组的　位置分布和概率的影响．以参数为Ｄ　，ｕｐ，ｕｄ，　，且　厂　］　ｋ—Ｉ（１一ｕｐ）×ｌ　Ｄ　ｌ　１—３的查询为例加以说明．　　１ｌ　１）元组具有同概率分布，不同位置分布时对过　滤区域面积的影响．　如图４（ａ）所示，在元组ｔ　的检测过程中，假设　在其Ｒ（ｔ。）内距离ｔ　最近的５个元组ｔ。，ｔ　，…，ｔ　Ｆｉｇ．４　Ｅｆｆｅｃｔ　ｏｎ　ｆｉｌｔｅｒｉｎｇ　ｒｅｇｉｏｎｓ　ｗｈｅｎ　ｔｕｐｌｅｓ　ｈａｖｅ　ｔｈｅ　ｓａｍｅ　ｐｒｏｂａｂｉｌｉｔｙ　ｂｕｔ　ｄｉｆｆｅｒｅｎｔ　ｐｏｓｉｔｉｏｎ　ｄｉｓｔｒｉｂｕｔｉｏｎ．（ａ）　Ｌｏｎｇｅｒ　ｄｉｓｔａｎｃｅ　ｂｅｔｗｅｅｎ　ｔｕｐｌｅｓ　ａｎｄ（ｂ）Ｓｈｏｒｔｅｒ　ｄｉｓｔａｎｃｅ　ｂｅｔｗｅｅｎ　ｔｕｐｌｅｓ．　图４具有相同概率值不同位置分布的元组对过滤区域　的影响．（ａ）元组间距离较远；（ｂ）元组间距离较近　计算机研究与发展２０１０，４７（３）　中至少发生３个的概率刚好大于　，确定过滤区域　＠ｐ（　１），其半径为ｒｐ（￡１）一ｕｄ—ｒａ（ｔ　）；如图４（ｂ）所　示，若保持各元组的概率值不变，而各元组向ｔ　有　不同程度的靠近，可确定新的过滤区域＠：（ｔ。），其　半径为ｒ：（￡　）一“　—ｒ：（ｆ１）．由于　（￡　）≥ｒ　（　１），因　此可得ｒ　（　）≤ｒ：（ｔ　）．在元组概率相同的情况下，　元组分布越密单个过滤区域的面积越大．　２）元组具有相同位置分布，不同概率分布时对　过滤区域面积的影响．　继续使用上述查询条件，并设　一０．３．Ｒ（　）包　含表３中的５个元组，其中各个元组的概率如表３　所示．如图５（ａ）所示，在对ｔ　的检测中，当１＂Ａ—ｄｉｓｔ　（￡　，ｔ　）时，　（￡　）至少发生３个元组的概率为０．３８６，　大于　，可得到过滤区域＠　（ｔ　），其半径ｒ　（ｔ　）一　ｕｄ—ｒ】（ｔ】）．　Ｔａｂｌｅ　３　Ｏｒｉｇｉｎａｌ　Ｐｒｏｂａｂｉｌｉｔｙ　ｏｆ　Ｔｕｐｌｅｓ　表３修改前的元组概率　Ｔｕｐｌｅ　Ｐｒｏｂａｂｉｌｉｔｙ　（ｂ）　Ｆｉｇ．５　Ｅｆｆｅｃｔ　ｏｎ　ｆｉｌｔｅｒｉｎｇ　ｒｅｇｉｏｎｓ　ｗｈｅｎ　ｔｕｐｌｅｓ　ｈａｖｅ　ｄｉｆｆｅｒｅｎｔ　ｐｒｏｂａｂｉｌｉｔｉｅｓ　ｂｕｔ　ｔｈｅ　ｓａｍｅ　ｐｏｓｉｔｉｏｎ　ｄｉｓｔｒｉｂｕｔｉｏｎ．　（ａ）Ｌａｒｇｅｒ　ｐｒｏｂａｂｉｌｉｔｉｅｓ　ｏｆ　ｔｕｐｌｅｓ　ａｎｄ（ｂ）Ｓｍａｌｌｅｒ　ｐｒｏｂａｂｉｌｉｔｉｅｓ　ｏｆ　ｔｕｐｌｅｓ．　图５具有不同概率分值相同位置分布的元组对过滤区　域的影响．（ａ）元组概率值较大；（ｂ）元组概率值较小　保持各个元组的位置分布不变，修改个别元组　的概率，如表４所示．再次计算得，在ｄｉｓｔ（ｔ　，ｔ　）范　围内，至少发生３个元组的概率为０．２４，小于　．因　此必须扩展求解范围，如图５（ｂ）所示，在ｄｉｓｔ（ｔ　，　ｔ　）范围内，至少发生３个元组的概率为０．３５１，大于　．这时可得到＠　（　），其半径ｒ　（ｔ　）＝＝：ｕｄ—ｒ：（￡　）．　由于　（￡　）＜ｒ：（￡　），所以新的过滤区域要小．在元组　位置不变时元组概率越高，单个过滤区域面积越大．　于浩等：基于距离的不确定离群点检测　Ｔａｂｌｅ　４　Ｍｏｄｉｆｉｅｄ　Ｐｒｏｂａｂｉｌｉｔｙ　ｏｆ　Ｔｕｐｌｅｓ　表４修改后的元组概率　ｏ．５　Ｏ．４　ｏ．４　ｏ．５　ｏ．３　由以上讨论可知，如果以Ｇｒｉｄ中每个单元格提　供的元组密度和概率分布信息为依据，优先处理包　含较多元组且其中元组的概率较大的单元格，则将　有利于提高离群点检测的效率．然而，如果过滤区域　之间的重叠较大，总体的检测效率仍将不高．因此，　为了获得良好的效率，一方面既需要提高单个过滤　区域的面积，另一方面还需要尽可能地减少过滤区　域之间的重叠．　算法１．ｏ—ＲＦＡ算法描述．　输入：不确定数据库Ｄ　；　参数ｕｄ，ｕｐ，　；　输出：（ｕｄ，ｕｐ，　）一离群点．　①将Ｄ　加载到集合Ｔ中，将Ｔ中的每个元组　标记为ｕｎｐｒｕｎｅｄ，并将其映射到格Ｇ中；　厂　－１　②ｋ一｝（１～ｕｐ）ｘ　Ｊ　Ｄｕ　Ｊ）ｆ；结果集Ｒ一　；　Ｉ　ｆ　③初始化一个空的队列Ｑ；　④ｆｏｒ　Ｇ中的每个单元Ｇ　ｄｏ　⑤　ｉｆ　Ｇ　中没有元组ｔｈｅｎ　⑥　将Ｇ　标记为ｅｍｐｔｙ；　⑦　ｅｌｓｅ将Ｇ　标记为ｒａｗ；　ｅｎｄ　ｉｆ　ｅｎｄ　ｆｏｒ　⑧ｗｈｉｌｅ存在被标记为ｒａｗ的单元ｄ０　⑨　从Ｇ中获得下一个单元Ｇ　；　⑩ｐｕｓｈ（Ｑ，Ｇ　，）；　⑩　ｗｈｉｌｅ　Ｑ．ｅｍｐｔｙ！一Ｔｒｕｅ　ｄｏ　⑥　Ｇ　一ｔｏｐ（Ｑ）；ｐｏｐ（Ｑ）；　⑩　ｆｏｒ　Ｇ　中的每个元组ｔ，ｄｏ　⑩　计算ｔ，的邻居Ｒ（￡，）；　⑩　根据Ｒ（ｔ，）中每个点到ｔ，的距离为这　些点排序；　⑩　ｒｐ（ｔｊ）一　—ＤＰＡ（Ｒ（￡，），ｋ，　）；　⑥　ｉｆ　ｒ　（　）＞ｕｄ　ｔｈｅｎ　⑩　将ｔ，存入离群点集合Ｒ；　４７９　⑩　ｅｌｓｅ　⑩　将　（　）内的元组标记为ｐｒｕｎｅｄ；　⑨　将Ｒ　（￡　）内的单元标记为ｄｏｎｅ；　③　将ｔ，和Ｒ　（￡，）插入队列Ｑ；　ｅｎｄ　ｉｆ　ｅｎｄ　ｆｏｒ　⑧　将单元Ｇ，，标记为ｄｏｎｅ；　⑨　ｗｈｉｌｅ　ｔｏｐ（Ｑ）被标记为ｄｏｎｅ　ｄｏ　⑤ｐｏｐ（Ｑ）；　ｅｎｄ　ｗｈｉｌｅ　ｅｎｄ　ｗｈｉｌｅ　ｅｎｄ　ｗｈｉｌｅ　④ｒｅｔｕｒｎ　Ｒ．　假设在某一某元组附近的元组位置排列和概率　分布变化不大，则其附近元组的过滤区域的大小都　很接近，这样有利于提高过滤效率．　基于以上讨论，本文提出了启发式的ｏｒｄｅｒ—　ＲＦＡ算法（ｏ—ＲＦＡ），从２方面提高离群点检测的效　率．在提高单个过滤区域面积方面，为综合考虑元组　位置分布和概率分布这２个因素，ｏ—ＲＦＡ采取了一　种折中的方法：以所含元组概率之和作为单元格的　优先级，优先处理元组概率之和大的单元格（通过优　先队列实现）．在减小过滤区域重叠方面，在处理某　个单元格中的元组时，ｏ—ＲＦＡ根据其过滤区域的半　径，找到如图５所示的６个距离它√３　ｒ口（￡）的虚拟点　（该点所在位置不一定有元组）所在的单元格，并将　这些单元格（如果位于分布区域内，非空且未处理）　插入优先对列中，作为此后选择下一个要处理的单　元格时的候选．当单元格内的元组都处理完毕后，ｏ—　ＲＦＡ则从优先队列中选取优先级最大的单元格进　行处理．　ｏ—ＲＦＡ以所有单元格中所含元组概率之和最　大的单元格为起点，通过优先队列控制算法的路线，　依次处理队列中的单元格．当队列为空、但尚有非空　单元格未被处理时，则从剩余的单元格中选择概率　之和最大的单元格作为新的起点，继续处理余下的　单元格，直到所有的非空单元格都被处理完毕．　４高效概率计算方法ＤＰＡ　第３节提出的２种过滤算法都涉及对单个元组　ｔ的检测，其核心环节即求解ｔ的邻居元组集Ｒ（ｆ）　中至少发生　个元组的概率，这是一个组合事件的概　率求解，基本方法是找到符合要求的所有事件组合，　４８０　然后计算概率．该方法的事件复杂度为０（２　“　Ｉ），在　Ｉ　Ｒ（￡）１较大时是不可忍受的．本文找到了该组合事件　的等价事件及求解其概率的高效方法，即高效概率计　算方法ＤＰＡ，具有线形的时问复杂度Ｏ（ｋ　ｌＲ（￡）Ｊ）．　本节首先介绍等价事件的构造，然后说明其概率的　求解方法．　令Ｒ一｛ｔ。，ｔ。，…，ｔ　），Ｒ中元组可不排序，但保　持元组之间的先后顺序不变；对Ｖｔｊ∈Ｒ，其左集合　Ｓｊ　ｆ　一｛ｔｌ，…，ｔ卜】），右集合Ｓ”ｉｇｈ　＝｛ｔ，＋ｌ，…，ｔ　｝．　表５为问题表述用到的符号、表达式及其含义．可　见对元组ｔ的检测即求解事件ＥＲ（ｔ），ｋ］的概率　Ｐ（［Ｒ（￡），忌］）．　Ｔａｂｌｅ　５　Ｓｙｍｂｏｌｓ　ａｎｄ　Ｎｏｔａｔｉｏｎｓ　表５符号与描述　［Ｒ，愚］　Ａｔ　ｌｅａｓｔ　ｔｕｐｌｅｓ　ａｐｐｅａｒｉｎｇ　ｉｎ　Ｒ　（Ｒ・矗＞　Ｏｎｌｙ　ｔｕｐｌｅｓ　ａｐｐｅａｒｉｎｇ　ｉｎ　Ｒ　●　Ｅｖｅｎｔ　ｐｒｏｄｕｃｔ　∑　Ｅｖｅｎｔ　ｓｕｍｍａｔｉｏｎ　当ｋ＞ＩＲ（　）Ｉ时，显然［Ｒ，忌］为不可能事件，　Ｐ（ＥＲ（￡），忌］）一０，ｔ为离群点．　当忌≤ＩＲ（　）ｌ时，至少存在一个可能世界实例　Ｗ，且ｌ　Ｗ　Ｉ≥忌．构造如下事件：将ｔ　作为枢轴元组，　ＳＨ出发生且仅发生ｋ一１个元组，ｔ　自身一定发生，　Ｓｎ础　可随意发生．这样就表示了一个在ｔ，发生的条　件下Ｒ（　）中至少发生ｋ个元组的事件：　＜Ｓｊ－ｌｅ“，ｋ一１＞・ｔ　・Ｅｓｊ　ｇｈ　，Ｏ］（ＣＥ（　Ｊ）），　称该事件为构造事件ＣＥ（ｔ，），通过对构造事件的研　究，得到如下性质：　‘　性质１．［Ｒ（￡），是］与构造事件的和事件是等价　的，即　ｌＲ（ｆ）ｌ　［　），ｋ－１一∑＜ｓ　ｅｆｔ，是一１＞・ｔｊ・Ｅｓ　Ｉｇｈ　，０］．　Ｊ：１　证明．设任意事件ｃ∈［Ｒ（　），愚］，Ｃ中发生的元　组数量为ｚ，可以找到ｔｊ∈Ｒ（￡），使：　ｃ一＜Ｓ，’ｌｅｆｆ＇ｋ一１＞・ｔ，・＜￣ｊ－，ｉｇｈ　，ｌ一是＞．　由于＜ｓ九。ｇｈ　，ｚ一是＞∈［ｓ　。　ｈ　，Ｏ］，因此可得：　ｃ∈∑＜＝１　ｓ川ｅｆｔ，ｋ一１＞・ｔ　・Ｅｓ州ｇｈ　，０］，　ｌＲ（ｆ）Ｉ　￣ｌＪＥＲ（ｔ），志］　∑＜ＳＪ　ｆｌ，　一１＞・ｔｊ・［ｓ　ｈｌ，０］．　对事件集合Ｃ一＜５Ｊ　ｈ，是一１＞・ｔｊ・Ｅｓ　。　ｈＩ，０］，　如果．ｆ＜　，ｃ为空集；若　≥　，Ｃ就表示了一个在ｔ　计算机研究与发展２０１０，４７（３）　发生条件下事件集合［Ｒ（￡），是］的子事件集合，那么　Ｃ　［Ｒ（￡），忌］，因此可以得到：　ｌＲ（｝）　∑＜Ｊ＝１　ｓ川ｅｆｔ，ｋ一１＞・ｔ　・Ｅｓ　Ｉｇｈ　，０］　ＥＲ（ｔ），　综上可得：　Ｒ（ｆ）ｌ　（　），最］一∑＜ｓ川ｅｆｔ，ｋ一１＞　．［ｓｎＩｇｈ　，０］．　Ｊ＝１　证毕．　从等价事件集合＜ｓＪ＿１ｅｆｉ’ｋ一１＞・ｔｊ・［Ｓｎ　ｈｒ，０］　的构造方式上还可以看出，无论遍历元组的顺序如　何，最后的复和事件都将是ＥＲ（￡），愚］．通过进一步　考查可以得出：当　＜志时，＜ＳＨ出，ｋ一１＞是不可能发　生的．因此可得：　・　ｌＲ（ｆ）ｊ　ＥＲ（ｔ），志］　∑＜ｓ　，ｋ一１＞・￡　．［ｓ　蛳，ｏ］．　Ｊ＝　性质２．各构造事件＜Ｓ川　ｆｌ，愚一１＞・ｔ　・ＦＳｊ．ｒｉｇｈ　０］之间的关系是互斥关系，其中Ｊ≥是，即对于　－≠　Ｊｚ，ＣＥ（ｔ　）与ＣＥ（ｔ　，）是互斥的，其中　≥志且　ｚ≥　ｋ．　证明．设］　＞　≥惫，使得ＣＥ（ｔｉ．）与ＣＥ（ｔ　）　同时发生．由于Ｒ（￡）中所有元组保持顺序不变，则　有（Ｓ　ｌｅｆｔ　Ｕ　ｔｉ１）　Ｓ　ｌ　ｆ【’由于＜Ｓｉ１　ｆＩ，ｋ一１＞与ｔｉ１要　同时发生，这将导致Ｓ　有至少愚个元组发生，这　与＜Ｓ　。　ｋ一１＞的定义是矛盾的，ＣＥ（ｔ　）与ＣＥ　（￡　）同时发生不成立，因此两者是互斥的．　证毕．　基于性质１，２，得到求解［尺（￡），矗］概率的公式：　ｆＲ（ｆ）ｌ　Ｐ（ＥＲ（ｔ），志］）一∑Ｐ（＜Ｓｊ－ｌｅｆｔ）志一１＞・　Ｊ一１　ｔ　・［Ｓ／　，０］）．　由于各个元组问相互独立，可得：　Ｐ（ＣＥ（ｔ，））一Ｐ（＜Ｓ　ｆｆ’ｋ一１＞）×　Ｐ（ｃＪ）ｘ　Ｐ（［Ｓｊ－ｒｉｇｈｆ’０］），　［ｓ　。　，０］是必然事件，Ｐ（［Ｓｊ　ｒｉｇｈ　，ｏ］）一１，因此可得　Ｐ（ＣＥ（ｔ　））一Ｐ（＜Ｓ　Ｉ　ｆ　，ｋ一１＞）×Ｐ（ｔｊ），　Ｐ（＜ｓ¨　，足＞）存在如下递推性质：　ｆＰ（＜Ｓ（，＿１）＿ｌ　，ｋ一１＞）尸（　）＋　ｌ　一　一　＿｛ｌ　１，　（　Ｓ　ｅｆｔ一　一ＯＡ　ｋ　；）　　１０，（Ｉ　ｓ　ｌ＜矗）　由此可得当愚≤ｌＲ（　）Ｉ时Ｐ（ＥＲ（ｔ），忌］）的求解公式：　Ｐ（ＥＲ（ｔ），忌］）一∑Ｐ（＜ｓ川　，ｋ一１＞）×Ｐ（ｔ　）．　（２）　于　浩等：基于距离的不确定离群点检测　４８１　若ｌ　Ｒ（￡）ｌ＜ｋ该算法返回一１，否则，顺序处理　Ｒ（￡）中的元组ｔ，，每计算出一个Ｐ（ＣＥ（ｔ，））值就累　加到ＳｕｍＰｒｏｂ中，若ＳｕｍＰｒｏｂ＞　，算法终止，返回　ｔ与ｔ，间的距离；否则，按上述方式继续处理．若访　５．１离群点参数影响　本节中所使用的二维实验数据集分布如图６所　示，不确定数据点个数为１０００００．定义中３个参数　的选择决定了离群点定义的严格程度（即离群点的　问Ｒ（　）中所有元组后ＳｕｍＰｒｏｂ仍小于　，返回一１．　个数），从而影响了各算法的运行时间．　这一算法称为ＤＰＡ（ｄｙｎａｍｉｃ　ｐｒｏｇｒａｍｍｉｎｇ　ａｐｐｒｏａｃｈ）．　计算Ｐ（［Ｒ（￡），ｋ３）的复杂度为Ｏ（ｋｎ），较排列组合方法　近于０（２　）的复杂度要好很多，其中ｌＲ（￡）１一　．　需要说明的是，本文中ＤＰＡ方法作为过滤算　法的辅助算法使用．实际上ＤＰＡ是针对单个元组　进行检测的方法，依次对Ｄ　中每个元组ｔ找到Ｒ　（　）后使用ＤＰＡ是可以完成对整个数据库的检测　的，本文称这种方法为ＢＡ（ｂａｓｉｃ　ａｐｐｒｏａｃｈ），实验中　将此方法同过滤算法做比较，这里不加赘述．　ｏ　２００　４００　６００　８００　１０００　５　实验分析　Ｆｉｇ．６　Ｄａｔａ　ｄｉｓｔｒｉｂｕｔｉｏｎ．　啪　咖　伽　瑚　图６数据集分布　由于尚无针对基于距离的不确定离群点检测的　图７（ａ）反映了参数ｕｐ（０．９９９０～０．９９９９）对算　研究，无法同已有方法进行对比，只能在本文提出的　法运行时间的影响．随着ｕｐ的增大ｋ值增大，离群　不同方法间进行比较．本文实验计划从（ｕｐ，ｕｄ，　）一　点数量大幅减少（从２２３９９减少到１９９５），因而所有　离群点参数影响、可扩展性２个方面进行．实验中使　算法的运行时问都大幅度减少．由于未采用过滤技　用的二维数据集总体上服从一定分布函数，数据使　术，ＢＡ的运行时间远多于另外２种算法．除此之　用Ｍａｔｌａｂ生成，它们分布在长１０００、宽１０００的固　外，对于ｂ—ＲＦＡ与。一ＲＦＡ而言，ｕｐ的增大还将导　定矩形区域中，根据不同的实验需求采用不同分布；　致非离群点的过滤圆半径增大，从而提高过滤性能，　各数据点的可信度值（取值范围为Ｏ～１．０）总体上服　进一步减少算法的运行时间．如图７（ｂ）所示，ｂ—　从均匀分布．全部实验采用Ｃ＋＋语言编写，所测得　ＲＦＡ和。一ＲＦＡ的被过滤数据点数量随着ｕｐ的增　的算法运行时间为１０次重复测试所得结果的平均　大而大幅度增加．此外，由于采用了启发式的策略，　值，参数ｕｐ，ｕｄ，　的默认值分别为０．９９９６，２０，０．７．　ｏ～ＲＦＡ的效率略高于ｂ—ＲＦＡ．　ｕｄ＝２０，　＝０．７，ｏｕｔｌｉｅｒ：２２３９９￣１９９５　ｕｄ＝２０，五：０．７，ｏｕｔｌｉｅｒ：２２３９９￣１９９５　ｋ　ｋ　（ａ）　（ｂ）　Ｆｉｇ．７　Ｔｅｓｔ　ｗｈｅｎ　ｖａｒｙｉｎｇ　ｕｐ．（ａ）Ｒｕｎｎｉｎｇ　ｔｉｍｅ　ａｎｄ（ｂ）Ｎｕｍｂｅｒ　ｏｆ　ｐｒｕｎｅｄ　ｔｕｐｌｅｓ　图７参数“ｐ的测试．（ａ）运行时间；（ｂ）被过滤的数据量　图８（ａ）反映了ＢＡ，ｂ—ＲＦＡ和。一ＲＦＡ的运行时　下，得益于有效的过滤技术，ｂ－ＲＦＡ与。一ＲＦＡ的运　间随着参数ｕｄ增大（１０～３０）的变化情况．ｕｄ增大　行时间则小得多．并且，当　增大时，非离群点的　时数据点的邻居大量增加，导致花费在离群点上的　过滤圆半径也随之增大，因而过滤性能得以提高（如　计算量增大．由于没有采用过滤技术，ＢＡ的总体运　图８（ｂ）所示，被过滤的数据点大量增加），花费在非　行时间快速增加，并且远大于其他２种算法．相比之　离群点上的计算量大幅减小，从而导致算法的总体　曲ｐＪ０　４８２　计算机研究与发展２０１０，４７（３）　运行时间反而逐渐降低．此外，ｏ—ＲＦＡ由于采用了　使用，ｂ—ＲＦＡ与０一ＲＦＡ的运行时间远小于ＢＡ的运　启发式的元组处理次序，因而具有略高于ｂ—ＲＦＡ的　行时间．此外，　变大时非ｏｕｔｌｉｅｒ的过滤圆半径随　效率．　∞＼警　１＿　ｕ１ｕｕｎ　之减小，因而过滤性能下降（如图９（ｂ）所示，被过滤　∞＼∞ｇ　ａ—ｉ　图９（ａ）反映了参数　（Ｏ．１ｔＯ．９）对算法运行时　的数据点逐渐减少），导致了ｂ—ＲＦＡ和Ｏ—ＲＦＡ运行　间的影响．当　增大时离群点逐渐增加，所有算法的　时间的增加．同样，ｏ—ＲＦＡ的效率略高于ｂ－ＲＦＡ的　运行时间都呈现逐渐增大的趋势．由于过滤技术的　效率．　０．９９９６，　＝０．７，ｏｕｔｌｉｅｒ：３４８６４～３６１３　ＰＵ＝Ｏ．９９９６．　＝０．７．ｏｕｔｌｉｅｒ：３４８６４－３６１３　ｕｄ　叽ｐｊ０。　ｐａ写　×　０＿【　∞ｐＪ００　Ｈ（ｂ）　　星　×　０＿【　Ｆｉｇ．８　Ｔｅｓｔ　ｗｈｅｎ　ｖａｒｙｉｎｇ　ｕｄ．（ａ）Ｒｕｎｎｉｎｇ　ｔｉｍｅ　ａｎｄ（ｂ）Ｎｕｍｂｅｒ　ｏｆ　ｐｒｕｎｅｄ　ｔｕｐｌｅｓ　图８参数　的测试．（ａ）运行时间；（ｂ）被过滤的数据量　ｕｄ＝２０，ｕｐ＝０．９９９６，ｏｕｔｌｉｅｒ：７８０８～１００３１　Ｆｉｇ．９　Ｔｅｓｔ　ｗｈｅｎ　ｖａｒｙｉｎｇ　Ａ．（ａ）Ｒｕｎｎｉｎｇ　ｔｉｍｅ　ａｎｄ（ｂ）Ｎｕｍｂｅｒ　ｏｆ　ｐｒｕｎｅｄ　ｔｕｐｌｅｓ　图９参数　的测试．（ａ）运行时间；（ｂ）被过滤的数据量　５．２可扩展性　二维的均匀分布（如图８所示）与二维正态分布（如　良好的可扩展性是指当改变数据规模或数据分　图９所示），不确定数据点个数的变化范围分别为　布时算法仍然可以保持优良的性能．本节分别使用　６００００　１５００００与６００００　１２００００，对本文３种检测　ｕｄ＝２０，ｐｕ＝Ｏ．９９９６，　＝０．７，ｏｕｔｌｉｅｒ：１６６９～３２１５　（ａ）　（ｂ）　Ｆｉｇ．１０　Ｔｅｓｔ　ｆｏｒ　ｕｎｉｆｏｒｍ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｗｈｅｎ　ｖａｒｙｉｎｇ　ｎｕｍｂｅｒ　ｏｆ　ｔｕｐｌｅｓ．（ａ）Ｒｕｎｎｉｎｇ　ｔｉｍｅ　ａｎｄ　（ｂ）Ｎｕｍｂｅｒ　ｏｆ　ｐｒｕｎｅｄ　ｔｕｐｌｅｓ．　图ｌ０均匀分布下变化元组数的测试．（ａ）运；ｒ时间；（ｂ）被过滤的数据量　于浩等：基于距离的不确定离群点检测　４８３　算法进行可扩展性测试．　外，如图１０（ｂ）和图１１（ｂ）所示，随着数据量增大，ｂ—　图１０（ａ）和图１１（ａ）分别展现了在均匀分布与　ＲＦＡ和。一ＲＦＡ中被过滤数据点的数量也迅速增　．正态分布的数据集上３种算法的运行时间随着数据　∞＼ｕｇＩｌ　ＩＩ—ｕｕｎ　大，从而导致它们的运行时间增长得比ＢＡ慢很多，　点数量增加的变化情况．当数据点增多时３种算法　因而具有更好的可扩展性．此外，从图１Ｏ和图１ｌ还　的运行时间都逐渐增加．然而，由于过滤技术的使　可以看出，在均匀分布和正态分布的情况下，ｏ—ＲＦＡ　用，ｂ—ＲＦＡ和。一ＲＦＡ的运行时间较ＢＡ小得多．此　都具有比ｂ—ＲＦＡ更好的效率．　ｕｄ＝２０，　＝０．９９９６，　ｕｄ＝２０，ｕｐ＝０．９９９６，　＝０．７．ｏｕｔｌｉｅｒ：５３３２～１０４５４　＝０．７．ｏｕｔｌｉｅｒ：５３３２～１０４５４　１２Ｏ　８Ｏ　４０　Ｏ　６０　７０　８Ｏ　９Ｏ　１００　１１０　１２０　１０—０ｘＮｕｍｂｅｒ　ｏｆＲｅｃｏｒｄ　１０一。×Ｎｕｍｂｅｒ　ｏｆＲｅｃｏｒｄ　∞ｐＪ００　ｑ箬已　×　０＿【　（ａ）　（ｂ）　Ｆｉｇ．１　１　Ｔｅｓｔ　ｆｏｒ　ｎｏｒｍａｌ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｗｈｅｎ　ｖａｒｙｉｎｇ　ｎｕｍｂｅｒ　ｏｆ　ｔｕｐｌｅｓ．（ａ）Ｒｕｎｎｉｎｇ　ｔｉｍｅ；ａｎｄ　（ｂ）Ｎｕｍｂｅｒ　ｏｆ　ｐｒｕｎｅｄ　ｔｕｐｌｅｓ．　图１１　正态分布下变化元组数的测试．（ａ）运行时间；（ｂ）被过滤的数据量　［４］　Ｂａｒｎｅｔｔ　Ｖ，Ｌｅｗｉｓ　Ｔ．Ｏｕｔｌｉｅｒｓ　ｉｎ　Ｓｔａｔｉｓｔｉｃａｌ　Ｄａｔａ［Ｍ］．Ｎｅｗ　６结论及未来工作　Ｙｏｒｋ：Ｊｏｈｎ　Ｗｉｌｅｙ　ａｎｄ　Ｓｏｎｓ，１９９４　Ｅ５］Ｂｒｅｕｎｉｎｇ　Ｍ　Ｍ，Ｋｒｉｅｇｅｌ　Ｈ　Ｐ，Ｎｇ　Ｒ　Ｔ，ｅｔ　ａ１．ＬＯＦ：　Ｉｄｅｎｔｉｆｙｉｎｇ　ｄｅｎｓｉｔｙ—ｂａｓｅｄ　ｌｏｃａｌ　ｏｕｔｌｉｅｒｓ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＡＣＭ　不确定数据的离群点检测是一个新兴的研究领　ＳＩＧＭ０Ｄ　２０００．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ，２０００：９３－１０４　域，其价值将在广泛的应用领域中得到重视．本文针　［６］Ｔｕｋｅｙ　Ｊ　Ｗ．Ｅｘｐｌｏｒａｔｏｒｙ　Ｄａｔａ　Ａｎａｌｙｓｉｓ［Ｍ］．Ｒｅａｄｉｎｇ，ＭＡ：　对不缺定性数据的离群点检测提出了新的定义，并　Ａｄｄｉｓｏｎ—Ｗｅｓｌｅｙ　ａｎｄ　Ｓｏｎｓ，１９９４　提出高效的过滤方法ｂ—ＲＦＡ与。一ＲＦＡ及概率计算　［７］Ａｒｎｉｎｇ　Ａ，Ａｇｒａｗａｌ　Ｒ，Ｒａｇｈａｖａｎ　Ｐ．Ａ　ｌｉｎｅａｒ　ｍｅｔｈｏｄ　ｆｏｒ　ｄｅｖｉａｔｉｏｎ　ｄｅｔｅｃｔｉｏｎ　ｉｎ　ｌａｒｇｅ　ｄａｔａｂａｓｅｓ［ｃ］Ｉ／Ｐｒｏｃ　ｏｆ　ＫＤＤ．　方法ＤＰＡ．并通过实验证明检测方法具有高效性和　Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ，１９９６：１６４—１６９　良好的可扩展性．　［８］　Ｓａｒａｗａｇｉ　Ｓ，Ａｇｒａｗａｌ　Ｒ，Ｍｅｇｉｄｄｏ　Ｎ．Ｄｉｓｃｏｖｅｒｙ—ｄｒｉｖｅｎ　未来工作包括支持更复杂的不确定数据模型，　ｅｘｐｌｏｒａｔｉｏｎ　ｏｆ　ＯＬＡＰ　ｄａｔａ　ｃｕｂｅｓ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＥＤＢＴ．　Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，１９９８：１６８—１８２　如具有互斥关系的不确定数据的检测、基于密度和　［９］Ｊａｇａｄｉｓｈ　Ｈ　Ｖ，Ｋｏｕｄａｓ　Ｎ，Ｍｕｔｈｕｋｒｉｓｈｎａｎ　Ｓ．Ｍｉｎｉｎｇ　统计的不确定数据离群点检测等．　ｄｅｖｉａｎｔｓ　ｉｎ　ａ　ｔｉｍｅ　ｓｅｒｉｅｓ　ｄａｔａｂａｓｅｓ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＶＬＤＢ．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ：Ｍｏｒｇａｎ　Ｋａｎｆｍａｎｎ，１９９９：１０２—１１３　参　考　文　献　［１０］Ｐｅｉ　Ｊ，Ｊｉａｎｇ　Ｂ，Ｌｉｎ　ｘ　Ｍ，ｅｔ　ａ１．Ｐｒｏｂａｂｉｌｉｓｔｉｃ　ｓｋｙｌｉｎｅｓ　ｏｎ　ｕｎｃｅｒｔａｉｎ　ｄａｔａ［Ｃ］／［Ｐｒｏｃ　ｏｆ　ＶＬＤＢ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ，　２００７：１５－２６　［１］　Ｋｎｏｒｒ　Ｅ　Ｍ，Ｎｇ　Ｒ　Ｔ．Ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｍｉｎｉｎｇ　ｄｉｓｔａｎｃｅ　ｂａｓｅｄ　［１１］Ｋｒｉｅｇｅｌ　Ｈ，Ｐｆｅｉｆｌｅ　Ｍ．Ｄｅｎｓｉｔｙ　ｂａｓｅｄ　ｃｌｕｓｔｅｒｉｎｇ　ｏｆ　ｕｎｃｅｒｔａｉｎ　ｏｕｔｌｉｅｒｓ　ｉｎ　ｌａｒｇｅ　ｄａｔａｓｅｔｓ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＶＬＤＢ．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ：　ｄａｔａ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＫＤＤ．Ｃｈｉｃａｇｏ，ＵＳＡ：ＡＭＣ，２００５：６７２—　Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ，１９９８：３９２—４０３　６７７　Ｅ２］　Ｋｎｏｒｒ　Ｅ　Ｍ，Ｎｇ　Ｒ　Ｔ．Ｆｉｎｄｉｎｇ　ｉｎｔｅｎｓｉｏｎａｌ　ｋｎｏｗｌｅｄｇｅ　ｏｆ　［１２］Ｓｏｌｉｍａｎ　Ｍ　Ａ，Ｉｌｙａｓ　Ｉ　Ｆ，Ｃｈａｎｇ　Ｋ　Ｃ．Ｔｏｐ—ｋ　ｑｕｅｒｙ　ｐｒｏｃｅｓｓｉｎｇ　ｄｉｓｔａｎｃｅ　ｂａｓｅｄ　ｏｕｔｌｉｅｒｓ［ｃ］ＨＰｒｏｃ　ｏｆ　ＶＩ　ＤＢ．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ：　ｉｎ　ｕｎｃｅｒｔａｉｎ　ｄａｔａｂａｓｅｓ［ｃ］／［Ｐｒｏｃ　ｏｆ　ＩＣＤＥ．Ａｔｌａｎｔａ，ＵＳＡ：　Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ，１９９９：２１１　２２２　ＳＩＡＭ，２００７：３４５－３６０　［３］　Ｎｉ　Ｗｅｉｗｅｉ，Ｃｈｅｎ　Ｇｅｎｇ，Ｉ　ｕ　Ｊｉｅｐｉｎｇ，ｅｔ　ａ１．Ｌｏｃａｌ　ｅｎｔｒｏｐｙ　ｂａｓｅｄ　ｗｅｉｇｈｔｅｄ　ｓｕｂｓｐａｃｅ　ｏｕｔｌｉｅｒ　ｍｉｎｉｎｇ　ａｌｇｏｒｉｔｈｍｓ［Ｊ］．　［１３］Ｍｉｎｇ　Ｈ，Ｊｉａｎ　Ｐ，Ｚｈａｎｇ　Ｗ　Ｊ，ｅｔ　ａ１．Ｒａｎｋｉｎｇ　ｑｕｅｒｉｅｓ　ｏｎ　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｒｅｓｅａｒｃｈ　Ｄｅｖｅｌｏｐｍｅｎｔ，２００８，４５（７）：　ｕｎｃｅｒｔａｉｎ　ｄａｔａ：Ａ　ｐｒｏｂａｂｉｌｉｓｔｉｃ　ｔｈｒｅｓｈｏｌｄ　ａｐｐｒｏａｃｈ［Ｃ］／／Ｐｒｏｃ　１１８９—１１９４（ｉｎ　Ｃｈｉｎｅｓｅ）　ｏｆ　ＡＣＭ　ＳＩＧＭＯＤ　２００８．Ｃｈｉｃａｇｏ，ＵＳＡ：ＡＭＣ，２００８：６７３—　（倪巍伟，陈耿，陆介平，等．基于局部信息熵的加权子空间　６８９　离群点检测算法［Ｊ］．计算机研究与发展，２００８，４５（７）：　［１４］Ａｇｇａｒｗａｌ　Ｃ　Ｃ，Ｙｕ　Ｐ　Ｓ．Ｏｕｔｌｉｅｒ　ｄｅｔｅｃｔｉｏｎ　ｗｉｔｈ　ｕｎｃｅｒｔａｉｎ　ｄａｔａ　１１８９－１１９４）　［ｃ］／／Ｐｒｏｃ　ｏｆ　ＳＤＭ．Ａｔｌａｎｔａ，ＵＳＡ：ＳＩＡＭ，２００８：４８３—４９３　４８４　计算机研究与发展２０１０，４７（３）　Ｎｏｒｔｈｅａｓｔｅｒｎ　Ｕｎｉｖｅｒｓｉｔｙ．Ｈｉｓ　ｃｕｒｒｅｎｔ　ｒｅｓｅａｒｃｈ　ｉｎｔｅｒｅｓｔｓ　ｉｎｃｌｕｄｅ　ｕｎｃｅｒｔａｉｎ　ｄａｔａ　ａｎｄ　ｏｕｔｌｉｅｒ　ｄｅｔｅｃｔｉｏｎ　ｉｎ　ｔｈｅ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋ．　ｓｅｎｉｏｒ　ｍｅｍｂｅｒ　ｏｆ　Ｃｈｉｎａ　Ｃｏｍｐｕｔｅｒ　Ｆｅｄｅｒａｔｉｏｎ．　杨晓春，１９７３年生，教授，博士生导师，中国计算机学会高级　会员，主要研究方向为数据库理论与技术、数据质量分析．　王斌，１９８４年生，硕士研究生，主要研究方向为不确定数　据管理和无线传感器网络中的异常检测．　Ｒｅｓｅａｒｃｈ　Ｂａｃｋｇｒｏｕｎｄ　Ｏｕｔｌｉｅｒ　ｄｅｔｅｃｔｉｏｎ　ｉｓ　ｏｎｅ　ｏｆ　ｔｈｅ　ｖａｌｕａｂｌｅ　ｔｅｃｈｎｉｑｕｅｓ　ｉｎ　ｍａｎｙ　ａｐｐｌｉｃａｔｉｏｎｓ，ｓｕｃｈ　ａｓ　ｎｅｔｗｏｒｋ　ｉｎｔｒｕｓｉｏｎ　ｄｅｔｅｃｔｉｏｎ，ｅｖｅｎｔ　ｄｅｔｅｃｔｉｏｎ　ｉｎ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋ（ＷＳＮ），ａｎｄ　ＳＯ　ｏｎ．Ｔｈｉｓ　ｔｅｃｈｎｉｑｕｅ　ｈａｓ　ｂｅｅｎ　ｗｅｌｌ　ｓｔｕｄｉｅｄ　ｏｎ　ｄｅｔｅｒｍｉｎｉｓｔｉｃ　ｄａｔａｂａｓｅｓ．　Ｈｏｗｅｖｅｒ，ｉｔ　ｉｓ　ａ　ｎｅｗ　ｔａｓｋ　ｏｎ　ｅｍｅｒｇｉｎｇ　ｕｎｃｅｒｔａｉｎ　ｄａｔａｂａｓｅ．Ｕｓｉｎｇ　ｔｈｅ　ｎｅｗ　ｕｎｃｅｒｔａｉｎ　ｄａｔａ　ｍｏｄｅｌ，ｍａｎｙ　ｒｅａｌ　ａｐｐｌｉｃａｔｉｏｎｓ，ｓｕｃｈ　ａｓ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋ，ｄａｔａ　ｉｎｔｅｇｒａｔｉｏｎ，ａｎｄ　ｄａｔａ　ｍｉｎｉｎｇ，ｃａｎ　ｂｅ　ｂｅｔｔｅｒ　ｄｅｓｃｒｉｂｅｄ．Ｔｈｅ　ｆｅａｓｉｂｉｌｉｔｙ　ｏｆ　ｓｕｃｈ　ａｐｐｌｉｃａｔｉｏｎｓ　ｃａｎ　ｂｅ　ｆｕｒｔｈｅｒ　ｅｎｈａｎｃｅｄ．Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ａ　ｎｅｗ　ｄｅｆｉｎｉｔｉｏｎ　ｏｆ　ｏｕｔｌｉｅｒ　ｏｎ　ｕｎｃｅｒｔａｉｎ　ｄａｔａ　ｉｓ　ｄｅｆｉｎｅｄ．Ｂａｓｅｄ　ｏｎ　ｉｔ，ｓｏｍｅ　ｅｆｆｉｃｉｅｎｔ　ｆｉｌｔｅｒｉｎｇ　ａｐｐｒｏａｃｈｅｓ　ｆｏｒ　ｏｕｔｌｉｅｒ　ｄｅｔｅｃｔｉｏｎ　ａｒｅ　ｐｒｏｐｏｓｅｄ，ｉｎｃｌｕｄｉｎｇ　３　ｂａｓｉｃ　ｆｉｌｔｅｒｉｎｇ　ａｐｐｒｏａｃｈ，ｃａｌｌｅｄ　ｂ—ＲＦＡ，ａｎｄ　ａｎ　ｉｍｐｒｏｖｅｄ　ｆｉｌｔｅｒｉｎｇ　ａｐｐｒｏａｃｈ，ｃａｌｌｅｄ　Ｏ－ＲＦＡ．Ｍｏｒｅｏｖｅｒ，ａ　ｐｒｏｂａｂｉｌｉｔｙ　ａｐｐｒｏａｃｈ，ｃａｌｌｅｄ　ＤＰＡ，ｉｓ　ｐｒｏｐｏｓｅｄ　ｔＯ　ｅｆｆｉｃｉｅｎｔｌｙ　ｄｅｔｅｃｔ　ｏｕｔｌｉｅｒ　ｏｎ　ｕｎｃｅｒｔａｉｎ　ｄａｔａｂａｓｅ．Ｔｈｅ　ａｐｐｒｏａｃｈ　ｂ－ＲＦＡ　ｕｔｉｌｉｚｅｓ　ｔｈｅ　ｐｒｏｐｅｒｔｙ　ｏｆ　ｎｏｎ—ｏｕｔｌｉｅｒ　ｔｏ　ｒｅｄｕｃｅ　ｔｈｅ　ｔｉｍｅｓ　ｏｆ　ｄｅｔｅｃｔｉｏｎ．Ｍｏｒｅｏｖｅｒ，Ｏ－ＲＦＡ　ｉｍｐｒｏｖｅｓ　一　一＿　‰一一．ｌ～曼　～一～一一～～一一　埘一　～　　嘶～一．　～一～一～一　～～一一～　ｂ　ＲＦＡ　ｂｙ　ｍｉｎｉｎｇ　ａｎｄ　ｕｓｉｎｇ　ｔｈｅ　ｄａｔａ　ｄｉｓｔｒｉｂｕｔｉｏｎ．Ｆｕｒｔｈｅｒｍｏｒｅ，ＤＰＡ　ｆｉｎｄｓ　ｔｈｅ　ｒｅｃｕｒｓｉｏｎ　ｒｕｌｅ　ｉｎ　ｐｒｏｂａｂｉｌｉｔｙ　ｃｏｍｐｕｔａｔｉｏｎ　ａｎｄ　ｇｒｅａｔｌｙ　ｉｍｐｒｏｖｅｓ　ｔｈｅ　ｅｆｆｉｃｉｅｎｃｙ　ｏｆ　ｓｉｎｇｌｅ　ｄａｔａ　ｄｅｔｅｃｔｉｏｎ．Ｏｕｒ　ｗｏｒｋ　ｉｓ　ｓｕｐｐｏｒｔｅｄ　ｂｙ　ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｃｈｉｎａ（Ｎｏｓ．６０８２８００４，６０９７３０２０），ｔｈｅ　Ｐｒｏｇｒａｍ　ｆｏｒ　Ｎｅｗ　Ｃｅｎｔｕｒｙ　Ｅｘｃｅｌｌｅｎｔ　Ｔａｌｅｎｔｓ　ｉｎ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎｏ．ＮＣＥＴ　０６—０２９０），ａｎｄ　ｔｈｅ　Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ｋｎｏｗｌｅｄｇｅ　Ｅｎｇｉｎｅｅｒｉｎｇ　ｆｏｒ　ｔｈｅ　Ｍｉｎｉｓｔｒｙ　ｏｆ　Ｅｄｕｃａｔｉｏｎ，Ｒｅｎｍｉｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｃｈｉｎａ　（ＮＯ．２００８００２）．