戴春娥，陳維斌，傅順開，李志強

DAI Chun’e,CHEN Weibin,FU Shunkai,LI Zhiqiang

華僑大學 計算機科學與技術(shù)學院，福建 廈門361021

College of Computer Science and Technology,Huaqiao University,Xiamen,Fujian 361021,China

1 引言

數(shù)據(jù)挖掘是一個從大量歷史數(shù)據(jù)中發(fā)現(xiàn)有趣模式的過程[1]，目前已經(jīng)應用在商務智能、Web 搜索、金融、數(shù)字圖書館等領域。數(shù)據(jù)挖掘?qū)ι鐣哂泻艽笥绊懀⑶椅磥磉@種影響將繼續(xù)。隨著信息技術(shù)和互聯(lián)網(wǎng)的快速發(fā)展，各領域收集的數(shù)據(jù)規(guī)模已經(jīng)達到TB 甚至PB 量級，這對計算速度提出了嚴峻挑戰(zhàn)。

GPU（Graphics Processing Unit）是相對于CPU 的一個概念，伴隨著多媒體計算需求的迅猛增長而被意識到，并最終成為一個獨立于傳統(tǒng)CPU 的處理器。如今，GPU 已經(jīng)不再局限于3D 圖形處理了，GPU 通用計算技術(shù)發(fā)展已經(jīng)引起業(yè)界不少的關(guān)注，事實也證明在浮點運算、并行計算等部分計算方面，GPU 可以提供數(shù)十倍乃至上百倍于CPU 的性能。相比CPU 而言，GPU 有以下特點[2-3]：（l）GPU 通常具有更大的內(nèi)存帶寬；（2）GPU 具有更多的執(zhí)行單元；（3）GPU 較同等級的CPU 具有價格優(yōu)勢?；贕PU 高性能和性價比等優(yōu)勢，現(xiàn)在GPU 的應用已經(jīng)擴展到了圖形領域之外的范圍內(nèi)，如數(shù)值天氣預報[4]，地質(zhì)勘探[5]、代數(shù)計算[6-7]、分子動力學模擬[8]、數(shù)據(jù)庫操作[9]等。

本文首先介紹GPU 特性和主流編程模型，隨后著重介紹已有的通過GPU 加速經(jīng)典數(shù)據(jù)挖掘算法的工作，包括聚類、分類、關(guān)聯(lián)分析、時序分析以及當下熱門的深度學習，并討論適合于GPU 加速數(shù)據(jù)挖掘算法的特征。最后，分別基于CPU 和GPU 實現(xiàn)協(xié)同過濾算法，通過大規(guī)模實驗比較和驗證GPU 對加速數(shù)據(jù)挖掘傳統(tǒng)算法的效果和效率，為未來進一步深入研究奠定基礎。

2 基于GPU 的計算和編程

2.1 GPU

GPU 之所以在某些應用中較CPU 能夠獲得更高的性能，主要是因為GPU 和CPU 在硬件結(jié)構(gòu)設計上存在很大差異。如圖1 所示[10]，GPU 將大量的晶體管用作ALU 計算單元，從而適應密集且可并行的圖像渲染計算處理需要。相對GPU 而言，CPU 卻是將更多的晶體管用作復雜的控制單元和緩存等非計算功能，并以此來提高少量執(zhí)行單元的執(zhí)行效率。

圖1 CPU 與GPU 中晶體管的使用情況

此外，存儲帶寬是另一個重要問題。存儲器到處理器的帶寬已經(jīng)成為許多應用程序的瓶頸。目前GPU 的芯片帶寬是CPU 芯片帶寬的6 倍左右[11]。

2.2 CPU/GPU 協(xié)同并行計算

在諸多適用于高性能計算的體系結(jié)構(gòu)中，采用通用多核CPU 與定制加速協(xié)處理器相結(jié)合的異構(gòu)體系結(jié)構(gòu)成為構(gòu)造千萬億次計算機系統(tǒng)的一種可行途徑。而在眾多異構(gòu)混合平臺中，基于CPU/GPU 異構(gòu)協(xié)同的計算平臺具有很大的發(fā)展?jié)摿ΑＴ趨f(xié)同并行計算時，CPU 和GPU 應各取所長，即CPU 承擔程序控制，而密集計算交由GPU 完成。另外，除管理和調(diào)度GPU 計算任務外，CPU 也應當承擔一部分科學計算任務[12]。

新型異構(gòu)混合體系結(jié)構(gòu)對大規(guī)模并行算法研究提出了新的挑戰(zhàn)，迫切需要深入研究與該體系結(jié)構(gòu)相適應的并行算法。事實上，目前基于GPU 加速的數(shù)據(jù)挖掘算法實現(xiàn)都有CPU 參與協(xié)同計算，只是討論的重點多集中在為適應GPU 而進行的并行化設計上。實踐中，需要找出密集計算部分并將其遷移到GPU 中執(zhí)行，剩余部分仍然由CPU 來完成。

2.3 CUDA

為了加速GPU通用計算的發(fā)展，NVIDIA公司在2007年推出統(tǒng)一計算設備架構(gòu)（Compute Unified Device Architecture，CUDA）[10，13]。CUDA 編程模型將CPU 作為主機，GPU 作為協(xié)處理器，兩者協(xié)同工作，各司其職。CPU 負責進行邏輯性強的事務處理和串行計算，GPU則專注于執(zhí)行高度線程化的并行處理任務。CUDA 采用單指令多線程（SIMT）執(zhí)行模式，而內(nèi)核函數(shù)（kernel）執(zhí)行GPU 上的并行計算任務，是整個程序中一個可以被并行執(zhí)行的步驟。CUDA 計算流程通常包含CPU 到GPU 數(shù)據(jù)傳遞、內(nèi)核函數(shù)執(zhí)行、GPU 到CPU 數(shù)據(jù)傳遞三個步驟。

CUDA 不需要借助于圖形學API，并采用了比較容易掌握的類C/C++語言進行開發(fā)，為開發(fā)人員有效利用GPU 的強大性能提供了條件。CUDA 被廣泛應用于石油勘探、天文計算、流體力學模擬、分子動力學仿真、生物計算和圖像處理等領域，在很多應用中獲得了幾倍、幾十倍，乃至上百倍的加速比[13]。

2.4 并行編程語言和模型

過去幾十年里，人們相繼提出了很多并行編程語言和模型，其中使用最廣泛的是為可擴展的集群計算設計的消息傳遞接口（Message Passing Interface，MPI）和為共享存儲器的多處理器系統(tǒng)設計的OpenMP[14]。OpenMP最初是為CPU 執(zhí)行而設計的。

OpenACC[15]是計算機廠商為異構(gòu)計算系統(tǒng)提出的一種新編程模型，其主要優(yōu)勢是為抽象掉許多并行編程細節(jié)提供了編譯自動化和運行時系統(tǒng)支持。這使得應用程序在不同廠商的計算機和同一廠商不同時代的產(chǎn)品中保持兼容性。然而，學習OpenACC 需要理解所有相關(guān)的并行編程細節(jié)。

在MPI 編程模型中，集群中的計算節(jié)點之間相互不共享存儲器；節(jié)點之間的數(shù)據(jù)共享與交互都通過顯式傳遞消息的方式實現(xiàn)。MPI 成功應用于高性能科學計算（HPC）領域?，F(xiàn)在很多HPC 集群采用的是異構(gòu)的CPU/GPU 節(jié)點。在集群層次上，開發(fā)人員使用MPI 進行編程，但在節(jié)點層次上，CUDA 是非常高效的編程接口。由于計算節(jié)點之間缺乏共享存儲器機制，要把應用程序移植到MPI中需要做大量針對性分析和分解工作。

包括蘋果公司在內(nèi)的幾大公司在2009 年共同開發(fā)了一套標準編程接口，稱之為OpenCL[16]。與CUDA 類似，OpenCL 編程模型定義了語言擴展和運行時API，使程序員可以在大規(guī)模并行處理中進行并行管理和數(shù)據(jù)傳遞。與CUDA 相比，OpenCL 更多地依賴API，而不是語言的擴展，這允許廠商快速調(diào)整現(xiàn)有編譯器和工具來處理OpenCL 程序。OpenCL 和CUDA 在關(guān)鍵概念和特性上有諸多相似之處，因此CUDA 程序員可以很快掌握OpenCL。

2.5 MATLAB

因提供豐富的庫函數(shù)庫以及諸多其他研究者貢獻和共享的函數(shù)庫，MATLAB 是研究人員實現(xiàn)算法的常用平臺。通過封裝的數(shù)據(jù)容器（GPUArrays）和函數(shù)，MATLAB 允許沒有底層CUDA 編程能力的研究人員可以較容易獲得GPU 計算能力，因此MATLAB 較OpenCL更容易上手。截止準備本文時，2014版本的MATLAB提供了226 個內(nèi)置的GPU 版本的庫函數(shù)。對于有CUDA編程經(jīng)驗的人員，MATLAB 允許直接集成CUDA 內(nèi)核進MATLAB 應用。本文第四章的實驗亦基于MATLAB實現(xiàn)。

2.6 JACKET 引擎

JACKET[17]是一個由AccelerEyes 公司開發(fā)專門用于以MATLAB 為基礎的基于GPU 的計算引擎，其最新版本已經(jīng)包含了高層的接口，完全屏蔽了底層硬件的復雜性，并支持所有支持CUDA 的GPU 計算，降低了進行CUDA 開發(fā)的門檻。JACKET 是MATLAB 代碼在GPU上運行的插件。JACKET 允許標準的MATLAB 代碼能夠在任何支持CUDA 的GPU 上運行，這使得廣大的MATLAB 及C/C++用戶可以直接使用GPU 強大的計算能力進行相關(guān)應用領域的快速原型開發(fā)。JACKET 包含了一套運行于MATLAB 環(huán)境中優(yōu)化并行計算的基礎函數(shù)庫。并且支持MATLAB 數(shù)據(jù)類型，可將任何存儲于MATLAB CPU 內(nèi)存中的變量數(shù)據(jù)轉(zhuǎn)換為GPU 上的數(shù)據(jù)類型，對以往的MATLAB 程序來說，只需更改數(shù)據(jù)類型，就能遷移到GPU 上運行。本文的第四章的實驗亦基于JACKET 在MATLAB 上實現(xiàn)。

3 相關(guān)工作綜述

3.1 基于CPU 的數(shù)據(jù)挖掘算法實現(xiàn)

數(shù)據(jù)挖掘算法的研究一直很活躍，許多成熟和經(jīng)典的算法已經(jīng)實現(xiàn)在諸多研究或商用軟件包/平臺，例如開源的Weka[18]和KNIME，以及商用的IBM公司的PASW Modeler（即之前SPSS公司的Clementine?）。這些軟件默認都是單機版本，可運行在普通PC 或高性能服務器上，基于CPU 的計算能力。為了適應目前大規(guī)模的計算，出現(xiàn)了基于Google 公司提出的MapReduce[19]計算框架實現(xiàn)的開源數(shù)據(jù)挖掘平臺Mahout[20]。相關(guān)的研究起源于斯坦福大學Andrew Ng研究組2006年的經(jīng)典論著[21]。由于現(xiàn)有的算法需要先找到可“遷移”到MapReduce 的方式，因此目前Mahout 平臺上僅有幾個能支持分布式部署的數(shù)據(jù)挖掘算法，包括用于分類的樸素貝葉斯、隨機森林，用于聚類的k-Means，基于項目的協(xié)同過濾等。目前Mahout仍然是基于CPU 的計算能力。

3.2 聚類算法

聚類是數(shù)據(jù)挖掘中用來發(fā)現(xiàn)數(shù)據(jù)分布和隱含模式的一種無監(jiān)督學習，每個訓練元組的類標號是未知的，并且要學習的個數(shù)或集合也可能事先不知道。對于給定的數(shù)據(jù)集，聚類算法按照一定的度量，將數(shù)據(jù)對象分組為多個簇，使得在同一個簇中的對象之間具有較高的相似度，而不同簇中的對象差別很大[22-23]。k-Means 算法是經(jīng)典的基于距離/劃分的聚類分析算法，也是應用得最廣泛的算法之一，采用距離作為相似性的評價指標，即認為兩個對象距離越近，其相似度就越大。k-Means算法的流程如下[24]：

輸入：簇的數(shù)目k和包含n個對象數(shù)據(jù)集D。

輸出：k個簇的集合。

方法：

（1）從D中任意選擇k個對象作為初始簇中心。計算每個數(shù)據(jù)對象到各簇中心的歐氏距離，將每個數(shù)據(jù)對象分配到最相似的簇中。

（2）重新計算每個簇中對象的均值。

（3）循環(huán)執(zhí)行步驟2～3 兩個步驟，直到各個簇內(nèi)對象不再變化。

上述算法步驟2 屬于計算密度最大的部分，且具備并行化的條件。計算各個數(shù)據(jù)對象到各簇中心的歐氏距離和將數(shù)據(jù)對象分配到最近的簇的時候，數(shù)據(jù)對象之間都是相互獨立的，不需要進行交換，且沒有先后順序，后計算的對象不需要等待前一次計算的結(jié)果，僅在完成全部分配過程之后，才需要進行一次數(shù)據(jù)匯總。所以文獻[25]的作者們使用GPU 并行優(yōu)化了一維數(shù)據(jù)的k-Means 算法的步驟2，并使用帶緩存機制的常數(shù)存儲器保存中心點數(shù)據(jù)，能獲得更好的讀取效率。文獻中還展示了實驗結(jié)果，在8600GT 上取得了14 倍左右的加速效果。

DBSCAN 屬于基于密度的聚類算法中最常被引用的，G-DBSCAN 是它的一個GPU 加速版本[26]。文獻[26]的實驗顯示較DBSCAN 可以實現(xiàn)高達112 倍的加速。

BIRCH 是經(jīng)典的基于層次的聚類算法，文獻[27]中基于CUDA 實現(xiàn)的GPU 加速版本在實驗中獲得了高達154 倍的加速。

3.3 分類算法

分類是數(shù)據(jù)挖掘中應用領域極其廣泛的重要技術(shù)之一，至今已經(jīng)提出很多算法。分類算法[28]是一種監(jiān)督學習，通過對已知類別訓練集的分析，從中發(fā)現(xiàn)分類規(guī)則，以此預測新數(shù)據(jù)的類別。分類算法是將一個未知樣本分到幾個已存在類的過程，主要包含兩個步驟：首先，根據(jù)類標號已知的訓練數(shù)據(jù)集，訓練并構(gòu)建一個模型，用于描述預定的數(shù)據(jù)類集或概念集；其次，使用所獲得的模型對新的數(shù)據(jù)進行分類。近年來，許多研究已經(jīng)轉(zhuǎn)向?qū)崿F(xiàn)基于GPU 加速分類算法，包括k-NN（k近鄰）分類算法[29]，支持向量機分類算法[30]，貝葉斯分類算法[31-32]等。

kNN 算法[33]是數(shù)據(jù)挖掘中應用最廣泛的一種分類算法，簡單易實現(xiàn)。它是一種典型的基于實例的學習法，將待判定的檢驗元組與所有的訓練元組進行比較，挑選與其最相似的k個訓練數(shù)據(jù)，基于相應的標簽和一定的選舉規(guī)則來決定其標簽。

在Shenshen Liang 等人的文章[34]指出，由于kNN 算法是一種惰性學習法，對于每個待分類的樣本，它都需要計算其與訓練樣本庫中所有樣本的距離，然后通過排序，才能得到與待分類樣本最相鄰的k個鄰居。那么當遇到大規(guī)模數(shù)據(jù)并且是高維樣本時，kNN 算法的時間復雜度和空間復雜度將會很高，造成執(zhí)行效率低下，無法勝任大數(shù)據(jù)分析任務。所以加速距離的計算是提高kNN 算法的核心問題。因為每個待分類的樣本都可以獨立地進行kNN 分類，前后之間沒有計算順序上的相關(guān)性，因此可以采用GPU 并行運算方法解決kNN 算法串行復雜度高的問題。將計算測試集和訓練集中點與點之間的距離和排序一步采用GPU 并行化完成，其余如判斷類標號一步難以在GPU 上高效實現(xiàn)，由CPU 完成。文獻[34]通過GPU 并行化實現(xiàn)kNN 算法，讓kNN算法時間復雜度大幅度減少，從而說明GPU 對kNN 算法的加速效果是非常明顯的。

3.4 關(guān)聯(lián)分析算法

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中較成熟和重要的研究方法，旨在挖掘事務數(shù)據(jù)庫頻繁出現(xiàn)的項集。因此，挖掘關(guān)聯(lián)規(guī)則的問題可以歸結(jié)為挖掘頻繁項集[35]。關(guān)聯(lián)分析算法首先找出所有的頻繁項集，然后根據(jù)最小支持度和最小置信度從頻繁項集中產(chǎn)生強關(guān)聯(lián)規(guī)則。

Apriori 算法[36]是最有影響力的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項目集的經(jīng)典算法。Apriori 算法使用逐層搜索的迭代方法產(chǎn)生頻繁項目集，即利用k頻繁項集來產(chǎn)生(k+1)項集，是一種基于生成候選項集的關(guān)聯(lián)規(guī)則挖掘方法。在劉瑩等人的文章[37]中指出，產(chǎn)生候選項和計算支持度，占據(jù)Apriori 的大部分計算量。產(chǎn)生候選項的任務是連接兩個頻繁項集，而這個任務在不同線程之間是獨立的，所以這個過程適合在GPU 上被并行化。通過掃描交易數(shù)據(jù)庫，計算支持度程序記錄一個候選項集出現(xiàn)的次數(shù)。由于每個候選項集的計數(shù)與其他項集的計數(shù)相對獨立，同樣適合于多線程并行。所以文獻[37]的作者們在實現(xiàn)Apriori 時使用GPU 并行化了產(chǎn)生候選項和計算支持度這兩個過程，取得了顯著的加速效果。

文獻[38]是目前發(fā)現(xiàn)的對于在GPU 上實現(xiàn)頻繁項集挖掘最全面細致的研究。他們使用的是早期的CUDA平臺，采用了bitmap 和trie 兩種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)GPU 的挖掘算法，并且根據(jù)不同數(shù)據(jù)集和支持度進行了算法性能的對比，均相對于CPU 版本的算法獲得的一定的加速比。

3.5 時序分析

由于越來越多的數(shù)據(jù)都與時間有著密切的關(guān)系，時序數(shù)據(jù)作為數(shù)據(jù)挖掘研究的重要分支之一，越來越受到人們的重視。其研究的目的主要包括以下兩個方面：一是學習待觀察過程過去的行為特征；二是預測未來該過程的可能狀態(tài)或表現(xiàn)。

時序數(shù)據(jù)挖掘主要包含以下幾個主要任務：數(shù)據(jù)預處理，時序數(shù)據(jù)表示，分割，相似度度量，分類，聚類等。這些任務中很多都涉及到相當大的計算量。由于問題規(guī)模的不斷擴大，并且對于實時性能的要求，時序數(shù)據(jù)挖掘的任務就必須要求充分地提高計算速度或者通過優(yōu)化減少計算量。

時序數(shù)據(jù)的表示有時候會采取特征來表示，這就涉及到了特征提取問題，當特征數(shù)量龐大的時候就需要進行維數(shù)約簡，主要的方法有奇異值分解法，離散小波變換。這些計算都涉及到很大的時間復雜度，為了減少計算的時間消耗，Sheetal Lahabar 等人使用GPU 加速SVD 的計算，獲得了60 多倍的加速效果[39]。

動態(tài)時間彎曲（Dynamic Time Warping，DTW）起初被應用于文本數(shù)據(jù)匹配和視覺模式識別的研究領域，是一種相似性度量算法。研究表明這種基于非線性彎曲技術(shù)的算法可以獲得很高的識別、匹配精度。Berndt和Clifford 提出了將DTW 的概念引入小型時間序列分析領域，在初步的實驗中取得了較好的結(jié)果[40]。隨著問題規(guī)模的擴大，對于DTW 的計算成為了時序數(shù)據(jù)挖掘的首先要處理的問題。在DTW 中，搜索需要找出與訓練數(shù)據(jù)最近距離的樣本，這就需要搜索與每個訓練樣本的距離，這就可以很好地利用GPU 進行并行化處理。Doruk Sart 等人在對DTW 加速的處理中，獲得了兩個數(shù)量級的加速效果[41]。

而對于分類和聚類任務的加速，上面已經(jīng)提到，這里不再累贅。

3.6 深度學習

深度學習雖然隸屬機器學習，但鑒于機器學習和數(shù)據(jù)挖掘領域的緊密聯(lián)系，深度學習必定將在數(shù)據(jù)挖掘領域獲得越來越多的應用。從2006 年Hinton 和他的學生Salakhutdinov 在《科學》上發(fā)表的文章[42]開始，深度學習在學術(shù)界持續(xù)升溫。

深度學習的實質(zhì)是通過構(gòu)建具有很多隱層的機器學習模型和海量的訓練數(shù)據(jù)，來學習更有用的特征，從而最終提升分類預測的準確性[43]。

如何在工程上利用大規(guī)模的并行計算平臺來實現(xiàn)海量數(shù)據(jù)訓練，是各個機構(gòu)從事深度學習技術(shù)研發(fā)首先要解決的問題。傳統(tǒng)的大數(shù)據(jù)平臺如Hadoop，由于數(shù)據(jù)處理延遲太高而不適合需要頻繁迭代的深度學習。神經(jīng)網(wǎng)絡一般基于大量相似的神經(jīng)元，故本質(zhì)上可以高度并行化訓練；通過映射到GPU，可以實現(xiàn)比單純依賴CPU 顯著的提升。

谷歌搭建的DistBelief[44]是一個采用普通服務器的深度學習并行計算平臺，采用異步算法，由很多計算單元獨立更新同一個參數(shù)服務器的模型參數(shù)，實現(xiàn)了隨機梯度下降算法的并行化，加快了模型訓練速度。百度的多GPU 并行計算平臺克服了傳統(tǒng)SGD 訓練不能并行的技術(shù)難題，神經(jīng)網(wǎng)絡的訓練已經(jīng)可以在海量語料上并行展開[43]。

NVIDIA 在2014 年9 月推出了深度學習GPU 加速庫cuDNN，可以方便地嵌入高層級機器學習框架中使用，例如Caffe[45]。cuDNN 支持NVIDIA 的全系列GPU，包括低端的Tegra K1 和高端的Tesla K40，并承諾可向上支持未來的GPU。

3.7 小結(jié)

并行化能帶來多少倍的加速取決于算法中可并行化的部分。例如，如果可并行部分的時間占整個應用程序執(zhí)行時間的20%，那么即使將并行部分加速100 倍，總執(zhí)行時間也只能減少19.8%，整個應用程序的加速只有1.247 倍；即使無限加速也只能減少約20%的執(zhí)行時間，總加速不會超過1.25 倍。

對于一個數(shù)據(jù)挖掘（學習和預測）算法進行GPU 加速實現(xiàn)，首先要思考是否存在可并行執(zhí)行的部分，之后再結(jié)合GPU 的架構(gòu)特點進行針對性實現(xiàn)優(yōu)化。然而，由于數(shù)據(jù)挖掘算法普遍是數(shù)據(jù)密集型計算，而GPU 片內(nèi)存儲容量有限，如何降低與內(nèi)存交換數(shù)據(jù)集是一個要解決的關(guān)鍵問題。

通過以上相關(guān)工作的分析，可以發(fā)現(xiàn)數(shù)據(jù)挖掘算法在GPU 上的加速具有數(shù)據(jù)獨立，可并行化共同特征。本文提出數(shù)據(jù)挖掘算法在GPU 上加速實現(xiàn)的一種解決思路：在大數(shù)據(jù)下，分析算法的性能瓶頸，從而確定算法中耗時大，時間復雜度高的部分，將此部分在GPU 上執(zhí)行，不耗時部分在CPU 上串行執(zhí)行，以達到加速效果。為了更充分利用GPU 的并行計算的體系結(jié)構(gòu)，可深入分析耗時大的部分，將具有數(shù)據(jù)獨立，可并行化的部分在GPU 上并行執(zhí)行，達到更進一步的加速效果。

4 實踐和分析：協(xié)同過濾推薦

當前主要的協(xié)同過濾推薦算法有兩類：基于用戶（user-based）和基于項目（item-based）的協(xié)同過濾推薦算法?；陧椖康膮f(xié)同過濾推薦算法[46-50]認為，項目間的評分具有相似性，可以通過用戶對目標項目的若干相似項目的評分來估計該項目的分值?；谟脩舻膮f(xié)同過濾推薦算法[50-51]認為，如果用戶對一些項目的評分比較相似，那么他們對其他項目的評分也比較相似。本文根據(jù)以上總結(jié)的算法特征圍繞兩種經(jīng)典協(xié)同過濾算法的實現(xiàn)，通過大規(guī)模數(shù)據(jù)的實驗來驗證GPU 相對于傳統(tǒng)CPU 的優(yōu)勢。

4.1 算法實現(xiàn)

4.1.1 基于CPU 實現(xiàn)協(xié)同過濾推薦的兩類經(jīng)典算法

本文基于MATLAB實現(xiàn)CPU版本的基于用戶和基于項目的兩種經(jīng)典協(xié)同過濾推薦算法。實現(xiàn)的步驟[51-55]：

（1）數(shù)據(jù)表示：收集用戶的評分數(shù)據(jù)，并進行數(shù)據(jù)清理、轉(zhuǎn)換，最終形成一個m×n的用戶-項目評分矩陣R，m和n分別代表矩陣中的用戶數(shù)和項目數(shù)，矩陣中的元素代表用戶對項目的評分值。

（2）最近鄰居搜索：主要完成對目標用戶/項目的最近鄰居的查找。通過計算目標用戶/項目與其他用戶/項目之間的相似度，算出與目標用戶/項目最相似的最近鄰居集。該過程分兩步完成：首先采用協(xié)同過濾推薦算法中運用較多的度量方法“Pearson 相關(guān)系數(shù)”計算用戶/項目之間的相似度得到相應的相似度矩陣，其次是采用最近鄰方法找到目標用戶/項目的最近的K個鄰居，這些鄰居是由與目標相似度最高的一些用戶/項目組成的。

設用戶u 和用戶v 共同評分的項目集合用Iuv表示，則用戶u 和用戶v 之間的相似性sim(u，v)通過Pearson相關(guān)系數(shù)來度量，如式（1）所示：

其中Ru，i表示用戶u 對項目i的評分，和分別表示用戶u 和用戶v 對項目的平均評分。

設對項目i和項目j共同評分過的用戶集合用Uij表示，則項目i和項目j之間的相似性sim(i，j) 通過Pearson 相關(guān)系數(shù)來度量，如式（2）所示：

其中Ru，i表示用戶u 對項目i的評分，和分別表示對項目i和項目j的平均評分。

（3）產(chǎn)生推薦：根據(jù)之前計算好的用戶/項目之間的相似度，并使用相應的預測評分函數(shù)對用戶未打分的項目進行預測，得到預測評分矩陣，然后選擇預測評分最高的Top-n項推薦給目標用戶。

基于用戶的協(xié)同過濾推薦算法的預測評分函數(shù)，如式（3）所示：

其中NNu表示用戶u 的最近鄰居集合，sim(u，v)表示用戶u 和最近鄰居v 之間的相似性。

基于項目的協(xié)同過濾推薦算法的預測評分函數(shù)，如式（4）所示：

其中NNi表示項目i的最近鄰居集合，sim(i，j)表示項目i和最近鄰居j之間的相似性。

（4）性能評估：本研究擬采用平均絕對誤差MAE 作為評價推薦系統(tǒng)預測質(zhì)量的評價標準。MAE 可以直觀地對預測質(zhì)量進行度量，是最常用的一種方法。MAE通過計算預測的用戶評分與實際評分之間的偏差度量預測的準確性；MAE 越小，預測質(zhì)量越高。假設預測用戶對n個項目的評分集合為{r1，r2，…，rn}，而用戶實際上對這n個項目相應的評分集合為{w1，w2，…，wn}，根據(jù)平均絕對誤差，如式（5）所示：

4.1.2 基于GPU 實現(xiàn)協(xié)同過濾推薦的兩類經(jīng)典算法

在大數(shù)據(jù)下，協(xié)同過濾算法中主要的時間消耗在于相似度計算模塊，占了整個算法的大部分時間，且每個用戶/項目之間的相似度可以被獨立計算，不依靠其他用戶/項目，具備并行化的條件，所以在以下的實驗中，將相似度計算模塊在GPU 上執(zhí)行，其他部分在CPU 上執(zhí)行，進而提高整個算法的執(zhí)行效率。

使用MATLAB 編程技術(shù)和JACKET 編程技術(shù)在GPU 上分別實現(xiàn)基于用戶和基于項目的兩種經(jīng)典協(xié)同過濾推薦算法。實現(xiàn)步驟如下：

（1）數(shù)據(jù)表示：收集用戶的評分數(shù)據(jù)，并進行數(shù)據(jù)清理、轉(zhuǎn)換，最終形成用戶-項目評分矩陣。

（2）將收集的數(shù)據(jù)從CPU 傳輸至GPU。

（3）對傳輸?shù)紾PU 上的數(shù)據(jù)執(zhí)行GPU 操作，調(diào)用相關(guān)函數(shù)庫，采用公式（1）和（2）分別計算并獲取用戶/項目間的相似度矩陣。

（4）將GPU 計算結(jié)果返回CPU 中以便后續(xù)操作。

（5）采用公式（3）和（4）在CPU 上分別獲取兩種經(jīng)典算法的評分預測矩陣。

（6）選擇預測評分最高的Top-n項推薦給目標用戶。

（7）采用公式（5）求兩種經(jīng)典算法的平均絕對誤差MAE。

4.2 實驗結(jié)果與分析

4.2.1 實驗環(huán)境

本實驗所用的CPU 是Intel Xeon E5 2687W，核心數(shù)量是八核，主頻率是3.1 GHz，內(nèi)存大小是32 GB；所使用的GPU是NVIDIA Quadro K4000，顯存容量是3 GB，顯存帶寬是134 GB/s 核心頻率是811 MHz，流處理器數(shù)是768 個。使用Windows7 64 位操作系統(tǒng)，編程環(huán)境使用最新的CUDA。

4.2.2 實驗數(shù)據(jù)

本實驗使用目前比較常用的MovieLens[56]數(shù)據(jù)集作為測試數(shù)據(jù)，該數(shù)據(jù)集從MovieLens 網(wǎng)站（http：//movielens.umn.edu/）采集而來，由美國Minnesota 大學的GroupLens 研究小組提供，數(shù)據(jù)集1 包含943 個用戶對1 682部電影約10 萬的評分數(shù)據(jù)，數(shù)據(jù)集2 包含6 040 個用戶對3 952 部電影約100 萬的評分數(shù)據(jù)，其中每個用戶至少對20 部電影進行了評分。評分的范圍是1～5，1 表示“很差”，5 表示“很好”。實驗需要將每個數(shù)據(jù)集劃分為一個訓練集和一個測試集，每次隨機選出其中80%的評分數(shù)據(jù)用作訓練集，另20%用作測試集。

4.2.3 實驗結(jié)果與分析

本文采用加速比來比較算法的CPU 實現(xiàn)和GPU 實現(xiàn)的運行效率。計算加速比的方法如式（6）所示：

在公式中，TimeCPU表示算法在CPU 上的平均運行時間，TimeGPU表示算法在GPU 上的平均運行時間。所有實驗中均取最近鄰居數(shù)為20，且各實驗結(jié)果均為5 次獨立測試的平均值。

圖2 是關(guān)于兩個算法核心步驟的加速效果，而圖3則展示了算法整體加速效果?？梢钥闯觯海?）整體加速效果取決于核心步驟的加速效果。（2）GPU 版本的算法在性能上較CPU 版本有較顯著的優(yōu)勢，且面對大數(shù)據(jù)集的加速效果更為明顯。例如在基于100 萬條數(shù)據(jù)集時，Item-based 的整體算法的加速比達到了14 倍左右，而面對10 萬條數(shù)據(jù)集時，加速比不到8 倍。這可以解釋為GPU 的多核優(yōu)勢在面對大數(shù)據(jù)集時被更為充分地得到釋放。（3）算法對User-based 和Item-based 兩種算法的加速比相近。

圖2 計算相似度加速比

圖4 是關(guān)于算法預測效果的評估，可以看出基于GPU 加速的兩類經(jīng)典協(xié)同過濾算法與基于CPU 的兩類經(jīng)典協(xié)同過濾算法在預測效果上相近。如果結(jié)合圖2和圖3，可獲得結(jié)論-能夠基于GPU 獲得可觀的計算加速而不犧牲應用效果。

圖3 整體算法加速比

圖4 算法的MAE 比較

4.3 小結(jié)

本文通過使用JACKET加快開發(fā)過程。目前國內(nèi)還缺少對JACKET 的了解和應用，JACKET 的出現(xiàn)為科學領域進行大規(guī)模計算仿真提供了新的研究方法，并使得研究人員可以在熟悉的MATLAB平臺上實現(xiàn)相關(guān)算法。

5 結(jié)束語

本文既對基于GPU 加速經(jīng)典數(shù)據(jù)挖掘的研究進行了分類回顧和小結(jié)，也實踐了基于GPU 加速協(xié)同過濾計算，通過和基于CPU 的版本對比，確實可以實現(xiàn)可觀的效率提升。這對深入研究將GPU 應用到大數(shù)據(jù)處理場景可以積累寶貴的一手經(jīng)驗，并在已知的尚未基于GPU 加速的數(shù)據(jù)挖掘算法有的放矢。

[1] Han Jiawei，Kamber M，Pei Jian.Data Mining：concepts and techniques[M].3rd ed.[S.l.]：Morgan Kaufmann，2012：5-8.

[2] Owens J D，Houston M，Luebke D，et al.GPU computing[J].Proceedings of the IEEE，2008，96（5）：879-899.

[3] NVIDIA CUDA Zone[EB/OL].（2012-03-09）.http：//developer.nvidia.com/page/home.html.

[4] Michalakes J，Vachharajani M.GPU acceleration of numerical weather prediction[J].Parallel Processing Letters，2008，18（4）：531-548.

[5] 劉欽，佟小龍.GPU/CPU 協(xié)同并行計算（CPPC）在地震勘探資料處理中的應用[R].2008.

[6] Bell N，Garland M.Implementing sparse matrix-vector multiplication on throughput-oriented processors[C]//Proceedings of the Conference on High Performance Computing Networking，Storage and Analysis.ACM，2009.

[7] Bolz J，F(xiàn)armer I，Grinspun E，et al.Sparse matrix solvers on the GPU：conjugate gradients and multigrid[C]//ACM Transactions on Graphics（TOG）.ACM，2003，22（3）：917-924.

[8] Stone J E，Phillips J C，F(xiàn)reddolino P L，et al.Accelerating molecular modeling applications with graphics processors[J].Journal of Computational Chemistry，2007，28（16）：2618-2640.

[9] Govindaraju N K，Lloyd B，Wang W，et al.Fast computation of database operations using graphics processors[C]//Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data.ACM，2004：215-226.

[10] NVIDIA Corporation.NVIDIA CUDA programming guide version 2.3.1[R].2009：1-3.

[11] David B K，Wen-mei W H.Programming massively parallel processors：A handson approach[M].2nd ed.[S.l.]：Elsevier Inc，2006.

[12] 盧風順，宋君強，銀福康，等.CPU/GPU 協(xié)同并行計算研究綜述[J].計算機科學，2011（3）：5-9.

[13] 張舒，褚艷利.GPU 高性能運算之CUDA[M].北京：中國水利水電出版社，2009：1-13.

[14] Dagum L，Menon R.OpenMP：an industry standard APfor shared-memory programming[J].Computational Science& Engineering.IEEE，1998，5（1）：46-55.

[15] Wienke S，Springer P，Terboven C，et al.OpenACC—first experiences with real-world applications[M]//Euro-Par 2012 Parallel Processing.Berlin Heidelberg：Springer，2012：859-870.

[16] Breitbart J，F(xiàn)ohry C.OpenCL-an effective programming model for data parallel computations at the cell broadband engine[C]//2010 IEEE International Symposium on Parallel & Distributed Processing，Workshops and Phd Forum（IPDPSW）.IEEE，2010：1-8.

[17] 王恒，高建瓴.基于GPU 的MATLAB 計算與仿真研究[J].貴州大學學報：自然科學版，2012，6：95-98.

[18] Mark H，Eibe F，Geoffrey H，et al.The WEKA data mining software：An update[J].SIGKDD Explorations，2009，11（1）.

[19] Jeffry D，Sanjay G.MapReduce：Simplied data processing on large clusters[C]//Proceedings of 6th Symposium on Operating System Design and Implementation（OSDI），2004.

[20] Sean O，Robin A，Ted D，et al.Mahout in action[M].[S.l.]：Manning Publications，2011.

[21] Cheng-Tao C，Sang K K，Yi-An L，et al.Map-Reduce for machine learning on multicore[C]//Proceedings of 20th Neural Information Processing Systems（NIPS），2006：281-288.

[22] 孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學報，2008，19（1）：48-61.

[23] 周濤，陸惠玲.數(shù)據(jù)挖掘中聚類算法研究進展[J].計算機工程與應用，2012，48（12）：100-111.

[24] 周愛武，于亞飛.K-Means 聚類算法研究[J].計算機技術(shù)與發(fā)展，2011，21（2）：62-65.

[25] Farivar R，Rebolledo D，Chan E，et al.A parallel implementation of K-Means Clustering on GPUs[C]//Proceedings of the 2008 International Conference on Parallel and Distributed Processing Techniques and Applications.[S.l.]：Springer-Verlag，2008：340-345.

[26] Guilherme A，Gabriel R，Daniel M，et al.G-DBSCAN：A GPU accelerated algorithm for density-based clustering[J].Procedia Computer Science，2013，18：369-378.

[27] Jianqiang D，F(xiàn)ei W，Bo Y.Accelerating BIRCH for clustering large scale streaming data using CUDA dynamic parallelism[C]//Proceedings of 14th International Conference on Intelligent Data Engineering and Automated Learning（IDEAL），2013.

[28] 郭煒星.數(shù)據(jù)挖掘分類算法研究[D].杭州：浙江大學，2008.

[29] Garcia V，Debreuve E，Barlaud M.Fastknearest neighbor search using GPU[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops.IEEE，2008：1-6.

[30] Catanzaro B，Sundaram N，Keutzer K.Fast support vector machine training and classification on graphics processors[C]//Proceedings of the 25th International Conference on Machine Learning.ACM，2008：104-111.

[31] Andrade G，Viegas F，Ramos G S，et al.GPU-NB：A fast CUDA-based implementation of Na?ve Bayes[C]//2013 25th International Symposium on Computer Architecture and High Performance Computing（S BAC-PAD）.IEEE，2013：168-175.

[32] 劉琳，何劍鋒，王紅玲.GPU 加速數(shù)據(jù)挖掘算法的研究[J].鄭州工業(yè)大學學報：理學版，2010，42（2）：31-34.

[33] 潘麗芳，楊炳儒.基于簇的K最近鄰(KNN)分類算法研究[J].計算機工程與設計，2009，30（18）：4260-4262.

[34] Liang S，Liu Y，Wang C，et al.A CUDA-based parallel implementation of K-nearest neighbor algorithm[C]//International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery.IEEE，2009：291-296.

[35] Han J，Cheng H，Xin D，et al.Frequent pattern mining：current status and future directions[J].Data Mining and Knowledge Discovery，2007，15（1）：55-86.

[36] 崔貫勛，李梁，王柯柯，等.關(guān)聯(lián)規(guī)則挖掘中Apriori 算法的研究與改進[J].計算機應用，2010（11）：2952-2955.

[37] 劉瑩，菅立恒，梁莘燊，等.基于CUDA 架構(gòu)的GPU 的并行數(shù)據(jù)挖掘技術(shù)研究[J].科研信息化技術(shù)與應用，2010（4）：38-52.

[38] Fang W，Lu M，Xiao X，et al.Frequent itemset mining on graphics processors[C]//Proceedings of the Fifth International Workshop on Data Management on New Hardware.ACM，2009：34-42.

[39] Lahabar S，Narayanan P J.Singular value decomposition on GPU using CUDA[C]//2009 IEEE International Symposium on Parallel & Distributed Processing.IEEE，2009：1-10.

[40] Berndt D J，Clifford J.Using dynamic time warping to find patterns in time series[C]//KDD Workshop，1994，10（16）：359-370.

[41] Sart D，Mueen A，Najjar W，et al.Accelerating dynamic time warping subsequence search with GPUs and FPGAs[C]//2010 IEEE 10th International Conference on Data Mining（ICDM）.IEEE，2010：1001-1006.

[42] Hinton G E，Salakhutdinov R R.Reducing the dimensionality of data with neural networks[J].Science，2006，313（5786）：504-507.

[43] 余凱，賈磊，陳雨強，等.深度學習的昨天、今天和明天[J].計算機研究與發(fā)展，2013，50（9）：1799-1804.

[44] Dean J，Corrado G，Monga R，et al.Large scale distributed deep networks[C]//Advances in Neural Information Processing Systems，2012：1223-1231.

[45] Yang Q J.Caffe：An open source convolutional architecture for fast feature embedding[Z].2013.

[46] 鄧愛林，左子葉，朱揚勇.基于項目聚類的協(xié)同過濾推薦算法[J].小型微型計算機系統(tǒng)，2004（9）：1665-1670.

[47] Sarwar B，Karypis G，Konstan J，et al.Item-based collaborative filtering recommendation algorithms[C]//Proceedings of the 10th International Conference on World Wide Web.ACM，2001：285-295.

[48] 鄧愛林，朱揚勇，施伯樂.基于項目評分預測的協(xié)同過濾推薦算法[J].軟件學報，2003（9）：1621-1628.

[49] 張忠平，郭獻麗.一種優(yōu)化的基于項目評分預測的協(xié)同過濾推薦算法[J].計算機應用研究，2008（9）：2658-2660.

[50] 孫光福，吳樂，劉淇，等.基于時序行為的協(xié)同過濾推薦算法[J].軟件學報，2013（11）：2721-2733.

[51] Ekstrand M D，Ridel J T，Konstan J A.Collaborative filtering recommender systems[M].Hanover：Now Publishers Inc，2010：81-173.

[52] 王國霞，劉賀平.個性化推薦系統(tǒng)綜述[J].計算機工程與應用，2012，48（7）：66-76.

[53] Jannach D，Zanker M，F(xiàn)elfernig A，et al.推薦系統(tǒng)[M].蔣凡，譯.北京：人民郵電出版社，2013：8-13.

[54] 項亮.推薦系統(tǒng)實踐[M].北京：人民郵電出版社，2012：184-186.

[55] 張瑤，陳維斌，傅順開.協(xié)同過濾推薦研究綜述[J].微型機與應用，2013（6）：4-6.

[56] Grouplens.MovieLens[EB/OL].[2014-02-13].http：//grouplens.org.University of Minnesota.