基于GPU的LOF算法加速.pdf

1、異常檢測是指發(fā)現(xiàn)系統(tǒng)或用戶偏離常規(guī)的行為，在信用卡欺詐、網(wǎng)絡(luò)入侵、系統(tǒng)故障檢測等方面有著廣泛的應(yīng)用。異常檢測通常將正常的行為特征存儲在數(shù)據(jù)庫中，然后將當(dāng)前行為特征與數(shù)據(jù)庫中的行為特征進(jìn)行比較，當(dāng)兩者偏差足夠大時判斷發(fā)生了異常。
　　用于異常檢測的方法很多，LOF(Local Outlier Factor)算法通過計(jì)算測試實(shí)例的LOF值來判斷其是否異常，由于檢測率高而得到廣泛的應(yīng)用。然而，LOF算法的計(jì)算復(fù)雜度很高，其中時間開銷最大

2、的操作是kNN計(jì)算。在數(shù)據(jù)規(guī)模很大時，LOF算法的時間開銷限制了它在低延遲應(yīng)用中的使用。雖然有很多工作對LOF算法以及kNN算法進(jìn)行了多種方式的優(yōu)化，但這些優(yōu)化方法在數(shù)據(jù)規(guī)模很大或數(shù)據(jù)維度很高時都存在復(fù)雜度太高的問題。
　　近年來，GPU已經(jīng)發(fā)展為包含成百上千個計(jì)算單元、具有強(qiáng)大計(jì)算能力的眾核處理器。GPU統(tǒng)一架構(gòu)及CUDA（Compute Unified Device Architecture）的出現(xiàn)極大地方便了GPU的編程工作

3、，使得GPU的應(yīng)用領(lǐng)域從最初的圖形圖像渲染很快擴(kuò)展到通用計(jì)算領(lǐng)域。目前已有一些工作使用GPU來加速異常檢測領(lǐng)域的算法，其中就有針對LOF算法以及kNN算法的并行化工作。但這些工作都沒有充分利用GPU的體系結(jié)構(gòu)特點(diǎn)，LOF算法和kNN算法在GPU上還有很大的優(yōu)化空間。
　　本文研究基于GPU的LOF算法高效實(shí)現(xiàn)，重點(diǎn)研究時間開銷最大的kNN算法的高效實(shí)現(xiàn)。本文將kNN計(jì)算分為距離計(jì)算和k-近鄰查找兩個步驟，分別進(jìn)行優(yōu)化。對于距離計(jì)算

4、，本文重新定義了數(shù)據(jù)實(shí)例的數(shù)據(jù)結(jié)構(gòu)以及存儲方式，并充分利用全局存儲器的合并訪問特性來提高訪存效率。對于k-近鄰查找，本文通過距離過濾減少需要參與排序的距離值，減少了線程串行化排序的執(zhí)行時間。基于高效的kNN實(shí)現(xiàn)，本文在CPU-GPU平臺上實(shí)現(xiàn)了LOF算法的并行加速。
　　本文在真實(shí)的數(shù)據(jù)集上對基于GPU的kNN算法實(shí)現(xiàn)及LOF算法實(shí)現(xiàn)進(jìn)行了實(shí)驗(yàn)評估，并與其它同類實(shí)現(xiàn)進(jìn)行了比較。實(shí)驗(yàn)表明本文實(shí)現(xiàn)比已有同類實(shí)現(xiàn)有顯著的性能提升。