基于GPU的LOF算法加速.pdf

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

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

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

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