通過GPU 加速數(shù)據(jù)挖掘的研究進(jìn)展和實(shí)踐

戴春娥，陳維斌，傅順開，李志強(qiáng)

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

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

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

1 引言

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

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

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

2 基于GPU 的計(jì)算和編程

2.1 GPU

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

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

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

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

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

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

2.3 CUDA

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

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

2.4 并行編程語言和模型

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

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

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

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

2.5 MATLAB

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

2.6 JACKET 引擎

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

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

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

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

3.2 聚類算法

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

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

輸出：k個(gè)簇的集合。

方法：

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

（2）重新計(jì)算每個(gè)簇中對(duì)象的均值。

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

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

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

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

3.3 分類算法

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

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

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

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

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

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

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

3.5 時(shí)序分析

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

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

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

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

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

3.6 深度學(xué)習(xí)

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

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

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

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

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

3.7 小結(jié)

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

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

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

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

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

4.1 算法實(shí)現(xiàn)

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

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

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

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

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

其中Ru，i表示用戶u 對(duì)項(xiàng)目i的評(píng)分，和分別表示用戶u 和用戶v 對(duì)項(xiàng)目的平均評(píng)分。

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

其中Ru，i表示用戶u 對(duì)項(xiàng)目i的評(píng)分，和分別表示對(duì)項(xiàng)目i和項(xiàng)目j的平均評(píng)分。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（6）選擇預(yù)測評(píng)分最高的Top-n項(xiàng)推薦給目標(biāo)用戶。

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

4.2 實(shí)驗(yàn)結(jié)果與分析

4.2.1 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yà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 個(gè)。使用Windows7 64 位操作系統(tǒng)，編程環(huán)境使用最新的CUDA。

4.2.2 實(shí)驗(yàn)數(shù)據(jù)

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

4.2.3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

圖2 計(jì)算相似度加速比

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

圖3 整體算法加速比

圖4 算法的MAE 比較

4.3 小結(jié)

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

5 結(jié)束語

本文既對(duì)基于GPU 加速經(jīng)典數(shù)據(jù)挖掘的研究進(jìn)行了分類回顧和小結(jié)，也實(shí)踐了基于GPU 加速協(xié)同過濾計(jì)算，通過和基于CPU 的版本對(duì)比，確實(shí)可以實(shí)現(xiàn)可觀的效率提升。這對(duì)深入研究將GPU 應(yīng)用到大數(shù)據(jù)處理場景可以積累寶貴的一手經(jīng)驗(yàn)，并在已知的尚未基于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é)同并行計(jì)算（CPPC）在地震勘探資料處理中的應(yīng)用[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] 盧風(fēng)順，宋君強(qiáng)，銀?？?，等.CPU/GPU 協(xié)同并行計(jì)算研究綜述[J].計(jì)算機(jī)科學(xué)，2011（3）：5-9.

[13] 張舒，褚艷利.GPU 高性能運(yùn)算之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ì)算與仿真研究[J].貴州大學(xué)學(xué)報(bào)：自然科學(xué)版，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].軟件學(xué)報(bào)，2008，19（1）：48-61.

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

[24] 周愛武，于亞飛.K-Means 聚類算法研究[J].計(jì)算機(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].杭州：浙江大學(xué)，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è)大學(xué)學(xué)報(bào)：理學(xué)版，2010，42（2）：31-34.

[33] 潘麗芳，楊炳儒.基于簇的K最近鄰(KNN)分類算法研究[J].計(jì)算機(jī)工程與設(shè)計(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ìn)[J].計(jì)算機(jī)應(yīng)用，2010（11）：2952-2955.

[37] 劉瑩，菅立恒，梁莘燊，等.基于CUDA 架構(gòu)的GPU 的并行數(shù)據(jù)挖掘技術(shù)研究[J].科研信息化技術(shù)與應(yīng)用，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] 余凱，賈磊，陳雨強(qiáng)，等.深度學(xué)習(xí)的昨天、今天和明天[J].計(jì)算機(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] 鄧愛林，左子葉，朱揚(yáng)勇.基于項(xiàng)目聚類的協(xié)同過濾推薦算法[J].小型微型計(jì)算機(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] 鄧愛林，朱揚(yáng)勇，施伯樂.基于項(xiàng)目評(píng)分預(yù)測的協(xié)同過濾推薦算法[J].軟件學(xué)報(bào)，2003（9）：1621-1628.

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

[50] 孫光福，吳樂，劉淇，等.基于時(shí)序行為的協(xié)同過濾推薦算法[J].軟件學(xué)報(bào)，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] 王國霞，劉賀平.個(gè)性化推薦系統(tǒng)綜述[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（7）：66-76.

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

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

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

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