基于gpu的lof算法加速

《基于gpu的lof算法加速》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中国科学技术大学硕士学位论文基于GPU的LOF算法加速作者姓名．t学科专业：导师姓名：完成时间：田盼计算机系统结构华蓓教授二。一四年四月二十二日UniversityofScienceandTechnologyofChinaAdissertationformaster’SdegreeAccelerationofLOFAlgorithmonGPUAuthor’SName：PanTianSpeciality：Supervisor：Finishedtime：ComputerArchitectureProf．BeiHuaA

2、pril22小，2014拜您pl￥．3-．2-l中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明a作者签名：i刎签字日期：净雒。豳幺群橇中国科学技术大学学位论文授权使用声明作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件

3、和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。}m开口保密(年)作者签名：≤圣碰签字日期：兰壁：丛：爿摘要异常检测是指发现系统或用户偏离常规的行为，在信用卡欺诈、网络入侵、系统故障检测等方面有着广泛的应用。异常检测通常将正常的行为特征存储在数据库中，然后将当前行为特征与数据库中的行为特征进行比较，当两者偏差足够大时判断发生了异常。用于异常检测的方法很多，

4、LOF(LocalOutlierFactor)算法通过计算测试实例的LOF值来判断其是否异常，由于检测率高而得到广泛的应用。然而，LOF算法的计算复杂度很高，其中时间开销最大的操作是kNN计算。在数据规模很大时，LOF算法的时间开销限制了它在低延迟应用中的使用。虽然有很多工作对LOF算法以及kNN算法进行了多种方式的优化，但这些优化方法在数据规模很大或数据维度很高时都存在复杂度太高的问题。近年来，GPU已经发展为包含成百上千个计算单元、具有强大计算能力的众核处理器。GPU统一架构及CUDA(ComputeUnif

5、iedDeviceArchitecture)的出现极大地方便了GPU的编程工作，使得GPU的应用领域从最初的图形图像渲染很快扩展到通用计算领域。目前已有一些工作使用GPU来加速异常检测领域的算法，其中就有针对LOF算法以及kNN算法的并行化工作。但这些工作都没有充分利用GPU的体系结构特点，LOF算法和kNN算法在GPU上还有很大的优化空间。本文研究基于GPU的LOF算法高效实现，重点研究时间开销最大的kNN算法的高效实现。本文将kNN计算分为距离计算和k．近邻查找两个步骤，分别进行优化。对于距离计算，本文重新定

6、义了数据实例的数据结构以及存储方式，并充分利用全局存储器的合并访问特性来提高访存效率。对于k．近邻查找，本文通过距离过滤减少需要参与排序的距离值，减少了线程串行化排序的执行时间。基于高效的kNN实现，本文在CPU．GPU平台上实现了LOF算法的并行加速。本文在真实的数据集上对基于GPU的kNN算法实现及LOF算法实现进行了实验评估，并与其它同类实现进行了比较。实验表明本文实现比已有同类实现有显著的性能提升。关键词：异常检测，LOF算法，kNN算法，GPU，并行优化摘要IIAbstractAnomalydetect

7、ionistofindthosedeviantonesfrombehaviorsofsystemoruser,whichhasbeenusedinawiderangeofapplicationssuchas，creditcardfrauddetection，networkintrusiondetection，systemfaultdetectionandSOon．Themethodusedgenerallyinanomalydetectionistostorethenormalbehavioralcharacte

8、risticsintothedatabase，andthencomparethebehaviorcharacteristicsofcurrentinstanceandthoseinthedatabase．Ifthedeviationislargeenough，thecurrentinstancewillbedeterminedasanexception．Therearea