基于密度的Top-n局部异常点快速检测算法

局部异常检测（Local outlier factor,LOF）能够有效解决数据倾斜分布下的异常检测问题,在很多应用领域具有较好的异常检测效果.本文面向大数据异常检测,提出了一种快速的Top-n局部异常点检测算法MTLOF（Multi-granularity upper bound pruning based top-n LOF detection）,融合索引结构和多层LOF上界设计了多粒度的剪枝策略,以快速发现Top-n局部异常点.首先,提出了四个更接近真实LOF值的上界,以避免直接计算LOF值,并对它们的计算复杂度进行了理论分析;其次,结合索引结构和UB₁、UB₂上界,提出了两层的Cell剪枝策略,不仅采用全局Cell剪枝策略,还引入了基于Cell内部数据对象分布的局部剪枝策略,有效解决了高密度区域的剪枝问题;再次,利用所提的UB₃和UB₄上界,提出了两个更加合理有效的数据对象剪枝策略,UB₃和UB₄上界更加接近于真实LOF值,有利于剪枝更多数据对象,而基于计算复用的上界计算方法,大大降低了计算成本;最后,优化了初始Top-n局部异常点的选择方法,利用区域划分和建立的索引结构,在数据稀疏区域选择初始局部异常点,有利于将LOF值较大的数据对象选为初始局部异常点,有效提升初始剪枝临界值,使得初始阶段剪枝掉更多的数据对象,进一步提高检测效率.在六个真实数据集上的综合实验评估验证MTLOF算法的高效性和可扩展性,相比最新的TOLF（Top-n LOF）算法,时间效率提升可高达3.5倍.     

基于k-核过滤的社交网络影响最大化算法

针对现有社交网络影响最大化算法影响范围小和时间复杂度高的问题,提出一种基于独立级联模型的k-核过滤算法。首先,介绍了一种节点影响力排名不依赖于整个网络的现有影响力最大化算法;然后,通过预训练k,找到对现有算法具有最佳优化效果且与选择种子数无关的k值;最后,通过计算图的k-核过滤不属于k-核子图的节点和边,在k-核子图上执行现有影响最大化算法,达到降低计算复杂度的目的。为验证k-核过滤算法对不同算法有不同的优化效果,在不同规模数据集上进行了实验。结果显示,应用k-核过滤算法后：与原PMIA算法相比,影响范围最多扩大13.89%,执行时间最多缩短8.34%;与原核覆盖算法（CCA）相比,影响范围没有太大差异,但执行时间最多缩短28.5%;与OutDegree算法相比,影响范围最多扩大21.81%,执行时间最多缩短26.96%;与Random算法相比,影响范围最多扩大71.99%,执行时间最多缩短24.21%。进一步提出了一种新的影响最大化算法GIMS,它比PMIA和IRIE的影响范围更大,执行时间保持在秒级别,而且GIMS算法的k-核过滤算法与原GIMS算法的影响范围和执行时间差异不大。实验结果表明,k-核过滤算法能够增大现有算法选择种子节点集合的影响范围,并且减少执行时间;GIMS算法具有更好的影响范围效果和执行效率,并且更加鲁棒。     

基于局部密度的快速离群点检测算法

已有的密度离群点检测算法LOF不能适应数据分布异常情况离群点检测,INFLO算法虽引入反向k近邻点集有效地解决了数据分布异常情况的离群点检测问题,但存在需要对所有数据点不加区分地分析其k近邻和反向k近邻点集导致的效率降低问题。针对该问题,提出局部密度离群点检测算法--LDBO,引入强k近邻点和弱k近邻点概念,通过分析邻近数据点的离群相关性,对数据点区别对待;并提出数据点离群性预判断策略,尽可能避免不必要的反向k近邻分析,有效提高数据分布异常情况离群点检测算法的效率。理论分析和实验结果表明,LDBO算法效率优于INFLO,算法是有效可行的。     

iLOF*:一种改进的局部异常检测算法

异常检测是数据挖掘领域研究的基本问题之一,已被广泛应用于气象预报、网络入侵检测、电信和信用卡欺诈侦察等领域.基于密度的异常检测算法LOF具有较好的检测效果和适用性,但其计算量较大,运行效率不够高,且在进行对象之间的距离计算时忽略了不同属性对异常值的不同影响.针对以上不足,本文提出了一种高效的LOF改进算法iLOF^*.该算法利用网格进行数据约简,从而提高了算法的运行效率;同时,在进行对象之间的距离计算时,引入信息熵,给不同属性赋予不同的权值,从而提高了算法的准确率.另外,用MapReduce计算框架将iLOF^*算法并行化,进一步提高了算法在大规模数据集上的运行效率.最后的实验结果验证了iLOF^*算法的有效性和高效性.     

基于数据场的改进LOF算法

LOF（Local Outlier Factor）是一种经典基于密度的局部离群点检测算法，为提高算法的精确度，以便更精准挖掘出局部离群点，在LOF算法的基础上，提出了一种基于数据场的改进LOF离群点检测算法。通过对数据集每一维的属性值应用数据场理论，计算势值，进而引入平均势差的概念，针对每一维度中大于平均势差的任意两点在计算距离时加入一个权值，从而提高离群点检测的精确度，实验结果表明该算法是可行的，并且拥有更高的精确度。     

工业过程数据异常检测的改进局部离群因子法

局部离群因子(LOF)是对过程数据的局部离群程度的定义,然而工业过程对数据异常检测的实时性要求高,要求出所有采样点的离群因子计算量较大。故本文对LOF算法进行相应的改进,采用k-近邻计算对象的局部可达密度,同时利用1种预处理采样点的方法CDC(Closest Distance to Center),通过计算每个点到中心点的距离先对采样点进行修剪,剔除大部分不可能是离群点的采样点,只需要计算剩余点改进的LOF值,从而提高离群点检测的效率。最终通过对TE过程数据仿真,说明在保证离群点检测准确性的情况下,相比于LOF缩短了算法运行的时间。     

基于Hadoop的局部异常检测算法

为了提高局部异常检测算法的检测效率以及检测的准确度,提出基于Hadoop的分布式局部异常检测算法MRDINFLO。该算法在INFLuenced Outlierness(INFLO)算法的基础上,引入了MapReduce计算框架,将数据点的k近邻、k距离、反向k近邻、局部离群因子的计算并行化处理,从而提高了检测效率。算法在计算各个数据对象之间的距离时采用加权距离,通过引入信息熵来判断离群属性,给离群属性以较大的权重,从而提高了异常检测的准确度。实验在3节点Hadoop集群上进行,输入数据为KDD-CUP 99。当输入数据集大小为500万条时,所提出的MR-DINFLO算法检测准确度为0. 94,检测时间为2 589 s。实验结果表明该算法具有高效可行性。     

散乱点云的自适应α-shape曲面重建

针对α-shape算法不适用于散乱非均匀点集曲面重建的问题,提出了一种基于点云数据局部特征尺寸（LFS）的自适应α-shape曲面重建改进算法。首先,以采样点的k-邻近点计算出负极点逼近曲面中轴（MA）;然后,根据近似中轴计算曲面在采样点处的局部特征尺寸,并依据局部特征尺寸对原始点云进行非均匀降采样;最后,根据三角面片的外接球半径和对应的α值自适应重建出物体表面。与α-shape算法相比,所提算法可以有效合理地减少点云数据量,点云简化率达到70%左右,同时重建结果中冗余三角面片更少且基本没有孔洞。实验结果表明,所提算法能够自适应地重建出非均匀点集的表面。     

结合局部敏感哈希的k近邻数据填补算法

k近邻(kNN)算法是缺失数据填补的常用算法,但由于需要逐个计算所有记录对之间的相似度,因此其填补耗时较高。为提高算法效率,提出结合局部敏感哈希(LSH)的kNN数据填补算法LSH-kNN。首先,对不存在缺失的完整记录进行局部敏感哈希,为之后查找近似最近邻提供索引;其次,针对枚举型、数值型以及混合型缺失数据分别提出对应的局部敏感哈希方法,对每一条待填补的不完整记录进行局部敏感哈希,按得到的哈希值找到与其疑似相似的候选记录;最后在候选记录中通过逐个计算相似度来找到其中相似程度最高的k条记录,并按照kNN算法对不完整记录进行填补。通过在4个真实数据集上的实验表明,结合局部敏感哈希的kNN填补算法LSH-kNN相对经典的kNN算法能够显著提高填补效率,并且保持准确性基本不变。     

基于B-list的快速频繁模式挖掘算法

针对现有的频繁模式挖掘算法存在建树复杂、挖掘效率低等问题,提出一种基于构造链表（B-list）的频繁模式挖掘（BLFPM）算法。BLFPM使用一种新的数据结构B-list表示频繁项集,通过连接两个k-1-频繁项集的B-list可以快速得到k-项集的支持度,避免了多次扫描数据库;针对连接两个B-list时间复杂度高的问题,给出了一种线性时间复杂度的连接方法,提高了BLFPM的时间效率;同时,BLFPM采用集合枚举树代表搜索空间,并使用子集非频繁剪枝策略,减小了频繁模式挖掘的搜索空间,提高了算法的执行速度。实验结果表明,与NSFI算法和prepost算法相比,BLFPM的时间效率提高约12%到29%,空间效率提高约10%到24%,对稀疏数据库或稠密数据库进行频繁模式挖掘均可以得到良好的效果。     

基于iForest和LOF的流量异常检测

异常检测在现代大规模分布式系统的安全管理中起着重要作用,而网络流量异常检测则是组成异常检测系统的重要工具。网络流量异常检测的目的是找到和大多数流量数据不同的流量,并将这些离群点视为异常。由于现有的基于树分离的孤立森林（iForest）检测方法存在不能检测出局部异常的缺陷,为了克服这个缺陷,提出一种基于iForest和局部离群因子（LOF）近邻集成的无监督的流量异常检测方法。首先,改进原始的iForest与LOF算法,在提升检测精度的同时控制算法时间;然后分别使用两种改进算法进行检测,并将结果进行融合以得到最终的检测结果;最后在自制数据集上对所提方法进行有效性验证。实验结果表明,所提方法能够有效地隔离出异常,获得良好的流量异常检测效果。     

基于网格查询的局部离群点检测算法

针对基于密度的局部离群因子算法（LOF），需要计算距离矩阵来进行[k]近邻查寻，算法时间复杂度高，不适合大规模数据集检测的问题，提出基于网格查询的局部离群点检测算法。算法利用距离目标网格中的数据点最近的[k]个其他数据点，一定在该目标网格或在该目标网格的最近邻接网格中这一特性，来改进LOF算法的邻域查询操作，以此减少LOF算法在邻域查询时的计算量。实验结果证明，提出的LOGD算法在与原LOF算法具有基本相同的检测准确率的情况下，能够有效地降低离群点检测的时间。     

使用均值距离与关联性标记的并行OPTICS算法

针对大数据环境下传统并行密度聚类算法中存在的数据划分不合理,聚类结果准确度不高,结果受参数影响较大以及并行效率低等问题,提出一种MapReduce下使用均值距离与关联性标记的并行OPTICS算法——POMDRM-MR。算法使用一种基于维度稀疏度的减少边界点划分策略（DS-PRBP）,划分数据集;针对各个分区,提出标记点排序识别簇算法（MOPTICS）,构建数据点与核心点之间的关联性,并标记数据点迭代次数,在距离度量中,使用领域均值距离策略（FMD）,计算数据点的领域均值距离,代替可达距离排序,输出关联性标记序列;最后结合重排序序列提取簇算法（REC）,对输出序列进行二次排序并提取簇,提高算法局部聚类的准确性和稳定性;在合并全局簇时,算法提出边界密度筛选策略（BD-FLC）,计算筛选密度相近局部簇;又基于n叉树的并集型合并与MapReduce模型,提出并行局部簇合并算法（MCNT-MR）,加快局部簇收敛,并行合并局部簇,提升全局簇合并效率。对照实验表明,POMDRM-MR算法聚类效果更佳,且在大规模数据集下算法的并行化性能更好。     

基于密度的不确定数据离群点检测研究

针对不确定数据集进行离群点检测,设计了基于密度的不确定数据的局部离群因子(Uncertain Local Outlier Factor,ULOF)算法.通过建立不确定数据的可能世界模型来确定不确定对象在可能世界中的概率.结合传统的LOF算法推导出ULOF算法,根据ULOF值判断不确定对象的局部离群程度;然后对ULOF算法的效率性和准确性进行了详细分析,提出了基于网格的剪枝策略、k最近邻查询优化来减少数据的候选集;最后通过实验证明了ULOF算法对不确定数据检测的可行性和效率性,优化后的方法有效地提高了异常检测准确率,降低了时间复杂度,改善了不确定数据的异常检测性能.     

一种基于邻域系统密度差异度量的离群点检测算法

针对离群点检测算法LOF在高维离散分布数据集中检测精度较低及参数敏感性较高的问题,提出了基于邻域系统密度差异度量的离群点检测NSD（neighborhood system density difference）算法。相较于传统基于密度的离群点检测方法,NSD算法引入了截取距离的概念。首先计算数据集中对象在截取距离内的邻居点个数;其次计算对象的邻域系统密度;然后将对象的密度与它邻居的密度进行比较,判定目标对象与其邻居趋向于同一簇的程度;最后输出最可能是离群点的对象。将NSD算法与LOF、LDOF、CBOF算法在真实数据集与合成数据集中对比实验发现,NSD算法具有较高的检测准确率和执行效率以及较低的参数敏感性,证明了NSD算法是有效可行的。     

一种云环境下的高效异常检测策略研究

针对虚拟机进行异常检测是提高云计算系统可靠性的重要手段之一。然而,云环境中虚拟机的性能指标数据具有维度高、信息冗余等特点,会降低检测效率和准确度。同时,传统异常检测方法难以定量刻画系统的异常状态,而局部异常因子(Local Outlier Factor,LOF)算法虽可量化其异常程度,但它以相同权重计算不同维度变量对系统状态的影响,导致算法对异常的区分能力减弱。针对以上问题,提出一种高效的异常检测策略。该策略以最大相关最小冗余算法和主成分分析法对性能指标进行筛选降维,提高了异常检测的效率;为LOF算法中不同维度的变量赋予不同权重,强化了不同指标对异常的区分度。实验表明,该策略相对于传统异常检测方法,效率和检测率都有显著提高。     

基于Isolation Forest的并行化异常探测设计

异常探测具有广泛的应用,受到了工业界和学术界的共同关注。在众多异常探测方法中,Isolation Forest算法具有执行效率高、探测准确度好的特点,获得了众多应用。但是,传统Isolation Forest算法难以处理大规模数据。为解决此问题,设计了一种基于云计算平台的算法。具体地,使用Hadoop分布式存储系统和MapReduce分布式计算框架设计并实现了基于Isolation Forest的并行化异常探测算法PIFH。通过将探测模型构建和数据异常评价的过程并行化,提升了PIFH算法探测异常的执行效率,扩展了其应用范围。利用真实世界数据集验证了所提算法的执行效率和可扩展性。