田 盼,华 蓓,陆 李

(中国科学技术大学计算机科学与技术学院,合肥230027)

基于GPU的K-近邻算法实现

田 盼,华 蓓,陆 李

(中国科学技术大学计算机科学与技术学院,合肥230027)

K-近邻计算在数据集规模较大时计算复杂度较高,因此,利用图形处理器(GPU)强大的并行计算能力对K-近邻算法进行加速。在分析现有K-近邻算法的基础上,针对该算法时间开销过大的问题,结合GPU的体系结构特征实现基于GPU的K-近邻算法。利用全局存储器的合并访问特性,提高GPU全局存储器访问数据的效率,通过事先过滤数据的方法来减少参与排序的数据量,进而减少排序阶段的线程串行化时间。在KDD,Poker, Covertype 3个数据集上进行实验,结果表明,该实现方法在距离计算阶段每秒执行的浮点运算次数为266.37×109次,而排序阶段为26.47×109次,优于已有方法。

K-近邻问题;图形处理器;并行计算;算法加速;合并访问;全局存储器

1 概述

异常检测是指发现系统或用户偏离常规的行为。异常检测在信用卡欺诈[1]、网络入侵[2]、系统故障检测[3]等方面具有广泛应用。通常将正常的行为特征存储在数据库中,然后将当前行为特征与数据库中的行为特征进行比较,当两者偏差足够大时判断发生了异常。局部异常因子(Local Outlier Factor,LOF)[4]算法是目前应用最广泛的离群点检测算法,它通过计算每个对象相对于其邻域的孤立情况(局部离群因子)来判断对象是否为离群点,进而判定是否异常。然而LOF算法的计算复杂度很高,其中,最耗时的操作是计算每个对象的k个最近邻居[5]。……