周 宇，曹英楠，王永超

（南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院/人工智能學(xué)院，南京 211106）

隨著多核CPU 性能、存儲(chǔ)設(shè)備性價(jià)比的迅速提升、網(wǎng)絡(luò)帶寬的不斷增加，以及移動(dòng)互聯(lián)網(wǎng)、物聯(lián)網(wǎng)、云計(jì)算等新一代信息技術(shù)的迅速發(fā)展和快速普及，人類生產(chǎn)生活已和信息技術(shù)相互交融，全球數(shù)據(jù)量出現(xiàn)爆發(fā)式增長(zhǎng)。海量集聚的數(shù)據(jù)中蘊(yùn)含著前所未有的社會(huì)價(jià)值和商業(yè)價(jià)值，政府和企業(yè)可通過分析處理大規(guī)模的用戶數(shù)據(jù)得到傳統(tǒng)數(shù)據(jù)分析方式無(wú)法獲知的隱藏價(jià)值和模式，從而為公眾和客戶提供更加迅速、準(zhǔn)確的公共服務(wù)及產(chǎn)品，大數(shù)據(jù)研究領(lǐng)域也因此吸引了社會(huì)各界的廣泛關(guān)注。

大數(shù)據(jù)［1］指的是利用傳統(tǒng)的數(shù)據(jù)處理分析技術(shù)或軟硬件工具無(wú)法在可容忍的時(shí)間范圍內(nèi)對(duì)數(shù)據(jù)進(jìn)行采集、處理和分析的數(shù)據(jù)集。其相較于傳統(tǒng)的數(shù)據(jù)集，擁有4V 特點(diǎn)［1］：規(guī)模性（Volume）、多樣性（Variety）、價(jià)值（Value）和實(shí)效性（Velocity）。根據(jù)挖掘任務(wù)的不同，數(shù)據(jù)挖掘處理方法可分為分類分析、聚類分析、關(guān)聯(lián)規(guī)則挖掘和序列分析等多種不同的方法。Blackett 將各處理方法進(jìn)一步地按數(shù)據(jù)分析的程度劃分為3 類［2］：使用歷史數(shù)據(jù)進(jìn)行總結(jié)的描述性分析、利用相關(guān)技術(shù)預(yù)測(cè)未來概率或趨勢(shì)的預(yù)測(cè)性分析、發(fā)現(xiàn)隱藏?cái)?shù)據(jù)相關(guān)性以幫助用戶制定決策的規(guī)則性分析。聚類分析被用于描述數(shù)據(jù)，其通過衡量數(shù)據(jù)之間的相似性對(duì)數(shù)據(jù)進(jìn)行分類；分類分析根據(jù)訓(xùn)練數(shù)據(jù)獲得分類規(guī)則，故而常被用于預(yù)測(cè)分析；關(guān)聯(lián)規(guī)則挖掘目的在于從數(shù)據(jù)庫(kù)中發(fā)現(xiàn)并提取有價(jià)值的隱藏模式，且其思路同樣適用于序列模式發(fā)現(xiàn)。其中，分類屬于監(jiān)督學(xué)習(xí)，聚類和關(guān)聯(lián)規(guī)則挖掘?qū)儆跓o(wú)監(jiān)督學(xué)習(xí)，這3 類方法作為常用機(jī)器學(xué)習(xí)算法，在學(xué)術(shù)界受到較多關(guān)注和研究，發(fā)展出了許多方法和理論，本文將按照分類、聚類和關(guān)聯(lián)規(guī)則挖掘依次對(duì)相關(guān)內(nèi)容進(jìn)行展開。

大數(shù)據(jù)的4V 特征及其影響意味著數(shù)據(jù)的高復(fù)雜度和高計(jì)算成本，故難以使用傳統(tǒng)數(shù)據(jù)挖掘方法來分析處理數(shù)據(jù)。在分類問題中，傳統(tǒng)的對(duì)靜態(tài)數(shù)據(jù)處理的方法已比較完善，但流式數(shù)據(jù)作為大數(shù)據(jù)的一個(gè)重要來源，傳統(tǒng)算法難以對(duì)流式數(shù)據(jù)處理中出現(xiàn)的概念漂移現(xiàn)象進(jìn)行應(yīng)對(duì)，故針對(duì)大數(shù)據(jù)中流式數(shù)據(jù)的分類算法比較關(guān)鍵。聚類和關(guān)聯(lián)規(guī)則挖掘方法最初便用于從各種應(yīng)用的數(shù)據(jù)庫(kù)中發(fā)現(xiàn)隱藏的有價(jià)值信息，因此在大數(shù)據(jù)時(shí)代，相關(guān)算法也受到越來越多的關(guān)注，面對(duì)大數(shù)據(jù)處理的挑戰(zhàn)，關(guān)鍵在于如何通過并行傳統(tǒng)算法或是提出新的算法來應(yīng)對(duì)。

1 面向大數(shù)據(jù)的流式數(shù)據(jù)分類算法

本文按照?qǐng)D1 的思維框架圖，首先介紹流式數(shù)據(jù)的分類算法，分類作為一種監(jiān)督學(xué)習(xí)方法［3］，其目的是通過訓(xùn)練數(shù)據(jù)集中的實(shí)例以及實(shí)例所屬的類標(biāo)簽發(fā)現(xiàn)分類規(guī)則，并使用該分類規(guī)則來預(yù)測(cè)未知實(shí)例所屬類標(biāo)簽。分類過程有兩個(gè)階段：（1）分類規(guī)則學(xué)習(xí)階段，該階段通過分析、歸納訓(xùn)練集中各實(shí)例類標(biāo)簽情況，發(fā)現(xiàn)分類規(guī)則，創(chuàng)建合適的分類器模型；（2）測(cè)試集的分類階段，該階段需在驗(yàn)證集上評(píng)估分類器模型的分類準(zhǔn)確率，若準(zhǔn)確度較好，則使用該分類器對(duì)測(cè)試集中實(shí)例進(jìn)行預(yù)先分類，否則需重新訓(xùn)練分類器模型。

1.1 流式數(shù)據(jù)特點(diǎn)

在大數(shù)據(jù)時(shí)代，流式數(shù)據(jù)作為大數(shù)據(jù)的一個(gè)重要來源［4?5］，大多源自日常生活中的簡(jiǎn)單操作，例如網(wǎng)上購(gòu)物數(shù)據(jù)、網(wǎng)絡(luò)社交信息以及web 應(yīng)用程序生成的日志信息等。 其具有如下主要特性［6］：

（1）無(wú)限性。流式數(shù)據(jù)作為真實(shí)世界中的記錄，數(shù)據(jù)量是連續(xù)不斷、無(wú)限的。

（2）實(shí)時(shí)性。各類數(shù)據(jù)源產(chǎn)生的數(shù)據(jù)是實(shí)時(shí)的，不可預(yù)知的。

（3）時(shí)序性。數(shù)據(jù)按產(chǎn)生的時(shí)間先后順序按序到達(dá)。

（4）一次處理。因流式數(shù)據(jù)是實(shí)時(shí)且數(shù)據(jù)量無(wú)限，故流式數(shù)據(jù)中的數(shù)據(jù)通常只處理一次，在沒有特別保存的情況下，流式數(shù)據(jù)不能被再次處理。

（5）富含變化。流式數(shù)據(jù)隨時(shí)間不斷產(chǎn)生的過程中，其數(shù)據(jù)分布動(dòng)態(tài)改變，即會(huì)出現(xiàn)概念漂移的現(xiàn)象［7］。

1.2 概念漂移及其處理技術(shù)

概念漂移指流式數(shù)據(jù)中數(shù)據(jù)分布隨時(shí)間發(fā)生變化，導(dǎo)致實(shí)例和實(shí)例所屬類標(biāo)簽之間的分類規(guī)則發(fā)生改變。如圖2 所示，常見的概念漂移有如下幾種類型［8］：

圖2 概念漂移分布類型Fig.2 Conceptual drift distribution type

（1）突變漂移。概念在短時(shí)間發(fā)生巨大的變化且不可逆。

（2）漸變漂移。概念隨著時(shí)間逐漸的變化，且中間可能發(fā)生往復(fù)。

（3）增量漂移。概念隨著時(shí)間緩慢的不可逆的演變。

（4）重復(fù)漂移。是一種臨時(shí)性的改變，在短時(shí)間內(nèi)會(huì)恢復(fù)成之前的狀態(tài)。

（5）罕見漂移。概念的異常改變。

（6）噪聲漂移。概念會(huì)由于數(shù)據(jù)中的噪聲隨機(jī)改變，但不是真正的概念漂移。

流式數(shù)據(jù)分類關(guān)注的是實(shí)例和所屬類標(biāo)簽之間最新的分類規(guī)則，故相關(guān)算法應(yīng)具備一定的遺忘能力，使得所學(xué)習(xí)的分類器模型與最新的概念相一致。當(dāng)概念漂移發(fā)生時(shí)，常用的幾種概念漂移處理技術(shù)如下［7］：

（1）滑動(dòng)窗口技術(shù)?；瑒?dòng)窗口作為一個(gè)緩沖區(qū)，在緩沖區(qū)內(nèi)的數(shù)據(jù)實(shí)例能反映當(dāng)前最新的數(shù)據(jù)分布狀況，且該窗口可以實(shí)時(shí)地對(duì)舊實(shí)例進(jìn)行遺棄。當(dāng)算法檢測(cè)到概念漂移時(shí)，縮小窗口范圍，否則適當(dāng)?shù)卦黾哟翱诖笮?，確保當(dāng)前訓(xùn)練數(shù)據(jù)與最新數(shù)據(jù)分布保持一致，從而確保分類模型的準(zhǔn)確性。

（2）概念漂移檢測(cè)技術(shù)。通過統(tǒng)計(jì)量比如誤差、分錯(cuò)率等來監(jiān)視數(shù)據(jù)分布的變化，是與給定分類器相合作的外部算法。如漂移檢測(cè)法（Drift de?tection method，DDM）［9］使用統(tǒng)計(jì)量分類錯(cuò)誤率和誤差標(biāo)準(zhǔn)差，設(shè)置警告和漂移閾值，該算法一旦檢測(cè)到數(shù)據(jù)分布開始變化并達(dá)到警告閾值，便向分類器模型發(fā)送警告信號(hào)，當(dāng)達(dá)到漂移閾值時(shí)，表示概念漂移已經(jīng)發(fā)生，需丟棄當(dāng)前分類器重新學(xué)習(xí)，DDM 算法能有效檢測(cè)到突變漂移，但不擅長(zhǎng)漸變漂移。基于Hoffding 邊界的在線漂移檢測(cè)方法［10］對(duì)DDM 算法進(jìn)行了改進(jìn)，其通過監(jiān)控一系列性能指標(biāo)的平均值，使用移動(dòng)平均線和加權(quán)移動(dòng)平均線，使得算法具備突變漂移和漸變漂移的檢測(cè)能力。

（3）集成學(xué)習(xí)技術(shù)［11］。將多個(gè)訓(xùn)練好的基分類器通過某種規(guī)則（投票、加權(quán)等）組合成一個(gè)新的分類器，從而得到比基分類器更好的分類效果。每個(gè)基分類器的訓(xùn)練數(shù)據(jù)不同，新的基分類器訓(xùn)練最近到達(dá)的數(shù)據(jù)，并淘汰掉性能最差的基分類器，使得集成分類器能適應(yīng)數(shù)據(jù)分布的變化。

由于流式數(shù)據(jù)自身的5 個(gè)特點(diǎn)，流式數(shù)據(jù)分類算法要求具備在資源受限的環(huán)境中實(shí)時(shí)地分析處理數(shù)據(jù)能力以及遇到概念漂移現(xiàn)象時(shí)具備快速恢復(fù)性和適應(yīng)性能力。存在的流式數(shù)據(jù)分類算法按所含分類器個(gè)數(shù)主要分類兩大類［11］：?jiǎn)文Ｐ退惴ê图煞诸愃惴ā?/p>

1.3 單模型算法

單模型算法，也稱為單分類器方法，通過對(duì)傳統(tǒng)批量分類算法的改進(jìn)和擴(kuò)展，并配備特定的概念漂移處理機(jī)制，使之能夠適應(yīng)流中數(shù)據(jù)的變化。根據(jù)傳統(tǒng)分類算法，單模型算法可以分為基于決策樹、支持向量機(jī)和貝葉斯模型等幾種類型。由于分類問題基本都是線性不可分問題，決策樹作為經(jīng)典的非線性分類器，已發(fā)展出許多基于決策樹的流式數(shù)據(jù)分類算法，同時(shí)支持向量機(jī)作為一個(gè)線性分類器，可以通過利用核函數(shù)將非線性數(shù)據(jù)映射到高維空間使其轉(zhuǎn)變?yōu)榫€性可分問題。兩類方法各有優(yōu)勢(shì)，且呈現(xiàn)出平行發(fā)展的趨勢(shì)，因此本文主要介紹基于決策樹和基于支持向量機(jī)的兩類單模型算法。

1.3.1 基于決策樹的單模型算法

決策樹算法的主要思想［12］：從包含待分類樣本全集的根節(jié)點(diǎn)開始，遞歸地將根節(jié)點(diǎn)或者葉子節(jié)點(diǎn)替換為內(nèi)部節(jié)點(diǎn)（決策節(jié)點(diǎn)）進(jìn)行樣本屬性的測(cè)試來生長(zhǎng)樹，直到當(dāng)前葉子節(jié)點(diǎn)沒有屬性可以劃分或?qū)儆谝粋€(gè)類時(shí)，算法完成對(duì)決策樹的構(gòu)造。

Domingos 等提出了快速?zèng)Q策樹（Very fast de?cision tree，VFDT）［13］，該算法在決策節(jié)點(diǎn)的屬性劃分上采用信息熵增益和基尼指數(shù)作為評(píng)判標(biāo)準(zhǔn)，僅掃描流式數(shù)據(jù)一次且不保存，能對(duì)大量數(shù)據(jù)流進(jìn)行分類，但其沒有考慮發(fā)生概念漂移的情況。針對(duì)VFDT 的該缺點(diǎn)，Hulten 等［14］提出了概念自適應(yīng)的快速?zèng)Q策樹（Concept adaptive VFDT，CVFDT），該算法在VFDT 基礎(chǔ)上，引入了處理概念漂移的滑動(dòng)窗口技術(shù)，其通過當(dāng)前窗口的流式數(shù)據(jù)建立臨時(shí)子樹，并在每次窗口滑動(dòng)時(shí)對(duì)決策樹進(jìn)行優(yōu)化更新。為了進(jìn)一步解決不確定數(shù)據(jù)流中概念漂移問題，劉志軍等［15］提出了自適應(yīng)快速?zèng)Q策樹（Adaptive fast decision tree，AFDT），該算法將數(shù)據(jù)流中的特征屬性分為不確定數(shù)值屬性和不確定分類屬性，并與概念漂移問題緊密聯(lián)系，通過不斷將不確定數(shù)值屬性轉(zhuǎn)化為不確定分類屬性來構(gòu)建決策樹。極速?zèng)Q策樹（Extremely fast de?cision tree，EFDT）［16］與VFDT 類似，不同之處是在對(duì)決策節(jié)點(diǎn)進(jìn)行屬性劃分時(shí)，使用Hoeffding 邊界來確定最佳屬性劃分帶來的增益，且最佳屬性劃分具有一定的置信度，使得其所需時(shí)間比VFDT 要長(zhǎng)，但分類準(zhǔn)確率有明顯提高。Pecori等［17］提出的流式模糊決策樹（Streaming fuzzy de?cision tree，SFDT）將模糊邏輯和模糊集理論中的一些元素與VFDT 相結(jié)合，利用均勻模糊劃分對(duì)每個(gè)輸入屬性進(jìn)行離散化，每個(gè)節(jié)點(diǎn)在分裂時(shí)以模糊信息增益作為度量指標(biāo)選擇最佳的輸入屬性，該算法相比于VFDT 較為復(fù)雜，但其能高效處理模糊數(shù)據(jù)和噪聲數(shù)據(jù)，有效提高分類的精度。

1.3.2 基于支持向量機(jī)的單模型算法

支持向量機(jī)的主要思想是［18］：針對(duì)線性不可分的情況，通過使用一個(gè)預(yù)先定義的核函數(shù)導(dǎo)出的非線性映射，將原始線性不可分的樣本映射到較高維的線性可分的特征空間中，在新的特征空間采用線性算法對(duì)樣本的非線性特征進(jìn)行線性分析。

Wang 等［19］提出了一種用于大規(guī)模內(nèi)核在線訓(xùn)練的預(yù)算隨機(jī)梯度下降算法（Budgeted stochas?tic gradient descent，BSGD），該算法通過迭代地接收標(biāo)記的流式數(shù)據(jù)，利用隨機(jī)梯度下降（Stochastic gradient descent，SGD）在相應(yīng)的目標(biāo)函數(shù)上更新模型權(quán)重以及動(dòng)態(tài)更新支持向量的數(shù)目來解決概念漂移問題，當(dāng)支持向量數(shù)目超出預(yù)定于上界時(shí)，使用刪除、合并以及投影3 種主要的預(yù)算維護(hù)策略來控制支持向量的數(shù)量。該算法能有效地處理大規(guī)模流式數(shù)據(jù)分類，而且擁有較高的分類準(zhǔn)確率。Le 等［20］提出了用于大規(guī)模在線學(xué)習(xí)的近似向量機(jī)算法。算法首先將整個(gè)輸入空間域用足夠小的單元重疊分區(qū)覆蓋，并構(gòu)造出相應(yīng)的覆蓋核心集，當(dāng)有新的流式數(shù)據(jù)實(shí)例到來時(shí)，找到包含該實(shí)例的單元并用相應(yīng)的核心點(diǎn)來近似這個(gè)實(shí)例，最后在近似表示該實(shí)例的核心點(diǎn)以及實(shí)例本身中通過伯努利隨機(jī)采樣選擇一個(gè)加入支持向量集中，實(shí)現(xiàn)對(duì)模型的增量更新。該算法利用當(dāng)前數(shù)據(jù)不斷增量更新模型，從而能靈活地處理概念漂移問題，并增加分類的準(zhǔn)確性。

上述基于決策樹的分類模型，易構(gòu)建且可解釋性強(qiáng)，可以結(jié)合概念漂移檢測(cè)技術(shù)處理應(yīng)對(duì)概念漂移問題。由于現(xiàn)實(shí)數(shù)據(jù)的高維性及不平衡特性，未來可以在決策節(jié)點(diǎn)分裂時(shí)的屬性劃分上做進(jìn)一步研究，以提高分類的準(zhǔn)確性?；谙蛄繖C(jī)的分類模型能學(xué)習(xí)特征空間的維數(shù)，利用在線學(xué)習(xí)技術(shù)增量的更新模型來解決概念漂移問題，但隨著數(shù)據(jù)量的增加，其支持向量的數(shù)目也會(huì)不斷增長(zhǎng)，進(jìn)而導(dǎo)致模型的可擴(kuò)展性差，未來可以在動(dòng)態(tài)更新支持向量數(shù)目、核心集覆蓋等問題上進(jìn)行研究，從而提高模型的準(zhǔn)確性及擴(kuò)展性。表1 概述了基于決策樹和基于SVM 的單模型算法優(yōu)缺點(diǎn)。

表1 基于決策樹和基于SVM 的單模型算法優(yōu)缺點(diǎn)Table 1 Merits and demerits of single model algorithms based on DT and SVM

1.4 集成分類算法

集成學(xué)習(xí)算法，也稱為多模型算法，根據(jù)不同時(shí)間段的數(shù)據(jù)訓(xùn)練N個(gè)基分類器，通過某種組合方式將各分類模型組合成集成分類器，并將各基分類器的結(jié)果按某種機(jī)制進(jìn)行綜合得到集成模型的結(jié)果，使得集成模型的魯棒性更強(qiáng)，并能夠靈活地處理概念漂移問題。根據(jù)模型每次處理數(shù)據(jù)的數(shù)據(jù)量，可分為基于數(shù)據(jù)塊的集成分類算法和基于單個(gè)實(shí)例的在線集成分類算法［21］。

1.4.1 基于數(shù)據(jù)塊的集成分類算法

基于數(shù)據(jù)塊集成的主要思想是［22］：數(shù)據(jù)以塊的形式進(jìn)行傳輸，每個(gè)塊包含固定數(shù)目的訓(xùn)練實(shí)例，根據(jù)訓(xùn)練生成N個(gè)基分類器，淘汰準(zhǔn)確率低的分類模型，在線更新集成模型，最后綜合各分類器的分類結(jié)果，達(dá)到快速適應(yīng)數(shù)據(jù)分布變化的目的。

文獻(xiàn)［23］中提出了一種準(zhǔn)確率更新集成算法（Accuracy updated ensemble，AUE），該算法采用大小為n的窗口和增量的基學(xué)習(xí)器，使得集成模型中基分類器都可根據(jù)當(dāng)前塊的訓(xùn)練實(shí)例增量式更新，從而能更快速地適應(yīng)突變漂移。文獻(xiàn)［24］提出的CVFDT 更新集成算法（CVFDT update en?semble，CUE）使用VFDT 訓(xùn)練基分類器，用最新數(shù)據(jù)塊更新準(zhǔn)確率低于隨機(jī)猜測(cè)準(zhǔn)確率的基分類器，并對(duì)訓(xùn)練數(shù)據(jù)采用bagging 操作增加基分類器間相異度，其分類準(zhǔn)確率和概念漂移適應(yīng)度都較高?；谛畔㈧氐募煞诸愃惴ǎ‥nsemble classi?fication algorithm based on information entropy，ECBE）［25］根據(jù)分類前后熵值差異檢測(cè)概念漂移并決定各基分類器的權(quán)值，通過相鄰概念漂移周期內(nèi)各基分類器權(quán)值信息得出概念穩(wěn)定時(shí)的權(quán)值下界，移除權(quán)值低于該下界的基分類器，既提高了分類準(zhǔn)確率又能快速適應(yīng)新概念。Sarnovsky 等［26］提出了多樣化動(dòng)態(tài)類加權(quán)集成算法。該算法維護(hù)可變數(shù)量的異構(gòu)的基分類器，根據(jù)基分類器的性能動(dòng)態(tài)調(diào)整其權(quán)重，一旦權(quán)重低于給定閾值，即將該分類器從集成模型中移除。通過多樣性調(diào)整投票的組合規(guī)則以及各基分類器預(yù)測(cè)的聚合最終獲得集成模型結(jié)果，若結(jié)果不正確，則向集成模型中添加新的隨機(jī)基分類器。由于基分類器的自適應(yīng)機(jī)制和多樣化，使得該集成模型能有效處理各類型的概念漂移。

1.4.2 基于單個(gè)實(shí)例的在線集成分類算法

基于單個(gè)實(shí)例的在線集成主要思想是［27］：數(shù)據(jù)流中的實(shí)例單獨(dú)到達(dá)，一次僅處理一個(gè)訓(xùn)練實(shí)例并對(duì)其進(jìn)行增量學(xué)習(xí)，不斷地修正集成分類模型，從而可以在有限的時(shí)間和內(nèi)存下對(duì)數(shù)據(jù)流分類做出快速反應(yīng)。

Zhai 等［28］提出的EBPegasos 集成算法以在線核SVM 作為基分類器，檢測(cè)到概念漂移時(shí)，首先判斷漂移對(duì)各基分類器的影響，若影響較大，則需移除性能最差的基分類器，并創(chuàng)建新的基分類器，若影響不大，則對(duì)各基分類器進(jìn)行增量更新，使得集成模型在遺忘和利用舊概念之間達(dá)成良好的平衡。Shan 等［29］提出的在線主動(dòng)學(xué)習(xí)集成模型（On?line active learning ensemble，OALEnsemble）由一個(gè)穩(wěn)定分類器和一定數(shù)目的動(dòng)態(tài)分類器構(gòu)成，穩(wěn)定分類器根據(jù)數(shù)據(jù)流分布變化的長(zhǎng)期趨勢(shì)，捕捉漸變漂移，動(dòng)態(tài)分類器根據(jù)數(shù)據(jù)流最新的變化，及時(shí)更新基分類器，捕捉突變漂移，使得該算法對(duì)概念漂移有較強(qiáng)的處理應(yīng)對(duì)能力。Canzian 等［30］提出了一種感知器加權(quán)多數(shù)投票算法，該算法采用一組分布式的學(xué)習(xí)器，每個(gè)學(xué)習(xí)器可以采用不同類型的局部分類器生成局部預(yù)測(cè)，收集并使用加權(quán)多數(shù)投票規(guī)則聚合其余學(xué)習(xí)器的局部預(yù)測(cè)以生成最終預(yù)測(cè)，最后根據(jù)學(xué)習(xí)器的預(yù)測(cè)結(jié)果，通過感知器學(xué)習(xí)規(guī)則來動(dòng)態(tài)更新其聚合權(quán)值，使其能靈活應(yīng)該概念漂移問題。該算法能對(duì)分布式、異構(gòu)以及動(dòng)態(tài)的數(shù)據(jù)進(jìn)行分類且性能較高。

集成學(xué)習(xí)和在線集成學(xué)習(xí)都是通過聚合策略將多個(gè)學(xué)習(xí)器進(jìn)行聚合從而得到集成結(jié)果，通過在學(xué)習(xí)過程中結(jié)合概念漂移檢測(cè)技術(shù)監(jiān)測(cè)流式數(shù)據(jù)分布的變化來快速適應(yīng)各類型的概念漂移，但這使得算法性能在一定程度上受到漂移檢測(cè)技術(shù)的限制。為了進(jìn)一步提高和改善集成模型的準(zhǔn)確率和性能，未來可以向基分類器的多樣化和高魯棒性的漂移檢測(cè)算法發(fā)展研究。

2 大數(shù)據(jù)聚類

大數(shù)據(jù)聚類是一種無(wú)監(jiān)督學(xué)習(xí)方法［31］，即不需要預(yù)先定義類別和訓(xùn)練樣本，其目的是將未知的數(shù)據(jù)集分成若干簇，使得同一簇中的數(shù)據(jù)點(diǎn)具有盡可能大的相似度，而不同簇中的數(shù)據(jù)點(diǎn)具有盡可能大的相異性。聚類過程主要有兩個(gè)階段：（1）定義相似函數(shù)，將其作為判斷數(shù)據(jù)之間是否相似的依據(jù)；（2）選擇合適的聚類算法將數(shù)據(jù)對(duì)象劃分到不同的簇中。大數(shù)據(jù)聚類分析方法可分為單機(jī)聚類方法以及多機(jī)器集群聚類方法［32］。單機(jī)聚類方法的實(shí)現(xiàn)主要是通過對(duì)經(jīng)典聚類算法進(jìn)行優(yōu)化、擴(kuò)展以及對(duì)數(shù)據(jù)集進(jìn)行降維或采樣等處理，而主流的多機(jī)聚類方法則主要體現(xiàn)在體系結(jié)構(gòu)等方面，其底層聚類算法與經(jīng)典聚類算法無(wú)本質(zhì)差別。

2.1 單機(jī)聚類

為解決處理大規(guī)模數(shù)據(jù)聚類的需求，單機(jī)聚類算法也一直在演進(jìn)，現(xiàn)在的單機(jī)聚類主要有2 個(gè)研究方向：通過改進(jìn)、優(yōu)化經(jīng)典的聚類算法，使算法本身即具備精確的聚類效果又有良好的可擴(kuò)展性，或是在不改變數(shù)據(jù)分布特征的前提下，直接對(duì)待處理的數(shù)據(jù)集進(jìn)行采樣或降維等處理，即通過減少數(shù)據(jù)量或縮小整個(gè)數(shù)據(jù)集的形式來處理大規(guī)模數(shù)據(jù)。

在經(jīng)典聚類算法基礎(chǔ)上進(jìn)行改進(jìn)、優(yōu)化的可擴(kuò)展單機(jī)聚類算法，如Monath 等［33］提出的子聚類組件算法（Sub?cluster component algorithm，SCC），是一種凝聚型層次聚類，算法使用鏈接函數(shù)來衡量?jī)山M點(diǎn)的相似性，以最佳優(yōu)先方式進(jìn)行迭代，即迭代從最易決定相似性高低的簇開始，并延長(zhǎng)相似度衡量困難的決定，直至其易判斷，且算法的每次迭代都會(huì)以不同的粒度生成簇。該算法能生成高質(zhì)量的聚類結(jié)果，且可以擴(kuò)展到數(shù)十億數(shù)據(jù)點(diǎn)而不犧牲質(zhì)量。Kobren 等［34］提出了一種純度增強(qiáng)旋轉(zhuǎn)的層級(jí)聚類算法（Purity enhancing rotations for clus?ter hierarchies，PERCH），算法將新數(shù)據(jù)點(diǎn)路由到葉子上，以增量的方式進(jìn)行樹結(jié)構(gòu)的構(gòu)建，通過樹的旋轉(zhuǎn)糾正貪婪增量聚類過程中的錯(cuò)誤，提高了子樹的純度、聚類的質(zhì)量以及算法執(zhí)行速度，并引入促進(jìn)平衡的旋轉(zhuǎn)，使得算法可擴(kuò)展到大量數(shù)據(jù)點(diǎn)N和集群K的極端聚類上。

對(duì)待處理數(shù)據(jù)集進(jìn)行采樣或降維等處理的單機(jī)聚類算法，如Zhao 等［35］提出了分層抽樣加擴(kuò)展的模糊C?means 聚類算法。該算法首先通過局部敏感哈希技術(shù)將相似數(shù)據(jù)劃分到一起，粗略地將大規(guī)模數(shù)據(jù)劃分成若干層，并從各層中隨機(jī)抽取數(shù)據(jù)對(duì)象形成代表性樣本；其次在采樣的樣本上使用模糊C?means 聚類算法生成局部聚類結(jié)果；最后使用最近鄰近標(biāo)記實(shí)現(xiàn)樣本外擴(kuò)展，即將樣本外對(duì)象分配到距它們最近的、已確定的簇中。該算法通過對(duì)數(shù)據(jù)進(jìn)行分層采樣，保持了原始大規(guī)模數(shù)據(jù)集中的數(shù)據(jù)分布特征，提高了聚類質(zhì)量和計(jì)算效率。Chen 等［36］提出了一種基于深度學(xué)習(xí)的深度流形聚類方法（Deep multi?manifold clustering，DMC），由于位于流形局部的點(diǎn)具有相似的表示，算法首先通過迭代最小化局部保持目標(biāo)函數(shù)使得學(xué)習(xí)到的表示有意義，其次通過直接對(duì)表示執(zhí)行K?means 聚類算法確定聚類中心，并使用面向聚類的目標(biāo)函數(shù)，即根據(jù)表示到各質(zhì)心的接近程度來懲罰表示，來指導(dǎo)模型提取特定于聚類的表示，最后將兩個(gè)目標(biāo)函數(shù)集合為一個(gè)聯(lián)合損失函數(shù)，使用反向傳播不斷地對(duì)其優(yōu)化，使得算法具有更精確的聚類效果以及更強(qiáng)大的性能。Mautz 等［37］提出了一種在高維空間中具有輕量級(jí)參數(shù)的非冗余K?means 聚類算法（Non?redundant K?means，Nr?K?means），該算法尋找數(shù)據(jù)集中相互正交的子空間，確保發(fā)現(xiàn)的聚類代表數(shù)據(jù)的不同視圖，并在所有子空間中優(yōu)K?means的目標(biāo)函數(shù)，從而識(shí)別不同子空間中的多個(gè)非冗余簇，即數(shù)據(jù)對(duì)象在不同子空間中屬于不同簇，可進(jìn)一步分析各個(gè)非冗余簇之間的關(guān)系。算法引入的噪音空間能過濾不能在所有子空間中表示良好的數(shù)據(jù)特性，使得算法具備同時(shí)降維的能力以及高效地執(zhí)行速度。

2.2 多機(jī)聚類

多機(jī)聚類首先將待處理數(shù)據(jù)劃分成若干塊，分別加載到不同機(jī)器上執(zhí)行分組聚類，其次綜合分組聚類結(jié)果并根據(jù)分析結(jié)果自動(dòng)改進(jìn)聚類過程，最后再重新進(jìn)行分組聚類，直到綜合聚類結(jié)果符合一定的終止條件。多機(jī)聚類具有較高的處理速度和可擴(kuò)展性，但增加了機(jī)器間的通信成本，因此優(yōu)秀的多機(jī)聚類算法需在盡可能少的通信成本下，獲得較好的聚類效果。多機(jī)聚類可以分為并行聚類和分布式聚類［38］。

2.2.1 并行聚類

并行聚類主要是通過縱向擴(kuò)展平臺(tái)實(shí)現(xiàn)單機(jī)聚類算法的并行，常見的縱向擴(kuò)展平臺(tái)如多核CPU，圖形處理單元（Graphics processing unit，GPU）等。

基于多核CPU 的聚類算法，如Hadian 等［39］提出了基于多核CPU 的并行K?means 算法，該算法有兩個(gè)線程集組成：主線程和塊聚類線程。主線程負(fù)責(zé)在讀取數(shù)據(jù)集時(shí)按預(yù)定義的大小劃分塊，并使用隊(duì)列概念將塊發(fā)送給塊聚類線程。塊聚類線程接受塊后使用K?means 算法進(jìn)行聚類，得到當(dāng)前塊的質(zhì)心并存儲(chǔ)入全局質(zhì)心列表中。所有塊聚類完成時(shí)，主線程加載全局質(zhì)心列表，通過K?means 算法對(duì)質(zhì)心進(jìn)行聚類，形成最終聚類，在12 核機(jī)器上的評(píng)估結(jié)果顯示，該算法在產(chǎn)生的聚類質(zhì)量上與K?means、K?means++相同但運(yùn)行速度快得多。Er?dem 等［40］提出了一種多核具有噪聲的基于密度的空間聚類算法（Multicore fast density?based spatial clusteringofapplicationswithnoise，M?FDBSCAN），該算法首先將二維模糊數(shù)據(jù)對(duì)象集按核數(shù)進(jìn)行劃分，其次對(duì)每個(gè)子集并行使用FD?BSCAN 算法進(jìn)行聚類，獲得部分確定聚類區(qū)域，最后合并成最終聚類區(qū)域，該算法性能隨著核數(shù)的增加呈線性增長(zhǎng)，處理速度明顯增加。

基于GPU 的聚類算法，如Melo 等［41］提出了基于GPU 并行化的點(diǎn)排序識(shí)別聚類結(jié)構(gòu)（Ordering points to identify the clustering structure，OPTICS）實(shí)現(xiàn)方式，OPTICS 并行化有兩個(gè)階段，即圖形構(gòu)造和執(zhí)行OPTICS 算法，其中執(zhí)行OPTICS 時(shí)間較短，重點(diǎn)在于圖形構(gòu)造的并行化。算法使用3 個(gè)向量分別存儲(chǔ)頂點(diǎn)、鄰接列表節(jié)點(diǎn)以及邊的權(quán)值。在構(gòu)造成圖時(shí)，并行地對(duì)這3 個(gè)向量進(jìn)行頂點(diǎn)度計(jì)算、鄰接索引計(jì)算、鄰接表組裝和排序操作，實(shí)驗(yàn)結(jié)果表明，該方法不僅降低了OPTICS 算法的復(fù)雜度，而且執(zhí)行速度比基于CPU 的版本快得多。

前文的幾種基于多核CPU 以及基于GPU 的聚類算法中，多核CPU 適用于復(fù)雜程度高的算法，GPU 適用于低復(fù)雜度、高計(jì)算量的算法。為進(jìn)一步優(yōu)化算法的性能，未來可以探索和設(shè)計(jì)將多核CPU 與GPU 并行計(jì)算相結(jié)合，同時(shí)利用兩者優(yōu)勢(shì)的算法。

2.2.2 分布式聚類

分布式聚類使用分布式計(jì)算框架自動(dòng)對(duì)數(shù)據(jù)集進(jìn)行劃分和分配，并在集群上實(shí)現(xiàn)聚類算法的并行，更適合處理大數(shù)據(jù)聚類，常見的分布式計(jì)算框架有MapReduce、Spark 等。

Li 等［42］提出的Multiplex K?means 算法，使用MapReduce 并行執(zhí)行多個(gè)具有不同質(zhì)心組的K?means 進(jìn)程，Map 函數(shù)負(fù)責(zé)計(jì)算當(dāng)前點(diǎn)與所有質(zhì)心間的距離，Reduce 函數(shù)負(fù)責(zé)質(zhì)心的更新，每一次迭代根據(jù)聚類內(nèi)總變異值對(duì)其進(jìn)行評(píng)估，對(duì)聚類質(zhì)量差的K?means 過程進(jìn)行剪枝，避免無(wú)用計(jì)算，對(duì)保留的高質(zhì)量質(zhì)心群采用啟發(fā)式方法生成新的質(zhì)心群，擴(kuò)大聚類結(jié)果的搜索范圍，避免陷入局部最優(yōu)解，重復(fù)此過程獲得最終聚類結(jié)果，該算法相比于串行的K?means 算法有更好的效果，也適用于大數(shù)據(jù)集聚類。He 等［43］提出了一種MR?DBSCAN 算法，該算法根據(jù)空間鄰近度對(duì)數(shù)據(jù)進(jìn)行分區(qū)，并在各分區(qū)獨(dú)立執(zhí)行DB?SCAN 聚類算法，全局聚類結(jié)果由局部聚類結(jié)果聚合而成，該算法子程序完全并行且可擴(kuò)展性良好。胡健等［44］提出的一種基于改進(jìn)的果蠅算法（Improved fruit fly optimization algorithm，IFOA）的并行密度聚類算法（The density?based cluster?ing algorithm by using IFOA based on MapRe?duce，MR?DBIFOA），使用K?維樹和貪心算法對(duì)數(shù)據(jù)進(jìn)行劃分，使得各分區(qū)內(nèi)數(shù)據(jù)對(duì)象數(shù)量相近，并通過基于自適應(yīng)搜索策略和聚類判定函數(shù)IFOA 對(duì)局部聚類的參數(shù)進(jìn)行態(tài)尋優(yōu)，提升局部聚類效果，并結(jié)合MapReduce 實(shí)現(xiàn)局部聚類的并行計(jì)算，合并得到全局聚類結(jié)果。該算法在大數(shù)據(jù)集下的聚類效果、尋優(yōu)能力和魯棒性方面效果良好并具有較強(qiáng)的并行性能。

基于Spark 的聚類算法，如王博文等［45］提出利用Spark 設(shè)計(jì)的并行K?means 算法，首先隨機(jī)選取多個(gè)數(shù)據(jù)點(diǎn)作為質(zhì)心，其次在一個(gè)彈性分布式數(shù)據(jù)集（Resilient distributed dataset，RDD）變換中，并行計(jì)算當(dāng)前數(shù)據(jù)實(shí)例與各質(zhì)心的距離，將其劃分到距離最近質(zhì)心的所屬類簇，接著將各類簇的均值點(diǎn)更新為新質(zhì)心，若相鄰兩次質(zhì)心的誤差小于給定閾值，則得到最終聚類結(jié)果，反之，再次計(jì)算距離進(jìn)行迭代。該算法有不錯(cuò)的聚類效果和并行能力。Liu等［46］提出了一種基于Spark RDD 模型的分布式密度峰值聚類算法。該算法首先預(yù)定義局部密度閾值P和密度較高點(diǎn)的距離閾值D，其次通過調(diào)用Spark 的圖形計(jì)算API（GraphX）生成圖并計(jì)算截?cái)嗑嚯x，然后計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的局部密度p和與密度高點(diǎn)的距離閾值d，最后選擇p>P且d>D的數(shù)據(jù)點(diǎn)作為聚類中心，選擇pD的數(shù)據(jù)點(diǎn)作為隔離點(diǎn)，將剩余點(diǎn)分配到與其最近的聚類中心，從而完成聚類，該算法比使用MapReduce 實(shí)現(xiàn)的密度峰值聚類算法快10 倍，能更高效地處理大數(shù)據(jù)聚類。

基于分布式計(jì)算框架的算法能有效處理大數(shù)據(jù)聚類且擴(kuò)展性好，但其消耗的軟硬件資源較多，未來可以向著在消耗軟硬件資較少的前提下實(shí)現(xiàn)高效、精確及可擴(kuò)展的大數(shù)據(jù)聚類算法的方向進(jìn)行研究。

3 大數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘

大數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘指從大量數(shù)據(jù)中發(fā)現(xiàn)隱藏的信息關(guān)聯(lián)性，并通過分析該關(guān)聯(lián)性幫助決策者制定正確的決策。關(guān)聯(lián)規(guī)則的強(qiáng)度可用支持度和置信度來衡量［47］：若有規(guī)則X→Y，則支持度為事務(wù)X和Y在事務(wù)數(shù)據(jù)庫(kù)中出現(xiàn)的頻率，用于判斷該規(guī)則是否有利用價(jià)值；置信度為當(dāng)事務(wù)X出現(xiàn)時(shí)事務(wù)Y出現(xiàn)的頻率，用于判斷該規(guī)則的正確度。關(guān)聯(lián)規(guī)則挖掘主要有兩個(gè)步驟：（1）從數(shù)據(jù)中找出支持度不小于最小支持度的規(guī)則，稱為頻繁模式或頻繁項(xiàng)集；（2）從頻繁模式中找出置信度不小于最小置信度閾值的強(qiáng)關(guān)聯(lián)規(guī)則，其中重點(diǎn)在于頻繁模式的挖掘。關(guān)聯(lián)規(guī)則挖掘可分為基本的單機(jī)關(guān)聯(lián)規(guī)則挖掘和基于分布式計(jì)算框架的多機(jī)并行關(guān)聯(lián)規(guī)則挖掘［48］。

3.1 單機(jī)關(guān)聯(lián)規(guī)則挖掘

單機(jī)挖掘的基本方法有3 種：基于多候選產(chǎn)生的Apriori 算法［49］、基于模式增長(zhǎng)的頻繁模式增長(zhǎng)算法（Frequent?pattern growth，F(xiàn)P?growth）［50］和基于垂直格式的Eclat 算法［51］，其余的單機(jī)算法大都是在基本方法的基礎(chǔ)上，通過改善存儲(chǔ)結(jié)構(gòu)快速高效地對(duì)候選集剪枝以及快速獲取候選集支持度而提出來的。

Apriori 算法依據(jù)兩個(gè)先驗(yàn)性質(zhì)，即非頻繁項(xiàng)集的超集一定是非頻繁項(xiàng)集以及頻繁項(xiàng)集的子集必為頻繁項(xiàng)集，對(duì)事務(wù)數(shù)據(jù)庫(kù)進(jìn)行一遍掃描，并根據(jù)MinSup 剪枝得到頻繁1 項(xiàng)集，然后連接頻繁1項(xiàng)集得到候選2 項(xiàng)集，再次掃描數(shù)據(jù)庫(kù)剪枝獲得頻繁2 項(xiàng)集，以此類推進(jìn)行迭代，直到無(wú)候選項(xiàng)集產(chǎn)生為止，最后根據(jù)MinCon 篩選頻繁項(xiàng)集得到強(qiáng)關(guān)聯(lián)規(guī)則。該算法的優(yōu)點(diǎn)在于對(duì)每次迭代進(jìn)行剪枝，在一定程度上減少了計(jì)算量，但每次剪枝需訪問數(shù)據(jù)庫(kù)且算法執(zhí)行過程中產(chǎn)生了大量候選項(xiàng)集，其導(dǎo)致算法的執(zhí)行效率低下。

FP?growth 算法主要包含兩個(gè)階段：（1）構(gòu)造FP?Tree，掃描一次數(shù)據(jù)庫(kù)得到頻繁1 項(xiàng)集，再次掃描去除事務(wù)中非頻繁項(xiàng)目并將剩余項(xiàng)目按支持度遞減的順序進(jìn)行排列，初始根節(jié)點(diǎn)為空，將事務(wù)依次插入到FP?Tree 中，每條事務(wù)在插入時(shí)，事務(wù)的第1 項(xiàng)作為根節(jié)點(diǎn)的子節(jié)點(diǎn)插入，若已含該節(jié)點(diǎn)，則只需將該節(jié)點(diǎn)的節(jié)點(diǎn)計(jì)數(shù)加1，否則將該項(xiàng)新生為根節(jié)點(diǎn)的子節(jié)點(diǎn)插入，在插入事務(wù)的第2 項(xiàng)時(shí)，將其作為已插入節(jié)點(diǎn)的子節(jié)點(diǎn)并按相同方法進(jìn)行插入，直至該事務(wù)的所有項(xiàng)目插入完畢。（2）自底向上地對(duì)FP?Tree 進(jìn)行遞歸挖掘，從頻繁1 項(xiàng)集中支持度最低的項(xiàng)目作為初始后綴開始，在FP?Tree中查找該后綴的條件模式基并構(gòu)造其條件FP?Tree，遞歸地挖掘該條件FP?Tree 的頻繁模式并將其與初始后綴連接實(shí)現(xiàn)模式增長(zhǎng)。該算法相較于Apriori 有兩個(gè)優(yōu)勢(shì)，即不產(chǎn)生候選項(xiàng)集以及只訪問數(shù)據(jù)庫(kù)2 次，其不足之處在于壓縮原始數(shù)據(jù)的FP?Tree 需全部裝載入內(nèi)存，當(dāng)數(shù)據(jù)量大時(shí)，會(huì)導(dǎo)致計(jì)算能力受限。

Apriori 和FP?growth 算法都以水平數(shù)據(jù)格式{TID:itemset}挖掘頻繁項(xiàng)集,而Eclat 算法采用的是垂直數(shù)據(jù)格式{item:TIDSET}。在支持度計(jì)算上，水平數(shù)據(jù)格式需訪問一次數(shù)據(jù)庫(kù)得到而垂直數(shù)據(jù)格式中支持度即為該項(xiàng)目的TID 集長(zhǎng)度。Eclat算法通過遍歷1 次事務(wù)數(shù)據(jù)庫(kù)，將數(shù)據(jù)格式轉(zhuǎn)換為垂直格式，并通過支持度計(jì)算和剪枝得到頻繁1 項(xiàng)集，將頻繁1 項(xiàng)集求交集、剪枝得到頻繁2 項(xiàng)集，迭代此過程直至無(wú)候選項(xiàng)集產(chǎn)生。該算法與Apriori算法都是通過頻繁k項(xiàng)集生成頻繁k+1 項(xiàng)集，但其只需訪問數(shù)據(jù)庫(kù)1 次，加快了候選項(xiàng)集的產(chǎn)生，且優(yōu)化了支持度的計(jì)算方式，3 種基本方法的優(yōu)缺點(diǎn)對(duì)比見表2。

吳磊［48］提出的基于事務(wù)映射區(qū)間求交算法（Interval interaction and transaction mapping，IITM）在FP?Tree 基礎(chǔ)上，采用深度優(yōu)先遍歷為每個(gè)節(jié)點(diǎn)生成區(qū)間，獲得壓縮程度更強(qiáng)的頻繁1 項(xiàng)集區(qū)間列表，并使用哈希結(jié)構(gòu)進(jìn)行存儲(chǔ)。IITM 使用頻繁1 項(xiàng)集和頻繁k項(xiàng)集來生成候選k+1 項(xiàng)集，并使用由頻繁k項(xiàng)集生成的布隆過濾器對(duì)候選項(xiàng)集進(jìn)行高效地剪枝，在支持度計(jì)算上，由兩個(gè)區(qū)間列表求交得到候選k+1 項(xiàng)集的區(qū)間列表，從區(qū)間列表中即可獲得支持度，并篩選出頻繁k+1 項(xiàng)集。該算法使用區(qū)間進(jìn)一步壓縮數(shù)據(jù)，引入布隆過濾器降低候選項(xiàng)集的數(shù)目，通過區(qū)間求交快速獲取候選項(xiàng)集的支持度，使得算法具有較高的效率。

3.2 多機(jī)并行關(guān)聯(lián)規(guī)則挖掘

多機(jī)并行關(guān)聯(lián)規(guī)則挖掘指將數(shù)據(jù)進(jìn)行劃分并分配到各節(jié)點(diǎn)當(dāng)中，每個(gè)節(jié)點(diǎn)運(yùn)用單機(jī)上的挖掘方法獨(dú)立地完成頻繁模式的挖掘，最后將各節(jié)點(diǎn)結(jié)果進(jìn)行匯總得到最終結(jié)果，適合于大數(shù)據(jù)上的關(guān)聯(lián)規(guī)則挖掘。常見的多機(jī)并行挖掘方式按照大數(shù)據(jù)處理平臺(tái)的不同大致可分為基于GPU 的并行關(guān)聯(lián)規(guī)則挖掘、基于MapReduce 的并行關(guān)聯(lián)規(guī)則挖掘以及基于Spark 的并行關(guān)聯(lián)規(guī)則挖掘。

3.2.1 基于GPU 的并行關(guān)聯(lián)規(guī)則挖掘

張旭［52］提出了基于GPU 的并行關(guān)聯(lián)規(guī)則挖掘算法，該算法利用統(tǒng)一計(jì)算框架（Compute unified device architecture，CUDA）編程模型，在CPU 主機(jī)端完成邏輯復(fù)雜的候選項(xiàng)集生成，在GPU 設(shè)備端并行計(jì)算邏輯簡(jiǎn)單但計(jì)算量大的候選項(xiàng)集的支持度。算法依此主要分為兩個(gè)階段：（1）在CPU 中進(jìn)行，在深度為k的前綴樹中，找到前k-1 項(xiàng)相同的兩個(gè)頻繁k項(xiàng)集，將它們的第k項(xiàng)按字典順序進(jìn)行連接，得到候選k+1 項(xiàng)集，并將存儲(chǔ)結(jié)構(gòu)由前綴樹轉(zhuǎn)換為位表結(jié)構(gòu)，以便在GPU 中進(jìn)行計(jì)算；（2）在GPU 中進(jìn)行，將兩個(gè)頻繁k項(xiàng)集的位表進(jìn)行按位與運(yùn)算得到候選k+1 項(xiàng)集的位表，使用多個(gè)并行線程計(jì)算其位表中“1”的數(shù)目，得出候選項(xiàng)集的支持度并判斷其是否為頻繁項(xiàng)集。該算法通過GPU 加速了支持度計(jì)算速率，且算法的性能隨著測(cè)試數(shù)據(jù)集規(guī)模的增長(zhǎng)逐步擴(kuò)大。

Chon 等［53］提出了基于GPU 的GMiner 算法，該算法采用第1 層遍歷策略（Travesal from the first level，TEL）和中間層跳轉(zhuǎn)策略（Hopping from the intermediate level，HIL）充分發(fā)揮GPU 的計(jì)算能力。TEL 將頻繁1 項(xiàng)集映射到事務(wù)數(shù)據(jù)塊內(nèi)并劃分得到若干分區(qū)，將分區(qū)和事務(wù)數(shù)據(jù)塊傳送至GPU 中，在GPU 中通過按位與得到候選項(xiàng)集的部分支持度，并傳送入主存進(jìn)行匯總。TEL 僅對(duì)頻繁1 項(xiàng)集進(jìn)行大量計(jì)算來挖掘全部頻繁項(xiàng)集，在挖掘較長(zhǎng)的頻繁項(xiàng)集時(shí)性能較低，而HIL 策略通過使用更多GPU 顯存來提高此性能。該算法充分利用GPU 的計(jì)算能力，且其性能隨著GPU 數(shù)量的增加呈線性增長(zhǎng)，適用于大規(guī)模數(shù)據(jù)集的挖掘。

Djenouri 等［54］提出的CGSS（Single scan on multiple cluster nodes equipped with GPUs）算法結(jié)合了集群和GPU 的能力，將挖掘過程進(jìn)一步加速。在CGSS 中，集群采用主從模式且每臺(tái)機(jī)器都配有GPU 設(shè)備端，該算法主要分為5 個(gè)過程：（1）簡(jiǎn)單分區(qū)。主節(jié)點(diǎn)將事務(wù)數(shù)據(jù)庫(kù)等分成p個(gè)分區(qū)分配工作節(jié)點(diǎn)。（2）智能分區(qū)。根據(jù)工作節(jié)點(diǎn)GPU 中線程塊數(shù)量r，各分區(qū)通過迭代將相鄰事務(wù)依次分配給不同的線程塊，劃分成r個(gè)子分區(qū)。（3）各線程塊生成所有可能的候選項(xiàng)集，并存入線程塊的本地哈希表中。（4）合并。每個(gè)GPU 工作節(jié)點(diǎn)合并其線程塊的本地哈希表創(chuàng)建GPU 本地哈希表，主節(jié)點(diǎn)在GPU 本地哈希表的基礎(chǔ)上創(chuàng)建1 個(gè)全局哈希表。（5）生成頻繁項(xiàng)集。該算法利用分區(qū)策略解決了集群負(fù)載的不均衡以及減少了線程發(fā)散，在面向大數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘上具有更高的性能和并行能力。

3.2.2 基于MapReduce 的并行關(guān)聯(lián)規(guī)則挖掘

（1）并行Apriori 算法

Huang 等［55］提出的基于MapReduce 的Smart?Cache 算法，由兩個(gè)MapReduce 作業(yè)組成：第1 個(gè)是在Map 函數(shù)中，降低MinSup 得到局部支持度，根據(jù)局部支持度執(zhí)行局部挖掘算法，將支持度在兩者之間的項(xiàng)集存入Cache 中，通過簡(jiǎn)單的線性回歸分析出Cache 容量呈非線性增長(zhǎng)的轉(zhuǎn)折點(diǎn)，即最佳局部支持度閾值，將根據(jù)局部支持度篩選得到的局部頻繁項(xiàng)集以及支持度信息寫入Hadoop 分布式文件系統(tǒng)（Hadoop distributed filesystem，HDFS）的Cache 文件中，Reduce 將Map 的結(jié)果進(jìn)行匯總；第2 個(gè)是Map 任務(wù)在HDFS 的Cache 文件中查找支持度信息，Reduce 任務(wù)通過合并各個(gè)候選項(xiàng)集的支持度得到全局頻繁項(xiàng)集。該算法使用局部支持度提高了結(jié)果的準(zhǔn)確性，通過存儲(chǔ)第1 個(gè)MapRe?duce 產(chǎn)生的支持度信息，大大減少了第2 階段的計(jì)算量，提高了執(zhí)行效率和算法性能。

Chon 等［56］提出的BIGMiner（BIG data pat?tern miner）算法，包括預(yù)計(jì)算和挖掘頻繁k 項(xiàng)集2個(gè)階段。預(yù)計(jì)算階段根據(jù)預(yù)定義集合長(zhǎng)度將頻繁1 項(xiàng)集劃分成互不相交的集合，枚舉出所有子集，生成垂直數(shù)據(jù)格式的事物塊。挖掘階段中Map 任務(wù)根據(jù)頻繁k項(xiàng)集和事務(wù)塊生成候選k+1 項(xiàng)集及局部支持度，Reduce 任務(wù)合并局部支持度獲取頻繁k+1 項(xiàng)集，并將其廣播到所有機(jī)器，用于下次迭代時(shí)Map 任務(wù)中。該算法在執(zhí)行過程中不產(chǎn)生中間數(shù)據(jù)，且只需廣播頻繁k項(xiàng)集的網(wǎng)絡(luò)開銷，使得算法伸縮性好，在大規(guī)模數(shù)據(jù)上具有較高性能。

（2）并行FP?growth 算法

Xun 等［57］提出了基于頻繁完全樹（Frequent items ultrametric tree，F(xiàn)UI?Tree）的FiDoop 算法，F(xiàn)UI?Tree 相較于FP?Tree 最大的優(yōu)勢(shì)在于避免了遞歸遍歷。FiDoop 算法首先通過2 次掃描事物數(shù)據(jù)庫(kù)，將各條事務(wù)中非頻繁項(xiàng)目丟棄，得到含有k個(gè)頻繁項(xiàng)目的k項(xiàng)集；其次將k項(xiàng)集分解成2～（k-1）個(gè)項(xiàng)集，使用長(zhǎng)度相同的項(xiàng)集構(gòu)造FUI?Tree；最后通過FUI?Tree 的葉節(jié)點(diǎn)計(jì)數(shù)便可獲得所有頻繁項(xiàng)集。該算法實(shí)現(xiàn)了自動(dòng)并行化，能夠在大型集群上并行地進(jìn)行數(shù)據(jù)挖掘，進(jìn)一步加快了數(shù)據(jù)挖掘速度，面對(duì)高維數(shù)據(jù)集時(shí)，Xun 等［57］還提出了通過維度減少的方法來提高挖掘效率的FiDoop?HD算法。

Wang 等［58］提出了一種基于多項(xiàng)目支持的頻繁模式挖掘算法（Multiple item support frequent patterns，MISFP?growth）。該算法首先在數(shù)據(jù)預(yù)處理階段引入預(yù)定義的多項(xiàng)目支持度；其次用1 個(gè)MapReduce 作業(yè)完成對(duì)各項(xiàng)目實(shí)際支持度的計(jì)算，得到多項(xiàng)支持的最小值，刪去事務(wù)中低于最小多項(xiàng)支持的項(xiàng)目，并將剩余各項(xiàng)目按實(shí)際支持度大小降序排序；最后根據(jù)多項(xiàng)支持劃分成子事務(wù)塊，與FP?growth 算法類似，通過構(gòu)建MISFP?Tree 的后綴條件模式基以及條件模式樹來遞歸地挖掘頻繁模式。實(shí)驗(yàn)結(jié)果證明，該算法在多項(xiàng)支持的數(shù)據(jù)集上實(shí)現(xiàn)了高效的挖掘，且通過并行計(jì)算減少了執(zhí)行時(shí)間，適合于大數(shù)據(jù)分析應(yīng)用。

（3）并行Eclat 算法

Gole 等［59］提出的ClustBigFIM 是一種將聚類和頻繁模式挖掘混合的算法。算法利用MapRe?duce 計(jì)算模型首先對(duì)待處理大型數(shù)據(jù)集進(jìn)行K?means 聚類生成多個(gè)簇；其次對(duì)每一個(gè)簇并行執(zhí)行Apriori 算法挖掘頻繁k模式，使用生成的前綴樹得到TID 列表，并將其合并成一個(gè)全局TID 列表，以便于將水平格式轉(zhuǎn)換為垂直格式；最后通過對(duì)前綴樹執(zhí)行Eclat 算法挖掘頻繁k+1 項(xiàng)集。該算法使用K?means 算法對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，并對(duì)簇進(jìn)行頻繁項(xiàng)集挖掘，從而使得算法的執(zhí)行效率更加地高效，能更快地處理大數(shù)據(jù)集。

張春等［60］提出了一種基于MapReduce 的MREclatK 算法。該算法的思路比較簡(jiǎn)單，整個(gè)并行計(jì)算過程由一個(gè)MapReduce 作業(yè)迭代完成。具體地，首先執(zhí)行一次MapReduce 作業(yè)得到頻繁1 項(xiàng)集，接著在每次迭代過程中在Map 端將數(shù)據(jù)格式轉(zhuǎn)換為垂直格式，將剪枝后的頻繁1 項(xiàng)集和頻繁k項(xiàng)集求并集獲得候選k+1 項(xiàng)集，求交集獲得相應(yīng)的支持度，在Reduce 端合并候選k+1 項(xiàng)集得到全局支持度，通過比較MinSup 篩選得到頻繁k+1 項(xiàng)集。該算法將傳統(tǒng)Eclat 算法向MapReduce 計(jì)算模型上進(jìn)行了遷移，使得該算法能處理海量數(shù)據(jù)。

3.2.3 基于Spark 的并行關(guān)聯(lián)規(guī)則挖掘

（1）并行Apriori 算法

Rathee 等［61］提出的無(wú)需生成候選項(xiàng)集的算法R?Apriori 包含3 個(gè)步驟：第1 步獲取頻繁1 項(xiàng)集，Map 函數(shù)完成flatMap（）和map（）的轉(zhuǎn)換操作，Re?duce 函數(shù)調(diào)用reduceByKey（）計(jì)算每個(gè)項(xiàng)目的支持度并修剪出頻繁1 項(xiàng)集，存入布隆過濾器中；第2步Map 函數(shù)將事務(wù)中不包含在布隆過濾器的項(xiàng)目進(jìn)行修剪，利用修剪后的事務(wù)快速生成所有可能的項(xiàng)集對(duì)，再使用Reduce 函數(shù)來計(jì)算支持度并得到頻繁2 項(xiàng)集；第3 步由頻繁k項(xiàng)集迭代生成頻繁k+1 項(xiàng)集。該算法通過步驟2 消除了候選項(xiàng)集的生成，降低了計(jì)算復(fù)雜度，有效地提高了效率和性能。

Rathee 等［62］提出的動(dòng)態(tài)關(guān)聯(lián)規(guī)則挖掘算法Adaptive?Miner，改進(jìn)了R?Apriori 算法的頻繁模式挖掘過程，該算法根據(jù)上一次迭代中生成的頻繁項(xiàng)集數(shù)量分別計(jì)算R?Apriori 方法和常規(guī)Apriori 方法的時(shí)間消耗成本，動(dòng)態(tài)選擇當(dāng)下最優(yōu)的方法執(zhí)行此次迭代，使得其具有更高的挖掘速度和性能。

（2）并行FP?Growth 算法

Shi 等［63］提出了一種基于Spark 的分布式FP?Growth 算法（Distributed FP?growth algorithm based on Spark，DFPS）。該算法首先將全局頻繁1項(xiàng)集廣播到各節(jié)點(diǎn)；其次分配條件模式庫(kù)，將頻繁1 項(xiàng)集中各項(xiàng)目按支持度降序排列，除首個(gè)項(xiàng)目外為剩余各項(xiàng)目分配一個(gè)分區(qū)存放條件模式基，并將事物中的項(xiàng)目分發(fā)到相應(yīng)的分區(qū)；最后進(jìn)行并行挖掘，各分區(qū)間數(shù)據(jù)相互獨(dú)立，無(wú)需傳遞消息，獨(dú)立地使用傳統(tǒng)FP?growth 算法來挖掘頻繁項(xiàng)集。該算法在并行挖掘階段消除了節(jié)點(diǎn)間的通信負(fù)載，且無(wú)多余的候選項(xiàng)目集生成，使得DFPS 在大數(shù)據(jù)環(huán)境下的執(zhí)行速度、并行能力以及可擴(kuò)展性都得到了顯著提升。

吳磊［48］提出了PIITM 算法，該算法將IITM 算法遷移到Spark 平臺(tái)上對(duì)大規(guī)模數(shù)據(jù)進(jìn)行分布式并行挖掘。算法中各節(jié)點(diǎn)根據(jù)頻繁1 項(xiàng)集生成局部FP?Tree，并將生成的條件模式基根據(jù)后綴發(fā)送至相應(yīng)的節(jié)點(diǎn)上，數(shù)據(jù)相互獨(dú)立的各節(jié)點(diǎn)獨(dú)立地執(zhí)行IITM 算法挖掘局部頻繁項(xiàng)集，最后由Reduce 作業(yè)匯總各結(jié)果并篩選出頻繁項(xiàng)集。該算法充分考慮了節(jié)點(diǎn)間的負(fù)載均衡，且擴(kuò)展性強(qiáng)，適應(yīng)大規(guī)模集群。

（3）并行Eclat 算法

馮興杰等［64］提出了一種基于Spark 的Eclat 算法SPEclat，算法首先以（Item，BitSet）的形式獲取并存儲(chǔ)頻繁1 項(xiàng)集，其次將具有相同前綴的頻繁k項(xiàng)集劃分到同一節(jié)點(diǎn)上，最后在各節(jié)點(diǎn)上將頻繁k項(xiàng)集進(jìn)行自連接得到候選k+1 項(xiàng)集，并根據(jù)Min?Sup 得到頻繁k+1 項(xiàng)集。該算法優(yōu)化了支持度的計(jì)算，減少了候選項(xiàng)集的數(shù)量，在處理大規(guī)模數(shù)據(jù)方面具有較高的性能，但其沒有對(duì)節(jié)點(diǎn)進(jìn)行負(fù)載均衡處理。

Huang 等［65］提出了一種優(yōu)化的Eclat 算法（Bal?anced parallel eclat，BPEclat），該算法在SPEclat 算法基礎(chǔ)上，使用范圍劃分思想平衡計(jì)算節(jié)點(diǎn)負(fù)載，根據(jù)Apriori 算法的先驗(yàn)性質(zhì)刪除不滿足MinSup的非頻繁項(xiàng)集，對(duì)候選項(xiàng)集的生成采取了進(jìn)一步優(yōu)化。實(shí)驗(yàn)結(jié)果表明該算法通過減少候選項(xiàng)集的數(shù)量，提高了時(shí)間效率，在處理大數(shù)據(jù)時(shí)更為可靠，并具有較好的可擴(kuò)展性。

上述基于GPU、基于MapReduce 以及基于Spark 的并行關(guān)聯(lián)規(guī)則挖掘算法的主要思想是將經(jīng)典算法遷移至分布式計(jì)算平臺(tái)，但隨著數(shù)據(jù)量的不斷更新增加，將會(huì)產(chǎn)生海量的關(guān)聯(lián)規(guī)則，故如何壓縮關(guān)聯(lián)規(guī)則數(shù)量以及如何利用已有的結(jié)果來增量地進(jìn)行關(guān)聯(lián)規(guī)則的挖掘，都值得在未來深入探索。

4 結(jié)論

本文從數(shù)據(jù)挖掘角度介紹了大數(shù)據(jù)處理算法，分別從流式大數(shù)據(jù)分類算法、大數(shù)據(jù)聚類算法和大數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘3 方面梳理總結(jié)了近年來國(guó)內(nèi)外專家學(xué)者取得的進(jìn)展。隨著CUDA、MapRe?duce 和Spark 等分布式并行計(jì)算平臺(tái)的普遍應(yīng)用，面向大數(shù)據(jù)的數(shù)據(jù)挖掘算法的研究取得了巨大的進(jìn)步，但針對(duì)大數(shù)據(jù)真實(shí)性、高維和高噪聲等特點(diǎn)，仍需在如下方面開展進(jìn)一步研究：

（1）增量式更新算法。對(duì)于當(dāng)前大多面向大數(shù)據(jù)的數(shù)據(jù)挖掘算法都根據(jù)固定大小的數(shù)據(jù)集進(jìn)行分析和評(píng)估算法性能，但在信息時(shí)代新數(shù)據(jù)無(wú)時(shí)無(wú)刻不在增加，要求算法能對(duì)結(jié)果進(jìn)行動(dòng)態(tài)更新，因此需進(jìn)一步研究處理新舊數(shù)據(jù)變化的增量式更新算法。

（2）適用于高維數(shù)據(jù)的算法設(shè)計(jì)。目前大多面向大數(shù)據(jù)的數(shù)據(jù)挖掘算法都屬于低維度算法，而大數(shù)據(jù)普遍具有超高維度、高稀疏特性，其意味著數(shù)據(jù)的高復(fù)雜性和高計(jì)算成本，因此設(shè)計(jì)適用于處理高維數(shù)據(jù)的高性能算法值得在未來深入探索。

（3）分布式并行算法的設(shè)計(jì)和實(shí)現(xiàn)?，F(xiàn)有面向大數(shù)據(jù)的分布式并行算法大多是經(jīng)典算法向分布式計(jì)算平臺(tái)的遷移，并通過改進(jìn)數(shù)據(jù)劃分方法達(dá)到負(fù)載均衡和降低通信開銷的目的。鑒于這一問題，未來可以考慮根據(jù)大數(shù)據(jù)的特點(diǎn)并結(jié)合分布式計(jì)算平臺(tái)自身優(yōu)勢(shì)，設(shè)計(jì)并實(shí)現(xiàn)高性能、高并行性以及低復(fù)雜度的分布式并行算法。